Implementing multidestination worms in switch-based parallel systems: Architectural alternatives and their impact

Multidestination message passing has been proposed as an attractive mechani sm for efficiently implementing multicast and other collective operations o n direct networks. However, applying this mechanism to switch-based paralle l systems is nontrivial. In this paper, we propose alternative switch archi tectures with differing buffer organizations to implement multidestination worms on switch-based parallel systems. First, we discuss issues related to such implementation (deadlock-freedom, replication mechanisms, header enco ding, and routing). Next, we demonstrate how an existing central-buffer-bas ed switch architecture supporting unicast message passing can be enhanced t o accommodate multidestination message passing. Similarly, implementing mul tidestination worms on an input-buffer-based switch architecture is discuss ed, and two architectural alternatives are presented that reduce the wiring complexity in a practical switch implementation. The central-buffer-based and input-buffer-based implementations are evaluated against each other, as well as against the corresponding software-based schemes. Simulation exper iments under a range of traffic (multiple multicast, bimodal, varying degre e of multicast, and message length) and system size are used for evaluation . The study demonstrates the superiority of the central-buffer-based switch architecture. It also indicates that under bimodal traffic the central-buf fer-based hardware multicast implementation affects background unicast traf fic less adversely compared to a software-based multicast implementation. T hese results show that multidestination message passing can be applied easi ly and effectively to switch-based parallel systems to deliver good multica st and collective communication performance.