Efficient Broadcast and Multicast on Multistage Interconnection Networks using Multiport Encoding

Copyright [©] (1998) by IEEE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

This paper proposes a new approach for implementing fast multicast and broadcast in unidirectional and bidirectional multistage interconnection networks (MINs) with multiport encoded multidestination worms. For a MIN with n stages such worms use n header flits each. One flit is used for each stage of the network and indicates the output ports to which a multicast message needs to be replicated. A multiport encoded worm with (d1, d2..., dn, 1 < di < k) degrees of replication for the respective stages is capable of covering (d1 x d2 x...x dn) distinations with single communication start-up. In this paper a switch architecture is proposed for implementing multidestination worms without deadlock. Three grouping algorithms of varying complexity are presented to derive the associated multiport encoded worms for a multicast to an arbitrary set of destinations. Using these worms a multinomial tree-based scheme is proposed to implement the multicast. This scheme significantly reduces broadcast/multicast latency compared to schemes using unicast messages. Simulation studies for both unidirectional and bidirectional MIN systems indicate that improvement in broadcast/multicast latency up to a factor of 4 is feasible using the new approach. Interestingly, this approach is able to implement multicast with reduced latency as the number of destinations increases beyond a certain number. Compared to implementing unicast messages this approach requires little additional logic at the switches. Thus, the scheme demonstrates significant potential..

By: Rajeev Sivaram (The Ohio State Univ.), Dhabaleswar K. Panda (The Ohio State Univ.) and Craig B. Stunkel

Published in: IEEE Transactions on Parallel and Distributed Systems, volume 9, (no 10), pages 1004-28 in 1998

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .