PaperlayerView exact revision on arXiv

Source-linked AI summary

Speeding Up Distributed Machine Learning Using Codes

Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris Papailiopoulos, Kannan Ramchandran

arXiv:1512.02673v3cs.DCcs.ITcs.LGcs.PF

TL;DR

Large-scale distributed learning is affected by stragglers, failures, and communication bottlenecks, while connections between coding, machine learning, and distributed systems have been limited. The paper applies coding to matrix multiplication and data shuffling, showing theoretical gains over uncoded methods and experimental speedups of up to 40%.

  • Problem

    Distributed machine-learning systems face stragglers, system failures, and communication bottlenecks, but coding has had limited interaction with distributed machine learning and systems.

  • Method

    The paper embeds coding into algorithmic design for matrix multiplication and data shuffling, using redundancy against stragglers and cached data to reduce communication.

  • Results

    Coded matrix multiplication is Θ(log n) times faster under exponential-tailed subtask runtimes, while coded shuffling reduces communication by Θ(γ(n)) when each worker caches a constant data fraction.

  • Takeaways & Limitations

    Coding can reduce computation and communication bottlenecks in distributed learning while operating within the algorithmic design layer over input representations.

Abstract

from arXiv · show

Codes are widely used in many engineering applications to offer robustness against noise. In large-scale systems there are several types of noise that can affect the performance of distributed machine learning algorithms -- straggler nodes, system failures, or communication bottlenecks -- but there has been little interaction cutting across codes, machine learning, and distributed systems. In this work, we provide theoretical insights on how coded solutions can achieve significant gains compared to uncoded ones. We focus on two of the most basic building blocks of distributed learning algorithms: matrix multiplication and data shuffling. For matrix multiplication, we use codes to alleviate the effect of stragglers, and show that if the number of homogeneous workers is $n$, and the runtime of each subtask has an exponential tail, coded computation can speed up distributed matrix multiplication by a factor of $\log n$. For data shuffling, we use codes to reduce communication bottlenecks, exploiting the excess in storage. We show that when a constant fraction $α$ of the data matrix can be cached at each worker, and $n$ is the number of workers, \emph{coded shuffling} reduces the communication cost by a factor of $(α+ \frac{1}{n})γ(n)$ compared to uncoded shuffling, where $γ(n)$ is the ratio of the cost of unicasting $n$ messages to $n$ users to multicasting a common message (of the same size) to $n$ users. For instance, $γ(n) \simeq n$ if multicasting a message to $n$ users is as cheap as unicasting a message to one user. We also provide experiment results, corroborating our theoretical gains of the coded algorithms.

I. INTRODUCTION

The paper applies coding theory to two core distributed-learning bottlenecks: computation slowed by stragglers and communication-heavy data shuffling. It develops coded matrix multiplication and coded shuffling, with theoretical speedups and algorithmic integration at the representation-data layer.

  • Scope and motivation: Coding targets matrix multiplication and data shuffling, two primitives underlying many distributed data-processing and machine-learning algorithms.The paper focuses on computation and communication phases rather than redesigning the entire distributed workflow.
  • Coded shuffling: Θ(γ(n)) communication-cost reduction is obtained by coded shuffling when a constant fraction of the data matrix is cached at each worker.γ(n) measures the advantage of multicasting over unicasting; γ(n) ≃ n when multicast to n users costs as much as one unicast.
  • Design approach: Coding and decoding operate over input representations such as floats or doubles and are embedded in algorithmic design without modifying the distributed system.This places the coding solution at the algorithmic design layer rather than the stored or transmitted bit layer.
  • Coded computation: Coded computation stores A1, A2, and A1 + A2 so the master recovers AX from any 2 worker products without waiting for the slowest response.For example, A2X is recovered by subtracting A1X from (A1 + A2)X.
  • Coded computation: Θ(log n) faster matrix multiplication is achieved with optimal coding when n workers have exponentially distributed subtask runtimes.Coded computation uses redundancy to avoid waiting for a bounded number of stragglers.
  • Coded shuffling: 50% communication-cost savings arise in the two-worker coded-shuffling example by multicasting A2 + A3 instead of separately transmitting A2 and A3.Workers use their cached batches to decode the desired data.

II. RELATED WORK

Prior work addresses stragglers through detection, asynchronous execution, replication, and coded storage, while this paper develops coding-based approaches for computation and shuffling.

  • Stragglers arise from unpredictable latency, shared resources, maintenance, and power limits, and cannot be completely removed from distributed clusters.
  • Asynchronous execution reduces dependence on stragglers but can break serial consistency and fail to guarantee the serial algorithm’s output.
  • Replication-based scheduling reduces latency by collecting fast responses and potentially canceling slower replicas.
  • This paper uses coding opportunities for distributed computation and data shuffling, including coded caching to reduce communication costs.
  • Coded computation introduces redundancy so the original task can be decoded from a subset of subtask results, treating unfinished subtasks as erasures.

