Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems

By Jehoshua Bruck, C. T. Ho, Shlomo Kipnis, Eli Upfal, Derrick Weathersby. 1997

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Song Han
2. Ji Lin
3. Yujun Lin
4. Huizi Mao
5. Ze Liu
6. Yunhe Wang
7. Han Hu
8. Fan Yang

Citations in the corpus

• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training (2017, methodology): “With the all-reduce communication model [31, 32], the density of sparse data doubles at every aggregation step in the worst case.”
• Performance analysis of MPI collective operations (2005, methodology): “Bruck algorithm requires log 2 P communication steps.”
• Optimization of Collective Communication Operations in MPICH (2005, methodology): “2 Bruck Algorithm The Bruck algorithm for allgather [7] (referred to as concatenation) is a variant of the dissemination algorithm for barrier, described in [10].”
• Optimization of Collective Reduction Operations (2004, methodology): “Collective algorithms for wide-area cluster are developed in [5,7,8], further protocol tuning can be found in [3, 4 ,9,12], and automatic tuning in [13].”
• Tutel: Adaptive Mixture-of-Experts at Scale (2022, methodology): “3Message Passing Interface (MPI) [41] also has developed various Allto-All algorithms [5, 35, 42], but we only discuss NCCL in this work as it outperforms MPI in most DL scenarios.”
• A Unified Coded Deep Neural Network Training Strategy based on Generalized PolyDot codes (2018, methodology): “Using efficient all-to-all communication protocols [76], [78] popular in parallel computing, the communication cost of all nodes broadcasting its own sub-vector s̃p of length N m to all other nodes has a communication cost of α logP + 2β N m P = Θ( m P ) using All-Gather protocol.”
• The analysis of a plane wave pseudopotential density functional theory code on a GPU machine (2013, methodology): “In OpenMPI and othermajorMPI implementations, pairwise is commonly used for large message all-to-all communication, while some other algorithms such as the Bruck algorithm [22] should be used for short messages.”