Cloud Scheduling (TetriSched)

Datacenters increasingly use a heterogeneous collection of machines with different capabilities (e.g., memory capacity, GPU accelerator) to execute a heterogeneous collection of workloads (e.g., long-running services, batch data analytics, interactive development/test). To maximize resource efficiency and utilization, the machines are often aggregated into a resource pool where workloads are consolidated. A cluster scheduler is then tasked with assigning resources to workloads.

The challenge is to assign the right resources to each. One job might be concerned about completion time and run fastest on a machine with a GPU. Another job might be concerned with long-term availability, which is enhanced by running its constituent processes (tasks) on machines attached to separate power distribution units. When machines are homogeneous, such concerns can often be ignored as all choices are equal. When workloads are homogeneous, understanding of their concerns can be hard-coded into the scheduler. But, neither workloads nor resources are homogeneous in modern datacenters.

To maximize the benefits of resource consolidation, consumers must somehow communicate their specific needs/concerns so that the scheduler can make informed decisions. A scheduler that understands the quantitative tradeoffs involved with the constraints set by each job should be able to make better decisions. By translating each workload's distinct concerns (e.g., availabilities, runtimes, response times) to a common metric called utility, tradeoffs between them can be quantified, where higher utility is better. As should be expected, the more information about significant needs/concerns that can be used by the scheduler, the higher the utility.

The TetriSched project introduces a scheduler that accepts resource requests in the form of utility functions. These utility functions use an algebraic language to describe the utility associated with one or more spatial (which machines) and temporal outcome, quantifying the relative value of each acceptable allocation. TetriSched translates the collection of utility functions into a Mixed Integer Linear Program (MILP) problem and solves it to plan a schedule that optimizes overall utility.

Tetrisched fills the constraint handling gap. Most schedulers take an all-or-nothing approach, either treating all constraints as strict requirements or completely ignoring them. Tetrisched recognizes that tradeoffs are inherent in user preferences, providing a flexible constraint scheme that encodes resource preferences and their relative utility.

People

FACULTY

Greg Ganger
Mor Harchol-Balter

GRAD STUDENTS

Angela Jiang
Junwoo Park
Alexey Tumanov
Timothy Zhu

INDUSTRY COLLABORATORS

Michael A. Kozuch, Intel

Publications

• 3Sigma: Distribution-based Cluster Scheduling for Runtime Uncertainty. Jun Woo Park, Alexey Tumanov, Angela Jiang, Michael A. Kozuch, Gregory R. Ganger. EuroSys ’18, April 23–26, 2018, Porto, Portugal. Supersedes CMU-PDL-17-107, Nov. 2017.
  Abstract / PDF [1.4M]
  
  
• 3Sigma: Distribution-based cluster scheduling for runtime uncertainty. Jun Woo Park, Alexey Tumanov, Angela Jiang, Michael A. Kozuch, Gregory R. Ganger. Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-17-107, November 2017.
  Abstract / PDF [800K]
  
  
• JamaisVu: Robust Scheduling with Auto-Estimated Job Runtimes. Alexey Tumanov, Angela Jiang, Jun Woo Park, Michael A. Kozuch, Gregory R. Ganger. Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-16-104. September 2016.
  Abstract / PDF [1.6M]
  
  
• TetriSched: Global Rescheduling with Adaptive Plan-ahead in Dynamic Heterogeneous Clusters. Alexey Tumanov, Timothy Zhu, Jun Woo Park, Michael A. Kozuch, Mor Harchol-Balter, Gregory R. Ganger. ACM European Conference on Computer Systems, 2016 (EuroSys'16), 18th-21st April, 2016, London, UK.
  Abstract / PDF [8M]
  
  
• TetriSched: Space-Time Scheduling for Heterogeneous Datacenters. Alexey Tumanov, Timothy Zhu, Michael A. Kozuch†, Mor Harchol-Balter, Gregory R. Ganger. Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-13-112, December, 2013.
  Abstract / PDF [716K]
  
  
• alsched: Algebraic Scheduling of Mixed Workloads in Heterogeneous Clouds. Alexey Tumanov, James Cipar, Michael A. Kozuch, Gregory R. Ganger. 3rd ACM Symposium on Cloud Computing. October 14th-17th, 2012 - San Jose, CA.
  Abstract / PDF [379K]
  
  
• Heterogeneity and Dynamicity of Clouds at Scale: Google Trace Analysis. Charles Reiss, Alexey Tumanov, Gregory R. Ganger, Randy H. Katz, Michael A. Kozuch. 3rd ACM Symposium on Cloud Computing. October 14th-17th, 2012 - San Jose, CA.
  Abstract / PDF [3.1M]
  
  
• Towards Understanding Heterogeneous Clouds at Scale: Google Trace Analysis Charles Reiss, Alexey Tumanov, Gregory R. Ganger, Randy H. Katz, Michael A. Kozuch. Intel Science and Technology Center for Cloud Computing Technical Report ISTC-CC-TR-12-101, April 27, 2012.
  Abstract / PDF [876K]

 

Acknowledgements

We thank the members and companies of the PDL Consortium: Amazon, Datadog, Google, Honda, Intel Corporation, IBM, Jane Street, Meta, Microsoft Research, Oracle Corporation, Pure Storage, Salesforce, Samsung Semiconductor Inc., Two Sigma, and Western Digital for their interest, insights, feedback, and support.