Recursive Laminar Decomposition for Preemptive Resource Allocation

Abstract

Preemptive resource allocation is a fundamental scheduling problem in cloud computing and GPU clusters, where jobs with release times, deadlines, and resource demands must be assigned to shared hosts. State-of-the-art approximation algorithms achieve strong guarantees only when job time-windows form a laminar family of nested or disjoint intervals, and they handle general instances by approximating the workload with a single laminar subfamily. It was unknown, however, whether real production workloads contain richer laminar structure that this single-subfamily approach leaves unexploited. To investigate this, we analyzed the Alibaba OpenB GPU cluster trace of 8,152 production jobs by repeatedly extracting maximum laminar subfamilies, each computed as a maximum independent set in the interval-crossing graph, until no jobs remained. We then developed Recursive Laminar Decomposition, a framework that applies existing laminar scheduling algorithms to every extracted layer rather than to a single subfamily. Although the first laminar subfamily contains only 56.16% of jobs, each successive extraction removed roughly half of the remaining jobs, decomposing the entire trace into just 12 laminar layers in approximately 20 seconds. We implemented and validated the scheduling algorithms against exact optima on small instances. On the production trace, the framework increased throughput by up to 20.5% over single-layer scheduling. It also produced valid schedules in high-slackness regimes where the baseline algorithm offers no guarantee. These results demonstrate that production workloads possess a compact layered laminar structure that can be exploited to extend efficient laminar scheduling algorithms to realistic, non-laminar instances.