PaperlayerView exact revision on arXiv

Source-linked AI summary

Coded Computation over Heterogeneous Clusters

Amirhossein Reisizadeh, Saurav Prakash, Ramtin Pedarsani, Amir Salman Avestimehr

arXiv:1701.05973v5cs.DCcs.IT

TL;DR

Distributed computing clusters have abundant resources but suffer performance degradation from system noise, while heterogeneous machine capabilities make load allocation difficult. The paper proposes HCMM, a coded matrix multiplication framework based on tractable expected-return optimization, and establishes asymptotic optimality across shifted exponential and Weibull runtime models. It also extends the allocation problem to monetary budget constraints and develops a heuristic for budget-limited tasks.

  • Problem

    System noise degrades distributed computing, and heterogeneous machine capabilities make exact optimal load allocation difficult.

  • Method

    HCMM uses coded matrix multiplication and a tractable optimization that maximizes expected returned results to allocate computation loads across heterogeneous workers.

  • Results

    HCMM is asymptotically optimal for shifted exponential and shifted Weibull runtimes and provides unbounded gains over uncoded scenarios.

  • Takeaways & Limitations

    HCMM combines load balancing with reduced redundant computation and extends asymptotically optimal allocation to feasible budget-constrained scenarios.

Abstract

from arXiv · show

In large-scale distributed computing clusters, such as Amazon EC2, there are several types of "system noise" that can result in major degradation of performance: bottlenecks due to limited communication bandwidth, latency due to straggler nodes, etc. On the other hand, these systems enjoy abundance of redundancy - a vast number of computing nodes and large storage capacity. There have been recent results that demonstrate the impact of coding for efficient utilization of computation and storage redundancy to alleviate the effect of stragglers and communication bottlenecks in homogeneous clusters. In this paper, we focus on general heterogeneous distributed computing clusters consisting of a variety of computing machines with different capabilities. We propose a coding framework for speeding up distributed computing in heterogeneous clusters by trading redundancy for reducing the latency of computation. In particular, we propose Heterogeneous Coded Matrix Multiplication (HCMM) algorithm for performing distributed matrix multiplication over heterogeneous clusters that is provably asymptotically optimal for a broad class of processing time distributions. Moreover, we show that HCMM is unboundedly faster than any uncoded scheme. To demonstrate practicality of HCMM, we carry out experiments over Amazon EC2 clusters where HCMM is found to be up to $61\%$, $46\%$ and $36\%$ respectively faster than three benchmark load allocation schemes - Uniform Uncoded, Load-balanced Uncoded, and Uniform Coded. Additionally, we provide a generalization to the problem of optimal load allocation in heterogeneous settings, where we take into account the monetary costs associated with the clusters. We argue that HCMM is asymptotically optimal for budget-constrained scenarios as well, and we develop a heuristic algorithm for (HCMM) load allocation for budget-limited computation tasks.

I. INTRODUCTION

The paper develops coded computation for heterogeneous clusters, where system noise and differing machine capabilities complicate distributed matrix multiplication. HCMM uses coding and load allocation to achieve asymptotically optimal performance, unbounded gains over uncoded schemes, and budget-aware allocation.

  • Motivation: Heterogeneous cloud clusters face system failures, limited communication bandwidth, and straggler nodes despite abundant storage and computing resources.
  • Problem and approach: HCMM extends coded distributed matrix multiplication from homogeneous to heterogeneous clusters containing machines with different capabilities.Matrix multiplication supports applications including logistic regression, reinforcement learning, and gradient descent.
  • Problem and approach: HCMM is derived from a tractable optimization maximizing expected returned computation results and asymptotically approximates optimal load allocation.The exact heterogeneous optimization is described as intractable.
  • Main results: HCMM is Θ(log n) times faster than uncoded schemes under shifted exponential runtimes and provides similar unbounded gains under shifted Weibull runtimes.
  • Main results: HCMM achieves numerical speedups of up to 73%, 56%, and 42% over Uniform Uncoded, Load-balanced Uncoded, and Uniform Coded schemes, respectively.The paper also reports Amazon EC2 experiments comparing these three benchmark schemes.
  • Budget-constrained allocation: Under budget constraints, HCMM is asymptotically optimal and a heuristic searches for suboptimal load-machine assignments satisfying a predefined budget.The heuristic reduces average cost by decreasing the number of fastest participating machines.

