Optimizing the Bruck Algorithm for Non-uniform All-to-all Communication
Optimizing the Bruck Algorithm for Non-uniform All-to-all Communication
复制标题
优化非均匀全对全通信的布鲁克算法
DOI：
10.1145/3502181.3531468
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kumar, Sidharth
中科院分区：
文献类型：
--
作者：
Fan, Ke;Gilray, Thomas;Pascucci, Valerio;Huang, Xuan;Micinski, Kristopher;Kumar, Sidharth
在MPI中，集合例程MPI_Alltoall和MPI_Alltoallv在促进所有进程间数据交换方面起着重要作用。MPI_Alltoallv是MPI_Alltoall的推广，支持非均匀分布的数据交换。MPI的流行实现，如MPICH和OpenMPI，使用诸如扩展算法和Bruck算法的技术组合来实现MPI_Alltoall。与Bruck的对数复杂度（P：进程计数）相比，外插具有P的线性复杂度;在运行时基于数据块大小在这两种技术之间进行选择。但是，MPI_Alltoallv通常仅使用扩展算法的变体来实现，因此无法获得日志时间Bruck算法提供的性能优势（特别是对于较小的数据负载）。在本文中，我们首先实现并经验性地评估用于均匀和非均匀数据负载的Bruck算法的所有现有变体-这形成了我们自己的基于Bruck的非均匀全对全算法的基础。特别是，我们开发了两个开源的实现，填充Bruck和两阶段Bruck，有效地推广Bruck算法的非均匀的所有到所有的数据交换。我们经验验证的技术在三个超级计算机：西塔，科里，和踩踏，使用微基准和两个现实世界的应用程序：图挖掘和程序分析。我们执行弱和强的扩展研究的范围内的平均消息大小，不平衡程度和分布方案，并证明我们的技术优于供应商优化的Cray的MPI_Alltoallv高达50%的一些工作负载和规模。
In MPI, collective routines MPI_Alltoall and MPI_Alltoallv play an important role in facilitating all-to-all inter-process data exchange. MPI_Alltoallv is a generalization of MPI_Alltoall, supporting the exchange of non-uniform distributions of data. Popular implementations of MPI, such as MPICH and OpenMPI, implement MPI_Alltoall using a combination of techniques such as the Spread-out algorithm and the Bruck algorithm. Spread-out has a linear complexity in P, compared to Bruck's logarithmic complexity (P: process count); a selection between these two techniques is made at runtime based on the data block size. However, MPI_Alltoallv is typically implemented using only variants of the spread-out algorithm, and therefore misses out on the performance benefits that the log-time Bruck algorithm offers (especially for smaller data loads).In this paper, we first implement and empirically evaluate all existing variants of the Bruck algorithm for uniform and non-uniform data loads-this forms the basis for our own Bruck-based non-uniform all-to-all algorithms. In particular, we developed two open-source implementations, padded Bruck and two-phase Bruck, that efficiently generalize Bruck algorithm to non-uniform all-to-all data exchange. We empirically validate the techniques on three supercomputers: Theta, Cori, and Stampede, using both microbenchmarks and two real-world applications: graph mining and program analysis. We perform weak and strong scaling studies for a range of average message sizes, degrees of imbalance, and distribution schemes, and demonstrate that our techniques outperform vendor-optimized Cray's MPI_Alltoallv by as much as 50% for some workloads and scales.
登录
查看更多内容
DOI：
10.1109/hipc53243.2021.00033
发表时间：
2021-12
期刊：
2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC)
影响因子：
--
作者：
Oded Green;Zhihui Du;Sanyamee Patel;Zehui Xie;Hang Liu;David A. Bader
通讯作者：
Oded Green;Zhihui Du;Sanyamee Patel;Zehui Xie;Hang Liu;David A. Bader
OpenMP/MPI 混合编程模型的早期实验
DOI：
10.1007/978-3-540-79561-2_4
发表时间：
2008
期刊：
Journal of the Royal Statistical Society: Series B (Statistical Methodology)
影响因子：
--
作者：
E. Lusk;Anthony Chan
通讯作者：
Anthony Chan
DOI：
10.1002/cpe.3758
发表时间：
2016-12
期刊：
Concurrency and Computation: Practice and Experience
影响因子：
--
作者：
James Dinan;P. Balaji;Darius Buntinas;David Goodell;W. Gropp;R. Thakur
通讯作者：
James Dinan;P. Balaji;Darius Buntinas;David Goodell;W. Gropp;R. Thakur
使用 MPI-3 一侧实现高度可扩展的远程内存访问编程
DOI：
10.1145/2503210.2503286
发表时间：
2013
期刊：
2013 SC - International Conference for High Performance Computing, Networking, Storage and Analysis (SC)
影响因子：
--
作者：
Robert Gerstenberger;Maciej Besta;Torsten Hoefler
通讯作者：
Torsten Hoefler
HykSort：分布式内存架构上超立方体快速排序的新变体
DOI：
--
发表时间：
2013
期刊：
International Conference on Supercomputing
影响因子：
--
作者：
H. Sundar;D. Malhotra;G. Biros
通讯作者：
G. Biros