PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Optimal Recovery Threshold of Coded Matrix Multiplication

Sanghamitra Dutta, Mohammad Fahim, Farzin Haddadpour, Haewon Jeong, Viveck Cadambe, Pulkit Grover

arXiv:1801.10292v2cs.ITcs.DC

TL;DR

The paper studies how to make distributed matrix multiplication resilient to faulty and straggling workers while respecting per-worker storage limits. It introduces MatDot, systematic MatDot, and PolyDot coding strategies. MatDot achieves a recovery threshold of 2m −1 versus m^2 for Polynomial codes, while PolyDot trades recovery threshold against communication cost.

  • Problem

    Distributed matrix multiplication must tolerate faulty and straggling workers under memory and communication constraints.

  • Method

    The paper constructs MatDot and systematic MatDot codes, then develops PolyDot codes that interpolate between MatDot and Polynomial codes.

  • Results

    MatDot codes achieve recovery threshold 2m −1, compared with m^2 for Polynomial codes when each worker stores an m-th fraction of each matrix.

  • Takeaways & Limitations

    PolyDot codes provide a tunable trade-off between recovery threshold and communication cost, while MatDot attains the smallest threshold in the stated storage setting.

Abstract

from arXiv · show

We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent "Polynomial code" constructions in recovery threshold, i.e., the required number of successful workers. When $m$-th fraction of each matrix can be stored in each worker node, Polynomial codes require $m^2$ successful workers, while our MatDot codes only require $2m-1$ successful workers, albeit at a higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Further, we propose "PolyDot" coding that interpolates between Polynomial codes and MatDot codes to trade off communication cost and recovery threshold. Finally, we demonstrate a coding technique for multiplying $n$ matrices ($n \geq 3$) by applying MatDot and PolyDot coding ideas.

I. INTRODUCTION

The paper addresses fault- and delay-resilient distributed matrix multiplication by introducing coded strategies with lower recovery thresholds under per-worker storage constraints. MatDot codes reduce the threshold relative to Polynomial codes, while systematic MatDot and PolyDot extend the construction and its communication trade-offs.

  • Motivation: Massive parallelization introduces bottlenecks from faulty nodes and stragglers, motivating coded computation for resilient matrix multiplication.Stragglers are slow or delay-prone processors that can bottleneck the computation when all parallel nodes must finish.
  • Contributions: When each worker stores an m-th fraction of each matrix, Polynomial codes require a recovery threshold of Θ(m^2), whereas MatDot codes require Θ(m).The paper also gives the exact MatDot threshold 2m −1 for the stated matrix-multiplication setup.
  • Contributions: The systematic MatDot construction achieves the same recovery threshold, with the first m worker operations interpretable as uncoded multiplication.This construction is presented separately from the basic MatDot construction.
  • Contributions: PolyDot codes unify MatDot and Polynomial codes, providing a trade-off between recovery threshold and per-worker communication cost.The paper identifies higher communication cost as the price of MatDot’s lower recovery threshold.
  • System model: The computational system separates master preprocessing and task distribution from worker computation and fusion-node aggregation, decoding, and post-processing.Workers may fail or delay, so successful computation uses outputs from successful workers; the formulation assumes symmetric matrix distribution.
  • MatDot codes: MatDot codes divide A into vertical column-blocks and B into horizontal row-blocks, requiring only matched block products rather than all m^2 cross-products.The resulting desired product is recovered as a coefficient of a matrix polynomial by interpolation from 2m −1 evaluations.

B. Complexity analyses of MatDot codes

MatDot encoding and decoding add manageable computational overhead, while worker computation remains the dominant cost when P is much smaller than N. Its main trade-off is higher fusion-node communication than Polynomial codes.

  • O(N^2m log^2 m) decoding complexity is required for interpolating the degree-2m − 2 polynomial across N^2 matrix elements.
  • O(N^2P) encoding complexity is required across P workers because each worker performs two additions of m scaled matrices.
  • O(N^3/m) operations are required per worker for multiplying the encoded N × N/m and N/m × N matrices.
  • O(PN^2/m) symbols are communicated by the master, while the fusion node receives O(mN^2) symbols from successful workers.The master communication matches Polynomial codes, but Polynomial codes require only O(N^2) symbols at the fusion node.

C. Why does MatDot exceed the fundamental limits in [6]

