Large-Scale Machine Learning Cluster Scheduling via Multi-Agent Graph Reinforcement Learning

Xiaoyang Zhao, Chuan Wu

TL;DR

Scheduling thousands of deep learning jobs across massive GPU clusters is a logistical nightmare because jobs often "fight" over shared hardware like CPUs and PCIe buses. This paper introduces a decentralized scheduling framework that uses Multi-Agent Reinforcement Learning (MARL) and Graph Neural Networks (GNNs) to cooperatively place jobs, reducing interference and cutting average job completion times by over 20%.

What Problem Does This Paper Address?

In modern data centers, thousands of GPUs are shared among various deep learning (DL) tasks. Traditional schedulers usually focus on "bin-packing"—trying to fit as many tasks as possible onto the fewest servers to save resources. However, this ignores inter-job interference. Even if two jobs use different GPUs, they might compete for the same CPU cores or PCIe bandwidth, leading to significant performance slowdowns (up to 30% according to the authors' measurements).

Furthermore, as clusters grow to thousands of nodes, a single centralized scheduler becomes a bottleneck. It can't process job arrivals fast enough, and the "state space" (the mathematical representation of the cluster) becomes too complex for standard Reinforcement Learning (RL) algorithms to learn effectively.

Methods

The authors propose a hierarchical, multi-agent approach to break down the complexity:

  1. Multi-Agent Reinforcement Learning (MARL): Instead of one giant scheduler, the cluster is divided into partitions, each managed by its own RL agent. These agents communicate and cooperate, allowing the system to scale while making localized, fast decisions.
  2. Hierarchical Graph Neural Networks (GNNs): To help the agents understand the cluster's physical layout, the authors use GNNs.
  3. An Inner Graph encodes the architecture within a server (CPUs, GPUs, and PCIe switches).
  4. An Inter-Scheduler Graph encodes the network topology between partitions (switches and links).
  5. Interference Model: Since it's impossible to run every possible combination of jobs to see how they interfere during training, the authors built a specialized model. It predicts slowdowns based on CPU utilization and PCIe bus contention, providing realistic "rewards" to the RL agents during their offline training phase.
  6. Actor-Critic Training: The agents use an actor-critic algorithm (specifically looking at job progress as a reward) to learn placement policies that minimize the average Job Completion Time (JCT).

Datasets

  • Workload Traces: The researchers used publicly available Google cluster traces to simulate realistic job arrival patterns and resource demands.
  • DL Model Benchmarks: For training and interference profiling, they used eight representative DL models implemented in MXNet, including ResNet-50, VGG-16, and various NLP models like Seq2Seq and CTC.
  • Cluster Topologies: Evaluation was performed on simulated Fat-tree, VL2, and BCube network topologies to prove the scheduler's adaptability.

Key Insights and Ideas

  • The "Socket" Matters: The authors found that placing two jobs on the same server but on different CPU sockets (each with its own PCIe bus) significantly reduces interference compared to sharing a single socket. Their "device-level" GNN captures this nuance.
  • Decentralization is a Feature, Not a Bug: A single RL agent struggles to converge in a cluster of 2,000 servers. By using multiple agents that only "see" their neighborhood and aggregate summaries from others, the model learns faster and finds better policies.
  • Topology-Awareness: By encoding the network as a graph, the scheduler naturally learns to avoid congested links and place communication-heavy tasks (like those in a distributed training job) closer together.

Key Results

  • Performance Boost: In large-scale simulations (2,000 servers), the proposed framework outperformed industry-standard baselines (like Tetris and Load Balancing) by more than 20% in average Job Completion Time.
  • Faster Convergence: The multi-agent system reached an optimal policy in roughly 200 epochs, whereas a single-agent scheduler failed to reach the same performance even after 400 epochs.
  • Real-world Validation: A prototype deployed on a 48-GPU Kubernetes testbed on AWS EKS confirmed the simulation results, showing an 18.9% improvement over the default Kubernetes scheduler.

Limitations and Future Work

  • Offline Training: The RL agents require significant offline training using the interference model before they can be deployed. Adapting to a brand-new hardware architecture would require re-profiling and re-training.
  • No Preemption: The current model assumes that once a job is placed, it runs to completion. It does not account for "preemptive" scheduling, where a high-priority job might kick a lower-priority one off a server.
  • Static Resource Demands: The scheduler assumes job resource needs are known at arrival and stay constant, which may not always be true for complex, multi-stage ML pipelines.

Summary updated

Abstract

Efficient scheduling of distributed deep learning (DL) jobs in large GPU clusters is crucial for resource efficiency and job performance. While server sharing among jobs improves resource utilization, interference among co-located DL jobs occurs due to resource contention. Interference-aware job placement has been studied, with white-box approaches based on explicit interference modeling and black-box schedulers with reinforcement learning. In today’s clusters containing thousands of GPU servers, running a single scheduler to manage all arrival jobs in a timely and effective manner is challenging, due to the large workload scale. We adopt multiple schedulers in a large-scale cluster/data center, and propose a multi-agent reinforcement learning (MARL) scheduling framework to cooperatively learn fine-grained job placement policies, towards the objective of minimizing job completion time (JCT). To achieve topology-aware placements, our proposed framework uses hierarchical graph neural networks to encode the data center topology and server architecture. In view of a common lack of precise reward samples corresponding to different placements, a job interference model is further devised to predict interference levels in face of various co-locations, for training of the MARL schedulers. Testbed and trace-driven evaluations show that our scheduler framework outperforms representative scheduling schemes by more than 20% in terms of average JCT, and is adaptive to various machine learning cluster topologies.
BibTeX
@article{zhao2022large,
  author = {Xiaoyang Zhao and Chuan Wu},
  title = {{Large-Scale Machine Learning Cluster Scheduling via Multi-Agent Graph Reinforcement Learning}},
  journal = {IEEE Trans. Netw. Serv. Manag.},
  year = {2022},
  url = {https://openreview.net/forum?id=K4axphitRS},
}

Loading related content...

Figure