Paper
:
Slack Squeeze Coded Computing for Adaptive Straggler Mitigation
Event Type
Paper
Registration Categories
TP
Tags
Algorithms
Clouds and Distributed Computing
Machine Learning
Performance
Resiliency
Scheduling
Award Finalists
BP Finalist
BSP Finalist
TimeTuesday, 19 November 20192:30pm - 3pm
Location405-406-407
DescriptionWhile 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.
Archive
Back To Top Button