EUVIMEDEUVIMED entdecken
Crossref

Efficient Straggler Replication in Large-Scale Parallel Computing

Da Wang, Gauri Joshi, Gregory W. Wornell

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →