Skip to yearly menu bar Skip to main content


Poster

Coded Sparse Matrix Multiplication

Sinong Wang · Jiashang Liu · Ness Shroff

Hall B #211

Abstract: In a large-scale and distributed matrix multiplication problem C=AB, where CRr×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.

Live content is unavailable. Log in and register to view live content