PaperlayerView exact revision on arXiv

Source-linked AI summary

Rateless Codes for Near-Perfect Load Balancing in Distributed Matrix-Vector Multiplication

Ankur Mallick, Malhar Chaudhari, Utsav Sheth, Ganesh Palanikumar, Gauri Joshi

arXiv:1804.10331v5cs.DCcs.IT

TL;DR

Stragglers bottleneck distributed matrix-vector multiplication, and fixed-rate coding ignores partial work from slow workers. The paper uses rateless LT fountain coding, creating random linear combinations of matrix rows and decoding after slightly more than m completed products. It proves near-ideal latency with asymptotically zero redundant computation and reports up to 3× speed-up over uncoded schemes.

  • Problem

    Fixed-rate erasure coding handles unpredictable slowdowns but ignores partial work from straggling workers, causing redundant computation.

  • Method

    Rateless LT coding distributes random linear combinations of matrix rows and uses peeling decoding after m(1 + ϵ) products are completed collectively.

  • Results

    The strategy achieves near-ideal latency and asymptotically zero redundant computation, with experiments showing up to 3× speed-up over uncoded schemes.

  • Takeaways & Limitations

    Rateless coding provides a better latency-computation trade-off than uncoded, replication, and MDS-coded approaches while utilizing partial work from slow workers.

  • Takeaways & Limitations

    The queueing analysis is difficult for small redundancy and remains an open question for future research.

Abstract

from arXiv · show

Large-scale machine learning and data mining applications require computer systems to perform massive matrix-vector and matrix-matrix multiplication operations that need to be parallelized across multiple nodes. The presence of straggling nodes -- computing nodes that unpredictably slowdown or fail -- is a major bottleneck in such distributed computations. Ideal load balancing strategies that dynamically allocate more tasks to faster nodes require knowledge or monitoring of node speeds as well as the ability to quickly move data. Recently proposed fixed-rate erasure coding strategies can handle unpredictable node slowdown, but they ignore partial work done by straggling nodes thus resulting in a lot of redundant computation. We propose a \emph{rateless fountain coding} strategy that achieves the best of both worlds -- we prove that its latency is asymptotically equal to ideal load balancing, and it performs asymptotically zero redundant computations. Our idea is to create linear combinations of the $m$ rows of the matrix and assign these encoded rows to different worker nodes. The original matrix-vector product can be decoded as soon as slightly more than $m$ row-vector products are collectively finished by the nodes. We conduct experiments in three computing environments: local parallel computing, Amazon EC2, and Amazon Lambda, which show that rateless coding gives as much as $3\times$ speed-up over uncoded schemes.

1 INTRODUCTION

Distributed matrix-vector multiplication is vulnerable to unpredictable stragglers, while dynamic load balancing incurs monitoring and data-movement costs. The paper proposes rateless LT coding to use partial work from slow workers and approach ideal latency with negligible redundant computation.

  • 1 INTRODUCTION: Straggling workers can greatly increase distributed-computation latency, even when individual task delays are usually small.The paper motivates mitigation because large parallel jobs complete only after their slow or unresponsive tasks finish.
  • 1 INTRODUCTION: Dynamic load balancing moves tasks from slow to fast workers but requires continual monitoring, centralized control, and potentially costly data movement.These requirements may be infeasible in cloud systems with unpredictable slowdowns, network outages, privacy concerns, or geographically distributed nodes.
  • 1 INTRODUCTION: Fixed-rate replication and MDS coding cannot balance work within selected workers and discard partial computations from stragglers.These strategies use results from fixed subsets of workers, leaving work from the remaining workers unused.
  • 1 INTRODUCTION: Rateless LT coding creates αm random linear combinations of the matrix rows, distributes them across workers, and decodes Ax after m(1 + ϵ) products.A Robust Soliton degree distribution supports iterative peeling decoding with low decoding complexity.
  • 1 INTRODUCTION: Experiments span local, Amazon EC2, and Amazon Lambda environments, while prior LT-based work used fixed-rate coding and discarded slow-worker partial computations.The paper presents theoretical analysis and experiments across three computing environments.
  • 1 INTRODUCTION: The rateless strategy asymptotically matches ideal latency and computation cost while using partial work from slow workers.The theoretical result states that both latency and computation count converge to the ideal strategy as the matrix size grows.

