PaperlayerView exact revision on arXiv

Source-linked AI summary

Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis

Tal Ben-Nun, Torsten Hoefler

arXiv:1802.09941v2cs.LGcs.CVcs.DCcs.NE

TL;DR

Training increasingly complex DNNs requires substantial computational resources, motivating systematic analysis of parallel and distributed methods. This survey organizes concurrency from individual operators to network training and distributed systems, using theoretical models and reviewing algorithmic and architectural approaches. It concludes by identifying supported directions for expanding parallelism, while excluding reinforcement-learning algorithms from its scope and noting survey-coverage limits.

  • Problem

    Growing datasets and increasingly complex DNNs make training computationally and memory intensive, creating a need to understand how training can be accelerated through concurrency.

  • Method

    The survey reviews parallel and distributed deep learning from operator-level computation through network training, communication, system architectures, and architecture search, analyzing concurrency with the Work-Depth model.

  • Results

    The survey synthesizes concurrency strategies spanning vectorization, DNN evaluation and training, distributed algorithms, communication schemes, and distributed-memory systems.

  • Takeaways & Limitations

    Parallel and distributed deep learning must be considered across computation, communication, optimization, and system design, from single operators to multi-machine training.

  • Takeaways & Limitations

    Reinforcement-learning algorithms are outside the survey’s scope, although their parallelization techniques are described as similar.

Abstract

from arXiv · show

Deep Neural Networks (DNNs) are becoming an important tool in modern computing applications. Accelerating their training is a major challenge and techniques range from distributed algorithms to low-level circuit design. In this survey, we describe the problem from a theoretical perspective, followed by approaches for its parallelization. We present trends in DNN architectures and the resulting implications on parallelization strategies. We then review and model the different types of concurrency in DNNs: from the single operator, through parallelism in network inference and training, to distributed deep learning. We discuss asynchronous stochastic optimization, distributed system architectures, communication schemes, and neural architecture search. Based on those approaches, we extrapolate potential directions for parallelism in deep learning.

1 INTRODUCTION

Deep learning has achieved broad success, but growing dataset sizes and model complexity make training increasingly computationally demanding. This survey reviews parallel and distributed approaches across DNN computation and analyzes their concurrency using the Work-Depth model.

  • DNNs have enabled accurate solutions across applications including image classification, speech recognition, and medical diagnosis.
  • Growing datasets and increasingly complex networks raise the computational and memory demands of training.
  • The survey reviews parallelism and distribution from vectorization through supercomputing, covering DNN evaluation, training algorithms, and distributed systems.
  • The review analyzes concurrency and average parallelism with the Work-Depth model to compare the surveyed approaches.
  • The survey complements prior work focused on applications, neural-network history, scaling, optimization, and hardware architectures.
  • Its scope includes concurrency tradeoffs, DNN operators, full-network training and inference, distributed training, communication reduction, and system implementations.

2 TERMINOLOGY AND ALGORITHMS

This section defines supervised learning and DNN optimization, then connects training acceleration to single-machine and distributed parallelism. It introduces concurrency analysis, communication mechanisms, and parallel reduction algorithms for deep learning systems.

  • 2.1 Supervised Learning: Supervised learning optimizes a parameterized function so predictions approximate labels drawn from the same distribution as observed samples.The survey represents DNN parameters across multiple layers and seeks weights minimizing expected loss.
  • 2.1 Supervised Learning: Classification identifies a sample’s class, whereas regression predicts values in one domain from observations in another.The survey uses probability-distribution outputs and differentiable losses for multi-class classification.
  • 2.1 Supervised Learning: SGD repeatedly samples training examples, computes gradients, and updates weights; for suitable convex functions, it converges at O(1/T).The update rule depends on gradients, previous weights, iteration, and hyperparameters such as the learning rate.
  • 2.3 Parallelism: Among 240 reviewed papers, 147 report empirical results with hardware details, and publications increasingly use GPU-accelerated multi-node systems.The survey reports distributed-memory architectures with accelerators as the default option beginning from 2015.
  • 2.3.2 Multi-machine Parallelism: Distributed training addresses compute and memory demands by using multiple networked machines, while communication remains slower than intra-machine communication.Latency, bandwidth, and message rate characterize interconnect performance.
  • 2.3.2 Multi-machine Parallelism: MPI became the de-facto portable communication standard in distributed deep learning beginning from 2016.The survey relates this adoption to deep learning’s similarity to large-scale HPC applications.
  • 2.5 Parallel Algorithms: Parallel allreduce can use tree-based summation and broadcast, with tree complexity Ttree = 2 log2(P)(L + γmG).The best practical algorithm depends on the system, process count, and message size.

