PaperlayerView exact revision on arXiv

Source-linked AI summary

Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication

Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr

arXiv:1705.10464v2cs.ITcs.DC

TL;DR

Distributed matrix multiplication suffers from latency caused by slow workers, motivating the search for an optimal recovery threshold with efficient master-side decoding. The paper introduces polynomial codes, which organize intermediate computations for interpolation-based recovery and achieve the optimum threshold, with extensions and optimality results for related metrics and convolution.

  • Problem

    Distributed matrix multiplication must mitigate latency from straggling workers while determining the minimum worker subset that permits output recovery and efficient decoding.

  • Method

    Polynomial codes design encoded worker computations so that recovery becomes polynomial interpolation, equivalently Reed-Solomon decoding.

  • Results

    Polynomial codes achieve the optimum recovery threshold mn and optimality across recovery threshold, computation latency, deadline failure probability, and communication load.

  • Takeaways & Limitations

    The code provides order-wise improvement over prior schemes and extends to distributed convolution, where a variation reaches within a factor of 2 of the optimum threshold.

Abstract

from arXiv · show

We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to efficiently deal with straggling workers. The proposed strategy, named as \emph{polynomial codes}, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics. Furthermore, we extend this code to distributed convolution and show its order-wise optimality.

I. INTRODUCTION

The paper addresses straggler-induced latency in distributed matrix multiplication by designing polynomial codes that achieve optimal recovery and efficient decoding. The approach improves on prior coding schemes and extends to distributed convolution.

  • Motivation: Distributed matrix multiplication is motivated by large-scale analytics and machine learning workloads requiring substantial computation and storage.Frameworks such as Hadoop MapReduce and Spark support datasets of tens of terabytes and more.
  • Motivation: Stragglers create a performance bottleneck because the master may need to wait for the slowest workers to finish.Coding-based computation redundancy is proposed as an alternative to replicating straggling tasks.
  • Polynomial Codes: Polynomial codes achieve the optimum recovery threshold mn, which does not scale with the number of workers and is Θ(1).The result applies when each worker stores 1/m of A and 1/n of B.
  • Polynomial Codes: Polynomial codes make any mn intermediate computations sufficient to recover the output by creating an MDS structure on worker computations.The master reconstructs the output through polynomial interpolation, or equivalently Reed-Solomon decoding.
  • Optimality: The code is optimal for recovery threshold, computation latency, deadline failure probability, and communication load.Optimality follows from an information-theoretic cut-set lower bound requiring at least mn returned matrix blocks.

II. SYSTEM MODEL, PROBLEM FORMULATION, AND MAIN RESULT

The system computes C = A^⊺B with a master and N workers, each storing fractional portions of both input matrices. Workers return encoded submatrix products, and the master decodes C from a subset of results.

  • System Model: The target is computing C = A^⊺B in a distributed system with one master and N workers.Each worker stores 1/m of A and 1/n of B.
  • System Model: Each worker stores submatrices derived from A and B, computes their product, and returns the result to the master.The stored submatrices are generated using arbitrary functions of the respective input matrices.
  • Recovery: The master waits for a subset of worker results before applying decoding functions to recover the final output.The model does not impose constraints on decoding functions, although efficient decoding is desirable.

A. Problem Formulation

The formulation represents a computation strategy by functions that assign stored submatrices to workers and defines recoverability through the smallest worker subset sufficient to reconstruct the output.

  • Problem Formulation: A computation strategy consists of 2N functions that generate each worker’s stored submatrices from A and B.The functions are denoted f = (f0, ..., fN−1) and g = (g0, ..., gN−1).
  • Problem Formulation: A strategy is k-recoverable if the master can recover C from the computing results of any k workers.This definition requires recovery from every worker subset of size k.
  • Problem Formulation: The recovery threshold k(f, g) is the minimum integer k for which a computation strategy is k-recoverable.The optimum recovery threshold K∗ is the minimum threshold over all computation strategies.
  • Problem Formulation: The central objective is to determine K∗ and construct a computation strategy that achieves it.The formulation seeks both the optimal threshold and an attaining strategy.

B. Main Result

The polynomial code achieves the optimum recovery threshold for distributed matrix multiplication while enabling efficient decoding through polynomial interpolation. It improves on prior schemes in recovery threshold and is also optimal across several additional performance metrics.

  • The polynomial code achieves K∗ while allowing decoding with the complexity of polynomial interpolation given mn points.Its worker computations are structured so reconstruction can use interpolation or Reed–Solomon decoding.
  • The proposed threshold does not scale with N, whereas the 1D MDS and product-code thresholds scale linearly with N.This gives an order-wise improvement over the stated prior schemes.
  • The polynomial code is optimal for computation latency, failure probability given a deadline, and communication load in addition to recovery threshold.These optimality claims follow from a matching information-theoretic lower bound.
  • Polynomial codes extend to distributed convolution, yielding order-wise improvement directly and a variation within a factor of 2 of the optimum recovery threshold.The variation exploits convolution's computational structure.
  • The Reed–Solomon structure permits detecting up to N − mn module errors and correcting up to ⌊(N−mn)/2⌋ errors.This provides fault-tolerance capability in addition to straggler mitigation.

