PaperlayerView exact revision on arXiv

Source-linked AI summary

Coded Sparse Matrix Multiplication

Sinong Wang, Jiashang Liu, Ness Shroff

arXiv:1802.03430v2cs.DCcs.NAmath.NA

TL;DR

Distributed matrix multiplication can bottleneck while waiting for a few slow workers. The paper proposes sparse code, a coded matrix-multiplication scheme, and reports a Θ(mn) recovery threshold with high probability and nearly linear decoding time in nnz(C).

  • Problem

    Waiting for a few slow workers is a major performance bottleneck in distributed matrix multiplication.

    Source: §I · p. 1

  • Method

    The paper introduces sparse code, a coded matrix-multiplication scheme with low computation overhead and decoding time linear in nnz(C).

    Source: §VI · p. 15

  • Results

    Θ(mn) recovery threshold with high probability and nearly linear decoding time O(nnz(C) ln(mn)) at the master node.

    Source: A. Main Results · p. 4

  • Takeaways & Limitations

    Theoretical and simulation results exhibit order-wise improvement for sparse code compared with existing schemes.

    Source: §VI · p. 15

Abstract

from arXiv · show

In a large-scale and distributed matrix multiplication problem $C=A^{\intercal}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.

I. INTRODUCTION

Slow workers delay distributed matrix multiplication, while sparse machine-learning matrices make the computational cost of coding a central concern. The section asks whether coding can mitigate stragglers without imposing high overhead on sparse multiplication.

I. INTRODUCTION

  • Waiting for a few slow workers is a major performance bottleneck in distributed matrix multiplication; slow or faulty processors are called stragglers.Coding adds redundancy so the output can be recovered from partial worker results.Source: §I · p. 1
  • Sparse machine-learning problems can have nnz(A) ≪ rs, nnz(B) ≪ st, and nnz(C) ≪ rt, motivating the question of whether coding efficiently mitigates stragglers.The introduction notes such problems occur in machine learning and signal processing.Source: §I · pp. 1–2

A. Motivation: Coding Straggler

  • Polynomial-code matrix additions can increase coded-matrix densities by at most m and n, making multiplication roughly O(mn) times the uncoded cost.The passage explains this as a consequence of adding sparse submatrices into coded matrices.Source: A. Motivation: Coding Straggler · p. 2
  • For sparse matrices, the measured polynomial-code scheme required five or more times the uncoded computation, with the ratio particularly large, O(mn), when matrices were sparse.The comparison plots the average local-computation-time ratio against matrix density.Source: A. Motivation: Coding Straggler · pp. 2–3
  • Existing polynomial and MDS decoding can take O(rt ln2(mn ln(mn))), which the authors characterize as costly for large-scale sparse data.The paper seeks a coded scheme with small recovery threshold, low computation overhead, and decoding complexity dependent only on nnz(C).Source: A. Motivation: Coding Straggler · p. 3

B. Main Contribution

Sparse code combines sparse-aware worker computations with hybrid decoding to achieve a Θ(mn) recovery threshold and nearly linear decoding. The paper also analyzes its rank conditions and reports order-wise improvements over existing schemes.

B. Main Contribution

  • Sparse code exploits sparsity in both input and output matrices, with computation load O(ln(mn)) times the uncoded scheme and decoding O(nnz(C) ln(mn)).The paper describes the decoding time as nearly linear in the number of nonzeros in C.Source: B. Main Contribution · p. 3
  • Each worker selects input submatrices using degree distribution P, computes a weighted linear combination, and returns results for the master’s hybrid decoding.The master begins decoding when the collected coefficient matrix is full rank.Source: B. Main Contribution · p. 3
  • Under a Wave Soliton degree distribution, the hybrid decoder recovers results after Θ(mn) completed tasks, with a constant number of rooting steps.For small mn, the paper formulates an optimization problem to determine the degree distribution P.Source: B. Main Contribution · p. 3
  • The rank analysis reduces to whether a random bipartite graph contains a perfect matching, yielding full rank with high probability after mn tasks.The analysis uses the Schwartz-Zeppel Lemma, combinatorial graph theory, and the probabilistic method; degree-distribution-generated rows have dependent elements.Source: B. Main Contribution · p. 3
  • The paper implements sparse code on Ohio Supercomputing Center resources and reports empirical performance gains over existing strategies.The supplied passages identify the implementation site but do not specify benchmark values.Source: B. Main Contribution · p. 3

