# Algorithmic Techniques for GPU Scheduling: A Comprehensive Survey
## 4 Looking Forward: LLM Focus
### Algorithmic Challenges in Large-Scale Training Job Scheduling  
Training state-of-the-art language models--with hundreds of billions of parameters--exposes scheduling challenges far beyond classical batch abstractions. Such jobs are _mal-leable_: they can run on widely varying numbers and types of GPUs and exhibit super-linear speed-ups up to a point of diminishing returns. Hence a scheduler must decide not only _when_ and _where_ to run each job, but also _how many_ and _which_ accelerators to allocate, revising those decisions dynamically as resources churn. [PERSON] tackles this combinatorial explosion by introducing _cells_--fixed pipeline-parallel configurations that discretize the search space to enable accurate performance modeling--yielding large throughput gains on heterogeneous clusters while keeping optimization tractable [203].  
The parallelization strategy itself is a scheduling primitive. Hybrid data-tensor-pipeline schemes can raise per-GPU FLOPs by 20\(\sim\)40% on thousand-GPU clusters, as demonstrated by [PERSON] on [PERSON] for a 175 B-parameter model [204]. Jointly choosing (i) a job's internal parallel plan and (ii) its placement on unrelated parallel machines is akin to an assignment problem with exponentially many configurations; naive ILP formulations are intractable, but cell abstractions and specialized network-flow reductions show promise [203]. There is rich room for heuristics and approximation algorithms that approach optimality without exhaustive enumeration.  
Elasticity further complicates matters: workloads expand or contract via batch-size or micro-batching adjustments in response to resource availability. Pollux's co-adaptive scheduling reallocates GPUs at epoch boundaries and tunes hyper-parameters on the fly [68]; Sia maintains per-job throughput curves for multiple GPU counts and solves a small optimizer each quantum [55]. A principled elasticity model therefore requires non-linear speed-up prediction across device types and counts, plus arbitration rules that prevent greedy expansions from starving neighbors--an open frontier for malleable-task theory in accelerator-rich settings.  
Reliability and cost enter next. Multi-day runs on preemptible VMs must balance savings against the risk of lost progress; Varuna morphs its parallelism on the fly, re-packing when nodes vanish and exploiting arrivals to shorten makespan [205]. Conceptually, GPUs come in \"cheap-but-volatile\" and \"stable-but-expensive\" flavors; scheduling under stochastic failures then resembles stochastic project planning with checkpoint-interval tuning, erasure-coded gradient replication, or peer-to-peer state mirroring as control knobs. Researchers currently lack ground truth data needed to compare restart latency across system designs. Until that gap is addressed, it remains difficult to meaningfully benchmark how quickly poisoned or compromised jobs recover under mechanisms such as checkpointing, erasure-coded replay, or Varuna-style live repacking.  
Finally, cluster scale forces a rethink of control hierarchy. A single monolithic scheduler can bottleneck at tens of thousands of GPUs. Hierarchical schemes partition capacity among frameworks or priority classes, delegating fine-grain placement to sub-schedulers, while fully decentralized approaches--where jobs make local decisions from small samples, such as in Sparrow [206]--remain largely unexplored for LLM training. Advances in volunteer/federated learning suggest that coordination-light schemes are feasible [207], but the central question is how to approximate global optimality and fairness under partial information and bounded communication.  
Taken together, malleability, parallelism co-design, elasticity, reliability, and decentralized control form an intertwined agenda for both systems and theory. Addressing them will require new abstractions that couple performance-modeling fidelity with algorithmic tractability, alongside robustness techniques that scale gracefully to the next order of cluster heterogeneity.