Efficient all-to-all broadcast in all-port mesh and torus networks
Efficient all-to-all broadcast in all-port mesh and torus networks
复制标题
DOI：
10.1109/hpca.1999.744382
复制
发表时间：
1999-01
期刊：
影响因子：
--
通讯作者：
Yuanyuan Yang;Jianchao Wang
中科院分区：
文献类型：
--
作者：
Yuanyuan Yang;Jianchao Wang
全对全通信是并行计算中最密集的通信模式之一，并且出现在许多重要的应用中。在本文中，我们提出了一种新的全对全广播算法在全端口网状和环面网络。与现有的全对全广播算法不同，新算法利用了消息切换时间和传输时间的重叠，实现了全对全广播的最优传输时间。此外，在大多数情况下，总通信延迟在一个小的恒定范围内接近所有对所有广播的下限。最后，该算法概念简单，并且对于每条消息和每个节点都是对称的，因此可以很容易地在硬件上实现，并在实践中达到最佳效果。
All-to-all communication is one of the most dense communication patterns and occurs in many important applications in parallel computing. In this paper, we present a new all-to-all broadcast algorithm in all-port mesh and torus networks. Unlike existing all-to-all broadcast algorithms, the new algorithm takes advantage of overlapping of message switching time and transmission time, and achieves optimal transmission time for all-to-all broadcast. In addition, in most cases, the total communication delay is close to the lower bound of all-to-all broadcast within a small constant range. Finally, the algorithm is conceptually simple, and symmetrical for every message and every node so that it can be easily implemented in hardware and achieves the optimum in practice.