“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products

By Sanghamitra Dutta, Viveck R. Cadambe, Pulkit Grover. 2017

395 citations recorded by the source corpus.

We consider the problem of computing a matrix-vector product <inline-formula> <tex-math notation="LaTeX">$Ax$ </tex-math></inline-formula> using a set of <inline-formula> <tex-math notation="LaTeX">$P$ </tex-math></inline-formula> parallel or distributed processing nodes prone to “straggling,” <italic>i.e.</italic>, unpredictable delays. Every processing node can access only a fraction <inline-formula> <tex-math notation="LaTeX">$({s}/{N})$ </tex-math></inline-formula> of the <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula>-length vector <inline-formula> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula>, and all processing nodes compute an equal number of dot products. We propose a novel error correcting code-that we call “Short-Dot”–that introduces redundant, shorter dot products such that only a subset of the nodes’ outputs are sufficient to compute <inline-formula> <tex-math notation="LaTeX">$Ax$ </tex-math></inline-formula>. To address the problem of straggling in computing matrix-vector products, prior work uses replication or erasure coding to encode parts of the matrix <inline-formula> <tex-math notation="LaTeX">$A$ </tex-math></inline-formula>, but the length of the dot products computed at each processing node is still <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula>. The key novelty in our work is that instead of computing the long dot products as required in the original matrix-vector product, we construct a larger number of redundant and short dot products that only require a fraction of <inline-formula> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> to be accessed during the computation. Short-Dot is thus useful in a communication-constrained scenario as it allows for only a fraction of <inline-formula> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> to be accessed by each processing node. Further, we show that in the particular regime where the number of available processing nodes is greater than the total number of dot products, Short-Dot has lower <italic>expected computation time</italic> under straggling under an exponential model compared to existing strategies, e.g. replication, in a scaling sense. We also derive fundamental limits on the trade-off between the length of the dot products and the recovery threshold, i.e., the required number of processing nodes, showing that Short-Dot is near-optimal.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, ML Systems & Hardware, Numerical Methods & Scientific Computing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

In ML Systems & Hardware

In Numerical Methods & Scientific Computing

Citations in the corpus

FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, methodology): “Many methods have been proposed to address systems heterogeneity and in particular stragglers in distributed learning using coding theory, e.g., [Dutta et al., 2016, Lee et al., 2018, Reisizadeh et al., 2019b, Tandon et al., 2016, Yu et al., 2017].”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, methodology): “algorithms in this article, we are only aware of two concurrent works [29] (see Footnote 13) and [47]14 that provide (codingtheoretic) solutions to this problem.”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, background): “, 2016), more recent work has employed coding theory to speed up distributed machine learning systems (Lee et al., 2017; Li et al., 2015; Dutta et al., 2016; 2017; Reisizadeh et al., 2017; Yang et al., 2017).”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “• In several prior works such as [19, 21, 42, 49], it is often assumed, for the ease of analysis, that runtimes are exponentially distributed.”
Speeding Up Distributed Machine Learning Using Codes (2015, background): “[44] propose a coded computation scheme called ‘Short-Dot’.”
Straggler Mitigation in Distributed Optimization Through Data Encoding (2017, methodology): “Additionally, use of coding in distributed computing has been explored in [13, 7].”
Data Encoding for Byzantine-Resilient Distributed Gradient Descent (2018, methodology): “There has been significant recent interest in using codingtheoretic techniques to mitigate the well-known straggler problem [12], including gradient coding [15]–[18], encoding computation [19], [20], data encoding [13].”
Coded convolution for parallel and distributed computing within a deadline (2017, methodology): “In [4], we introduce a novel class of codes called – Short-Dot codes – that compute multiple straggler-tolerant short dot products towards 2017 IEEE International Symposium on Information Theory (ISIT)”
Gradient Coding Using the Stochastic Block Model (2018, methodology): “It has been used to reduce the runtime of the shuffling phase of MapReduce [5], make distributed matrix multiplication more efficient [6], and reduce the effect of stragglers in certain machine learning computations [7].”
Improving Distributed Gradient Descent Using Reed-Solomon Codes (2017, methodology): “[7] proposed a method that speeds up distributed matrix multiplication by sparsifying the inner products computed at each machine.”
Approximate Gradient Coding via Sparse Random Graphs (2017, methodology): “The use of codes for distributed matrix multiplication and linear operations on functions was also studied in [6], which analyzes the trade-oﬀ between the ﬂexibility and sparsity of the code.”
Coded Distributed Computing for Inverse Problems (2017, methodology): “[6, 8] for matrix multiplications), techniques that utilize ECC achieve scaling-sense speedups in average computation time compared to replication.”
Encoded distributed optimization (2017, background): “The work in [5] also focused on linear operations, where the idea is to break up large dot products into shorter dot products, and perform redundant copies of the short dot products to provide resilience against failures.”
Near-Optimal Straggler Mitigation for Distributed Gradient Methods (2017, methodology): “In [10], [11], maximum distance separable (MDS) error-correcting codes were applied to speedup distributed linear algebra operations (e.g., matrix multiplications).”