# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 2 Models
### Evaluation Metrics and Validation Methods for Scheduling Models  
Measuring the effectiveness of a scheduling model and any algorithms it inspires relies on well-defined metrics that capture both system efficiency and user-centric outcomes. Beyond the objectives listed in Table 3, scheduling for ML workloads introduces an important additional dimension: model quality. Optimizing solely for execution time can be misleading if, for example, resource allocations that minimize runtime degrade the final accuracy of a trained model. To address this, researchers have proposed ML-specific performance metrics. SLAQ assesses schedulers by the final training loss or accuracy achieved under a fixed resource budget, ensuring that faster completions do not come at the expense of model fidelity [108]. Pollux, on the other hand, defines _goodput_ as the count of training samples that genuinely contribute to convergence, filtering out those wasted by suboptimal settings (e.g., excessively large batch sizes) [68]. These metrics are crucial whenever the ultimate goal of scheduling is not just speed but also the quality of the ML outcome. Once suitable evaluation metrics have been defined, most studies adopt a three-pronged strategy for validating new scheduling models. First, _theoretical analysis_ furnishes provable bounds on latency, fairness, or resource utilization under idealized assumptions, clarifying fundamental performance ceilings and exposing worst-case behaviors. Second, _simulation_--typically trace-driven or synthetic--offers a controlled sandbox in which competing designs can be stress-tested across diverse workload mixes and cluster sizes, enabling repeatable, apples-to-apples comparisons. Finally, _real-world deployment_ on production clusters supplies the decisive reality check: it surfaces implementation overheads, robustness to unforeseen traffic spikes, and subtle interactions with existing infrastructure. Collectively, these layers of proof, in-silico experimentation, and live trials yield a comprehensive picture of each scheduler's strengths, limitations, and practical applicability. Theoretical analysis: After selecting appropriate performance metrics, one method for evaluating a scheduling model or policy is through theoretical analysis. This approach entails proving bounds or optimality guarantees under the model's simplifying assumptions. For instance, one might show that a scheduling algorithm yields a makespan no greater than \(1.5\times\) an optimal solution (i.e., a 1.5-approximation) on any input, or that under a given stochastic workload model, a policy minimizes expected response time. When models are sufficiently constrained--say, by assuming independent jobs or exact knowledge of runtimes--tools from classical scheduling theory or queueing theory can be applied to derive these results. Such proofs lend confidence by demonstrating, for example, that a new strategy enjoys strictly better worst-case performance or fairness properties than existing approaches. That said, these guarantees often depend on idealized conditions--e.g., i.i.d. job sizes or negligible context-switch overhead--that real GPU clusters may violate [129]. Consequently, theoretical insights are most compelling when paired with empirical validation. Simulation: To assess scheduling models in settings closer to real-world deployments, researchers employ event-driven simulators that model a GPU cluster's behavior: jobs arrive, are queued, and then dispatched to virtual GPUs according to the scheduling policy, with completions and resource usage tracked precisely. Simulations may use synthetic workloads drawn from statistical distributions or replay traces of actual job arrivals and runtimes collected from production clusters [36; 130]. Throughout each run, key metrics such as average job completion time, waiting-time distributions, GPU utilization over time, and fairness indices (e.g., [PERSON]'s index or the proportion of jobs meeting specified SLOs) are recorded [117].