Multidestination message passing in wormhole k-ary n-cube networks with base routing conformed paths

This paper proposes multidestination message passing on wormhole k-ary n-cu be networks using a new base-routing-conformed-path (BRCP) model. This mode l allows both unicast (single-destination) and multidestination messages to co-exist in a given network without leading to deadlock. The model is illu strated with several common routing schemes (deterministic, as well as adap tive), and the associated deadlock-freedom properties are analyzed. Using t his model, a set of new algorithms for popular collective communication ope rations, broadcast and multicast, are proposed and evaluated, it is shown t hat the proposed algorithms can considerably reduce the latency of these op erations compared to the Umesh (unicast-based multicast) [1] and the Hamilt onian path-based [2] schemes. Avery interesting result that is presented sh ows that a multicast can be implemented with reduced or near-constant laten cy as the number of processors participating in the multicast increases bey ond a certain number. It is also shown that the BRCP model can take advanta ge of adaptivity in routing schemes to further reduce the latency of these operations. The multidestination mechanism and the BRCP model establish a n ew foundation to provide fast and scalable collective communication support on wormhole-routed systems.