Architectural support for efficient multicasting in irregular networks

Parallel computing on networks of workstations is fast becoming a cost-effe ctive high-performance computing alternative to MPPs. Such a computing envi ronment typically consists of processing nodes interconnected through a swi tch-based irregular network. Many of the problems that were solved for regu lar networks have to be solved anew for these systems. One such problem is that of efficient multicast communication. In this paper, we propose two br oad categories of schemes for efficient multicasting in such irregular netw orks: network interface-based (NI-based) and switch-based. The NI-based mul ticasting schemes use the network interface of intermediate destinations fo r absorbing and retransmitting messages to other destinations in the multic ast tree. In contrast, the switch-based multicasting schemes use hardware s upport for packet replication at the switches of the network and a concept known as multidestination routing to convey a multicast message from one so urce to multiple destinations. We first present alternative schemes for eff icient multipacket forwarding at the NI and derive an optimal k-binomial mu lticast tree for multipacket NI-based multicast. We then propose two switch -based multicasting schemes that differ in the power of the encoding scheme and the complexity of the decoding logic at the switches. These multicasti ng schemes use path-based multidestination worms that can cover all nodes c onnected to switches along a valid unicast path and tree-based multidestina tion worms that can cover entire destination sets in a single phase using o ne worm, respectively. For each scheme, we describe the associated header e ncoding and decoding operation, the method for deriving multidestination wo rms that cover arbitrary multicast destination sets, and the multicasting s cheme using the derived multidestination worms. We then compare the NI-base d multicasting scheme to the switch-based multicasting schemes with path-ba sed and tree-based multidestination worms using simulation to determine the system parameters that affect each of the schemes and the range of system parameters for which each scheme performs best. Our results show that the s witch-based multicasting scheme using a single tree-based multidestination worm performs the best among the three schemes. However, the NI-based multi casting scheme is capable of delivering high performance compared to the sw itch-based multicast using path-based worms, especially when the software o verhead at the network interface is less than half of the overhead at the h ost. We therefore conclude that support for multicast at the NI is an impor tant first step to improving multicast performance. However, there is still considerable gain that can be achieved by supporting hardware multicast in switches. Finally, while supporting such hardware multicast, it is better to support schemes that can achieve multicast in one phase.