III. POLYNOMIAL CODE AND ITS OPTIMALITY

The motivating example encodes matrix submatrices so that any four of five worker results recover the output. Its algebraic structure turns decoding into polynomial interpolation.

  • A. Motivating Example: Workers store A0 + iA1 and B0 + i^2B1, producing coded products indexed by worker i.This design encodes the two column-wise matrix partitions with different powers of i.
  • A. Motivating Example: The example uses five workers, each storing half of both input matrices, and targets recovery from any four results.Each worker stores coded submatrices and computes their product.
  • A. Motivating Example: Four received results determine the four uncoded matrix-product components needed for C.The decoding equations use the returned worker products to recover the target components.
  • A. Motivating Example: The designed computation makes decoding a polynomial interpolation problem, or equivalently Reed-Solomon decoding.Fast interpolation algorithms provide almost-linear decoding complexity.
  • A. Motivating Example: Recovering C from four workers is equivalent to interpolating a 3rd-degree polynomial at four points.The coefficient matrix is Vandermonde and is invertible when the worker parameters are distinct in F7.

B. General Polynomial Code

The general polynomial code partitions the inputs, encodes them as polynomial evaluations at distinct field points, and recovers the output by interpolation from any mn workers.

  • B. General Polynomial Code: Each input matrix is divided into m and n column-wise submatrices, respectively.The partitions are written as A = [A0 A1 ... Am−1] and B = [B0 B1 ... Bn−1].
  • B. General Polynomial Code: Workers receive distinct field points xi, and an (α, β)-polynomial code defines their coded inputs and computations.Worker assignments use distinct xi values in Fq.
  • B. General Polynomial Code: Choosing (α, β) = (1, m) gives distinct exponents for the mn uncoded output components.This parameter choice is designed to avoid exponent collisions.
  • B. General Polynomial Code: Each worker evaluates a degree mn −1 polynomial whose coefficients are exactly the mn uncoded components of C.Any mn distinct evaluations uniquely determine this polynomial and therefore C.
  • B. General Polynomial Code: Decoding has complexity O(rt log2(mn) log log(mn)) using polynomial interpolation.The process interpolates degree mn −1 polynomials for rt output entries.
  • B. General Polynomial Code: Interpolation or Reed-Solomon algorithms can reduce decoding complexity further, while finite-field embedding supports real or complex inputs.Quantization and finite-field embedding are suggested for practical implementations.

C. Optimality of Polynomial Code for Recovery Threshold

The recovery threshold mn is both achievable by polynomial codes and necessary for any computation strategy. The code is also optimal under several other performance metrics.

  • C. Optimality of Polynomial Code for Recovery Threshold: A polynomial-code construction achieves recovery threshold mn, providing the upper bound K* ≤ mn.An information-theoretic converse supplies the matching lower bound.
  • C. Optimality of Polynomial Code for Recovery Threshold: At least mn workers are necessary because the output contains rt log2 q bits while each worker provides at most rt/mn log2 q bits.The cut-set bound yields K* ≥ mn.
  • C. Optimality of Polynomial Code for Recovery Threshold: Random linear codes can achieve the optimal threshold with high probability but incur large coding overhead and higher decoding complexity.The stated classical inversion complexity is O(m3n3 + mnrt).
  • D. Optimality of Polynomial Code for Other Performance Metrics: Polynomial code is optimal for computation latency, with every computation strategy satisfying T ≥ Tpoly.This establishes polynomial code as attaining the minimum latency under the considered model.
  • D. Optimality of Polynomial Code for Other Performance Metrics: Polynomial code also minimizes the probability of failure by a deadline and achieves the minimum communication load.These results are stated as a corollary and theorem, respectively.

IV. EXTENSION TO DISTRIBUTED CONVOLUTION

