Multi-resource packing for cluster schedulers

By Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, Aditya Akella. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2014

673 citations recorded by the source corpus.

Tasks in modern data parallel clusters have highly diverse resource requirements, along CPU, memory, disk and network. Any of these resources may become bottlenecks and hence, the likelihood of wasting resources due to fragmentation is now larger. Today's schedulers do not explicitly reduce fragmentation. Worse, since they only allocate cores and memory, the resources that they ignore (disk and network) can be over-allocated leading to interference, failures and hogging of cores or memory that could have been used by other tasks. We present Tetris, a cluster scheduler that packs, i.e., matches multi-resource task requirements with resource availabilities of machines so as to increase cluster efficiency (makespan). Further, Tetris uses an analog of shortest-running-time-first to trade-off cluster efficiency for speeding up individual jobs. Tetris' packing heuristics seamlessly work alongside a large class of fairness policies. Trace-driven simulations and deployment of our prototype on a 250 node cluster shows median gains of 30% in job completion time while achieving nearly perfect fairness.

Subfields: Computer Networks and Communications, Information Systems

View Paper: https://www.semanticscholar.org/paper/52a7abba94fd77b53400a7bae72444f35f6cc463

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

Citations in the corpus

Resource Management with Deep Reinforcement Learning (2016, methodology): “…a Packer agent which allocates jobs in increasing order of alignment between job demands and resource availability (same as the packing heuristic in [17]); and Tetris (cid:63) , an agent based on Tetris [17] which balances preferences for short jobs and resource packing in a combined score.”
Hopper: Decentralized Speculation-aware Cluster Scheduling at Scale (2015, background): “Their tasks have diverse resource demands of CPU, memory and IO, varying by a factor of 24× (refer to [27] for detailed quantification).”
Learning scheduling algorithms for data processing clusters (2018, methodology): “Packing tasks efficiently in multiple resource dimensions requires complex heuristics [18; 19].”
Themis: Fair and Efficient GPU Cluster Scheduling for Machine Learning Workloads (2019, background): “Tetris [9] proposes resource-aware packing with an option to trade-off for fairness uses multi-dimensional bin-packing as the mechanism for achieving that.”
Pond: CXL-Based Memory Pooling Systems for Cloud Platforms (2022, neutral): “Scheduling VMs thus leads to a multi-dimensional bin-packing problem [32, 44, 47] which is complicated by constraints such as spreading VMs across multiple failure domains.”
Live Video Analytics at Scale with Approximation and Delay-Tolerance (2017, background): “Cluster schedulers [3, 31, 39, 42, 44, 49, 86] do not cater to the performance objectives of streaming video analytics.”
Low Latency Geo-distributed Data Analytics (2015, background): “these systems optimize task placement, they do not consider network contentions (which matter less within a DC), and they do not move data around to relieve potential network bottlenecks [33].”
Learning to Perform Local Rewriting for Combinatorial Optimization (2018, background): “Various work have studied these problems from both theoretical and empirical sides [8, 20, 3, 42, 48, 33, 13].”
Autopilot: workload autoscaling at Google (2020, background): “The desired number of replicas and their resource requirements are expected to be provided by users in many cloud resource management systems, as the scheduler uses them to pack tasks to machines [14].”
Large-scale cluster management at Google with Borg (2015, methodology): “In addition, several research groups have proto-typed systems that improve the quality of scheduling decisions in certain ways (e.g., [25, 40, 72, 74]).”
Balancing efficiency and fairness in heterogeneous GPU clusters for deep learning (2020, background): “Faircloud [34] considers the problem of sharing network while Tetris [17] schedules based on multiple resource requirements such as CPU, memory, disk and network.”
Optimus: an efficient dynamic resource scheduler for deep learning clusters (2018, background): “(ii) Tetris [37], which preferentially allocates resources to jobs with low duration or small resource consumption and packs jobs to servers to minimize resource fragmentation.”
Reinforcement Learning for Primary care e Appointment Scheduling (2017, background): “The system is complex and often impossible to model accurately [2], [3]; 2.”