# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 1 Introduction
### Cluster Computing and the Necessity of GPU Scheduling Algorithms  
Cluster computing has undergone significant evolution over the past few decades. The initial drive for greater computational throughput gave rise to CPU clusters composed of a small number of high-performance cores [51]. However, as machine learning and deep learning (DL) workloads surged, GPUs have become an indispensable element of modern infrastructure. Large-scale GPU clusters--once the domain of specialized scientific centers--are now commonplace in academic, industrial, and cloud environments [52; 53; 54]. These systems comprise interconnected nodes, each hosting one or more GPUs, and often feature heterogeneous hardware configurations that integrate diverse CPU architectures, memory hierarchies, and GPU generations [44; 55; 56; 57]. To support the high data rates demanded by ML/DL workloads, GPU clusters employ high-speed interconnects--such as PCIe, NVLink, and InfiniBand--to facilitate rapid data exchange both within and across nodes [58; 59]. Figure 1 depicts a representative GPU cluster architecture.  
In modern GPU clusters, the high capital and operational costs of GPU hardware and supporting infrastructure demand sophisticated scheduling strategies. High-end GPUs such as the Nvidia A100 80 GB can cost nearly $15,000 [60], and utilization rates in large-scale deployments can plummet to 50 % [44; 61]. Such under-utilization reflects not a shortage of demand but suboptimal resource allocation. Critical resources--including GPU and CPU compute units, memory bandwidth, and interconnect bandwidth--are both scarce and expensive [62; 36; 56; 63]. Advanced scheduling algorithms that optimize across these dimensions are therefore essential to minimize idle time, balance operator and user objectives, and achieve substantial cost efficiencies in large-scale environments.  
Several intertwined factors exacerbate scheduling challenges in these clusters. Heterogeneity extends beyond hardware to encompass a wide spectrum of job profiles: from training workloads that run for days [64] to latency-sensitive inference tasks that complete in milliseconds [65]. Uncertainty in execution times further complicates allocation decisions, as does the diversity of resource requests--ranging from fractional GPUs to multi-GPU or CPU-only configurations. Consequently, simple heuristics such as first-fit or bin-packing fail to capture the multi-dimensional nature of GPU cluster scheduling [36].  
Scheduling challenges are also exacerbated by conflicting objectives between cluster operators and users. Operators typically aim to optimize GPU and resource utilization while minimizing job completion times [56; 66; 67; 68], while users prioritize job accuracy and fairness in allocation [62; 69; 70]. As a result, no single scheduling solution is universally applicable. Algorithmic scheduling techniques have already shown impressive performance, with one algorithm reducing unallocated GPUs by up to 49% [36]. Such improvements could result in significant cost savings, particularly in large-scale data centers with thou  
Figure 1: The general setup of a GPU cluster: The dashed arrows represent data-flow, and the solid arrows represent scheduling decisions.  
sands of GPUs. For instance, Helios, operated by SenseTime, manages four clusters with a total of 6416 GPUs [64].  
Building on the challenges outlined above, LLMs (large language models) further amplify the scale and complexity of GPU cluster scheduling. In certain LLM configurations, GPU utilization can dip below 50%, and decreases further as model parameter counts grow--despite proposed methods that can boost utilization to over 75% [61]. Resource allocation for LLM training brings additional difficulties not encountered in standard deep learning workloads, since most existing schedulers were not designed to handle the vast scale, heterogeneity, and dynamic demands of LLMs. Overcoming these challenges will require more sophisticated scheduling strategies.