PaperlayerView exact revision on arXiv

Source-linked AI summary

A Distributed Synchronous SGD Algorithm with Global Top-$k$ Sparsification for Low Bandwidth Networks

Shaohuai Shi, Qiang Wang, Kaiyong Zhao, Zhenheng Tang, Yuxin Wang, Xiang Huang, Xiaowen Chu

arXiv:1901.04359v2cs.DCcs.LG

TL;DR

Distributed S-SGD needs substantial gradient communication, while existing Top-k aggregation remains inefficient because irregular indices lead to O(kP) communication. The paper introduces gTop-k S-SGD, which selects global top-k gradients and reduces aggregation complexity to O(k log P). Experiments report nearly consistent convergence with S-SGD and higher scaling efficiency on a 32-GPU, 1-Gbps Ethernet cluster.

  • Problem

    Irregular indices make sparse Top-k gradients difficult to aggregate, and AllGather-based methods have O(kP) communication that is inefficient with many workers.

  • Method

    gTop-k S-SGD selects the global k largest absolute gradients from P workers and aggregates them with a tree-based gTopKAllReduce algorithm.

  • Results

    gTop-k S-SGD shows nearly consistent convergence with S-SGD and achieves 2.7-12.8x speedup over S-SGD on a 32-node cluster connected by 1-Gbps Ethernet.

  • Takeaways & Limitations

    Reducing aggregation complexity to O(k log P) gives gTop-k S-SGD higher scaling efficiency than S-SGD and Top-k S-SGD in the evaluated low-bandwidth cluster.

Abstract

from arXiv · show

Distributed synchronous stochastic gradient descent (S-SGD) has been widely used in training large-scale deep neural networks (DNNs), but it typically requires very high communication bandwidth between computational workers (e.g., GPUs) to exchange gradients iteratively. Recently, Top-$k$ sparsification techniques have been proposed to reduce the volume of data to be exchanged among workers. Top-$k$ sparsification can zero-out a significant portion of gradients without impacting the model convergence. However, the sparse gradients should be transferred with their irregular indices, which makes the sparse gradients aggregation difficult. Current methods that use AllGather to accumulate the sparse gradients have a communication complexity of $O(kP)$, where $P$ is the number of workers, which is inefficient on low bandwidth networks with a large number of workers. We observe that not all top-$k$ gradients from $P$ workers are needed for the model update, and therefore we propose a novel global Top-$k$ (gTop-$k$) sparsification mechanism to address the problem. Specifically, we choose global top-$k$ largest absolute values of gradients from $P$ workers, instead of accumulating all local top-$k$ gradients to update the model in each iteration. The gradient aggregation method based on gTop-$k$ sparsification reduces the communication complexity from $O(kP)$ to $O(k\log P)$. Through extensive experiments on different DNNs, we verify that gTop-$k$ S-SGD has nearly consistent convergence performance with S-SGD, and it has only slight degradations on generalization performance. In terms of scaling efficiency, we evaluate gTop-$k$ on a cluster with 32 GPU machines which are interconnected with 1 Gbps Ethernet. The experimental results show that our method achieves $2.7-12\times$ higher scaling efficiency than S-SGD and $1.1-1.7\times$ improvement than the existing Top-$k$ S-SGD.

I. INTRODUCTION

