Two-Layer Evolutionary Scheduling for Machine Learning Jobs in Multi-Cluster Environments
Authors: Jingyuan Xu, Changwu Huang, Lemeng Pan, Ke Tang, Xin Yao
Organizations: Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation, Department of Computer Science and Engineering of Southern University of Science and Technology, Shenzhen, China. · School of AI and Liberal Arts, Beijing Normal-Hong Kong Baptist University, Zhuhai, China. · Huawei Technologies Company, Ltd., Shenzhen, China. · School of Data Science, Lingnan University, Hong Kong SAR, China.
The rapid growth of large-scale machine learning (ML) workloads has led to unprecedented demands on GPU cluster scheduling systems. However, existing heuristic schedulers struggle to handle the complexity and dynamics of multi-cluster GPU environments, often leading to load imbalance, long queuing delays, and poor alignment to business objectives. This paper formulates the ML scheduling problem in multi-cluster GPU environments as online multi-objective optimization that minimizes the average and maximum weighted queuing times while maximizing GPU time utilization. To solve this optimization problem, we propose EVO-GP, a two-layer evolutionary online scheduling method that decouples global job-to-cluster allocation from intra-cluster GPU resource allocation. At the job-to-cluster allocation layer, an evolutionary algorithm assigns arriving jobs to feasible clusters to promote load balance across clusters. At the resource allocation layer, a priority function automatically learned offline via genetic programming is used to rank jobs and guide GPU allocation within each cluster. Extensive experiments on both real-world data and simulated workloads demonstrate that the proposed EVO-GP method consistently outperforms state-of-the-art baselines, while maintaining superior adaptability and scalability.
Figures & tables
Fig. 1: Overall illustration of EVO-GP.
Fig. 2: An example of an individual encoding and its corresponding scheduling.
Terminal Set
Description
dj(t)
The remaining duration of job j .
qj(t)
The length of time that job j has been queued.
uj
The priority defined by the user for job j .
gj
The total number of GPUs required by job j .
Function Set
+,−,×,% (protected division)
TABLE I: Function and Terminal sets of GP
Fig. 3: A training subset is constructed within each generation for fitness evaluation.
Worker Num
GPU Num
Avg. Training Hours
Weight
1
1
1.499136
2.44 × 10 -1
1
2
0.906435
1.23 × 10 -1
1
4
1.050502
8.20 × 10 -2
1
8
3.285060
4.29 × 10 -1
2
2
1.701724
3.00 × 10 -2
2
4
1.348965
1.00 × 10 -3
TABLE II: Types of Machine Learning Jobs and Their Characteristics
Fig. 4: Ranking of scheduling algorithms under the scalarized multi-objective metric on 30 test instances
Fig. 5: Job Queuing Time Distributions under GP-Learned and Tiresias Priority Functions.
Fig. 6: Different objective values of each algorithm on a representative test instance.
Fig. 7: Results of AvgJCT (Average Job Completion Time) and MaxQT (Maximum Queuing Time) from various algorithms.
Fig. 8: AvgJCT and MaxQT of the proposed EVO-GP under different values of ω .
Fig. 9: Impact of load pressure on different algorithms.
Fig. 10: Example of the learned priority function by GP with workload simulator.
Online resource allocation studies how to assign scarce capacity to arriving requests under uncertainty while balancing reward, cost, fairness, and feasibility.
GPU clusters have become essential computing resources for AI and scientific research in academia and industry. However, their high cost and growing demand often result in long queueing delays. While previous monitoring efforts have operated at second- or minute-level frequencies, they primarily informed job-level scheduling for clusters and lacked the detail needed to optimize GPU-level utilization. This paper presents an in-depth study of a university research GPU cluster, analyzing resource usage at 100 ms intervals. We have developed a lightweight monitoring tool that leverages Nvidia's DCGM library to capture fine-grained "compute utilization" metrics within GPUs. Deployed on a cluster with 89 nodes and 319 GPUs, our tool collected data over several months. This paper focuses on a 10-day period with 7,399 jobs submitted by 150 users from 12 departments. Our study reveals three key findings: (1) the GPU cluster exhibits significant underutilization, with over 70% of jobs using less than 20% of GPU memory and 50% averaging below 5% Streaming Multiprocessor (SM) utilization; (2) 80% of jobs have a drastic mismatch between their requested and actual durations, significantly limiting the scheduler's effectiveness; and (3) the multi-GPU jobs we examined show highly periodic communication patterns. These findings suggest there is plenty of room in the middle: substantial utilization gains are available through better job scheduling and GPU multitasking, independent of hardware or application improvements. Our monitoring solution is available as open-source software at https://github.com/als244/gpu_server_monitoring.
Andrew Sheinberg, Samyak Gupta, Kai Li
Princeton University, Department of Computer Science, Princeton, New Jersey, USA.
The rapid growth of large-scale machine learning (ML) has made distributed training across multiple GPUs a fundamental component of modern ML systems. As model sizes and computational throughput continue to increase, communication overhead has become a dominant bottleneck in multi-GPU training, particularly when computation and communication are executed sequentially. This work explores concurrent execution of computation and collective communication using two portable runtime controls: shared-memory-driven occupancy shaping for computation kernels and elevated scheduling priority for communication kernels. Our approach regulates computation-kernel residency through per-block shared-memory allocation, leaving sufficient on-chip resources for communication kernels to make progress. In addition, assigning higher priority to communication streams ensures steady communication progress once resources become available. Experiments on NVIDIA A40, A100, H100, and AMD MI250X GPUs demonstrate that the proposed method enables effective computation-communication overlap and reduces total execution time by up to 25.5 percent, without modifying vendor libraries or kernel implementations.
Minyu Cui, Miquel Pericas
Chalmers University of Technology and University of Gothenburg, Gothenburg, Sweden
Deep learning training commonly runs on shared multi-tenant GPU servers, where exclusive allocation provides isolation but can leave resources underutilized and increase queueing time. Collocation can improve efficiency, but interference-agnostic placement may cause severe slowdowns, while inaccurate memory information can lead to out-of-memory (OOM) failures. We present AEGIS, a server-scale runtime scheduling system for controlled collocation of deep learning training workloads on shared multi-GPU servers. AEGIS integrates memory feasibility, post-placement observation, runtime-pressure filtering, placement, and OOM-aware recovery in a single scheduling loop. After placement, AEGIS observes workload activity before permitting further collocation, then uses low-overhead telemetry to determine whether a GPU can safely accept additional work. OOM failures trigger retries under progressively safer memory conditions, eventually falling back to exclusive execution. This online approach avoids costly offline pairwise compatibility profiling. We evaluate AEGIS using vision, Transformer, recommendation, and LLM-style workloads across three production-derived traces. AEGIS reduces geometric-mean makespan by 16% relative to Lucid, 21% relative to Horus, and 27% relative to exclusive allocation. Sensitivity studies show that activity-anchored observation and runtime-pressure filtering balance conservative isolation against interference-agnostic collocation, improving makespan while limiting sharing-induced per-task slowdown.
Ehsan Yousefzadeh-Asl-Miandoab, Büşra Karatay Demiray, Florina M. Ciorba +2
IT University of Copenhagen Denmark · University of Basel Switzerland