Coded convolution for parallel and distributed computing within a deadline

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

147 citations recorded by the source corpus.

We consider the problem of computing the convolution of two long vectors using parallel processors in the presence of “stragglers”. Stragglers refer to the small fraction of faulty or slow processors that delays the entire computation in time-critical distributed systems. We first show that splitting the vectors into smaller pieces and using a linear code to encode these pieces provides improved resilience against stragglers than replication-based schemes under a simple, worst-case straggler analysis. We then demonstrate that under commonly used models of computation time, coding can dramatically improve the probability of finishing the computation within a target “deadline” time. As opposed to the more commonly used technique of expected computation time analysis, we quantify the exponents of the probability of failure in the limit of large deadlines. Our exponent metric captures the probability of failing to finish before a specified deadline time, i.e., the behavior of the “tail”. Moreover, our technique also allows for simple closed form expressions for more general models of computation time, e.g. shifted Weibull models instead of only shifted exponentials. Thus, through this problem of coded convolution, we establish the utility of a novel asymptotic failure exponent analysis for distributed systems.

Subfields: Computer Networks and Communications, Hardware and Architecture

How researchers see this paper

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

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (2017, methodology): “As a by-product, we also prove the optimality of polynomial code under several other performance metrics considered in previous literature: computation latency [5, 10], probability of failure given a deadline [9], and communication load [16, 17, 18].”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “recovery, expected computation time, deadline exponents [47],”
Secure Distributed Computing With Straggling Servers Using Polynomial Codes (2019, methodology): “Furthermore, coding techniques may be exploited to mitigate the straggling effect for various distributed computing scenarios such as distributed matrix multiplication [3]–[8], distributed convolution [9], and distributed gradient descent [10], [11].”
Communication-Computation Efficient Gradient Coding (2018, methodology): “proposed new efficient coding schemes to calculate convolutions [15] and the product of a matrix and a long vector [14], Yu et al.”
Coded computation over heterogeneous clusters (2017, methodology): “A similar model has been considered in [34] as well.”
Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication (2018, methodology): “While this follows the shifted exponential delay models used in [12], [14] and [38], the key difference is that the shift is parameterized by the number of computations at each worker.”
Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding (2018, methodology): “The techniques we developed in this paper can also be extended to several other problems, such as coded convolution [12] and fault tolerance computing [14], [15], leading to tight characterizations.”