Distributed S-SGD accelerates DNN training but is constrained by gradient-communication overhead, especially when sparse gradients have irregular indices. The paper proposes gTop-k S-SGD, which selects global largest gradients to reduce communication and improves scaling efficiency on low-bandwidth networks.

  • Motivation: S-SGD distributes mini-batch computation across workers but requires gradient averaging communications that can become a system bottleneck.Communication overhead grows as computational units improve faster than network speed.
  • Motivation: Top-k sparsification reduces transferred gradient values, but irregular nonzero indices prevent direct use of dense AllReduce for aggregation.Sparse aggregation therefore requires handling both gradient values and their indices.
  • gTop-k S-SGD: Global Top-k selects the k largest absolute gradients from accumulated worker results because not all locally selected gradients contribute equally to model updates.This further sparsifies the accumulated gradients before updating the model.
  • gTop-k S-SGD: gTopKAllReduce uses a tree structure to reduce gradient-aggregation communication complexity from O(kP) to O(k log P).The method targets the worker-count scalability problem of AllGather-based Top-k aggregation.
  • Evaluation: On a 32-node GPU cluster connected by 1-Gbps Ethernet, gTop-k S-SGD achieved 2.7-12.8x speedup over S-SGD and was generally around 1.5 times faster than Top-k S-SGD.The implementation used PyTorch and MPI across experiments with various DNNs and datasets.

II. PRELIMINARIES

DNN training uses layered transformations and mini-batch SGD, while synchronous data-parallel training averages gradients across workers at each iteration. This averaging introduces communication costs that can limit scaling.

  • DNNs: DNNs consist of hierarchical layers whose trainable parameters are updated through mini-batch SGD and backpropagation.Each layer applies a transformer function, such as an inner product or convolution with an activation function.
  • Mini-batch SGD: Each training iteration reads a mini-batch, performs feed-forward computation, and computes gradients through backward propagation.The feed-forward and backward-propagation phases dominate single-worker iteration time.
  • Synchronous SGD: S-SGD assigns different mini-batches to P workers, then averages their gradients to update a consistent model.Workers begin each iteration with the same model and calculate gradients in parallel.
  • Synchronous SGD: Gradient averaging requires communication because workers store gradients separately, making communication a potential system bottleneck.The average S-SGD iteration time is approximated as t_iter = t_f + t_b + t_c.

D. DenseAllReduce

DenseAllReduce directly implements dense synchronous gradient aggregation using a ring-based AllReduce collective. Its communication cost depends on worker count and model or gradient size.

  • DenseAllReduce: The summation of worker gradients can be implemented directly with an AllReduce collective called DenseAllReduce.The paper identifies ring-based AllReduce, also included in NCCL, as an efficient dense-GPU-cluster implementation.
  • DenseAllReduce: Ring-based AllReduce communication is modeled using latency α and per-element transmission time β.α is message startup latency, while β is transmission time per element.
  • DenseAllReduce: Top-k S-SGD algorithms use sparse gradient values and indices instead of dense gradients, requiring a distinct aggregation procedure.Algorithm 1 specifies the dataset, initialized weights, mini-batch size, worker count, iterations, and selected-gradient count as inputs.
  • DenseAllReduce: The sparse aggregation procedure accumulates selected values at their worker-provided indices and averages the resulting gradient.The algorithm updates indexed entries, divides by P, and returns the aggregated gradient.

E. Top-k sparsification

Top-k sparsification reduces communicated gradients by retaining only the largest absolute values, but irregular indices make aggregation difficult. Existing AllGather-based aggregation becomes less attractive as the worker count grows.

  • Top-k sparsification: Top-k sparsification communicates only the k largest absolute gradient values from each worker and accumulates zeroed values as residuals.Prior studies report little impact on model convergence and accuracy.
  • Aggregation challenge: Sparse gradients from different workers may have inconsistent indices, making efficient TopKAllReduce implementations non-trivial.The irregular index structure prevents direct reuse of dense-gradient aggregation.
  • Aggregation challenge: AllGather-based TopKAllReduce transfers sparse values together with their corresponding indices, with both vectors having size k.The communication model evaluates the cost of gathering 2k values.
  • Scalability: As P increases, the AllGather-based Top-k communication time t_tar_c grows linearly, reducing the benefit of sparsification.The paper introduces global Top-k sparsification to address this scalability problem.

III. METHODOLOGY

