Multidestination Message Passing in Wormhole k-ary n-cube Networks with Base Routing Conformed Paths
Multidestination Message Passing in Wormhole k-ary n-cube Networks with Base Routing Conformed Paths
复制标题
DOI：
10.1109/71.744844
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
D. Panda;Sanjay Singal;R. Kesavan
中科院分区：
文献类型：
--
作者：
D. Panda;Sanjay Singal;R. Kesavan
本文提出了一种新的基本路由一致路径（BRCP）模型，用于虫洞k元n立方体网络上的多目的地消息传递。此模型允许单播（单目的地）和多目的地消息在给定网络中共存，而不会导致死锁。该模型说明了几种常见的路由方案（确定性，以及自适应），并分析了相关的死锁自由属性。使用这个模型，一组新的算法，流行的集体通信业务，广播和组播，提出和评估。结果表明，所提出的算法可以大大减少这些操作的延迟相比，Umesh（单播为基础的多播）和汉密尔顿路径为基础的计划。一个非常有趣的结果表明，多播可以实现减少或接近恒定的延迟，参与多播的处理器的数量增加超过一定数量。它还表明，BRCP模型可以利用路由方案的自适应性，以进一步减少这些操作的延迟。多目的地机制和BRCP模型建立了一个新的基础，以提供快速和可扩展的集体通信支持虫洞路由系统。
This paper proposes multidestination message passing on wormhole k-ary n-cube networks using a new base-routing-conformed-path (BRCP) model. This model allows both unicast (single-destination) and multidestination messages to co-exist in a given network without leading to deadlock. The model is illustrated with several common routing schemes (deterministic, as well as adaptive), and the associated deadlock-freedom properties are analyzed. Using this model, a set of new algorithms for popular collective communication operations, broadcast and multicast, are proposed and evaluated. It is shown that the proposed algorithms can considerably reduce the latency of these operations compared to the Umesh (unicast-based multicast) and the Hamiltonian path-based schemes. A very interesting result that is presented shows that a multicast can be implemented with reduced or near-constant latency as the number of processors participating in the multicast increases beyond a certain number. It is also shown that the BRCP model can take advantage of adaptivity in routing schemes to further reduce the latency of these operations. The multidestination mechanism and the BRCP model establish a new foundation to provide fast and scalable collective communication support on wormhole-routed systems.