K. Qiu (Canada) and S.K. Das (USA)
Parallel algorithm, interconnection network, neighbourhood broadcasting.
The neighbourhood broadcasting problem in an intercon nection network is defined as sending a fixed sized message from the source node to all its neighbours such that in one time unit, a node can send to or receive from exactly one of its neighbours a datum of constant size. Previously, this problem has been studied for the hypercube, the star inter connection network (a Cayley graph), and a special family of Cayley graphs of permutation groups formed by trans positions. All these algorithms are asymptotically optimal and use binomial trees and other special properties of the underlying interconnection networks. As a result, differ ent schemes are required for different interconnection net works and routings for different nodes are also different. In this paper, we show that a simple optimal algorithm we proposed recently for the star network is general enough to be applied to a broader family of Cayley graphs such as the hypercube and pancake interconnection network (for which no previous neighbourhood broadcasting algorithm is known), resulting in simple and asymptotically optimal algorithms. Thus, we have a unified scheme for optimal neighbourhood broadcasting that applies to several inter connection networks with uniform routing.
Important Links:
Go Back
