Multicast communication algorithm on a wormhole-routed star graph interconnection network

A contention-free and deadlock-free unicast based multicast algorithm is developed for star graph interconnection networks. The algorithm is developed recursively, and is based on the hierarchical properties of the star graph. The wormhole communication technique is used, and it is assumed that one input channel can drive only one output channel at a time. In order to eliminate contention in the multicast algorithm, the minimal deterministic routing algorithm is converted to a nonminimal one. For the proposed nonminimal routing, it is shown that the same number of virtual channels (n-1) required for minimal routing provides deadlock avoidance as well.