short-paper

Speculation-aware Cluster Scheduling

Authors:

Xiaoqi Ren,

Ganesh Ananthanarayanan,

Adam Wierman,

Minlan YuAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 43, Issue 2

Pages 42 - 44

https://doi.org/10.1145/2825236.2825254

Published: 16 September 2015 Publication History

Get Access

Abstract

Stragglers are a crucial roadblock to achieving predictable performance in today's clusters. Speculation has been widelyadopted in order to mitigate the impact of stragglers; however speculation mechanisms are designed and operated independently of job scheduling when, in fact, scheduling a speculative copy of a task has a direct impact on the resources available for other jobs. In this work, based on a simple model and its analysis, we design Hopper, a job scheduler that is speculation-aware, i.e., that integrates the tradeoffs associated with speculation into job scheduling decisions.

References

[1]

Hadoop. http://hadoop.apache.org.

Google Scholar

[2]

G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica. Effective Straggler Mitigation: Attack of the Clones. In USENIX NSDI, 2013.

Digital Library

Google Scholar

[3]

G. Ananthanarayanan, A. Ghodsi, A. Wang, D. Borthakur, S. Kandula, S. Shenker, and I. Stoica. PACMan: Coordinated Memory Caching for Parallel Jobs. In USENIX NSDI, 2012.

Digital Library

Google Scholar

[4]

G. Ananthanarayanan, M. Hung, X. Ren, I. Stoica, A. Wierman, and M. Yu. GRASS: Trimming Stragglers in Approximation Analytics. In USENIX NSDI, 2014.

Digital Library

Google Scholar

[5]

G. Ananthanarayanan, S. Kandula, A. Greenberg, I. Stoica, E. Harris, and B. Saha. Reining in the Outliers in Map-Reduce Clusters Using Mantri. In USENIX OSDI, 2010.

Digital Library

Google Scholar

[6]

H. Chen, J. Marden, and A. Wierman. On the Impact of Heterogeneity and Back-end Scheduling in Load Balancing Designs. In INFOCOM. IEEE, 2009.

Crossref

Google Scholar

[7]

J. Dean and L. Barroso. The Tail at Scale. Communications of the ACM, (2), 2013.

Digital Library

Google Scholar

[8]

J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM, 2008.

Digital Library

Google Scholar

[9]

F. Dogar, T. Karagiannis, H. Ballani, and A. Rowstron. Decentralized Task-aware Scheduling for Data Center Networks. In Proceedings of the 2014 ACM conference on SIGCOMM, pages 431--442. ACM, 2014.

Digital Library

Google Scholar

[10]

O. K, P. Wendell, M. Zaharia, and I. Stoica. Sparrow: Distributed, Low Latency Scheduling. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 69--84. ACM, 2013.

Digital Library

Google Scholar

[11]

M. Lin, L. Zhang, A. Wierman, and J. Tan. Joint Optimization of Overlapping Phases in MapReduce. Performance Evaluation, 2013.

Digital Library

Google Scholar

[12]

M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. Franklin, S. Shenker, and I. Stoica. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. In USENIX NSDI, 2012.

Digital Library

Google Scholar

[13]

X. Ren, G. Ananthanarayanan, A. Wierman, and M. Yu. Hopper: Decentralized Speculation-aware Cluster Scheduling at Scale. ACM SIGCOMM, 2015.

Digital Library

Google Scholar

[14]

M. Zaharia, A. Konwinski, A. D. Joseph, R. Katz, and I. Stoica. Improving MapReduce Performance in Heterogeneous Environments. In USENIX OSDI, 2008.

Digital Library

Google Scholar

Cited By

View all

Qiu ZPérez JBirke RChen LHarrison P(2017)Cutting Latency Tail: Analyzing and Validating Replication without CancelingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.270626828:11(3128-3141)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1109/TPDS.2017.2706268
Xu HLau W(2017)Optimization for Speculative Execution in Big Data Processing ClustersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.256496228:2(530-545)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2564962

Speculation-aware Cluster Scheduling
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Optimal Scheduling of Aperiodic Jobs on Cluster
Euro-Par '01: Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing

This paper presents an algorithm to schedule aperiodic jobs on a cluster system. A cluster consists of one dispatcher and multiple schedulers. The algorithm is optimal for the response time of each aperiodic job. Aperiodic jobs are partitioned into ...
Optimal virtual cluster-based multiprocessor scheduling

Scheduling of constrained deadline sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have ...
Energy-Aware Task Scheduling of MapReduce Cluster
ICSS '15: Proceedings of the 2015 International Conference on Service Science

Energy consumption in data center is gradually exceeding other operating expenditures. It is imperative to enhance the energy efficiency of data center. In this paper, two heuristics on AIS (All-In Strategy) - TSA (Task Scheduling on AIS) and TSAGT (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 43, Issue 2

September 2015

79 pages

ISSN:0163-5999

DOI:10.1145/2825236

Editor:
Giuliano Casale
Imperial College London, London

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 September 2015

Published in SIGMETRICS Volume 43, Issue 2

Check for updates

Qualifiers

Short-paper

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
86
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Qiu ZPérez JBirke RChen LHarrison P(2017)Cutting Latency Tail: Analyzing and Validating Replication without CancelingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.270626828:11(3128-3141)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1109/TPDS.2017.2706268
Xu HLau W(2017)Optimization for Speculative Execution in Big Data Processing ClustersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.256496228:2(530-545)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2564962

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Optimal Scheduling of Aperiodic Jobs on Cluster

Optimal virtual cluster-based multiprocessor scheduling

Energy-Aware Task Scheduling of MapReduce Cluster