PaperlayerView exact revision on arXiv

Source-linked AI summary

Coded convolution for parallel and distributed computing within a deadline

Sanghamitra Dutta, Viveck Cadambe, Pulkit Grover

arXiv:1705.03875v1cs.ITmath.IT

TL;DR

Stragglers can delay distributed convolution past a deadline, while expected computation time does not capture deadline-failure probabilities. The paper proposes coded convolution and an asymptotic failure-exponent analysis; its coded strategy has a failure-probability exponent ratio to naive uncoded convolution that scales as Ω(P) and diverges for large P.

  • Problem

    The paper studies reliable convolution of two long vectors across parallel processors when slow or faulty processors can delay completion past a target deadline.

    Source: §I · p. 1

  • Method

    The paper splits and codes convolution vectors for deadline-driven distributed computation and analyzes failure probabilities using an asymptotic exponent under shifted Weibull computation times.

    Source: §I · p. 1

  • Results

    For N1 = Θ(N2) and fixed Weibull parameter α, the coded-to-naive-uncoded asymptotic failure-probability exponent ratio scales as Ω(P), diverging for large P.

    Source: §VI · p. 7

  • Takeaways & Limitations

    The proposed strategy outperforms existing strategies in the exponent of the probability of missing a deadline for large deadlines, and allows online encoding and reconstruction.

    Source: §VII · p. 8

Abstract

from arXiv · show

We consider the problem of computing the convolution of two long vectors using parallel processing units in the presence of "stragglers". Stragglers refer to the small fraction of faulty or slow processors that delays the entire computation in time-critical distributed systems. We first show that splitting the vectors into smaller pieces and using a linear code to encode these pieces provides better resilience against stragglers than replication-based schemes under a simple, worst-case straggler analysis. We then demonstrate that under commonly used models of computation time, coding can dramatically improve the probability of finishing the computation within a target "deadline" time. As opposed to the more commonly used technique of expected computation time analysis, we quantify the exponents of the probability of failure in the limit of large deadlines. Our exponent metric captures the probability of failing to finish before a specified deadline time, i.e. , the behavior of the "tail". Moreover, our technique also allows for simple closed form expressions for more general models of computation time, e.g. shifted Weibull models instead of only shifted exponentials. Thus, through this problem of coded convolution, we establish the utility of a novel asymptotic failure exponent analysis for distributed systems.

I. INTRODUCTION

Convolution supports applications from system response to feature extraction, while slow processors can give distributed computation a long-tailed runtime that threatens deadlines. The paper proposes coded convolution and an asymptotic deadline-failure exponent analysis, including shifted Weibull computation times.

I. INTRODUCTION

  • Convolution with a system’s Green’s function yields its response to an arbitrary input, and convolution also supports feature extraction in CNNs.The introduction notes that low-latency machine-learning inference is bottlenecked primarily by computation time.Source: §I · p. 1
  • The paper proposes splitting and coding convolution inputs for deadline-reliable computation, with online encoding and decoding rather than preprocessing.It also introduces an asymptotic failure-exponent analysis under shifted Weibull computation times, which include shifted exponentials.Source: §I · p. 1
  • A few slow processors can create a long-tailed computation-time distribution and delay completion past a specified deadline.The paper links this straggler problem to Dean and Barroso.Source: §I · p. 1
  • Prior work considered replication, error-correcting codes, coded convolutions, and erasure coding for distributed computation.The paper situates its convolution work as building on.Source: §I · p. 1
  • Expected computation time is a common comparison metric, but it does not capture the probability of missing a specified deadline.The paper notes that extending expected-time analysis to higher moments becomes unwieldy.Source: §I · p. 2

II. ASSUMPTIONS AND PROBLEM FORMULATION

The paper uses two assumed convolution-complexity scenarios, depending on whether the vector lengths are comparable or one is sufficiently shorter.

