SAPipe: Staleness-Aware Pipeline for Data Parallel DNN Training
Authors: Yangrui Chen
Cong Xie
Meng Ma
Juncheng Gu
Yanghua Peng
Haibin Lin
Chuan Wu
Yibo Zhu
Venue: NeurIPS 2022 Accept (2022)
Keywords: data parallelism
communication optimization
staleness mitigation

Abstract: Data parallelism across multiple machines is widely adopted for accelerating distributed deep learning, but it is hard to achieve linear speedup due to the heavy communication. In this paper, we propose SAPipe, a performant system that pushes the training speed of data parallelism to its fullest extent. By introducing partial staleness, the communication overlaps the computation with minimal staleness in SAPipe. To mitigate additional problems incurred by staleness, SAPipe adopts staleness compensation techniques including weight prediction and delay compensation with provably lower error bounds. Additionally, SAPipe presents an algorithm-system co-design with runtime optimization to minimize system overhead for the staleness training pipeline and staleness compensation. We have implemented SAPipe in the BytePS framework, compatible to both TensorFlow and PyTorch. Our experiments show that SAPipe achieves up to 157% speedups over BytePS (non-stale), and outperforms PipeSGD in accuracy by up to 13.7%.

SAPipe: Staleness-Aware Pipeline for Data-Parallel DNN Training
Yangrui Chen
Cong Xie
The University of Hong Kong yrchenOcs hku. hk
ByteDance cong xie@bytedaneeecomm
Meng Ma ByteDance
Juncheng Gu
ByteDance juncheng ww@gygedageb..ccoooommm com
meng. mwwbybeddance.coomm
Yanghua Peng
Haibin Lin
ByteDance
ByteDance
haibin www.inninnneeedcee.comm com
Chuan Wu
Yibo Zhu
The University of Hong Kong cwuêcs hku. hk
Byte 2hyyboo@ytedancee.co
Abstract
Data parallelism across multiple machines is widely adopted for accelerating dis- tributed deep learning, but it is hard to achieve linear speedup due to the heavy communication. In this paper, we propose SAPipe, a performant system that pushes the training speed of data parallelism its fullest extent. By introducing partial staleness, the communication overlaps the computation with minimal stal- eness in SAPipe. To mitigate additional problems incurred by staleness, SAPipe adopts staleness compensation techniques including weight prediction and delay compensation with provably lower error bounds. Additionally, SAPipe presents Aigorithm-systen co-design with runtime optimization to minimize system overhead for the staleness training pipeline and staleness compensation. We have implemented SAPipe in the BytePS framework, compatible both TensorFlow and Py PyTrchh Our experiments show that SAPipe achieves up to 1577 speedups over BytePS (non-stale), and outperforms PipeSGD in accuracy by up to 13.7%.
1 Introduction
Deep Neural Networks (DNNs) have achieved ground-breaking performance on a wide range of domains, such as computer vision (CV) [T0 I7 and natural language processing (NLP) (2) 7).
Meanwhile, the model sizes and data volumes have grown exponentially, making DNN training time-consuming and resource-intensive The most common approach accelerate DNN training is to use data parallelism, scaling DNN training across multiple devices. Despite the substantial speedup, distributed machine learning systems with data parallelism often cannot fully utilize the computation resources and achieve linear scaling (i.e., GPU number times single-GPU training speed), due to
non-negligible communication overhead [3 2 23 13].
Many recent studies have been devoted to developing communication acceleration techniques. Some works reduce communication traffic using gradient compression mixed-precision training 21].
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