A B C

The section illustrates how minibatch size relates to SGD performance and accuracy, including an empirical ResNet-50 accuracy figure where lower values are better.

  • The illustration compares minibatch SGD performance and accuracy after a fixed number of epochs.
  • The ResNet-50 figure presents empirical accuracy results adapted from prior work, with lower values indicating better accuracy.
  • The figure examines the effect of minibatch size on accuracy and performance.

3 THE EFFICIENCY TRADEOFF: GENERALIZATION VS. UTILIZATION

Minibatch size creates a tradeoff between statistical quality and hardware utilization: batches that are too small waste available concurrency, while excessively large batches can impair convergence and generalization. Adjustments such as learning-rate schedules can extend, but not eliminate, the upper limit on useful minibatch sizes.

  • Minibatches should be large enough to exploit concurrency in loss evaluation but not so large that result quality decays.The paper identifies these regimes as regions A and C, respectively.
  • Large minibatches can improve convergence through a negative term, but increased gradient variance and learning rate can hinder convergence.
  • Typical minibatch sizes range from orders of 10 to 10,000, and larger batches require adjusted or scheduled optimization.Successful large-batch methods use static or adaptive learning-rate adjustment, warmup, variance control, adaptive batch growth, or specific schedules.
  • Large-batch techniques increase the upper bound on feasible minibatch sizes but do not remove it.

4 DEEP NEURAL NETWORKS

DNNs are compositions of neural operators whose structures determine computation, dependencies, and available concurrency. The survey connects operator-level computation with network training, showing that parallel work generally dominates dependency depth while architectural trends shift parallelization toward minibatches and resource-efficient designs.

  • DNN structure: A DNN is built from neurons and operators arranged as layered compositions, with feed-forward networks using forward connections and recurrent networks retaining within-layer state.Neurons apply nonlinear activation functions to accumulated weighted inputs.
  • Feed-forward operators: Convolution reduces parameters through sparse connections and shared weights, applying Cout kernels of size Cin×Ky×Kx to each image tensor.The output dimensions are N × Cout × H′ × W′, with H′ and W′ determined by kernel size when boundary extensions are excluded.
  • Feed-forward operators: Pooling subsamples contiguous spatial regions to reduce tensor size and support learning features corresponding to larger regions of the original data.Max-pooling and average pooling are examples of the operation.
  • Feed-forward operators: Batch normalization creates dependencies between minibatch samples by centering them around zero mean and unit variance, using scaling factors and numerical stabilization.The transformation uses γ and β as scaling factors and ϵ for numerical stability.
  • Training computation: Backpropagation computes the loss gradient by first evaluating operators in dependency order and then propagating information backward through the network.RNNs instead commonly use backpropagation through time, unrolling recurrent layers over a selected sequence length with shared weights.
  • Concurrency analysis: Work asymptotically dominates dependency depth for DNN layers, with maximal dependency paths at most logarithmic in the parameters.The Work-Depth analysis supports the major role of parallelism in feasible DNN evaluation and training.
  • Trends in DNN characteristics: Since 2015, resource-reduction efforts have accompanied increased average parallelism, shifting parallelization toward concurrency within minibatches.Smaller networks also require less memory and communication for embedded, mobile, and distributed settings.

5 CONCURRENCY IN OPERATORS

DNN operator parallelism depends on reshaping computations, data layout, and the characteristics of each implementation. Performance modeling and experiments show that no single convolution method is optimal across all settings.

  • Operator concurrency: Layer execution can be parallelized directly in many cases, while other operators require reshaping computations to expose parallelism.The survey analyzes operator performance using concurrency and Work-Depth characteristics.
  • Performance modeling: CUBLAS performance changes nonlinearly with matrix dimensions because the library selects among 15 internal implementations.These implementation regions appear as segments in the performance plot.
  • Performance modeling: Performance models predicted minibatch computation and backpropagation time with ∼5–19% error, including on GPU clusters with asynchronous communication.Related models reported 10–30% prediction error when using operation counts alone.
  • Convolution: FFT convolution provides up to 16× performance over GEMM for larger kernels, while pruned FFT reduces kernel-transform operations by 3×.ZNNi reports 5× and 10× speedups for CPUs and GPUs, respectively.
  • Convolution: Convolution methods differ in Work-Depth behavior, with average parallelism determined by kernel size or image size, so no one-size-fits-all method exists.Work and Depth metrics are not always sufficient to characterize performance.
  • Convolution: Transposing tensors from N×C×H×W to C×H×W×N yields up to 27.9× speedup for one operator and 5.6× for AlexNet.The reported speedup persists even when transposition occurs during DNN computation.

