Computation Efficient Coded Linear Transform

Sinong Wang, Jiashang Liu, Ness B. Shroff, Pengyu YangAISTATS 2019 · OpenReview

Abstract

In large-scale distributed linear transform problems, coded computation plays an important role to reduce the delay caused by slow machines. However, existing coded schemes could end up destroying the sparsity of the original data, leading to a significant increase in local computation time. This paper introduces a new class of "coded computation" strategies—specifically the s-diagonal code and (d1, d2)-cross code—designed to speed up distributed linear transformations ($y = Ax$). These codes achieve the theoretical optimum for both recovery speed and computational efficiency, particularly when dealing with large-scale sparse data.

Introduction

In distributed computing, a large task like multiplying a massive matrix $A$ by a vector $x$ is split across many worker nodes. However, the system is often bottlenecked by "stragglers"—nodes that are slow or fail. To mitigate this, researchers use coded computation, sending redundant, mathematically combined versions of the data to workers so the master node can reconstruct the final result even if some workers haven't finished.

The gold standard has been "Polynomial codes," which offer an optimal recovery threshold (the minimum number of workers needed). However, most existing codes "smear" the data together. If the original matrix $A$ is sparse, these codes turn it into a dense matrix, creating a massive "computation overhead" that often negates the time saved by ignoring stragglers.

System Model and Methods

The proposed framework involves a master node that encodes data submatrices and distributes them to workers.

Distributed coded computation framework illustrating data encoding, worker computation, and decoding at the master node.

The authors propose two primary novel coding schemes:

  1. s-diagonal code: A structured coding matrix where each worker only processes a small, overlapping "diagonal" slice of the input submatrices. It is designed to be as sparse as possible while guaranteeing recovery from any $n$ out of $m$ workers.
  2. Probabilistic (d1, d2)-cross code: By relaxing the requirement to work for almost all subsets of workers with high probability, this code achieves constant computation load. The amount of work per node does not increase even as the total number of workers grows.

To support these, a Fast Decoding Algorithm was developed using a hybrid "peeling decoding" approach (similar to solving Sudoku) and Gaussian elimination, keeping decoding time nearly linear ($O(rs)$).

Experimental Evaluation

The methods were evaluated using synthetic Bernoulli matrices, the University of Florida Sparse Matrix Collection ($10^6 \times 10^6$ dimensions), and the LIBSVM dataset for distributed gradient descent.

The "aha moment" of this research is realizing that the density of the coding matrix is as critical as straggler tolerance. By mapping the recovery problem to bipartite graph matching, the authors prove that sparsity can be maintained without sacrificing reliability.

Key Results

The s-diagonal code achieves the theoretical minimum computation load ($n(s+1)$) while maintaining the optimal recovery threshold.

Comparison of job completion times for various coding schemes across different numbers of workers (n) and stragglers (s).

As shown in the experimental results, the (2,2)-cross code converged 30% faster than sparse MDS codes and at least 4 times faster than state-of-the-art Polynomial codes. Notably, even as the number of stragglers ($s$) increased, the job completion time for the cross-code remained nearly constant, demonstrating superior resilience compared to other methods.

Conclusion

This work demonstrates that it is possible to break the "deterministic" limit of computation overhead in coded distributed systems. By focusing on sparsity preservation, the proposed s-diagonal and cross codes offer a significant performance boost for linear transformations. Future work may extend these concepts to non-linear operations common in deep learning and further optimize communication costs in bandwidth-constrained environments.

Summary updated

Abstract

In large-scale distributed linear transform problems, coded computation plays an important role to reduce the delay caused by slow machines. However, existing coded schemes could end up destroying ...
BibTeX
@inproceedings{wang2019computation,
  author = {Sinong Wang and Jiashang Liu and Ness B. Shroff and Pengyu Yang},
  title = {{Computation Efficient Coded Linear Transform}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=50-d77iAYrep},
}
Figure