Compression-Informed Coded Computing
Authors:
- 25 June 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2177-2182
Abstract
Large-scale computations are ubiquitous and demand exorbitant resources, with matrix multiplication being a prominent example. Multiplying high-dimensional matrices is cumbersome for an individual server but is frequently needed in many applications. To alleviate the computational cost, one can take a low-rank approximation of the matrix product and distribute it over multiple workers. However, the tail latency of such distributed computations is degraded by straggling workers. One solution is to query extra workers with coded inputs to replace the outputs of straggling workers; this technique is called "coded computing." Nearly all existing coded computing schemes apply to multiplying any matrices. Instead, we propose a new framework to design coded computing schemes to take advantage of the structure induced by compression, which we call compression-informed coded computing. We then showcase the benefits of the framework in two steps. First, we illustrate how sketching can lead to linear dependencies in the matrices multiplied by the workers. Second, we apply locality-based coded computing to leverage these linear dependencies to make do with fewer workers compared to coded computing schemes that ignore the structure of the matrices being multiplied.Keywords
This publication has 40 references indexed in Scilit:
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017
- Sketching as a Tool for Numerical Linear AlgebraFoundations and Trends® in Theoretical Computer Science, 2014
- Algorithm-based fault tolerance applied to high performance computingJournal of Parallel and Distributed Computing, 2009
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix MultiplicationSIAM Journal on Computing, 2006
- The source-channel separation theorem revisitedIEEE Transactions on Information Theory, 1995
- Stability of a Method for Multiplying Complex Matrices with Three Real Matrix MultiplicationsSIAM Journal on Matrix Analysis and Applications, 1992
- A linear algebraic model of algorithm-based fault toleranceIEEE Transactions on Computers, 1988
- Extensions of Lipschitz mappings into a Hilbert space1984
- Multiple access channels with arbitrarily correlated sourcesIEEE Transactions on Information Theory, 1980
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948