# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Choosing a Scheduling Paradigm in Practice  
To transform the catalog of paradigms in Section 2 into actionable guidance, we distill our empirical findings and surveyed case studies (Table 4) into a compact decision matrix. Practitioners can read the table top-to-bottom, stopping at the first row whose scenario description matches their workload. A short narrative justification follows Table 4.  
Choosing a scheduling paradigm in practice depends on four interacting axes. First is the _load regime and preemption cost_: in lightly loaded or single-tenant clusters, classical greedy heuristics--such as Gavel's bipartite matching--achieve near-optimal makespan with minimal overhead. However, once utilization exceeds roughly 75%, reinforcement learning (RL) schedulers like Decima offer better adaptability to bursty arrivals and workload variability, consistently outperforming static rules though only after a warm-up period and with reduced interpretability. Second, the _objective hierarchy_ determines whether fairness should outweigh throughput. In highly multi-tenant settings, DRF-aligned dynamic programming solvers can bound finish-time unfairness within a small constant factor of the leximin ideal. However, their exponential state space and reliance on exact runtime models confine them to small batches or partitioned sub-clusters. This limitation pushes larger deployments toward approximate or hybrid heuristics that trade a marginal degree of fairness for scalability. Third, _predictability and deadline sensitivity_ shape inference \begin{table}
\begin{tabular}{p{113.8 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt}} \hline \hline
**Workload Scenario** & **Primary Paradigm** & **Alternative Paradigm** & **Rationale** \\ \hline Single-tenant & & & Low job-completion time (JCT) \\ training-only, homogeneous cluster, preemptions costly & Greedy heuristic (e.g., SJF + backfill) & Queueing-index (SRPT/PS) & with minimal overhead; preemption avoidance simplifies implementation. \\ \hline Multi-tenant mixed & & & Provides provable fairness \\ (training + inference), fairness critical, moderate load & DRF-based DP / optimization & Hybrid heuristic + ML-assisted prediction & guarantees (e.g., bounded max-slowdown); small throughput trade-off. \\ \hline High load (\(>\)75\% utilization), variable DAGs, preemption cheap & Reinforcement learning (e.g., Decima) & Hybrid heuristic (HEFT + backfill) & Learns long-horizon dispatch policies to reduce p95 latency; alternative achieves near-optimal makespan with lower engineering cost. \\ \hline Real-time inference with static SLOs (50\(\sim\)200 ms), deadline-sensitive & Queueing-index (SRPT/processor-sharing) & Learning-assisted size prediction + PS & Size-based prioritization minimizes tail-latency; if exact sizes are unknown, predictions feed into PS to approach SRPT behavior. \\ \hline Energy-budgeted training under power/carbon caps & MILP-based multi-objective optimization & Hybrid heuristic with DVFS & Precise modeling of time–energy trade-offs; alternative reduces solver latency while achieving near-optimal energy usage. \\ \hline Offline batch scheduling with a fully known job set optimization & Offline MILP or DAG-based optimization & Queueing-theory policies (e.g., \(M/G/k\) with SRPT) & Computes optimal makespan for fixed jobs; when scale is large, queueing models offer analytical insights under stochastic approximations. \\ \hline Unpredictable workloads, heterogeneous GPUs, noisy runtime estimates & Hybrid heuristic + ML prediction & Robust heuristic (backfill with conservative reservations) & ML–predictions guide placement, but the fallback heuristic prevents starvation when prediction error is high. \\ \hline PDE / HPC solvers & Communication-aware MILP & Static bin-packing & Long-lived, tightly coupled jobs with predictable runtimes; performance dominated by NVLink/NVSwitch topology rather than queue dynamics. \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Decision matrix for selecting a GPU-cluster scheduling paradigm.