6 CONCURRENCY IN NETWORKS

DNN concurrency spans data, model, pipeline, and hybrid parallelism, exploiting minibatches, network structure, and asynchronous execution. These strategies improve utilization and scaling while introducing synchronization, communication, or accuracy trade-offs.

  • Overview: High average parallelism enables concurrent evaluation and backpropagation by partitioning minibatches, layer breadth, and network depth.The survey analyzes these approaches using concurrency and average parallelism in the Work-Depth model.
  • Data Parallelism: Data parallelism partitions minibatch samples across computational resources, then averages partitioned gradients during weight updates.Most operators process samples independently, but gradient aggregation can induce an allreduce operation.
  • Data Parallelism: 8k, 32k, and 64k-sample minibatches were achieved without considerable accuracy loss, although Batch Normalization can hinder scaling through full synchronization.Using local normalization on subsets such as 32 samples can make synchronization local when enough samples are assigned to each processor.
  • Model Parallelism: Model-parallel methods reduce communication through specialized computation schemes, including Cannon’s algorithm for fully connected layers and replicated network elements.Cannon’s algorithm reports better efficiency and speedups than simple partitioning on small-scale multilayer fully connected networks.
  • Model Parallelism: A 3-node multi-GPU cluster outperformed a same-size CNN running on 5,000 CPU nodes when using locally connected networks and model parallelism.The approach avoids communication-bound training because locally connected networks lack weight sharing apart from spatial image boundaries.
  • Pipelining: Pipelining overlaps computations or assigns depth-partitioned layers to processors, combining data-parallel and model-parallel characteristics.It can overlap forward evaluation, backpropagation, and weight updates, mitigating processor idle time.
  • Hybrid Parallelism: A hybrid AlexNet scheme achieved up to 6.25× speedup for 8 GPUs over one with less than 1% accuracy loss by combining data and model parallelism.Data parallelism was applied to convolutional layers and model parallelism to the fully connected part.
  • Asynchronous Execution: AMPNet schedules internal and cross-layer tasks asynchronously, enabling pipelines across forward evaluation, backpropagation, and weight updates.Its stated advantages concern recurrent, tree-based, and gated network structures.

7 CONCURRENCY IN TRAINING

Distributed deep learning exposes tradeoffs among model consistency, parameter centralization, communication, fault tolerance, and hyperparameter or architecture search. The survey reviews these approaches and their concurrency implications.

  • Distributed training schemes vary along model consistency, parameter distribution, and training distribution.Figures 18 and 19 summarize the associated techniques and optimizations.
  • Model consistency: Inconsistent methods such as HOGWILD relax synchronization by allowing stale parameter reads and concurrent updates.Its distributed-memory extensions still attain convergence for deep learning problems.
  • Model consistency: O(1/√mT) convergence and linear scaling are reported for asynchronous HOGWILD variants with m participating nodes.Agents can train almost independently under the asynchronous design.
  • Model consistency: Synchronous allreduce scales nearly linearly up to 32–50 nodes, whereas asynchronous or SSP methods suit larger or heterogeneous clusters.SSP bounds staleness through periodic global synchronization and helps control stragglers.
  • Communication: Project Adam reduces fully connected-layer communication from m · Cout · Cin to m · N · (Cout + Cin) by computing gradients on the parameter server.The method exchanges activations and errors instead of parameters, trading communication for redundant computation.
  • Communication: Gradient sparsification achieves compression ratios of 846–2,871× for a non-convolutional DNN, with up to 1.8% error reduction reported.Thresholding, normalization, clipping, and warm-up are used to address sparsification-related accuracy loss.

8 CONCLUDING REMARKS

The survey presents deep learning as broadly parallel, from operator computation to architecture search, and uses the Work-Depth model to analyze concurrency where possible. It projects continued automation, graph-level optimization, elastic systems, and new opportunities from more complex models.

  • Nearly every aspect of DNN training is inherently parallel, from convolution computation to meta-optimization of architectures.Even sequential aspects may expose more concurrency by relaxing consistency requirements while retaining reasonable accuracy.
  • The survey reviews parallel approaches and provides concurrency analysis using the Work-Depth model when possible.
  • Deeper, more interconnected architectures increase interest in reducing memory footprint and operations for mobile inference.The authors expect further research on post-training compression and training compressible networks.
  • Compilers that optimize entire neural-network graphs through transformations such as fusion have achieved 4× speedup over manually tuned individual operators.
  • Future distributed-learning ecosystems may hide low-level infrastructure while combining cloud support, elastic training, and evolutionary optimization.The passage identifies adaptive and financially viable optimization methods as a possible outcome.
  • Automated architecture search and progressive training may make parameter sweeps and manual DNN architecture engineering obsolete.The survey links such advances to the need for exploiting parallelism.