2 PROBLEM FORMULATION

The system distributes encoded matrix rows across workers that compute row-vector products for a master, which decodes Ax from returned products. Performance is evaluated by latency and total computations against ideal, replication, and MDS-based task-assignment strategies.

  • 2.1 System Model: The master encodes an m × n matrix into an me × n matrix, partitions encoded rows across p workers, and decodes Ax from aggregated results.The redundancy factor is α = me/m, with me ≥ m.
  • 2.1 System Model: Worker runtimes are random because node speed and assigned computational load vary, so the master waits for additional products whenever the received encoded results are undecodable.Workers communicate only with the master in the described system model.
  • 2.2 Performance Criteria: Latency is the time until the master can decode Ax, while computations count all row-vector products completed before decoding.Every strategy must perform at least m computations.
  • 2.2 Performance Criteria: The rateless strategy waits for only m(1 + ϵ) products collectively, contrasting with replication’s submatrix-wise fastest-worker rule and MDS’s k-worker completion rule.This task-collection behavior is the central load-balancing distinction shown in the comparison.
  • 2.3 Benchmarks for Comparison: Ideal load balancing dynamically assigns one row task whenever a worker becomes idle and completes when exactly m tasks finish collectively.This central-queue policy allows faster workers to complete more tasks than slower workers.
  • 2.3 Benchmarks for Comparison: Replication assigns each submatrix to r workers and uses the fastest result for each submatrix, while MDS coding uses k of p workers and tolerates p − k stragglers.Replication with r = 1 is the uncoded strategy; MDS coding adds redundant matrices.
  • 2.3 Benchmarks for Comparison: LT encoding forms each encoded row by summing randomly selected source rows, and peeling decoding repeatedly resolves degree-one symbols and subtracts them from connected sums.The degree is sampled from the Robust Soliton distribution.
  • 2.3 Benchmarks for Comparison: MDS coding performs mp/k row-vector products when no workers are slow, rather than the m products required without redundancy.Its straggler tolerance therefore carries a computation overhead even in the absence of slow nodes.

3 PROPOSED RATELESS CODED STRATEGY

The proposed strategy applies LT rateless codes to matrix-vector multiplication by distributing random linear combinations of matrix rows across workers. The master decodes the product after collecting enough coded results, while LT decoding remains computationally efficient.

  • 3.1 LT Codes: LT coding generates encoded rows by randomly selecting and summing source rows of the matrix, with degrees drawn from the Robust Soliton distribution.The matrix rows are treated as source symbols, and each encoded row is a random linear combination of them.
  • 3.1 LT Codes: The original matrix-vector product can be recovered from M′ coded results, where M′ = m + O(√m ln^2(m/δ)) with probability at least 1 − δ.M′ is the decoding threshold: the number of encoded symbols required to recover the m source symbols.
  • 3.1 LT Codes: LT decoding requires O(m lnm) complexity, compared with O(m^3) for a generic random linear code.The lower decoding complexity is a key practical benefit of the Robust Soliton construction.
  • 3.2 Distributed Implementation: The encoded matrix is precomputed, divided equally among workers, and queried through coded row-vector products until the master has enough results to decode Ax.The master stores the row mapping, collects coded products, applies iterative peeling decoding, and then signals workers to stop.
  • 3.2 Distributed Implementation: Blockwise communication reduces communication overhead, but LT codes may require M′ − m extra symbols and can be improved using Raptor or systematic rateless codes.For m = 11760, the implementation reports waiting for 12500 coded products to decode with 99% probability.

4 PERFORMANCE ANALYSIS