The methodology observes that only a subset of locally selected gradients contributes to updates, then introduces global Top-k sparsification to retain the globally largest values. The proposed procedure maintains residuals while updating the model with the global selection.

  • III. METHODOLOGY: The methodology assumes P is a power of 2 while analyzing Top-k sparsification and presenting global Top-k aggregation.The section first examines observations from Top-k S-SGD before presenting the proposed algorithm.
  • Observations from Top-k sparsification: Among the K non-zero gradients formed by aggregating local Top-k selections, only a smaller number is needed for model updates.Here k ≤ K ≤ k×P, so the aggregated sparse gradient can be further sparsified.
  • Observations from Top-k sparsification: The convergence experiment uses ResNet-20 on 4 workers with k = 0.001×m elements updated at each iteration.The figure caption identifies this setting as the convergence evaluation shown in Fig. 1.
  • Naive gTop-k: The naive gTop-k procedure selects local top-k gradients, performs sparse aggregation, then selects a global threshold for the model update.It stores local residuals before aggregation and extra residuals after applying the global mask.
  • Naive gTop-k: After global masking, each worker updates its parameters with the selected global gradients and retains unselected contributions as residuals.The algorithm applies the global mask before the parameter update and stores extra residuals using its complement.

B. The key idea of gTop-k

gTop-k selects the global k largest-magnitude gradients from distributed sparse vectors instead of aggregating every worker’s local top-k values. A tree-based implementation repeatedly applies pairwise top-k selection to reduce the global result across workers.

  • Global selection: gTop-k selects the k largest absolute values from the sparsified gradients produced by all workers for model updates.This avoids retaining all possible kP nonzero gradients after local sparsification.
  • Pairwise operation: The pairwise Top-k operation merges two k-sparse vectors, retains their k largest-magnitude entries, and preserves the corresponding indices.It can be implemented by exchanging the vectors and locally selecting from at most 2k nonzero values.
  • Tree aggregation: gTopKAllReduce applies pairwise top-k operations in a tree to compute the global sparse vector across distributed workers.The result is stored at the first worker and then broadcast to the others, with a mask recording selected indices.
  • Tree aggregation: For 8 workers, the tree selects the global Top-k in log2P = log2 8 = 3 communication rounds.The figure illustrates the composition eG = eG1 ⊤ eG2 ⊤ ... ⊤ eG8.

D. Communication complexity analysis of gTopKAllReduce

gTopKAllReduce performs logarithmically many communication rounds and has lower communication complexity than TopKAllReduce, particularly as the worker count grows.

  • Communication cost: gTopKAllReduce takes log P rounds to compute the global top-k result and then broadcasts that result to all workers.Each reduction round transfers 2k elements, and the broadcast uses the flat-tree algorithm.
  • Scaling: The communication complexity of gTopKAllReduce is much lower than TopKAllReduce, especially when P is large.The analysis targets the high impact of the worker count on the time cost of irregular-index gradient aggregation.

E. gTop-k S-SGD with gTopKAllReduce

The gTop-k S-SGD algorithm replaces local sparse-gradient aggregation with gTopKAllReduce while retaining residual gradients and updating the model with the selected global gradients. The evaluation uses diverse DNNs on a 32-node, 1-Gbps Ethernet cluster.

  • Algorithm: gTop-k S-SGD invokes gTopKAllReduce to aggregate selected sparse gradients, replacing the earlier Top-k aggregation step.The added computation is described as much smaller than the communication overhead.
  • Algorithm: The training procedure stores residual gradients, computes a global mask, stores extra residuals, and updates weights with the selected gradients.The algorithm samples worker-local mini-batches and selects k gradients before global aggregation.
  • Evaluation: Experiments evaluate convergence, communication time, and training efficiency against dense and Top-k S-SGD baselines.The study uses multiple DNNs and datasets in a 32-node cluster connected by 1-Gbps Ethernet.

B. Convergence comparison

