Efficient multicast on irregular switch-based cut-through networks with up-down routing

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.