Coded computation over heterogeneous clusters
Coded computation over heterogeneous clusters
复制标题
DOI：
10.1109/isit.2017.8006961
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
Amirhossein Reisizadeh;Saurav Prakash;Ramtin Pedarsani;A. Avestimehr
中科院分区：
文献类型：
--
作者：
Amirhossein Reisizadeh;Saurav Prakash;Ramtin Pedarsani;A. Avestimehr
在大规模分布式计算簇（例如亚马逊EC2）中，有几种类型的“系统噪声”会导致性能的重大降级：系统故障，由于通信带宽有限，由于Straggler节点而导致的延迟，因此，瓶颈是瓶颈。另一方面，这些系统享有冗余的抽象 - 大量的计算节点和大量的存储容量。在本文中，我们专注于一般的异质分布计算群集，以减轻散乱者和通信瓶颈的效果。通过交易冗余，尤其是降低计算的延迟，我们提出了异源编码矩阵，具有散落的服务器的群集。乘法（HCMM）算法用于在异质簇上执行分布式矩阵乘法，但如果群集中的工人节点的数量是N，我们表明HCMM是θ（log n）的次数，而不是任何未脱皮的方案。我们进一步提供了数值结果，与“未编码”和“均匀编码”方案相比，HCMM的显着加速度高达49％和34％。
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: system failures, 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 with straggling servers 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. Moreover, if the number of worker nodes in the cluster is n, we show that HCMM is Θ(log n) times faster than any uncoded scheme. We further provide numerical results demonstrating significant speedups of up to 49% and 34% for HCMM in comparison to the “uncoded” and “homogeneous coded” schemes, respectively.