MatDot exceeds the cited fundamental limit because that limit assumes each worker communicates only N^2/m^2 symbols, whereas MatDot workers communicate N^2 symbols. Its systematic construction preserves the 2m−1 recovery threshold while enabling recovery from the first m systematic workers when they finish first.

  • Why the limit does not apply: The fundamental limit in assumes N^2/m^2 symbols communicated by each worker, so it does not apply to MatDot.MatDot instead communicates N^2 symbols per worker; the transmitted matrices contain O(N^2/m) information because of their rank.
  • Communication trade-off: MatDot communicates (2m−1)N^2 symbols in total, exceeding the N^2 symbols in AB.This establishes a trade-off between recovery threshold and worker–fusion communication cost.
  • Systematic recovery: Systematic MatDot codes recover AB by summing the outputs of the first m systematic workers when those workers finish first.Otherwise, the fusion node can interpolate the product polynomial from up to 2m−1 worker outputs and recover the systematic outputs.
  • Systematic recovery: For m=2, the illustrated systematic MatDot system uses four worker nodes and has recovery threshold 3.The construction splits A vertically and B horizontally before encoding worker inputs.
  • Systematic recovery: 2m−1 is the recovery threshold of the systematic construction for every integer m≥2 dividing N.The first m worker outputs are the block products whose sum equals AB.

A. Complexity analyses of the systematic codes

PolyDot codes generalize MatDot and Polynomial codes through parameters s and t, creating tunable recovery-threshold and communication-cost trade-offs. The construction recovers the product after t^2(2s −1) successful workers, with MatDot and Polynomial codes as endpoint cases.

  • PolyDot construction: t^2(2s −1) successful workers suffice for PolyDot codes, with per-worker fusion-node communication bounded by O(N 2/t^2).The parameters satisfy st = m, with s and t dividing N.
  • Example: m = 4 and s = t = 2 gives recovery threshold 12, between MatDot's 9 and Polynomial codes' 16.This example demonstrates the intermediate recovery threshold produced by PolyDot coding.
  • Endpoint cases: s = m and t = 1 yields MatDot codes, while s = 1 and t = m yields Polynomial codes.These endpoint choices instantiate the two existing coding strategies within the PolyDot framework.
  • Trade-off: s = t = √m gives recovery threshold m(2√m −1) = Θ(m^1.5) and total communication Θ(√mN 2), between the endpoint costs.The intermediate setting uses less communication than MatDot but more than Polynomial codes.
  • Construction principle: The three-variable polynomial construction is converted to a single-variable interpolation problem through a substitution involving x, y, and z.The initial substitution yields t^2(2s −1), while a subsequent substitution improves the threshold to st^2 + s −1.

A. Complexity analyses of PolyDot codes

The complexity analysis separates worker encoding, worker computation, communication, and fusion-node decoding for PolyDot codes. Encoding and decoding scale with matrix size and the code parameters, while worker computation depends on the partition dimensions.

  • Encoding: Encoding across P workers has overall complexity O(N 2P).Each worker scales and adds m matrices containing N 2/m elements.
  • Decoding: Decoding has complexity O(N 2t^2(2s −1) log^2 t^2(2s −1)).The fusion node interpolates a polynomial of degree t^2(2s −1)−1 for each of N 2 output elements.
  • Worker computation: Each worker performs matrix multiplication requiring O(N^3/(mt)) computations.The worker multiplies matrices of dimensions N/t × N/s and N/s × N/t.
  • Communication: Each worker receives O(N 2/m) symbols from the master and sends O(N 2/t^2) symbols to the fusion node.The total fusion-node traffic is O((2s −1)N 2), while the recovery threshold is O(t^2(2s −1)).

VI. MULTIPLYING MORE THAN TWO MATRICES

The paper extends coded computation to products of n matrices using one-round coding strategies based on alternating MatDot and Polynomial ideas. These codes reduce communication rounds but require a recovery threshold that grows as Θ(m^⌈n/2⌉).

  • VI. MULTIPLYING MORE THAN TWO MATRICES: n-matrix codes multiply C = D^(1)D^(2) ··· D^(n) using MatDot and Polynomial codes in an alternating fashion.The construction targets products of n matrices with n ≥ 3.
  • B. Codes for n-matrix multiplication: Θ(m^⌈n/2⌉) successful nodes suffice for the proposed n-matrix codes.Theorem 4 states this recovery-threshold scaling for the multiple-matrix problem.
  • A. Problem Statement: Each worker can receive at most nN 2/m symbols from the master node.The system also requires master and fusion-node computation to remain below worker computation complexity.
  • A. Problem Statement: One-round n-matrix coding avoids the intermediate communications required by sequential pairwise multiplication.Sequentially applying two-matrix codes can be inefficient when communication setup overhead increases with the number of rounds.
  • B. Codes for n-matrix multiplication: For n = 4 and m = 2, the example achieves recovery threshold 7.The construction encodes two paired matrix products and recovers the four-matrix product from polynomial coefficients.
  • B. Codes for n-matrix multiplication: For n = 3 and m = 2, the example achieves recovery threshold 5.The coded product is A^(1)B^(1)A^(2).

