DropCompute: simple and more robust  distributed synchronous training via compute variance reduction
Authors: Niv Giladi
Shahar Gottlieb
Moran Shkolnik
Asaf Karnieli
Ron Banner
Elad Hoffer
Kfir Yehuda Levy
Daniel Soudry
Venue: NeurIPS 2023 poster (2023)
Keywords: distributed optimization
large-scale parallel SGD
synchronous training
TL;DR: A new method for improving the robustness and scalability of synchronous training

Abstract: Background: Distributed training is essential for large scale training of deep neural networks (DNNs). The dominant methods for large scale DNN training are synchronous (e.g. All-Reduce), but these require waiting for all workers in each step. Thus, these methods are limited by the delays caused by straggling workers.
Results: We study a typical scenario in which workers are straggling due to variability in compute time. We find an analytical relation between compute time properties and scalability limitations, caused by such straggling workers. With these findings, we propose a simple yet effective decentralized method to reduce the variation among workers and thus improve the robustness of synchronous training. This method can be integrated with the widely used All-Reduce. Our findings are validated on large-scale training tasks using 200 Gaudi Accelerators.

Doopeompute: simple and more robust distributed synchronous training via compute variance reduction
Niv Giladi
Shahar Gottlieb
Moran Shkolnik 1.2
Asaf Karnieli
Ron Banner
Elad Hoffer²
Kfir Yehuda Levy'
Daniel Soudry!
TTechnion Isracl Institute of Technology
Habana-Labs
(giladiniv, moranshkolnik, elad.hoffer, kfiryehud, damiel. sod.oooyrr)ggmalllc.oomm {sgottlieb, akarnieli, abammer)dhabana.aa
Abstract
Background. Distributed training is essential for large scale training of deep neural networks (DNNs). The dominant methods for large scale DNN training are synchronous (e.g. All-Reduce), but these require waiting for all workers each step. Thus, these methods are limited by the delays caused by straggling workers. Results. We study a typical scenario in which workers are straggling due variability in compute time. We find an analytical relation between compute time properties and scalability limitations, caused by such straggling workers. With these findings, we propose simple yet effective decentralized method to reduce the variation among workers and thus improve the robustness of synchronous training. This method can be integrated with the widely used All-Reduce. Our findings are validated on large-scale training tasks using 200 Gaudi Accelerators. reference implementation is provided.
Introduction
Deep Neural Networks (DNNs) training continues to scale over size and computational footprint, as result of higher number of trainable parameters, wider and deeper models, and growing amounts of training data. As improvements in model quality (measured by test loss, for example) (Kaplan) al. (020)) lead over hardware capabilities (Hooker 2020). this scale-up translates into need for growing number training devices working in tandem (Chowdhery et al.] 2022). turning distributed training the standard approach for training DNNs
large scale.
Distributed training typically refers to three parallelism paradigms - data parallel, model parallel and layer pipelining (Ben-Nun & Hoetler 2019). Several variants and hybrid solutions exist in modern implementations such as tensor parallel (Narayanan et al. (202]) and parameter sharding (Rajbhandar) et al. 2020 Rasley et al. 2020). These can be used separately combined they orthogonal to each other. Mainly, data parallelism is straightforward, where the data is sharded among workers, and all workers share the same global model state. At each step, workers compute gradients locally and then aggregate them before taking an optimization step. When training synchronously, workers update their parameters in lockstep. This ensures that all workers hold a consensus on the same model and that gradients are averaged over all workers before being applied to the model. This approach is easy to implement and allows for good convergence properties, and correspondingly is the prevalent optimization method.
Equaal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Linear
250
Linear
20
Baseline
200
Baseline
DropCompute
DropCompute
Speedup
Speedup
15
150
10
100
50
0
0
50
100
150
200
0 500
1000
1500
2000
Workers
Workers
Figure 1: DropCompute improves robustness and scalability of synchronous training. A scale graph, showcasing the proposed method runtime performance of synchronous training of 1.5 billion parameter model with additive noise, simulating compute variance. The baseline represents existing synchronous training and the dashed black line linear scaling. (left) Real measurements of up 200 workers. (right) extrapolation 2048 workers using a theoretical estimation, also proposed in paper. More details are provided section 5.2
Although state-of-the-ari models use synchronous optimization for training, synchronous methods scale poorly, stragglers and communication overhead might severely deteriorate system utilization. Many resources are invested in alleviating these issues in large-scale training systems since even minor improvements can be worth hundreds of thousands of dollars. These issues are exacerbated as the required scale grows, even in homogeneous high- pett-rrrffomee computing clusters (Petrini et al.) interested in cases where significant computing
2003 Hoefler et al., 2010). In this paper, variace between the workers exists. This includes (but not limited to) straggling workers.
For instance, certain learning tasks entail heterogeneity in the required computation of data, such as varying sentence lengths in language processing, or different image sizes and frame numbers in computer vision. In addition, recent state-of-the-an models use all three parallelism paradigms (data (DP), tensor (TP), and pipeline (PP) parallelism), thus each data parallel node is a set of processing units (accelerators) communicating between them (via TP and PP) to calculate the model gradients collectively. This could potentially intensify compute variance between data parallel workers. Moreover, sub-optimal hardware systems also lead to straggling workers. Although some sources of heterogeneity can be mitigated by non-trivial engineering work, they still persist as challenges that can introduce compute variance and substantial performance drops. This is further discussed in appendix [A]
In this paper, we suggest simple, yet effective method called DropCompute to improve the robustness and scalability of synchronous optimization the face of compute variance. We model the compute time random variable and show that under reasonable assumptions, tail of straggling workers slows down the system at a rate that is not proportional the contributed compute by these straggling workers. We harness the gradient accumulation method widely used in Large Language Models (LLMs) (Ott et al., 2018 Liu al. 2019) to implement the method a few lines of code on a relevant large-scale learning task.
The contributions of work include:
DropCompute: a novel, decentralized method to better handle heterogeneity or stragglers without additional typer-parameters. DropCompute is hardware and framework agnostic, runs on top of existing optimizers, and can also be combined with other methods that improve other aspects of robustness such communication overhead.
A theoretical convergence proof of SGD with stochastic batch size, in DropCompute.
A theoretical runtime analysis on standard synchronous training and the proposed method. We find an approximation of the expected speedup using DropCompute, and show this speedup goes infinity as the number of workers grows.
An empirical evaluation of proposed method on a relevant large scale task, using up to 200 accelerators connected with high bandwidth communication. For example, when using DropCompute before and after system optimizations (for both software and hardware) we show accelerations of 18% and 5%, respectively.

---

