Source-linked AI summary
"Short-Dot": Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
Sanghamitra Dutta, Viveck Cadambe, Pulkit Grover
TL;DR
Distributed linear transforms are slowed by stragglers and by the costs of computing, storing, and communicating long dot products. Short-Dot introduces coded redundancy through shorter dot products, and the paper reports theoretical and experimental speedups over existing strategies while characterizing the resilience–length trade-off.
Problem
Stragglers bottleneck distributed linear transforms, while existing coded strategies compute N-length dot products at each processor.
Method
Short-Dot constructs P sparse coded vectors so that any K ≥ M computed short dot products suffice to recover the M original products.
Results
Short-Dot is universally faster than competing strategies for M ≤ P and achieves an Ω(log(P)) speedup over uncoded processing and repetition when M is linear in P.
Takeaways & Limitations
Short-Dot reduces computation, storage, and communication costs by assigning shorter input portions to processors while retaining recovery from a subset of outputs.
Takeaways & Limitations
The analysis assumes shifted-exponential service times, and one stated construction condition is relaxed only in a later remark.
Abstract
from arXiv · showhide
Faced with saturation of Moore's law and increasing dimension of data, system designers have increasingly resorted to parallel and distributed computing. However, distributed computing is often bottle necked by a small fraction of slow processors called "stragglers" that reduce the speed of computation because the fusion node has to wait for all processors to finish. To combat the effect of stragglers, recent literature introduces redundancy in computations across processors, e.g.,~using repetition-based strategies or erasure codes. The fusion node can exploit this redundancy by completing the computation using outputs from only a subset of the processors, ignoring the stragglers. In this paper, we propose a novel technique -- that we call "Short-Dot" -- to introduce redundant computations in a coding theory inspired fashion, for computing linear transforms of long vectors. Instead of computing long dot products as required in the original linear transform, we construct a larger number of redundant and short dot products that can be computed faster and more efficiently at individual processors. In reference to comparable schemes that introduce redundancy to tackle stragglers, Short-Dot reduces the cost of computation, storage and communication since shorter portions are stored and computed at each processor, and also shorter portions of the input is communicated to each processor. We demonstrate through probabilistic analysis as well as experiments that Short-Dot offers significant speed-up compared to existing techniques. We also derive trade-offs between the length of the dot-products and the resilience to stragglers (number of processors to wait for), for any such strategy and compare it to that achieved by our strategy.
1 Introduction
Short-Dot addresses straggler-induced delays in distributed linear transforms by replacing long per-processor dot products with redundant shorter ones. The paper develops the method, characterizes its straggler–dot-product-length trade-off, and reports theoretical and experimental speedups over existing strategies.
- Motivation: Distributed linear transforms are increasingly needed for high-dimensional data, but stragglers can delay completion when uncoded processing requires outputs from every processor.Linear transforms support machine learning, signal processing, and data acquisition, while single-processor speed improvements are constrained by Moore’s-law saturation.
- Short-Dot: Shorter dot products reduce per-processor computation, storage, and communication because processors store and receive only relevant portions of the input.These benefits are motivated by processor memory limits, computation time proportional to dot-product length, and communication costs for distributing x.
- Short-Dot: Short-Dot computes Ax through P coded dot products whose rows contain designed zeros, allowing each processor to compute a shorter product while any K outputs recover Ax.The construction uses P > M processors, and K parameterizes resilience: any K of P coded outputs suffice.
- Fundamental limits: Short-Dot is near-optimal for large N because its achievable dot-product length matches the dominant term in a fundamental lower bound.The paper derives limits on the trade-off between task length and the number of processors required to finish.
- Performance: Short-Dot is universally faster than competing strategies for M ≤ P; when M is linear in P, it achieves an Ω(log(P)) speedup over uncoded processing and repetition.Under exponential service-time tails, the analysis compares Short-Dot with uncoded processing, repetition, and MDS coding; experiments also report faster performance than existing strategies.
2 Our coded parallelization strategy: Short-Dot
Short-Dot encodes a linear transform into P sparse rows whose short dot products can be decoded from any K processor outputs. Its construction uses redundancy and prescribed sparsity to reduce per-processor computation while tolerating stragglers.
- Encoding construction: Short-Dot constructs F = B Ã so any K rows of F can generate the M rows of A.B is chosen so its relevant square submatrices are invertible, enabling decoding from any K processors.
- Decoding: The fusion node linearly combines outputs from the earliest K of P processors to recover Ax.Only the coordinates indexed by each sparse row’s support are communicated and computed.
- Sparse computation: The strategy permits application-specific sparsity patterns through the construction of F.A cyclic unit block is concatenated N/P times to form the sparsity pattern shown in Figure 4.
- Sparse computation: Each row of F has sparsity at most s = N/P (P − K + M), yielding short dot products at individual processors.The construction appends K − M vectors to A to enforce the desired sparsity pattern.
- Comparison with Short-MDS: Short-MDS partitions A into blocks and applies MDS coding, while Short-Dot handles non-divisible sparsity regimes without requiring more processors in the worst case.When s divides N, Short-MDS is described as a special case of Short-Dot.
3 Limits on trade-off between the length of dot-products and parameter K
The paper derives lower bounds linking per-processor dot-product length to the number K of processor outputs required for recovery. These bounds show that Short-Dot is near-optimal when the input dimension N is sufficiently large.
- Basic lower bound: For any A with no all-zero columns, the average row sparsity of F obeys a lower bound derived from this column-zero constraint.The bound follows by relating maximum column zeros to average column zeros and then to average row sparsity.
- Basic lower bound: Any valid coding matrix F must satisfy K ≥ 1 + the maximum number of zeros in any column of F.Otherwise, some K rows could not generate a nonzero entry required by A.
- Comparison with Short-Dot: Short-Dot achieves column sparsity at most P − K + M, compared with the hard lower bound P − K + 1; the bound is tight for M = 1.Its average row-sparsity bound is also tight only for M = 1.
- Tighter bound: For M > 1, some matrices A impose a tighter sparsity lower bound on every F that recovers A from any K rows.The proof limits the number of columns having more than K − M zeros and uses this to bound average sparsity.
- Tighter bound: When N is sufficiently larger than P and M, the N-independent term becomes negligible and Short-Dot’s achieved sparsity matches the leading lower-bound term.The paper therefore concludes that Short-Dot is near-optimal for large N.
4 Analysis of expected computation time for exponential tail models
The analysis models processor service times with shifted-exponential tails and evaluates Short-Dot through expected order statistics. Under this model, Short-Dot’s expected computation time is minimized by choosing the number of processors awaited so that P − K = Θ(M), and it outperforms competing strategies across regimes of M.
- Service-time model: The shifted-exponential model gives tasks a size-proportional minimum time followed by an exponential latency tail governed by the straggling parameter µ.For an s-length dot product, the model replaces the task size N with s; the authors note that empirical validation is needed for any particular environment.
- Expected computation time: Short-Dot’s expected computation time is the expected K-th order statistic among P independent exponential service times.The analysis uses closed-form order-statistic expressions for exponential tails.
- Expected computation time: P − K = Θ(M) minimizes the expected computation time expression for Short-Dot.This choice determines the balance between the number of processors awaited and the number of computed dot products.
- Numerical comparison: Figure 5 reports Short-Dot as faster than MDS when M ≪ P and faster than Uncoded when M ≈ P, with universal superiority across the plotted M range.Repetition is the slowest strategy for the chosen straggling parameter, and ripples arise when M does not exactly divide P.
- Regime comparisons: Short-Dot outperforms MDS coding strategy by a factor diverging to infinity for large P when M is sub-linear in P.Table 2 summarizes the order-sense expected computation times for linear and sub-linear regimes of M.
- Regime comparisons: Short-Dot outperforms Uncoded Strategy by a factor diverging to infinity for large P when M is linear in P.The comparison is stated in order-sense expected computation time.
2 Refer to Appendix for more accurate analysis taking integer effects into account
The appendix-oriented analysis accounts for specific scaling regimes and integer-related effects in the expected computation-time comparisons. When M = P/log P, Short-Dot’s scaled expected time decays to zero while the competing strategies remain bounded away from zero, yielding a speed-up that diverges with P.
- General comparison: Short-Dot universally outperforms MDS Coding, Repetition, and Uncoded strategies over the entire range of M.The comparison is stated for the expected computation-time analysis.
- Scaling regime: M = P/log P is the explicit regime used to show Short-Dot’s speed-ups diverge for large P against all three competing strategies.Theorem 4 specifies this scaling regime for the comparison.
- Scaling regime: Under M = P/log P, Short-Dot’s expected computation time scaled by N decays to 0 as P →∞.The theorem contrasts this decay with the competing strategies’ asymptotic scaling.
- Scaling regime: The competing MDS, repetition, and uncoded strategies have expected computation times scaled by N that remain Ω(1) as P →∞.This is the asymptotic contrast used in the theorem’s speed-up result.
- Proof strategy: The appendix proof substitutes M = P/log P into the expected-time expressions for uncoded, repetition, and MDS-coded strategies.Separate expressions are evaluated for each competing strategy.
- Speed-up: Short-Dot’s speed-up in the M = P/log P regime is log P/log(log P), which diverges to infinity for large P.The result is illustrated in Figure 6, which plots the logarithmically scaled expected computation times.
5 Encoding and Decoding Complexity
Short-Dot’s encoding constructs sparse coded rows so shorter dot products can be used, while Vandermonde structure reduces encoding and decoding to polynomial operations. The resulting decoding complexity is independent of N when M,K ≪ N.
- Encoding Complexity: Encoding forms a P×N matrix F using a P×K matrix B and sparse rows, while any K processor outputs suffice to recover Ax.Each row of F has at most N(P−K+M)/P nonzero elements, and K rows can be linearly combined to generate the rows of A.
- Encoding Complexity: The naive encoding complexity is O(N((K−M)^3 + (K−M)M + PK)), with only N/P unique sparsity patterns in this design.This encoding cost exceeds MDS encoding complexity O(NMP), but is a one-time preprocessing cost.
- Reduced Complexity using Vandermonde matrices: Vandermonde matrices convert encoding into polynomial evaluation and interpolation, reducing encoding complexity to O(NP log^2(P)).The construction uses polynomial operations of degree less than P at P points.
- Decoding Complexity: Decoding uses the first K completed dot products, solves K linear equations, and returns the first M values needed for Ax.The decoded vector is formed by solving for w and taking its first M entries.
- Reduced Complexity using Vandermonde matrices: Short-Dot decoding costs O(K^3 + KM), independent of N when M,K ≪ N, and Vandermonde interpolation further reduces this to O(K log^2(K)).The Vandermonde decoder interpolates a degree-(K−1) polynomial from K arbitrary points.
6 Experimental Results
Experiments on a CMU computing cluster evaluate Short-Dot against uncoded processing and MDS codes for MNIST classification. Short-Dot has the lowest mean computation time, while uncoded processing shows greater variability.
- Experimental setup: The experiment classifies 10,000 MNIST handwritten digits using a trained 1-layer neural network with weight matrix A10×785.Jobs are scheduled simultaneously across P processors using HTCondor.
- Results: Short-Dot outperforms both MDS and Uncoded in mean computation time across the experimental runs.The reported computation time includes input communication, parallel dot-product computation, output collection, decoding, and classification over 35 runs.
- Results: 32%: Short-Dot is faster than MDS, while 12%: Short-Dot is faster than Uncoded in mean computation time.Figure 7 compares Uncoded Strategy, Short-Dot (K=18), and MDS codes.
- Results: Uncoded processing has greater variability and a much higher maximum observed time than MDS and Short-Dot.MDS waits for only 10 of 20 processors but has longer per-processor computation time, increasing straggling.
- Experimental limitations: The experimental times are elevated by platform overheads, including cluster startup and text-file communication and collection.The authors identify alternate distributed platforms with better communication protocols as future work.
7 Discussion
Short-Dot reduces stored-vector and input-communication lengths relative to MDS coding, making it suitable for memory-limited and communication-constrained systems. The construction also extends to error correction and to cases with M ≥ P.
- Practical advantages: Short-Dot stores shorter vectors and communicates shorter input portions than MDS coding, reducing per-processor memory and communication requirements.This is useful when processors cannot pre-store vectors of length N or when multicasting the full input is inefficient.
- Error correction: A Short-Dot code tolerating P−K stragglers can correct floor((P−K)/2) faulty outputs under coding-theoretic arguments.The claim follows from the corresponding Hamming-distance bound.
- Error correction: Error correction can also be formulated as sparse reconstruction using l0 minimization, relaxed to l1 minimization under constraints on B.The sparse-reconstruction formulation provides an alternative decoding route for unknown erroneous outputs.
- Generalization: For M ≥ P, the matrix can be divided into horizontal row chunks and Short-Dot applied to each chunk sequentially.Grouping rows with identical sparsity patterns can further reduce online communication costs.
8 Appendix
The appendix analyzes expected computation time under independent exponential service times and compares Short-Dot with uncoded, repetition, and MDS strategies. It reports asymptotic speedups across linear and sub-linear regimes of M relative to P.
- Probabilistic model: The probabilistic analysis assumes independent processor service times with exponential tails, where μ controls unpredictable computation latency.Expected computation time is analyzed for regimes where M is linear or sub-linear in P.
- Short-Dot analysis: Short-Dot’s expected completion time is governed by the K-th order statistic of P independent processor times and is minimized when K = P−Θ(M).The resulting expression is treated as an upper bound because P bounds the dot-product length.
- Comparison with uncoded processing: When M is linear in P, Short-Dot achieves an Ω(log(P)) speedup over uncoded parallel processing and repetition.The factor diverges as P grows.
- Uncoded strategy: When M is linear in P, uncoded processing takes Θ(MN/P log(P)) expected time, whereas Short-Dot achieves O(N).This yields an asymptotic Short-Dot speedup in the linear-M regime.
- Theoretical plots: Figure 8 varies M from 1 to P for repetition with μ = 5 and P = 1000 while accounting for integer effects.The plot shows theoretical expected computation time under those fixed parameters.
- Comparison with coded strategies: When M is sub-linear in P, Short-Dot outperforms repetition and MDS coding by factors that diverge for large P.The appendix states that Short-Dot universally outperforms the competing strategies over M ≤ P.