II. ASSUMPTIONS AND PROBLEM FORMULATION

  • For comparable vector lengths, Scenario 1 assumes convolution complexity C(m1 + m2) log(m1 + m2), with C a constant.The paper notes that FFT convolution has Θ((m1 + m2 − 1)(log(m1 + m2 − 1) + 1)) complexity.Source: §II · p. 2
  • When log(m2) = o(log(m1)), Scenario 2 assumes overlap-method complexity 2Cm1(log(2m2) + 1), with C a constant.The overlap-add method divides the longer vector into pieces comparable in length to the shorter one and combines the resulting outputs.Source: §II · p. 2

Problem Formulation

The problem is to convolve a fixed vector with an unknown input using parallel processors while accounting for stragglers and a completion deadline.

Problem Formulation

  • The task is to convolve a length-N1 vector a with an unknown length-N2 input x using P parallel processing units, reliably and before a specified deadline.Source: Problem Formulation · p. 2
  • The stated condition P ≤ min{N1, N2} keeps the vector lengths from being too far apart for relatively small P.Source: Problem Formulation · p. 2
  • A Toeplitz-matrix formulation has naive Θ(N1N2) complexity, while single-processor FFT convolution under Scenario 1 has complexity C(N1 + N2) log(N1 + N2).The paper notes that matrix-vector parallelization cannot reduce per-processor complexity below Θ(N1N2/P), which may remain larger when P is not large enough.Source: Problem Formulation · p. 2

III. THE NAIVE UNCODED STRATEGY

The naive strategy divides both vectors into pieces and computes their partial convolutions in parallel, then shifts and adds the outputs to reconstruct the full convolution. This approach requires every processor to finish, and using the processors in multiple rounds only increases complexity.

III. THE NAIVE UNCODED STRATEGY

  • The uncoded strategy divides both vectors into smaller pieces and assigns their partial convolutions to the P processors in one shot.The lengths of the pieces are chosen to be comparable when using Scenario 1.Source: §III · p. 2
  • Under Scenario 2, the naive strategy requires equal or higher per-processor complexity, and using the P processors in multiple rounds only increases complexity.Source: §III · p. 3
  • For uncoded convolution, the minimum per-processor complexity in order sense occurs when s1 = s2.The supplied passage does not preserve the full expression for the optimal piece length.Source: §III · p. 3
  • Reconstruction pads partial convolutions, shifts them by their piece offsets, and adds the shifted outputs to obtain the full convolution.The same shift-and-add process combines the partial results for successive pieces of the other vector.Source: §III · p. 3
  • The uncoded strategy requires all P processors to finish, so stragglers can delay the computation beyond its deadline.Source: §III · p. 3

IV. THE REPLICATION STRATEGY

The replication strategy divides the convolution into equal parts and assigns each part r copies across P processors. Its worst-case wait occurs when all replicas of every task but one have finished before any copy of the remaining task finishes.

IV. THE REPLICATION STRATEGY

  • The strategy divides the convolution into P/r equal parts and assigns r replicas to each part, using all P processors.Source: §IV · p. 4
  • Theorem 1 expresses the strategy's requirement as K short convolutions of length s.Source: §IV · p. 4
  • In the worst case, replicas for all but one task finish before any replica of the final task finishes.Source: §IV · p. 4

V. THE CODED CONVOLUTION STRATEGY

Coded Convolution divides the vectors into length-s pieces, encodes pieces of one vector with an MDS code, and distributes coded convolutions across processors. The original partial results can be recovered from a sufficient subset of completed coded outputs.

V. THE CODED CONVOLUTION STRATEGY

B. Comparison with replication strategy:

The section compares coded convolution with replication by worst-case processor wait under equal per-processor computational complexity. It reports that coded convolution waits for fewer processors.

B. Comparison with replication strategy:

C. Computational Complexity of Encoding and Reconstruction:

The section examines whether online encoding and reconstruction add material computational cost. For Vandermonde encoding, their combined complexity relative to per-processor complexity tends to zero as N1, N2, and P grow.

C. Computational Complexity of Encoding and Reconstruction:

VI. ASYMPTOTIC ANALYSIS OF EXPONENTS