Across image-classification and language-modeling experiments, gTop-k S-SGD generally maintains convergence close to dense S-SGD. Communication experiments show its advantage increases with more workers or larger messages.

  • Cifar-10: ResNet-20 converges almost identically to dense S-SGD, while VGG-16 converges slightly better than the baseline.Both comparisons use the Cifar-10 dataset with four workers.
  • ImageNet: AlexNet and ResNet-50 have convergence rates close to their baselines, with ResNet-50 converging faster and AlexNet slightly worse at ρ = 0.001.The AlexNet difference may reflect unbalanced parameter distributions across layer types.
  • Language modeling: LSTM-PTB convergence is almost the same as S-SGD at density 0.005.This result is reported for the PTB language-modeling dataset with four workers.
  • Overall convergence: Across three DNN types and datasets, gTop-k S-SGD keeps model convergence very close to dense S-SGD.The paper summarizes the method as not damaging the model during training.
  • Communication performance: gTopKAllReduce becomes more efficient than TopKAllReduce as the number of workers or message size increases.TopKAllReduce is slightly faster with few workers, but becomes much worse when the node count reaches 16.

D. Scaling efficiency

gTop-k S-SGD improves scaling efficiency over dense and conventional Top-k S-SGD on low-bandwidth GPU clusters, while communication remains a major cost for some models.

  • Scaling results: 6.7× faster than dense S-SGD and 1.4× faster than Top-k S-SGD on average when scaling to 32 GPUs.On AlexNet, the improvements reach up to 12× over S-SGD and 1.7× over Top-k S-SGD.
  • Scaling results: gTop-k S-SGD maintains more stable scaling efficiency as the number of GPUs increases, whereas Top-k S-SGD declines at 32 GPUs.Dense S-SGD has the worst scaling efficiency because full gradients make communication slow on 1GbE clusters.
  • Experimental setup: The compared scaling-efficiency methods are DenseAllReduce, TopKAllReduce, and gTopKAllReduce with k = 0.001 × m.The figure reports scaling efficiency, where higher values are better.
  • Experimental setup: The experiments evaluate system throughput on a 32-GPU cluster and report processed images per second, including gTop-k speedups over dense and Top-k methods.The throughput notation uses g/d for gTop-k versus dense and g/t for gTop-k versus Top-k.
  • Time breakdown: For VGG-16 and AlexNet, communication overhead is much larger than computation because both models contain three large fully connected layers.The time breakdown separates computation, compression, and gTop-k communication.

V. DISCUSSION

The discussion examines how density and mini-batch size affect convergence and generalization, alongside the communication-scaling motivation for gTop-k. It also identifies future work on overlapping communication with computation.

  • Convergence sensitivity to density: A density of 0.0005 does not substantially affect convergence for VGG-16 and ResNet-20 on CIFAR-10 with four workers.Higher sparsification can improve scaling efficiency, but density must be balanced against convergence speed.
  • Convergence sensitivity to density: The upper bound of sparsity must be respected because excessive sparsity can hurt model convergence.The discussion frames density selection as a trade-off between sparsification and convergence speed.
  • Mini-batch sensitivity: With P = 32 and mini-batch size 1024, gTop-k causes approximately 9% accuracy degradation on ResNet-20 and approximately 1% on VGG-16 versus Top-k.The comparison uses top-1 validation accuracy on CIFAR-10 after 120 epochs.
  • Mini-batch sensitivity: Reducing the mini-batch size gives gTop-k more updates per weight and can improve ResNet-20 accuracy, while larger mini-batches can increase degradation.The paper attributes this difference to gTop-k updating k weights per iteration instead of k × P weights.
  • Communication motivation: Top-k aggregation communicates O(kP), whereas gTop-k reduces the aggregation complexity to O(k log P) by further sparsifying accumulated gradients.The method selects the largest absolute gradients before updating the model.
  • Future work: Future work will investigate layer-wise sparsification to overlap communication overhead with computation tasks.The paper identifies pipelining between computation and communication as a way to increase scalability.
Loading 1901.04359v2…