ComputingComputer EngineeringComputer ScienceCluster ComputingHeterogeneous ComputingParallel ComputingHardware AccelerationJob SchedulingResource SchedulingResource-constrained SchedulingTask SchedulingWorkload SchedulingAcceleratorsBipartite MatchingFair Resource AllocationGpu AcceleratorsLoadOnline Bipartite MatchingScheduling Under Resource ConstraintsScheduling With Heterogeneous Resources
Modern deep learning frameworks support a variety of hardware, including CPU, GPU, and other accelerators, to perform computation. In this paper, we study how to schedule jobs over such interchangeable resources - each with a different rate of computation - to optimize performance while providing fairness among users in a shared cluster. We demonstrate theoretically and empirically that existing solutions and their straightforward modifications perform poorly in the presence of interchangeable resources, which motivates the design and implementation of AlloX. At its core, AlloX transforms the scheduling problem into a min-cost bipartite matching problem and provides dynamic fair allocation over time. We theoretically prove its optimality in an ideal, offline setting and show empirically that it works well in the online scenario by incorporating with Kubernetes. Evaluations on a small-scale CPU-GPU hybrid cluster and large-scale simulations highlight that AlloX can reduce the average job completion time significantly (by up to 95% when the system load is high) while providing fairness and preventing starvation.
53
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
TensorFlow: a system for large-scale machine learning
Martı́n Abadi, Paul Barham, Jianmin Chen et al. · Operating Systems Design and Implementation · 2016 · 6.4K citations
In-Datacenter Performance Analysis of a Tensor Processing Unit
Norman P. Jouppi, Cliff Young, Nishant Patil et al. · 2017 · 4.4K citations
Vinod Kumar Vavilapalli, Arun C. Murthy, Chris Douglas et al. · 2013 · 1.8K citations