Efficient Straggler Replication in Large-Scale Parallel Computing
ACM Transactions on Modeling and Performance Evaluation of Computing Systems · 30.06.2019 · 4 (2) · 1-23
DOI: 10.1145/3310336 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Modeling and Performance Evaluation of Computing Systems, online erschienen am 23.04.2019. Verfasst von Da Wang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 32-mal zitiert (Crossref) und nennt 43 Literaturangaben. Gefördert von: Schlumberger Foundation, National Science Foundation, Air Force Office of Scientific Research.
Abstract (Originalsprache)
In a cloud computing job with many parallel tasks, the tasks on the slowest machines (straggling tasks) become the bottleneck in the job completion. Computing frameworks such as MapReduce and Spark tackle this by replicating the straggling tasks and waiting for any one copy to finish. Despite being adopted in practice, there is little analysis of how replication affects the latency and the cost of additional computing resources. In this article, we provide a framework to analyze this latency-cost tradeoff and find the best replication strategy by answering design questions, such as (1) when to replicate straggling tasks, (2) how many replicas to launch, and (3) whether to kill the original copy or not. Our analysis reveals that for certain execution time distributions, a small amount of task replication can drastically reduce both latency and the cost of computing resources. We also propose an algorithm to estimate the latency and cost based on the empirical distribution of task execution time. Evaluations using samples in the Google Cluster Trace suggest further latency and cost reduction compared to the existing replication strategy used in MapReduce.
Förderung
- Schlumberger Foundation
- National Science Foundation
- Air Force Office of Scientific Research
Zitieren
APA
Wang, D., Joshi, G., & Wornell, G. W. (2019). Efficient Straggler Replication in Large-Scale Parallel Computing. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 4(2), 1-23. https://doi.org/10.1145/3310336
Vancouver
Wang D, Joshi G, Wornell GW. Efficient Straggler Replication in Large-Scale Parallel Computing. ACM Transactions on Modeling and Performance Evaluation of Computing Systems. 2019;4(2):1-23. doi:10.1145/3310336
BibTeX
@article{Wang2019,
author = {Wang, Da and Joshi, Gauri and Wornell, Gregory W.},
title = {Efficient Straggler Replication in Large-Scale Parallel Computing},
journal = {ACM Transactions on Modeling and Performance Evaluation of Computing Systems},
year = {2019},
volume = {4},
number = {2},
pages = {1--23},
doi = {10.1145/3310336}
}
EUVIMED