Broadcasting schemes for hypercubes with background traffic
Optimal broadcasting schemes for interconnection networks (INs) are most essential for the efficient interprocess communication amongst parallel computers. In this paper two novel broadcasting schemes are proposed for hypercube computers with bursty background traffic and a single-port mode of message passing communication. The schemes utilize a maximum entropy (ME) based queue-by-queue decomposition algorithm for arbitrary queueing network models (QNMs) [D.D. Kouvatsos, I. Awan, Perform. Eval. 51 (2003) 191] and are based on binomial trees and graph theoretic concepts. It is shown that the overall cost of the one-to-all broadcasting scheme is given by max{?1,?2,,?2n/2}, where ?i, i=1,2,,2n/2 is the total weight at each leaf node of the binomial tree and n is the degree of the hypercube. Moreover, the upper bound of the total cost of the neighbourhood broadcasting scheme is determined by ?i=1Fmax{?i}, where F is an upper bound of the number of steps and is equal to 1.33?log2(n?1)?+1. Evidence based on empirical studies indicates the suitability of the schemes for achieving optimal broadcasting costs.
hypercubes interconnection network (in) queueing network model (qnm) binomial tree one-to-all broadcasting neighbourhood broadcasting maximum entropy (me) principle