A ANALYSIS OF INFLUENTIAL CONVOLUTIONAL NEURAL NETWORKS

The section introduces LeNet-5 and AlexNet as influential convolutional neural networks, with figures illustrating their architectures.

  • LeNet-5 is presented as an influential convolutional neural network architecture.

A.1 LeNet[145]

LeNet-5 processes handwritten-digit images through alternating convolution and pooling stages before fully connected classification. Its inference exhibits substantial concurrency that grows linearly with minibatch size.

  • LeNet-5 processes a single-channel 2D input through repeated convolution and max-pooling stages, followed by fully connected layers and softmax output.
  • The section analyzes LeNet-5 inference using average parallelism measured as W/D.
  • The displayed work expression decomposes inference cost into convolution and pooling contributions across the network layers.
  • LeNet-5 exhibits high concurrency that increases linearly with minibatch size.

A.2 AlexNet[136]

AlexNet combined convolutional and fully connected layers with training techniques that supported its strong ImageNet performance. Its success helped drive broader interest in deep neural networks.

  • Nearly twofold accuracy improvement over the preceding state of the art made AlexNet the ILSVRC 2012 winner.The preceding state of the art had 26.2% top-5 error.
  • AlexNet used convolution-pooling layers, fully connected layers, convolution sequences, and Local Response Normalization.
  • Data augmentation and Dropout-based network regularization were identified as two major factors in AlexNet’s success.
  • The network was implemented for GPUs and trained on ImageNet with minibatches of 128 images.

A.4 ResNet[93]

As DNNs became deeper, successful training became harder. ResNet addressed this depth-related degradation with shortcut connections, enabling much deeper networks and improved feature learning.

  • Increasing network depth made successful training harder for architectures such as VGG.
  • ResNet adds each convolutional module’s input to its output through shortcut identity connections.The layers are trained with respect to residuals rather than their original values.
  • ResNet enabled training networks 50 to 152 layers deep, allowing higher-level features to be learned.

A.5 DenseNet[108]

DenseNets increase inter-layer connectivity by concatenating preceding outputs, supporting gradient propagation and feature reuse. Compared with ResNets, they can achieve lower CIFAR-10 error but involve a parameter trade-off.

  • DenseNet blocks concatenate each layer’s outputs to the inputs of subsequent layers rather than using only module identity shortcuts.
  • Dense connectivity supports gradient propagation because later layers receive earlier inputs and need not represent only high-level features.
  • With half the parameters and operations, DenseNets achieve results similar to ResNets.
  • 3.62% CIFAR-10 error with 15.3M parameters was achieved by DenseNets, versus 6.41% error with 1.7M parameters for ResNets.The comparison concerns 250-layer DenseNets and the reported ResNet baseline.
  • DNN compression and newer architectures seek to reduce parameters and operations while maintaining or increasing accuracy.

C CONVOLUTION COMPUTATION ANALYSIS

The convolution analysis models direct, im2col, FFT, and Winograd implementations using work and depth, exposing their parallel structure and computational costs. The formulations specify tensor layouts, transformations, and matrix operations for each approach.

  • The analysis assumes 4D input, kernel, and output tensors, with zero padding and unit stride giving W′ = W − Kx + 1 and H′ = H − Ky + 1.
  • Direct Convolution: Direct convolution parallelizes over samples, output channels, and output positions while reducing across input channels and kernel dimensions.Its work is W = N · Cout · H′ · W′ · Cin · Ky · Kx.
  • im2col Convolution: im2col transforms convolution into matrix multiplication using A, F, and B, with B ← F · A producing the reshaped output.
  • FFT Convolution: FFT convolution transforms inputs and kernels with 2D FFTs, performs batched pointwise multiplication and summation, then applies a 2D inverse FFT.The transformed computation uses batched complex matrix-matrix multiplication in practical implementations.
  • Winograd Convolution: Winograd convolution divides inputs into overlapping tiles and applies Winograd transforms before the channel-wise matrix multiplication and inverse output transform.For an m × m output tile and r × r kernel, the input tile size is α = m + r − 1.
Loading 1802.09941v2…