Broadcasting schemes for hypercubes with background traffic
Optimal broadcasting schemes for interconnection networks (INs) are most essential for the efficient interprocess communication amongs: 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 ΣFi = 1 max{ω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.