# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 3 Scheduling Algorithms and Their Performance
### Cross-Paradigm Empirical Comparison  
The previous discussion compared scheduling paradigms primarily on qualitative grounds such as scalability to thousands of GPUs, fault tolerance, and the transparency of scheduling decisions. To complement that narrative, we now turn to a quantitative perspective: given a representative workload, which paradigms deliver the greatest gains in latency, throughput, and fairness? Table 5 presents key performance metrics from representative algorithms within each paradigm. Metrics are normalized against baseline approaches (e.g., heuristic or default schedulers) to emphasize relative improvements. Latency measures job completion time (lower is better), throughput/utilization captures jobs completed per unit time or resource efficiency (higher is better), and fairness reflects how well each approach maintained equitable resource sharing. \begin{table}
\begin{tabular}{p{56.9 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt}} \hline \hline
** Paradigm** & **Representative Algorithms/Workloads** & **Latency Improvement** & **Throughput/Utilization** & **Fairness Impact** \\ \hline \multirow{3}{*}{Greedy heuristics} & Tiresias [74] (LAS, training); Gandivafa (time-sharing) & \(\approx\)5.5\(\times\)\(\downarrow\) mean JCT vs. fair baseline; long-job slowdowns mitigated & High GPU utilization via backfilling; heterogeneous GPUs reused via token trading & Maintains long-term fair share \\ \hline \multirow{3}{*}{Dynamic programming} & Lyra [173] (capacity loaning, mixed training + inference) & \((1.48\)\(\sim\)1.53)\(\times\)\(\downarrow\) queuing/JCT & Up to 25\% \(\uparrow\) GPU utilization when borrowing idle inference GPUs & Inference SLOs preserved \\ \hline \multirow{3}{*}{MILP optimization} & Chronus [84] (deadline, training); Dorm/Allox (fair allocation) & \(14.7\times\)\(\downarrow\) deadline misses; \(19.9\times\)\(\downarrow\) best-effort JCT & Near-optimal utilization; MILP solved in batches (solver overhead acceptable) & Strong DRF-level fairness \\ \hline \multirow{3}{*}{Queueing theory} & LAS priority (Tiresias, training) [74]; dynamic batching model (inference) & \((5\)\(\sim\)6)\(\times\)\(\downarrow\) short-job wait; latency vs. batch size analytically predictable & Up to 13\(\times\)\(\uparrow\) throughput at large batch; short-job throughput boosted & Possible long-job slowdowns if not combined with fairness controls \\ \hline \multirow{3}{*}{ML-assisted prediction} & Helios [106] & \multirow{3}{*}{\(\approx\)44\% \(\downarrow\) average JCT; SCHEDTUNE [174] (interference, memory usage)} & 81\% \(\uparrow\) GPU-mem utilization; avoids OOM; better packing & Generally fair with tuned safeguards \\ \hline \multirow{3}{*}{Reinforcement learning} & DL2 [159] (supervised, + RL, training); SCHED\({}^{2}\)[157] (Q-learning) & \(44.1\%\)\(\downarrow\) average JCT vs. expert heuristic & \(1.8\times\)\(\uparrow\) jobs / hour; lower fragmentation & Fairness achieved when encoded in reward \\ \hline \multirow{3}{*}{Hybrid approaches} & Pollux [68] (adaptive goodput); AntMan [168] (elastic scaling) & \((1.2\)\(\sim\)1.3)\(\times\)\(\downarrow\) average JCT & \(1.5\times\)\(\uparrow\) throughput; (\(25\sim 40\))\% \(\uparrow\) goodput & Balances efficiency \& fairness \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Cross-paradigm empirical comparison of GPU scheduling algorithms. Improvements are reported relative to each study’s baseline (\(\uparrow\) means higher/better, \(\downarrow\) means lower/better). We summarize the absolute performance of representative GPU scheduling systems in Table 6.  
Design takeawaysGreedy heuristics offer robust, dependable performance across a wide range of applications and are relatively easy to implement. However, they typically require manual tuning for each deployment context, and their fairness can degrade under bursty or heterogeneous workloads.