Dk. Panda et al., Multidestination message passing in wormhole k-ary n-cube networks with base routing conformed paths, IEEE PARALL, 10(1), 1999, pp. 76-96
Citations number
31
Categorie Soggetti
Computer Science & Engineering
Journal title
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
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.