Graph

Scheduling (production processes)

Processor scheduling

Mathematics

Schedule

Operating system

Algorithm

Distributed computing

Statistics

Mathematical optimization

Job scheduler

Variety (cybernetics)

Parallel computing

Artificial intelligence

Bipartite graph

Matching (statistics)

Computer science

Computation

Multi-core processor

Cloud computing

Theoretical computer science

GPU cluster

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.

AlloX