0 A(1)B(1)A(2)

The construction encodes split matrices into polynomials whose worker-product evaluations allow the fusion node to recover selected coefficients, including products of more than two matrices. For n-matrix multiplication, the required number of successful workers depends on whether n is even or odd.

  • 0 A(1)B(1)A(2): Each worker evaluates the encoding polynomials, computes the resulting matrix product, and sends its output to the fusion node.
  • 0 A(1)B(1)A(2): For the three-matrix example, interpolation of five evaluations recovers coefficients containing A(1)B(1)A(2).
  • 0 A(1)B(1)A(2): The construction splits each input matrix into m blocks before encoding them into polynomial evaluations sent to workers.
  • 0 A(1)B(1)A(2): The general n-matrix construction recovers the desired coefficient from any 2m^(n/2)−1 successful workers when n is even.
  • 0 A(1)B(1)A(2): When n is odd, the construction uses any m^((n−1)/2)(m+1)−1 successful workers to recover the required coefficients.
  • 0 A(1)B(1)A(2): With fewer successful workers than the corresponding threshold, the fusion node declares a failure.

C. Complexity analyses of Construction 4

Construction 4 analyzes worker computation, encoding and decoding, and communication costs for multiplying n matrices. The worker computation scales as O(nN^3/m^2), while communication depends on the parity of n.

  • C. Complexity analyses of Construction 4: Decoding interpolates a polynomial whose degree depends on n and m, with interpolation complexity applied elementwise.
  • C. Complexity analyses of Construction 4: For even n, each worker has computational complexity O(max(nN^3/m^2, N^3/m)).
  • C. Complexity analyses of Construction 4: For odd n, each worker has computational complexity O(nN^3/m^2).
  • C. Complexity analyses of Construction 4: The master node communicates O(nPN^2/m) symbols to the workers.
  • C. Complexity analyses of Construction 4: The fusion node receives O(m^(n/2)N^2) symbols from successful workers when n is even.

D. Generalized n-matrix multiplication

The generalized n-matrix construction introduces flexible block partitions and polynomial substitutions parameterized by s and t. These choices yield recovery thresholds that include improved even- and odd-n expressions and specialize to earlier constructions.

  • D. Generalized n-matrix multiplication: The generalized construction splits input matrices flexibly to trade off communication and computation.
  • D. Generalized n-matrix multiplication: Choosing s=m and t=1 recovers the earlier threshold 2m^(n/2)−1 for even n and its odd-n counterpart.
  • D. Generalized n-matrix multiplication: Each worker evaluates encoded polynomials at distinct points, multiplies the resulting matrix terms, and sends the product to the fusion node.
  • D. Generalized n-matrix multiplication: The fusion node decodes from any k(n,s,t) successful workers, while fewer workers cause failure.
  • D. Generalized n-matrix multiplication: The improved substitutions assign larger powers to selected variables to reduce the maximum degree of the product polynomial.
  • D. Generalized n-matrix multiplication: For even n, Theorem 6 gives a recovery threshold expressed using s and t for any integers satisfying m=st.
  • D. Generalized n-matrix multiplication: For n=2, the generalized substitutions produce thresholds matching subsequent constructions.

E. Complexity analyses of generalized n-matrix codes

The generalized codes quantify decoding, communication, and worker-computation costs, while allowing different block partitions across matrices. The discussion emphasizes that recovery threshold alone does not capture practical coded-computation costs.

  • E. Complexity analyses of generalized n-matrix codes: Decoding complexity is O(N^2k(n,s,t)log^2 k(n,s,t)).
  • E. Complexity analyses of generalized n-matrix codes: The master node sends O(nPN^2/m) encoded symbols before computation begins.
  • E. Complexity analyses of generalized n-matrix codes: For even n, increasing t raises recovery threshold while reducing communication cost for fixed m.
  • E. Complexity analyses of generalized n-matrix codes: For odd n, communication decreases with t while the recovery threshold remains O(m^((n+1)/2)).
  • E. Complexity analyses of generalized n-matrix codes: Each worker has computation complexity at most O(max(nN^3/m^1.5,N^3/m)) for any s and t.
  • E. Complexity analyses of generalized n-matrix codes: The framework permits different partition parameters across matrices and supports nonsquare dimensions through tailored splitting.
  • E. Complexity analyses of generalized n-matrix codes: The discussion warns that focusing exclusively on recovery thresholds while ignoring encoding and decoding costs can produce impractical coded-computing solutions.

