Coded convolution for parallel and distributed computing within a deadline
Authors:
- Sanghamitra DuttaSDSanghamitra Dutta
- Viveck CadambeVCViveck Cadambe
- Pulkit GroverPGPulkit Grover
Preprint
Abstract
We consider the problem of computing the convolution of two long vectors using parallel processing units 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 better 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.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017
- A Unified Coding Framework for Distributed Computing with Straggling Servers2017
- Using Straggler Replication to Reduce Latency in Large-scale Parallel ComputingACM SIGMETRICS Performance Evaluation Review, 2015
- Efficient task replication for fast response times in parallel computationACM SIGMETRICS Performance Evaluation Review, 2014
- On the Delay-Storage Trade-Off in Content Download from Coded Distributed Storage SystemsIEEE Journal on Selected Areas in Communications, 2014
- The tail at scaleCommunications of the ACM, 2013
- Algorithm-based fault tolerance applied to high performance computingJournal of Parallel and Distributed Computing, 2009
- Fault-Tolerant Convolution Via Chinese Remainder Codes Constructed From Non-Coprime ModuliIEEE Transactions on Signal Processing, 2008
- On the arithmetic operational complexity for solving Vandermonde linear equationsJapan Journal of Industrial and Applied Mathematics, 2000
- Algorithm-Based Fault Tolerance for Matrix OperationsIEEE Transactions on Computers, 1984