B. Network Model

The paper models distributed matrix-vector multiplication in a master-worker cluster where workers return coded or uncoded inner products, and the master reconstructs Ax after receiving enough results. It formulates heterogeneous load allocation under worker runtime distributions and establishes HCMM's asymptotic and empirical advantages over benchmark schemes.

  • B. Network Model: Workers compute assigned inner products and unicast results to the master, which recovers Ax after receiving a decodable set of at least r results.The setup supports coded computation by allowing recovery from returned coded rows.
  • B. Network Model: Worker runtimes are modeled as mutually independent shifted exponential variables and later generalized to shifted Weibull variables.The shifted exponential model includes deterministic shift and stochastic straggling terms, with parameters scaling with worker load.
  • B. Network Model: The optimization seeks a load allocation minimizing average time to receive a decodable set of at least r inner products.Equal loads are not generally optimal in heterogeneous clusters, while directly solving the allocation problem is hard.
  • D. Main Results: HCMM asymptotically solves the heterogeneous load-allocation problem and is Θ(log n) times faster than uncoded schemes under shifted exponential runtimes.The paper also proves unbounded gains over uncoded schemes under shifted Weibull runtimes.
  • D. Main Results: 73%, 56% and 42% are the reported maximum numerical speedups over Uniform Uncoded, Load-balanced Uncoded and Uniform Coded, respectively.Amazon EC2 experiments use LT codes to evaluate the coded implementation.

III. THE PROPOSED HCMM SCHEME AND PROOFS OF THEOREMS 1 AND 2

HCMM replaces the hard direct load-allocation optimization with a tractable two-step formulation that maximizes expected aggregate return at a fixed time and then selects a completion time. The resulting worker loads are derived from runtime parameters and implemented after rounding.

  • A. Alternative Formulation of Pmain via Maximal Aggregate Return: The paper reformulates the hard allocation problem by maximizing aggregate return for a fixed feasible time and then finding the smallest time with sufficient return.This alternative formulation is intended to be efficiently solvable and asymptotically approximate the original problem.
  • A. Alternative Formulation of Pmain via Maximal Aggregate Return: At time t, worker i returns its assigned load ℓi if Ti≤t, so the master’s aggregate return is the sum of these completed contributions.The indicator 1{Ti≤t} captures whether worker i has finished by time t.
  • A. Alternative Formulation of Pmain via Maximal Aggregate Return: HCMM assigns loads from the alternative formulation’s solution at t*, producing the algorithm’s worker-specific computation allocation.Algorithm 1 takes worker computation-time parameters as input and outputs the load assigned to each worker.
  • A. Alternative Formulation of Pmain via Maximal Aggregate Return: The fixed-time optimization decomposes into n independent worker-level problems because there is no constraint coupling load allocations.The resulting optimality condition determines each worker’s load as a function of t and runtime parameters.
  • A. Alternative Formulation of Pmain via Maximal Aggregate Return: The analytical load allocation may be real-valued, so practical implementations round worker loads before experiments.The paper states that loads are often large enough for rounding effects to be insignificant.
  • A. Alternative Formulation of Pmain via Maximal Aggregate Return: The auxiliary time τ* is defined as the point where the optimized allocation produces exactly r returned inner products on average and converges to t* for large n.This approximation supports the asymptotic analysis of the HCMM construction.

C. Asymptotic Optimality of HCMM

The proof section establishes HCMM’s asymptotic optimality by comparing its completion time with the optimum allocation’s completion time under the shifted exponential model.

  • C. Asymptotic Optimality of HCMM: HCMM’s expected completion time converges to the optimum expected completion time as the number of workers grows.The proof concludes limn→∞E[THCMM] = limn→∞E[TOPT].
  • C. Asymptotic Optimality of HCMM: The proof defines THCMM as the time to receive at least r inner products under HCMM and Tmax as the finish time of all workers.These variables support the comparison between HCMM’s stopping time and the full worker-completion time.

