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.

本文提出了一种编码框架（HCMM）以提高异构分布式计算的速度，并展示了在 Amazon EC2 上进行分布式矩阵乘法实验的结果。该方法比三种基准负载分配方案的速度分别快 61％，46％和 36％。同时，我们还提供了在异构设置中的最优负载分配问题的一般化解决方案，并开发了一个启发式算法（HCMM）负载分配问题。