R. Sivaram et al., EFFICIENT BROADCAST AND MULTICAST ON MULTISTAGE INTERCONNECTION NETWORKS USING MULTIPORT ENCODING, IEEE transactions on parallel and distributed systems, 9(10), 1998, pp. 1004-1028
Citations number
37
Categorie Soggetti
Computer Science Theory & Methods","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
This paper proposes a new approach for implementing fast multicast and
broadcast in unidirectional and bidirectional multistage interconnect
ion 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 it indicates the output ports t
o which a multicast message needs to be replicated. A multiport encode
d worm with (d(1), d(2)..., d(n), 1 less than or equal to d(i) less th
an or equal to k) degrees of replication for the respective stages is
capable of covering (d(1) x d(2) x...x d(n)) destinations with a singl
e communication start-up. In this paper, a switch architecture is prop
osed for implementing multidestination worms without deadlock. Three g
rouping algorithms of varying complexity are presented to derive the a
ssociated 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 reduce
s broadcast/multicast latency compared to schemes using unicast messag
es. Simulation studies for both unidirectional and bidirectional MIN s
ystems indicate that improvement in broadcast/multicast latency up to
a factor of four is feasible using the new approach. Interestingly, th
is 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 addition
al logic at the switches. Thus, the scheme demonstrates significant po
tential for implementing efficient collective communication operations
on current and future MIN-based systems.