2
Related Work
The challenge of training deep neural networks on large scale has been extensively explored. With rapidly growing models and data sizes, numerous works tackled the weaknesses in synchronous DNN training on a large scale and suggested methods to alleviate these weaknesses.
Redundancy methods. This line of work addresses the straggling worker problem using a redundancy mechanism. Redundant workers or redundant data are used such that straggling workers will not slow down the entire system (Chen et al., 2016; Bitar et al. (2020). These methods provide better robustness synchronous training, even in the event of a complete failure of subset of the workers or considerable communication slowdown. However, the robustness is limited by the redundancy factor, and more generally, more compute resources are required and full utilization cannot be achieved. In addition, some coordination method is required to keep the training synchronous, i.e., keeping consensus between the model replicas of the workers. In particular, Chen et al. (2016); Bitar et al. (2020) use a centralized approach of a parameter server to determine which workers are left out at each iteration. Modern large-scale systems use decentralized variants of All-Reduce (von Luxburg et al.) Patarasuk & Yuan 2009). so it is not trivial to determine which workers should be considered at each step, given that each worker can see different subset of straggling workers. Moreover, combining redundancy with communication primitive collectives (c.g., All-Reduce) requires adaptation to existing underlying frameworks (Sanders et al. 2019).
Asynchronous optimization. Another approach is introducing asynchrony to the optimization. Asynchronous training is inherently more scalable than synchronous training by being robust to all kinds of workers and communication faults. This includes periodic synchronization by exchanging parameters every 7 optimization steps (Stich 2019; [in et al.) 2020 Wang & Joshi 202 Zhang et al. 2015 Wang et al. 2020; Li et al.) (220blaa). approximate distributed averaging where each worker communicates with a subset of workers each step (Jiang et al. 2017 Lian et al.) 2017: Assran ct al. 20199] Yang et al. 2020), and many more. These works provide better scale-up properties and improve time performance. The main drawback is asynchronous optimization itself. In practice, the convergence is less stable, and more optimization steps are needed to generalize synchronous training. In addition, hyperparameters should be chosen more precisely to guarantee convergence and generalization properties (Giladi et al. 2019 Mitliagkas al. 2016). Due to these issues, asynchronous methods are less commonly used on a large scale.
well as
Sparse and compressed communication. Alternatively, several works addressed only the communi- cation overhead, common technique to reduce the amount data exchanged by the workers at each step. This can be done by gradient pruning (Xu et al.] (02T), gradient compression (Seide itt al., 2014; Chen et al., 2020; Tang et al. 202I) or low-rank approximation (Vogels et al.) 2019). These works reduce the communication overhead in deterministic form while ignoring any compute variance across processing workers. This makes these works orthogonal to ours and potentially can be combined with method.
3 Reducing Compute Variance
This paper proposes method called DropCompute that improves the robustness of synchronous training by reducing compute variance. First, we describe the vanilla synchronous training framework. Then, introduce the proposed approach.
3.1 Problem setup
We start with model formulation for data-parallel synchronous SGD training with N workers, where each worker holds replica of the model parameters 0. In parallelism paradigms that combine TP or PP with DP, N represents the count of data- paralearallel workers, not the total number of workers involved in training. Given dataset D, we are interested in minimizing the empirical loss
0)D,0)
1 D
Σ ((2.0), ZED
where ((2,0) the loss with respect to data-point z and the model parameters At each step, the workers calculate gradients based on a local batch and then aggregate the gradients before taking an
3

---

optimization step. An equivalent strategy would be that the workers aggregate the parameters after taking an optimization step based on the local gradients. The aggregation done in decentralized fashion, such as AllReduce.
We also consider the of gradient accumulation increase the size of the local batch. Gradient accumulation breaks down each worker's s local batch into M micro-batches for computation, which enables reaching a large global batch size beyond hardware capacity. This is common practice in training of LLM on large scale where a substantial number of accumulations are being utilized (Smith al., 2022 Nvidia 2023). In each iteration and accumulation m, the gradients of the loss function with respect to the model parameters are computed, denoted by
(m (0.) V LD(D), s,n 0.)
(m)
In
where (m)) in C D is the micro-batch m of worker sampled without replacement from D, and we assume constant micro-batch size [D The gradients accumulated by worker at step i are
gn (0.)
1 M
Σ (0:).
Finally, the workers aggregate and average the computed gradients to update the model parameters
1 N Σ gn (0.),
0.t1 (.)) g(O,)
(1)
where 1) is the learning rate. Equation E requires all workers to receive all gradients before updating the parameters. This communication restriction is what makes the training synchronous and ensures the model parameters are the same for all workers. However, due to this restriction, the slowest worker each step dictates the iteration time. More generally, any variation in computation time among workers will lead to workers with idle time. Therefore, to improve the efficiency and robustness of the synchronous training process, we need to reduce the computation time variance among workers (namely, the compute variance).
3.2 Our method: DropCompute
To mitigate the effect of compute variance and improve the robustness of synchronous training, we propose simple yet effective method called DropCompute. DropCompute reduces the compute variance by introducing compute threshold after which workers have stop calculating local gradients and move directly to the communication phase, i.e., Equation
In each iteration i, each worker measures the time while calculating its local batch, and compares it against a given threshold т, which is set as described section 4.4 that time exceeds the compute threshold, the worker stops and sends the gradients it has calculated so far. The rest of the training remains unchanged, thus synchronous training is intact. The pseudo-code of DropCompute is shown in Algorithm|| [ This method maintains decentralized approach while improving its robustness to compute variance and stragglers in particular. Since our method drops samples, the batch size is longer deterministic. Specifically, the total batch size (the total number of samples used in one iteration by workers) can be smaller than the maximal total batch size bmax = M (M(())) ( Nevertheless, we show both theoretically and empirically that this makes no difference to convergence or generalization when the number of computed samples remains the same. Next, we analyze this method in section aad evaluate it in section 5
4 Method Analysis
After establishing the notion of compute variance and the formulation of the proposed method, we analyze synchronous training and the potential value of the proposed method on the training time performance. To do so, we start with convergence guarantees when using DropCompute. Then, we theoretically analyze the computation time with synchronous training and when using DropCompute. Through this analysis, estimate the potential speedup over vanilla synchronous training.

---

Algorithm DropCompute on worker n. at iteration i
1: Input: model parameters 0;; total number of micro-batched M; compute threshold 7
2: local batch data Di, (D ( i....... " step time Tn to compute local batch Di,
3: Initialize step time 7n = 0 and accumulated gradients go.()) 0
4: do (1) and (2) parallet:
5:
(I) for ghih) (0.) VC(D (m) im 0t)
................................ MM do
6:
Compute gradient
7:
In. (0.) + 9n (0,) (++)= + g!(Tm) (0.)/M
> Accumulate gradients (atomic)
8:
(2) wait for Tn > and break for loop (1)
9:
Output: In (n:):)
AllReduce
4.1
Convergence analysis of DropCompute
Using DropCompute, the batch size is no longer fixed, but random variable, which can also potentially depends on the data samples. To the best of our knowledge, this setting is somewhat different from existing convergence guarantees. Therefore, in this section, we provide convergence guarantees for DropCompute by analyzing the convergence of SGD with stochastic batch size.
Assumption 4.1. Following the notations in section consider possibly non-convex smooth loss function L(D, 0), with a global minimum E Rdd and the following (commonly used) assumptions
1. L-smooth: All functions C(,,0) with L-Lipschitzian gradients.
2. Unbiased estimation: Each Vl(z, 0, E DD an unbiased estimate of L 0:) which is the true (full batch) gradient at 0 Namely, Vi [E[ 0,) = VL 0,)
3. Bounded variance: The variance of the stochastic gradient is bounded by a constant Ø,
Vi: E(IV 0,) (CDD,6))1 o².
Theorem 4.1. Under the above assumption, applying SGD with DropCompute (Algorithm D. ensures
BI 2Lbmax (CD,
20 LIVILE 0, L(D,0*) VK
K
where bmax is the maximal total batch size, K is the total number of samples that are used throughout the training, 02 is the initial model, and is a random sample of 0; from the trajectory obtained by Algorithmm 7 where i is selected with probability proportional the total batch size at iteration i. The expectation is with respect to the randomization introduced due to sampling from 'D throughout the optimization process and with respect to choosing 0.
The bound in Theorem 4.1 is similar to existing fixed batch-size guarantees (Dekel et al. 2012). The second term in the bound does not degrade with the batch sizes, and behaves like D(1/VK) while the first term behaves like (bbaxx/ K). This implies that as long bmax O(vK) K), the second term dominant and we are in the regime of linear speedup. This shows we can attain a linear speedup despite using changing batch sizes, as long as the maximal batch size is bounded.
Similarly, in Theorem D.I in appendix D.I we show that the loss itself converges, in the convex case along with a proof. The proof of Theorem 4. is provided in appendix D.2 Lastly, we discuss the impact of the stochastic batch size on generalization appendix D.4
4.2 Iteration time in standard synchronous distributed training
We start with finding dosed-form expression for the cumulative distribution function (CDF) of the iteration time, denoted as T, defined as
max (71, T2...., Tx),
This is easily satisfied when all workers access all data.
5

---

where T, represents the time taken by worker to compute its local batch, which follows some cumulative probability function Fr, (I) = PTT, z), which we assume is independent for each worker. Let (r(x) represent the cumulative distribution function and fr(x) represent the probability density function the maximum iteration time T. The relation between Fr(x) and Fr,, (æ)
(x P (max (Ti TN) - x)
II Fr, (z).
Differentiating with respect to x and applying the chain rule gives:
dFr
fr(x) = dr (x) JT. (z)
II Fr. (a.)
n=1
In the special case where all of the workers' iteration time distributions are identically and indepen- dently distributed (i.idd), this reduces to the well-known formula:
fr( = N fr. Fr. (x)
(3)
If the iteration time of each worker is distributed normally (~ NN,, o))). the expected value of T can be approximated shown by Bailey et al. (2014):
B(T) R a. (1-7).0-1
x (1 (1- +
e )1- + #M
+7. Φ-
(4)
where & is the CDF of the standard normal distribution, and is the euler-mascheroni constant. Asymptotically the total iteration time E[T] = (vologV). When the number of micro-batches
M > 1, we can make a similar approximation under Central Limit Theorem (CLT) conditions. More details are in appendix C.2
4.3 Iteration time and number of micro-batches with DropCompute
When using DropCompute with constant threshold т, each worker is preempted at T, min {T, J and joins the AllReduce. Therefore, the total iteration time with DropCompute
T+ min min (T,T)+T* +T,
where 7 a serial latency present in each iteration, which includes the AllReduce step. This upper limit serves to clip extreme values of T,, effectively constraining the range of potential outcomes for T. As a result, the compute time variability decreases, leading to narrower distribution and enhanced compute efficiency. These effects are illustrated in Figure 2
As consequence of preempting each worker at T,, the number of micro-batches computed in each step varies. Denote as {((m) the compute latency of a single micro-batch m for worker n, and m (3) We can define the average number of micro-batches computed by each worker ン
T (m) before reaching threshold т as
M
1, if if <T
M
0,
otherwise
Under CLT conditions, the expected value M can be approximated in a closed form:
1 m T
E
(5)
where μ, o² are mean and variance for a single micro-batch (1r) compute latency, and the CDF of the standard normal distribution. This approximation closely fits the real value of M and can be used to analyze the expected gain from DropCompute. More details in appendix C.2

---

Real
no drops
Simulation
20
1% drop
3% drop
density
densily
5% drop
10
drop
7.4
7.6
7.8
8.0
8.2
8.4
8.6 B.E
7.8
8.0
8.2
8.4
8.6
8.8
9.0
step compute time [sec]
compute time 7 [sec]]
Figure 2: Reduction in variance and mean iteration time using DropCompute. Iteration time distribution of 200 workers using DropConpute on BERT 1.5B. (left) Step time T. distribution all workers, without DropCompute. (right) Maximum iteration time T, across all workers, using DropCompute, with different drop rates. The dashed 'simulation' distribution is generated by drawing Tn randomly from an independent normal distribution separately for each worker, using the empiric and variance of that worker.
4.4 Choosing the threshold
The throughput of the system can be the number of mncro-bbtthees computed per second. For N workers, this can be written as N NM/(T + To). To evaluate the effectivness of DropCompute, we consider the difference in throughput between the baseline and when using DropCompute. Doing so, we can define the effective speedup for т as:
Seff (T) DropCompute Throughput NMM/Miin (T, {T,T}+ +
M + + Mmin {T, T) + Tc)
(6)
Baseline Throughput
NM/(T + Tc)
Given the statistical characteristics of the training setting, it is possible estimate analytically the expected value the effective speedup ([See(()) ) by using Equations 5
and Moreover, when plugging in the asymptotic form of [[T), we find the expected speedup increases infinity with N
E (eVee((lgg log.N
(F)(N())
N
As shown in figure 3b Equation 4 less accurate when samples deviate from a normal distribution.
To find the optimal compute threshold, we synchronize the empirical distribution of micro-batch
a
(b)
(c)
250
20
simulation
20
Sen(T)
analylical
200
15
150
7
100
Mi
10
10
50-
simulation
5
analytical
analytical given E(T)
50
0-
2.5
5.0
7.5
10.0
10
15
Threshold [sec]
Threshold [sec]
Threshold [snc]
Figure 3: Statistical characteristics of the micro-batch computation latency {(()) can provide reliable estimate of the effective speedup Sot. The graphs depict Satt (7) based on Equation Calculations rely on
samples of ((m) to calculate M and before plugging them into Equation In the 'simulation' curves, directly use the samples to calculate M and T. For the 'analytical' curves, only the mean and variance of (m) are used to approximate and T using Equations and respectively. For 'analytical given R[T]'. M is approximated using Equations 5 but E[T'] is calculated directly from the samples. More details in appendix
C.2 Panels: (a) The z(m)) samples follow normal distribution. (b) samples are taken from BERTI.S 1.5B pre- training with simulated delay described in Section (c) The optimal compute threshold can be found automatically. The effective speedup, micro- batch completion rate, and step speedup as function of in simulated delay environment.
compute latency between all workers after few iterations. Given this distribution, we find 7 and M, and search in a decentralized way for the threshold r* that maximizes the effective speedup San (T)

---

defined in Equation 6 Overall, the cost of synchronizing the empirical distribution and finding r" is negligible, compared full training session, because happens only once in a training session. Lowering the threshold leads to reduced compute time but higher compute drop rates. Figure 3c highlights this trade-off and the optimal r* marked.
4.5 Compensating for dropped samples
The effective speedup metric Seff. accounts for dropped samples by treating them as a source of slowdown in direct proportion to the drop rate. This consideration enables us execute additional computations to achieve the theoretical speedup. The extent of extra time spent on redundant calculations can be as much as R = (M/M - 1) times the computational effort required when not applying DropComp
For instance, when 10% of the samples are dropped, we can expect to perform approximately 11% more calculations. Achieving this can be approached in several ways. One straightforward compensation method for LLM training involves adding an extra R Iasee steps to the training process, where hase represents the number of training steps conducted without using DropCompute. In practice, achieving the original accuracy often requires even fewer additional steps, as illustrated in Figure 5 resulting in an higher effective speedup.
Another method of compensating for the dropped samples is increase the maximal batch size. When increasing the batch by R and dropping in average .M /M, we keep the average batch size the same as without using DropCompule, hence compensating for the lost samples. A third method, orthogonal to the first two, resampling dropped samples before starting a new epoch to diversify the overall samples seen by the model. These approaches are rigorously tested and compared in Table Tb
5 Experiments
To be useful, DropCompute must possess two properties. First, it should not compromise the accuracy of the trained model. This property is put to test in section 5.1 where we fully train BERT-Large and ResNet-50 (Devlin et al. 2018 He et al. 2015), each on a different task, with different drop rates to compare accuracy. Second, DropCompute should maintain a high level of runtime performance, especially when compute variance or straggling workers exist and vanilla synchronous training time deteriorates. Section 5.2 tests runtime performance of DropCompute by training 1.5 billion parameter language model, BERTI, 1,5 (Devlin et al., 2018) with additive noise to the compute time of each worker.
Experimental setup. The analysis of all BERT models is performed on the same dataset as Devlin et al. (2018), which is concatenation of Wikipedia and BooksCorpus with 2.5B and 800M words respectively. The finetuning of the pretrained models is performed on SQuAD-v (Rajpurkar et al.. 2016). We verify the generality of DropCompute by additional evaluation of ResNet-50 model for image classification on ImageNet (Deng et al., 2009). The experiments depicted in section 5.2 and section 5.1 are executed on Habana Gaudi-1 I and Gaudi-2 accelerators, respectively, with high performance network (Habana 2022))
5.1 Generalization performance
The sole difference in the optimization when DropCompule is applied is that the batch size is not deterministic, but stochastic, explained in section 3.2 To complement theorem 4.1 we examine the generalization performance achieved with a stochastic batch size on two popular tasks.
Image classification. To evaluate the generality of stochastic batch size and DropCompute in particular, we evaluate the Top-1 accuracy of a ResNet-50 model on the Imagenet dataset using our method. Since it is not common to use gradient accumulation in large scale training of this task, we simulate the drops such that each worker randomly drops its local batch, so the total batch size is stochastic. This simulated environment enables without compromising accuracy. Figure 10 in appendix B.2.2 shows that up to 10% drop rate, which more than what DropCompute operates on, there is negligible deterioration in accuracy.
examine the extent of drop rate can
Large language model. Training L.MSs is resource intensive, typically using large batch sizes, which makes DropCompute appealing. We evaluate DropCompute method on this task by fully pretraining
8

---

(a) Varying drop rate, no compensation
(b) 10% drop rate, with compensation
% Drop rate
Fl score dev set
Compensation method
Fl score on dev set
0%
91.32 + 0.15
None
91.19 + 0.02
2.5-3%
91.34 + 0.04
11% extra steps
91.40 + 0.08
5.5-6%
91.44 = 0.02
11% increased batch size
91.38 + 0.08
10-11%
91.19 = 0.02
re-computation
91.19 + 0.11
Table 1: Maintaining the accuracy of BERT-Laage pretraining. Fine-tuning results SqUAD v1.1, where the Fl score obtained by the pretrained model. (a) The effect of different drop rates during pretraining on the final accuracy, without compensating for the dropped samples. (b) When 10% drop rate used during pretraining, with different methods of compensating for the dropped samples.
BERT-Large model several times, each with a different drop rate. We follow the optimization regime described You al. (2019) with batch size of 64K for phase-1 and 32K for phase-2 (more details are provided in appendix B.2). Each of the pretrained models is fine-tuned on the SQuAD task times with different initializations. Fine-tuning is performed without drops, as it is not large scale resource consuming task. Table La shows the average accuracy (#: standard deviation) obtained for each drop rate. As shown, DropCompute difference. Higher values measured up to 20% of dropped gradients provide acceleration with a small yet discernible hit on accuracy. We note that these results are for a fixed budget of steps. In the presence of compute variance, the effective speedup indicates that additional steps can be executed while still maintaining competitive runtime performance. This notion is demonstrated in section 5.2
drop rates of up to 10% have negligible accuracy
5.2 Runtime performance
The main purpose of our proposed method is to maintain runtime performance when compute variance present. We examine this by measuring the speedup of DropCompute over standard synchronous training in several settings. First, we measure the potential speedup for different drop rates and training settings by post analysis of synchronous training without drops. In addition, we introduce compute variance by training with additive noise, and measure actual speedups using DropCompute. The experiments in this section are performed on BERTL.5B. Details are provided in appendix [
Training with different number of workers and batches We evaluate the potential speedup of DropCompute several training settings with natural heterogeneity and drops. For each setting, we post analyze what would have been the speedup for different drop rates. As can be seen in Figure 4 DropCompute exhibits increasing benefits with a growing number of workers and compute requirements. However, there are diminishing returns in terms of speedup with more accumulations. This could possibly be explained by the amortization time of a large number of micro-batches
N=32
M=8
speedup
effective speedup
N-
M 16
N-128
M-32
N-192
M-64
3-
24
%
10
15
20
10
15
20
% drop
drop
Figure 4: DropCompute exhibits increasing benefit large scale. Effective speedup versus drop rate with (left) accumulations and varying workers, and (right) workers and varying number accumulations.
Simulated delay environment. Although DropCompute may have value when the workers' compute latency variance is low, its significance becomes crucial when the workers' compute latency exhibits high variability. To evaluate our method, we introduce a delay environment where random latency added to each micro-batch computation. This additive noise follows a bounded log-normal distribution. Detailed information and motivation regarding the additive noise are in appendix B. The experiments are executed with 12 gradient accumulations and a local batch size of 192. In the negative impact of compute variance scalability is demonstrated and mitigated
Figure I

---

using DropCompute. The results in Figure also correspond to section 4n and Equation where theoretical extrapolation follows the same trend line. When utilizing DropCompuute in this setup, achieving the same training loss as the baseline might requires additional training steps, however, it leads to a notable reduction in overall training time. Figure with 64 workers, where approximately 3% more steps is needed to reach the same loss, in 13% less time.
in training session
baseline
baseline
10
DropCompute
10-
Compute
Training
5-
5-
0
1000
2000
3000
4000
5000
10000
20000
30000 Time [sec]
40000
Steps
Figure 5: DropCompute improves training time for workers with compute variance. Train loss curve of BERTL.5B pretraining. in simulated delay environment. (left) Horizontal axis training steps, and (right) horizontal axis in training time.
Discussion
Summary. Efficient scalable systems are a key component to enable the continued development of deep learning models. To this day, state-of-the-art models rely on synchronous distributed optimization. The challenge to maintain synchronous training as an efficient solution grows larger with the quickly growing model sizes and data. Therefore, improving the robustness and scalability of distributed synchronous training is an important endeavor. This paper tackles the challenge of maintaining synchronous training scalable in the face of compute variance. We propose DropCompute to improve the robustness of synchronous training. Workers drop their remaining compute when they reach a compute threshold, determined by exchanging and analyzing the compute latency distribution. We find that for small percentage of dropped data, much larger percentage of time can be saved, depending on the compute latency distribution of the workers. In addition, we provide theoretical convergence guarantees and runtime predictions. We further discuss the motivation behind DropCompute and how it effectively solves the problem in appendix A
Limitations. While DropCompute is simple and straightforward. it deals with system efficiency, and as such, the user-level implementation provided is not optimal. Mainly, the provided implementation is limited by using many gradient accumulations and integrating compute timeout in between them. However, we believe that this not major concern since having multiple gradient accumulations is common practice in training LLM on large scale and is used in state-of-the-ar training configurations (Smith et al.) 2022] Nvidia 2023). In addition, DropCompute addresses variance that originates from the compute stage of the training iteration and does not solve the potential issue of network variance during the all-reduce stage.
Future directions. DropCompute is described and analyzed in this paper as a method built on top of synchronous training. However, this method can be integrated with other possibly asynchronous methods such as periodic synchronization. In appendix B.3], we implement DropCompute on top of Local-SGD (Lin al.) 2020) and show that DropCompute can also improve the robustness of Local- SGD to stragglers. A different extension for DropCompute is to apply it during the model backward calculation and save the partial gradients that were already calculated. This would generalize DropCompute for workloads that do not utilize gradient accumulations. However, it will require further study as it differs from the stochastic Batch-size setting where the entire data sample is either saved or dropped.
Acknowledgments
We thank Itay Hubara for technical advising and valuable comments on the manuscript. The research of DS was Funded by the European Union (ERC, A-B-C-Deep, 101039436). Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency (ERCEA). Neither the European Union nor the granting authority can be held responsible for them. DS also acknowledges the support of Schmidt Career Advancement Chair in AL.
10

---

References
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference Machine Learning, pp. 344 353. PMLR, 2019.
David H Bailey, Jonathan M Borwein, Marcos López de Prado, and Qiji Jim Zhu. Pseudomathematies and financial charlatanism: The effects of backtest over fitting on out-of-sample performance. Notices of the AMS, 61(5):458-771, 2014.
Tal Ben-Nun and Torsten Hoefler. Demystifying parallel and distributed deep learning: An in- depth concurrency analysis. ACM Comput. Surv. 52(4), aug 2019. ISSN 0360-0300. doi: 10.1145/3320060. https://dooi htt////i..rg//....1 (320000
Rawad Bitar, Mary Wootters, and Salim El Rouayheb. Stochastic gradient coding for straggler mitigation in distributed learning. IEEE Journal on Selected Areas in Information Theory, 1(1): 277-291, 2020.
Chia- Yu Chen, Jiamin Ni, Songtao Lu, Xiaodong Cui, Pin-Yu Chen, Xiao Sun, Naigang Wang. Swagath Venkataramani, Vijayalakshmi Viji Srinivasan, Wei Zhang, et al. Scalecom: Scalable sparsified gradient compression for communication-effiicee distributed training. Advances in Neural Information Processing Systems, 33: 18551-55113333 -13663, 2020.
Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting distributed synchronous sgd. arXiv preprint 1604.0090 2016.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.023111 2022.
Mostafa Dehghani, Basil Mustafa, Josip Djolonga, Jonathan Heek, Matthias Minderer, Mathilde Caron, Andreas Steiner, Joan Puigcerver, Robert Geirhos, Ibrahim Alabdulmohsin, al. Patch n'pack: Navit, vision transformer for any aspect ratio and resolution. arXiv preprint arXiv:2307.06304 2023.
Ofer Dekel, Ran Filah-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches Journal of Machine Learning Research, 13(1), 2012.
J. Deng, W. Dong, R. Socher, L.-J. Li. K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint a 10.0000 2018.
Jonas Geiping, Micah Goldblum, Phil Pope, Michael Moeller, and Tom Goldstein. Stochastic training is not necessary for generalization. In International Conference Learning Representations, 2022. URL / wwt./eoormmidd-ZESe.....
Niv Giladi, Mor Shpigel Nacson, Elad Hoffer, and Daniel Soudry. At stability's 's edge: How to adjust hyperparametters to preserve minima selection in asynchronous training of neural networks? arXiv 12340, 2019.
preprint arXiv: 1234,
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint 0al.aaah222000Haaaaaici//ioaarar
2017.
Habana. Habana gaudi training whitepaper, June 2020. URL http:///aaaaae/aabaaaaaaaa/oo/aa
Habana. Pre-training the bert 1.5b model with deepspeed. January 2023. URL httpt:tt////deelpee 10-555mmmmel---e (eith-deepspedd
habana, wi/blog/preleeeeeeeeoooooaooo wttpb//o//reeerrannnng-----ee-ee www.tttg-tteneeeeeeeeee
Elad Hazan et Introduction to online convex optimization. Foundations and Trends@ Optimiza-
tion, 2(3-4):157-325, 2016.

---

Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015.
Torsten Hoefler, Timo Schneider, and Andrew Lumsdaine. Characterizing the influence of system noise on large-scale applications by simulation. In SC" Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-11. IEEE, 2010.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. Advances in neural information processing systems, 30, 2017.
Sara Hooker. The hardware lottery. CoRR, abs/2009.06489) 2020. URL https:///axxiiii org/
abs/2009. 06489
Zhanhong Jiang, Aditya Balu, Chinmay Hegde, and Soumik Sarkar. Collaborative deep learning in fixed topology networks. Advances in Neural Information Processing Systems, 30, 2017.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffiee Wu, and Dario Amodei. Scaling laws for neural language models, 2020. URL htttt:tttt///aattete
org/ absaaas///0/ 2001 08361
Matej Kosec, Sheng Fu, and Mario Michael Krell. Packing: Towards 2x NLP BERT acceleration. CoRR, abs/2107.022 020077, 2021. URLptttps //rx/v/xxvv.v/// org/ abs 2107. 02027
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Kfir Levy. Online to offline conversions, universality and adaptive minibatch sizes. Advances in Neural Information Processing Systems, 30, 2017.
Shigang Li, Tal Ben-Nun, Giorgi Nadiradze, Salvatore Di Girolamo, Nikoli Dryden, Dan Alistarh, and Torsten Hoefler. Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging. IEEE Transactions on Parallel and Distributed Systems, 32(7):125--1739, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2020b.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Huangxing Lin, Weihong Zeng, Yihong Zhuang, Xinghao Ding, Yue Huang, and John Paisley. Learning rate dropout. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-11, 2022. doi: 10. 109//NNI 2.02..31111..
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. In International Conference on Learning Representations, 2020.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach, 2019. http:://////r www.aawwwww.r.aaaaaaaaaaaeeo awtpaabbs.../// 11692
Peter Mattson, Christine Cheng, Cody Coleman, Greg Diamos, Paulius Micikevicius, David A. Patterson, Hanlin Tang, Gu-Yeor Wei, Peter Bailis, Vietor Bittorf, David Brooks, Dehao Chen, Debojyoti Dutta, Udit Gupta, Kim M. Hazelwood, Andrew Hock, Xinyuan Huang, Bill Jia, Daniel Kang. David Kanter, Naveen Kumar, Jeffery Liao, Guokai Ma, Deepak Narayanan, Tayo Oguntebi, Gemnady Pekhimenko, Lillian Pentecost, Vijay Janapa Reddi, Taylor Robie, Tom St. John, Carole-Jean Wu, Lingjie Xu, Cliff Young, and Matei Zaharia. MIperf training benchmark. CoRR, abs/1910.01500, 2019. URL httpttttt///.i..oo.
01500
Ioannis Mitliagkas, Ce Zhang, Stefan Hadjis, and Christopher Ré. Asynchrony begets momentum, with an application to deep learning. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 997-1004. IEEE, 2016
12

---

Deepak Narayanan, Mohammad Shoeybi, Jared Casper. Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand. Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, Amar Phanishayee, and Matei Zaharia. Efficient large-scale language model training gpu clusters using megatron-Im. In Proceedings of the International Conference for High Performance Computing. Networking, Storage and Analysis, SC '21, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 44108441.... doi: 10.1144//453817744476222 URL https://doii org/
10. 1..1145/3458811. 047446888773376209
Arvind Neelakantan, Luke Vilnis, Quoe V. Le, llya Sutskever, Lukasz Kaiser, Karol Kurach, and James Martens. Adding gradient noise improves learning for very deep networks, 2015. URL.
httts://aaxiiv.oorg///////11111
Nvidia. mlcommons training results v3.0 gpt3.
http://hhhhoo.oooooooooooooo/aat results_va v3. wttpiaavv..ttteteee http:///a...aaatteoo////ee//t//n httpa///ww///a////////e/ttatttta
2023.
Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. Scaling neural machine translation. In Proceedings of the Third Conference on Machine Translation: Research Papers, pp. 1-9, Brussels, Belgium, October 2018. Association for Computational Linguistics. doi: 10118653/11W118-666
URL
Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Journal of Parallel and Distributed Computing. 69(2):117-124, 2009.
Fabrizio Petrini, Darren J Kerbyson, and Scott Pakin. The case of the missing supercomputer
performance: Achieving optimal performance on the 8.192 processors of asci q. In Proceedings of the 2003 ACM/IEE conference on Supercomputing, pp. 55, 2003.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1-66 2020a. URL
http://jmlr. www.o//g/gp..eeeeo.. wwwpees//11///// 20-074 074.004..h hhmml
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learming Research, 21 21(5555485-551, 2020b.
Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero: Memory optimizations toward training trillion parameter models. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-16. IEEE, 2020.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference Empirical Methods in Natural Language Processing, pp. 2383-2392, Austin, Texas, November 2016. Association for Computational Linguistics.
Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. Deepspeed: System optimiza- tions enable training deep learning models with over 100 billion parameters. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 3505535506 2020.
Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, and Roman Dementiev. Sequential and Parallel Algorithms and Data Structures. Springer, 2019.
Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. Bloom: A 176b- parameter open-access multilingual language model. arXiv preprint arXiv:2211.05100, 2022.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and application to data-paralles distributed training of speech dnns. In Interspeech 2014, September 2014.
13

---

Shaden Smith, Mostofa Patwary, Brandon Norick, Patrick LeGresley, Samyam Rajbhandari, Jared Casper, Zhun Liu, Shrimai Prabhumoye, George Zerveas, Vijay Korthikanti. et Using deepspeed and megatron to train megatron-tune tuurnng nig 530b, a large-scale generative language model. arXiv preprint arXiv:2201. /9990, 2022.
Pawel Sobkowicz, Mike Thelwall, Kevan Buckley, Georgios Paltoglou, and Antoni Sobkowicz. Lognormal distributions of user post lengths in internet discussions- consequence of the weber- fechner law? EPJ Data Science, 2(1):1-20, 2013.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
Mingxing Tan and Quoe Le. Efficientmetv2: Smaller models and faster training. In International
conference on machine learning, pp. 10096- 10106. PMLR, 2021.
Hanlin Tang, Shaoduo Gan, Ammar Ahmad Awan, Samyam Rajbhandari, Conglong Li, Xiangru Lian, Ji Liu, Ce Zhang, and Yuxiong He. 1-bit adam: Communication efficient large-scale training with adam's 's convergence speed. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 10118-10129, PMLR, 18-24 Jul 2021.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 2023.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient
compression for distributed optimization. Advances in Neural Information Processing Systems, 32, 2019.
von Luxburg. S Bengio, HM Wallach, Fergus, SVN Vishwanathan, and Garnett. https://github com/biiddresaarthbbiaaalllled
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of local-update sgd algorithms. Journal of Machine Learning Research, 22, 2021.
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication--fficceent distributed sgd with slow momentum. In International Conference on Learning Representations, 2020.
Hang Xu, Kelly Kostopoulou, Aritra Dutta, Xin Li, Alexandros Ntoulas, and Panos Kalnis. Deepre- duce: sparse- tensor communication framework for federated deep learning. Advances Neural Information Processing Systems, 34:21150-211 216022211,,,-11 2021.
Donglin Yang, Wei Rang, and Dazhao Cheng. Mitigating stragglers in the decentralized training on heterogeneous clusters. In Proceedings of the 21st International Middleware Conference, pp. 386-399, 2020.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint Xiv: httv:/708 03888, 2017.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv: 2019.
Sixin Zhang, Anna E Choromanska, and Yann LeCun. Deep learning with elastic averaging sgd. Advances in neural information processing systems, 28, 2015.
Shuai Zheng, Haibin Lin, Sheng Zha, and Mu Li. Accelerated large batch optimization of bert pretraining in 54 minutes, 2020.
14


Reviews:
[{"review_id": "XQr7a9LzJl", "reviewer": "Reviewer_Zc33", "summary": "This paper proposes a strategy to improve the scalability of DNN training for highly distributed workloads by allowing nodes that are lagging behind, in terms of processing time, to stop computing updates and share partial results with the other nodes in the cluster. The proposed method, DropCompute, allows the training strategy to remain synchronous while supporting scalability. The primary method to scale train while maintaining reasonable performance typically relies on asynchronous processing and/or sharing of updates between nodes in the training cluster to avoid the performance impact of straggler nodes. By maintaining the synchronous training guarantees DropCompute avoids the less desirable divergent model convergence behavior that may exist with an asynchronous approach. The authors propose a simple strategy to implement DropCompute using modern DNN software and provide theoretical and empirical results to support the claim that dynamically dropping straggler computation does not result in a negative impact on the training accuracy of the final model while simultaneously enabling faster and more reliable computation times as the number of nodes in the cluster are increased. Evaluation results consisting of runtime performance and final model training accuracy are provided to support the authors' claims regarding the effectiveness of DropCompute on real-world models.", "questions": "No questions at this time.", "limitations": "All limitations and societal impacts were addressed by the authors.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The authors provide a clear description and mathematical model to understand the expected behavior of dropping straggler computations. The simplicity of the method lends itself to a simple description and implementation that is clear and easy to follow.\n- With the increased scale of training the influence of computational variability will continue to grow in importance. This fact leads to the natural importance of methods that are robust to possible large variations that may exist between various nodes in a cluster.\n- Asynchronous training has been the go-to strategy for a number of years but the adverse impact of this strategy has been downplayed to achieve more distributed training at higher performance. DropCompute is a refreshing novel take on the distributed computation problem and is amenable to simple implementation on top of existing DNN software, which is reminiscent of dropout or dropconnect training.\n- The theoretical analysis provides an interesting analysis of the expected behavior of dropcomute training and the overall impact on the final accuracy of the model.\n- Evaluation data using a simulated delay environment support the performance claims presented by the authors.\n", "weaknesses": "- Though DropCompute is interesting the community of researchers with access to training environments large enough and experience sufficient computational variability to truly benefit from the approach could be small.\n- How often do researchers with access to large distributed training systems experience high compute variability?\n- The implementation would benefit from a lower-level implementation to increase overall efficiency. This was noted by the authors. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Weakness 1 response\nWe appreciate the reviewer's concern regarding the limited audience that may directly benefit from DropCompute. However, the growing investment in large-scale training environments and the potential impact on efficiency justifies our focus on optimizing such settings. Also, depending on the task and system properties, medium-scale systems (16-32 workers) could also profit from DropCompute. All major cloud providers offer access to such set-ups, and many sources such as [*Falcon, W., & The PyTorch Lightning team. (2019). PyTorch Lightning (Version 1.4)], [Sylvain Gugger, B.. (2022). Accelerate: Training and inference at scale made simple, efficient and adaptable.*],and  [*NVidia Deep Learning Examples repository*] support multi-node training regimes, which indicates these are very popular. \n\n### Weakness 2 response\nStragglers/Compute variance can result from various reasons, and we even experienced it in some of our experiments (see **GQ1: Is compute variance really an issue?**). Researchers in particular are exposed to such cases, due to suboptimality of large research clusters. When benchmarking large scale systems (such as MLPerf), both hardware and software should be optimized. Changing the implementation, as researchers normally do, will likely destabilize the system and induce compute variance. \nCompute variance poses a significant challenge in achieving linear scaling (as shown in figure 1), and the problem increases with the scale of the system (As written in **GQ1: Is compute variance really an issue?**).\n\n### Weakness 3 response\nWe thank the reviewer for highlighting this point. This point strengthens our approach as a lower level implementation would increase the efficiency of our solution.\nA low-level implementation highly depends on framework and HW details, and we hope that with the publication of this paper, engineers will provide lower level more efficient implementation of DropCompute for their respective systems.\n"}, {"review_id": "EAODz1mebz", "reviewer": "Reviewer_5jtg", "summary": "This paper introduces DropCompute, a method to mitigate load imbalance across workers when doing distributed training. It splits mini-batches into micro-batches, and uses a dynamically-calculated time budget, which, when exceeded, results in the remaining micro-batches being dropped and communication to aggregate gradients beginning. A convergence analysis is provided, and experiments are conducted on ResNet-50 and BERT.", "questions": "1. Is load imbalance an issue in practice? Can you name concrete situations, which occur in practice, where it is an issue?\n2. Can you add an experiment showing DropCompute's benefit without artificially-induced delays?\n3. Please add experimental comparisons with asynchronous/wait-avoiding systems (see above).\n4. Why drop samples? It seems wasteful --- why not just use them in the next iteration? Is this due to a desire to follow synchronous training?\n5. It might be worth clarifying that DropCompute cannot address all causes of stragglers. In particular, it seems like it does nothing for delays caused by network issues (e.g., contention, dropped packets, routing issues, etc.). This is not a criticism so much as a limitation that should be acknowledged.\n", "limitations": "Limitations are discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Load imbalance is an important emerging topic and somewhat understudied in distributed deep learning.\n2. DropCompute is a simple but appealing idea; integrating with micro-batching is a nice idea.\n3. The paper includes theoretical analyses and justifications for their choices.\n4. The experiments cover large, representative networks (ResNet-50, BERT) in different tasks/domains.", "weaknesses": "1. The motivation and significance of the paper is unclear to me: I am not sure load imbalance is an issue in practice for training. The paper gives the example of varying sentence lengths, but transformers typically concatenate sentences and pad to fixed lengths during training. Another example given is varying image sizes, but I do not think it is typical to train that way. The paper would be much stronger if there were concrete examples of widely-used and/or important use cases with load imbalance during training. This could be an issue in reinforcement learning, but that is a very different setting. Networks with conditional computation may also exhibit load imbalance, but I do not know any widely used examples.\n2. A related issue to this shows up in the experimental evaluation: Delays are manually induced through simulation, rather than actual load imbalance. While this is useful for ablation studies and accuracy analysis, it reinforces my prior point.\n3. There are no comparisons with other techniques to handle stragglers, such as asynchronous methods. For example, Li et al., \"Breaking (Global) Barriers in Parallel Stochastic Optimization with Wait-Avoiding Group Averaging\", IEEE TPDS, 2021 (see also the references therein).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Weakness 1 response\nWe thank the reviewer for the suggestion to add more concrete use case examples. Heterogeneity in computation causes issues when training in parallel schemes, and so many such workloads rely on “tricks” (such as packing of sentences and padding) in order to reduce computational variance, at the expense of performing redundant work. These approaches not only use additional resources, but also require tedious offline engineering work. Our approach doesn’t require any modification of the training task, and works “out of the box”. In addition, “waiting for the slowest worker” can also be seen as a type of “padding” and our method reduces the need for such wait. There are several examples where input shape might vary during training in vision as well as other domains (e.g., [*Tan et al. “EfficientNetV2: Smaller Models and Faster Training”, Dehghani et al.*], [*“Patch n’ Pack: NaViT, a Vision Transformer for any Aspect Ratio and Resolution”*], and [*Raffel et al. “Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer”*]). Other reasons for compute variance are listed in (**GQ1: Is compute variance really an issue?**). We will add all those concrete examples to the paper.\n\n### Weakness 2 response\nAs written in (**GQ2: How effective is DropCompute in practice?**), we also conducted experiments on large clusters of up to 192 workers without simulative delays (section 5.2 and figure 4 and attached PDF), that prove the effectiveness of DropCompute in both gaining performance and making the system robust to stochastic non-performant outliers. \n\n### Weakness 3 response\nWe thank the reviewer for the suggested paper ― we will add it to the ‘related-work’ section.\nWe focused on improving synchronous methods on a large scale, since staleness (even when bounded) is known to cause some accuracy loss of the model ― as is shown in the mentioned paper, figure 5 (-0.5% top-1 accuracy). This is also described in our paper’s “Related work ― Asynchronous optimization” paragraph. In this sense, according to table 1 in the mentioned paper, our method falls into the “No Staleness - Gradient Averaging” category, while WAGMA-SGD is a “Bounded Staleness - Model Averaging” variant. Nonetheless, in appendix A.3, we have made a comparison with Local-SGD, which is similar to WAGMA-SGD (both model-averaging with bounded staleness). Moreover, we have shown that these periodic synchronization methods are often orthogonal to DropCompute and can be integrated together while capitalizing on both (as is done in appendix A.3).\n\n### Question 1 response\nYes. See **GQ1: Is compute variance really an issue?**\n\n### Question 2 response\nAs written in (**GQ2: How effective is DropCompute in practice?**), we performed such an experiment in section 5.2, figure 4. In addition, we performed another experiment on a sub-optimal system which recovered ~18% performance.\n\n### Question 3 response\n Please refer to appendix section A.3.\n\n### Question 4 response\nThis is a great idea which we tried. However, we found that using the dropped gradients in the next iteration causes accuracy degradation similar to what is seen in asynchronous training. If the intention is to recompute the data samples in the next iterations this is also possible, as in our answer to reviewer **btsj**, in regard to his weakness (2).\n\n### Question 5 response\nOur work focuses on solving compute variance issues, as opposed to other methods which treat communication problems, some of which are described in our “related work” section. We believe that handling straggling network connections using our approach is possible, but requires further research and HW support. We thank the reviewer, and will add ‘stragglers due to network issues’ to our limitations and future directions section."}, {"review_id": "zKEj4JOIg0", "reviewer": "Reviewer_btsj", "summary": "The authors proposed a method to drop computation (DropCompute) of **microbatches** of a **minibatch** on decentralized workers if their execution time exceeds a certain threshhold. The author provided theoretical convergence proof of this method as well as theoretical/experimental study of the performance gain or speed up of this method.", "questions": "* in step 6 Algorithm 1 the authors mentioned step 7 and step 10 are in parallel, does it mean step 9 could stop in the middle if time out in step 10 or step 8-9 are still atomic? The description seems to suggest it is the former one (otherwise step 10 can be just a break condition in the forloop), but this results in gradients with i or i - 1 steps accumulation and breaks the theoretical analysis if my understand is correct.\n\n* is it possible to reuse dropped data/samples, e.g, there could be a synchronization of dropped sample indices of the dataloader of each replica so that next batch can be sampled with previously dropped data? Alternatively, can you cache the dropped data/samples locally on each replica, and use them in next batch. Both seem to be simple change to dataloaders.", "limitations": "The authors didn't talk about their limitations. But from my understand, the main limitations include the first 3 points mentioned in Weaknesses:\n* large number of microbatches assumption\n* training data dropping\n* the problem solved is not significiant for LLM trainings which mostly happen in datacenter (compared to Federated Learning)\n\nAdditionally, the method is only applicable to traditional data parallel training, for modern distributed system that adopts FSDP/DeepSpeed-Zero and Tensor/Pipeline Parallellsim, the proposed method can't help with their parallel compute variance (because it depends on gradient accumulation, again, multiple microbatches in a minibatch).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The proposed method is quite simple and straightforward in implementation, especially for decentralized SPMD distributed system.\n\n* The theoretical study of the convergence and speed up of this method is thorough and clear\n\n* The ablation study of the experimental section is clear", "weaknesses": "* If my understand is correct, the theoretical analysis (line 186) and efficacy (Figure 4 right) of the method relies on large enough minibatch size per replica, so that number of microbatches M >> 1. This probably worked fine for BERT training (line 241), however for modern LLM pretrainings, e.g., GPT3 XL (similar size as the model studied in this work), the global batchsize is 1M tokens/(2K tokens/sample) = 500 samples. Distributed on 200 replicas, minibatch / replica is only 2-3 samples, which fundamentally breaks the assumption. The global batchsize can be even smaller for fine-tuning. Addtionally, the evaluation on Image task (line 229) basically has only 1 microbath per minibatch, and does not serve a good experimental study for DropCompute (which is more like Federated Learning).\n\n* The proposed method drops data/samples per iteration. This might be fine if the data is trained multiple epochs like BERT scale, however for modern LLM, especially pretraining, the data is usually trained one epoch so if one micrabatch is dropped, it might be dropped from training forever.\n\n* The performance gain is marginal, e.g, theoretically at most 20% (Figure 3) by choosing the best threshold $\\tau$ or droprate, and in practice 5% (Figure 4) if maintaining final model quality. This is likely due to the compute variance of replicas follow a normal distribution (with small std) and the system w/o DropCompute is not significantly slowed down in this case. Things can be more interesting if the variance follows an extreme distribution, e.g., normal + delta function, but that's not likely true for datacenter clusters.\n\n* The author said no additional hyper-parameters are introduced (line 55), however proper droprate or threshold time $\\tau$ is still a new hyperparameter", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Weakness 1 response\nIt is true that some learning tasks do not use many microbatches, however, we argue that for LLMs the number of microbatches can be significantly larger. For example, the recent leading performance benchmark for LLMs, GPT-3 175B training with 3584 workers (including pipeline, tensor and data parallelism), utilizes 24 micro-batches [*MLCommons MLPerf v3.0 training benchmark*]. For reference, as can be seen in our experiments (section 5.2, figure 4a), it is sufficient to use 16 microbatches.\n\nFor ResNet50 experiments, the evaluation indeed uses a single microbatch, since we followed a realistic training regime. The purpose of this experiment is to diversify the learning domains our evaluations are based on, at the expense of simulation of the drops. It is possible to implement DropCompute in layers granularity (with backward hooks for example) such that workers can stop during backward pass - when reaching a timeout, stop the backprop and allreduce the gradients accumulated so far. However, this probably requires a lower level implementation to provide real value in terms of runtime performance. \n\nNonetheless, we thank the reviewer for raising this point, and we will add it to the limitations section.\n\n\n### Weakness 2 response\nOur evaluations consider the need to compensate for the dropped data samples with more steps. This is integrated in the definition of the \"effective speedup\" metric. Regarding missing samples (in case of training a single epoch), it is possible to reuse them, similar to the suggestion in your second question - saving the indices of the dropped samples and adding them back to the data loader. \n\n### Weakness 3 response\nAs written in (**GQ2: How effective is DropCompute in practice?**), the theoretical performance gain can be greater than 20% since it depends on the noise statistics (see appendix section B.3), scale, and the level of system optimizations. Moreover, even a 5-20% improvement can be significant in large-scale implementations. \n\n### Weakness 4 response\nWe note that the drop rate $\\tau$ is automatically determined by the method itself for maximum effective speedup, as detailed in Section 4.4, \"Choosing the Threshold\". By stating that “we do not introduce additional hyper-parameters”, we mean that no additional hyper parameter tuning is required which is the main drawback of using many hyper-parameters. \n\n### Question 1 response\nIn our implementation, step 8 can be interrupted (either before forward pass or before backward pass) while step 9 is atomic - i.e., either we accumulate the gradients from the micro-batch ‘m’, or drop it entirely. This is inline with our definition of $\\\\tilde{M}(\\\\tau)$ where a sample is counted only if $T_n^{(m)} < \\\\tau$ and therefore, our theoretical analysis remains valid.  We thank the reviewer for raising this question and will clarify it in the paper.\nOne might propose combining steps 8+9 and having the option of breaking computation during the backward pass, after calculating a portion of the micro-batch gradients. This approach is possible, and we tried it during the early stages of our experiments. According to our empirical experiments this does not harm convergence. However, for ease of use and analysis of our method, we decided to drop this idea. We thank the reviewer in seeing value in such optimizations and will include this approach in our “future directions” section.\n\n\n### Question 2 response\nIn workloads where a single epoch is trained this idea could be valuable. We thank the reviewer for this suggestion, and we will integrate it into the paper.\n\n### Limitations response\n- training data dropping - can be solved easily using your suggestion, of saving the indices of dropped examples\n\n- problem not significant in datacenter - we respectfully disagree - (see **GQ1: Is compute variance really an issue?**).\n\n- Tensor/Pipeline Parallelism - simple DropCompute can always be used at the data-parallel level (dropping micro-batches of an entire pipeline group). For example, training GPT3 at large scale (as done by [*NVidia in MLCommons MLPerf v3.0 training benchmark*]) utilizes a model-parallel level of 32 workers, and 112 worker data-parallel (overall 3584 workers). DropCompute could be used here by dropping a straggling 32-worker model-parallel unit. Also, it is plausible to assume that the communication required in the model-parallel unit would increase the compute variance and make DropCompute even more effective. In our terms, this case has N=112 droppable workers.\nWe thank the reviewer for raising this point and we will address this as part of our “limitations” and “future work” section.\n\n"}, {"review_id": "8QylaLIhy1", "reviewer": "Reviewer_PA5g", "summary": "This paper considers a typical scenario in which workers are straggling due to variability in compute time, in which the authors find an analytical relation between compute time properties and scalability limitations. They propose a decentralized method to reduce the variation among workers and   improve the robustness of synchronous training.", "questions": "What is the computation cost of Algorithm 2? Does it consume much time, and is the consuming time recorded in  Figure 5?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper studies the distribution of iteration time and presents some insights into understanding distributed optimization.\n\n2. Based on the analysis of the iteration time for the worker, the authors propose an algorithm that drops some data in computing local gradients to avoid waiting.\n\n3. They present the analysis of distributed SGD with stochastic batch size, which is novel and interesting.\n\n4. Numerical results are presented to verify the assumptions and demonstrate that the robustness of the convergence.", "weaknesses": "1. The convergence is proved under many extra assumptions than that of distributed SGD and cannot explain why the new algorithm can be better.\n\n2. According to Figure 5, the proposed algorithm seems only a little better than the baseline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Weakness 1 response\nWe prove convergence under the standard assumptions that are used in the analysis of distributed SGD. To be concrete, we make 2 assumptions: Smoothness, and bounded variance, both of them are standard in the analysis of distributed/parallel SGD, see e.g. the classical paper of [*Dekel et al, 201*2]\n \nWe prove results for both the non-convex case (in Theorem 4.1) and Convex case (in Theorem C.1)\n\nLastly, to remove any doubt, the unbiasedness assumption that we mention stems directly from the property of stochastic gradients.\n\n\n### Weakness 2 response\nWe respectfully disagree, see (**GQ2: How effective is DropCompute in practice?**).\n\n### Question 1 response\nThe computation cost of algorithm 2 is $\\\\theta(N\\\\cdot I\\\\cdot M)$ where $N$ is the number of workers, $I$ is the number of recorded iterations and $M$ is the number of accumulations per iteration. Overall, this cost is negligible, compared to a full training session, because it happens only once in a training session. "}]

Author rebuttal:
**We thank the reviewers for the insightful and constructive feedback. The evaluations provided in the paper will be improved along with the required modifications and clarifications. We will be happy for further questions and feedback.**

We thank reviewer Zc33's recognition of the novelty and importance of our work, where the reviewer described DropCompute as *“a refreshing novel take on the distributed computation problem”*. We are glad that the reviewers acknowledged the simplicity and straight-forwardness of our approach, as reviewer 5jtg wrote: *“DropCompute is a simple but appealing idea”*. We appreciate the positivity of the reviewers around our theoretical analysis which was described as *“thorough and clear”* (reviewer btsj).


## General Q&A:

**GQ1: Is compute variance really an issue?**

**A:** Yes. Compute variance can be the result of faulty hardware, clock throttling, host preemption/overhead, inefficient load balancing (for example, when training on dynamic sentence/image sizes), connectivity issues (in model parallel settings) and more. 

Generally, some of these issues can be handled by non-trivial engineering work:
Faulty hardware can be tested regularly and replaced, host overhead can be avoided by latency hiding and optimization of user script, and inefficient load balancing can be handled per workload by various tricks such as sample padding and packing. However, each of these issues in itself is a single point of failure ― which, if triggered, will cause a substantial slowdown in large-scale systems. 

Slowdown examples can be seen in some of our real experiments (i.e. without noise injection), which are attached in the PDF. The histograms there show real measurements in a sub-optimal system. We can clearly see a large variance in compute latency between iterations and workers. These graphs were not included in our original paper since they do not represent the final state of our system (which was regularly checked and optimized). However, as our goal is to improve robustness (i.e. performance for outlier cases), these cases are still relevant. Moreover, after the compute variance was reduced by HW and SW optimizations, we were still left with some compute variance (see Figure 2 in paper).

Although the issue of variance in sub-optimal systems is discussed intensively by system engineers, there is little reference to the matter in ML research papers. A prominent example can be seen in *Chen et. al, “Revisiting Distributed Synchronous SGD”, ICLR Workshop Track 2016*, where the performance is improved when dropping stragglers. 

These examples lead us to the conclusion that, in practice, workers do not finish computation at the same time, and this can have a significant impact on the training speed. Moreover, the effect of stragglers and compute variance on the training speed is expected to get worse as the distributed scale increases. This is due to the maximal worker distribution relation stated in equation 3. For example, when modeling the additive latency as normally distributed, the average maximal worker latency increases $\\mathbb{E}[T]$ with the amount of workers $N$ as $\\mathbb{E}[T]\\sim \\text{log} N$ (the asymptotic form of eq. 4). 




**GQ2: How effective is DropCompute in practice?**

**A:** The slowdown which is a result of compute variance can be avoided effortlessly using DropCompute. In a sub-optimal system with stragglers (*in attached PDF, figure (A)*) we recovered ~18% of performance. Given different systems and noise distribution, the contribution of DropCompute can be even larger (appendix section B.3). In addition, our theoretical analysis shows a greater speedup as the number of workers $N$ increases: $S_\\text{eff}\\rightarrow_{(N\\rightarrow \infty)} \infty $ (asymptotic combination of equations 4 and 6). On our own system, after the compute variance was reduced by HW and SW optimizations, we still gained a performance boost of 5% on 196 workers (section 5.2, figure 4), and the speedup is increased as the scale increases. These examples show that DropCompute makes large-scale training more robust, and “recovers” the lost performance due to any stochastic performance outlier. 

Last, but not least, even a small gain to large-scale training performance can be substantial - for example, if we assume **10\\$-32\\$/hour/8xA100** (according to AWS pricing), then saving 5% of the training time for the 70B model in *Touvron et al., “Llama 2: Open Foundation and Fine-Tuned Chat Models”, 2023*, would have saved **107,50\\$-344,064\\$**, and **67,686\\$-216,598\\$** for *“BLOOM: A 176B-Parameter Open-Access Multilingual Language Model”* for the 176B model.

Meta-review: The paper proposes a method for distributed synchronous training that reduces run-time variance among workers to make distributed training more reliable. The reviewers came to a consensus in favor of accepting this paper, and I agree with this consensus. I suggest that for the camera ready, the authors include some more content describing the practical effect of DropCompute on saving resources and cost in real systems.
Decision: Accept (poster)