A. When is coded computing useful? An example of coded tensor products

Coded computing is most useful when encoding and decoding overhead remain negligible relative to worker computation; tensor products expose a difficult regime because output size matches computational complexity. Polynomial coding recovers tensor products from m^2 evaluations, but its fusion-node decoding can be comparable to the full Θ(N^4) computation.

  • Polynomial-coded tensor products: Polynomial coding evaluates encoded matrix polynomials at distinct worker scalars, and each worker computes the tensor product of its two evaluations.The fusion node receives evaluations of the product polynomial from workers.
  • Polynomial-coded tensor products: m^2 evaluations suffice for Polynomial-coded tensor products because the worker polynomial has degree m^2 −1.The fusion node interpolates the polynomial to recover every Ai⊗Bj coefficient and therefore A⊗B.
  • When coded computing is useful: Θ(N^4) tensor-product outputs make online decoding potentially comparable to the entire computation.For linear operations whose output size matches computational complexity, decoding can be as high as the computational complexity.
  • When coded computing is useful: o(N) conditions on Pge(P) and Pgd(P) make matrix-product encoding and decoding overhead negligible relative to per-node computation.The stated condition applies to online encoding and decoding for matrix-matrix products.
  • When coded computing is useful: Coded computing is most useful when inputs are known in advance so encoding costs can be amortized across multiple computations.For matrix-vector products, master-node encoding is at least the order of input size because every input symbol must be used.

APPENDIX A PROOF OF THEOREM 4

Theorem 4 recovers the product of n matrices by embedding desired products in selected coefficients of a structured polynomial product. Polynomial interpolation then recovers those coefficients from a threshold determined by whether n is even or odd.

  • Coefficient identities: Claim 7 identifies the even-n product as a coefficient formed by multiplying recursively shifted component polynomials.The proof establishes the coefficient identity iteratively using Lemma 3.
  • Coefficient identities: Claim 8 extends the coefficient construction to odd n by isolating each of the m output components.Each component is recovered from a distinct coefficient of the combined polynomial.
  • Proof of Theorem 4: 2m^(n/2) −1 workers suffice when n is even, while (m+1)m^⌊n/2⌋ −1 suffice when n is odd.The fusion node reconstructs the required coefficient or coefficients from evaluations at distinct points.
  • Even n: For even n, the desired product is the coefficient of x^(mn/2−1) in the structured product polynomial.That polynomial has degree 2m^(n/2) −2, so 2m^(n/2) −1 evaluations recover all coefficients.
  • Odd n: For odd n, the desired output is represented by m coefficients associated with the final matrix polynomial.The polynomial degree is m^⌊n/2⌋(m+1) −2, requiring m^⌊n/2⌋(m+1) −1 evaluations.

APPENDIX B PROOF OF THEOREM 5

Theorem 5 constructs a polynomial whose coefficients encode entries of the n-matrix product. A mixed-radix representation proves coefficient uniqueness and identifies the degree positions corresponding to each output entry.

  • Proof strategy: The proof first establishes the maximum degree of pC(x), then shows that its designated coefficients recover C.The even-n case is presented explicitly, with odd n differing mechanically.
  • Degree bound: The maximum degree is obtained by setting i1=t−1, each intermediate index difference to 2s−2 or 2t−2, and the final index to t−1.This yields the maximum-degree expression stated in the proof.
  • Coefficient recovery: The coefficient of x^d(n,i,j) is Ci,j, the (i,j)-th entry of the product matrix C.The degree d(n,i,j) is defined separately for even and odd n.
  • Coefficient recovery: The target coefficient requires the first row index, matching adjacent inner indices, and the final column index to satisfy i1=i, j1=i2 through jn−1=in, and jn=j.These conditions select exactly the terms contributing to Ci,j.
  • Degree representation: Mixed-radix digits uniquely identify degrees up to sn+1tn+1 −1, enabling the proof to distinguish coefficient locations.The radix sequence alternates between t and s.
Loading 1801.10292v2…