UNICAST-BASED MULTICAST ALGORITHM IN WORMHOLE-ROUTED STAR GRAPH INTERCONNECTION NETWORKS

A contention-free unicast-based multicast algorithm is developed for w ormhole-routed star graph interconnection networks. Since the size of the buffers in the wormhole routing controller is much smaller than th e size of the message, only destination nodes of multicast should rece ive message and store it in their local buffers; all other nodes can o nly relay message via their routing controllers. For this reason, the neighbor-to-neighbor communications approach (used for developing broa dcast, scatter and total exchange algorithms) is replaced with a hiera rchical approach: a multicast tree composed of unicasts, in which only destination;nodes receive the message. Furthermore, a methodology for proving the contention-free property of the hierarchical multicast im plementation of the algorithm is developed. This methodology provides sufficient conditions for contention avoidance in the multicast algori thm regardless of the number of simultaneous unicasts permitted by the hardware architecture of the communication processor from the particu lar node. In order to eliminate contention in the multicast algorithm, a deterministic nonminimal routing algorithm is developed as well. It is shown that the proposed nonminimal routing uses only the same numb er of virtual channels. (n - 1) required by the minimal routing to avo id deadlock. This feature allows minimal and nonminimal routing to exi st in the network at the same time. (C) 1998 Elsevier Science B.V. All rights reserved.