The section analyzes failure-probability exponents as deadlines grow, using shifted Weibull computation times. It shows that, for comparable vector lengths and fixed Weibull parameter, coded convolution’s asymptotic failure-probability exponent outpaces the uncoded strategy as processor count grows.

VI. ASYMPTOTIC ANALYSIS OF EXPONENTS

  • The analysis uses a shifted Weibull model for the time to compute a convolution of two length-s vectors on one processor.For the shifted exponential model, the Weibull parameter α equals 1.Source: §VI · p. 6
  • For coded convolution, the analysis bounds the leading failure-exponent coefficient using the worst-case number K of processors that must finish.The failure probability is bounded using the probability that fewer than K processors finish by time t.Source: §VI · pp. 6–7
  • For uncoded convolution, the leading failure-exponent coefficient is exact because failure occurs precisely when at most P − 1 processors finish.The uncoded strategy waits for all P processors.Source: §VI · p. 7
  • For N1 = Θ(N2) and fixed Weibull parameter α, the coded-to-uncoded asymptotic failure-probability exponent ratio diverges as P grows.The theorem states that this ratio scales as Ω(…), but the supplied passage does not provide the expression inside the bound.Source: §VI · p. 7
  • The asymptotic failure exponent for replication depends on the worst-case number of processors that must finish.The simulations compare coded convolution with replication and report that coding outperforms it in the failure-probability exponent for large deadlines.Source: Comparison with Replication · p. 7
  • In simulations using shifted exponential computation times, coded convolution has the steepest failure-exponent decay for large deadlines, outperforming repetition and uncoded strategies.The simulated slopes are reported to be close to theoretically calculated values.Source: Comparison with Replication · p. 7, Figure 4 · p. 8

VII. DISCUSSION

The discussion reports better large-deadline failure exponents than existing strategies and notes that the coded strategy permits online encoding and reconstruction. The appendices compare uncoded scheduling costs, bound coding overhead, and analyze repetition’s failure exponent.

VII. DISCUSSION

  • The proposed strategy outperforms existing strategies in the exponent of deadline-failure probability as deadlines grow.It also allows online encoding and reconstruction, unlike prior coded matrix-vector approaches whose encoding cost can be amortized only when the matrix is pre-specified.Source: §VII · p. 8

APPENDIX A OPTIMAL UNCODED STRATEGY

  • Scenario 2 has equal or higher per-processor complexity, while serial processor reuse raises complexity roughly by √r and still requires every processor to finish.The serial-use cost is compared with performing the convolution in a single shot.Source: Appendix A · p. 9

APPENDIX B ENCODING AND DECODING COMPLEXITY

  • Vandermonde encoding costs O(sP(log P)^2) when N2≤P.Source: Appendix B · p. 10
  • Total reconstruction cost is o(2s log(2s)), so its ratio to per-processor convolution complexity tends to 0 as N1, N2, and P grow.The reconstruction cost includes decoding and subsequent additions.Source: Appendix B · p. 11

APPENDIX C EXPONENT FOR REPETITION

  • For repetition, the upper bound on the leading failure-exponent coefficient is attained at worst-case K=P-r+1 as the deadline grows.K is the number of processors to wait for in the worst case.Source: Appendix C · p. 11

APPENDIX D HEURISTIC ANALYSIS OF EXPONENTS

The appendix argues that some coded-regime choice of s has lower asymptotic failure probability than the uncoded strategy. For selected parameter values, it also reports plots comparing the strategies across chosen α values.

APPENDIX D HEURISTIC ANALYSIS OF EXPONENTS

  • Fig. 5 compares log(-ϵ(s)) for coded and uncoded strategies under N1=4N, N2=N, and P=√log N.The accompanying text reports coding outperforms uncoded for the chosen α values.Source: Figure 5 · p. 13, Appendix D · p. 13
  • The heuristic treats higher E(s) as faster decay of the failure exponent.Source: Appendix D · p. 13
  • Some s in the coded regime yields lower asymptotic failure probability than the uncoded regime.For N1=4N, N2=N, and P=√log N, the reported plots show coding outperforming uncoded for the selected α values.Source: Appendix D · p. 13
Loading 1705.03875v1…