Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper formalizes the admission control problem in multi-tenant GPU clusters using a multi-class, multi-resource queueing network framework. By establishing a structural decomposition of pending workloads into quotable and unfeasible categories, the authors provide a theoretical foundation for predicting wait times, demonstrating that optimal admission ordering is NP-hard. Validation through the Kueue system reveals that their model accurately identifies bottleneck resources and adheres to established queuing principles, offering significant insights into wait time management in GPU clusters.
Optimal admission ordering for GPU workloads is NP-hard, but this new framework reveals how to effectively manage wait times in multi-tenant environments.
GPU cluster operators cannot predict how long pending workloads will wait for admission. Existing systems use greedy heuristics with no formal wait time guarantees. We formalize GPU cluster admission as a multi-class, multi-resource queueing network and prove a structural decomposition: the pending queue partitions into quotable workloads (bounded wait time under stability) and unfeasible workloads (no finite bound without reconfiguration). For quotable workloads, we model each cluster queue as an M/G/k system where the effective server count k is determined by a vector packing reduction; under an explicit stochastic domination assumption, we establish O(1/(1-rho)) wait time scaling. We prove that optimal admission ordering is NP-hard under multi-dimensional resource demands via reduction from vector bin packing. We validate on Kueue, the standard Kubernetes workload queuing system, using CPU, memory, and GPU (via Dynamic Resource Allocation) resources. The vector k_eff correctly identifies bottleneck resource dimensions, Little's Law holds exactly, and the Erlang-C approximation consistently overestimates observed wait times in the conservative direction.