Quantum mechanics

Algorithm

Gaussian

Statistics

Materials science

Block matrix

Theoretical computer science

Sparse matrix

Computation

Eigenvalues and eigenvectors

Parallel computing

Coding (social sciences)

Computer science

Matrix (chemical analysis)

Speedup

Physics

Mathematics

Composite material

IEEE Journal on Selected Areas in Information Theory

The overall execution time of distributed matrix computations is often dominated by slow worker nodes (stragglers) within the computation clusters. Recently, coding-theoretic techniques have been utilized to mitigate the effect of stragglers where worker nodes are assigned the job of processing encoded submatrices of the original matrices. In many machine learning or optimization problems the relevant matrices are often sparse. Several prior coded computation methods operate with dense linear combinations of the original submatrices; this can significantly increase the worker node computation times and consequently the overall job execution time. Moreover, several existing techniques treat the stragglers as failures (erasures) and discard their computations. In this work, we present a coding approach which operates with limited encoding of the original submatrices and utilizes the partial computations done by the slower workers. While our scheme can continue to have the optimal threshold of prior work, it also allows us to trade off the straggler resilience with the worker computation speed for sparse input matrices. Extensive numerical experiments done over cloud platforms confirm that the proposed approach enhances the speed of the worker computations (and thus the whole process) significantly.

A Unified Treatment of Partial Stragglers and Sparse Matrices in Coded Matrix Computation