Slack Squeeze Coded Computing for Adaptive Straggler Mitigation

Authors: Krishna Giri Narra (University of Southern California), Zhifeng Lin (University of Southern California), Mehrdad Kiamari (University of Southern California), Salman Avestimehr (University of Southern California), Murali Annavaram (University of Southern California)

Abstract: While performing distributed computations in today's cloud-based platforms, execution speed variations among compute nodes can significantly reduce the performance and create bottlenecks like stragglers. Coded computation techniques leverage coding theory to inject computational redundancy and mitigate stragglers in distributed computations. In this paper, we propose a scheduling strategy for coded computation called SlackSqueeze Coded Computation (S2C2). S2C2 squeezes the compute slack (i.e., overhead) that is built into the coded computing frameworks by efficiently assigning work for all fast and slow nodes according to their speeds and without needing to re-distribute data. We implement an LSTM-based speed prediction algorithm to predict speeds of compute nodes. We evaluate S2C2 on linear algebraic algorithms, gradient descent, graph ranking, and graph filtering algorithms. We demonstrate a 19% to 39% reduction in total computation latency using S2C2 compared to job replication and coded computation. We further show how S2C2 can be applied beyond matrix-vector multiplication.


Presentation: file


Back to Technical Papers Archive Listing