Unicast-based multicast algorithm in wormhole-routed star graph interconnection networks

✍ Scribed by Jelena Mišić

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 266 KB
• Volume: 24
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(98)00009-x

✦ Synopsis

A contention-free unicast-based multicast algorithm is developed for wormhole-routed star graph interconnection networks. Since the size of the buffers in the wormhole routing controller is much smaller than the size of the message, only destination nodes of multicast should receive message and store it in their local buffers; all other nodes can only relay message via their routing Ž controllers. For this reason, the neighbor-to-neighbor communications approach used for develop-. ing broadcast, scatter and total exchange algorithms is replaced with a hierarchical 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 implementation of the algorithm is developed. This methodology provides sufficient conditions for contention avoidance in the multicast algorithm regardless of the number of simultaneous unicasts permitted by the hardware architecture of the communication processor from the particular 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 number of virtual channels, n y 1 required by the minimal routing to avoid deadlock. This feature allows minimal and nonminimal routing to exist in the network at the same time.