Coded computation over heterogeneous clusters

By Amirhossein Reisizadeh, Saurav Prakash, Ramtin Pedarsani, Amir Salman Avestimehr. 2017

246 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, background): “• Quantized Decentralized SGD (Q-DSGD) (Reisizadeh et al., 2019a): Iterates are updated according to (8).”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, background): “, 2016), more recent work has employed coding theory to speed up distributed machine learning systems (Lee et al., 2017; Li et al., 2015; Dutta et al., 2016; 2017; Reisizadeh et al., 2017; Yang et al., 2017).”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): ““Coded Computing” is now an emerging area of research ( [1], [2], [19], [21]–[54]) which advances on coding approaches in classical works on Algorithm-Based Fault Tolerance (ABFT), and also provides novel analyses of required computation time ( [2], [23], [44], [47]), including that in our prelimina”
Near-Optimal Straggler Mitigation for Distributed Gradient Methods (2017, methodology): “For the above optimization problem P2, an algorithm is developed in [23] for distributed matrix multiplication on heterogeneous clusters.”
Joint Device Scheduling and Resource Allocation for Latency Constrained Wireless Federated Learning (2020, background): “5 ms/sample and further set µ = 1 a for the computation latency model [34].”
Coded Computing for Federated Learning at the Edge (2020, background): “Related Works: Coded computing is a new paradigm that has been developed for injecting computation redundancy in unorthodox encoded forms to efficiently deal with communication bottleneck and system disturbances like stragglers, outages, node failures, and adversarial computations in distributed sys”
Approximate Gradient Coding via Sparse Random Graphs (2017, background): “Then, [21] propose another coding-theoretic algorithm for speeding up distributed matrix multiplication in heterogeneous clusters.”
Coded Computation Over Heterogeneous Clusters (2019, background): “This paper was presented at the 2017 IEEE International Symposium on Information Theory [1].”
Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning (2018, methodology): “s the straggler problem is based on coding-theoryinspired techniques Tandon et al. (2017); Lee et al. (2016); Dutta et al. (2016); Karakus et al. (2017a,b); Yang et al. (2017); Halbawi et al. (2017); Reisizadeh et al. (2017). Some of these works focus exclusively on coding for distributed linear ope”