B. Runtime of Uncoded/Coded Distributed Algorithms

Coded distributed algorithms terminate after collecting results from a decodable worker set, rather than waiting for every worker, so runtime depends on the code’s recovery structure.

  • Runtime analysis assumes identically distributed, independent task times, while distributions may differ across computation schemes.
  • A coded algorithm terminates when the master receives results from any decodable set of workers.
  • Uncoded computation is the special case whose only decodable set contains all workers, so one straggler can delay completion.
  • For an (n,k) MDS code, any k worker results form a decodable set, making runtime equal to the kth response rather than the nth.

C. Probabilistic Model of Runtime

The probabilistic model uses a common mother runtime distribution, symmetric task allocation, homogeneous workers, and independent task times to compare uncoded and coded algorithms.

  • Task runtimes follow scaled versions of a continuous mother distribution F, with homogeneous workers and independent computing times.
  • The symmetric allocation assumed here is optimal for homogeneous clusters but can be strictly suboptimal for heterogeneous clusters.
  • Uncoded runtime uses n subtasks, whereas coded schemes divide the task into k subtasks and add n−k coded tasks.
  • For an (n,k)-MDS-coded algorithm, the runtime distribution is the kth order statistic of worker runtimes.
  • For fixed n and k, repetition-coded runtime strictly dominates MDS-coded runtime because MDS decodable sets include repetition-code decodable sets.
  • The experiments compare uncoded, repetition-coded, and MDS-coded algorithms with n=10 and k=5 under shifted-exponential and Amazon EC2 runtime distributions; MDS has the lightest tail in both cases.

D. Optimal Code Design for Coded Distributed Algorithms: The Shifted-exponential Case

For shifted-exponential runtimes, the paper optimizes code parameters for expected runtime, establishes a lower bound, and shows that optimal MDS coding is order-optimal while incurring storage overhead.

  • The shifted-exponential model is the sum of a constant and an exponential random variable and is used for analytically tractable expected-runtime optimization.
  • The average uncoded runtime is 1 + (1/µ) log n, while repetition-coded and MDS-coded runtimes use different order-statistic expressions.
  • The optimal repetition code sets k=n when µ≥1, while for µ=1/v it sets k=µn and achieves minimum average runtime (1/(nµ))(1+log(nµ)).
  • Optimal repetition coding can beat uncoded runtime when µ<1 but still has a Θ(log n) factor and is not order-optimal.
  • Optimal MDS coding minimizes average runtime through an optimized k⋆, and when µ>1 its runtime is only 3.15 away from the lower bound.
  • Coded matrix multiplication requires 1/k of the data at each worker instead of 1/n, giving storage overhead factor n/k−1, or 1/α⋆−1 at the runtime-optimal k⋆.

E. Coded Gradient Descent: An MDS-coded Distributed Algorithm for Linear Regression

Coded gradient descent applies MDS-coded matrix multiplication twice per iteration to compute linear-regression gradients while mitigating straggler delays, with a storage-overhead trade-off.

  • Coded gradient descent solves large-scale linear regression by applying coded matrix multiplication to two matrix-vector multiplications in each iteration.The two computations are Ax(t) and AT(Ax(t) − y).
  • The uncoded algorithm computes gradients through distributed partial sums but must wait for every worker result, so each update is governed by the slowest response.
  • MDS coding encodes A for the first multiplication and its transpose for the second, using separate (n, k1)- and (n, k2)-coded algorithms.
  • The coded gradient descent algorithm incurs additional storage overhead at each node, with relative overhead at least about factor 2 when k1 ≃ n and k2 ≃ n.

F. Experimental Results

Experiments on Amazon EC2 evaluate coded matrix multiplication and coded gradient descent against uncoded alternatives, measuring average and tail runtimes under observed worker variability.

  • Measured round-trip times averaged 0.11 second, while the 95th percentile latency reached 0.20 second, indicating substantial task-time variability.The round trip includes input transmission, computation, and output transmission.
  • The experiments implemented coded and uncoded algorithms with OpenMPI on Amazon EC2 clusters containing 25 workers for matrix multiplication and 10 workers for gradient descent.
  • Coded matrix multiplication reduced average runtime by about 40% and tail runtime by about 60% on unreliable m1-small instances versus the best uncoded algorithm.
  • On c1-medium instances, coded matrix multiplication achieved the best performance in most tested cases, reducing average runtime by at most 39.5% and 95th percentile runtime by at most 58.3%.
  • Coded gradient descent reduced average runtime by 31.3% to 35.7% and tail runtime by 27.9% to 35.6% compared with uncoded gradient descent.

IV. CODED SHUFFLING