II. PRELIMINARY

  • The preliminary setup divides A and B into m and n column submatrices, respectively, producing mn blocks Cij for the master to recover from worker results.The recovery threshold is the minimum number of worker results sufficient to recover C.Source: §II · p. 4

A. Main Results

  • The sparse code achieves a Θ(mn) recovery threshold with high probability and nearly linear master decoding time O(nnz(C) ln(mn)).The paper says this matches the recovery-threshold lower bound with a constant gap and high probability.Source: A. Main Results · pp. 4–5
  • Table I compares coding schemes across recovery threshold, computation overhead, and decoding complexity, with the sparse code providing order-wise improvements.The paper identifies these three comparison dimensions; the supplied passages do not give the table's cell values.Source: A. Main Results · p. 4, Table I · p. 5

III. SPARSE CODES

Sparse code is introduced through a motivating example: workers compute sparse weighted sums, and the master combines peeling with rooting to recover C in O(nnz(C)) time.

A. Motivating Example

  • Each worker computes a weighted sum of the four output blocks, and peeling recovers blocks from degree-one tasks by subtracting known blocks.Source: A. Motivating Example · pp. 5–6
  • Solving the full-rank system directly recovers C but requires rt/4 linear systems and O(rt) complexity.Source: A. Motivating Example · p. 6
  • When peeling has no ripple, the master roots decoding by recovering a block through a linear combination of collected results.Source: A. Motivating Example · pp. 6–7
  • O(nnz(C)) decoding uses simple matrix additions to recover the output blocks.In the motivating example, peeling recovers C with three sparse matrix additions.Source: A. Motivating Example · pp. 6–7

B. General Sparse Code

The general sparse code assigns each worker a sparse random linear combination of input blocks, then uses rank, peeling, and rooting to decode.

B. General Sparse Code

  • Each worker's coefficients follow a degree distribution, with nonzero weights independently and uniformly drawn from a set S.Source: B. General Sparse Code · p. 7
  • The master decodes once the collected coefficient matrix has column full rank, using peeling and a rooting step when no ripple exists.Source: B. General Sparse Code · p. 7
  • Rooting recovers a chosen block by solving M^T u = e_k0 and taking the corresponding linear combination of collected results.Source: B. General Sparse Code · pp. 7–8
  • Decoding complexity depends on coefficient-matrix density, recovery threshold, and the number of rooting steps.Source: B. General Sparse Code · p. 8

IV. THEORETICAL ANALYSIS

The analysis designs a sparse coefficient matrix between low-density, high-threshold coding and dense, low-threshold coding, then studies full rank through random-graph matchings.

IV. THEORETICAL ANALYSIS

  • The analysis chooses a sparse coefficient matrix to limit decoding complexity, while recognizing that lower density can require collecting more workers for full rank.Source: §IV · p. 9
  • The sparse code achieves recovery threshold K = Θ(mn) and a constant number of rooting steps with high probability.Source: §IV · p. 9
  • The Wave Soliton distribution modifies the Soliton distribution by capping the maximum degree at mn and reallocating a constant weight from degree 2 to larger degrees.Source: §IV · p. 9

A. Full Rank Probability

B. Optimality of Recovery Threshold

Sparse code achieves a Θ(mn) recovery threshold with high probability and decoding complexity O(nnz(C) ln(mn)). The section also describes an optimization for choosing a degree distribution to reduce worker overhead while meeting recovery conditions.

B. Optimality of Recovery Threshold

  • With K = Θ(mn), sparse code recovers all mn blocks with probability at least 1 − e^−cmn, yielding a Θ(mn) recovery threshold and O(nnz(C) ln(mn)) decoding complexity.The recovery uses Θ(1) blocks from the rooting step.Source: B. Optimality of Recovery Threshold · p. 11
  • The practical recovery threshold is reported to be close to the information-theoretic lower bound, with overhead below 15%.The authors attribute the gap between the theoretical result and practical performance mainly to a pessimistic estimate in Theorem 3.Source: B. Optimality of Recovery Threshold · p. 11
  • Sparse code has a much lower practical recovery threshold than Tornado and LT codes, whose Θ(mn) thresholds can have large constants, especially below 10^3 blocks.The comparison is described as applying to the practical thresholds in Figure 4.Source: B. Optimality of Recovery Threshold · p. 11, Figure 4 · p. 12