The analysis compares LT coding with ideal load balancing, MDS coding, and replication under a worker-delay model with random initial delays and per-task computation time. LT latency approaches the ideal benchmark as redundancy grows, while its computation cost approaches the minimum and experiments show strong performance against fixed-rate alternatives.

  • 4.2 Ideal Load Balancing Strategy: Ideal load balancing is latency-optimal and performs exactly m row-vector products with zero redundant computation, but it is not exactly realizable in practice.Its implementation requires dynamically allocating tasks as workers become idle, potentially using work stealing or task movement.
  • 4.3 Rateless Coded Strategy: LT latency decreases with redundancy and approaches ideal load-balancing latency, with the gap shrinking exponentially under exponential initial delays.The analysis states that E[TLT] approaches E[Tideal] exponentially fast as redundancy increases.
  • 4.3 Rateless Coded Strategy: LT workers perform exactly M′ computations, and E[CLT] approaches the minimum m computations as m grows.Because E[M′] = m(1 + ϵ) with ϵ → 0, redundant computation is asymptotically negligible.
  • 4.4 MDS Coded Strategy: MDS and replication trade lower straggler sensitivity against extra computation, and their latency remains above the ideal benchmark because of logarithmic delay terms.Adding redundancy can increase computation and latency, while replication may perform nearly the worst-case number of assigned computations.
  • 4.3 Rateless Coded Strategy: LT decoding has O(m lnm) complexity, whereas MDS decoding has O(m^3) complexity, which is unacceptable for large matrices.This computational distinction supports using LT codes to exploit partial work without incurring generic MDS decoding costs.
  • 4.5 Replication Strategy: LT coding with α = 2.0 achieves near-ideal latency and fewer total computations than MDS coding in simulations with m = 10000 rows and p = 10 workers.Increasing α makes LT latency converge toward ideal latency without increasing computations; additional Pareto-delay simulations show similar improvements.

5 QUEUEING ANALYSIS

The LT-coded queueing analysis models streamed matrix-vector jobs and compares their response time with MDS and replication strategies. LT coding benefits from using partial work while avoiding the queueing penalties caused by heavier redundancy.

  • Queueing model: LT coding is analyzed for streamed vectors arriving as a Poisson process, with workers computing encoded products until the master can decode and cancel remaining tasks.The response time includes both queue waiting and service time.
  • LT latency analysis: For large encoded-to-source expansion, the LT mean response time is characterized through an M/G/1 queue with service time T_LT.The analysis applies the Pollaczek-Khinchine formula and uses bounds on the first two moments of T_LT.
  • Analysis boundary: When the expansion factor is small, the queueing analysis remains difficult and is left as an open problem.The resulting system generalizes a fork-join queueing model whose response time is difficult to analyze.
  • Comparison with fixed-rate coding: MDS and replication can reduce the number of required workers through redundancy, but their extra computations increase master-side waiting and overall response time.The trade-off is between completing with fewer workers and adding work to each worker.
  • Simulation: With queued jobs, simulations show that LT coding’s benefits over previous approaches become more pronounced.The experiment uses m = 10000 rows, p = 10 workers, and Poisson arrival rates from 0.1 to 0.6.

6 EXPERIMENTAL RESULTS

Experiments in local parallel, AWS EC2, and AWS Lambda environments compare LT coding with uncoded, replication, and MDS approaches. LT coding consistently achieves lower latency while using fewer computations than replication or MDS coding.

  • Experimental setup: The experiments introduce no artificial delays or background tasks to induce straggling.The reported comparisons therefore use the natural behavior of the tested computing environments.
  • Cross-environment results: 1.2×–3× lower average latency across parallel, EC2, and Lambda settings makes LT coding faster than the other evaluated approaches.Figure 8 summarizes the cross-environment comparison; error bars represent one standard deviation.
  • Cross-environment results: LT coding performs fewer total computations than replication or MDS coding across the evaluated environments.This indicates a lower computation cost alongside the latency advantage.
  • Parallel Computing Experiments: In local multiprocessing, LT and MDS coding are at least about 1.2× faster than uncoded and 2-replication approaches, while LT uses fewer computations.MDS latency is comparable to LT when k = 80 but worsens when k = 50.
  • AWS EC2: On AWS EC2, LT coding is almost 2× faster than MDS and almost 3× faster than uncoded computation.The experiment uses 70 workers and compares LT expansion factors α = 1.25 and 2.0 with MDS and replication baselines.

