Multiple multicast with minimized node contention on wormhole k-ary n-cubenetworks

This paper presents a new approach to minimize node contention while perfor ming multiple multicast/broadcast on wormhole k-ary n-cube networks with ov erlapped destination sets. The existing multicast algorithms in the literat ure deliver poor performance under multiple multicast because these algorit hms have been designed with only single multicast in mind. The new algorith ms introduced in this paper do not use any global knowledge about the respe ctive destination sets of the concurrent multicasts. Instead, only local in formation and a source-specific partitioning approach are used. For systems supporting unicast message-passing, a new SPUmesh (Source-Partitioned Umes h) algorithm is proposed and is shown to be superior than the conventional Umesh algorithm [2] for multiple multicast. Two different algorithms, SQHL (Source-Quadrant Hierarchical Leader) and SCHL (Source-Centered Hierarchica l Leader), are proposed for systems with multidestination message-passing a nd shown to be superior than the HL scheme [3]. All of these algorithms per form 1) 5-10 times faster than the existing algorithms under multiple multi cast and 2) as fast as existing algorithms under single multicast. Furtherm ore, the SCHL scheme demonstrates that the latency of multiple multicast ca n, in fact, be reduced as the degree of multicast increases beyond a certai n number. Thus, these algorithms demonstrate significant potential to be us ed for designing fast and scalable collective communication libraries on cu rrent and future generation wormhole systems.