while others schedule communication to overlap it with computation. For example, ByteSched- uler [23] and PACE propose preemptive communication scheduling to hide the communication overhead within forward computation time. These communication scheduling approaches reduce the communication overhead without affecting the convergence of training, but still cannot fully hide communication when the catpuuuiiicciio----ooottaaaaaaaa
ratio is high.
new direction accelerate distributed DNN training has been explored, which intentionally introduces staleness to the training pipeline in order to further increase the overlap between commu- nication and computation. For example. PipeSGD
uses the gradients from the previous iteration in stochastic gradient descent (SGD), resulting in fixed 1-step staleness.
Though introducing fixed staleness may fully overlap communication with computation for some DNNs, the staleness may also incur severe problems to the convergence of training. We observe significant accuracy degradation even training divergence with only 1-step staleness of gradients in our experiments. We identify this key limitation and propose 2 solutions: 1) partial staleness, which introduces staleness limited number of layers; 2) staleness compensation, which compensates the 1-step staleness by predicting the gradient to be produced in the next iteration, with optimized implementation reduce the overhead of prediction.
We design a performant and Staleness-Awary communication Pipeline (SAPipe) system for accelerat- ing distributed DNN training. which reduces the communication overhead in distributed training by overlapping communication with computation, and approaches the linear scaling.
The main contributions of this paper are as follows:
We propose a partial staleness algorithm, which finds the minimal number of layers to introduce staleness to, so as to keep the training pipeline running without stall ($ (31.1)
We adopt multiple staleness compensation techniques, including delay compensation, weight
prediction and their combinations ($ 3.2))
We propose an SAPipe, that are especially designed and implemented to minimize the system overhead of partial
system co-design, keree fusion, and other runtime optimizations in
staleness and staleness compensation ($ 3.3
We provide theoretical guarantees to show that SAPipe achieves the same convergence rate as vanilla SGD, and conditionally better error bounds compared to PipeSGD ($ 4.
We demonstrate that SAPipe outperforms existing frameworks. SAPipe achieves up to 157% specdups over BytePS (non-stale), and outperforms PipeSGD in accuracy by up to 13.7% 5).).
2 Background
Preliminaries. In distributed deep learning, we solve the following optimization problem with
workers: min F(z), where F(x) Eie(n] Fi(x) = 1, Ei E 24), Vi E [m]] is the objective function, x' E IRd is the set of model parameters (d is the total number of model parameters), 2; is mini-batch of data randomly sampled from the local data D, on device i, and f(-) loss function. A typical DNN is composed of m layers, which are concatenated into a flattened vector & for simplicity.
Distributed training with data parallelism. Data parallelism partitions the training data onto multiple devices, i.e., workers. Each worker propagates its local data through the model and calculate the loss (forward propagation). It uses the loss value to compute the gradients of each parameter (backward propagation), and aggregates them from all workers, before updated to the global model. To facilitate distributed training, the parameter server [18] and all-reduce (26) are the two most popular communication architectures for gradient aggregation. The detailed process is shown in highlighted in blue.
Algorithm| I
Staleness pipeline. To hide communication time, previous works (e.g., PipeSGD [19] introduce
1 -ssee staleness to the training pipeline, where the forward computation can progress without waiting for the gradient synchronization. To be more specific, the gradient aggregation of each layer is executed once its backward computation finished, followed by the optimizer update using the aggregated gradient from the previous iteration. Thus, the gradient aggregation overlaps with not only the backward computation and optimizer update of the current iteration, but also the forward computation of the next iteration. The gradient aggregation initiated in the current iteration will be

---

Algorithm Distributed Training Staleness Training Pipeline (PipeSGD)
Algorithm 2 Staleness-Aware Pipeline with Delay Compensation (SAPipe-DC)
1: Initialize zo
1: Initialize zo
2: for all iteration /. E [T] do
2:
for all iteration / E [T] do
3: for all workers E [rx] in parallel do
3:
for all workers E [x] in parallel do
4: Compute V (z Ai, D
4:
Compute V (1 Pit D ift then
5: i then
5:
6:
Same
Pass
6:
Ji.t (z 21,1-1)
7:
else
7:
Eie(nl 9hr
8:
DiD Vflae-1 1:
8:
Az; 21-1 I1-2
9:
R Vflae 2
9:
gt pC +- (D, Ax,,
10:
= EiEja Dist
10:
b DC is func. defined in Equ. (1)
11:
Et t optimizer (It-1, 9r.
11:
2t f- optimizer (It-1, 9t
DC
77t
Computstion Frameworks
TensorFiow
PyTorch
Comp
Comm.
Comm.
Comp.
Backward and Forward Propagation
Gracioms
Stalenass
Staleness Miligation
Stalenses Pipaline System
Milgation
Stareness
Pertil Stalenoss
Mitcction
Worker O
Workern
(1) The compucation gradients the communication service
synchronization, rece non non-stale synchronized results.
Butter Ostimizatoo
Butter Switch
Karrel Fuskon
(2) The computation sends requests for stale gradients.
Flandmm
and applies ght prediction and dalay compensation to the DNN model.
(5) The staloness millgation module loads ralated data from stalanass buffer,
(4) The communication service updittes the staleness buffer when synchronization gradients linished
(a) Architecture
(b) Workflow
Figure I: The architecture and workflow of SAPipe. Solid lines: data flow with all gradients. Dashed lines: data flow with stale gradients.
finished in the next iteration. We outline the conceptual distributed staleness training pipeline in Algorithm [ highlighted in orange. Staleness pipeline results delayed gradients, which may cause significant accuracy degradation of the converged model, as shown in our experiments ($.).
SAPipe Design
To address the convergence issue of staleness pipeline, we design staleness-aware system, SAPipe, as shown in Figure a.). based on the following key designs.
Partial Staleness. Not all layers in a DNN model require a staleness training pipeline to fully hide communication within computation. Our partial staleness algorithm finds minimal number of layers be updated by stale gradients ($ 3.T). while updating the other layers without staleness.
Staleness Compensation. To further mitigate the problem caused by staleness of the layers chosen by the partial staleness algorithm, compensate the staleness of the gradients by multiple approaches including delay compensation and weight prediction ($ 3.2).
Optimized Runtime. Both staleness training pipeline and staleness compensation incur additional overhead computation and memory copy. To minimize such overhead, we adopt several system
optimizations to achieve the nigh-performance runtime ($ 3.3

---

Table 1: Notations
Notation
Description
Notation
Description
b;
Duration of backward operator
T,t
Total number and index of iterations
U4
Duration of forward operator
gt
Stochastic gradient ft = 2ie(n) Pi.t
V/
Duration of comm. operator
(gt)ss
The jth coordinate of go. J E [d]
Completion time of operators
The jth coordinate of gi.t, on worker
71
Total number workers
(VFi)j
The jth coordinate of V F J E [d]
m
Total number layers
Hadamard (coordinate wise) product
Model parameter Rd d
The number of model parameters
3.1
Partial Staleness
Due to the layer-wise structure of DNN models and the reverse order of forward and backward passes, it only requires parts of the gradients be stale hide the communication overhead. Reducing the number of stale gradients mitigates the problems caused by staleness, improving convergence and keeping communication overhead hidden at the same time. We seek find the minimal number of stale gradients such that there is no training pipeline stall, i.e., no waiting time for computing devices.
A naive way is to enumerate all possible combinations of gradients and check if they lead training pipeline stall, which involves prohibitive complexity. Fortunately, the execution orders of the layers in sequential models are fixed, which provides the opportunity for efficient searching.
Theorem 1. In training pipeline without stall, if some forward layer is stale, then all its preceding forward layers are stale.
Detailed proof of Theorem is in the Appendix. Then we consider the case that the first & layers need be trained staled gradients for fully overlapping its computation and communication, and formulate the following convex program for finding the minimal number of stale layers. Here the variables defined in T
minimize
k
subject to
Σ vi S b; + Σ Ui Σ
S b
i = 1, 1,...,
m;
k=++
1=1
1=1
0 k < m,
12
0, b,
> 0,
0,
i
= 1 m.
The first constraint aims keep communication and computation fully overlapped. The second con- straint ensures that the non-delayed gradients should be synchronized before the start of computation of the corresponding layers. We assume that the computation time of each layer remains the same under different solutions and the execution order follows FIFO. The above problem can be solved in Omm² time by enumerating k. The optimal solution gives the minimal delayed gradients and ensures maximal training throughput.
In SAPipe, the first k layers updated with 1-step stal- eness, while the remaining layers are updated by vanilla distributed SGD without staleness (see Figure 2). The basic version of SAPipe (referred to as vanila SAPipe) is mixture of distributed SGD and PipeSGD as given in Al- gorithm For theoretical analysis, we add the following definition.
Deliul Piolinoo
Buler
Salkire lhe babien Ma
Saletesa
Poolire
Oradorss
Definition Let deraie [0, 1] denote the portion of model parameters updated by stale gradients, where dstate is the total number of model parameters contained in the lo layers that are updated with 1-step staleness.
Stie
Figure 2: DNN training pipeline. The ar- rows denote dependencies between two operators.
We focus on sequential models, and the discussion about extending our methods to DAG models can be found in the Appendix.

---

Algorithm 3 Staleness-Aware Pipeline with Weight Prediction (SAPipe-WP)
1: Initialize 20
2: for all iteration t E [T] do for all workers E [x] in parallel do
3:
4:
then f
5:
Compute Vf(oo 21,0), 21,0 Di
6:
else
7:
Pett 15
Computed in the prev. iteration
8:
Option 1: Di. - 9i,
D. Local gradient Latest sync. gradient Option 3: Ii. DC(gt-1 1 1,, Axy) + #i.t, where Ar, -r-1 24-2
9:
Option 2: Ii.z 9t-1
11:
b 1-step-ahead weight prediction Compute (i( Ziet Dj Synchronization is finished in the next iteration
Ti,t & optimizer (#t-1, Iist.
12:
13:
9t LiEn Di,t
14:
Tt f optimizer (It-1, 7p))
3.2 Staleness Compensation
We introduce two staleness compensation methods in our distributed training pipeline: delay compen- sation and weight prediction. Note that in SAPipe, they are only applied to the first k layers of DNN, chosen by the partial staleness algorithm above, while the remaining layers are updated by normal distributed training procedure as shown in the blue part of Algorithm
mitigate the effects of delayed gradients on the model with delay compensation. This method leverages Taylor expansion of the gradient function and efficient approximation of the Hessian matrix of the loss function. In the original design of ASGGG,, the following ooay-commensated gradient is used: 9: 22 tge ogr (x, 22 -1), where: > 9t is the gradient evaluated on I;-1, and X is hyperparameter. Note that the delay compensation above is diagonal approximation of the full matrix form: Gr o (It-1 - zt. -1- &
Delay compensation (DC). Inspired by DC-ASGD 33
gegp ge (z,-1- - Zy ) In this paper, we prefer to use the full-matrix form of DC to avoid the additional error caused by the diagonal approximation:
(1) The detailed algorithm of SAPipe with DC is shown in Algorithm 2 We will show that by com- pensating the 1-step staleness, SAPipe-DC achieves a lower error bound than vanilla SAPipe, and converges as fast as the non-stale baseline.
- IV- gr + Agr (xx - -1) 9t ~ DOX(ge,
Weight prediction (WP). In a I-step staleness pipeline, model weights are always updated using the synchronized gradients in the last iteration, resulting in convergence problems with inconsistent weight. The goal of WP is to estimate the 1-step-ahead weights for forward pass and backward pass, and to obtain -step-ahead gradients, in order to counteract the 1-step staleness. We provide three options for weight prediction: 1) WP with local gradient the current step. 2) WP with the latest synchronized gradient, and 3) WP with all the above combined and DC.
The algorithm of SAPipe with WP is given in Algorithm
3 Line 5 computes the normal gradients in the first step. In the following steps, Line 7 retrieves the local gradient cached in each worker, and Line 8 to Line provide the options for weight prediction. We apply an extra optimizer update using predicted gradients (Line [T] in each worker to predict 1-step-ahead weights, and conduct forward and backward propagation to obtain the I-step-ahead gradients (Line 12p. Line [3 finishes the synchronization of the gradients from the last step, and Line 14 uses them to update the model. Note that the delayed gradients the last step are computed based on 1-step predicted weights. Therefore, the 1-step staleness is compensated.
3.3 Optimized Runtime
Figure[b) shows the workflow of the staleness pipeline system. SAPipe's 's staleness pipeline incurs extra overhead, namely: (1) the computation of staleness compensation; (2) data transfer between the staleness buffer and other modules. To minimize the system overhead, we present an algorithm- system co-design. We fuse the computation operations in DC and WP methods and other small weight update functions into several batched kemnels. This saves a significant amount of kernel
5

---

launching time. We further optimize the usage of staleness buffer. We use double buffer system 228 to handle stale gradients. reducing the transferring overhead, and minimize the memory usage by sharing the staleness buffer between computation and communication. We also switch the location of the staleness buffer between CPU memory and GPU memory according to the execution time of communication and computation pipeline stages. This overlaps the transferring overhead of the staleness buffer between communication and computation devices.
Theoretical Results
We establish theoretical guarantees of the convergence of SAPipe for smooth but non-convex prob- lems, using SGD as the optimizer: optimizersan (11 90 mt) It-1 Th9r, with a constant learning rate V)- rp.
4.1 Assumptions
Assumption 1. (Smoothness) We assume that f(z; vz, are L-smooth: [ - ff( S L| - y/l, Vx, y, which implies f(; S Assumption 2. For any stochastic gradient gt., = ( Ri, ~ Dr where D; is the local dataset on worker i, we assume bounded variance and Ez-norm: Elllg,, - (Fi |l S V1, || < V2, vi [ni, E [T]. Furthermore, gradients from different workers are independent of each other.
(Vf(=; (
x) + $ 21 x11².
EnEr [V Assumption 3. Introduced in (30), we assume bounded gradient diversity: TEic( VFLT) S p, Va.
The gradient diversity shows to what extent the local gradients on different workers are distinguished from each other. It is easy to check that Assumption
3 iiiplies the bounded difference between the
1 local and global gradients: n LiEm [l) V VF
(=)|l S
1VV((())
Assumption 4. For DC in Eqm. 77.. we assume that the objective function f(x) is twice- differentiable. Thus, we have the Taylor's approximation on x' E IRd with bounded remainder: [(x) (V((x') V2 fa')(x - x'))]l S M||x - =''l2 where (² is the Hessian matrix evaluated on x'. We also assume that the Hessian approximation error is upper-bounded by A. Vx E RRd, i.e., (V)o)) -V2((x)) & A, with vector-induced matrix norm || 1|2-
Note that the original paper of DC-ASGD proves that A - 0 when t - oc under certain assumptions. Thus, it is reasonable to assume a bounded approximation error.
Assumption 5.
For simplicity, we assume that for partial staleness, the elements of every gradient are randomly and independently chosen to have I-step staleness.
Assumption 6. There exists at least one global minimum z.. where F(x.) S F(x), Vz. And we define the initial gap as Ro = F(ro) - F(..).
4.2 Convergence Analysis
We derive the following error bounds on the convergence of SAPipe under the above assumptions. All proofs can be found in Appendix A.
Theorem 2. Under Assumptions
7 2 and 6 taking n S t. after T iterations, for vanilla
SAPipe without DC or WP, we have the following error bound: B
s
2Rg + KKEro + Varo, where Erro = 122,2VV V2 and Varg = LgVi 7f
Remark 1. Theorem 2 shows that the overall convergence error bound of vanilla SAPipe includes
2 main components: the gradient estimation error Erro and the variance error Varg. Erro is rooted in the 1-step staleness. V arro is incurred by the random sampling in stochastic gradients.
When no layer is updated with staleness, SAPipe is reduced to vanilla distributed SGD. In this case, the gradient estimation error KErro vanishes with x O, which results in the exact error bound of vanilla distributed SGD. On the contrary, when all the layers are updated with staleness, SAPipe is reduced to PipeSGD with the gradient estimation error Erro and K 1.
Remark 2.
Theorem 3. Under Assumptions
/
5 and 6 taking a small enough X so that >11V22 -1-- V
and n S 1. after T iterations, for Algorithm
[SA (SAPipe-DC we have the following error bound:

---

+E [|V] & 2h + KErTDO + (1 - k)Van aro, where Errpc = 1281/* M - + 16V2
Remark 3. Regardless of the variance error, the main difference between the error bounds of vanilla SAPipe and SAPipe-DC the gradient estimation ervor. Note that if we have a small enough Hessian estimation error yielding very small M and A, by taking small enough q and making X 1, the overall gradient estimation error of SAPipe- DC is smaller than that of PipeSGD, i.e., ErTnC S Erro under certain conditions. In other words, SA SAPipe-DC has better convergence compared to PipeSGD when the Hessian approximation error is small enough.
Theorem 4. Under Assumptions
3 and 6 taking 7 I I. after T it- WP) with Option we have the following envor 2Rg + KE + Varo. where Errwp-1 =
2
erations, for Algorithm 3
(SAPipe-W??
bound: T +2 [V < 12r1² 1)) V/2 (3 4)
Remark 4. The main difference between Theorem 2 and Theorem 4 is the gradient estimation error, (3 -) 2) V1. When V1 and p are small enough (i.e., V1 S 2-e/u V2), SAPipe-W2 WP with Option produces smaller error compared the vanilla SAPipe, i.e., Errw Erro under certain conditions. In other words, SAPipe Pipe-WPPPPpe WP with Option I has better convergence compared vanilla SA SAPipe when the difference between the local datasets on different workers is small enough.
i... V2 versus (2 -2-1)
3-p/n
Theorem 5. Under Assumptions 1
2 and 6 taking 7) A.S S after T itera-
(SAPipe-WP) WPP with Option 2. we have the following error bound: L2n T Dt E [IVF((=-1))) S n + K.Errrr-22 + Varo, where Errwr-2 212 (2V) 2L 122)
tions, for Algorithm
3
2R.
Remark The main difference between Theorem 2 and Theorem 5 iss the gradient estimation error, Le., 1/2 versus 1-2f-=n² (2V1 + v2) When is small enough (i.e., I?2 1-2V,/V, ), SAPipe-Wi WP with Option 2 produces a smaller error compared to vanilla SAPipe, i.e., Errwp-2 < Erro under certain conditions. In other words, SA WP with Option has better convergence compared to vanilla SAPipe when the objective function is "smooth" enough.
4yp
Theorem Under Assumptions tions, for Algorithm (SAPipe-W) WPP) with Option 3, we have the following ervor bound: t- E [(I < 2Ro kErrwp-3 + Varo, where Errwp-3 = L2 of
and 6 taking n < 1. after T itera-
4n M2V3 + V2222 A)2 \2A?)].
Remark 6. The main difference between Theorem 2 and Theorem is is the gradient estimation error, i.e. V/2 versus Vi + 41)* M2 + V2 x)² >2 When т,, M, A are small enough and n is large enough, SAPipe-WP with Option produces a smaller error compared to vanilla SAPipe, i.e., Errwp-3- S Erro under certain conditions. Furthermore, À provides a trade-off between I and 2 If the objective function is relatively "smooth" yielding L < A, then X - is preferred, and otherwise > is preferred. In practice, since both and are unknown and depend on the model architecture and datasets, tuning X E [0, 1] is required for better performance.
is
Corollary 1. For vanilla SAPipe, SAPipe-DC and SAPipe-WP with all 3 options, taking &x min V 1)). we have
1 T ET E [[VF 5 VT
+ +
(VVT) same as vanilla SGD.
Remark 7. The corollary above shows that vanilla SAPipe. SAPipe-DC DC and SAPipe-Wi WP with all 3 options converge to a critical point where [[V - O, when T - +00, and the error decreases when there more workers. In general, vanilla SAPipe, SAPipe-DCC and SAPipe-WP
have the same overall convergence rate O VT However, the detailed gradient estimation error varies for different algorithmss as shown in Theorems 2
and Under certain conditions such low gradient variance, low grudient diversity, good smoothness, low Hessian approximation error, and specific choices of 1j and X one of these algorithms achieves the lowest convergence error. Hence, hyperparameter tuning and algorithm selection required in practice.
7

---

Table 2: Comparing model performance of SAPipe with baselines. We use perplexity (lower is better) as the metric for GPT-2, and accuracy (higher is better) for other models.
Model
VGG16
ResNet50
GPT-2
Transformer
Dataset
CIFAR-10
ImageNet
CIFAR-10
ImageNet
WikiText-2
Multi30K
BytePS
0.925 = 0.0020 0.731 + 0,0020 0.932 + 0.0022 0.762 a 0.0022
20. 10 + 0.23 0.673 = 0.0033
PipeSGD
0.906 = 0.0064 0.726 + 0.0019 0.893 + 0.0032 0.753 + 0.0015
22.36 + 0.33
0.531 = 0.0044
SAPipe-DC
0,908 = 0.0018 0.734 + 0.0011
0.894 + 0.0019 0.758 + 0.0150
22.50 + 0.48
0.526 = 0.0031
SAPipe-WP-OPT
0.926 + 0.0017 0.718 = 0.0020
0.932 = 0.0020 0.757 # 0.0022
21.80 + 0.25 0.663 = 0.0059
SAPipe-WP-OPE
0,902 = 0.0026 0.729 = 0.0059
0.908 + 0.0019 0.751 = 0.0061
22.60 + 0.09
0.662 = 0.0007
SAPIpe-WP-OPTS 0.914 = 0.0020 0.735 + 0.0038
0.897 = 0.0034 0.758 + 0.0013
20.23 = 0.32
0.668 = 0.0032
Over PipeSGID
2%
0.9%
3.9%
0.5%
2.13
13.7%
260
Sarge
Pedd00
1.0
GRUA
of GP
(a)
VGG16
(b) ResNet50
(c) GPT-2
(d) Transformer
Figure 3: Training throughput
Sybets
THE scuessy 8
3 3 92
Bypels
500
$18
SARipe
10
30
1020
2020
3000
2010
4020
6000
500
1200
1500
2000
(a) VGG16, ImageNet (b) ResNet50, CI (c) GPT-2, WikiText-2 (d) Transformer, Multi30K
Figure 4: Convergence of different models. x-axis wall-clock training time, and y-axis is perplexity (lower is better) for GPT-2, and test accuracy (higher is better) for others.
Evaluation
5.1 Set-up
Testbed. We evaluate SAPipe memory, 8 Tesla V100 GPUs with NVLinks, and 100Gbps bandwidth between any two machines.
P on 8 physical machines, each equipped with 90 CPU cores, 320GB
Models and datasets. We choose two CV models, VGG16 (27). ResNet50 [00. and two NLP models, pretrained GPT-2 [25], Transformer [29]. as our benchmark models. The batch sizes per GPU are 128 images, 128 images, 80 tokens and 3200 tokens, respectively. We adopt SGD optimizer with 0.9 Polyak's 's momentum [24] and 5e-5 weight decay when training VGG16 and ResNet50 models, and Adam [14] optimizer with (0.9, 0.98) betas for NLP models. The global learning rates for VGG16, ResNet50 and GPT-2 are 0.1, 0.1, and 5e-5, respectively, and we follow the learning rate setting in 29 when training Transformer. SAPipe uses Option in Algorithm as the default staleness compensation method, with X empirically set as 0.2.
We train CV models on two datasets: (i) CIFAR-10 [T6] and (ii) ImageNet [17. We fine-tune the pretrained GPT-2 model on (iii) WikiText-2 language modeling dataset (20). The Transformer model trained on (iv) Multi30K [8] for WMT16 English-to-German Multimodal Translation task.
Baselines. We compare SAPipe with three late-of-the-ar communication frameworks: (1) Horovod (26. high-performant all-reduce paradigm; (2) BytePS [3], an optimized parameter- server architecture; (3) PipeSGD [19, a pipelined training framework with 1-step staleness. All baselines and SAPipe are run on PyTorch computation framework. 4
?Code: https://github.co wwwpitthhuh.ooocCooom www./oooo///hccoecc Chipprissaapipe.gii
*Since PipeSGD not open-sourced, we implement its staleness pipeline based on BytePS architecture. 'Magnified figures and additional experiment results are in the Appendix.
8

---

Ac3
Speed
Acc
100
1.6
SytoPs
we optimized runtimme SAPps
90
ResNet50, CIFAR-10 ResNet50, ImageNet
Spoeed (mingin))) 60
e 1.2
Accuracy
80
1.0
80
Transformer, Multi3OK
70
b 0.5
60
0.4
70
0.2
BytePS PipeSGD SAPipe
0.0
VGG16
ResNet50
GPT-2
0.2
0.4
(a) VGGI6 with partial staleness.
(b) Runtime optimization.
(c) Sensitivity analysis
Figure 5: Deep dive in SAPipe. "SAPipe w/o" denotes SAPipe without partial staleness.
5.2 Results and Analysis
Convergence. Figure shows the convergence curves when training DNN models with 16 GPUs. We observe that SAPipe converges much faster than baselines. not only achieves the highest training throughput, but also incurs very little influence model convergence. For example, SAPipe roughly 35%, 67% and 21% faster for VGG16 than BytePS, Horovod and PipeSGD, respectively. Though PipeSGD has comparable training speed, it converges much slower across models, and decreases final accuracy by 13% with Transformer. This reveals the obvious error incurred by 1-step staleness.
Staleness mitigation. Table 2 lists the final model performance of different frameworks, 5 SAPipe achieves comparable test accuracy and perplexity with non-stale baseline, BytePS. PipeSGD incurs significant performance drop on four models. With staleness compensation, SAPipe solves the convergence problem with staleness pipeline, while greatly boosting the training speed. Overall, SAPipe achieves significant improvement in accuracy/perplexity over PipeSGD of 2.6%, 3.5%, 13.7% and 2. for VGGI6, ResNet50, Transformer and GPT-2, respectively.
We also compare different staleness compensation options SAPipe with baselines. The best option varies among DNN training jobs. For example. SAAPip--WP-OPTY (i.e., predicting weights using local gradients) achieves the highest test accuracy when training CV models on CIFAR-10, and "SAPipe-WPA WP-OPT3" (i.e., combined mitigation with WP and DC) is the best option for ImageNet, WikiText-2 and Multi30K datasets. Other options improve the convergence to some extent as compared to PipeSGD, but are suboptimal in these cases. The method to find the best staleness mitigation option for given DNN task is our future work.
Scalability. Figure 3 shows the throughput of baselines and SAPipe when training with different numbers of workers. SAPipe achieves up to 57% and 203% speedups over BytePS and Horovod in all settings. Horovod does not apply communication scheduling, which leads to the worst throughput. BytePS enables preemptive communication scheduling. but it does not overlap gradient synchroniza- tion of the first few layers with computation. Thus, the communication overhead in BytePS is still large for GPT-2 model. PiD performs the best among baselines, while SAPipe still achieves up to 6% speedup over PipeSGD, thanks to our tigh-peeformance runtime optimization.
Ablation study. We evaluate the effectiveness of each component of SAPipe. Figure 5(a) shows the throughput speedup and staleness mitigation with partial staleness when training VGGI6 on CIFAR-10 10 dataset with 8 GPUs We observe that with our partial staleness, SAPipe improves the final accuracy without slowing down training, by involving less delayed gradients.
We also compare SAPipe with BytePS, PipeSGD and SAPipe without runtime optimization when training DNN models with 32 GPUs, as shown in Figure (j.. We use the speedup over the BytePS baseline the throughput metric. "SAPipe w/o optimized execution" refers to a naive implementation of staleness-awan pipeline, which incurs non-negligible overhead for staleness mitigation. SAPipe achieves the highest throughput across all models, and the overhead of staleness mitigation decreases the training speed by 7% to 24% over SAPipe. Without runtime optimization, the staleness pipeline with mitigation methods could be slower than BytePS baseline by up to 6%.
Sensitivity. Figure 5 varies the value of hyperparameter À in WAP-P3" method when training ResNet50 and Transformer. We observe that the staleness compensation method is not
$ Hooooodd does impact the convergence and has the same final accuracy BytePS, omit it.

---

sensitive to the hyperparameter, and achieves the highest accuracy when it reaches 0.5, 0.2 and 0.2 when training on CIFAR-10, ImageNet and Multi30K datasets, respectively.
Related Work
optimization. Many popular ML frameworks, such as TensorFlow [ and Py- Torch [22] enable overlapping communication with backward propagation by default. Recent further overlap gradient synchronization with forward computation via tensor partitioning. at the cost of extra overhead. ASP [6] advocates asynchronous training to improve com- munication efficiency; without controlling the staleness, it leads to unstable convergence. SSP [1]] is another asynchronous training protocol with bounded staleness. PipeSGD [9] restricts the staleness one step training. However, these methods do not mitigate the error caused by staleness, which degrades the model performance. We focus on synchronous pipelined training, without gradient compression. We minimize the number of stale layers, and propose multiple staleness compensation methods, achieving both high training throughput and comparable accuracy.
Communication
works 12
23 3
Staleness mitigation. Staleness mitigation is important for asynchronous SGD. Widely used ap- proaches include staleness-awan aware rescaling of learning rate [2] and gradients 4 and delay compen- sation 33 [5 5
linear weight prediction to narrow down the difference between models used in forward and backward passes for model parallelism. In our experiments, we find that simply using delay compensation linear weight prediction in PipeSGD results in poor convergence, which calls for better strategies. Furthermore, the additional overhead incurred by staleness mitigation motivates our co-design of training algorithms and system optimization. However, the best staleness mitigation method varies in different DNN tasks, and this is the limitation of SAPipe that requires empirical experiments to find the optimal solution.
7 Conclusion
We present SAPipe, performant and staleness-aware pipelined system to accelerate distributed DNN training without model performance loss. To fully overlap gradient synchronization communication with computation with minimal staleness, we introduce partial staleness, which restricts the number of layers learned with stale gradients. To further mitigate convergence issues caused by staleness, SAPipe adopts weight prediction and delay compensation. With algorithm-syster co-design, SAPipe achieves both better error bounds in theory, and high-performance runtime in practice.
Acknowledgments and Disclosure of Funding
We are thankful the anonymous NeurlPS reviewers for their constructive feedback. This work was supported in part by Hong Kong Innovation and Technology Commission's is Innovation and Technol- ogy Fund (Partnership Research Programme with ByteDance Limited, Award No. PRP/082/20FX), and grants from Hong Kong RGC under the contracts HKU 17204619, 17208920 and 17207621.
References
[1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large-scale machine learning. In OSDI, 2016.
[2] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-Efficie SGD via Gradient Quantization and Encoding. In NeurlPS, 2017.
[3] Yixin Bao, Yanghua Peng, Yangrui Chen, and Chuan Wu. Preemptive All-reduce Scheduling for Expediting Distributed DNN Training. In INFOCOM, 2020.
[4] Saar Barkai, Ido Hakimi, and Assaf Schuster. Gap Aware Mitigation of Gradient Staleness, In ICLR, 2019.
[5] Chi-Chung Chen, Chia-Lin Yang, and Hsiang- Yun Cheng. Efficient and Robust Parallel DNN Training through Model Parallelism on Multi-GPU Platform, arXiv preprint arXiv: 1809.028399 2018.
10

---

[6] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large Scale Distributed Deep Networks. In NewrlPS, 2012.
[7] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL, 2019.
[8] Desmond Elliott, Stella Frank, Khalil Sima' an, and Lucia Specia. Multi30k: Multilingual english-german image descriptions. In VL@ ACL, 2016.
[9] Sayed Hadi Hashemi, Sangeetha Abdu Jyothi, and Roy Campbell. TicTTac Accelerating Distributed Deep Learning with Communication Scheduling. In MLSys, 2019.
[10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In CVPR, 2016.
[11] Qirong Ho, James Cipar, Henggang Cui, Seunghak Lee, Jin Kyu Kim, Phillip B Gibbons, Garth A Gibson, Greg Ganger, and Eric Xing. More effective distributed ML via a Stale Synchronous Parallel parameter server. In NeurlPS, 2013.
[12] Anand Jayarajan, Jinliang Wei, Garth Gibson, Alexandra Fedorova, and Gennady Pekhimenko. Priority-based Parameter Propagation for Distributed DNN Training In MLSys, 2019.
[13] Yimin Jiang, Yibo Zhu, Chang Lan, Bairen Yi, Yong Cui, and Chuanxiong Guo. A Unified Architecture for Accelerating Distributed DNN Training in Heterogeneous GPU/CPU Clusters. In OSDI, 2020.
[14] Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. CoRR, abs/1412.6980, 2014.
[15] Atli Kosson, Vitaliy Chiley, Abhinav Venigalla, Joel Hestness, and Urs Koster. Pipelined Backpropagation at Scale: Training Large Models without Batches. In MLSys, 2021.
[16] Alex Krizhevsky, Geoffrey Hinton, al. Learning Multiple Layers of Features from Tiny Images. 2009.
[17] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet Classification with Deep Convolutional Neural Networks. In NeurIPS, 2012.
[18] Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor-Yiing Su. Scaling Distributed Machine Learning with the Parameter Server. In OSDI, 2014.
[19] Youjie Li, Mingchao Yu, Songze Li, Salman Avestimehr, Nam Sung Kim, and Alexander Schwing. Pipe-SGD: Decentralized Pipelined SGD Framework for Distributed Deep Net Training. In NeurlPS, 2018.
[20] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer Sentinel Mixture Models. arXiv preprint arXiv: 000900789030 2016.
[21] Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory F. Diamos, Erich Elsen, David Gareía, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, and Hao Wu. Mixed Precision Training. In ICLR, 2018.
[22] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. PyTorch: An Imperative Style, High-PPeformance Deep Learning Library In NeurIPS, 2019.
[23] Yanghua Peng. Yibo Zhu, Yangrui Chen, Yixin Bao, Bairen Yi. Chang Lan, Chuan Wu, and Chuanxiong Guo. A generic communication scheduler for distributed DNN training acceleration. In SOSP, 2019.
[24] Boris Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964.
11

---

[25] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language Models are Unsupervised Multitask Learners. OpenAl blog. 1(8):9 2019.
[26] Alexander Sergeev and Mike Del Balso. Horovod: Fast and easy distributed deep learning in TensorFlow. arXiv preprint arXiv: 2018.
[27] Karen Simonyan and Andrew Zisserman. Very Deep Convolutional Networks for Large-scale Image Recognition. In ICLR, 2015.
(28) Xu Tan, Xiao- Shen, Xiao-Chun Ye, Da Wang, Dong-Rui Fan, Lunkai Zhang, Wen-Ming Li, Zhi-Min Zhang, and Zhi-Min Tang. non-stop double buffering mechanism for dataflow architecture. JCST, 2018.
[29] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In NeurlPS, 2017.
[30] Dong Yin, Ashwin Pananjady, Maximilian Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter L.. Bartlett. Gradient Diversity: a Key Ingredient for Scalable Distributed Learning. In AISTATS, 2018.
[31] Hao Zhang, Zeyu Zheng. Shizhen Xu, Wei Dai, Qirong Ho, Xiaodan Liang, Zhiting Hu, Jinliang Wei, Pengtao Xie, and Eric P Xing. Poseidon: An Efficient Communication Architecture for Distributed Deep Learning on GPU Clusters. In ATC, 2017.
[32] Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-Aware Asyne-SGD for Distributed Deep Learning. In IJCAI, 2015.
[33] Shuxin Zheng, Qi Meng, Taifeng Wang. Wei Chen, Nenghai Yu, Zhiming Ma, and Tie-Yan Liu. Asynchronous Stochastic Gradient Descent with Delay Compensation. In ICML, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In Section 5 (Experiment) and Section (related work)
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Section 4.1
(b) Did you include complete proofs of all theoretical results? [Yes] Appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Section 4. and source code
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
12

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A] Publicly available benchmarks
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "z_UFq0MAZO8", "reviewer": "Reviewer_oko6", "summary": "One of the challenges with scaling data parallel training of neural networks is that the natural dependencies between the forward propagation, backward propagation, and gradient updates limits the benefits of parallel execution.  A common solution in the state of the art is to use stale gradients to allow the gradient updates to overlap with the data motion between parallel ranks.  However, the use of stale gradients typically leads to a lower quality of solution in the trained network.  This paper presents several methods for addressing the staleness of gradients, using three techniques: partial staleness for “earlier” layers of the network, delay gradient compensation, and weight prediction.  Using these techniques they demonstrate that they can achieve runtime performance similar to the SOTA using stale gradients, but with a quality that nearly matches a standard SGD training approach.  The paper also provides both a convergence analysis and experimental analysis with both visual and language models demonstrating the impact of their proposed techniques.", "questions": "Figure 1 is introduced early in the text, prior to any significant discussion of partial stale gradient updates, yet it is illustrating partially stale gradients.  The figure, text, and caption should be refined to indicate that it is not showing the state of the art, but actually part of the proposed method.\n\nThe implementation of Algorithm 1 is strange.  Specifically, line 6 is weird for the base case.  For it to say “same as t > 1” should be clarified that there is really only a conditional for the PipeSGD case.\n\nFigure 2 doesn’t really convey what the authors probably intended for explaining the algorithm and does not contribute too much as is.  For subfigure 2a, the fact that the parts of the staleness-aware system are all in the lower box but with no real relationships between them and the runtime parts of the system is not helpful to the reader.  Furthermore for 2b, it would be better to represent the communication pattern with some sort of parallel timeline.  Again, with the cyclic dependencies of iterative training, the interplay of the communication isn’t clearly conveyed by 2b.\n\nIn the equation below line 111 it is not clear what u is as it doesn’t appear in the table.\n\nOn line 119 a figure that clearly shows how partial staleness / gradient updates works would improve the discussion.\n\nReplace Figure 5 analysis with a more challenging example for the ablation study, i.e. ResNet on ImageNet or one of the transformers, or both.", "limitations": "The biggest issue is that of the proposed techniques, on the use cases shown, one combination does not always win.  As a result it is not clear if these approaches were to be applied to a new problem area, which set of the staleness compensation techniques should be used.  Without some discussion of this, it is not clear how to leverage this work going forward without actually performing something of this analysis.  Furthermore, the section on sensitivity analysis does not address this.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper leverages multiple advancements in the community and integrates them into a common composition and framework, demonstrating that in aggregation they can provide an approach that is performant in terms of both speed and quality of the trained network.  Overall, they clearly indicate where the derived ideas come from, how they were used previously and how they are being integrated into a combined algorithm.  The explanation of the algorithm and visualization via diagram could use some improvement.  Please see the next section for specific comments, however, the reader is left with a general understanding of how the algorithm execute at runtime, but some better figures could significantly improve this.\n\nThe evaluation of the algorithm is mixed.  Overall it is good that the authors include both visual and language models, however, using VGG16 on CIFAR-10 for the ablative study is not nearly as interesting as if they had used a more modern and interesting model (e.g. ResNet or GPT-2).  Additionally, the later part of the paper is quite rushed with minimal explanation and analysis of the results.  For example Figure 5 has no analysis in the caption and only a bit in the text.  On a similar note, Figures 3-5 are extremely small and clearly not really meant for a reader to actually read.\n\nOne key challenge for this work is that none of the proposed optimization schemes performed the best on all benchmarks, and thus is is not clear a priori as to which technique (Opt1 - 3) should be used when.  This can pose a significant challenge to future application if a researcher would have to conduct an exhaustive test of all optimization methods to determine which may produce the best results for a new application.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hEajH28cCFX", "reviewer": "Reviewer_5UGd", "summary": "Synchronous data parallelism is widely adopted, but can suffer from poor scaling due to excessive communication overheads. This paper proposes using stale weight updates (weight gradients computed using the not latest weights) to better overlap computation and communication. It discusses various mitigation techniques to get bounded-stale data parallelism to work well in practice.", "questions": "- Are the ideas of delay compensation and weight prediction new? Don't these papers propose similar ideas for pipeline parallelism without flushes (which shouldn't make a difference): PipeMare [https://proceedings.mlsys.org/paper/2021/file/6c8349cc7260ae62e3b1396831a8398f-Paper.pdf] and Kosson et al. [https://arxiv.org/pdf/2003.11666.pdf].\n- Why does the optimization problem at the top of page 4 have a runtime complexity of O(m^2)?\n- What batch size was used? Communication overhead is smaller with larger batch sizes.\n- What is the effect of hardware (compute accelerator and network) on performance?\n- What is the effect of model on performance?\n- How much worse convergence rate (accuracy vs. number of iterations) does SAPipe have compared to synchronous DP (BytePS or Horovod)?\n- How much do the proposed mitigation techniques (delay compensation and weight prediction) help with convergence? What if I don't use any mitigation techniques? How badly does this do?", "limitations": "The authors did not discuss limitations of their work. Some discussion of situations where they expect SAPipe to not be a useful solution (e.g., particular types of models, hardware deployments, optimizers, or other situations where their theoretical analysis breaks down).", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### Strengths\n- The paper offers an alternative to synchronous data parallelism in situations where the network is not fast enough to hide the cost of communication.\n- The paper is well written and clear.\n- Distributed training performance is an important problem in Machine Learning Systems, and this paper proposes one more possible solution to the problem. \n\n#### Weaknesses\n- Evaluation is not entirely convincing: for example, Figure 4 shows accuracy vs. time, but I would have also liked to see accuracy vs. iteration to see the impact on convergence speed.\n- Baselines seem if-fy: why does ResNet-50 scale worse than GPT-2? I expect the convolutional layers in a ResNet-50 model to be much more amenable to data-parallel-style communication compared to a GPT-2 model with a lot of linear layers in the attention layers. VGG-16 doesn't scale well exactly for these reasons.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eWfRcdWc7QG", "reviewer": "Reviewer_9R6e", "summary": "This paper presents SAPipe, a system to support efficient data parallelism, where communication is effectively hidden within computation with adaptive staleness and corresponding compensations. Both theoretical analysis and empirical study are conducted to verify the effectiveness of the proposed solution.  ", "questions": "N.A. ", "limitations": "Perhaps some discussion about the scope of models should be considered; for example, can this approach be used for graph neural network training, where the layers in the model are not linearly stacked?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The idea of improving PipeSGD with adaptive partial staleness is simple but effective.\n\n- Theoretical analysis is provided to justify the design of the algorithm. \n\n- The experiment section is solid, and the performance boost is significant. \n\nWeaknesses:\n- Some writing and illustration can be further polished. For example, Figure 1 is a little confusing; for the default pipeline part, it seems that v3 begins before the end of b3 visually, this sees inaccurate without mentioning any potential other optimization, e.g., communicating in a thinner granularity. \n\n- Some reasonable baseline approaches are missing. For example, PyTorch-DDP should be included because it is a very popular data-parallel implementation and provides efficient system optimizations such as bucketing and communication overlapping.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept