Straggler-aware Distributed Learning: Communication Computation Latency Trade-off

Abstract

When gradient descent (GD) is scaled to many parallel workers for large scale machine learning problems, its per-iteration computation time is limited by the straggling workers. Straggling workers can be tolerated by assigning redundant computations and coding across data and computations, but in most existing schemes, each non-straggling worker transmits one message per iteration to the parameter server (PS) after completing all its computations. Imposing such a limitation results in two main drawbacks; over-computation due to inaccurate prediction of the straggling behaviour, and under-utilization due to treating workers as straggler/non-straggler and discarding partial computations carried out by stragglers. In this paper, to overcome these drawbacks, we consider multi-message communication (MMC) by allowing multiple computations to be conveyed from each worker per iteration, and design straggler avoidance techniques accordingly. Then, we analyze how the proposed designs can be employed efficiently to seek a balance between the computation and communication latency to minimize the overall latency. Furthermore, through extensive simulations, both model-based and real implementation on Amazon EC2 servers, we identify the advantages and disadvantages of these designs in different settings, and demonstrate that MMC can help improve upon existing straggler avoidance schemes.

This paper was presented in part at the 2019 IEEE International Symposium on Information Theory (ISIT) in Paris, France, and at the 2019 IEEE Data Science Workshop in Minneapolis, USA

References in corpus (22)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Speeding Up Distributed Machine Learning Using Codes
• Revisiting Distributed Synchronous SGD
• Optimal Distributed Online Prediction using Mini-Batches
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Communication-Computation Efficient Gradient Coding
• A Unified Coded Deep Neural Network Training Strategy Based on Generalized PolyDot Codes for Matrix Multiplication
• Computation Scheduling for Distributed Machine Learning with Straggling Workers
• Straggler Mitigation in Distributed Optimization Through Data Encoding
• Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding
• ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding
• Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD
• LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning
• Straggler Mitigation with Tiered Gradient Codes
• Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver
• CAMR: Coded Aggregated MapReduce
• Coded Fourier Transform
• Distributed Stochastic Gradient Descent Using LDGM Codes
• $C^{3}LES$: Codes for Coded Computation that Leverage Stragglers
• Heterogeneity-aware Gradient Coding for Straggler Tolerance
• A Droplet Approach Based on Raptor Codes for Distributed Computing With Straggling Servers
• Fundamental Limits of Approximate Gradient Coding

Cited by in corpus (8)

• Coded Computation across Shared Heterogeneous Workers with Communication Delay
• Bivariate Polynomial Coding for Efficient Distributed Matrix Multiplication
• Bivariate Polynomial Codes for Secure Distributed Matrix Multiplication
• Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation
• Adaptive Gradient Coding
• SCoTTi: Save Computation at Training Time with an adaptive framework
• Storage Codes with Flexible Number of Nodes
• Channel-Adaptive Robust Aggregation for Over-the-Air Federated Learning in Heterogeneous Networks