PaperlayerView exact revision on arXiv

Source-linked AI summary

SparCML: High-Performance Sparse Communication for Machine Learning

Cedric Renggli, Saleh Ashkboos, Mehdi Aghagolzadeh, Dan Alistarh, Torsten Hoefler

arXiv:1802.08021v3cs.DCstat.ML

TL;DR

SPARCML addresses the allreduce bottleneck in data-parallel machine learning by combining sparse communication, quantization, and relaxed or asynchronous operations. Its implementations achieve substantial speedups in synthetic and real workloads, while its theory guarantees convergence to a stationary point under stated assumptions.

  • Problem

    The global allreduce needed to synchronize distributed machine-learning gradients is a scalability bottleneck, while existing sparsification can densify across nodes and quantization has limited compression.

  • Method

    SPARCML extends MPI with sparse collective operations, error-compensated sparsification, stochastic quantization, non-blocking communication, and low-precision representations.

  • Results

    Across applications, SPARCML reports order-of-magnitude speedups, including almost 10× faster ASR LSTM training on 128 GPUs without significant accuracy loss.

  • Takeaways & Limitations

    SPARCML can provide substantial communication and end-to-end training-time reductions for machine-learning workloads that expose useful sparsity.

  • Takeaways & Limitations

    The convergence theory guarantees only ergodic convergence to a stationary point and does not specify precise practical hyperparameters beyond diminishing learning rates.

Abstract

from arXiv · show

Applying machine learning techniques to the quickly growing data in science and industry requires highly-scalable algorithms. Large datasets are most commonly processed "data parallel" distributed across many nodes. Each node's contribution to the overall gradient is summed using a global allreduce. This allreduce is the single communication and thus scalability bottleneck for most machine learning workloads. We observe that frequently, many gradient values are (close to) zero, leading to sparse of sparsifyable communications. To exploit this insight, we analyze, design, and implement a set of communication-efficient protocols for sparse input data, in conjunction with efficient machine learning algorithms which can leverage these primitives. Our communication protocols generalize standard collective operations, by allowing processes to contribute arbitrary sparse input data vectors. Our generic communication library, SparCML, extends MPI to support additional features, such as non-blocking (asynchronous) operations and low-precision data representations. As such, SparCML and its techniques will form the basis of future highly-scalable machine learning frameworks.

1 Introduction and Motivation

SPARCML targets the allreduce bottleneck in data-parallel machine learning by exploiting sparse gradients, relaxed consistency, quantization, and asynchronous communication. It reports substantial speedups across synthetic and real workloads.

  • 1 Introduction and Motivation: SPARCML is a general communication library that exploits sparsity and relaxed consistency while extending MPI with sparse reductions, low precision, and non-blocking operations.Its target applications include distributed deep-network training and large-scale regularized classification on supercomputing and datacenter clusters.
  • 1 Introduction and Motivation: 31× faster completion was achieved for a large-scale URL classification task than its Cray MPI-based variant.The comparison variant did not exploit sparsity.
  • 1 Introduction and Motivation: 6× lower end-to-end convergence time was achieved for a state-of-the-art natural-language-understanding network in the supercomputing deployment.The result is reported alongside integrations with CNTK and MPI-OPT.
  • 1 Introduction and Motivation: ImageNet wide residual-network training improved by ≃2× on 64 GPUs with less than 0.5% Top5 validation accuracy loss and no additional hyperparameter tuning.Gains were negligible for the smaller-parameter standard ResNet50 benchmark.
  • 1 Introduction and Motivation: ASR LSTM training on 128 GPUs fell from 14 days to 1.78 days, almost a 10× reduction without significant accuracy loss.The paper concludes that existing frameworks can leverage sparsity and relaxed consistency across varied machine-learning applications.

2 Preliminaries

The preliminaries frame data-parallel SGD as synchronized model updating whose scalability is limited by communication, then review sparsification and quantization as reduction strategies.

  • 2 Preliminaries: Data parallelism partitions data across nodes while maintaining synchronized model copies through global averaging or a central coordinator.The paper focuses on allreduce because parameter servers have obvious scaling limitations.
  • 2 Preliminaries: In SGD, each node computes a stochastic gradient from a mini-batch, and gradient updates are averaged globally to maintain a consistent model.The model is updated using the learning rate and each node’s stochastic gradient.
  • 2 Preliminaries: The communication trade-off is between processing more samples per iteration and paying the additional cost of the sum reduction.This reduction is necessary to maintain a consistent model across nodes.
  • 2 Preliminaries: Top-k SGD communicates only the k largest-magnitude gradient components, accumulates the rest, and sends them in later iterations.The communicated fraction can be below 1% of the components.
  • 2 Preliminaries: Quantization reduces gradient precision through an element-wise operator and can preserve convergence under zero-mean quantization noise, although added variance may slow convergence.

3 Communication-Reduction: A Critical View

The critical view identifies a tension in existing compression methods: sparse reductions can densify as node counts grow, while quantization offers only limited compression before accuracy suffers.

  • 3 Communication-Reduction: A Critical View: 5–10% per-node sparsity can become dense after reduction across many nodes, restoring communication as the bottleneck.Figure 1 reports reduced-result density versus node count and per-node density for ResNet20 on CIFAR-10, with consistency across stages and model families.
  • 3 Communication-Reduction: A Critical View: Above 99% sparsity can preserve compression but requires careful momentum and learning-rate tuning that is error-prone and time consuming.
  • 3 Communication-Reduction: A Critical View: Quantization’s compression rate is independent of node count, but theory and experiments suggest only 4–8× compression before added variance affects end accuracy.

4 Communication Reduction in SPARCML

SPARCML combines sparse error-compensated reductions with intermediate stochastic quantization and establishes convergence for the resulting method under standard assumptions.

  • 4 Communication Reduction in SPARCML: The sparse method accumulates omitted gradient values, truncates the accumulator into transmitted updates, and sums those updates through a sparsity-aware allreduce.
  • 4 Communication Reduction in SPARCML: SPARCML can quantize a reduced vector at an intermediate reduction stage when sparse contributions become dense, lowering bandwidth overhead with stochastic QSGD.The paper presents this combination as a novel extension of independently introduced sparsification and quantization techniques.
  • 4 Communication Reduction in SPARCML: For smooth non-convex objectives, SPARCML has a learning-rate schedule under which the minimum expected squared gradient norm converges to zero as T grows.
  • 4 Communication Reduction in SPARCML: The theoretical guarantee establishes ergodic convergence to a stationary point rather than convergence to a global minimum.The result does not provide precise practical hyperparameters beyond indicating diminishing learning rates.

5 Supporting Sparsity in SPARCML

SPARCML represents vectors as sparse streams and develops allgather/allreduce collectives that exploit sparsity while switching to dense storage when fill-in makes sparsity inefficient. Its analysis characterizes static and dynamic sparse regimes, including latency, bandwidth, and fundamental speedup limits.

  • 5.1 Sparse Streams: SPARCML stores sparse vectors as index-value streams and switches to dense representation when the nonzero count exceeds the sparsity threshold δ.The sparse format reduces communication only while nnz ≤ δ, and summation overhead makes the practical threshold smaller.
  • 5.2 Sparse Collective Operations: Sparse allreduce lets every node obtain the element-wise sum of sparse inputs without requiring global information about nonzero indices.The collective framework supports arbitrary coordinate-wise associative reductions with a neutral element under an α-β communication model.
  • 5.3 Communication Algorithms: Static sparse allreduce has latency log2(P)α, which is latency-optimal and independent of data density, while bandwidth depends on the sparsity pattern.Disjoint supports produce maximum fill-in, whereas fully overlapping supports reduce to a dense allreduce over k elements.
  • 5.3.3 The Dynamic Case: Switching to Dense: Dynamic sparse allreduce must spend at least log2(P)α + δβd and has a bandwidth lower bound equal to at least 1/(2κ) of bandwidth-optimal dense allreduce.The dynamic case therefore provides only a constant-factor bandwidth improvement when the result is not efficiently sparse.

6 Supporting Low-Precision Communication

SPARCML reduces communication further by combining sparse collectives with lower-precision output representations. It supports stochastic QSGD quantization at 2, 4, and 8 bits per entry while preserving SGD convergence guarantees.

  • 7 Supporting Low-Precision Communication: SPARCML supports 2-, 4-, and 8-bit output representations using stochastic QSGD quantization, which provably preserves SGD convergence.The method is intended to reduce bandwidth beyond sparsity alone.
  • 7 Supporting Low-Precision Communication: QSGD splits dense streams into buckets, quantizes each bucket independently, and stores packed low-precision values with a full-precision scaling factor.The buckets contain approximately 1024 consecutive entries, with the scale shared by all values in each bucket.

7 Artifact and Additional Features

SPARCML provides an MPI-like implementation for sparse communication and integrates with machine-learning software. Its evaluation measures reduction time across node counts and data densities using repeated experiments and quantiles.

  • 7.1 Interface and Code: SPARCML offers an MPI-like interface for sparse streams, requiring only minor changes to MPI-enabled code and implementing the library in around 2,000 lines of native C++11.The framework also integrates with CNTK and MPI-OPT.

8 Experiments