+ E[THCMM|E1

The proof bounds HCMM’s completion-time decomposition using event conditioning, aggregate-return monotonicity, and bounds on the maximum worker finish time.

  • + E[THCMM|E1: HCMM has received r inner products by THCMM, and aggregate return is increasing in time.This monotonicity supports the proof of the required return threshold.
  • + E[THCMM|E1: The analysis bounds Tmax using the maximum of worker runtimes and extends the argument from shifted exponential to shifted Weibull models.The proof uses stochastic upper bounds and concentration inequalities for separate terms.
  • + E[THCMM|E1: HCMM’s aggregate-return maximization supplies the comparison needed to establish the remaining inequality in the optimality proof.The proof invokes the fact that HCMM maximizes expected aggregate return for every feasible time.
  • + E[THCMM|E1: The proof concludes that HCMM and the optimum have equal limiting expected completion times.This yields the claimed asymptotic optimality.

D. Comparison with Uncoded Schemes

The comparison shows that HCMM achieves an orderwise speedup over uncoded schemes in heterogeneous clusters, including optimally load-balanced uncoded schemes.

  • In an uncoded scheme, redundancy is one, so the master waits for every worker before completing the computation.
  • The lower bound for uncoded performance is obtained by comparing heterogeneous machines with suitably faster or slower homogeneous replacements.
  • The uncoded completion time is determined by the maximum execution time across all worker nodes.
  • HCMM outperforms the best uncoded scheme by a factor of Θ(log n) under the shifted exponential run-time distribution.The comparison includes the optimal uncoded load allocation.

IV. GENERALIZATION TO THE SHIFTED WEIBULL MODEL AND PROOFS OF THEOREMS 3 AND 4

The analysis extends HCMM from shifted exponential to shifted Weibull worker run-times, proving asymptotic optimality and unbounded gains over uncoded schemes under constant parameters.

  • HCMM generalizes to shifted Weibull run-times, a broader class that includes shifted exponential distributions as the special case α_i = 1.
  • The optimal load allocation under the Weibull alternative formulation is obtained by solving an equation for each worker-specific parameter λ_i.
  • Under constant Weibull parameters and r = Θ(n), HCMM is asymptotically optimal.The theorem states that its expected execution time converges to the optimum.
  • HCMM has asymptotically constant expected execution time under the shifted Weibull model.
  • HCMM outperforms the best uncoded scheme by an unbounded factor under Weibull worker run-times.The comparison uses extreme-value behavior of uncoded completion times.

V. NUMERICAL STUDIES AND EXPERIMENTS USING AMAZON EC2 MACHINES

The paper evaluates HCMM through simulations and Amazon EC2 experiments against state-of-the-art load allocation schemes to measure practical speedups.

  • The evaluation combines numerical simulations with experiments on Amazon EC2 clusters.
  • HCMM is compared with state-of-the-art load allocation schemes to assess significant speedups.
  • The experiments are designed to demonstrate HCMM’s performance in practical heterogeneous computing settings.

A. Numerical Analysis

Numerical studies compare HCMM with three uncoded or coded baselines under shifted exponential and shifted Weibull models across heterogeneous worker scenarios. HCMM achieves the largest speedups while using less coding redundancy than Uniform Coded.

  • Numerical results: HCMM achieves speedups of up to 71%, 53%, and 39% over Uniform Uncoded, Load-balanced Uncoded, and Uniform Coded under shifted exponential run-times.
  • Numerical results: HCMM achieves gains of up to 73%, 56%, and 42% over Uniform Uncoded, Load-balanced Uncoded, and Uniform Coded under shifted Weibull run-times.
  • Coding redundancy: Under shifted exponential simulations, coding redundancy ranges from 1.41–1.46 for HCMM and 2.3–2.8 for Uniform Coded.
  • Coding redundancy: Under shifted Weibull simulations, coding redundancy ranges from 1.30–1.42 for HCMM and 2.0–2.5 for Uniform Coded.
  • Baseline schemes: Load-balanced Uncoded improves on Uniform Uncoded by assigning larger loads to faster machines, while Uniform Coded benefits from repeated computations.
  • Baseline schemes: HCMM combines efficient load balancing with a minimal number of redundant computations and provides the best expected execution time among the four schemes.

B. Experiments using Amazon EC2 machines

The Amazon EC2 experiments evaluate HCMM across three heterogeneous-cluster scenarios using LT codes, artificial straggler delays, and benchmark load-allocation schemes. HCMM fits the shifted exponential runtime model and achieves substantial execution-time gains with lower computation load than Uniform Coded.

  • Experimental setup: HCMM uses LT codes with peeling decoding, while Load-balanced Uncoded assigns rows proportional to workers' virtual CPU counts.The uncoded loads are normalized to sum to r, and LT decoding has nearly linear complexity.
  • Resource use: HCMM's total computation load is approximately 1.4, compared with 2.12–2.26 for Uniform Coded, yielding the best overall execution time with minimal coding overhead.The reported load comparison is for the three scenarios.
  • Experimental setup: The experiments cover three heterogeneous clusters with 11 or 16 machines and row sizes of 500000 or 1000000 elements.Scenario 1 uses 11 machines; Scenarios 2 and 3 use 16 machines, with Scenario 3 doubling the row size relative to Scenario 2.
  • Runtime model: The shifted exponential model provides a good first-order fit for worker runtimes in the EC2 experiments.Figure 5 reports empirical cumulative distribution functions for two Scenario 3 instances measured without manual delay.
  • Experimental results: 61%, 46%, and 36% are HCMM's maximum overall-execution-time gains over Uniform Uncoded, Load-balanced Uncoded, and Uniform Coded, respectively.These comparisons include decoding time and use LT codes with HCMM.

VI. GENERALIZATION TO COMPUTING SCENARIOS UNDER BUDGET CONSTRAINTS

The paper extends HCMM to load allocation with monetary constraints, modeling machine costs and identifying feasible allocations through asymptotic analysis. It also proposes a linear-search heuristic that removes faster machines until the budget is satisfied.

  • Problem formulation: The constrained objective minimizes expected runtime while satisfying a monetary budget for the computation.Machine costs are represented by a per-time-unit cost, with c = κµ^γ and γ ≥ 1.
  • Budget-constrained optimization: HCMM is asymptotically optimal for feasible budget-constrained load allocation and determines whether the computation task can satisfy the budget.Feasibility requires the available budget C to meet the minimum induced cost Cmin.
  • Cost structure: Using fewer fastest machines lowers expected cost, whereas using fewer slowest machines raises expected cost.The minimum cost uses only slowest machines, while the maximum cost uses only fastest machines.
  • Heuristic search: The heuristic starts with all available machines and repeatedly removes the fastest remaining machines until the HCMM allocation meets the budget.It returns the first feasible tuple and searches O(N) allocations instead of O(N1 ··· NK) exhaustive combinations.
  • Numerical examples: With C = 860, the heuristic reaches (n1, n2) = (10, 2) after 9 iterations, with expected cost 808.9 and average execution time E[THCMM] = 11.23.The scenario has two machine types and satisfies C ≥ Cmin = 629.2.
  • Numerical examples: With C = 475, the heuristic reaches (n1, n2, n3) = (10, 6, 0) after 15 iterations in the three-machine-type example.The example has Cmin = 314.6 and Cmax = 2516.8.

VII. CONCLUSION

The paper develops a coding framework for distributed matrix-vector multiplication in heterogeneous cloud environments and derives an asymptotically optimal HCMM load allocation. Amazon EC2 experiments show that HCMM with LT codes and peeling decoders significantly reduces average overall execution time.

  • The framework targets distributed matrix-vector multiplication in heterogeneous cloud computing environments.
  • HCMM is obtained from a tractable alternative to minimizing average runtime over all load allocations and is proved asymptotically optimal.
  • Amazon EC2 experiments compare HCMM with three benchmark load allocation schemes using numerical and experimental results.
  • HCMM combined with LT codes and peeling decoders provides significant gains in average overall execution time.

. From McDiarmid’s inequality, we have

The supplied passages state asymptotic parameter scalings used in a proof and a contradiction argument based on the number of equations available at the master node. The remaining passages provide author biographies and research backgrounds.

  • The proof uses r = Θ(n), s = Θ(n), λ_i = Θ(1), δ_i = Θ(n), and s^2 = Θ(n^2).
  • If t* < τ*, a positive probability of fewer than r equations at the master node by t* yields a contradiction.
  • The supplied passages also identify the paper’s authors and describe their education, positions, research interests, fellowships, and awards.
Loading 1701.05973v5…