7 CONCLUDING REMARKS

The paper concludes that rateless fountain coding improves distributed matrix-vector multiplication under stragglers by combining near-perfect load balancing with asymptotically negligible redundant computation. Its demonstrated scope is linear computation, while principled rateless coding for nonlinear tasks remains open.

  • Conclusions: Rateless coding requires only slightly more than m completed encoded row products, adapting to varying worker speeds with asymptotically zero redundant computation.The strategy also has low decoding complexity.
  • Conclusions: Theoretical analysis and experiments show a better latency-computation trade-off than uncoded, replication, and MDS coding approaches.The conclusion compares the proposed approach at the paper level rather than with a single experimental setting.
  • Future work: Future work targets other linear computations, including sparse matrix-vector multiplication, matrix-matrix multiplication, and Fourier transforms.The authors expect rateless properties and partial-work use to benefit these extensions.
  • Scope boundary: A principled rateless coding approach for nonlinear computations remains an open problem because erasure codes are inherently linear.Neural-network-based encoder and decoder methods are noted as recent attempts to handle nonlinear computation.

A PROPERTIES OF LT CODES

The LT-code properties establish modest encoding and decoding costs and show that decoding requires only a vanishing fractional overhead beyond m source symbols. Simulations further examine how successfully decoded symbols change as encoded symbols arrive.

  • Encoding complexity: Each encoded symbol has average degree O(log(m/δ)), so encoding uses O(log m) symbol operations on average.The degree bound supports the stated average encoding complexity.
  • Decoding guarantee: m + O(√m log^2(m/δ)) encoded symbols suffice to recover all m source symbols with probability at least 1 − δ.This is the stated LT decoding guarantee for constant δ > 0.
  • Decoding threshold: The expected decoding threshold is m(1 + ε), where ε approaches zero as m grows.Thus the required overhead is asymptotically a vanishing fraction of the source-block size.
  • Decoding complexity: LT decoding requires O(m log m) symbol operations on average.The complexity follows from the average encoded-symbol degree.
  • Simulation: In the simulation, the number of decoded symbols remains almost constant until 10,000 encoded symbols are received, then rises rapidly.The experiment uses LT-coded multiplication of a 10,000 × 10,000 matrix and a 10,000 × 1 vector.

C.1 Ideal Load Balancing Strategy

Ideal load balancing is a work-conserving benchmark that completes m computations as quickly as possible by assigning pending tasks to available workers. Any other allocation strategy cannot have lower latency under the delay model.

  • C.1 Ideal Load Balancing Strategy: Any distributed scheme without redundancy has latency at least Tideal, because deviations can leave workers idle while other workers still have pending computations.The comparison follows by ordering the time gaps between successive completed computations.
  • C.1 Ideal Load Balancing Strategy: Ideal load balancing assigns pending tasks to the first available worker, preventing idling while computations remain.This work-conserving property underlies its optimality.
  • C.1 Ideal Load Balancing Strategy: The same lower bound holds for redundant task allocations, so redundancy cannot outperform the ideal strategy.A redundant task completes after the earliest assigned worker becomes available plus one task-processing time.
  • C.1 Ideal Load Balancing Strategy: Under the delay model, worker i completes Bi computations at Yi = Xi + τBi, while Tideal is reached when the workers collectively complete m computations.Workers may contribute zero computations if their initial delays are sufficiently large.

C.2 Rateless Coded Strategy

The rateless strategy assigns encoded work with a decoding threshold close to m and analyzes when delayed workers can make its latency exceed the ideal benchmark. Its latency approaches ideal performance as redundancy increases while computation remains near the minimum threshold.

  • C.2 Rateless Coded Strategy: The decoding threshold satisfies M′ ≃ m, so the strategy needs only slightly more than m computations to recover the result.The analysis assumes this threshold relation and notes that its excess over m vanishes asymptotically.
  • C.2 Rateless Coded Strategy: The rateless coded latency TLT decreases with redundancy and approaches the ideal latency Tideal.The analysis bounds the probability and expected cost of events in which the fastest worker becomes idle before decoding.
  • C.2 Rateless Coded Strategy: TLT exceeds Tideal when the fastest worker becomes idle before the workers collectively complete enough computations for decoding.This event is decomposed into idling events Ej caused by delayed workers.
  • C.2 Rateless Coded Strategy: For two workers, increasing redundancy decreases the upper bound on Pr(TLT > Tideal), which becomes zero when the faster worker can complete the entire workload.The stated zero-probability condition is me > 2m.

