DESIGN AND PERFORMANCE ANALYSIS OF MULTISTAGE INTERCONNECTION NETWORKS USING A RECURSIVE MULTICAST ALGORITHM

In this paper, we study issues of the multicast communication in the m ultistage interconnection networks (MINs) for large-scale multicompute rs. In addition to point-to-point communication among processing nodes , efficient collective communication is critical to the performance of multicomputers. Multicast communication in which the same packet is d elivered from a source node to an arbitrary number of destination node s is fundamental in supporting collective communication primitives inc luding broadcast, reduction, and barrier synchronization operations. T his paper presents a new approach to support multicast communication, on the basis of a restricted address encoding scheme which constructs a short fixed-size multicast header, and a recursive scheme that recyc les a multicast packet one or more times through the MIN to send it to the desired destination nodes. We propose a recursive multicast algor ithm which provides deadlock-freedom for multiple multicast packets in MIN-based multicomputers. We also present performance model for the u nbuffered MIN using the multicast algorithm and analyze its performanc e in terms of the network throughput, where several multicast communic ations are considered. The proposed algorithm can be easily applied to wormhole or virtual cut-through MIN-based multicomputers.