The paper extends polynomial coding to distributed convolution, where workers compute convolutions of coded vectors and the master decodes from a subset of results. The extension improves on prior coded convolution and is nearly optimal.

  • IV. EXTENSION TO DISTRIBUTED CONVOLUTION: The convolution task computes c = a ∗ b from vector partitions over a sufficiently large finite field.Each worker stores two length-s vectors that are functions of the input vectors.
  • IV. EXTENSION TO DISTRIBUTED CONVOLUTION: Workers convolve their stored vectors, and the master waits for the fastest subset before decoding the final convolution.The objective is to characterize and closely achieve the optimum recovery threshold K*conv with efficient decoding.
  • IV. EXTENSION TO DISTRIBUTED CONVOLUTION: The prior coded convolution scheme injects redundancy into one input using MDS codes and has threshold K1D-MDS = N − N/n + m.That scheme is equivalent to the 1D MDS-coded scheme.
  • IV. EXTENSION TO DISTRIBUTED CONVOLUTION: The adapted polynomial code recovers all intermediate values ai ∗bj from any mn workers, strictly improving the prior scheme.This gives Kpoly = mn.
  • IV. EXTENSION TO DISTRIBUTED CONVOLUTION: An improved convolution-specific strategy further reduces the recovery threshold beyond the naive polynomial-code adaptation.The paper states this result as Theorem 4 for workers storing 1/m of a and 1/n of b.
  • IV. EXTENSION TO DISTRIBUTED CONVOLUTION: The convolution extension supports decoding with complexity equal to polynomial interpolation and characterizes the optimum threshold within a factor of 2.The fastest polynomial interpolation or Reed-Solomon decoding gives almost-linear complexity.

V. EXPERIMENT RESULTS

The experiment compares polynomial coding with an uncoded matrix-multiplication scheme on an 18-instance EC2 cluster under simulated stragglers. Polynomial coding reduces tail latency despite decoding overhead, while the comparison excludes some coded baselines because of the instance quota.

  • Experimental setup: The experiment uses Python and mpi4py on an Amazon EC2 cluster with one master and 17 workers.The master runs on a c1.medium instance and workers run on m1.small instances.
  • Experimental setup: Each worker stores and processes one-fourth of each input matrix, and the master decodes after receiving 16 responses.The master uses an FFT-based Reed–Solomon decoding implementation.
  • Baseline: The uncoded comparison uses 16 participating workers, waits for all of them, and requires no decoding.The uncoded workers process one-fourth fractions of uncoded rows from each input matrix.
  • Latency comparison: 37% tail-latency reduction is achieved by polynomial code under simulated straggler effects, including decoding overhead.A randomly selected worker runs a background thread that approximately doubles its computation time.
  • Experimental scope: The experiment cannot implement 1D MDS code and product code because they require at least 21 and 26 nodes, exceeding the EC2 request quota.The stated quota limit is 20 instances.

APPENDIX A OPTIMALITY OF POLYNOMIAL CODE IN LATENCY AND COMMUNICATION LOAD

The appendix proves polynomial code optimality for matrix-multiplication latency and communication load, then develops a convolution code that exploits recoverable linear combinations. The convolution construction reaches recovery threshold m+n−1 with almost-linear decoding complexity, while its optimum is characterized within a factor of 2.

  • Latency optimality: The computation latency T is the earliest time when the output is decodable from results returned by workers completed by that time.Worker computation times are denoted Ti.
  • Latency optimality: Polynomial code achieves the minimum possible computation latency because any strategy must await at least mn completed workers.The proof compares an arbitrary strategy's latency T with polynomial code latency Tpoly and establishes T ≥ Tpoly.
  • Communication optimality: rt log2 q bits is the minimum communication load, and polynomial code attains it using rt elements in Fq.The lower bound follows from the entropy required to recover the output.
  • Convolution construction: For convolution, polynomial coding uses α = β = 1 because recovering the final convolution does not require every individual ai ∗bj.The design allows linear combinations that share the same output-convolution term to be combined.
  • Convolution recovery: Convolution decoding has complexity O(s(m + n) log2(m + n) log log(m + n)), almost linear in input size s(m + n).The process performs interpolation for s degree-m+n−2 polynomials.
  • Convolution scope: The convolution construction extends to real or complex inputs by quantizing values and embedding them into a finite field.The paper states that the distributed convolution algorithm can then be applied directly.

APPENDIX C ORDER-WISE CHARACTERIZATION OF Kconv

The appendix gives lower bounds on the convolution recovery threshold using entropy and cut-set arguments. Together with the polynomial-code upper bound, these bounds characterize the optimum within a factor of 2.

  • Order-wise characterization: The upper and lower bounds differ by no more than a factor of 2 for the convolution recovery threshold.The lower bound is max{m,n}, while the construction supplies the corresponding upper bound through Theorem 4.
  • Lower bounds: A cut-set bound shows that at least n worker results are necessary when one input is fixed and the other is uniformly sampled.Each worker result has entropy at most s log2 q, while the convolution output has entropy sn log2 q.
  • Lower bounds: The convolution optimum satisfies K*conv ≥ max{m, n}, establishing a lower bound from worker-result information capacity.Separate arguments yield K*conv ≥ n and K*conv ≥ m.
Loading 1705.10464v2…