The coded-shuffling section addresses communication bottlenecks by proposing a coded shuffling algorithm and analyzing its performance in distributed machine learning.

  • Coded shuffling is introduced to address communication bottlenecks rather than straggler delays.
  • The section presents the data-shuffling problem, proposes Coded Shuffling, and analyzes the algorithm’s performance.
  • The approach treats data shuffling as a core component of parallel machine-learning algorithms.

A. Setup and Notations

The setup partitions the full dataset among workers before each iteration, with worker caches constrained to support distributed storage without eliminating shuffling entirely.

  • Before each iteration, the master randomly partitions the dataset into n subsets and sends each subset to its corresponding worker.
  • Each worker has a cache of s data rows, and q/n ≤ s ensures the data matrix can be fully stored across the workers.
  • The setup assumes s ≤ q, because storing more than q rows at each worker would allow every worker to hold the full data matrix and remove shuffling.
  • Workers receive non-overlapping datasets of cardinality q/n, with sampling performed without replacement.

B. Shuffling Schemes

Coded shuffling combines cache updates with multicast transmissions so workers obtain their next iteration’s data while exploiting coded cache contents.

  • Transmission and decoding: The master uses separate uncoded and coded transmission strategies, with worker-side decoding designed to recover each worker’s missing data rows.The coded strategy transmits combinations indexed by subsets of workers rather than separate messages for every destination.
  • Cache update: Coded shuffling maintains each worker’s current data subset and updates its cache with current-iteration data plus randomly sampled previous contents.The update preserves required data while creating coding opportunities for the next iteration.
  • Uncoded transmission: The uncoded scheme transmits every required uncached data point separately to each worker, yielding a total communication rate based on n(1 − s/q).As q grows, each worker already caches approximately an s/q fraction of its newly assigned rows.
  • Coded transmission: The coded scheme groups cache-exclusive data across worker subsets and multicasts summed messages that workers decode using their stored rows.Shorter matrices are zero-padded before summation, and workers discard encoded rows that do not involve them.

C. Example

A three-worker example shows how coded multicast messages let a worker recover missing rows by subtracting rows it already stores.

  • Example setup: For n = 3, worker 1 needs rows assigned to it that are absent from its cache, including rows stored exclusively by workers 2 or 3.Missing rows may also be replicated across both other workers’ caches.
  • Coded message: The coded transmission includes a multicast sum combining rows needed by different workers from cache-exclusive subsets.One message combines three terms associated with the three-worker subset.
  • Decoding: Worker 1 decodes its missing rows by subtracting the other summands, which correspond to rows already stored at worker 1.The same subtraction principle recovers rows exclusive to worker 2, exclusive to worker 3, and shared by both.

D. Main Results

The main results characterize coded-shuffling communication rates and show substantial reductions when storage and multicast advantages are available.

  • Rate characterization: Coded shuffling achieves a communication rate characterized by Theorem 6 under the cache-update and coded-transmission construction.The derivation computes exclusive-cache probabilities and aggregates multicast transmissions over worker subsets.
  • Numerical illustration: For n = 50 and q = 1000, caching s/q = 0.1 reduces data-shuffling communication overhead by more than 81%.The figure varies the coded and uncoded achievable rates with cache fraction over 1/n ≤ s/q ≤ 1.
  • Special cache regime: A factor 2 reduction in communication rate occurs when cache size is exactly sufficient to store the data required for processing, s = q/n.In this regime, the coded rate satisfies Rc = 1/2 Ru.
  • Asymptotic regime: Θ(n) communication-rate reduction is obtained when s/q approaches a positive constant and n/q approaches zero.This is the asymptotic regime where each worker caches a constant fraction of the data matrix.
  • Multicast dependence: Coded shuffling is cheaper than uncoded shuffling when the multicast advantage satisfies γ(n) > q/s.With constant s/q and γ(n) scaling with n, the reduction gain remains unbounded and increases with n.
  • Experimental comparison: On an Amazon EC2 cluster, MPI scatter transmission time grows linearly with receivers, whereas MPI broadcast grows logarithmically.This supports the practical advantage of multicasting over unicasting in point-to-point networks.

V. CONCLUSION

The paper concludes that coding can mitigate stragglers and communication bottlenecks, while identifying open questions about broader algorithms, convergence, trade-offs, and fundamental limits.

  • Contributions: Coded Computation and Coded Shuffling target system noise from stragglers and communication bottlenecks, with experiments reporting speedups of up to 40%.The conclusion describes the schemes as robustifying distributed algorithms through coding redundancy and reduced shuffling cost.
  • Coded computation: For coded computation, open problems include alternative codes and extending coding beyond matrix multiplication to broader distributed algorithms.Matrix multiplication is identified as a basic computational block, but broader algorithmic coverage remains unresolved.
  • Coded shuffling: For coded shuffling, convergence under shuffling and the trade-offs among bandwidth, storage, and statistical efficiency are not well understood.The conclusion also questions how close the achievable bandwidth gain is to the fundamental communication-rate limit.
Loading 1512.02673v3…