D THEORETICAL RESULTS FOR QUEUEING ANALYSIS

The queueing analysis models repeated matrix-vector products under Poisson arrivals and compares rateless, MDS, replication, and ideal strategies. The supplied results characterize service and response-time analyses for these schemes.

  • D THEORETICAL RESULTS FOR QUEUEING ANALYSIS: For large redundancy, rateless coding waits for M′ computations in total and can be modeled as a single server with service time TLT.This connects the rateless computation model to queueing analysis.
  • D THEORETICAL RESULTS FOR QUEUEING ANALYSIS: The MDS queue is modeled as a (p,k) fork-join system because the master waits for k workers to finish their assigned tasks.Its worker service time is Yi = Xi + τm/k.
  • D THEORETICAL RESULTS FOR QUEUEING ANALYSIS: The latency tail is highest for replication, while LT codes have the smallest tail and fewer redundant computations than MDS codes or replication.With multiple queued jobs, LT coding also has the least mean response time across the stated arrival values.
  • D THEORETICAL RESULTS FOR QUEUEING ANALYSIS: The replication queue is modeled as a (p/r,p/r) fork-join system because each submatrix is replicated across r workers and the fastest worker in each group suffices.The expected latency is analyzed using the effective group service times Wi.

E ADDITIONAL THEORETICAL RESULTS

Theoretical comparisons show that MDS and replication coding generally have higher latency than ideal load balancing because they cannot exploit work from slower workers. Equality with ideal performance occurs only under restrictive timing conditions in which slower workers start too late to contribute useful transferred work.

  • Comparison with Ideal Load Balancing: MDS and replication match ideal latency only in rare cases where slower workers cannot begin useful computations before the fastest workers complete their assigned work.For MDS, this condition prevents work transfer; for replication, it makes the coded and ideal schedules effectively identical.
  • MDS v/s Ideal: MDS latency exceeds ideal load balancing with high probability, except in timing regimes where the fastest k workers start together and stragglers start much later.The comparison follows from cases where ideal load balancing either excludes some workers or redistributes work beyond the fixed MDS allocation.
  • Replication v/s Ideal: Replication latency exceeds ideal load balancing with high probability, because nonfastest replicas perform redundant work that ideal balancing could reassign.Replication matches ideal performance only when slower workers in each group delay computation until all fastest workers finish.
  • Replication v/s Ideal: Replication divides the matrix into p/r submatrices, assigns each to r workers, and waits for the fastest worker in every group.The resulting group structure explains why slower replicas may compute redundantly rather than receive transferred tasks.

F ADDITIONAL SIMULATIONS AND EXPERIMENTS

Additional simulations compare LT coding with MDS coding and replication under Pareto-distributed worker delays and worker failures. The experiments report lower latency, fewer redundant computations, improved mean response time, and greater robustness to multiple node failures for LT coding.

  • Additional Simulations: LT coding with α = 2.0 clearly outperforms MDS coding with k = 8 in latency, redundant computations, and mean response time under Pareto (1,3) initial delays.The mean response time is averaged over 10 trials with 100 jobs per trial and Poisson (λ) arrivals.
  • Additional Experiments: LT coding with α = 2.0 is more robust to multiple node failures than replication with r = 2 and MDS coding with k = 5.The failure experiment uses an EC2 cluster with 10 t2.micro workers and encodes a 10000 × 10000 identity matrix.
  • Additional Simulations: In the delay model, worker i experiences an initial delay X_i before completing row-vector product tasks, each taking time τ, until enough tasks recover b = Ax.The latency T is the time until sufficient completed tasks allow recovery of the product.
Loading 1804.10331v5…