# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 3 Scheduling Algorithms and Their Performance
### Summary of Scheduling Algorithms and Their Applicability Concerns
_Scheduler latency_ is the first: sophisticated policies such as AlloX's \(O(n^{3})\) Hungarian matching [124] or Decima's neural inference path [127] can incur tens to hundreds of milliseconds per decision. Most production deployments therefore amortize this cost--by reevaluating every few seconds or minutes--or fall back on sub-millisecond heuristics when responsiveness trumps optimality. Second, _state movement_ remains expensive; naively dumping GPU memory to disk for preemption can erase any latency gains promised by fairness-driven models. Systems thus rely on iteration-boundary checkpoints or oversubscription techniques such as SALUS, which multiplex kernels and memory to avoid full context switches at the expense of per-job throughput [192]. Third, _monitoring and adaptivity_ require a fine-grained telemetry substrate--either node agents or in-band probes--that feeds live utilization and contention metrics back to the scheduler. Instrumentation that is too coarse risks stale decisions, whereas overly chatty probes can induce feedback oscillations, so designers must strike a careful balance between freshness, overhead, and stability. Beyond per-node telemetry, multi-tenancy adds a cluster-wide layer of complexity: Multi-tenant GPU clusters bring unique scheduling challenges due to interference on shared resources. Co-locating jobs can induce contention not only on CPU cores--leading to context-switching overhead--but also on memory bandwidth, PCIe bus, and disk I/O when GPUs reside on the same node [193; 194]. Distributed training workloads further exacerbate contention by saturating network links, potentially throttling performance across tenant jobs [77; 195]. To mitigate these issues, modern schedulers incorporate resource topology and affinity into placement decisions. For example, awareness of NVLink connectivity or rack-level bandwidth can lead a scheduler to favor slightly less balanced but network-friendly allocations, reducing contention [167; 131; 196]. Parrot's coflow-aware framework dynamically adjusts bandwidth allocations during distributed machine learning, improving average job completion time by up to 18.2% in multi-tenant clusters [197]. Security and isolation are also critical. Without strong tenant separation, one job may leak information or disrupt another via GPU side channels or crashes [198]. Hardware-level isolation mechanisms such as NVIDIA's MIG partitions are often required to enforce tenant boundaries safely. A concrete example of system-level complexity is AlloX's integration with Kubernetes. Implemented as a scheduling extender, it spanned thousands of lines of Go and Python code to manage containers, sample job runtimes on CPU versus GPU, and ultimately allocate whole GPUs--since current clusters lack support for arbitrary GPU time-slicing [124]. This experience highlights that many theoretically optimal strategies (e.g., splitting a GPU) must be abandoned or adapted due to system limitations. Taken together, these integration and multi-tenancy obstacles reinforce a final lesson: Successful GPU scheduling balances algorithmic elegance with engineering practicality. Designers must iterate between prototype implementation and algorithm refinement, addressing integration, monitoring, preemption, and telemetry overhead to ensure that theory translates into real-world performance improvements.