Bandwidth optimal all-reduce algorithms for clusters of workstations

By Pitch Patarasuk, Xin Yuan. 2009

496 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, Hardware and Architecture, ML Systems & Hardware

How researchers see this paper

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

In Computer Networks and Communications

In Electrical and Electronic Engineering

In Hardware and Architecture

In ML Systems & Hardware

Citations in the corpus

Mesh-TensorFlow: Deep Learning for Supercomputers (2018, background): “The physical network topology does affect performance; particularly important is the performance of MPI Allreduce, grouped by splitting the mesh by a subset of the dimensions, which can be very efficient [4] [5] if each such group is physically connected.”
Beyond human-level accuracy: computational challenges in deep learning (2019, methodology): “We model a synchronous stochastic gradient descent (SGD) approach implemented using a ring-allreduce [25].”
Deep Speech 2 : End-to-End Speech Recognition in English and Mandarin (2015, background): “aining with a minibatch of 512 or 1024, in order to converge to the best result. Since all-reduce is critical to the scalability of our training, we wrote our own implementation of the ring algorithm [48, 65] for higher performance and better stability. Our implementation avoids extraneous copies be”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “In AllReduce Stochastic Gradient Descent implementation (AllReduce-SGD) (Luehr, 2016; Patarasuk and Yuan, 2009; MPI contributors, 2015), the update rule per iteration is exactly the same as in S-PSGD, so they share the same convergence rate.”
Horovod: fast and easy distributed deep learning in TensorFlow (2018, methodology): “The algorithm was based on the approach introduced in the 2009 paper by Patarasuk and Yuan [9].”
Deep Leakage from Gradients (2019, background): “orithm level [6,10,15,22,30,30]. In general, distributed training can be classiﬁed into two categories: with a parameter server (centralized) [14,18,22] and without a parameter server (decentralized) [3,29,31]). In both schemes, each node ﬁrst performs the computation to reﬁne its local copy of the ”
Demystifying Parallel and Distributed Deep Learning (2018, background): “This algorithm achieves the lower bound [198] but may be harder to implement and tune.”
Practical Federated Gradient Boosting Decision Trees (2019, methodology): “Then we build L global hash tables using an AllReduce operation, (Patarasuk and Yuan 2009).”
HetPipe: Enabling Large DNN Training on (Whimpy) Heterogeneous GPU Clusters through Integration of Pipelined Model Parallelism and Data Parallelism (2020, methodology): “Our experimental results demonstrate that the performance of HetPipe is better than that of the state-of-the-art DP via Horovod [50] that uses AllReduce communication [45].”
Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning (2019, background): “Federated learning is gaining increasing attention thanks to its unique advantages over data-center-based training (Li et al., 2014; Patarasuk & Yuan, 2009): sensitive user data do not need to be uploaded to a data center, which better motivates users to participate (Shokri & Shmatikov, 2015).”
GradiVeQ: Vector Quantization for Bandwidth-Efficient Gradient Aggregation in Distributed CNN Training (2018, background): “Parallel aggregation, on the other hand, aims at minimizing communication congestion by shifting from centralized aggregation at a parameter server to distributed methods such as ring all-reduce (RAR) [29, 30, 31, 32].”
A Unified Architecture for Accelerating Distributed DNN Training in Heterogeneous GPU/CPU Clusters (2020, background): “With B network bandwidth, the time required is 2(n 1)M/nB, which is proved to be the optimal in topologies with uniformed link bandwidth [54], assuming no additional resources.”
Heterogeneity-Aware Asynchronous Decentralized Training (2019, methodology): “Thus, it is supported by many popular machine learning frameworks such as TensorFlow [1], MXNet [6] and PyTorch [38].”
On the Convergence of Quantized Parallel Restarted SGD for Serverless Learning (2020, methodology): “Alternatively, the workers are also able to preserve a consistent model using AllReduced (AR) paradigm without the central node [14].”
Gradient Compression Supercharged High-Performance Data Parallel DNN Training (2021, background): “While this design is bandwidth-optimal [54], such a coarse-grained approach fails to hide the compression-related overhead behind the communication overhead.”
Hop: Heterogeneity-aware Decentralized Training (2019, methodology): “The current approach to mitigate the communication bottle-neck is to apply ring All-Reduce [12,22] among all workers, without using PS.”
Scaling Distributed Machine Learning with In-Network Aggregation (2019, unknown): “This is a significant improvement over the equivalent cost for bandwidth-optimal all-reduce, which is 4|U | n 1 n [79].”