Experiments evaluate SPARCML on synthetic communication, sparse classification, and deep-learning workloads. Results show substantial gains when workloads retain exploitable sparsity, while benefits are limited for dense or communication-light settings.

  • Micro-Benchmarks: Sparse reductions outperform dense approaches at scale, but ring-based dense allreduce remains faster on fast networks with relatively few nodes.DSAR Split allgather improves performance at larger node counts, but only by a constant factor.
  • Large-Scale Classification: 63× lower time to convergence on the URL dataset results from SPARCML’s 185× communication reduction on eight Piz Daint nodes.Average epoch time falls from 378 seconds to 6 seconds, with communication decreasing from 319 to 1.7 seconds.
  • Training Deep Neural Networks: Deep-learning experiments preserve accuracy while accelerating communication-heavy tasks: ATIS training is 5.99× faster, versus 1.12× for CIFAR-10 and 1.5× for Hansards.The differing gains reflect whether communication or computation dominates each model’s runtime.
  • Large Workload Experiments: ImageNet ResNet50 gains only ≃6% from 99% layer sparsification because aggregation densifies gradients and sparsification overhead is significant.The authors also report that stronger sparsity harms convergence and that the implementation lacks Cray’s additional parameter tuning.
  • Large Workload Experiments: SPARCML reduces wide-ResNet training time by ≃2× with less than 0.5% Top-5 validation-accuracy loss and no extra hyperparameter tuning.For 4xResNet18, speedup is ≃2×; 4xResNet34 reaches ≃1.85× with less than 0.4% Top-5 accuracy difference.
  • Large Workload Experiments: Production speech training reaches similar accuracy in less than 1.8 days on 128 GPUs, with SPARCML models staying within 1% higher word-error rate.The speech experiments use error-versus-time curves across 32, 64, and 128 GPUs.

9 Related Work

The paper positions SPARCML alongside communication-reduction methods while combining stochastic quantization with sparsification and targeting efficient large-scale sparse communication.

  • Prior work addresses quantization, asynchronous communication, structured sparsification, and large-batch methods for reducing distributed-training communication costs.
  • SPARCML combines stochastic quantization and sparsification, with convergence guarantees and practical runtime gains in large-scale settings.
  • Unlike lossless factorization and large-batch methods, SPARCML targets bandwidth reduction at a fixed batch size, although aggregated gradients can become dense at large node counts.
  • Kylix assumes known data distributions and multiple reduction passes, making it unsuitable for the paper’s sparse machine-learning setting.

10 Conclusions and Further Work

The paper concludes that SPARCML provides an extensible framework for sparse and low-precision machine-learning communication, while identifying further applications and interactions with parallelization methods as future work.

  • SPARCML enables sparse and low-precision communication in existing computational frameworks and delivers order-of-magnitude speedups in several real-world applications.
  • Future work will study further sparse distributed-learning applications and the interaction between sparsity and approaches such as large-batch training.
  • The analysis simplifies formulas under three assumptions, but relaxing them can yield upper bounds or require additional algorithmic steps.

B Stochastic Density Analysis

The stochastic density analysis models the reduced vector’s nonzero count using Bernoulli variables, derives bounds and exact uniform-distribution expectations, and shows growth with node count and local sparsity.

  • The reduced result contains Y nonzero entries, where Y is represented as a sum of Bernoulli indicators over the N possible indices.
  • The union-bound estimate is tight when node supports are pairwise disjoint, reducing the problem to an allgather.
  • The uniform case provides a closed-form exact expectation and matches the earlier non-probabilistic upper bound N = P × k.
  • Under a uniform distribution, the expected intermediate-result size grows multiplicatively with the number of nodes P and nonzero entries k per node.
  • Figure 7 illustrates expected reduced-result size for N = 512 under a uniform distribution.

C Convergence Proof

The convergence analysis studies Quantized TopK SGD under smoothness, moment, and sparsity assumptions, using auxiliary variables to relate the uncompressed and observed iterates before proving convergence.

  • The analysis assumes an L-Lipschitz-smooth objective and bounded second moments for averages of independent stochastic gradients.
  • Algorithm 2 updates local error, sums sparse contributions across nodes, and applies the resulting model update.
  • The proof incorporates stochastic-quantization variance through an adjusted second-moment bound and assumes a constant fraction of gradients survives summed TopK operators.
  • Auxiliary iterate x_t tracks accumulated gradients without truncation or quantization, enabling bounds on its difference from the observed iterate v_t.
  • The proof targets ergodic convergence of Quantized TopK SGD to a point where gradients are zero.
  • The convergence theorem requires suitable decreasing learning rates and K satisfying a stated per-iteration condition before guaranteeing a bound after T steps.

D Hyperparameter Values used for DNN Experiments

The DNN experiments followed CNTK’s standard hyperparameter values and learning-rate schedules, with the main settings summarized in Table 3.

  • The experiments followed CNTK repository hyperparameter values and learning-rate schedules optimized for sequential execution.
  • The exact BrainScript configuration files were similar to those presented in reference.
  • Table 3 provides the main hyperparameter values used in the experiments.
Loading 1802.08021v3…