# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Components of a Model  
Most scheduling theory is _hardware-agnostic_, but GPU clusters differ significantly from traditional CPU farms. Table 2 highlights key architectural traits that strongly influence scheduling algorithm design. Frequent preemption--central to SRPT (shortest-remaining-processing-time)-style CPU scheduling--is generally impractical on GPUs. Interconnect contention necessitates topology-aware bin-packing or mixed-integer linear programming (MILP) approaches. NVIDIA's Multi-Instance GPU (MIG) allows resource multiplexing, but only at coarse, integer granularity. Accurate power modeling must decouple streaming multiprocessor (SM) and high bandwidth memory (HBM) usage, in contrast to the unified RAPL (running average power limit)-based models used for CPUs. GPU cluster architecture: Models typically represent the cluster as a set of compute nodes, each equipped with one or more GPUs, along with CPUs, memory, and high-speed \begin{table}
\begin{tabular}{l l l} \hline \hline
**Trait** & **Typical CPU Cluster** & **GPU Cluster (A100/H100 era)** \\ \hline Context switch / & \(\approx 3\)\(\mu\)\(\sim\)10 \(\mu\)s (core) & 10 ms\(\sim\)30 ms (kernel) \\ preemption & inexpensive, fine-grained & costly; whole-SM drain required [73, 74] \\ \hline \multirow{2}{*}{Device memory per worker} & \multirow{2}{*}{128, 256 GB DDR4/5 shared} & 40 \(\sim\) 80 GB HBM private to each device \\  & & Placement must avoid OOM even at low \\ \hline \multirow{3}{*}{NUMA / socket locality} & \multirow{3}{*}{1\(\sim\)4 hop latency tiers per node [75]} & Two tiers: NVLink/NVSwitch (200\(\sim\)900 GB/s) vs. PCIe (32 GB/s, 64 GB/s). Cross-tier traffic quickly \\  & & dominates runtime [58, 76]. \\ \hline \multirow{3}{*}{Partitioning granularity} & Core / SMT thread; OS-level control groups & MLG slices (1/7\(\sim\)1/2 device) or whole GPU \\  & & Integer-snapsack bin packing, no fractional \\ \hline \multirow{3}{*}{Inter-device topology} & \multirow{3}{*}{NUMA DRAM buses and Ethernet/IB} & On-node all-to-all (NVSwitch) + inter-node \\  & & fat-tree IB (NDR/HDR) \\ \cline{1-1}  & & Topology-aware placement yields up to \\ \cline{1-1}  & & 1.3\(\times\) speed-ups [77]. \\ \hline \multirow{3}{*}{Power management} & Per-core DVFS, RAPL & Device-level DVFS; memory clock often \\ \cline{1-1}  & & fixed \\ \cline{1-1}  & & energy models must separate SM vs. HBM \\ \cline{1-1}  & & power. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Hardware assumptions and their scheduling implications. network interfaces. Within a node, GPUs communicate over a fast interconnect, while nodes themselves are linked by a high-speed network, enabling workloads to span multiple machines [78; 79]. A _central scheduler_ or _cluster manager_ receives user submissions and determines how to assign GPUs to each job [80]. Jobs may demand fractions of a GPU, a single GPU, or multiple GPUs. Unless stated otherwise, we assume jobs arrive online and wait in a queue until sufficient resources become available. Jobs and GPU requirements: We model three primary entities: _jobs_, _resources_, and _queues_. Let \(J=\{1,2,\ldots,n\}\) denote the set of jobs to be scheduled. Each job \(j\in J\) is characterized by:  
* GPU demand \(g_{j}\) (which may be fractional or span multiple GPUs),
* estimated runtime \(p_{j}\),
* release time \(r_{j}\) (for online arrivals),
* optional priority or weight. The cluster provides \(m\) GPU slots, which may be homogeneous or heterogeneous across nodes. Scheduling systems may use a single global queue or multiple queues (e.g., to separate jobs by GPU type or priority) [81]. Some models allow preemption, while others assume jobs run non-preemptively to completion [82; 83]. In offline formulations, job runtimes may be known or stochastic; in online settings, runtimes are unknown and decisions must be made with incomplete information [74; 84].