Efficient Broadcast and Multicast on Multistage Interconnection Networks using Multiport Encoding

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..