DropCompute: simple and more robust distributed synchronous training via compute variance reduction

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.

Paper

References (66)

Scroll for more · 38 remaining

Similar papers

Peer review

Reviewer PA5g6/10 · confidence 2/52023-06-23

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.

Strengths

1. This paper studies the distribution of iteration time and presents some insights into understanding distributed optimization. 2. 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. 3. They present the analysis of distributed SGD with stochastic batch size, which is novel and interesting. 4. 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. 2. According to Figure 5, the proposed algorithm seems only a little better than the baseline.

Questions

What is the computation cost of Algorithm 2? Does it consume much time, and is the consuming time recorded in Figure 5?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

Yes

Reviewer btsj6/10 · confidence 4/52023-06-26

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.

Strengths

* The proposed method is quite simple and straightforward in implementation, especially for decentralized SPMD distributed system. * The theoretical study of the convergence and speed up of this method is thorough and clear * 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). * 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. * 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. * The author said no additional hyper-parameters are introduced (line 55), however proper droprate or threshold time $\tau$ is still a new hyperparameter

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. * 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors didn't talk about their limitations. But from my understand, the main limitations include the first 3 points mentioned in Weaknesses: * large number of microbatches assumption * training data dropping * the problem solved is not significiant for LLM trainings which mostly happen in datacenter (compared to Federated Learning) Additionally, 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).

Reviewer 5jtg6/10 · confidence 4/52023-07-07

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.

Strengths

1. Load imbalance is an important emerging topic and somewhat understudied in distributed deep learning. 2. DropCompute is a simple but appealing idea; integrating with micro-batching is a nice idea. 3. The paper includes theoretical analyses and justifications for their choices. 4. 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. 2. 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. 3. 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).

Questions

1. Is load imbalance an issue in practice? Can you name concrete situations, which occur in practice, where it is an issue? 2. Can you add an experiment showing DropCompute's benefit without artificially-induced delays? 3. Please add experimental comparisons with asynchronous/wait-avoiding systems (see above). 4. 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? 5. 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Limitations are discussed.

Reviewer Zc336/10 · confidence 3/52023-07-07

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.

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. - 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. - 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. - 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. - Evaluation data using a simulated delay environment support the performance claims presented by the authors.

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. - How often do researchers with access to large distributed training systems experience high compute variability? - The implementation would benefit from a lower-level implementation to increase overall efficiency. This was noted by the authors.

Questions

No questions at this time.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

All limitations and societal impacts were addressed by the authors.

Reviewer 5jtg2023-08-13

Response

Thank you for taking the time to thoroughly respond to my (& others) questions and comments. This has addressed some of my concerns. I am still not fully convinced that load imbalance is a major issue in practice, but I can buy that it shows up in some situations, and definitely agree that even small performance improvements can be significant for large models (although I rather suspect that large training runs are typically executed on quiet, well-maintained systems and running such training requires significant engineering effort). Regarding Q4, on dropping samples: I did indeed mean to recompute the samples in some future iteration. I agree that it does not seem like it would be too hard to implement. (But it may have some interesting implications for convergence, as the order in which samples are evaluated becomes correlated with compute time; e.g., very long samples may be penalized.) One suggestion which occurs to me, regarding related work and compute variance, is to discuss the relation of this to classic work in systems and high-performance computing on system noise. (In my experience, on modern systems, the lessons in these works have already been applied, but it is worth at least discussing them.) For example: - Petrini, Kerbyson, & Pakin, "The Case of the Missing Supercomputer Performance: Achieving Optimal Performance on the 8,192 Processors of ASCI Q", Supercomputing 2003 - Hoefler, Schneider, & Lumsdaine, "Characterizing the Influence of System Noise on Large-Scale Applications by Simulation", Supercomputing 2010

Authorsrebuttal2023-08-16

We thank the reviewer for the positive comments on the significance of DropCompute, and for the additional feedback, including the mentioned papers on discussing system noise in HPC.

Reviewer btsj2023-08-14

Thanks for the detailed explanations and the addtitional data on compute variance. I totally agree that a (**free and robust**) 5% speedup is siginificant in LLM trainings, however my concern is DropCompute is less applicable to LLM trainings due to: 1. The batch-size can indeed be larger, at the cost of developing new ML algorithms (like Optimizers) and collecting better datasets, and can hardly be applicable to fine-tuning. The 5-20% speedup is not **robust** to one of the most immportant hyper-parameters: batch-size, thus comes with a system/acc tradeoff. Additionally, LLMs are using much longer sentence size in pretraining (from 2K tokens to 4K/8K), which also limits mini batch size per replica. 2. Larger drop rate (>10%) comes at the loss of model accuracy (Table 1), which means it is not a **free**. ML researchers have to pick a drop rate carefully so that it improves throughputs while maintaining final model acc. That's why I brought up that this drop rate is an additional hyperarameter (as dicussed in Weakness 4 response, it can be auto inferred to maximize speed up, but maximized speed up does not guarantee final model acc). Since LLM has tons of downstream tasks depend on it, 5-10% speed up is not worth any loss in acc. Nonetheless, I do believe DropCompute shows clear values in training workloads with 1. large compute variance, 2. enough batch-size and 3. less downstream task dependencies due to its simplicity, just that its value in LLM training is not convincing enough to me. I'm not sure if the authors have time to experiment Question 2 response and see if it can recovers some acc loss at higher drop-rate, if so I am open to a borderline accept (5).

Authorsrebuttal2023-08-16

We thank the reviewer for the positive comments on the value of DropCompute, and for the additional feedback. Regarding the remaining concerns: **1a. Is it a limitation that DropCompute requires large batch sizes?** Large batch size is not the main constraint, but the number of micro-batches used (as the reviewer pointed out in the previous comment). We focused on applying DropCompute on workloads, such as LLMs pretraining, that already require large batch sizes, and enough micro-batches (>16, as we explained before). In addition, we believe that the trend in training larger and larger LLMs is leading towards an increased number of micro batches ― a trend that can only further help DropCompute. For example, we mentioned GPT3 which had 24 microbatches (in our rebuttal), and we think this number typically ‌increases in even larger models, such as the 160 microbatches in *[Smith et al. “Using DeepSpeed and Megatron to Train Megatron-Turing NLG 530B, A Large-Scale Generative Language Model”]*; note the authors there also explicitly mention gradient accumulation as a desired method in LLM training. Therefore, we do not believe this is a serious limitation. **1b. Are longer sentence sizes an issue for DropCompute?** No. Like the reviewer mentioned, LLMs are using longer sentence sizes in pretraining. However, we are not sure why this is a problem. In fact, this seems to benefit DropCopmute: longer sentence sizes lead to smaller micro-batches (because of memory constraints) which lead to more micro-batches per worker. **2. Does the DropCompute speedup we showed come for 'free’ (i.e. without accuracy degradation)?** Yes. There might be some misunderstanding regarding how we define the speedup versus the results in Table 1, so we would like to clarify it. Effective speedup (as defined in equation (6)) already considers the dropped samples. For example, if the drop rate is 10% and the effective speedup is 10%, it means that we have gone through ~11% more samples (while dropping 10% of all samples), in 10% less time. To compensate for the dropped samples and competitive runtime performance, we suggested doing more training steps (e.g., lines 275-277: “...achieving the same training loss as the baseline might requires additional training steps, however, it leads to a notable reduction in overall training time.”). We found this to be a hassle-free method in our experiments, as we illustrated in Figure 5. There, we trained with DropCompute (with 6.7% drop rate) until reaching the baseline training loss (instead of training a fixed budget of steps). This required 3% more steps, but took 13% less time. In Table 1, however, we report the model accuracy without adding more training steps (which leads to a further increased speedup, higher than the “effective speedup”). Therefore, we expected Table 1 to have accuracy losses. The point of Table 1 (and Figure 9 in the appendix) was to show that the actual speedup can be higher than the effective speedup, since we do not even have to add more steps, unless drop rate > 10% (we note we did not observe experiments with drop rate > 7%, even in our most extreme cases, presented in the PDF attached to the global response part of the rebuttal). If we were to add more iterations to the training sessions used to produce in Table 1 (to compensate for the drop rate), we would have reached a similar accuracy as the baseline (as we meant to say on lines 251-252, we apologize if this was not very clear). We hope that this answers any remaining concerns. Please let us know if there are any other concerns.

Reviewer btsj2023-08-16

Thank you again for your response. > However, we are not sure why this is a problem. In LLM training, the batch-size is actually num-tokens rather than num-sentences, when num-tokens is fixed, the longer the sentence, the smaller the num of sentences per replica. > Effective speedup ... in 10% less time. Thanks for clarifying, I might miss this detail in the context. Given that I am willing to increase the score to borderline 4. If you could conduct experiments with a compensating dataloader instead of dropping samples + more training steps, as I mentioned earlier I am open to a weak accept 6.

Authorsrebuttal2023-08-21

We thank the reviewer for the additional feedback. As requested, we conducted additional experiments with the settings described in Table 1, for BERT-Large pretraining. We focused on the most challenging case in Table 1, of 10% droprate. There, we had some degradation in accuracy (F1 score): from 91.32 +- 0.15 in the baseline without DropCompute, to 91.13 +- 0.02 with 10% droprate and without compensating at all for the dropped samples. We have tested 3 methods of compensating for the dropped samples: 1. Additional steps: training for extra ~11% steps (to maintain, on average, the total number of samples seen during training without DropCompute). This resulted in the baseline accuracy (91.40 +- 0.08). This validates our suggested approach of taking extra steps into account. 2. Increased batch size: training with an increased global batch size of ~11% (before dropping), to maintain, on average, the same batch size as the baseline (after dropping). This approach also resulted in the baseline performance (91.38 +- 0.08). 3. Saving the dropped samples indices, and reusing them before starting a new epoch. As suggested by the reviewer, this method uses the dropped samples explicitly. We have made the necessary code alterations to the data loader, but haven't finished yet to validate and complete the pretraining experiment. This experiment will not be completed by the end of the discussion period, but will be included in the final submission along with the first two results. We note that the first two methods do not reuse the dropped samples explicitly, yet the accuracy does not degrade. Therefore, there is no remaining gap to close by using the third approach (reusing he dropped samples), but it may accelerate training further (perhaps by combining with the other approaches). It also may be beneficial to accuracy in even more challenging cases. We thank the reviewer (and also reviewer 5jtg) for suggesting this valuable improvement of our method. We will definitely include it in the paper.

Reviewer btsj2023-08-21

Thanks for the quick updates. I have raised my score to 6 and looking forward to your final results.

Reviewer Zc332023-08-16

I thank the authors for their thoughtful response to my list of weaknesses. Based on their response to my review, also considering their overall response, I have increased my score accordingly. The contributions are interesting and worth consideration by the wider ML community of developers.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC