R. Kesavan et Dk. Panda, Efficient multicast on irregular switch-based cut-through networks with up-down routing, IEEE PARALL, 12(8), 2001, pp. 808-828
Citations number
43
Categorie Soggetti
Computer Science & Engineering
Journal title
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
The irregular switch-based network of workstations is fast becoming a cost-
effective platform for high performance computing. This paper presents effi
cient multicasting with reduced link contention on irregular switch-based c
ut-through interconnection using the popular up*/down* (UD) routing and uni
cast message passing. First, it is proven that, for an arbitrary irregular
network with UD routing, it Is not possible to create an ordered list of no
des to implement an arbitrary multicast in a link contention-free manner wi
th a minimal number of communication steps. Next, three different multicast
algorithms are proposed with their respective node orderings to reduce lin
k contention: switch-based ordering (SO), switch-based hierarchical orderin
g (SHO), and chain concatenation ordering (CCO). A variation of the binomia
l tree-based communication pattern, with unicast message passing, is used o
n the above orderings to implement multicast. Then, the problem of node con
tention is described in the case when multiple multicasts occur concurrentl
y in a system. Using source-based information, the CCO algorithm is modifie
d to propose a source-partitioned chain concatenation ordering (SPCCO) algo
rithm. It is also shown how the SPCCO algorithm reduces the effect of node
contention at the cost of link contention. Using detailed simulation experi
ments, the proposed multicast algorithms are compared with each other as we
ll as with the naive random ordering (RO) algorithm for a range of system s
izes, switch sizes, message lengths, input buffer sizes, degrees of connect
ivity, destination set sizes, and communication start-up times. For the cas
e of single multicast, the CCO algorithm is shown to be the best to Impleme
nt multicast with reduced link contention and minimum latency. For the case
of multiple multicasts, the SPCCO algorithm is shown to be the best when t
he start-up overhead dominates the propagation overhead and the CCO algorit
hm Is shown to be the best otherwise. The results also highlight the import
ance of reducing link contention when designing efficient multicast, even f
or systems with large input buffers in the switches. Thus, these results de
monstrate significant potential to be applied to current and future generat
ion NOW systems with irregular interconnection.