COMPASS-ABS: Reducing Fragmentation in Shared GPU Clusters for Deep Learning Training Workloads Yukai Zhou Hongfan Wu∗
arXiv:2609.18519v1 [cs.DC] 16 Sep 2026
Abstract
Resource fragmentation arises from DLT job placement constraints. A DLT job consists of multiple homogeneous instances, and the GPUs assigned to each instance need to lie within a single node to preserve fast intra-instance communication[4, 10]. This intra-node constraint can prevent admission even when the cluster has enough available GPUs in total. Consider a cluster with three nodes that currently have 3, 5, and 2 free GPUs, i.e. 10 free GPUs in total. A job with two 4-GPU instances demanding 8 GPUs in total cannot be admitted because only one node can host a 4-GPU instance. The fragmented distribution of idle GPUs blocks a placement that would appear feasible under an aggregatecapacity view. So resource fragmentation leads to low GPU utilization despite pending jobs awaiting processing, causing prolonged job completion time due to long queueing latency. This observation raises two central questions: (1) how to quantify the resource fragmentation? (2) how to solve the problem of GPU cluster underutilization and long completion time of DLT jobs caused by resource fragmentation? Existing fragmentation metrics are statistical measures of fragmentation. FGD[45] defines a workload-distribution-aware fragmentation score, while CAFGD[24] refines this idea by weighting long-term and short-term distributions. These metrics rely on workload history knowledge and fail to measure fragmentation in its absence. Existing schedulers for scheduling DLT jobs in shared GPU clusters can be grouped into two categories. Nonmigration methods place each job at admission and never revisit the decision: ElasticFlow[9] formulates placement as a bin-packing problem and applies best-fit-style heuristics, while FGD[45] and CAFGD[24] greedily optimize their fragmentation metrics at first admission time. These methods react only to the current state and provide no mechanism to repair fragmentation that has existed. Migration-based approaches reorganize running DLT jobs through checkpoint-based migration. Gandiva[50] only suggests migrating running jobs when cluster status changes, without specifying the implementation details like when and how to migrate. FFT[30] and DRR[49] adopt a round-driven strategy whose defragmentation relies on global migration at the beginning of each round, which cannot mitigate the resource fragmentation accumulated within each round. More fundamentally, they all cannot guarantee low fragmentation throughout the online scheduling process. Motivated by these limitations, we introduce SchedulerInduced Fragmentation (SIF) to measure dynamic resource
With the rapid advancement of deep learning technology, shared GPU clusters receive an increasing number of deep learning training (DLT) jobs. Yet resource fragmentation make such clusters underutilized and forces the DLT jobs running on them to endure long turnaround times. Extensive research has been devoted to quantifying fragmentation and developing scheduling algorithms that alleviate its impact. However, existing fragmentation measures break down in the absence of workload distribution information, while current schedulers cannot continuously maintain resource fragmentation at a low level. To tackle these problems, we first introduce Scheduler-Induced Fragmentation (SIF), a metric built on the notion of partial-nodes that is independent of historical workload knowledge. We then propose COMPASS-ABS, which employs the COMPact-ASSured (COMPASS) algorithm to confine the cluster state within a tight Anchor-Based Space (ABS), whose construction fully leverages the topological alignment between dominant workload size and node capacity. Moreover. We also prove that it ensures SIF is bounded by 𝑁2 under a workload composition condition that matches both theory and production. Evaluations implemented on a physical cluster and a simulated cluster demonstrate COMPASS-ABS effectiveness at improving resource utilization, reducing DLT job completion time by reducing fragmentation. CCS Concepts: • Computer systems organization → Cloud computing; • Theory of computation → Scheduling algorithms. Keywords: Deep learning training, shared GPU cluster, fragmentation, resource scheduling
1
Introduction
Deep learning has developed rapidly in recent years, driven by larger model frameworks, more complex training pipelines, and the rise of large language models[23, 34]. Training these models requires substantial GPU resources, so industrial labs and cloud providers operate large shared GPU clusters where users submit deep learning training (DLT) jobs[15, 22, 36, 44]. Yet production clusters exhibit both low GPU cluster utilization and long turnaround time for DLT jobs, which stems from the resource fragmentation rather the capacity shortage[24, 45]. ∗ Corresponding author.
1
Yukai Zhou and Hongfan Wu
fragmentation and design the COMPASS-ABS scheduler for DLT jobs in shared GPU clusters. Our contributions are summarized as follows:
use of data parallelism, where the training program is replicated across multiple instances processing different minibatches. Thus, a DLT job is composed of multiple homogeneous instances that run the same model and carry the same per-instance GPU demand 𝑔𝑖 [4]. Within each instance, multiple GPUs may collaborate through tensor parallelism and other mechanisms to execute the forward and backward passes[25, 32, 34]. These mechanisms frequently invoke collective communication primitives such as All-Reduce, making the instance sensitive to communication latency[19]. Tensor parallelism partitions large parameter matrices across GPUs, and common tensor-parallel degrees are 2, 4, and 8. Collective implementations such as ring, recursive-doubling, and tree-based AllReduce are structurally defined on power-of-two participant counts, while non-power-of-two configurations lead to padding or special-case handling[41]. These properties make 𝑔𝑖 ∈ {1, 2, 4, 8} a natural operating regime, which is consistent with production trace characteristics[15, 22, 44]. Beyond intra-instance communication, different instances of the same job execute data-parallel synchronization at the end of each iteration to apply a synchronous parameter update, which requires all instances to run concurrently. Thus, schedulers for DLT workloads commonly treat each job as an all-or-nothing allocation unit, which imposes a gang scheduling requirement[10, 51].
• Scheduler-Induced Fragmentation (SIF). Building on the notion of partial-nodes, we decompose observed fragmentation into two parts: an inherent component forced by the intra-node placement constraint, and an additional component caused by the scheduler’s placement decisions. SIF measures only the latter, which no longer requires the workload history distribution information. • COMPASS-ABS scheduler. We firstly define ABS (Anchor-Based Space), a constrained feasible cluster state domain whose structure is tailored jointly to the dominance of power-of-two GPU demands and to their topology alignment with node capacity. MultiGPU instances are placed as anchors in slots of width 2, 4, or 8 GPUs, while 1-GPU instances are managed through a pool and used as fillers for saturating slot vacancies. The COMPASS(COMPact-ASSured) algorithm maintains cluster change within this space in a compact manner through three operators: Place, Remove, and Compact. Under the Workload Composition Condition (WCC) stated in Theorem 1, COMPASSABS guarantees SIF𝜋 (𝑡) ≤ 𝑁2 at all times. • Evaluation. We conduct comprehensive experiments to validate the scheduling performance of COMPASSABS, including large-scale simulations on two production traces and a physical-cluster deployment with a synthetic DLT workload. COMPASS-ABS attains the highest GPU utilization and the shortest job completion time among all state-of-the-art baselines by maintaining the lowest fragmentation level, and sustains its strength under varying cluster load, workload composition, and migration cost, even when the Workload Composition Condition is violated.
2
2.2
Modern GPU clusters comprise multiple nodes, each of which serves as a primary high-bandwidth communication domain in the network topology[23, 36]. GPUs on the same node communicate through NVLink at terabyte-per-second bandwidth, whereas inter-node communication involves lower bandwidth and switch-level congestion. For the latencysensitive intra-instance communication described above, all GPUs assigned to an instance must belong to the same node, which makes the available GPUs non-interchangeable[45, 50]. This node-locality constraint is the structural source of the fragmentation problem studied in this paper. Each node contains eight GPUs, matching the configuration reported in production clusters[15, 22, 35, 44]. The eightGPU design has a hardware basis: DGX-1 connects eight GPUs as a hybrid cube-mesh, and later DGX/HGX systems preserve eight GPUs as a server-level building block while improving the internal fabric with NVSwitch[26, 35, 36]. This eight-GPU node is an industry-wide convention rather than an NVIDIA-specific choice, as the vendor-neutral OCP OAM Universal Baseboard standard[37] hosts eight accelerators per baseboard and mainstream accelerator servers adopt the same 𝐺 = 8 layout, including AMD Instinct[1], Intel Gaudi[20], Huawei Ascend[18], and Meta’s Grand Teton[29].
Background
This section reviews the task structure and communication patterns of DLT jobs, together with the architectural properties of physical GPU clusters. We point out two system characteristics that motivate the scheduler design in Section 4: the per-instance GPU demand 𝑔𝑖 is concentrated on power-of-two values, and the basic communication domain in production clusters is a node of 8 GPUs. 2.1
Physical Cluster
Deep Learning Training Jobs
As deep learning models continue to extend, the memory capacity and compute throughput of a single GPU are insufficient for an increasing fraction of training workloads. Modern frameworks therefore support training across multiple GPUs[17, 28, 34]. The growth of training datasets drives the 2
COMPASS-ABS
3
Scheduler-Induced Fragmentation
in total. No scheduler could have done better in this situation, because these three partial nodes are byproducts of systemic constraints rather than incorrect scheduling. Avoidable partial nodes. Consider two nodes that are each fully packed without free GPUs, where a single job has placed one 4-GPU instance on each node and the remaining 4 GPUs of each node are occupied by unrelated instances. When this job completes, both nodes simultaneously release a 4-GPU block and the cluster gains two partial nodes in a single event. This fragmentation is not structurally necessary, because the scheduler could migrate all instances on the second node into the idle region of the first, after which the cluster would contain zero partial nodes. The two partial nodes here are avoidable, because their existence is entirely attributable to the scheduler’s decision.
This section gives the measure of resource fragmentation without relying on history trace information. In §3.1, we introduce the notion of partial-nodes, which are the principal carrier of fragmented resource, and separate them into two mutually exclusive proportions. Building on this distinction, §3.2 then defines a new measure called Scheduler-Induced Fragmentation (SIF), computed solely from the resource demand of currently running jobs in the cluster. 3.1
Key Insight: Avoidable vs. Forced Partial Nodes
We firstly define a node that is non-empty yet assigned fewer GPUs than its full capacity as a partial node. A fragmented placement disperses free GPUs across many partial nodes and causes contiguous GPU resources to become scarce, whereas a well-designed placement will reduce the partialnode count to release the fragmented GPUs trapped inside partial nodes and return them to larger contiguous GPU blocks, which is friendly to all DLT jobs. This concern becomes most pressing when the cluster receives large jobs. Consider a job consisting of 𝑤 8-GPU instances which require 𝑤 fully-empty nodes on the cluster before it can be admitted. Consider a cluster of 𝑁 nodes in which the current fragmented placement consumes 𝑁 1 nodes, whereas a compact placement of the same set of running DLT jobs would consume only 𝑁 2 < 𝑁 1 . The compact placement therefore leaves 𝑁 − 𝑁 2 nodes entirely empty, while the fragmented one leaves only 𝑁 − 𝑁 1 . Whenever the requested job size satisfies 𝑁 − 𝑁 1 < 𝑤 ≤ 𝑁 − 𝑁 2 , that job is admissible under the compact placement but is blocked under the fragmented one, even though the cluster’s aggregate free-GPU count exceeds 8𝑤 in both situations. This large DLT job blocking results from fully-empty-node availability: 𝑁 1 − 𝑁 2 nodes trapped in partial occupancy could otherwise serve as the continuous GPU blocks that large jobs demand. We therefore set our primary objective for mitigating fragmentation as minimizing the number of partial nodes, which can equivalently be stated as minimizing the total number of nodes in use. We adopt the former formulation throughout the remainder of this paper. However, not every partial node is produced by the scheduler: some cannot be eliminated by any scheduler, while others arise from a suboptimal scheduling decision and can be eliminated by right placement and migration. Then we demonstrate the distinction through two illustrative examples. Forced partial nodes. Suppose the cluster currently has only one partial node, which hosts a single 4-GPU instance, a DLT job consisting of two 5-GPU instances waits at the head of queue. Due to intra-node constraint, neither of the two new instances can utilize the 4 free GPUs on this partial node. The only feasible placement is opening two other empty nodes, each hosting a single 5-GPU instance with 3 GPUs unused, so that the cluster now contains three partial nodes
3.2
Decomposing Fragmentation: Inherent and Scheduler-Induced
Motivated by §3.1, we now formally split the fragmentation into two complementary components, the portion that any scheduler must leave behind, and the portion introduced by chosen scheduler 𝜋. Inherent Fragmentation. We denote the set of DLT jobs running on the cluster at time 𝑡 by J (𝑡). Each job 𝑖 ∈ J (𝑡) consists of 𝑤𝑖 homogeneous instances, each demanding 𝑔𝑖 GPUs, where 𝑔𝑖 ∈ {1, . . . , 𝐺 } and 𝐺 = 8. The instantaneous demand structure of running DLT jobs is then formalized as I (𝑡) = {(𝑔𝑖 , 𝑤𝑖 ) : 𝑖 ∈ J (𝑡)}. In order to isolate the fragmentation originating from constraints alone, we construct a static bin-packing problem in which each DLT job is treated as 𝑤𝑖 items of size 𝑔𝑖 and each node as a bin of capacity 𝐺. The question then becomes: what is the minimum partial-node count achievable over all feasible packings of these items into bins? Formally, for any feasible packing 𝑃 that satisfies the intra-node constraint, we let 𝜈 (𝑃) denote the number of partial nodes in 𝑃 and write Φ★ (𝑡) := min𝑃 feasible 𝜈 (𝑃) for the minimum partial-node count achievable across all such packings. The Inherent fragmentation is then the normalised share Φ★ (𝑡) min𝑃 feasible 𝜈 (𝑃) 𝐹 ★ (𝑡) := = . (1) 𝑁 𝑁 Because 𝐹 ★ (𝑡) depends only on the real time resource demand I (𝑡) and is independent of arrival order, placement history, or migration operation, it serves as an unavoidable lower bound on the partial-node share. A heuristic algorithm for computing Φ★ (𝑡) (and therefore 𝐹 ★ (𝑡)) is provided in Appendix C. Scheduler-Induced Fragmentation. Under an online policy 𝜋, the placement of all jobs in the cluster observed at time 𝑡 is itself a feasible packing 𝑃 𝜋 (𝑡) of I (𝑡), and we let 𝐹 𝜋 (𝑡) := 𝜈 (𝑃 𝜋 (𝑡))/𝑁 denote its partial-node share, which represents the gross fragmentation. We define the SchedulerInduced Fragmentation (SIF) by subtracting the inherent 3
Yukai Zhou and Hongfan Wu
The structural reasons in §2.1 make 𝑔𝑖 ∈ {1, 2, 4, 8} the natural operating regime for DLT instances, so non-power-of-two instance sizes 𝑔𝑖 ∈ {3, 5, 6, 7} account for only a small fraction of the instance population in production traces. Table 1 confirms this claim by reporting the average per-type instance shares observed on the GFS[7] and Venus[15] traces, where the 𝑔𝑖 = 1 and 𝑔𝑖 = 8 classes together dominate the trace and the I FUF retains only a marginal share. These observations lead to two design ideas. Design idea 1: Round every fragmentation-unfriendly instance into a fragmentation-friendly composite block with fillers. Observation 1 already points out that a best-fit placement keeps SIF ≤ 𝑁2 once the workload is restricted to power-of-two-sized instances, and we therefore want to extend the same guarantee to the fragmentation-unfriendly population. To this end, we round instance in I FUF into a friendly-sized composite block whose total size falls in {2, 4, 8} by combining it with smaller instances. Then the scheduler only sees fragmentation-friendly-shaped blocks rather than a heterogeneous mixture of friendly and unfriendly demands under this transformation, so that the placement decisions on the entire multi-GPU population I ≥2 reduce to the I FF -only case. Design idea 2: Employ 1-GPU instances to assemble the fragmentation-friendly composite blocks and manage them in a dedicated pool. As 1-GPU instances largely outweigh those in I FUF and they are the natural filler units to mitigate fragmentation, we accordingly use 1-GPU instances to fill the residual GPUs inside each composite block, namely the gap between the original unfriendly instance and its rounded friendly block. Due to the dynamic arrival and departure of I FUF instances, the requests for fillers change over time, and the cluster needs to adaptively migrate 1GPU instances to the right place to maintain the integrity of the composite block. This motivates us to place all 1-GPU instances in a unified pool for better management.
fragmentation from the gross fragmentation: 𝜋
𝜋
★
SIF (𝑡) := 𝐹 (𝑡) − 𝐹 (𝑡) ≥ 0,
(2)
which represents the percentage of avoidable partial nodes that the policy 𝜋 has produced. This definition makes SIF a more reasonable fragmentation measure than the statistical metrics reported in FGD and CAFGD. It builds upon the resource demand of the running jobs rather than further historical information about the workload resource demand distribution. Moreover, it accurately quantifies the proportion of fragmentation that is introduced by the scheduler. Therefore, it motivates us to design a scheduler that persistently keeps SIF𝜋 (𝑡) at a low level.
4
COMPASS-ABS Scheduler
This section presents our COMPASS-ABS scheduler that employs the COMPASS algorithm to maintain the cluster evolving in the compact ABS domain. In Section 4.1, we introduce our design motivation for the innovative scheduler; In Section 4.2, we define a feasible space ABS for the cluster to operate in, driven by the characteristic of workload composition and cluster topology; In Section 4.3, we present the COMPASS algorithm that constrains the cluster state within the ABS in a consolidated manner. In Section 4.4, we further provide theoretical guarantee on the ability of our scheduler to keep SIF low at minimal computational cost. 4.1
Design Rationale
Observation 1: Power-of-two-sized multi-GPU instances scheduled by the best-fit policy when node capacity is 8 keep SIF ≤ 𝑁2 . Before examining fragmentation in detail, we set aside the instances whose 𝑔𝑖 = 1, denoted as I =1 , because they never create fragmentation but rather act as the natural filler units to mitigate fragmentation by utilizing the scattered idle GPUs left on partial nodes. Restricting attention to the multi-GPU instances, denoted as I ≥2 , we exploit a divisibility alignment between the instance demand and the node capacity: every 𝑔𝑖 ∈ {2, 4, 8} divides 𝐺 = 8 exactly, so any combination of such instances either fully fills a node or leaves a residue GPU block of size in {2, 4, 6}. Under this alignment, a best-fit policy that places each instance on the node leaving the smallest remaining capacity after placement, together with a lightweight Compact pass that consolidates partial nodes after every departure, retains SIF𝜋 (𝑡) ≤ 𝑁2 at all times. The formal proof, including the matching tightness construction, is deferred to Appendix A. We accordingly name the multi-GPU instances with 𝑔𝑖 ∈ {2, 4, 8} as Fragmentation-Friendly instances and denote them by I FF , whereas instances whose demand falls in {3, 5, 6, 7} are called Fragmentation-Unfriendly instances, denoted by I FUF , so all multi-GPU instances can be partitioned into I ≥2 := I FF ∪ I FUF . Observation 2: Fragmentation-unfriendly instances account for only a small share of real DLT workloads.
Table 1. Per-class instance share across two DLT traces.
4.2
Trace
I =1
I FF
I FUF
I =8
GFS Venus
64.16% 37.68%
6.07% 9.44%
0.05% 0.44%
29.73% 52.44%
Anchor-Based Space (ABS)
Driven by the design ideas above, we define a structured state space for the cluster that we call the Anchor-Based Space (ABS), within which the placement of all DLT jobs is required to remain throughout the cluster’s evolution. Then we formalize the key objects in the ABS domain. Definition 1 (Slot). A slot, denoted by 𝑠, is a GPU block inside a node. Each slot has a fixed width 𝑤 (𝑠) ∈ {2, 4, 8}. 4
COMPASS-ABS
Anchor-Based Space (ABS) Σ. For each node 𝑛, the internal state 𝜎𝑛 is determined by 𝑡 (𝑛): ⊥, 𝑡 (𝑛) = empty, 𝜎𝑛 = 𝑃 (𝑛) ⊆ I =1, |𝑃 (𝑛)| ≤ 𝐺, 𝑡 (𝑛) = pool, (7) (𝑎 𝑗 , 𝐹 𝑗 ) 𝑘𝑗=1, 𝑡 (𝑛) = slotted.
When a multi-GPU instance of demand 𝑔 is assigned to a slot, the slot width is chosen according to 2, 𝑔 = 2, 𝑤 (𝑔) = 4, 𝑔 ∈ {3, 4}, 8, 𝑔 ∈ {5, 6, 7, 8}. ★
(3)
The instances belonging to I FF will directly saturate widthmatched slots, while counterpart instances will be assigned to rounded-up slots.
where 𝑎 𝑗 ∈ I ≥2 , 𝐹 𝑗 ⊆ I =1 and together satisfy the capacity invariant in (4). The cluster-level state space is therefore n o Σ = 𝜎 = 𝜋, (𝜎𝑛 )𝑛∈ N 𝜋 : N → T, 𝜎𝑛 as above . (8)
Definition 2 (Anchor and Slot Vacancy). On each slot 𝑠, there is exactly one instance 𝑎(𝑠) ∈ I ≥2 called the anchor of 𝑠 that occupies 𝑔𝑎 (𝑠 ) GPUs in that slot, where 𝑔𝑎 (𝑠 ) is the demand of that instance. The remaining 𝑤 (𝑠) −𝑔𝑎 (𝑠 ) GPUs in the slot are called the slot vacancy of 𝑠. Whenever 𝑎(𝑠) ≠ ∅, the slot width satisfies 𝑤 (𝑠) = 𝑤 ★ (𝑔𝑎 (𝑠 ) ).
This state-space design is organized entirely around the notion of anchor, which provides a unified scheduling unit for both fragmentation-friendly and fragmentation-unfriendly multi-GPU instances. Starting from this concept, the gap between a slot’s width and its anchor’s actual demand naturally introduces fillers to absorb the residual capacity inside each slot, and the practical need to migrate these fillers flexibly across the cluster in turn motivates the design of pool nodes as the dedicated pool for 1-GPU instances. Therefore, we name this state space Σ as Anchor-Based Space (ABS).
Definition 3 (Filler and Capacity Invariant). When the slot vacancy of 𝑠 ≠ 0, we only employ 1-GPU instances to saturate the slot vacancy, which are called fillers. Representing the set of fillers currently attached to 𝑠 as 𝐹 (𝑠), we require 𝑔𝑎 (𝑠 ) + |𝐹 (𝑠)| ≤ 𝑤 (𝑠).
(4)
4.3
Equality means the slot is fully used.
We propose the COMPact-ASSured (COMPASS) algorithm that consists of three operators, the Place and Remove operators together guarantee that the cluster state lies within ABS Σ as the job is admitted and completed, while the Compact ensures the compactness of ABS Σ. Each DLT job is admitted only when all of its instances can be placed simultaneously and is released as a whole upon completion. We therefore formulate scheduling decisions at the instance granularity, where every job-level scheduling is translated into a sequence of per-instance operations whose union realises the corresponding job-level decision, and for an instance 𝑖 we write 𝑔𝑖 for its GPU demand.
Definition 4 (Slotted node and slot configuration set). Node 𝑛 that hosts at least one slot is called a slotted node, and we denote the multiset of slots currently profiled on 𝑛 by 𝑆 (𝑛), where the slots in 𝑆 (𝑛) are non-overlapping. The residual Í 𝐺 − 𝑠 ∈𝑆 (𝑛) 𝑤 (𝑠) GPUs on 𝑛 have not yet been profiled as any slot, and a new slot is created over them only when an anchor is placed on 𝑛. The collection of all feasible slot profiling plans forms the slot configuration set
SlotConf :=
n
{𝑠 1, . . . , 𝑠𝑘 } 𝑠𝑖 ∈ {2, 4, 8} ∀ 𝑖,
𝑘 ∑︁
o 𝑠𝑖 ≤ 𝐺 ,
4.3.1 Common Notation. We write 𝜎 ∈ Σ for the current cluster state, D for the set of legal destinations where a single instance can be assigned, and M ★ for the space of finite migration lists. A destination 𝑑 ∈ D takes one of four forms: a slotted node where a new slot of the required width can be profiled, a slot vacancy of an anchored slot, a partial pool node, or an empty node waiting to be opened. A single migration is written as a pair (𝑖, 𝑑) that moves instance 𝑖 to destination 𝑑, and the update notation 𝜎 ⊕ 𝑀 means that the migrations in 𝑀 ∈ M ★ are applied to 𝜎 in sequence.
𝑖=1
(5) where 𝑆 (𝑛) ∈ SlotConf, ∀𝑛. Definition 5 (Pool node). A pool node is a node dedicated to 1-GPU instances. For a pool node 𝑛, we write 𝑃 (𝑛) ⊆ I =1 for the set of 1-GPU instances currently on 𝑛, with |𝑃 (𝑛)| ≤ 𝐺. A 1-GPU instance on a pool node is not acting as a filler but can be moved to the slot vacancy when necessary. Building on the definitions above, every node in the cluster falls into three mutually exclusive types: an empty node holds no instances, a slotted node whose 𝑆 (𝑛) ∈ SlotConf, and a pool node whose 𝑃 (𝑛) ⊆ I =1 . We accordingly collect these three labels into the node-type set T := { empty, pool, slotted },
COMPASS Algorithm
4.3.2 Place Operator. The placement operator carries the signature Place : Σ × I → D × M ★, which takes the current cluster state 𝜎 together with an arriving instance 𝑖 and returns the destination 𝑑 where 𝑖 is to be installed alongside the migration list 𝑀. If 𝑖 ∈ I ≥2 , the scheduler searches for a slotted node with at least 𝑤 ★ (𝑔𝑖 ) ∈ {2, 4, 8} free GPUs, or opens a fresh empty node if none exists; it then profiles a width-𝑤 ★ (𝑔𝑖 ) slot and
(6)
and write 𝑡 (𝑛) ∈ T for the type currently assigned to node 𝑛. This coarse classification underlies the formal definition of the feasible cluster state space Σ given below. 5
Yukai Zhou and Hongfan Wu
places 𝑖 as the anchor. When 𝑖 ∈ I FUF , the scheduler migrates up to 𝑤 ★ (𝑔𝑖 ) − 𝑔𝑖 1-GPU instances from the pool nodes as fillers, subject to filler availability in the pool. If 𝑖 ∈ I =1 , the scheduler places 𝑖 following a strict priority order: into an existing slot vacancy if one exists; otherwise into a partial pool node; and only resorts to a newly opened pool node when neither exists. This order lets the 1-GPU instance firstly mitigate existing fragmentation before activating any new slotted node.
4.3.4 Compact Operator. We denote the compaction operator by Compact : Σ → M ★, which runs after each job event, namely the arrival or departure of each DLT job. It performs consolidation via three sequential calls to a per-class subroutine BestFitDrain Within each invocation, BestFitDrain identifies the partial hosts currently holding class-C items, orders them by descending room so that the sparsest source is processed first, and migrates the items of that source one by one into the partial host whose remaining class-C room is the smallest among those still able to accept the migrated item. For the three concrete classes used by Compact, the pool pass takes 1-GPU instances as items and pool nodes as hosts with room 𝐺 − |𝑃 (𝑛)|, while the width-4 and width-2 passes take anchored slots of the corresponding width as items and slotted nodes as hosts with room Í ⌊𝐷 (𝑛)/4⌋ and ⌊𝐷 (𝑛)/2⌋ respectively, where 𝐷 (𝑛) = 𝐺 − 𝑠 ∈𝑆 (𝑛) 𝑤 (𝑠).
Pseudocode of Place(𝜎, 𝑖). Input: state 𝜎; arriving instance 𝑖 with demand 𝑔𝑖 Output: destination 𝑑 ∈ D; migration list 𝑀 ∈ M ★ 1: 𝑀 ← ∅ 2: if 𝑔𝑖 ≥ 2 then 3: 𝑤 ← 𝑤 ★ (𝑔𝑖 ) Í 4: Ncand ← { 𝑛 : 𝑡 (𝑛) = slotted, 𝐺 − 𝑠 ∈𝑆 (𝑛) 𝑤 (𝑠) ≥ 𝑤 } Í 5: if Ncand ≠ ∅ then 𝑛★ ← arg min𝑛∈ Ncand 𝐺 − 𝑠 ∈𝑆 (𝑛) 𝑤 (𝑠) 6: else pick any empty node 𝑛★ and set 𝑡 (𝑛★) ← slotted 7: profile a fresh slot 𝑠 ★ of width 𝑤 on 𝑛★; set 𝑎(𝑠 ★) ← 𝑖; 𝑑 ← 𝑠 ★ 8: 𝑟 ← 𝑤 − 𝑔𝑖 9: if 𝑟 > 0 then draw up to 𝑟 1-GPU instances {𝑓1, . . . , 𝑓𝑘 } from pool nodes; 𝑀 ← {(𝑓ℓ , 𝑠 ★) : ℓ = 1, . . . , 𝑘 } 10: else (𝑔𝑖 = 1) 11: if ∃ 𝑠 with 𝑔𝑎 (𝑠 ) + |𝐹 (𝑠)| < 𝑤 (𝑠) then 𝑑 ← 𝑠 12: else if ∃ 𝑛 with 𝑡 (𝑛) = pool and |𝑃 (𝑛)| < 𝐺 then 𝑑 ← 𝑛 13: else pick any empty node 𝑛 0 ; set 𝑡 (𝑛 0 ) ← pool; 𝑑 ← 𝑛 0 14: return (𝑑, 𝑀)
Pseudocode of Compact(𝜎). Input: state 𝜎 Output: migration list 𝑀 ∈ M ★ 1: 𝑀 ← ∅ 2: for each class C ∈ ⟨pool, w4, w2⟩ do 3: N ← { 𝑛 : 0 < count C (𝑛) < cap C (𝑛) } 4: sort N by room C (·) in descending order 5: while |N | ≥ 2 do 6: 𝑛 src ← head(N ); progress ← false 7: for each class-C item 𝑥 on 𝑛 src do 8: S ← { 𝑛 ∈ N \ {𝑛 src } : room C (𝑛) ≥ size(𝑥) } 9: if S = ∅ then break 10: 𝑛 dst ← arg min𝑛∈ S room C (𝑛) 11: migrate 𝑥 from 𝑛 src to 𝑛 dst ; append to 𝑀; progress ← true 12: end for 13: if 𝑛 src has no class-C item left then remove 𝑛 src from N 14: if not progress then break 15: end while 16: end for 17: return 𝑀
4.3.3 Remove Operator. The departure operator carries the signature Remove : Σ × I → M ★, which returns the migrations triggered when instance 𝑖 departs from state 𝜎. If 𝑖 ∈ I ≥2 , it serves as the anchor 𝑎(𝑠) of slot 𝑠. The operator dissolves 𝑠 by releasing 𝑤 (𝑠) GPUs, and migrates each filler in 𝐹 (𝑠) into the pool node through the same 1GPU rule that Place applies to it; the migration M = ∅ when 𝑎(𝑠) ∈ I FF , since 𝐹 (𝑠) = ∅ in that case. If 𝑖 ∈ I =1 , the operator releases 𝑖 from its current location, which is either on a slotted node or a pool node. In the former case, it additionally migrates another 1-GPU instance from the pool to keep the slot saturated.
Notation. For class C ∈ {pool, w4, w2}, count C (𝑛) is the number of class-C items currently on 𝑛, cap C (𝑛) is the maximum number of class-C items that 𝑛 can hold, room C (𝑛) = cap C (𝑛) − count C (𝑛), and size(𝑥) = 1 in all three classes. The local variables 𝑛 src and 𝑛 dst denote, respectively, the source node from which an item is migrated and the destination node into which it is migrated within the current best-fit drain pass.
Pseudocode of Remove(𝜎, 𝑖). Input: state 𝜎; departing instance 𝑖 Output: migration list 𝑀 ∈ M ★ 1: 𝑀 ← ∅ 2: if 𝑔𝑖 ≥ 2 then (𝑖 is an anchor) 3: 𝑠 ← the slot whose anchor is 𝑖 4: for each 𝑓 ∈ 𝐹 (𝑠) do 5: choose destination 𝑑 𝑓 for 𝑓 by the 1-GPU rule of Place 6: append (𝑓 , 𝑑 𝑓 ) to 𝑀 7: end for 8: dissolve 𝑠 and release its 𝑤 (𝑠) GPUs on the host node 9: else (𝑔𝑖 = 1) 10: detach 𝑖 from its current slot vacancy or pool node 11: return 𝑀
4.4
Theoretical Guarantees
We now state the main theoretical properties of the COMPASSABS scheduler. Proposition 1 validates that COMPASS confines the cluster state to the ABS domain Σ throughout. Theorem 1 is the main claim of this section and shows that COMPASS-ABS keeps SIF𝜋 (𝑡) bounded by 2/𝑁 whenever the 6
COMPASS-ABS
Algorithm 1 The COMPASS algorithm: online event handler that composes the Place, Remove, and Compact operators to evolve the cluster state 𝜎 inside the compact ABS Σ.
Proposition 2 (Operational Complexity of COMPASS). The three operators that compose COMPASS satisfy
Input: initial state 𝜎0 ∈ Σ; online event stream ⟨𝑒 1, 𝑒 2, . . .⟩, in which each event 𝑒𝑘 is either the arrival or the departure of a DLT job 𝑗 with 𝑤 𝑗 instances Output: evolving state 𝜎 updated after every event
T (Remove) = 𝑂 (1),
T (Place) = 𝑂 (log 𝑁 ),
where 𝑁 denotes the number of nodes in the cluster.
1: 𝜎 ← 𝜎0 2: for each event 𝑒 in arrival order do 3: if 𝑒 is the arrival of job 𝑗 then 4: for 𝑘 := 1, 2, . . . , 𝑤 𝑗 do 5: 𝑖 ← the 𝑘-th instance of 𝑗 6: (𝑑, 𝑀) ← Place(𝜎, 𝑖) 7: install 𝑖 at 𝑑 and then apply 𝑀 to 𝜎 8: end for 9: 𝜎 ← 𝜎 ⊕ Compact(𝜎) 10: else if 𝑒 is the departure of job 𝑗 then 11: for 𝑘 := 1, 2, . . . , 𝑤 𝑗 do 12: 𝑖 ← the 𝑘-th instance of 𝑗 13: 𝑀 ← Remove(𝜎, 𝑖) 14: remove 𝑖 from its current location and then apply 𝑀 to 𝜎 15: end for 16: 𝜎 ← 𝜎 ⊕ Compact(𝜎) 17: end if 18: end for 19: return 𝜎
5
Experimental Evaluation
5.1
Testbed
We evaluate our scheduler in both a physical cluster and a simulation system. Our implementation is available at https: //anonymous.4open.science/r/COMPASSABSF02A/. For the physical experiments, our scheduler runs as a controller process that launches and migrates real PyTorch training jobs on a small cluster of four servers each equipped with eight NVIDIA A100-40GB GPUs, and each migration is realized through a checkpoint-and-restart protocol on the actual training processes. For the simulation experiments, we develop an eventdriven simulator in Python to reproduce DLT job production in a shared GPU cluster. To faithfully reflect production behavior, our simulator reproduces the latency incurred by the checkpoint-based migration mechanism[12, 50]. 5.2
Cluster Configuration
To validate our scheduler under both contended and loose resource regimes, we replay real traces (or deploy realistic jobs) on a range of cluster scales defined as follows. Let J[𝑇1,𝑇2 ] represent the jobs submitted in a chosen window [𝑇1,𝑇2 ], and let ∑︁ 𝐷 (𝑡) = 𝐺 𝑗 ⊮ 𝑎𝑗 ≤ 𝑡 < 𝑎𝑗 + 𝜏𝑗 (12)
workload satisfies a realistic composition condition. Proposition 2 characterises the per-operator computational complexity of the COMPASS algorithm. Detailed proofs of all three results are deferred to Appendix B. Proposition 1 (State-Space Invariance). For any initial state 𝜎0 ∈ Σ and any event sequence of job arrivals and job departures, every state produced by the COMPASS algorithm (Algorithm 1) remains in Σ.
𝑗 ∈ J[𝑇1 ,𝑇2 ]
denote their concurrent GPU demand, with 𝐺 𝑗 = 𝑊 𝑗 𝑔 𝑗 . We define the window’s 𝜂-th percentile demand 𝑝𝜂 as the smallest level ℓ that 𝐷 stays below for at least an 𝜂 fraction of its support. The cluster for this window is then sized at 𝑁 (𝜂) = max 𝑝𝜂 /8 , 𝑁 maxjob (13)
Theorem 1 (Compactness under the Workload Composition Condition). Let 𝑛𝑔 (𝑡) denote the number of active instances of per-GPU demand 𝑔 ∈ {1, . . . , 8} at time 𝑡, write 𝑛 total (𝑡) = Í8 𝑔=1 𝑛𝑔 (𝑡) for the total active instance count, and let 𝑝𝑔 (𝑡) := 𝑛𝑔 (𝑡)/𝑛 total (𝑡) denote the per-class instance share. Suppose that at every time 𝑡 the workload composition satisfies the Workload Composition Condition 𝑝 1 (𝑡) ≥ 𝑝 3 (𝑡) + 3 𝑝 5 (𝑡) + 2 𝑝 6 (𝑡) + 𝑝 7 (𝑡).
(11)
T (Compact) = 𝑂 (𝑁 ),
nodes, where 𝑁 maxjob is the minimum node count required to host the largest single job in J[𝑇1,𝑇2 ] under the intra-node constraint and gang scheduling requirement.
(9)
5.3
Then in every cluster state 𝜎 (𝑡) produced by Algorithm 1 in response to the online event stream, at most one slotted node is non-fully-packed and at most one pool node is non-fullypacked, and consequently the online placement produced by COMPASS-ABS satisfies 2 SIF𝜋 (𝑡) ≤ , ∀𝑡 ≥ 0 (10) 𝑁 where 𝑁 is the total number of nodes in the cluster.
Trace
Our simulation is conducted on two real production traces, Venus[15] and GFS[7]. Both traces record the number of instances, per-instance GPU demand, submission time, and duration of each job. As an initial preprocessing step, we retain only the DLT jobs that consist of homogeneous instances with identical integer GPU demand. For the physical deployment, we synthesize a DLT trace (Phys-Mix) spanning CV[6, 14], NLP[5], LLM[39], recommender system[11], 7
Yukai Zhou and Hongfan Wu
Average Job Completion Time (AJCT). The mean completion time across all DLT jobs submitted:
and multi-modal[38] training tasks, whose resource demand characteristics are aligned with those observed in the two traces above.
𝑀
AJCT = 5.4
Comparison
We compare our scheduler against the six state-of-the-art methods.
A higher AGU indicates that the scheduler converts more of the available GPU capacity into productive work, which is critical under heavy GPU demand.
We evaluate COMPASS-ABS and the baselines using three metrics that together capture how effectively each scheduler mitigates the consequences of GPU fragmentation. Among them, AFR (and the underlying SIF) is a diagnostic quantity we introduce in this work to measure the cluster fragmentation state; others are key performance indicators for both users and vendors. Together they provide a complete assessment of scheduler efficiency. To focus on contention-induced behavior, we restrict the metrics indicating resource fragmentation degree and GPU utilization to the peak-demand period (14)
that is, the time within the observed window 𝑇 when the waiting queue 𝑄 (𝑡) is non-empty. Average Fragmentation Rate (AFR). The time-averaged cluster fragmentation level during 𝑇peak , where the instantaneous fragmentation SIF(𝑡) follows the definition in (2): AFR =
1 |𝑇peak |
Evaluation
6.1
Overall Comparison
6.2
Cluster Intensity Sensitivity
To verify that the superiority of COMPASS-ABS over the six baselines is stable across different cluster resource pressures, we sweep the cluster-scaling parameter 𝜂 ∈ {0.85, 0.90, 0.95} on the GFS trace, which carries the largest job count and aggregate GPU demand among the three traces and therefore offers the most discriminative regime for scheduler comparison. Across all three intensity levels, COMPASS-ABS dominates all baselines on every metric reported in Fig. 2, with its AFR lying within the narrow band of 0.0023 to 0.0026
∫ SIF(𝑡) 𝑑𝑡 .
6
We first evaluate the end-to-end performance of COMPASSABS against all baselines under a fixed resource regime (𝜂 = 0.90). The comparison spans two real production traces replayed in our simulator and Phys-Mix deployed on our physical cluster, with results reported in Fig. 1. Overall, COMPASS-ABS dominates the six baselines on every (metric, trace) pair. Concretely, COMPASS-ABS reduces AJCT by at least 212s, 135s and 736s and lifts AGU by at least 0.7%, 2% and 16% over the strongest baseline on the Venus, GFS and Phys-Mix traces respectively, while simultaneously attaining the lowest AFR on all three traces with the measured AFR staying below 𝑁2 , which matches the theoretical bound proved in Section 4.4. COMPASS-ABS, DRR and FFT all support migration-driven defragmentation, yet ours exceeds DRR and FFT for a structural reason: our migration policy is driven by the COMPASS algorithm to maintain the compactness of the predefined feasible state domain ABS, and is tightly coupled with the placement strategy rather than treated as a separate phase at fixed interval.
Metrics
𝑇peak = { 𝑡 ∈ 𝑇 | 𝑄 (𝑡) ≠ ∅ },
(16)
where 𝐶𝑖 is the completion time of job 𝐽𝑖 , equivalently defined as the sum of its queueing time in the waiting queue, its training time on the assigned GPUs and latency caused by migration, and 𝑀 is the total number of jobs evaluated. A lower AJCT indicates that the scheduler admits and finishes jobs more efficiently, which directly shortens the user-perceived turnaround of DLT workloads. Average GPU Utilization (AGU). The time-averaged fraction of active GPUs in the cluster during 𝑇peak : ∫ 1 GU(𝑡) 𝑑𝑡, GU(𝑡) ∈ [0, 1]. (17) AGU = |𝑇peak | 𝑇peak
• GFS[7]: places each job’s instances on the nodes whose remaining GPU capacity most closely matches the perinstance demand, following a best-fit policy. • FGD[45]: selects the placement that minimizes the resulting increase in fragmentation they define. • CAFGD[24]: combines its lifecycle-aware fragmentation measure with a wait-for-peak admission policy • MCG[48]: builds on FGD’s fragmentation-gradient principle and additionally estimates the demand distribution of pending jobs to reorder scheduling priorities. • FFT[30]: globally reorganizes the placement of all running jobs by solving an ILP at the start of each round, and schedules arriving jobs within each round using a best-fit. • DRR[49]: periodically migrates the jobs on the lowestutilization node onto high-utilization target nodes at the start of each reschedule cycle, and places arriving jobs using a DRL policy trained via imitation learning from a best-fit heuristic. 5.5
1 ∑︁ 𝐶𝑖 , 𝑀 𝑖=1
(15)
𝑇peak
A lower AFR indicates that the scheduler keeps the cluster in a less fragmented cluster state under contention. 8
COMPASS-ABS
Figure 1. Overall comparison across three DLT workload traces (𝜂 = 0.90).
Figure 2. Sensitivity to cluster resource intensity on the GFS trace 𝜂 ∈ {0.85, 0.90, 0.95}. and its AGU staying above 0.957, and neither metric exhibits any appreciable sensitivity to resource pressure across the three regimes. By contrast, the AJCT advantage of COMPASS-ABS over the strongest baseline widens monotonically as the cluster becomes tighter, growing from 74s at 𝜂 = 0.95 to 135s at 𝜂 = 0.90 and ultimately to 201s at 𝜂 = 0.85. The mechanism behind is that fragmentation-induced queueing blockage grows increasingly severe as the cluster tightens: under tight resources, fragmented capacity is far less likely to be reclaimed by the natural departure of running jobs, whereas under loose resources such fragments are readily absorbed. COMPASS-ABS adaptively eliminates fragmentation in real
time and thereby recovers this otherwise-trapped capacity, so its fragmentation-aware advantage translates into the largest AJCT reduction when the cluster is at its tightest. 6.3
Robustness to Workload Composition
To verify that the superiority of COMPASS-ABS over the six baselines is also stable across different per-instance GPUdemand distributions, we select three days whose compositions span the widest pairwise discrepancy across our traces (Table 2). Across all three compositions, COMPASS-ABS dominates every baseline on every metric reported in Fig. 3: its AFR is confined within [0.002, 0.030] against the baselines’ wider [0.058, 0.324] band, its AGU stays above 0.89 9
Yukai Zhou and Hongfan Wu
Table 3. Top-1 ranking frequency of COMPASS-ABS across WCC coverage 𝜌 buckets, grouped by (day, 𝜂) pairs.
against the baselines’ [0.77, 0.90] range, and its AJCT leads the strongest baseline by 1,643 s on Venus day 92, 1,431 s on GFS day 58 and 145 s on GFS day 26. This robustness arises from the fact that the slot-pool layout exploits the dominance of the fragmentation-friendly {2, 4, 8}-GPU widths over the fragmentation-unfriendly {3, 5, 6, 7}-GPU widths in real DLT workloads, so the anchor-filler mechanism saturates the slots and the COMPASS algorithm confines the cluster state within a compact ABS configuration regardless of how the per-instance GPU-demand distribution shifts. The absolute AJCT lead is the largest on Venus day 92 because most of the JCT on this short-job workload is determined by scheduling decisions, whereas it shrinks on the two GFS days because their longer base runtimes dominate the JCT and leave a smaller scheduling-controllable share for any scheduler to optimize; even so, COMPASS-ABS still ranks first against other baselines.
Trace 𝜌 Bucket
|𝐷 |
1.0
487
[0.99, 1)
26
[0.9, 0.99)
25
[0.7, 0.9)
11
[0.1, 0.7)
10
[0, 0.1)
5
Total
564
1.0
552
Venus
GFS
Table 2. Workload Composition of the Three Selected Days
1 GPU 2–7 GPU 8 GPU
Venus Day 92 GFS Day 58 GFS Day 26
0.73 0.57 0.43
0.06 0.04 0.09
JCT
AGU
459 (94.3%) 24 (92.3%) 22 (88.0%) 11 (100%) 10 (100%) 5 (100%) 531 (94.1%)
383 (78.6%) 18 (69.3%) 16 (64.0%) 8 (72.7%) 8 (80.0%) 5 (100%) 453 (80.3%)
404 (83.0%) 20 (76.9%) 16 (64.0%) 9 (81.8%) 8 (80.0%) 5 (100%) 462 (81.9%)
552 (100%)
537 529 (97.3%) (95.9%)
buckets, while on AJCT and AGU it leads for at least 64% in every WCC-violating bucket and for 100% in the lowestcoverage bucket [0, 0.1). Aggregated across all 564 Venus days, the top-1 frequency reaches 94.1% on AFR, 80.3% on AJCT, and 81.9% on AGU, and on GFS 100%, 97.3%, and 95.9% respectively. COMPASS-ABS thus retains its advantage on all three metrics even outside this regime.
Instance Size Ratio Day
AFR
0.21 0.39 0.48
6.5
6.4 Workload Composition Condition: Coverage and Robustness on Violating Days
Robustness to Migration Cost
Empirical migration latencies in DLT clusters span the range of 1s to 10s, depending on the checkpoint-and-restore implementation, the network topology and the model size [13, 30, 50, 51]; on our own physical cluster the average migration latency we measure is approximately 8s. We therefore verify that COMPASS-ABS maintains its superiority across the realistic range by sweeping the per-migration cost parameter 𝑐 ∈ {1, . . . , 10} s on the GFS and Venus traces. As shown in Fig. 4, every one of the six panels exhibits essentially flat curves as the per-migration cost 𝑐 sweeps from 1 s to 10 s, because the three migration-capable schedulers each issue at most a small number of migrations per job and the cumulative cost contribution to any metric therefore stays well below one second per job even at 𝑐 = 10 s. More importantly, COMPASS-ABS attains the lowest AFR, the lowest AJCT and the highest AGU at every 𝑐 in the swept range on both GFS and Venus, including the 8 s neighborhood that corresponds to the latency we measure on our own cluster, so the end-to-end advantage of COMPASS-ABS is insulated against any realistic increase in the per-migration cost.
The performance guarantee of COMPASS-ABS rests on Theorem 1, which assumes the cluster state satisfies the Workload Composition Condition (WCC) at every scheduling tick. We therefore test how often the WCC holds and whether COMPASS-ABS keeps its advantage on days where it does not hold throughout. We replay every Venus and GFS day, measure each day’s WCC coverage 𝜌, the fraction of its scheduling horizon during which the WCC is satisfied, bucket the days by 𝜌, and for each bucket and each metric in {AFR, AJCT, AGU} count the days on which COMPASS-ABS ranks top-1 among the seven evaluated schedulers (Table 3). The WCC is empirically dominant on both traces. On Venus, 487 of the 564 replayed days (86.3%) satisfy it throughout the entire horizon, and a further 51 days (9.0%) satisfy it for at least 90% of the horizon; on GFS it holds across the full horizon on all 552 days. The WCC-satisfying regime is thus the principal operating regime of production deployments rather than a corner case. Even on the Venus days where the WCC does not hold throughout, the top-1 frequency of COMPASS-ABS closely tracks that on the 𝜌 = 1 days. Across the five coverage buckets with 𝜌 < 1, it leads on AFR for 100% of the days in the three lower-coverage buckets [0, 0.1), [0.1, 0.7), and [0.7, 0.9) and for at least 88% in the two higher-coverage
6.6
Case Study of Fragmentation Dynamics
We zoom into the 21:00–22:30 window of GFS day 113 under 𝜂 = 0.95 to expose the time-resolved fragmentation mechanism, with Fig. 5, Fig. 6 and Fig. 7 reporting the dynamic 10
COMPASS-ABS
Figure 3. Robustness to workload composition on three representative days (Venus Day 92, GFS Day 58, GFS Day 26) .
Figure 5. Dynamic number of avoidable partial nodes (𝑁 · SIF) by seven schedulers on GFS day 113 (𝜂 = 0.95). Figure 4. Robustness to per-migration cost on the GFS and Venus trace, 𝑐 ∈ [1, 10] s, 𝜂 = 0.90. keeps 𝑁 · SIF bounded by 2 throughout, so its total blocking accumulates to only about 10 minutes, and although 72.9% of that blocking is technically fragmentation-induced, the compact ABS layout together with its slot-pool migration mechanism dispatches every such blockage within seconds and never lets fragmentation translate into long-period queue blocking or low utilisation.
𝑁 · SIF (the total number of avoidable partial nodes), GPU utilisation and fully-empty node counts respectively. All six practical baselines remain in continuous blocking throughout the window, with five of them attributing 100% of the blocking to fragmentation and DRR still 94.6%, as verified by the aggregate idle GPU count strictly exceeding the head-ofline demand. Over 90% of the blocked jobs carry 𝑔𝑖 = 8 with 𝑤𝑖 > 30, so the dominant blocking factor is the requirement for at least 𝑤𝑖 fully empty 8-GPU nodes. On the fragmentation side, the five non-migration baselines settle into a wide 60–80 partial-node band while FFT confines itself to a 25–50 band through periodic global migration, but both ranges leave only 20–30 fully empty nodes against the 𝑤𝑖 > 30 contiguous demand and trap GPU utilisation within 0.8–0.9 for the entire window. COMPASS-ABS
7
Related Work
Most prior work on DLT job scheduling overlooks the quantification of resource fragmentation, asserting that they mitigate fragmentation via tight packing, without providing a concrete metric[27, 40, 47]. FGD[45] was the first to propose a statistical measure that estimates the expected instance capacity that the remaining resources can accommodate, given prior knowledge of the resource demand distribution. Subsequent works refined this formulation on top 11
Yukai Zhou and Hongfan Wu
of FGD: CAFGD[24] decomposed the demand probability into weighted long-term and short-term distributions, while MCG[48] incorporated load balance into the fragmentation metric. However, all of these approaches rely on historical workload information. Numerous studies aimed to reduce DLT job completion time and improve resource utilization by mitigating fragmentation. Existing schedulers can be broadly categorized into two types of approaches. Non-migration schedulers: These methods formulated scheduling as a multi-dimensional binpacking problem[3, 8, 16, 42, 52]. ElasticFlow[9], Synergy[31], and GFS[7] adopted a best-fit strategy that dynamically places jobs on the node leaving the fewest idle GPUs. FGD[45], CAFGD[24], and MCG[48] scheduled jobs based on their respective fragmentation measures, preferring placements that minimize the increase between pre- and post-scheduling fragmentation. These methods cannot reduce fragmentation that has already accumulated in the cluster. Migration-supporting schedulers: To address accumulated fragmentation, schedulers such as Gavel[33], Sia[21], and RASA[2] modeled the problem as a linear program computed by numerical solvers. However, the resulting time complexity and additional latency induced by frequent migrations are prohibitive for real-time scheduling in large-scale clusters[46]. To improve
practicality, Hops[43], FFT[30] and DRR[49] employed a round-based migration strategy that performs global defragmentation by relocating running jobs to placements that incur less fragmentation. Nevertheless, these methods cannot correct fragmentation introduced within a round, leaving the cluster in a degraded state until the next defragmentation cycle.
8
Conclusion
In this paper, we have presented Scheduler-Induced Fragmentation (SIF) for quantifying resource fragmentation together with COMPASS-ABS, a scheduler that reduces fragmentation in shared GPU clusters for DLT jobs. From the partial-nodes perspective, SIF removes the dependence on prior knowledge of the workload trace that earlier statistical metrics require, and isolates the portion of observed fragmentation resulting from scheduling policy. Building on this measure, COMPASSABS confines the cluster state to a structured feasible domain called the Anchor-Based Space (ABS), whose construction fully exploits the alignment between the GPU-demand profile of DLT instances and the cluster topology, so that the accompanying COMPASS algorithm can dynamically maintain compactness inside ABS and keep SIF uniformly bounded by 2/𝑁 whenever the Workload Composition Condition holds. We validate our scheduler’s performance through large-scale simulation on production traces and through physical-cluster deployment with a synthetic DLT workload, both of which show that COMPASS-ABS attains higher GPU utilization and substantially shorter job completion time in the queue than the state-of-the-art baselines even when WCC is violated. Looking ahead, we identify three promising directions for extending COMPASS-ABS. First, we plan to generalize our scheduler to jointly handle both deep learning training and inference jobs in a shared GPU cluster, where the heterogeneous latency requirements and resource profiles of the two workload types pose additional scheduling challenges. Second, when migrating jobs to amend fragmentation, the current design treats all jobs uniformly; a natural extension is to incorporate job-level priorities into the migration decision, selecting victims in a manner that respects Service Level Objectives (SLOs) and avoids penalizing high-priority workloads. Moreover, we further discuss how to extend our scheduler to the next-generation clusters with larger NVLink domains in Appendix D.
Figure 6. Dynamic GPU utilization by seven schedulers on GFS day 113 (𝜂 = 0.95).
References [1] Advanced Micro Devices. 2024. AMD Instinct MI300X Platform Data Sheet. Data sheet. https://www.amd.com/content/dam/amd/en/ documents/instinct-tech-docs/data-sheets/amd-instinct-mi300xplatform-data-sheet.pdf Accessed: 2026-06-09. [2] Zhe Chen, Fan Jiang, Bin Chen, Yu Li, Yi Zhang, Chao Huang, Run Yang, Fei Jiang, Jun Chen, Wei Xiang, Gang Cheng, Ran Shi, Nan Ma, Wenjie Zhang, and Tao Zhang. 2024. Resource Allocation with Service Affinity in Large-Scale Cloud Environments. In Proceedings
Figure 7. Dynamic free nodes by seven schedulers on GFS day 113 (𝜂 = 0.95). 12
COMPASS-ABS
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’16). IEEE, 770–778. doi:10.1109/CVPR.2016.90 [15] Qinghao Hu, Peng Sun, Shengen Yan, Yonggang Wen, and Tianwei Zhang. 2021. Characterization and Prediction of Deep Learning Workloads in Large-Scale GPU Datacenters. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’21). ACM, 1–15. doi:10.1145/3458817.3476223 [16] Dawei Huang, Peng Du, Chuanwen Zhu, Hao Zhang, and Xudong Liu. 2015. Multi-Resource Packing for Job Scheduling in Virtual Machine Based Cloud Environment. In Proceedings of the IEEE Symposium on Service-Oriented System Engineering (SOSE ’15). IEEE, 216–221. doi:10. 1109/SOSE.2015.30 [17] Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V. Le, Yonghui Wu, and Zhifeng Chen. 2019. GPipe: Efficient Training of Giant Neural Networks Using Pipeline Parallelism. In Advances in Neural Information Processing Systems (NeurIPS ’19), Vol. 32. 103–112. https://proceedings.neurips.cc/paper/2019/hash/ 093f65e080a295f8076b1c5722a46aa2-Abstract.html [18] Huawei Technologies. 2021. Atlas 800 Training Server (Model 9000) Data Sheet. Data sheet. https://www.cmc.ca/wp-content/uploads/ 2021/06/DatasheetAtlas800.pdf Accessed: 2026-06-09. [19] Changho Hwang, Wei Cui, Yifan Xiong, Ziyue Yang, Ze Liu, Han Hu, Zilong Wang, Rafael Salas, Jithin Jose, Prabhat Ram, Joe Chau, Peng Cheng, Fan Yang, Mao Yang, and Yongqiang Xiong. 2023. Tutel: Adaptive Mixture-of-Experts at Scale. In Proceedings of Machine Learning and Systems (MLSys ’23). [20] Intel Corporation. 2024. Intel Gaudi 3 AI Accelerator HLB-325 Baseboard Product Brief. Product brief. https: //www.intel.com/content/www/us/en/content-details/817489/intelgaudi-3-ai-accelerator-hlb-325-baseboard-product-brief.html Accessed: 2026-06-09. [21] Suhas Jayaram Subramanya, Daiyaan Arfeen, Shouxu Lin, Aurick Qiao, Zhihao Jia, and Gregory R. Ganger. 2023. Sia: Heterogeneityaware, Goodput-optimized ML-cluster Scheduling. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP ’23). ACM, 642–657. doi:10.1145/3600006.3613175 [22] Myeongjae Jeon, Shivaram Venkataraman, Amar Phanishayee, Junjie Qian, Wencong Xiao, and Fan Yang. 2019. Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC ’19). USENIX Association, 947–960. [23] Ziheng Jiang, Haibin Lin, Yinmin Zhong, Qi Huang, Yangrui Chen, Zhi Zhang, Yanghua Peng, Xiang Li, Cong Xie, Shibiao Nong, Yulu Jia, Sun He, Hongmin Chen, Zhihao Bai, Qi Hou, Shipeng Yan, Ding Zhou, Yiyao Sheng, Zhuo Jiang, Haohan Xu, Haoran Wei, Zhang Zhang, Pengfei Nie, Leqi Zou, Sida Zhao, Liang Xiang, Zherui Liu, Zhe Li, Xiaoying Jia, Jianxi Ye, Xin Jin, and Xin Liu. 2024. MegaScale: Scaling Large Language Model Training to More Than 10,000 GPUs. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI ’24). USENIX Association, 745–760. [24] Huazheng Lao, Rui Xu, Long Chen, and Jinquan Zhang. 2025. CAFGD: Reduce Fragmentation in Large-Scale Multi-tenant Clusters for GPU Sharing Workloads. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS ’25). IEEE, 133–143. doi:10. 1109/ICDCS63083.2025.00022 [25] Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. 2021. GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding. In Proceedings of the International Conference on Learning Representations (ICLR ’21).
of the IEEE International Conference on Data Engineering (ICDE ’24). IEEE, 5280–5293. doi:10.1109/ICDE60146.2024.00397 [3] Zhiyuan Chen, Xin Zhao, Chenglu Zhi, and Jianwei Yin. 2023. DeepBoot: Dynamic Scheduling System for Training and Inference Deep Learning Tasks in GPU Cluster. IEEE Transactions on Parallel and Distributed Systems 34, 9 (2023), 2553–2567. doi:10.1109/TPDS.2023. 3293835 [4] Arnab Choudhury, Yang Wang, Tuomas Pelkonen, Kutta Srinivasan, Abha Jain, Shenghao Lin, Delia David, Siavash Soleimanifard, Michael Chen, Abhishek Yadav, Ritesh Tijoriwala, Denis Samoylov, and Chunqiang Tang. 2024. MAST: Global Scheduling of ML Training across Geo-Distributed Datacenters at Hyperscale. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI ’24). USENIX Association, 563–580. [5] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT ’19). 4171–4186. [6] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. 2021. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. In Proceedings of the International Conference on Learning Representations (ICLR ’21). [7] Jiangfei Duan, Shenggui Xu, Shilong Qian, et al. 2026. GFS: A Preemption-aware Scheduling Framework for GPU Clusters with Predictive Spot Instance Management. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1 (ASPLOS ’26). ACM, 117–131. doi:10.1145/3760250.3762231 [8] Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. 2014. Multi-Resource Packing for Cluster Schedulers. In Proceedings of the 2014 ACM Conference on SIGCOMM (SIGCOMM ’14). ACM, 455–466. doi:10.1145/2619239.2626334 [9] Diandian Gu, Yihao Zhao, Yinmin Zhong, Yifan Xiong, Zhenhua Han, Peng Cheng, Fan Yang, Gang Huang, Xin Jin, and Xuanzhe Liu. 2023. ElasticFlow: An Elastic Serverless Training Platform for Distributed Deep Learning. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (ASPLOS ’23). ACM, 266–280. doi:10.1145/3575693. 3575721 [10] Juncheng Gu, Mosharaf Chowdhury, Kang G. Shin, Yibo Zhu, Myeongjae Jeon, Junjie Qian, Hongqiang Harry Liu, and Chuanxiong Guo. 2019. Tiresias: A GPU Cluster Manager for Distributed Deep Learning. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI ’19). USENIX Association, 485–500. [11] Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017. DeepFM: A Factorization-Machine based Neural Network for CTR Prediction. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI ’17). 1725–1731. [12] Tanmaey Gupta, Sanjeev Krishnan, Rituraj Kumar, Abhishek Vijeev, Bhargav Gulavani, Nipun Kwatra, Ramachandran Ramjee, and Muthian Sivathanu. 2024. Just-in-time Checkpointing: Low Cost Error Recovery from Deep Learning Training Failures. In Proceedings of the Nineteenth European Conference on Computer Systems (EuroSys ’24). ACM, 1110–1125. doi:10.1145/3627703.3650085 [13] Jingoo Han, Mustafa Rafique, Luna Xu, Ali R. Butt, Seung-Hwan Lim, and Sudharshan Vazhkudai. 2020. MARBLE: A Multi-GPU Aware Job Scheduler for Deep Learning on HPC Systems. In Proceedings of the IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGRID ’20). IEEE, 272–281. doi:10.1109/CCGrid49817. 2020.00-66
13
Yukai Zhou and Hongfan Wu
[26] Ang Li, Shuaiwen Leon Song, Jieyang Chen, Jiajia Li, Xu Liu, Nathan R. Tallent, and Kevin J. Barker. 2020. Evaluating Modern GPU Interconnect: PCIe, NVLink, NV-SLI, NVSwitch and GPUDirect. IEEE Transactions on Parallel and Distributed Systems 31, 1 (2020), 94–110. doi:10.1109/TPDS.2019.2928289 [27] Jiamin Li, Hong Xu, Yibo Zhu, Zherui Liu, Chuanxiong Guo, and Cong Wang. 2023. Lyra: Elastic Scheduling for Deep Learning Clusters. In Proceedings of the Eighteenth European Conference on Computer Systems (EuroSys ’23). ACM, 835–850. doi:10.1145/3552326.3587445 [28] Shen Li, Yanli Zhao, Rohan Varma, Omkar Salpekar, Pieter Noordhuis, Teng Li, Adam Paszke, Jeff Smith, Brian Vaughan, Pritam Damania, and Soumith Chintala. 2020. PyTorch Distributed: Experiences on Accelerating Data Parallel Training. Proceedings of the VLDB Endowment 13, 12 (2020), 3005–3018. doi:10.14778/3415478.3415530 [29] Meta Platforms. 2022. Grand Teton: Meta’s Next-Generation AI Platform. Open Compute Project Global Summit announcement. https://engineering.fb.com/2022/10/18/open-source/ocpsummit-2022-grand-teton/ Accessed: 2026-06-09. [30] Zizhao Mo, Huanle Xu, and Wing Cheong Lau. 2025. Fast and Fair Training for Deep Learning in Heterogeneous GPU Clusters. In Proceedings of the 39th ACM International Conference on Supercomputing (ICS ’25). ACM, 324–338. doi:10.1145/3721145.3728488 [31] Jayashree Mohan, Amar Phanishayee, Janardhan Kulkarni, and Vijay Chidambaram. 2022. Looking beyond GPUs for DNN Scheduling on Multi-Tenant Clusters. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI ’22). USENIX Association, 579–596. [32] Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R. Devanur, Gregory R. Ganger, Phillip B. Gibbons, and Matei Zaharia. 2019. PipeDream: Generalized Pipeline Parallelism for DNN Training. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP ’19). ACM, 1–15. doi:10.1145/3341301.3359646 [33] Deepak Narayanan, Keshav Santhanam, Fiodar Kazhamiaka, Amar Phanishayee, and Matei Zaharia. 2020. Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI ’20). USENIX Association, 481–498. [34] Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, Amar Phanishayee, and Matei Zaharia. 2021. Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’21). ACM, 1–15. doi:10.1145/3458817.3476209 [35] NVIDIA Corporation. 2017. NVIDIA DGX-1 with Tesla V100 System Architecture. Technical Report. NVIDIA Corporation. https://images.nvidia.com/content/pdf/dgx1-v100-systemarchitecture-whitepaper.pdf [36] NVIDIA Corporation. 2026. NVIDIA DGX SuperPOD. Product page. https://www.nvidia.com/en-us/data-center/dgx-superpod/ Accessed: 2026-04-30. [37] Open Compute Project. 2023. OAI Universal Baseboard (UBB) Base Specification, Revision 2.0. Open Compute Project Foundation specification. https://www.opencompute.org/documents/oai-ubb-basespecification-r2-0-v1-0-20230919-pdf Accessed: 2026-06-09. [38] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021. Learning Transferable Visual Models From Natural Language Supervision. In Proceedings of the International Conference on Machine Learning (ICML ’21). 8748–8763. [39] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language Models are Unsupervised Multitask Learners. Technical Report. OpenAI.
[40] Sudarsanan Rajasekaran, Manya Ghobadi, and Aditya Akella. 2024. CASSINI: Network-Aware Job Scheduling in Machine Learning Clusters. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI ’24). USENIX Association, 1403– 1420. [41] Rajeev Thakur, Rolf Rabenseifner, and William Gropp. 2005. Optimization of Collective Communication Operations in MPICH. The International Journal of High Performance Computing Applications 19, 1 (2005), 49–66. doi:10.1177/1094342005051521 [42] Abhishek Verma, Madhukar Korupolu, and John Wilkes. 2014. Evaluating Job Packing in Warehouse-Scale Computing. In Proceedings of the IEEE International Conference on Cluster Computing (CLUSTER ’14). IEEE, 48–56. doi:10.1109/CLUSTER.2014.6968735 [43] Qinghe Wang, Futian Wang, and Xinwei Zheng. 2024. Hops: Finegrained Heterogeneous Sensing, Efficient and Fair Deep Learning Cluster Scheduling System. In Proceedings of the 2024 ACM Symposium on Cloud Computing (SoCC ’24). ACM, 1–17. doi:10.1145/3698038. 3698515 [44] Qizhen Weng, Wencong Xiao, Yinghao Yu, Wei Wang, Cheng Wang, Jian He, Yong Li, Liping Zhang, Wei Lin, and Yu Ding. 2022. MLaaS in the Wild: Workload Analysis and Scheduling in Large-Scale Heterogeneous GPU Clusters. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI ’22). USENIX Association, 945–960. [45] Qizhen Weng, Lingyun Yang, Yinghao Yu, Wei Wang, Xiaochuan Tang, Guodong Yang, and Liping Zhang. 2023. Beware of Fragmentation: Scheduling GPU-Sharing Workloads with Fragmentation Gradient Descent. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC ’23). USENIX Association, 995–1008. [46] Gerhard J. Woeginger. 1997. There is No Asymptotic PTAS for TwoDimensional Vector Packing. Inform. Process. Lett. 64, 6 (1997), 293–297. doi:10.1016/S0020-0190(97)00179-8 [47] Bingyang Wu, Zili Zhang, Zhihao Bai, Xuanzhe Liu, and Xin Jin. 2023. Transparent GPU Sharing in Container Clouds for Deep Learning Workloads. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI ’23). USENIX Association, 69–85. [48] Haijie Wu, Xinhua Wang, Xiaoxuan Luo, Wangbo Shen, and Weiwei Lin. 2025. MCG-Sched: Multi-Cluster GPU Scheduling for Resource Fragmentation Reduction and Load Balancing. IEEE Transactions on Parallel and Distributed Systems 36, 12 (2025), 2789–2802. doi:10.1109/ TPDS.2025.3626153 [49] Qing Wu, Pengfei Chen, and Yu Wang. 2025. Defragmentation Scheduling with Deep Reinforcement Learning in Shared GPU Clusters. In Proceedings of the 2025 ACM Symposium on Cloud Computing (SoCC ’25). ACM, 402–415. doi:10.1145/3772052.3772242 [50] Wencong Xiao, Romil Bhardwaj, Ramachandran Ramjee, Muthian Sivathanu, Nipun Kwatra, Zhenhua Han, Pratyush Patel, Xuan Peng, Hanyu Zhao, Quanlu Zhang, Fan Yang, and Lidong Zhou. 2018. Gandiva: Introspective Cluster Scheduling for Deep Learning. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI ’18). USENIX Association, 595–610. [51] Zhisheng Ye, Wei Gao, Qinghao Hu, Peng Sun, Xiaolin Wang, Yingwei Luo, Tianwei Zhang, and Yonggang Wen. 2024. Deep Learning Workload Scheduling in GPU Datacenters: A Survey. Comput. Surveys 56, 6 (2024), 1–38. doi:10.1145/3638757 [52] Yihao Zhao, Yuanqiang Liu, Yanghua Peng, Yibo Zhu, Xuanzhe Liu, and Xin Jin. 2022. Multi-Resource Interleaving for Deep Learning Training. In Proceedings of the ACM SIGCOMM 2022 Conference (SIGCOMM ’22). ACM, 428–440. doi:10.1145/3544216.3544224
14
COMPASS-ABS
A
Compactness of Best-Fit on Power-of-Two Workloads
free(𝐵)before − 𝑠 = 𝑟 , so free(𝐵)before ≥ 𝑠. If 𝐵 was a fresh bin, then free(𝐵)before = 𝐺 = 8 and 𝑠 = 𝐺 − 𝑟 > 0; bin 𝐴 also had free space 𝑟 ≥ 𝑠, since 𝑟 = 𝐺 − 𝑠 and 𝐺 ≥ 𝑠 forces 𝑟 ≥ 0, and we ruled out 𝑟 = 0 because 𝐴 is partial. Concretely, for every reachable 𝑟 ∈ {2, 4, 6} the item size 𝑠 = 𝐺 − 𝑟 ∈ {6, 4, 2}, but only 𝑠 ∈ {2, 4} are admissible power-of-two items (size 6 is not in the workload), so the only case is 𝑠 ∈ {2, 4}, in which 𝐴 with free(𝐴) = 𝑟 also has free(𝐴) ≥ 𝑠 and best-fit would have picked 𝐴 over the fresh 𝐵 because the fresh bin has 𝐺 = 8 > 𝑟 . If 𝐵 was not fresh, then free(𝐵)before > 𝑟 , so free(𝐴) = 𝑟 < free(𝐵)before . Best-fit’s least-fit rule would then still have preferred 𝐴 over 𝐵, because 𝐴 leaves the smaller free space, provided 𝐴 can host the item. The admissibility condition free(𝐴) ≥ 𝑠 is exactly 𝑟 ≥ 𝑠. It holds because the placement into 𝐵 required free(𝐵)before ≥ 𝑠, and substituting 𝑟 = free(𝐵)before −𝑠 rewrites 𝑟 ≥ 𝑠 as free(𝐵)before ≥ 2𝑠. The only case where free(𝐴) < 𝑠 is when 𝑟 < 𝑠, but this is already excluded by the construction free(𝐵)before = 𝑟 + 𝑠 and the item size 𝑠 being one of {2, 4} which gives 𝑟 + 𝑠 ≤ 𝐺 hence 𝑟 ≤ 𝐺 − 𝑠. In every admissible sub-case best-fit’s tie-breaking prefers 𝐴, contradicting the placement having gone to 𝐵. □
This appendix formalises Observation 1 of Section 4.1. We consider the restricted setting in which every multi-GPU instance has demand 𝑔𝑖 ∈ {2, 4, 8}, i.e. the active workload is contained in I FF , and the cluster runs a stripped-down variant of Algorithm 1: each arrival is handled by a single Place call that uses best-fit (no Compact pass on arrival), and each departure is handled by per-instance Remove calls followed by a single Compact pass on the departure side only. We show that this minimal policy is already sufficient to enforce SIF𝜋 (𝑡) ≤ 2/𝑁 at all times, and we exhibit a finite event sequence that reaches the bound. A.1
Setup and statement
Let the active workload consist of items of size 𝑔 ∈ {2, 4, 8} that arrive and depart online, and let each node be a bin of capacity 𝐺 = 8. We use Φ𝜋 (𝑡) := 𝜈 (𝑃 𝜋 (𝑡)) for the partialnode count under policy 𝜋 at time 𝑡, with 𝐹 𝜋 (𝑡) = Φ𝜋 (𝑡)/𝑁 as in Section 3.2. The free space of a partial bin lies in {2, 4, 6}, because used capacity attainable by sums of items in {2, 4, 8} that strictly under-fill 𝐺 = 8 is one of {2, 4, 6}.
Lemma B.2 (free-six isolation). If some partial bin has free space 6, then no other partial bin exists at the same time.
Proposition 3 (Best-Fit Compactness on Power-of-Two Workloads). Let the policy place every arriving instance via best-fit, i.e. on the node leaving the smallest remaining capacity after placement and opening a fresh node when no existing node can host the instance, and let every departure be followed by a single Compact pass. If every active instance has 𝑔𝑖 ∈ {2, 4, 8}, then for every 𝑡 ≥ 0 the state 𝜎 (𝑡) produced by the policy satisfies
Proof. A bin with free = 6 contains exactly one size-2 item. Consider the most recent placement that put this size-2 item into the bin. The bin was empty just before the placement, because no other item-size combination from {2, 4, 8} yields used capacity 2. Best-fit opens a fresh empty bin only when no existing partial bin admits the item. The arriving item has size 2, so an admissible partial bin would only require free ≥ 2, which every partial bin satisfies because every partial free value lies in {2, 4, 6}. Hence no partial bin existed at the moment the size-2 item was placed in the fresh bin, and the new free = 6 bin is the sole partial bin at that instant. Each subsequent arrival event either (i) places a size-2 item, which best-fit routes into the existing free = 6 bin and reduces its free space to 4, removing it from the free = 6 class; or (ii) places a size-4 item, which best-fit routes into the existing free = 6 bin and reduces its free space to 2; or (iii) places a size-8 item, which opens a fresh bin that immediately becomes full and creates no new partial bin. In none of these cases is a second partial bin created while the original free = 6 bin still has free space 6, so the isolation invariant is preserved until the next departure event. □
2 , 𝑁 and both inequalities are tight in the sense that a finite arrival sequence reaches Φ𝜋 (𝑡) = 2. Φ𝜋 (𝑡) ≤ 2
A.2
and
SIF𝜋 (𝑡) ≤
Proof of Proposition 3
We bound Φ𝜋 (𝑡) separately on the two event types and combine the bounds. Throughout, “bin” is interchangeable with “node” and “item” with “instance”. Part 1: best-fit on arrival leaves at most two partial bins. We first show that immediately after any arrival event the cluster state has at most two partial bins. Lemma B.1 (free-value uniqueness). At any time during the arrival pass, at most one partial bin has remaining free space 𝑟 for each 𝑟 ∈ {2, 4, 6}.
Lemma B.3 (two-partial bound). At any time immediately after an arrival placement, the cluster has at most two partial bins, and the only reachable two-partial configuration has free spaces {2, 4}.
Proof. Suppose for contradiction that two partial bins 𝐴 and 𝐵 have free space 𝑟 at the same time. Let 𝐵 be the bin whose free space last became 𝑟 , and consider the placement event that produced free(𝐵) = 𝑟 . Just before that placement, free(𝐴) = 𝑟 already held by hypothesis. The placement put an item of size 𝑠 into 𝐵, with 𝑠 ≤ free(𝐵)before and
Proof. Combining Lemmas B.1 and B.2, the set of free-space values present across partial bins is a subset of {2, 4, 6} in which each value appears at most once, and the value 6 15
Yukai Zhou and Hongfan Wu
cannot coexist with any other partial bin. Hence the only feasible multisets of free-space values across partial bins are ∅, {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6} from cardinality counting, and the last two are forbidden by Lemma B.2. The remaining configurations have at most two partial bins. □
free space 4, matching the only feasible two-partial configuration identified in Lemma B.3 and witnessing Φ𝜋 (𝑡) = 2 together with SIF𝜋 (𝑡) = 2/𝑁 . This completes the proof of Proposition 3. □
B
Part 2: Compact on departure leaves at most one partial bin. Departures invoke a single Compact pass after the per-instance Remove calls have been applied. Under the present restriction I =1 = ∅, I FUF = ∅, so the active 1-GPU population 𝑛 1 (𝑡) is identically zero and the total slot vacancy aggregated across anchored fragmentation-unfriendly instances is identically zero. The Workload Composition Condition (9) therefore reduces to 0 ≥ 0 and holds trivially at every time. Lemma A.3 of Appendix B then contributes zero non-fully-packed pool nodes because no pool nodes exist, and Lemma A.4 of Appendix B contributes at most one non-fully-packed slotted node from the width-4 and width2 BestFitDrain passes. The post-departure state therefore satisfies Φ𝜋 (𝑡) ≤ 1.
Proofs for the Theoretical Guarantees of COMPASS-ABS
This appendix collects the detailed proofs of the three results stated in Section 4.4, namely the unconditional state-space invariance in Proposition 1, the conditional SIF ≤ 2/𝑁 compactness bound in Theorem 1, and the per-operator complexity in Proposition 2. We keep the notation introduced in Section 4.2 for the ABS domain Σ and in Section 4.3 for the three operators Place, Remove, and Compact. B.1
Proof of Proposition 1 (State-Space Invariance)
We prove that every event applied by Algorithm 1 maps Σ into Σ, so that by induction every state generated from an initial 𝜎0 ∈ Σ remains in Σ. Since the algorithm decomposes each job-level event into a finite sequence of per-instance operator calls together with at most one Compact call, it suffices to show that each operator branch preserves Σ when applied to a state already in Σ.
Combining the two parts. The cluster state changes only at event boundaries. After every arrival event Part 1 gives Φ𝜋 (𝑡) ≤ 2, and after every departure event Part 2 gives Φ𝜋 (𝑡) ≤ 1 ≤ 2. The bound Φ𝜋 (𝑡) ≤ 2 therefore holds at every event boundary and extends to every continuous time instant between consecutive events, so
Place preserves Σ. Consider an arrival 𝑖 with demand 𝑔𝑖 applied to 𝜎 ∈ Σ. We argue on the branches of Place. If 𝑔𝑖 ≥ 2, the operator selects a width 𝑤 = 𝑤 ★ (𝑔𝑖 ) ∈ {2, 4, 8} and aÍhost 𝑛★ such that either 𝑛★ is already slotted with 𝐺 − 𝑠 ∈𝑆 (𝑛★ ) 𝑤 (𝑠) ≥ 𝑤, or 𝑛★ was empty and is promoted to slotted with an empty profile. In the first case, appending a slot of width 𝑤 to 𝑆 (𝑛★) produces a new slot multiset whose total width is at most 𝐺 and whose constituents lie in {2, 4, 8}, hence the new 𝑆 (𝑛★) remains in SlotConf as defined in (5). In the second case, the post-event 𝑆 (𝑛★) = {𝑤 } trivially lies in SlotConf. The anchor of the new slot is set to 𝑖 so that 𝑤 (𝑠 ★) = 𝑤 ★ (𝑔𝑖 ) = 𝑤 ★ (𝑔𝑎 (𝑠 ★ ) ), which matches the constraint of Definition 2. The associated filler set is initialised to the up-to-𝑟 migrated 1-GPU instances with 𝑟 = 𝑤 − 𝑔𝑖 , so that |𝐹 (𝑠 ★)| ≤ 𝑟 = 𝑤 (𝑠 ★) − 𝑔𝑎 (𝑠 ★ ) and the capacity invariant (4) holds as an inequality. Every pool node from which a filler is drawn loses one occupant and therefore preserves |𝑃 (𝑛)| ≤ 𝐺. No other node is touched. If 𝑔𝑖 = 1, the operator places 𝑖 either into a slot vacancy (𝑔𝑎 (𝑠 ) +|𝐹 (𝑠)| < 𝑤 (𝑠)), or into a non-full pool node (|𝑃 (𝑛)| < 𝐺), or onto a freshly promoted pool node initialised with 𝑃 (𝑛) = {𝑖}. In the first case, |𝐹 (𝑠)| increases by one and the new value remains bounded by 𝑤 (𝑠) − 𝑔𝑎 (𝑠 ) by the entry condition 𝑔𝑎 (𝑠 ) + |𝐹 (𝑠)| < 𝑤 (𝑠). In the second case, |𝑃 (𝑛)| increases by one and remains bounded by 𝐺. In the third case, the new pool node has |𝑃 (𝑛 0 )| = 1 ≤ 𝐺. In all three cases the affected node remains a legal pool node or slotted node, and no slot configuration leaves SlotConf.
Φ (𝑡) ≤ 2, 𝜋
Φ𝜋 (𝑡) 2 ≤ , 𝑁 𝑁 2 SIF𝜋 (𝑡) ≤ 𝐹 𝜋 (𝑡) ≤ . 𝑁 𝐹 𝜋 (𝑡) =
for all 𝑡 ≥ 0, where the last inequality uses the non-negativity of the inherent fragmentation 𝐹 ★ (𝑡) from Section 3.2. Tightness. The bound Φ𝜋 (𝑡) = 2 is realised by the following arrival sequence on an otherwise fully-packed cluster. Suppose all nodes other than one are fully packed and the remaining node hosts a single size-4 anchor together with one size-2 anchor, leaving free space 2. A DLT job composed of three size-4 instances now arrives. Best-fit considers each arriving instance in turn. The first instance encounters free space 2 on the partial node, which does not admit a size4 item, so a fresh node is opened and the first instance is placed there, producing a new partial node with free space 4. The second instance sees free space 2 on the original partial node and free space 4 on the just-opened node, prefers the smaller fitting capacity, and is placed onto the just-opened node, which becomes fully packed. The third instance again finds the original partial node uninhabitable for a size-4 item and the now-full node also unable to host it, so a further fresh node is opened with free space 4. The cluster now contains two partial nodes, one with free space 2 and one with 16
COMPASS-ABS
Remove preserves Σ. Consider a departure 𝑖 applied to 𝜎 ∈ Σ. If 𝑖 is an anchor of some slot 𝑠, the operator dissolves 𝑠 and reinserts each filler 𝑓 ∈ 𝐹 (𝑠) by the 1-GPU rule of Place. Dissolving 𝑠 removes one element from 𝑆 (𝑛) for the host node 𝑛, so the new 𝑆 (𝑛) is a sub-multiset of the original 𝑆 (𝑛) ∈ SlotConf, and any sub-multiset of a SlotConf element again lies in SlotConf. The reinsertion step has already been shown to preserve Σ in the Place argument above, applied instance-by-instance to the elements of 𝐹 (𝑠). If 𝑖 is a 1-GPU instance currently attached as a filler in some slot 𝑠, the operator simply removes 𝑖 from 𝐹 (𝑠), which can only decrease |𝐹 (𝑠)| and therefore preserves (4) as a strict inequality. If 𝑖 is a 1-GPU pool occupant on some pool node 𝑛, the operator removes 𝑖 from 𝑃 (𝑛), which only decreases |𝑃 (𝑛)| and remains bounded by 𝐺.
algebraically equivalent to the slot-vacancy form ∑︁ 𝑛 1 (𝑡) ≥ 𝑤 (𝑠) − 𝑔𝑎 (𝑠 ) ,
which asserts that the active 1-GPU population is at least as large as the total slot vacancy currently exposed by anchored fragmentation-unfriendly instances. Proof. By Definition 1, every active anchor 𝑎(𝑠) ∈ I ≥2 has a slot width 𝑤 (𝑠) = 𝑤 ★ (𝑔𝑎 (𝑠 ) ). Inspecting 𝑤 ★ in (3) we obtain 𝑤 (𝑠) − 𝑔𝑎 (𝑠 ) = 0 for 𝑔𝑎 (𝑠 ) ∈ {2, 4, 8}, 𝑤 (𝑠) − 𝑔𝑎 (𝑠 ) = 1 for 𝑔𝑎 (𝑠 ) = 3, 𝑤 (𝑠) − 𝑔𝑎 (𝑠 ) = 3 for 𝑔𝑎 (𝑠 ) = 5, 𝑤 (𝑠) − 𝑔𝑎 (𝑠 ) = 2 for 𝑔𝑎 (𝑠 ) = 6, and 𝑤 (𝑠) − 𝑔𝑎 (𝑠 ) = 1 for 𝑔𝑎 (𝑠 ) = 7. Summing over all active anchors and grouping by demand, ∑︁ 𝑤 (𝑠) − 𝑔𝑎 (𝑠 ) = 𝑛 3 (𝑡) + 3 𝑛 5 (𝑡) + 2 𝑛 6 (𝑡) + 𝑛 7 (𝑡). 𝑠: 𝑎 (𝑠 )≠∅
Substituting this identity into (18) and dividing both sides by 𝑛 total (𝑡) > 0 yields (9), and the implication is reversible since each step is an equivalence. In what follows we use (18) interchangeably with the original form. □
Compact preserves Σ. Migrations (𝑥, 𝑛 dst ) executed within the BestFitDrain loop are performed only when room C (𝑛 dst ) ≥ size(𝑥) holds for the current class C. Concretely, for the pool pass the destination pool node has |𝑃 (𝑛 dst )| < 𝐺 before the migration, so |𝑃 (𝑛 dst )| stays at most 𝐺 after the migration. For the width-4 pass the destination slotted node has ⌊𝐷 (𝑛 dst )/4⌋ ≥ 1 so that 𝐷 (𝑛 dst ) ≥ 4, hence appending Í a width-4 slot keeps 𝑠 ∈𝑆 (𝑛dst ) 𝑤 (𝑠) + 4 ≤ 𝐺 and the new 𝑆 (𝑛 dst ) remains in SlotConf. The width-2 pass is analogous with the inequality 𝐷 (𝑛 dst ) ≥ 2. Migrating a slot also detaches its filler set and reattaches it to the new host, which by the capacity invariant 𝑔𝑎 (𝑠 ) + |𝐹 (𝑠)| ≤ 𝑤 (𝑠) on the source side remains valid on the destination side because 𝑤 (𝑠) does not change under migration. Every migration therefore preserves Σ, and so does the entire Compact call which is a finite composition of such migrations.
Lemma A.2 (Slot Saturation under the Workload Composition Condition). Under (18), at the end of every event handled by Algorithm 1 (whether a job arrival or a job departure) the capacity invariant in (4) holds with equality for every active fragmentation-unfriendly anchor, namely 𝑔𝑎 (𝑠 ) + |𝐹 (𝑠)| = 𝑤 (𝑠)
∀𝑠 with 𝑎(𝑠) ∈ I FUF .
(19)
Proof. By construction Place pulls 𝑤 (𝑠) − 𝑔𝑎 (𝑠 ) fillers from the pool whenever a fragmentation-unfriendly anchor is installed, and Remove in the 1-GPU branch additionally migrates one replacement filler from the pool whenever a filler departs from a slot. Both operators therefore actively maintain the saturation equality (19) as long as the pool population is non-empty. The only obstacle is filler shortage at the moment when fillers are being drawn, and the slot-vacancy form (18) guarantees that the total active 1-GPU population 𝑛 1 (𝑡) is at least the total slot vacancy aggregated across all anchored fragmentation-unfriendly instances at the end of the event. Since Compact does not create new slot vacancy and the 1-GPU pool is internally redistributed across pool nodes without changing 𝑛 1 (𝑡), (18) carries through to the post-Compact state. Because Algorithm 1 now invokes Compact at the end of both arrival and departure branches, every event terminates in a post-Compact state, and the equality (19) therefore holds at the end of every event. □
Conclusion. By induction on the event sequence, every state produced by Algorithm 1 remains in Σ, which establishes Proposition 1. □ B.2
(18)
𝑠: 𝑎 (𝑠 )≠∅
Proof of Theorem 1 (Compactness under the Workload Composition Condition)
Throughout this subsection we assume that the fractionform Workload Composition Condition (9) stated inside Theorem 1 holds at the time 𝑡 under consideration. The argument proceeds in three stages. We first translate the fraction form into a structurally more convenient slot-vacancy form (Lemma A.1), then show that this slot-vacancy form implies the saturation of every anchored fragmentation-unfriendly slot at the end of each operator call (Lemma A.2), and finally show that the three BestFitDrain passes inside Compact leave at most one partial node per node-type (Lemmas A.3 and A.4), which after normalisation by the cluster size 𝑁 yields the SIF𝜋 (𝑡) ≤ 2/𝑁 bound.
Lemma A.3 (Pool Pass Compactness). After the pool pass of Compact, at most one pool node is non-fully-packed. Proof. The pool pass instantiates BestFitDrain policy with countpool (𝑛) = |𝑃 (𝑛)|, cappool (𝑛) = 𝐺, and roompool (𝑛) = 𝐺 − |𝑃 (𝑛)|, and the set of partial hosts is N = {𝑛 : 0 < |𝑃 (𝑛)| < 𝐺 }. Each iteration picks the head of N as 𝑛 src , the node with the largest remaining room. The drain loop
Lemma A.1 (Slot-Vacancy Form of the Workload Composition Condition). The fraction-form condition (9) is 17
Yukai Zhou and Hongfan Wu
selects, for each 1-GPU item 𝑥 on 𝑛 src , the eligible destination with the smallest room roompool (𝑛 dst ) ≥ 1 and migrates 𝑥 there. Each migration strictly increases |𝑃 (𝑛 dst )| and strictly decreases |𝑃 (𝑛 src )|. The loop terminates either when |N | ≤ 1 or when no progress is made during an iteration. Suppose for contradiction that termination occurs with |N | ≥ 2 and no progress in the last iteration. “No progress” means that for every 𝑥 on 𝑛 src the eligible set S = {𝑛 ∈ N \ {𝑛 src } : roompool (𝑛) ≥ 1} is empty. But |N | ≥ 2 implies the existence of at least one 𝑛 ′ ∈ N \ {𝑛 src } with |𝑃 (𝑛 ′ )| < 𝐺, equivalently roompool (𝑛 ′ ) ≥ 1, so 𝑛 ′ ∈ S, a contradiction. Therefore termination implies |N | ≤ 1, which is exactly the claim that at most one pool node is non-fully-packed. □
contradicting its membership in the partial set; therefore 𝐷 (𝑛 (4) ) = 2, which means 𝑆 (𝑛 (4) ) = {4}, because {4, 2} already exhausts the width-2 room and {4, 4} is fully-packed. But then roomw2 (𝑛 (4) ) = ⌊2/2⌋ = 1 ≥ 1, so 𝑛 (4) is a width-2eligible destination that can absorb any width-2 slot present on 𝑛 (2) . The width-2 pass would therefore have made a migration from 𝑛 (2) to 𝑛 (4) , contradicting the assumption that the width-2 pass left 𝑛 (2) ≠ 𝑛 (4) . We conclude that the survivor sets of the two passes coincide, hence at most one slotted node remains partial after the entire Compact call. □ Concluding the proof of Theorem 1. Combining Lemmas A.3 and A.4, immediately after every Compact invocation performed by Algorithm 1 under the Workload Composition Condition (9), at most one pool node and at most one slotted node are non-fully-packed, so at most two non-empty nodes in the cluster carry unused GPU capacity. Because Algorithm 1 invokes Compact in both the arrival branch and the departure branch, every event handled by the algorithm terminates in a state that satisfies this two-partial-node bound. The cluster state changes only at event boundaries, so the bound extends from every event boundary to every continuous time instant between consecutive events; that is, the two-partial-node bound holds for all 𝑡 ≥ 0. It remains to translate this combinatorial bound into the Scheduler-Induced Fragmentation metric of Section 3. Recall that 𝐹 𝜋 (𝑡) denotes the proportion of partial nodes in the cluster state produced by policy 𝜋, that 𝐹 ★ (𝑡) ≥ 0 denotes the inherent partial-node proportion attainable by any feasible packing of the active demand I (𝑡), and that SIF𝜋 (𝑡) := 𝐹 𝜋 (𝑡) − 𝐹 ★ (𝑡). Dividing the partial-node count by the cluster size 𝑁 converts the two-partial-node bound into 𝐹 𝜋 (𝑡) ≤ 2/𝑁 for all 𝑡 ≥ 0, and the non-negativity of 𝐹 ★ (𝑡) then gives
Lemma A.4 (Slotted Compactness). After the width-4 and width-2 passes of Compact, and under the slot saturation guaranteed by Lemma A.2, at most one slotted node is nonfully-packed. Proof. Under Lemma A.2 every active slot is internally saturated, so a slotted Í node 𝑛 is non-fully-packed if and only if 𝐷 (𝑛) = 𝐺 − 𝑠 ∈𝑆 (𝑛) 𝑤 (𝑠) > 0, i.e. the Í node has unprofiled residual capacity. Possible values of 𝑠 ∈𝑆 (𝑛) 𝑤 (𝑠) are subsums of multisets drawn from {2, 4, 8} bounded above Í by 𝐺 = 8, so a fully-packed slotted node has 𝑠 ∈𝑆 (𝑛) 𝑤 (𝑠) = 8 achieved by one of the multisets {8}, {4, 4}, {4, Í 2, 2}, {2, 2, 2, 2}, while a non-fully-packed slotted node has 𝑠 ∈𝑆 (𝑛) 𝑤 (𝑠) ≤ 6 achieved by one of {2}, {4}, {2, 2}, {4, 2}, {2, 2, 2}. The width-4 pass treats anchored width-4 slots as items and slotted nodes as hosts, with countw4 (𝑛) counting width4 anchored slots in 𝑆 (𝑛) and roomw4 (𝑛) = ⌊𝐷 (𝑛)/4⌋. Repeating the contradiction argument of Lemma A.3 with the width-4 class, if the width-4 pass terminates with two or more nodes still satisfying 0 < countw4 (𝑛) < capw4 (𝑛) and with positive room on at least one of them, then the head source has an eligible destination and the loop must perform a migration, contradicting the no-progress termination condition. The pass therefore terminates with at most one slotted node in the width-4 partial set. After the width-4 pass, consider the remaining partial slotted nodes. Each such node either has no width-4 slot at all, or it is the unique node left in the width-4 partial set. The first sub-population is then processed by the width-2 pass under the same argument applied to the width-2 class. The same no-progress contradiction shows that the width-2 pass terminates with at most one node in the width-2 partial set. It remains to argue that the survivor of the width-4 pass and the survivor of the width-2 pass can be taken to be the same node. Suppose the width-4 pass leaves a single partial node 𝑛 (4) and the width-2 pass leaves a single partial node 𝑛 (2) ≠ 𝑛 (4) . The node 𝑛 (4) contains a single width-4 anchored slot and has 𝐷 (𝑛 (4) ) ∈ {0, 2} from the multiset enumeration above. If 𝐷 (𝑛 (4) ) = 0 then 𝑛 (4) is fully-packed,
SIF𝜋 (𝑡) = 𝐹 𝜋 (𝑡) − 𝐹 ★ (𝑡) ≤ 𝐹 𝜋 (𝑡) ≤ This completes the proof of Theorem 1. B.3
2 𝑁
∀ 𝑡 ≥ 0. □
Proof of Proposition 2 (Operational Complexity)
We bound the per-operator running time under the standard assumption that the slot index, the pool index, and the emptynode index are maintained as balanced search trees keyed by the relevant priority. The bookkeeping cost of incremental index maintenance is absorbed into the operator-level bounds below. Place is 𝑂 (log 𝑁 ). The multi-GPU branch performs three operations on the slotted-node index: a candidate query for the smallest remaining capacity above the threshold 𝑤 ★ (𝑔𝑖 ), an insertion of a new slot record, and at most 𝑤 ★ (𝑔𝑖 ) −𝑔𝑖 ≤ 6 filler-draw operations from the pool index. Each of these operations runs in 𝑂 (log 𝑁 ) on a balanced search tree of 𝑁 entries, and the constant number of filler draws contributes only an 𝑂 (log 𝑁 ) overhead. The 1-GPU branch performs 18
COMPASS-ABS
C.1
one priority query for an open slot vacancy or a non-full pool node, again at 𝑂 (log 𝑁 ) cost. Therefore T (Place) = 𝑂 (log 𝑁 ).
Each fragmentation-unfriendly instance 𝑔 ∈ I FUF can be combined with strictly smaller active instances into a composite block whose total GPU count falls in {4, 8}, namely
Remove is 𝑂 (1). If 𝑖 is a 1-GPU occupant, the operator detaches 𝑖 from its current container in 𝑂 (1) time by following the parent pointer maintained in the slot or pool index. If 𝑖 is an anchor of slot 𝑠, the operator dissolves 𝑠 in 𝑂 (1) time and reinserts each of the |𝐹 (𝑠)| ≤ 6 fillers by the 1-GPU rule of Place, each at 𝑂 (log 𝑁 ) cost. Since |𝐹 (𝑠)| is bounded by the constant 𝐺 − 𝑔𝑎 (𝑠 ) ≤ 6, the total work of an anchor departure is dominated by a constant number of 𝑂 (log 𝑁 ) filler reinsertions, so the local handler cost is 𝑂 (1) when the filler reinsertions are charged to the subsequent Compact pass that already runs in 𝑂 (𝑁 ). We therefore report T (Remove) = 𝑂 (1) for the local edit.
𝑔=3:
3 + 1 = 4,
𝑔=5:
5 + 3 = 8 or 5 + 2 + 1 = 8 or 5 + 1 + 1 + 1 = 8,
𝑔=6:
6 + 2 = 8 or 6 + 1 + 1 = 8,
𝑔=7:
7 + 1 = 8.
If every active FUF instance is paired into such a composite, the remaining item population consists of composites of size {4, 8}, original I FF instances of size {2, 4, 8}, and any 1-GPU instances not consumed as fillers, so the multiset of item sizes is contained in {1, 2, 4, 8}. The Workload Composition Condition (9) stated in Theorem 1 is exactly the algebraic condition under which the active 1-GPU population is sufficient to complete this pairing for every FUF instance, so under that condition the reduction to a power-of-two item multiset always succeeds.
Compact is 𝑂 (𝑁 ). A single pass of BestFitDrain visits each partial host at most once as 𝑛 src in the outer loop, and inside the loop it performs at most count C (𝑛 src ) ≤ 𝐺 item migrations, each at 𝑂 (log 𝑁 ) cost. The total work per class is therefore 𝑂 (𝑁 log 𝑁 ), and aggregating across the three classes (pool, w4, w2) gives the same asymptotic bound. With a slightly tighter amortised analysis that charges each migration to the destination node whose room strictly decreases as a result, the log 𝑁 factor collapses to 𝑂 (𝑁 ) total, matching the bound stated in the proposition. □
C
Key observation: reduing to power-of-two items
C.2
Closed form solution under the Workload Composition Condition When all item sizes lie in {1, 2, 4, 8}, packing into bins with capacity 𝐺 = 8 admits an trivial optimum: a Best-Fit-Decreasing pass that processes items in the order 8 → 4 → 2 → 1 always closes one bin per multiple of 𝐺 and leaves at most one partial bin whose load equals 𝑇 (𝑡) mod 𝐺, where
Algorithm for Computing Φ★ (𝑡) and 𝐹 ★ (𝑡)
The inherent fragmentation defined in Section 3.2 is
𝑇 (𝑡) :=
8 ∑︁
𝑔 · 𝑛𝑔 (𝑡)
(20)
𝑔=1
Φ★ (𝑡) 𝐹 (𝑡) = , 𝑁 ★
Φ (𝑡) := ★
denotes the total active GPU demand at time 𝑡. This is because every two width-4 items pack into a single full bin, every four width-2 items pack into a single full bin, every eight width-1 items pack into a single full bin, and any residual mixture below capacity 𝐺 collapses into a single tail bin by the nested-power-of-two structure. The number of partial bins in the optimal packing is therefore
min 𝜈 (𝑃),
𝑃 feasible
where 𝜈 (𝑃) is the number of partial nodes in a feasible packing 𝑃 of the instantaneous instance multiset I (𝑡) and Φ★ (𝑡) is the minimum partial-node count attainable across all such packings. Throughout this appendix the algorithm computes the integer-valued Φ★ (𝑡), from which 𝐹 ★ (𝑡) follows by the single division by the cluster size 𝑁 . Evaluating Φ★ (𝑡) via a general bin-packing solver is already expensive on a single time slice and prohibitive on a trace-long evaluation. The structural analysis carried out in Section 4 for COMPASSABS, however, supplies enough structure to compute Φ★ (𝑡) either in closed form or by a small residual ILP. We describe the algorithm in this appendix and then use it as the oracle scheduler SIFOpt in the empirical evaluation of Section 5.
(
0, 𝑇 (𝑡) mod 𝐺 = 0, 1, otherwise, (21) 𝐹 ★ (𝑡) = Φ★ (𝑡)/𝑁 ∈ {0, 1/𝑁 }. In other words, under the condition the inherent fragmentation floor never exceeds a single node: at most one bin carries unavoidable residue 𝑇 (𝑡) mod 𝐺, and every partial node beyond that one is therefore scheduler-induced and accounted for by SIF𝜋 (𝑡). Both cases of (21) are tight and achievable by the explicit Best-FitDecreasing placement described below. Φ (𝑡) = ⊮ 𝑇 (𝑡) . 0 ★
19
(mod 𝐺)
=
Yukai Zhou and Hongfan Wu
C.3
Residual ILP when the Workload Composition Condition fails
small subset of FUF instances that the combining stage could not pair, and the size of that ILP is bounded by the deficit 𝛿 (𝑡) = (𝑛 3 + 3𝑛 5 + 2𝑛 6 + 𝑛 7 ) − 𝑛 1 rather than by the cluster size, so the procedure remains tractable on production traces even when (9) is momentarily violated.
When (9) fails, the active 1-GPU population is short by 𝛿 (𝑡) := 𝑛 3 + 3𝑛 5 + 2𝑛 6 + 𝑛 7 − 𝑛 1 relative to the filler demand of the FUF anchors. After the greedy combining stage exhausts the 1-GPU supply, exactly 𝛿 (𝑡) units of FUF slot vacancy remain unfilled, equivalently a small residual subset 𝑈 (𝑡) ⊆ I FUF of FUF instances enter the placement stage still carrying their original size in {3, 5, 6, 7}. The item multiset is therefore no longer contained in {1, 2, 4, 8}, and the closed form (21) no longer applies. In that case we restrict the optimization to 𝑈 (𝑡): we first place all power-of-two items via Best-Fit-Decreasing as in the closed-form case, then run an integer linear program that places the residual FUF instances on top of the resulting state and minimises the total partial-node count. The size of this ILP is governed by |𝑈 (𝑡)| rather than 𝑛 total (𝑡), and |𝑈 (𝑡)| is in turn bounded by 𝛿 (𝑡), which is empirically a small constant on production traces because the Workload Composition Condition holds during the overwhelming majority of evaluated time slices and fails only briefly during transient mixture shifts. C.4
Complexity. The combining stage scans the instance multiset once at 𝑂 (𝑛 total (𝑡)) cost. The Best-Fit-Decreasing placement runs in 𝑂 (𝑛 total (𝑡) log 𝑛 total (𝑡)) with a balanced search tree keyed by bin remaining capacity, and degenerates to 𝑂 (𝑛 total (𝑡)) for the power-of-two item set because each item closes exactly one bin position. Whenever (9) holds, the closed-form return at line 8 short-circuits the placement step for the purpose of reporting Φ★ (𝑡), so the dominant cost is the linear-time combining and the optional witness materialisation. When (9) fails, the residual ILP at line 12 runs on at most 𝛿 (𝑡) ≤ |𝑈 (𝑡)| variables and remains millisecond-scale on production traces with 𝛿 (𝑡) of the order of tens.
Algorithm 2 Computing Φ★ (𝑡) and the SIFOpt placement witness; 𝐹 ★ (𝑡) = Φ★ (𝑡)/𝑁 .
Algorithm summary
We now state the procedure explicitly. The inputs are the active instance counts 𝑛 1 (𝑡), . . . , 𝑛 8 (𝑡) at time 𝑡; the outputs are the optimal partial-node count Φ★ (𝑡) and a witness packing 𝑃 ★ (𝑡) realising it (which the SIFOpt oracle scheduler uses as its target placement). The normalised inherent fragmentation 𝐹 ★ (𝑡) used in Section 3.2 is then obtained as 𝐹 ★ (𝑡) = Φ★ (𝑡)/𝑁 .
Input: active instance counts 𝑛𝑔 (𝑡) for 𝑔 = 1, . . . , 8 Output: Φ★ (𝑡) ∈ Z ≥0 together with a witness packing 𝑃 ★ (𝑡) (and 𝐹 ★ (𝑡) = Φ★ (𝑡)/𝑁 ) Í8 1: 𝑇 ← 𝑔=1 𝑔 · 𝑛𝑔 (𝑡) 2: if 𝑛 1 (𝑡) ≥ 𝑛 3 (𝑡) + 3𝑛 5 (𝑡) + 2𝑛 6 (𝑡) + 𝑛 7 (𝑡) then (WCC holds) 3: for each 𝑖 ∈ I =5 (𝑡) do pair 𝑖 with one I =3 instance if available, else with I =2 + I =1 , else with three I =1 instances (form an 8-composite) 4: for each 𝑖 ∈ I =6 (𝑡) do pair 𝑖 with one I =2 if available, else with two I =1 (form an 8-composite) 5: for each 𝑖 ∈ I =7 (𝑡) do pair 𝑖 with one I =1 (form an 8composite) 6: for each 𝑖 ∈ I =3 (𝑡) not consumed in line 3 do pair 𝑖 with one I =1 (form a 4-composite) 7: run Best-Fit-Decreasing over the resulting items (sizes in {1, 2, 4, 8}) into bins of capacity 𝐺 to obtain 𝑃 ★ (𝑡) 8: return ⊮[𝑇 mod 𝐺 ≠ 0], 𝑃 ★ (𝑡) 9: else (WCC fails; small residual subset of FUF instances cannot pair) 10: greedily perform lines 3–6 until the 1-GPU pool is exhausted; collect unpaired FUF instances into 𝑈 (𝑡) 11: run Best-Fit-Decreasing over the paired items into a tentative packing 𝑃0 12: solve the integer program min 𝜈 (𝑃 0 ⊕ 𝑥)
Logic of the procedure. The algorithm proceeds in two stages that mirror the structural analysis of Section 4. The combining stage (lines 3–6) absorbs every fragmentationunfriendly instance into a composite block of size {4, 8} by pairing it with strictly smaller active instances. Combining priorities are chosen so as to consume the smallest number of 1-GPU instances first when the fragmentation-unfriendly size already has a natural partner of non-unit size in the active set (e.g., 5 + 3 before 5 + 1 + 1 + 1); the priority order does not affect Φ★ (𝑡) as long as combining succeeds for all FUF instances, because the resulting power-of-two item multiset has the same total 𝑇 (𝑡) and Best-Fit-Decreasing on a power-of-two item set always attains the bin-count lower bound ⌈𝑇 (𝑡)/𝐺⌉. The placement stage (line 7) then runs Best-Fit-Decreasing in the order 8 → 4 → 2 → 1 and materialises this lower bound. Under the Workload Composition Condition, the closed form (21) reads off the partialnode count directly from 𝑇 (𝑡) mod 𝐺 without ever inspecting the placement, but the placement is still produced as a witness so that the SIFOpt oracle scheduler has a concrete target to migrate towards in its evaluation runs. When the condition fails, the residual ILP at lines 12–13 handles the
|𝑈 (𝑡 ) |×𝑀
𝑥 ∈Z ≥0
s.t. 𝑥 places each instance in 𝑈 (𝑡) into one bin of 𝑃 0 or into a new bin where 𝑀 is the bin index space and 𝜈 counts partial bins 13: return 𝜈 (𝑃 0 ⊕ 𝑥 ★), 𝑃0 ⊕ 𝑥 ★ 20
COMPASS-ABS
D
Extension to Multi-Panel NVLink Communication Domains
in a panel-slot of width 𝑤 𝑝★ (𝑝𝑖 ) ∈ {2, 4, 8} panels:
The COMPASS-ABS design developed in Section 4 hardwires the per-node GPU count at 𝐺 = 8 together with the slot widths {2, 4, 8}, both of which trace back to the DGX-1 / HGX baseboard abstraction in which a single node forms one NVLink communication domain. Recent NVIDIA platforms such as NVL72 and the projected NVL576 extend the highbandwidth NVLink fabric across multiple baseboards inside a single rack-scale assembly, so that the basic intra-instance communication domain now contains 𝐺 dom GPUs with 𝐺 dom no longer equal to 8. Throughout this appendix we assume only that 𝐺 dom = 𝐺𝑝 · 𝐾,
𝐺 𝑝 = 8,
𝐾 ∈ Z ≥1,
𝑤 𝑝★ (𝑝)
(23)
Multi-panel instances with 𝑝𝑖 ∈ {2, 4, 8} are called panelfragmentation-friendly (panel-FF); those with 𝑝𝑖 ∈ {3, 5, 6, 7} are panel-fragmentation-unfriendly (panel-FUF). A 1-panel instance, namely a 𝑔𝑖 = 𝐺 𝑝 = 8 instance that fully occupies one baseboard, plays at the panel level the role that a 1-GPU instance plays at the GPU level inside a panel: it can either saturate a panel-vacancy in an anchored panel-FUF panelslot, or sit in a panel-pool reserved for panel-level fillers. The full cluster-wide state space is the Cartesian product across NVLink domains of Σpanel , with the internal state of each non-saturated panel still drawn from the GPU-level Σ of Section 4.2. We call the resulting two-level state space the hierarchical ABS and denote it by Σhier .
(22)
namely that each NVLink communication domain comprises exactly 𝐾 baseboards of 𝐺 𝑝 = 8 GPUs each. The original DGX-1 / HGX system corresponds to 𝐾 = 1, NVL72 corresponds to 𝐾 = 9, and a hypothetical NVL576 corresponds to 𝐾 = 72 if treated as a single flat domain or 𝐾 = 8 if treated as eight NVL72 sub-domains. The structural fact we exploit is that the 8-GPU baseboard survives across all of these platforms as the basic hardware building block; only the number of baseboards that sit inside a single NVLink domain varies. We refer to a 𝐺 𝑝 = 8 baseboard as a panel throughout this appendix. Workloads on a multi-panel NVLink domain now admit two qualitatively different instance classes:
D.2
Hierarchical Workload Composition Condition
The Workload Composition Condition (9) of Theorem 1 extends to the two-level setting by imposing one condition per level. Let 𝑛𝑔 (𝑡) denote the count of active sub-panel instances (panel) of GPU demand 𝑔 ∈ {1, . . . , 8} at time 𝑡, and let 𝑛𝑝 (𝑡) denote the count of active multi-panel instances of panel demand 𝑝 ∈ {2, 3, . . .}. The GPU-level condition stays identical to (9), namely 𝑛 1 (𝑡) ≥ 𝑛 3 (𝑡) + 3𝑛 5 (𝑡) + 2𝑛 6 (𝑡) + 𝑛 7 (𝑡),
(24)
and the panel-level condition takes the structurally identical form
• Sub-panel instances with 𝑔𝑖 ∈ {1, . . . , 8} that fit within one panel, exactly as in the original setting; and • Multi-panel instances with 𝑔𝑖 ∈ {16, 24, 32, 40, 48, 56, 64, . . . , 𝐺 dom } that span multiple panels in the same NVLink domain through the rack-scale NVLink fabric.
(panel)
𝑛 8 (𝑡) ≥ 𝑛 3
(panel)
D.3
(𝑡) + 3𝑛 5
(panel)
(𝑡) + 2𝑛 6
(panel)
(𝑡), (25) where the left-hand side is the active count of 𝑔𝑖 = 8 instances, treated as 1-panel fillers at the panel level. Equation (25) is obtained from (24) by the substitution 1-GPU ↦→ 1-panel together with the analogue of the slot-vacancy form (18) at panel granularity, and uses the same coefficient pattern {1, 3, 2, 1} for the same algebraic reason as in Lemma A.1.
The within-panel intra-instance constraint of Section 2.2 is replaced by an intra-domain constraint: every GPU assigned to a single instance must lie in the same NVLink domain. Subpanel instances satisfy this trivially; multi-panel instances exercise it. D.1
2, 𝑝 = 2, = 4, 𝑝 ∈ {3, 4}, 8, 𝑝 ∈ {5, 6, 7, 8}.
(𝑡) + 𝑛 7
Hierarchical COMPASS algorithm
The extended scheduler adopts two structurally identical Place/Remove/Compact pipelines, one per level, dispatched according to the demand class of the arriving or departing instance:
Hierarchical Anchor-Based Space
We extend COMPASS-ABS to a two-level scheduler that runs the original within-panel policy on each panel and a structurally identical panel-level analogue across panels within each NVLink domain. The panel-level state space Σpanel mirrors the ABS construction of Section 4.2 verbatim under two substitutions: the panel replaces the GPU as the atomic placement unit, and the domain capacity 𝐾 replaces the node capacity 𝐺 = 8. A multi-panel instance of demand 𝑔𝑖 has panel demand 𝑝𝑖 := 𝑔𝑖 /𝐺 𝑝 ∈ {2, 3, . . .} and is anchored
• Sub-panel events (𝑔𝑖 ≤ 8): handled by the GPU-level COMPASS-ABS of Section 4.3 acting on the host panel. • Multi-panel events (𝑔𝑖 ∈ {16, 24, . . . , 𝐺 dom − 𝐺 𝑝 }): handled by the panel-level analogue acting on the host NVLink domain, with 𝑔𝑖 = 8 instances serving as panel-fillers. 21
Yukai Zhou and Hongfan Wu
• Domain-filling events (𝑔𝑖 = 𝐺 dom ): occupy an entire NVLink domain at once and are treated as a width-𝐾 degenerate panel-slot. Algorithm 1 is invoked at both levels and each Compact pass runs over the BestFitDrain classes for its level. At the GPU level the three classes remain {pool, w4, w2 } on capacity 𝐺 𝑝 = 8; at the panel level they become {panel-pool, panel-w4, panel-w2 } on capacity 𝐾. Because the two levels act on disjoint populations of items, the two compaction passes do not interfere and run independently after each event. D.4
panel-w2 } exactly as the GPU-level pass operates on its own class set, and the combinatorial argument of Lemma A.4 does not depend on 𝐺 taking any particular value beyond requiring that the slot widths {2, 4, 8} remain a valid subdecomposition of the capacity. For the NVL72 instantiation with 𝐾 = 9, any panel-level layout decomposes into at most one width-8 panel-slot together with one residual panel acting as a panel-pool, which is the structural reason the 9-panel layout fits cleanly into the existing framework despite 𝐾 = 9 not being a power of two: the lone residual panel coincides exactly with the panel-pool slot that the framework already requires. The same hierarchical scheduler and the same compactness bound apply to every multi-panel platform whose NVLink domain comprises an integer number of 8-GPU baseboards, including the original DGX-1 / HGX system (𝐾 = 1, in which the panel level is trivially empty), DGX-2 and SuperPod intermediate systems (𝐾 = 2), the NVL72 system (𝐾 = 9), and the projected NVL576 system (𝐾 = 72 flat, or 𝐾 = 8 across NVL72 sub-domains as a third tier). In summary, as long as the NVLink domain contains an integer multiple of 𝐺 𝑝 = 8 GPUs, the hierarchical COMPASS-ABS scheduler remains valid and the SIF bound (26) continues to hold.
Hierarchical compactness guarantee
The compactness guarantee of Theorem 1 lifts to the hierarchical setting in a structurally identical form. Theorem 2 (Hierarchical Compactness). Assume that the GPU-level Workload Composition Condition (24) and the panellevel Workload Composition Condition (25) both hold at every 𝑡 ≥ 0. Then in every cluster state produced by the hierarchical COMPASS-ABS scheduler: 1. across the entire cluster, at most one panel-resident slotted GPU-region and at most one panel-resident GPUpool region are non-fully-packed; and 2. within each NVLink domain that hosts at least one multi-panel anchor, at most one panel-slot region and at most one panel-pool region are non-fully-packed. Consequently, after normalising the partial-region count at each level by the corresponding domain size, the GPU-level and panel-level scheduler-induced fragmentation measures satisfy 2 SIF𝜋GPU (𝑡) ≤ (cluster-wide, 𝑁 p panels), 𝑁p (26) 2 SIF𝜋panel (𝑡) ≤ (per NVLink domain of 𝐾 panels), 𝐾 for all 𝑡 ≥ 0. Proof sketch. The argument reduces to two independent invocations of the proof of Theorem 1 given in Appendix B.2, one on the GPU-level state inside each panel and one on the panel-level state inside each NVLink domain. Both invocations are valid because Lemmas A.1–A.4 of Appendix B.2 depend only on (i) the power-of-two slot widths {2, 4, 8} being a valid sub-decomposition of the local capacity, (ii) the anchor-filler invariant under the friendly/unfriendly dichotomy of (23), and (iii) the class structure {pool, w4, w2 } on which BestFitDrain operates, all of which are preserved under the substitution 𝐺 → 𝐾 and 1-GPU → 1-panel at the panel level. □ D.5
Generality with respect to the domain panel count
Theorem 2 is stated for an arbitrary positive integer 𝐾, without assuming that 𝐾 is a power of two. The panel-level BestFitDrain operates on class set {panel-pool, panel-w4, 22