Tetrisched: Space-Time Scheduling for Heterogeneous DatacentersCarnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-13-112, December, 2013.
Alexey Tumanov, Timothy Zhu, Michael A. Kozuch†, Mor Harchol-Balter, Gregory R. Ganger
Carnegie Mellon University
Pittsburgh, PA 15213
† Intel Labs
Tetrisched is a new scheduler that explicitly considers both job-specific preferences and estimated job runtimes in its allocation of resources. Combined, this information allows tetrisched to provide higher overall value to complex application mixes consolidated on heterogeneous collections of machines. Job-specific preferences, provided by tenants in the form of composable utility functions, allow tetrisched to understand which resources are preferred, and by how much, over other acceptable options. Estimated job runtimes allow tetrisched to plan ahead in deciding whether to wait for a busy preferred resource to become free or to assign a less preferred resource. Tetrisched translates this information, which can be provided automatically by middleware (our wizard) that understands the right SLOs, runtime estimates, and budgets, into a MILP problem that it solves to maximize overall utility. Experiments with a variety of job type mixes, workload intensities, degrees of burstiness, preference strengths, and input inaccuracies show that tetrisched consistently provides significantly better schedules than alternative approaches.
FULL PAPER: pdf