Coded Sparse Matrix Multiplication

Abstract

In a large-scale and distributed matrix multiplication problem $C=A^{⊺}B$, where $C\in {\mathbb{R}}^{r\times t}$, the coded computation plays an important role to effectively deal with "stragglers" (distributed computations that may get delayed due to few slow or faulty processors). However, existing coded schemes could destroy the significant sparsity that exists in large-scale machine learning problems, and could result in much higher computation overhead, i.e., $O(rt)$ decoding time. In this paper, we develop a new coded computation strategy, we call \emph{sparse code}, which achieves near \emph{optimal recovery threshold}, \emph{low computation overhead}, and \emph{linear decoding time} $O(nnz(C))$. We implement our scheme and demonstrate the advantage of the approach over both uncoded and current fastest coded strategies.

arXiv commentnew comparisons with existing sparse codes are added

References in corpus (2)

• Speeding Up Distributed Machine Learning Using Codes
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication

Cited by in corpus (16)

• Learning a Code: Machine Learning for Approximate Non-Linear Coded Computation
• Fundamental Limits of Coded Linear Transform
• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• A Survey of Coded Distributed Computing
• Secure Coded Multi-Party Computation for Massive Matrix Operations
• Parity Models: A General Framework for Coding-Based Resilience in ML Inference
• Coded Iterative Computing using Substitute Decoding
• Rateless Codes for Private Distributed Matrix-Matrix Multiplication
• CodeNet: Training Large Scale Neural Networks in Presence of Soft-Errors
• $C^{3}LES$: Codes for Coded Computation that Leverage Stragglers
• Parity-Checked Strassen Algorithm
• GCSA Codes with Noise Alignment for Secure Coded Multi-Party Batch Matrix Multiplication
• Adaptive Gradient Coding
• Erasure coding for distributed matrix multiplication for matrices with bounded entries
• Coded Elastic Computing
• Fault-Tolerant Strassen-Like Matrix Multiplication