C. Optimal Design of Sparse Code

  • For small m and n, the asymptotic analysis used to bound full-rank probability and decoding error can be loose.The section motivates optimizing the degree distribution using the preceding analyses.Source: C. Optimal Design of Sparse Code · p. 12
  • The degree-distribution optimization minimizes average degree to reduce worker computation and communication overhead, subject to a full-rank probability constraint.The analysis replaces the difficult exact probability constraint with a bound and discretizes an interval to obtain linear constraints.Source: C. Optimal Design of Sparse Code · p. 12

V. EXPERIMENTAL RESULTS

Experiments compare sparse code with uncoded and existing coded schemes on generated and real sparse matrices. Sparse code shows lower completion times and order-wise improvements in the reported comparisons, with especially pronounced effects on real datasets.

V. EXPERIMENTAL RESULTS

  • For two 1.5E5 × 1.5E5 matrices with 6E5 nonzeros, sparse code has the minimum job completion time, using 20–30% of LT-code time, 30–50% of sparse-MDS and product-code time, and 15–20% of polynomial-code time.The uncoded scheme is faster than polynomial code in this comparison.Source: Figure 5 · p. 13, §V · p. 13
  • Sparse code outperforms product and polynomial codes across component times, with larger effects on transmission and decoding.The comparison covers input communication, parallel multiplication, output fetching, and decoding.Source: §V · pp. 13–14, Figure 6 · p. 14
  • In the reported comparison, at s = 2, the proposed sparse code requires 18 workers, whereas the LT code requires 24 workers on average.Source: §V · p. 14
  • Sparse code speeds up 1–3× over the uncoded scheme and outperforms existing codes, with stronger effects on real datasets.Timing results are averages over 20 runs; for square, tall, and fat matrices, LT, random sparse, and product codes finish faster than uncoded, while on the real datasets they finish slower.Source: Table III · p. 15, §V · p. 15

VI. CONCLUSION

  • The conclusion reports order-wise improvement over existing schemes in both theoretical and simulation results.The proposed scheme is described as having near-optimal recovery threshold, low computation overhead, and decoding time linear in the number of nonzeros.Source: §VI · p. 15

A. Proof of Theorem 2

The proof establishes the matching condition needed for recovery by bounding the probability of violating sets in the random bipartite graph. It divides the analysis into cases based on the size and side of the violating set.

A. Proof of Theorem 2

  • The proof uses Hall's theorem: if the bipartite graph lacks a perfect matching, a violating set S must exist on one side of the graph.The argument bounds the probability of such sets separately for S in V1 and S in V2.Source: A. Proof of Theorem 2 · pp. 17, 21
  • For S ⊆ V1, the proof divides set sizes into cases and concludes that the probability of a violating set is o(1).The cases include isolated vertices, intermediate sizes, and sets whose size is proportional to d.Source: A. Proof of Theorem 2 · pp. 17, 20, 21, 22
  • Figure 7 illustrates two structures satisfying the stated conditions for a violating set, each without a perfect matching.Source: A. Proof of Theorem 2 · p. 17, Figure 7 · p. 18
  • For S ⊆ V2, the proof relaxes one condition to upper-bound the event and likewise concludes that its probability is o(1).The analysis treats constant, sublinear, and proportional set sizes.Source: A. Proof of Theorem 2 · pp. 21–22

B. Proof of Lemma 3

The proof applies a random-graph peeling-decoding bound to the degree distribution generated by the code. It expresses the failure probability in terms of the recovery threshold and the resulting edge-degree distributions.

B. Proof of Lemma 3

  • The recovery analysis draws on an existing quantitative condition for peeling decoding expressed through λ(x) and ρ(x).Source: B. Proof of Lemma 3 · p. 22
  • Lemma 6 bounds the probability that peeling decoding fails to recover at least δd blocks by e^−cd for some constant c.Source: B. Proof of Lemma 3 · p. 23
  • The proof derives the left and right edge-degree distributions from the Wave Soliton degree distribution and the recovery threshold K.It then uses these distributions with Lemma 6, setting δ = b/mn, to obtain the lemma.Source: B. Proof of Lemma 3 · pp. 22–23

C. Proof of Theorem 3

For K=cd+1, the proof invokes a basic fact and the Wave Soliton distribution, then addresses a remaining bound involving e−cΩ′.

D. Optimal Design of Sparse Code

The section designs a degree distribution by relaxing a hard full-rank constraint to a perfect-matching probability constraint. It derives an exact matching-probability formula and reports optimized distributions with lower recovery thresholds and more rooting steps than RSD at the same average degree.

Loading 1802.03430v2…