OrigaMIG: MIG-Aware VM Placement with a Neighborhood-Restricted BILP and Live Migration

OrigaMIG: MIG-Aware VM Placement with a Neighborhood-Restricted BILP and Live Migration Ahmad Siavashia , Mahmoud Momtazpourb a Independent Researcher b Department of Computer Engineering, Amirkabir University of Technology

Abstract

arXiv:2610.06646v1 [cs.DC] 5 Oct 2026

The extensive use of GPUs in cloud computing, accelerated by the spread of large language model (LLM) services, and the growing need for multitenancy have driven the development of innovative solutions for efficient GPU resource management. Multi-Instance GPU (MIG) technology from NVIDIA enables shared GPU usage in cloud data centers by providing isolated instances, which are offered as MIG-backed virtual GPUs (vGPUs). However, MIG placement rules often lead to fragmentation and suboptimal resource allocation. In this work, we formally model the MIG-aware virtual machine (VM) placement as a binary integer linear programming (BILP) problem aimed at maximizing request acceptance, consolidating resources, and reducing migration overhead. Building upon this formulation, we propose OrigaMIG, a MIG-aware placement optimizer. OrigaMIG places each arriving request at once with a lightweight greedy rule and calls the solver only when a request cannot be placed or the GPUs of a class become fragmented. Each call solves the BILP on a small neighborhood of physical machines (PMs), keeps the rest of the data center fixed, and executes the solution as live migrations. We compare OrigaMIG with the default placement and with two state-of-the-art MIG-aware policies in simulation, across six loads, eleven variants of the workload and the hardware, and data centers of up to 4096 PMs. On 256 A100 and A30 GPUs in 128 PMs, OrigaMIG keeps fewer PMs active than the stronger policy in 29 of 30 paired runs while migrating 29% to 49% fewer VMs, and it uses the least energy per admitted GPU-hour at every load. Against the default placement, it keeps up to 12.5% fewer PMs active and admits up to 7.8 percentage points more of the requested GPU memory. On small data centers, it stays within 4.1% of the optimal number of active PMs. Keywords: Cloud Computing, Resource Management, VM Placement, GPU Defragmentation, NVIDIA Multi-Instance GPU

1. Introduction The rapid expansion of machine learning, data analytics, and high-performance computing (HPC) workloads has positioned GPUs at the heart of cloud computing services, a role amplified by the spread of self-hosted LLM services [1]. While GPUs offer exceptional parallel processing capabilities, they also introduce challenges in scheduling and resource sharing. Traditional scheduling methods, designed for standalone, monolithic GPUs, struggle to efficiently allocate resources when multiple tenants need to share a single GPU [2–6]. NVIDIA’s MIG technology, available on Ampere and Hopper GPUs [7], partially addresses this challenge by partitioning a single GPU into multiple isolated and heterogeneous instances, each with dedicated memory and compute slices. This approach enhances performance isolation, enabling multiple workloads to run on the same GPU. However, MIG enforces rigid rules for slice alignment and profile placement, which can lead to fragmentation, where memory slices become unusable or inefficiently allocated, ultimately reducing overall resource efficiency [8].

Email addresses: a.siavashi@outlook.com (Ahmad Siavashi), momtazpour@aut.ac.ir (Mahmoud Momtazpour)

The NVIDIA A100 40GB, a MIG-enabled GPU, comprises 7 compute slices and 8 memory slices, each providing 5 GB of memory for a total capacity of 40 GB. It supports six distinct MIG GPU instance (GI) profiles, as shown in Table 1, with each profile combining specific numbers of compute slices and memory slices. These profiles follow a naming convention, where the first digit is the number of compute slices and the second number is the memory in GB. While enabling MIG mode is a necessary first step, creating GPU instances and their corresponding compute instances (CIs) is also required. However, this paper focuses exclusively on GIs, leaving details about CIs outside its scope. A VM receives a GI as a MIG-backed vGPU [9], with one vGPU per GI; the required profile is set by the workload the VM hosts, not by the scheduler. NVIDIA vGPU software supports live migration of such a VM, and requires that the destination GPU hosts a GI of the same profile. Table 1: GPU instance profiles on A100 40GB Profile 1g.5gb 1g.10gb 2g.10gb 3g.20gb 4g.20gb 7g.40gb

Compute 1/7 1/7 2/7 3/7 4/7 7/7

Memory 1/8 2/8 2/8 4/8 4/8 8/8

Instances 7 4 3 2 1 1

Start Slices 0, 1, 2, 3, 4, 5, 6 0, 2, 4, 6 0, 2, 4 0, 4 0 0

1g.10gb

1g.10gb

2g.10gb

2g.10gb

1g.5gb 0

1g.5gb 1

3g.20gb 3

2

1

7

6

1g.5gb ×

0

1

3

2

5

4

NVIDIA A100 (MIG-Enabled)

NVIDIA A100 (MIG-Enabled)

(a) Non-contiguous memory slices

(b) Restriction on start slice

3g.20gb 0

5

4

4g.20gb

1g.5gb ×

2

3

1g.5gb

1g.5gb

1g.5gb

4

5

6

7

⇒

1g.5gb

1g.5gb

1g.5gb

1g.5gb

0

1

2

3

NVIDIA A100 (MIG-Enabled)

7

6

3g.20gb 4

5

6

7

NVIDIA A100 (MIG-Enabled)

(c) Rearrangement of allocated slices Figure 1: MIG fragmentation scenarios

Specific rules determine the allocation of GIs on MIG-enabled A100 GPUs, as detailed in NVIDIA’s documentation [7]. This work adopts a perspective focused on memory slices rather than compute slices for greater intuitiveness. The start slices in Table 1 already account for the compute slices, since the number of instances of a profile is the smaller of the bounds set by the memory slices and the compute slices of the GPU. No arrangement of profiles on the memory slices therefore exceeds the compute slices. These allocation principles are followed in other MIG-enabled GPUs. The rules for placing MIG profiles present challenges in the allocation of GIs. GIs are created and destroyed in response to accepted and completed requests, from short batch jobs to the long-lived tenants of self-hosted LLM serving, which can lead to fragmentation. Fig. 1(a) depicts a common fragmentation scenario where, due to non-contiguous memory slices, it is impossible to allocate either 1g.10gb or 2g.10gb GIs. In MIG, however, having contiguous free memory slices does not always ensure GI allocation. Fig. 1(b) depicts a situation where the displayed MIG profiles cannot be assigned to the specified contiguous slices, owing to the lack of availability of their necessary start slices. Furthermore, Fig. 1(c) illustrates a scenario where compacting the allocated slices on the GPU allows for the assignment of an additional 1g.5gb profile. These illustrations show traditional external fragmentation and the placement fragmentation specific to MIG, where contiguous slices remain free but their necessary start slices are unavailable. In large-scale cloud environments, fragmentation worsens as MIG partitions are continuously created and removed to accommodate shifting user demands. GPUs account for most of the cost of these machines, and their placement rules leave capacity unusable where CPU and RAM would not. A naive or short-sighted allocation strategy can quickly lock GPUs into a suboptimal state, limiting the acceptance of high-priority requests and increasing the number of active GPUs. To our knowledge, no existing placement strategy accounts for MIG’s strict placement constraints when placing VMs across a heterogeneous, multi-host data center.

This article makes the following contributions. • An analysis of the default GI placement policy of MIG (Section 3). We analyze the configuration flexibility (CF) of a GPU, its number of free start slices summed over the GI profiles, show that the default policy puts each GI where it maximizes CF, and find that 67% of the 723 configurations of an A100 arrange their GIs suboptimally. As a count of free start slices, CF enters the objective of the BILP as a linear term. • A BILP model of MIG-aware VM placement across a heterogeneous data center with several GPUs per PM (Section 4). It models the start slices of each GI profile and the CPU and RAM of the PMs, and its objective weighs the admitted requests, the active PMs and GPUs, and the migrations of running VMs. • OrigaMIG, an online optimizer built on this model (Section 5). It admits requests on a fast greedy path and rearranges GIs on a slow path. A request that the greedy rule cannot place triggers an admission call, and a fragmented class of GPUs triggers a consolidation call. Each call solves the BILP on a neighborhood of at most 16 PMs with the rest of the data center fixed, and executes the solution as an ordered sequence of live migrations of MIG-backed vGPUs [9]. OrigaMIG never removes a running VM. • An evaluation in simulation against the default placement and two state-of-the-art MIG-aware policies, MFI [10] and TC [11], adapted to VMs on PMs (Section 6). The default placement, FF, pairs first-fit host selection with the default GI placement of Section 3. The evaluation covers loads from 0.5 to 1.2 on 128 PMs with A100 and A30 GPUs, eleven variants of the workload and the hardware, including a production trace, the cost of migrations, an ablation of OrigaMIG, data centers of up to 4096 PMs, and the energy of the PMs and GPUs. 2

• A comparison of OrigaMIG with the optimal placement on data centers of 8 to 32 PMs, and a measurement of how the time to solve the BILP over a whole data center grows (Sections 6.8 and 6.9).

based on GPU utilization and job waiting time, their method outperforms heuristics in 76% of test cases. In [34], authors explore a GPU-enabled VM placement problem for NVIDIA GRID, optimizing performance using a cost function based on GPU utilization, fully executed VMs, and GPU execution time. Various VM placement policies are analyzed, with one achieving the best results. MIG Partitioning and Co-location. Later, NVIDIA introduced MIG [7], which enabled both homogeneous and heterogeneous instances; however, it enforces a strict set of placement rules, making placement more complex than the earlier GRID solution. To optimize MIG partitions for serving DNNs, Tan et al. [35] introduce the reconfigurable machine scheduling problem, a new NP-hard abstraction. They propose MIG-serving, a pipeline combining greedy heuristics, genetic algorithm, and Monte Carlo tree search for cost-efficient deployments. MIG-serving includes an optimizer for deployment generation and a controller for seamless application. Experiments on a 24-GPU A100 cluster show up to a 40% GPU reduction over baseline static allocations with minimal service disruptions. In [36], the authors integrate GPU partitioning with power-aware scheduling to optimize resource allocation in CPU-GPU heterogeneous systems under power constraints. Leveraging MIG for fine-grained workload co-location, their approach employs scalability and interference models to improve efficiency and achieve near-optimal configurations across diverse workloads. In [6], authors highlight the rapid advancements in GPU technology, enhancing HPC and AI/ML research but also leading to inefficient resource utilization. To address this, they propose MISO, a technique leveraging MIG on NVIDIA datacenter GPUs (e.g., A100, H100) for dynamic GPU resource partitioning. MISO utilizes the lightweight Multi-Process Service (MPS) [37] to predict optimal MIG partitioning without incurring exploration overhead. This approach improves GPU efficiency, achieving 49% and 16% lower average job completion times (JCT) compared to unpartitioned and optimal static GPU partitioning, respectively. In [38], authors integrate MPS and MIG hierarchically, using reinforcement learning to jointly optimize partitioning and job co-scheduling. Experimental results demonstrate up to 1.87× throughput improvement over time-sharing scheduling. In [39], authors present MIGER, a scheduling framework that combines MIG’s hardware partitions with MPS concurrency to improve job turnaround in GPU clusters. The authors model the MIG-enabled placement of jobs as an NP-hard optimization and design both exact and heuristic algorithms to allocate GPU instances. Through real cluster experiments, MIGER achieved 36% and 46.6% faster job completion times than state-of-the-art MIG-based and MPS-based solutions, respectively. Similarly, in [8], the authors propose ParvaGPU, a GPU space-sharing framework that integrates MIG and MPS to optimize DNN inference in cloud environments. It mitigates GPU underutilization with the Optimal Triplet Decision algorithm, which selects MPS-activated MIG instances for maximum throughput. The Demand Matching algorithm optimally assigns instances to

On 128 PMs, about the size of one partition of a data center such as a row or a pod, OrigaMIG keeps fewer PMs active than TC, the stronger baseline, in 29 of 30 paired runs over six loads, while migrating 29% to 49% fewer VMs. Against the default placement (FF), it keeps up to 12.5% fewer PMs active, against 9.1% for TC, admits up to 7.8 percentage points more of the requested GPU memory, and uses the least energy per admitted GPU-hour at every load. Across eleven variants of the workload and the hardware, OrigaMIG keeps fewer PMs active than TC in seven, about as many in one, and more in the three with the largest VMs relative to their GPUs. One instance of OrigaMIG serves up to about 1024 PMs, so a larger data center runs one instance per partition of its PMs. On data centers of 8 to 32 PMs, OrigaMIG stays within 4.1% of the optimal number of active PMs, with calls of about one second or less. The remainder of this paper is structured as follows. Section 2 reviews related work, while Section 3 describes the default GI placement policy. Section 4 formalizes the problem as a BILP model, and Section 5 presents our proposed optimizer, OrigaMIG, which rearranges GIs by solving the BILP on small neighborhoods of PMs. Section 6 provides an evaluation of OrigaMIG, Section 7 discusses its use and its limits, and Section 8 concludes with future directions. 2. Related Work The problem of VM placement in cloud data centers is well studied [12–28]. However, GPU virtualization introduces unique constraints that do not arise with CPUs, leading to additional challenges [29]. As a result, GPU-enabled VM placement becomes more complex and challenging. GPU-Sharing VM Placement (GRID Era). NVIDIA introduced GRID [9], whose early generations required co-resident vGPU partitions to be homogeneous. In [30], NVIDIA GRID is examined for GPU-enabled VM placement, highlighting inefficiencies in the first-fit strategy as VM numbers grow. The proposed first-fit increasing algorithm improves acceptance rate (59%), makespan (25%), and energy consumption (21%). In [31], NVIDIA GRID is further analyzed for GPU-aware VM placement, enhancing energy efficiency, reducing host search space, and shortening makespan while tackling GPU resource management challenges in cloud applications. An integer linear programming model for GPU-enabled VM placement using NVIDIA GRID GPU virtualization is proposed in [32], aiming to minimize physical GPU usage in the cloud. Two heuristics match its performance with faster execution. A metaheuristic approach using dense neural networks (DNN) is proposed in [33]. The authors build a simulator for GPU-enabled VM placement with NVIDIA GRID, implement six heuristics, and train DNNs on various configurations. They also explore combining multiple DNNs. Using a custom metric 3

Table 2: MIG-aware placement and scheduling approaches. The parenthesis in Placed unit gives the form in which the unit runs, and Migration lists the entities moved or reconfigured at runtime. Work MIG-serving [35] MIGER [39] ParvaGPU [8] Turkkan et al. [11] Zambianco et al. [10] Ting et al. [43] OrigaMIG

Sharing MIG MIG+MPS MIG+MPS MIG MIG MIG MIG

Placed unit DNN services (pods) DL jobs (MPS processes) DNN inference services (MPS processes) LLM replicas (pods) Generic requests (unspecified) LLM inference jobs (unspecified) VMs

Profile chosen by GIs/unit Infrastructure Scheduler Several Homog. cluster Scheduler One Homog. cluster Scheduler Several Homog. cluster Request Request Request Request

One One One Several

meet high request rates. To reduce GPU non-contiguous space inefficiency, Segment Relocation redistributes instances, while Allocation Optimization minimizes fragmentation by resizing partitions. Evaluations on A100 GPUs show that ParvaGPU ensures service-level objective (SLO) compliance while reducing GPU usage. Placement, Fragmentation, and Migration. Tang et al. [40] tackle GPU sharing from an I/O perspective by accounting for PCIe data-transfer bottlenecks in MIG-enabled environments. They introduce a PCIe-bandwidth-aware scheduler that places MIG partitions so as to avoid PCIe-bandwidth contention, thereby preventing performance degradation when multiple partitions contend for host-to-GPU links. In [41], in the fractional-sharing setting, authors identify GPU fragmentation as a key inefficiency in large ML clusters, where traditional bin packing fails to address partial GPU allocations. They propose Fragmentation Gradient Descent (FGD), which quantifies fragmentation and schedules tasks along its steepest descent to optimize GPU use. Evaluated on a 6,200-GPU cluster, FGD reduces unallocated GPUs by up to 49%, reclaiming 290 more GPUs than existing schedulers. Saraha et al. [42] dynamically fuse and split MIG partitions at runtime to improve throughput and energy efficiency. Turning to fragmentation, Turkkan et al. [11] formulate MIG placement and migration as a mixed-integer program for large language model (LLM) inference workloads. Two online fragmentation-aware MIG schedulers have also been proposed [10, 43]: the former minimizes a fragmentation metric through single-pass placement, while the latter combines conditional load balancing with dynamic repartitioning and migration under a makespan objective. Villarrubia et al. [44, 45] study offline moldable-task MIG scheduling, first with an approximation-bound heuristic and subsequently with deep reinforcement learning. In the fractional GPU-sharing setting, Lettich et al. [46] extend FGD with power awareness, while Wu et al. [47] apply deep reinforcement learning to defragment shared GPU clusters. Finally, Flex-MIG [48] relaxes MIG’s one-to-one execution model using host-side memory collectives, a complementary direction that future placement schedulers may exploit. Table 2 summarizes how OrigaMIG differs from the works that account for the MIG placement constraints. Unlike the surveyed approaches, which schedule jobs or inference requests, OrigaMIG places VMs that request whole GPU instances, while two of them further sub-divide each GPU

Homog. cluster Homog. GPU pool Single node Hetero. data center

Planning Periodic Online Offline

Migration Pods + GIs GIs GIs

Objective GPUs used JCT under QoS GPU usage under SLO

Periodic Online Online Online

Pods + GIs None Jobs + GIs VMs + GIs

Active GPUs, migrations Fragmentation Makespan Acceptance, consolidation, migrations

through MPS. The three serving systems choose the MIG profile of each service from offline profiles, whereas OrigaMIG, like the fragmentation-aware schedulers, takes the profile as part of the request. Among these works, OrigaMIG is also the only one to model heterogeneous, multi-host infrastructure, capturing host CPU and memory across GPUs that may differ in type and generation, where the others assume a single node or a homogeneous cluster. Finally, OrigaMIG migrates VMs both within and across GPUs and hosts and it jointly optimizes acceptance rate, consolidation, and migration overhead, treating the number of migrations as an explicit objective rather than a by-product of reconfiguration. 3. Default GI Placement Policy In this section, we examine how the default GI placement policy affects a GPU’s ability to host future profiles. We use the configuration flexibility (CF) metric [49] to quantify this flexibility, analyze how default placements influence it, and highlight common inefficiencies. These insights highlight the challenges involved in designing VM placement strategies that align with NVIDIA’s fixed MIG management rules. A configuration G is the set of GI placements on a GPU, each represented as Start:Size in memory slices, so placing a profile p of size g p at start slice z adds the placement z:g p to it. Let S (F, p) denote the set of permissible start slices of p in a set F of free memory slices.

S (F, p) = {z ∈ g p Z≥0 | z ≤ s p , {z, . . . , z + g p − 1} ⊆ F}

(1)

A start slice is a multiple of g p , and the g p slices the GI occupies are all free. The limit s p is the last start slice permitted by the compute slices of the GPU. Given a set P of all supported profiles (see Table 1) and the slices F left free by G, CF(G) is then defined as the total number of possible placements for all profiles within the current GPU configuration as follows: CF(G) =

X

|S (F, p)|

(2)

p∈P

For example, the configuration G = {0:1, 3:1} in Fig. 1(b) leaves F = {1, 2, 4, 5, 6, 7} free and has a CF(G) = 9 because it can accommodate 5 × 1g.5gb, 2 × 1g.10gb, 1 × 2g.10gb, and 1 × 4

3g.20gb profiles. The default GI placement policy observed in our experiments with NVIDIA driver R530 positions a profile within the given configuration to maximize the CF value. For a given GI profile preq , the policy selects the start slice z∗ that maximizes CF, and the lowest such slice when several attain the maximum, as represented mathematically below:         arg maxCF(G ∪ {z:g preq }) z = min     z∈S (F,preq ) ∗

ones due to each profile’s specific slice fitting requirements. Fig. 2 contrasts two GPU configurations with identical CF but different per-profile capacity. As highlighted in Table 3, despite possessing the same CF, Configuration B accommodates more 1g.10gb profiles, albeit at the expense of one fewer 4g.20gb profile. 1g.5gb 0

(3)

1

2

3

1g.5gb 5

4

6

7

6

7

NVIDIA A100 (MIG-Enabled)

The profile cannot be placed when S (F, preq ) is empty. Let us now examine all possible MIG memory configurations for a single A100 GPU, both exhaustively and under the default GI placement policy, to highlight how GI placement affects resource efficiency. Using the CF metric, we show that default allocations frequently result in suboptimal configurations. We employ depth-first search to develop a tree that consists of all possible memory configurations for a single A100 GPU, starting from a state where the GPU is not in use. We generate a new child node for each configuration by adding a new GI. This addition of GIs continues until the GPU cannot accommodate any more, resulting in 78 terminal nodes where no further GIs can be added. The finalized tree encompasses 723 unique configurations. In practical scenarios, the addition or removal of GIs shifts the configuration of the GPU to one of these identified configurations. Configurations may have the same GIs but show different CF values based on how the GIs are arranged in their slices. Defining an optimal configuration as one that attains the highest CF value among all arrangements with the same set of GIs, it is found that 67% of the 723 configurations, or 482 in total, are in suboptimal arrangements. In multi-GPU environments, the probability of encountering different GI profiles becomes more crucial. The default GI placement policy, which sequentially assigns GIs, results in 179 configurations, representing 25% of the total 723 possible configurations in the space, when GIs are only added. This sequential assignment approach can lead to suboptimal GPU states. Take, for instance, the arrival of two 1g.5gb GI profiles. Ideally, in an empty GPU, these GIs should occupy memory slices 4 and 5. However, treating GIs independently may lead to them being placed in slices 4 and 6, which is not the most efficient allocation. Approximately 33%, equating to 59 out of the 179 allocations made by the default policy, fall short of being optimal. Moreover, since the policy does not reposition GIs post-allocation, the departure and subsequent arrival of GIs shift the configuration to any of the 723, and one that was initially optimal can become suboptimal. The CF metric effectively indicates a configuration’s capacity to accommodate new GIs, but it simplifies the optimality calculation by treating different profiles as equivalent. This approach neglects real-world conditions where certain GIs, such as 1g.10gb, might be more likely to occur. Contrary to what might be assumed, sufficient space for a larger profile does not guarantee the fit of smaller

(a) Configuration A 1g.5gb

1g.5gb

0

1

2

3

5

4

NVIDIA A100 (MIG-Enabled)

(b) Configuration B Figure 2: Configurations with identical CF but different per-profile capacity

Table 3: Per-profile capacity of the two configurations in Fig. 2 Profile 1g.5gb 1g.10gb 2g.10gb 3g.20gb 4g.20gb 7g.40gb CF

Configuration A 5 2 2 1 1 0 11

Configuration B 5 3 2 1 0 0 11

In a single GPU with 723 unique configurations, 59% or 428 configurations can support a specific profile more effectively than alternative configurations that have the same profiles arranged in different slices, despite these alternatives having the same or lower CF value. With two GPUs, there are 723+2−1 = 2 261, 726 distinct configurations and in 79%, or 205,575 cases, alternative configurations exist that can accommodate at least one type of profile more effectively, even if they have the same or lower CF compared to the original arrangement. With the addition of more GPUs, the complexity of the configuration space grows significantly, making a thorough examination increasingly difficult, or perhaps impractical. These analyses show that suboptimal configurations are common across the space and among the allocations the default policy makes. The default policy assigns one GI at a time on a single GPU and does not reposition it once allocated. This work therefore proposes a VM placement policy tailored for MIG-enabled cloud data centers, in which migration emerges as a necessary tool to achieve better allocations and mitigate suboptimal configurations. 4. Problem Definition and Objectives We model the problem as a BILP [49] in which requests arrive online, each with requirements and a duration that are unknown a priori, and placement decisions may also migrate 5

∀ j ∈ M, ∀k ∈ K j , ∀p ∈ P jk , ∀z ∈ S (U jk , p)

previously placed VMs. We adopt a discrete-time approach in which the requests arriving in each interval are evaluated and placed alongside the VMs already residing. We solve each interval without knowledge of the requests that follow, which makes the setting non-clairvoyant. Time indices are omitted to enhance readability, and primed variables denote previous-interval state. We assume that a GI is created on the PM before its VM starts or arrives there by migration, so the model places each GI rather than selecting among instances that already exist. The model supports heterogeneity in workloads and infrastructure configurations, closely mirroring real-world environments. Consider N as the set of VMs and M as the set of physical machines (PMs). We refer to the ith VM in N as VMi and the jth PM in M as PM j . The collection of GPUs in PM j is represented by K j . The variable xi j is used to indicate the allocation of VMi to PM j . The set Vi holds the GIs that VMi requests, and is empty for a VM without a GPU. Each GI v ∈ Vi has its own profile pv , which sets its size gv and its compatibility class hv . Similarly, yiv jkz represents the assignment of GI v of VMi to the start slice z of the kth GPU of PM j , and Siv jk is the set of permissible start slices for that GI. The essential symbols are provided in Table 4.    S (U jk , pv ) Siv jk =   ∅

f jkpz ≤ γ jk

mi ≥

−

X

ai xi j −

X

b jφ j −

XX

i∈N j∈M

j∈M

j∈M k∈K j

δi (mi + ωi ) +

XX X

X

ωi ≥

Subject to X xi j ci ≤ C j

(5)

(6)

∀j ∈ M

(7)

i∈N

X

xi j ri ≤ R j

i∈N

X ′ X xi j ≤ xi j ≤ 1 j∈M

j∈M

X X

yiv jkz = xi j

∀i ∈ N

(8)

∀i ∈ N, ∀v ∈ Vi , ∀ j ∈ M

(9)

k∈K j z∈Siv jk

o jku ≤ γ jk

∀ j ∈ M, ∀k ∈ K j , ∀u ∈ U jk

f jkpz + o jku ≤ 1

(14)

XX X

′

(1 − yiv jkz )yiv jkz

∀i ∈ N, ∀v ∈ Vi

(15) (16)

The first term of Eq. (5) is designed to optimize the request acceptance by maximizing the sum of weights ai for each VM allocated. The second term aims to consolidate resources by minimizing the number of active PMs and GPUs, using b j to weight each PM, e jk to weight each GPU, and γ jk to indicate active GPUs. Consolidation reduces fragmentation, which in turn allows the acceptance of the requests that follow. The third term seeks to minimize the migration of VMs and their GIs weighted by δi , thus enhancing system stability and efficiency. The fourth term extends the consolidation to the arrangement of GIs within a GPU by rewarding each start slice left free for a profile p with w p , where P jk holds the profiles of the compatibility class of the GPU. With all w p equal, the term sums the CF of the active GPUs, and unequal w p rank the profiles by their expected demand. The weights place the four terms on a common scale. For example, ai larger than the w p of the start slices its GIs occupy makes its acceptance preferable to the free windows. Constraints set by Eq. (6) and Eq. (7) ensure that the CPU and RAM allocations for each PM do not exceed its respective capacities C j and R j . Eq. (8) guarantees that each VM is allocated to at most one PM, and that a VM allocated in the previous interval stays allocated, so the model may migrate a running VM but never evicts it, whereas Eq. (9) ensures that each accepted VM receives each of its GIs on its own PM, and a rejected VM none. Eq. (10) is designed to prevent overlapping GIs on the same GPU by allowing at most one GI on each memory slice. It also requires γ jk to be set whenever the GPU hosts a GI. Eq. (11) lets f jkpz be set only when no GI occupies any of the g p slices from z, so at the optimum the sum of f jkpz over z equals |S (F, p)| of Eq. (1) for the slices F left free. The bound f jkpz ≤ γ jk keeps the reward off GPUs that host no GI, so at the optimum the term is the sum of the free windows of the active GPUs only. Eq. (12) and Eq. (13) are used to determine φ j and γ jk ensuring that VMs are not assigned to powered-off PMs. Eq. (14) and Eq. (15) count, per VM, whether the VM (resp. any of its GIs) is placed on a PM (resp. a GPU and start slice) that it did not previously occupy, and a single inter-machine migration counts once. A GI is created before its VM starts, so a different slice is a different GI and the change is counted as a migration. Finally, Eq. (16) defines the domains of all variables. Table 5 presents example parameters for various NVIDIA A100 MIG profiles. In this illustration, it is assumed that H jk =

(4)

∀j ∈ M

∀i ∈ N

xi j , yiv jkz , φ j , γ jk , mi , ωi , f jkpz ∈ {0, 1}

e jk γ jk

w p f jkpz

X ′ (1 − xi j )xi j

j∈M k∈K j z∈Siv jk

j∈M k∈K j p∈P jk z∈S (U jk ,p)

i∈N

(13)

j∈M

Eq. (4) applies Eq. (1) to GI v of VMi on the k GPU of PM j , with all of its memory slices U jk free, so Siv jk does not depend on the GIs already placed. The set is empty on a GPU of a different compatibility class, where the classes hv and H jk are P P P categorical. We write o jku = i∈N v∈Vi z∈Siv jk , z≤u<z+gv yiv jkz for the sum over the GIs that would cover slice u of the kth GPU of PM j , which Eq. (10) limits to one, so o jku indicates whether the slice is occupied. Using these definitions, the problem is formulated as follows: XX

(12)

i∈N v∈Vi z∈Siv jk

th

Maximize

∀ j ∈ M, ∀k ∈ K j , ∀p ∈ P jk , ∀z ∈ S (U jk , p)

xi j ≤ φ j ∀i ∈ N, ∀ j ∈ M XX X γ jk ≤ yiv jkz ∀ j ∈ M, ∀k ∈ K j

if hv = H jk otherwise

∀i ∈ N, ∀v ∈ Vi , ∀ j ∈ M, ∀k ∈ K j

(11)

(10)

∀u ∈ {z, . . . , z + g p − 1} 6

Table 4: Table of notations Notation N M VMi PM j Kj U jk xi j ′ xi j yiv jkz ′ yiv jkz ai bj e jk mi ωi δi ci Cj ri Rj Vi pv gv Siv jk φj γ jk H jk hv o jku P jk wp f jkpz

penalizes migrations without bounding their total. A penalty rather than a bound lets the model migrate a VM whenever the resulting gain in acceptance or consolidation outweighs δi . Moreover, inter-machine migrations (mi = 1) of VMs holding a GI also flip ωi = 1, but intra-machine migrations do not result in machine switches. This model characteristic halves the penalty of intra-machine migrations relative to inter-machine migrations. Complexity. The size of the BILP depends on the number of VMs and on the size of the infrastructure. The model contains |N||M| variables xi j . In addition, each GI has one variable yiv jkz for every permissible start slice on every GPU of its compatibility class, which is at most |U jk | per GPU. As a result, the number of variables, constraints, and nonzero coefficients is proportional to |N| multiplied by the number of PMs and GPUs, P |M| + j∈M |K j |, and the model is built in time proportional to its size. Solving the model is much harder than building it. The problem includes bin packing as a special case, and bin packing is strongly NP-complete [50]. Consequently, the BILP is strongly NP-hard, and no exact algorithm can solve it in polynomial time unless P = NP. In practice, the solver finds a good placement quickly, because keeping all VMs in place and rejecting the new requests is always a feasible solution. Most of the time is spent on proving that a placement is optimal, and this proof is expensive when many PMs and GPUs are identical.

Description Set of VMs Set of PMs The ith VM in the set N The jth PM in the set M Collection of GPUs in PM j Collection of memory slices in GPU k of PM j Indicates allocation of VMi to PM j Represents previous allocation state of VMi to PM j Represents assignment of GI v of VMi to start slice z of GPU k Previous assignment of GI v of VMi to start slice z of GPU k Weight associated with VMi in the objective function Weight associated with PM j in the objective function Weight associated with GPU k of PM j in the objective function Binary indicator of inter-machine migration of VMi Binary indicator that a GI of VMi changed GPU or slice Migration penalty of VMi , and zero for newly arrived VMs CPU requirement of VMi CPU capacity of PM j RAM requirement of VMi RAM capacity of PM j Set of GIs requested by VMi Profile of GI v Size of GI v Permissible start slices of GI v of VMi on GPU k of PM j Binary variable indicating if PM j is powered-on Binary variable indicating if GPU k of PM j hosts a GI Compatibility class of the kth GPU in PM j Compatibility class of GI v Indicates whether slice u of GPU k of PM j is occupied Profiles supported by GPU k of PM j Weight of a free start slice of profile p Indicates if start slice z of GPU k is free for profile p

Table 5: Values for A100 40GB MIG profiles; other GPU families supply their own.

Profile 1g.5gb 1g.10gb 2g.10gb 3g.20gb 4g.20gb 7g.40gb

gv 1 2 2 4 4 8

sp 6 6 4 4 0 0

5. The Proposed Method

hv 100 100 100 100 100 100

In this section, we present OrigaMIG. As Section 4 explains, the BILP is strongly NP-hard, and proving a placement optimal becomes expensive as the data center grows. OrigaMIG therefore solves the BILP for a few PMs at a time and keeps the rest of the data center fixed. It has three components. An arrival rule places each request immediately, and triggers decide when the optimizer runs. The optimizer selects a neighborhood of PMs and solves the BILP on it. An executor turns the solution into a valid order of live migrations. OrigaMIG never removes a running VM.

100 for every j ∈ M and k ∈ K j , when k corresponds to an A100 GPU. The collection U jk then holds the 8 memory slices of the GPU. The profiles with identical memory requirements are given similar gv values, although their compute slice needs may vary. These example settings of gv and s p demonstrate how the allocation can be managed. The weights ai can be used to rank VMs based on predefined criteria. For example, assigning them equal values leaves the tendency to accept smaller VMs preferentially, since a GPU can host several small GIs in place of one large GI. Higher ai values for larger GPU demands mitigate this tendency. In contrast, the weights b j can modify the selection priority of physical machines. For example, higher values for machines with fewer GPUs improve consolidation. The parameter δi , set to zero for new VMs, omits their initial placement from the migration count. Conversely, a higher value inhibits the migration of VMs of interest. For instance, an elevated value assigned to a previously migrated VM reduces the likelihood of frequent VM preemptions. δi sets the cost of a migration rather than the number permitted, as Eq. (5)

5.1. Arrival Rule and Triggers OrigaMIG places each arriving request immediately, without a solver. It selects the first PM that can host the VM, and the default GI placement policy of Section 3 places each GI on its GPU. A VM placed by this arrival rule becomes a running VM from then on. A request that the arrival rule cannot place joins the pending set Q. An admission call starts whenever Q is not empty, and a consolidation call starts when the threshold below is reached. We also allow a timer to start consolidation calls periodically, but we leave it off because the threshold already reacts to fragmentation. Only one call runs at a time, and admission calls take priority. For a compatibility class h, the threshold uses the gap X X Γh = γ jk j∈M k∈K j , H jk =h

−

l 1 X

X

|Uh | i∈N v∈V , h =h i

7

v

m gv ,

(17)

where the sum over i runs over the placed VMs, and |Uh | is the number of memory slices of a GPU of class h. The first term counts the active GPUs of class h. The second term is a lower bound on the number of GPUs of class h needed by the placed GIs of this class. The gap Γh therefore bounds the number of GPUs that consolidation can switch off, and the gap grows with fragmentation. We keep both sums as counters, so Γh is updated in constant time. A consolidation call for class h starts when Γh ≥ θ. The threshold θ is at least one, because Γh = 0 proves that no GPU can be switched off. A call that changes nothing disables the threshold of class h until Γh increases or a VM departs from a PM of class h. A PM of class h is a PM with at least one GPU of class h. We also treat the PMs without GPUs, M0 , as one more class. For this class, the gap is P P X m l  i∈N0 ci i∈N0 ri , , (18) Γ0 = φ j − max Cmax Rmax j∈M

Algorithm 1: Neighborhood selection of OrigaMIG procedure AdmissionCall(Q) M̂ ← ∅ 3 for each VMi ∈ Q, oldest first do 4 C ← PMs whose free resources fit VMi 5 if C , ∅ then 6 add C to M̂, fewest VMs first 7 else 8 C ← PMs that would fit VMi if empty 9 if C , ∅ then 10 add C to M̂, by free memory slices 11 else 12 reject VMi 1

2

13 14 15

fill M̂ with active PMs, by free memory slices, then CPU add a powered-off PM that fits the oldest VM of Q, if any N̂ ← VMs on M̂, plus VMs of Q whose first PM is in M̂

where N0 holds the placed VMs that run on M0 , and Cmax and Rmax are the largest CPU and RAM capacities of a PM of M0 . The second term is a lower bound on the number of PMs of M0 needed by the VMs of N0 .

procedure ConsolidationCall(h) S ← active PMs of class h, fewest VMs first P P 18 keep j ∈ S only if b j + k∈K j , γ jk =1 e jk > w p CF j + i∈N j 2δi 19 R ← other active PMs of class h, plus active PMs of M0 20 keep at most 12 Mmax PMs in S ; fill M̂ with S , then R 21 while some PM of S cannot be emptied into R do 22 remove the last PM from S

5.2. Neighborhood Selection

23

0

16

17

Each call selects a neighborhood M̂ ⊆ M of at most Mmax PMs. The set N̂ holds the VMs that run on M̂ and the pending VMs of the call. The call skips a PM whose VMs would raise |N̂| above Nmax . The only exception is the first PM selected for the oldest pending VM, which ensures that every admission call reaches a decision for that VM. The limits Mmax and Nmax keep the restricted BILP small enough to be solved to optimality within seconds. OrigaMIG relies on four relations among the weights of Eq. (5). First, ai exceeds b j plus e jk for each GI of the VM, so the admission of one VM is worth switching on a PM and the GPUs that its GIs use. Second, b j and e jk exceed the migration penalties of a few VMs, so switching off a PM is worth a few migrations. Third, e jk exceeds w p times the CF of an empty GPU of its class, which Section 3 defines. As a result, a GPU that becomes active always costs more than the free start slices it adds. Fourth, δi of a placed VM is large compared with w p . A migration made only to raise CF must then add more than δi /w p free start slices. OrigaMIG therefore does not select PMs by CF. Instead, each neighborhood aims at an admission or at switching off PMs. Admission call. The selection of an admission call is in Algorithm 1. The free resources of a PM fit a VM when the PM has enough free CPU and RAM and each GI of the VM fits one of its GPUs. A test takes the GIs one by one, starting from the largest, and a GI fits a GPU when the GPU has enough free memory slices and compute slices for the profile of the GI, and Table 1 lists the profiles of the A100. The test ignores start slices, which a rearrangement can change. The powered-off PM is added because it can receive displaced VMs, and it can host the pending VM when the arrival rule failed only because it places the GIs one at a time. The call rejects a pending VM if

N̂ ← VMs on M̂

the solution does not admit it, and the other pending VMs wait for the next call. Consolidation call. The selection of a consolidation call is in Algorithm 1. The sources S are the PMs that the call tries to empty, and the receivers R take their VMs. In the algorithm, CF j is the sum of the CF of the active GPUs of j, and N j the VMs running on j. A VM that leaves a PM costs up to 2δi , because its move sets both mi and ωi . The PMs without GPUs join the receivers because a VM without GIs may move to them in every consolidation call. 5.3. Restricted BILP Each call acts as one interval of Section 4, with M̂ and N̂ in place of M and N. This fixes all other PMs and VMs, and it sets xi j = 0 for every VM of N̂ and every PM outside M̂. The primed variables hold the placement at the start of the call. The solver starts from the current placement with all pending VMs rejected, which satisfies every constraint. It runs multithreaded, and it stops at optimality or when a time limit is reached. OrigaMIG then evaluates Eq. (5) over M̂ and N̂ for the returned placement and for the current placement. It recomputes φ j , γ jk , mi , ωi , and f jkpz from each placement, because a solution found before the proof of optimality may leave them at other values. It also subtracts δi for each parking move of VMi that the executor plans within a PM, and 2δi for each parking move to another PM. OrigaMIG applies the plan only if its value is strictly larger than the value of the current placement. Fixing most of a solution and solving the rest exactly is large neighborhood search [51, 52]. Each call is one step of 8

Table 6: GPU instance profiles on A30 24GB and their values in the BILP

this search on the BILP. As Section 4 explains, the size of the restricted BILP is proportional to |N̂| multiplied by | M̂| + P j∈ M̂ |K j |, which Mmax and Nmax bound, so it stays bounded as the data center grows.

Profile 1g.6gb 2g.12gb 4g.24gb

Compute 1/4 2/4 4/4

Memory 1/4 2/4 4/4

Instances 4 2 1

Start Slices 0, 1, 2, 3 0, 2 0

gv 1 2 4

sp 3 2 0

hv 30 30 30

5.4. Execution of Migrations 6. Evaluation

The solution is a target state, not an order of actions. As Section 1 explains, the destination GI must exist before a live migration. In addition, the source GI stays until the migration completes. The executor therefore plans the steps on a copy of the state before it acts. Each step creates the new GIs of one VM at their start slices through the NVIDIA management library. It then migrates or starts the VM and destroys its old GIs. A step is ready when its new slices are free. A start or a move between PMs also needs free CPU and RAM on the destination. If no step is ready, the remaining steps block each other in a cycle, which may consist of a single step. The executor then parks the VM whose removal makes the most steps ready. It moves this VM to free memory and compute slices of its class and to free CPU and RAM that no remaining step needs. A parked VM blocks no step again, so each VM is parked at most once. For example, in Fig. 1(c), parking the VM of the 3g.20gb GI on another GPU unblocks all steps. If no parking place exists, OrigaMIG discards the plan, and no step has run. Otherwise, OrigaMIG switches on the PMs that the plan needs before the first step, and it powers off the PMs left empty after the last step. While a call runs, the arrival rule places no request on M̂, and a departure only removes steps.

We evaluate OrigaMIG in simulation against online placement policies and against the optimum of the BILP. The evaluation answers four questions. First, does OrigaMIG admit more requests, keep fewer PMs and GPUs active, and use less energy than the baselines, across loads, workloads, and hardware (Sections 6.4 and 6.5)? Second, what do its migrations cost (Section 6.6)? Third, what does each of its components contribute, and does OrigaMIG keep up as the data center grows (Section 6.7)? Fourth, how far is it from the optimum, and how does the cost of finding the optimum grow (Sections 6.8 and 6.9)? 6.1. Experimental Setup We evaluate the placement policies in GPUCloudSim [30]. The simulated PMs carry up to two MIG-enabled GPU models, the A100 40GB and the A30 24GB. Their profiles and values in the BILP are in Tables 1, 5, and 6. Each model forms its own compatibility class (H jk = 100 for the A100, H jk = 30 for the A30), so a GI runs only on the model of its profile. The BILP of Section 4 is modeled and solved with the CP-SAT engine of Google OR-Tools [53]. In each OrigaMIG call, the solver runs on eight threads with a time limit of 10 s, and the neighborhood holds at most Mmax = 16 PMs and Nmax = 64 VMs. The consolidation threshold is θ = 1, the smallest value that Section 5.1 allows. Every 10 s, OrigaMIG checks whether to start a call. The weights are ai = 100, b j = 50, e jk = 20, and w p = 1 for every profile, and the migration penalty is δi = 10 for a placed VM and 0 for a new one. They satisfy the four relations of Section 5.2. First, a VM requests at most two GIs, so ai exceeds b j + 2e jk = 90, the cost of switching on a PM and two GPUs. Second, b j exceeds 4δi = 40, the cost of two moves between PMs, and e jk exceeds δi = 10, the cost of one move within a PM. Third, e jk exceeds the CF of an empty A100, 18, and of an empty A30, 7. Fourth, a migration made only to raise CF must gain more than δi /w p = 10 in CF, more than half the CF of an empty A100, so OrigaMIG migrates only to admit a VM or to switch off a PM or a GPU. In Sections 6.4–6.7, unless stated otherwise, the data center has 128 PMs, 96 with two A100 GPUs and 32 with two A30 GPUs. Each PM has 80 cores and 512 GB of RAM. With 128 PMs, the data center is about the size of one partition, such as a row or a pod, the unit on which large-scale allocators optimize [54, 55]. We study larger data centers in Section 6.7. Each run has a warm-up of 48 h, after which we measure for 3 days. We repeat each run with five seeds in Section 6.4 and with three seeds in the other subsections. A seed gives every policy the same requests, so we compare two policies on the same

5.5. Properties and Cost Every intermediate state satisfies Eq. (6), Eq. (7), and Eq. (10), because each step uses only free resources and a migrating VM holds resources at both ends. Each constraint of the BILP involves one PM, one GPU, or one VM, together with the xi j and yiv jkz that link them. No VM of N̂ is placed outside M̂, and no other VM runs on M̂. Therefore, a feasible solution of the restricted BILP is feasible for the full BILP when combined with the fixed part of the data center, and the two objectives differ by a constant. This holds for any M̂, so the guarantees below do not depend on the selection rules. OrigaMIG offers three guarantees. First, a call never lowers the value of Eq. (5), since a plan is applied only if it strictly improves the current placement after parking moves are counted. Second, if the solver proves optimality and the plan is applied, the placement is optimal for Eq. (5) among all placements that keep every running VM, admit only the pending VMs of N̂, and change only M̂. Third, without arrivals and departures, the calls stop changing the data center. The migration terms of Eq. (5) are never positive, so each applied plan strictly raises the other terms. These terms take only finitely many values. The time limit can invalidate only the second guarantee. However, OrigaMIG does not guarantee optimality for the whole data center or over time, since the selection rules are heuristics and the setting is non-clairvoyant. Finally, a call costs one pass over the PMs, solving within the time limit, and at most 2|N̂| steps. 9

load ρ = λ E[L] E[ f ]/|K|, where L is the lifetime of a VM, f the share of the memory slices of a GPU that the GIs of the VM occupy, and |K| the number of GPUs. The GPU model of a VM is drawn so that both models carry the same load ρ. The workload of Section 6.8 has ρ = 0.74.

Table 7: Powers of the energy model Device PM without its GPUs (2× Xeon Platinum 8380) A100 40GB PCIe A30 24GB

Pidle 143 W 50 W 33 W

Pmax 647 W 250 W 165 W

Source [56] [58, 59] [57]

6.3. Baselines

seed before averaging over seeds. We report means with 95% confidence intervals. We measure the following metrics. The acceptance is the share of the requested memory slices that the data center admits, so that a large request counts more than a small one. The active PMs and active GPUs are the time averages of the numbers of PMs that host a VM and of GPUs that hold a GI. The packing density is the share of the memory slices of the active GPUs that GIs occupy. The energy is that consumed by the active PMs and their GPUs, and we also report it per admitted GPU-hour. The switchings are the number of PMs switched on per hour, observed once per minute. For OrigaMIG and TC, we count the migrations per hour, and, for OrigaMIG, the time that a request waits in Q. We compute the energy as follows. We assume that a PM without VMs is switched off immediately and switched on when a VM needs it, and we ignore the time and energy of switching. An active PM draws the power that a SPECpower_ssj2008 measurement of a server with the same CPUs reports for its load [56]; the load is the share of its cores that the VMs use, and we interpolate linearly between the reported load levels. A GPU with GIs draws Pidle + (Pmax − Pidle ) u, where u is the share of its compute slices that GIs occupy, as in GPUCloudSim [30]. A GPU without GIs draws Pidle , since a GPU cannot power off while its PM is running [57]. Table 7 lists the powers. The idle power of the A100 is measured on its SXM4 version [58]. We found no idle-power measurement for the A30, so we estimate its idle power by scaling its maximum power with the idle-to-maximum power ratio of the A100. In the energy per admitted GPU-hour, a GI counts as the fraction of a GPU equal to its share of the compute slices.

We compare OrigaMIG against the following placement policies. All of them are online and non-clairvoyant like OrigaMIG, and they place the GIs of a multi-GI VM one GI at a time. • First-Fit (FF) pairs first-fit host selection [30] with the default GI placement policy of Section 3: the VM is placed on the first host that can accommodate it, and each GI is placed at the start slice that maximizes CF, with ties broken by the lowest slice. FF is the default placement, and we report the gains of the other policies over it. • Minimum Fragmentation Increment (MFI) is the online policy of Zambianco et al. [10]. It scores the fragmentation of a GPU by summing, for each profile whose memory slices fit in the free slices of the GPU, the number of memory slices of the profile times the number of its start slices at which the required slices are not all free. A GI goes to the GPU and start slice that increase this score the least. • Turkkan Compaction (TC) is the rule-based placement and compaction of Turkkan et al. [11]. A GI goes to the GPU whose joint slice utilization (sm + sc )/(S m + S c ) after the assignment is the largest, at a start slice taken from a fixed preference order for the A100. Here sm and sc are the used memory and compute slices of the GPU, and S m and S c are its memory and compute slices. Periodically, TC examines the active GPUs, starting from the least utilized, and vacates a GPU when all its workloads fit on the other active GPUs by the same rule. The moves use only resources that were free before the compaction, so they apply at once. If a GPU cannot be vacated, TC adds a free GPU to the compaction and keeps the moves only if they vacate at least two GPUs.

6.2. Workload To our knowledge, no public trace captures VM requests for MIG profiles. Existing GPU cluster traces, such as Alibaba’s [41, 60], record jobs requesting whole GPUs or GPU fractions, which do not map directly to MIG profiles. We therefore generate synthetic workloads, combining transient jobs with the long-lived, heterogeneous tenants of self-hosted LLM serving [61]. As a check, we map the Alibaba trace to MIG profiles in Section 6.5. Requests arrive according to a Poisson process. Of the requests, 70% are jobs with a mean lifetime of 2 h, and 30% are tenants with a mean lifetime of 24 h. Lifetimes are exponential. A VM requests one GI, or two GIs with probability 0.5. All its GIs are of one GPU model, and each profile of that model is equally likely. A VM also requests 4 cores and 16 GB of RAM per compute slice of its GIs. The lifetime of a VM starts when it is admitted. We set the arrival rate λ by the offered

Adaptations. MFI and TC were evaluated with single GIs on GPUs of one model, without CPU and RAM. We adapt both to VMs on PMs and otherwise keep their rules. In both, the GIs of a VM, largest first, go to one PM with enough CPU and RAM, so a VM moves as a whole. A GI goes only to GPUs of its class. Ties are broken by the lowest PM, GPU, and start slice, and a VM that fits nowhere is rejected. MFI computes the score of a GPU with the profiles and start slices of its model and chooses the PM with the smallest total increase. TC chooses the PM with the largest mean utilization of the GPUs that the VM uses. The original TC places a batch of new workloads and keeps those that do not fit pending. We place each VM when it arrives. We use the start slices of the default GI placement policy, which also covers the A30. TC compacts each class every 15 min, a period the original leaves open. It takes the idle 10

|N| = 64

|N| grows with |M|

Model size

|M| = 32

0.5, OrigaMIG keeps 12.5% fewer PMs active than FF, TC 9.1%, and MFI 2.7%. TC packs the active GPUs tighter, 96.8% against 92.5%, and keeps fewer GPUs active, because it vacates GPUs, whereas the weights of OrigaMIG value an empty PM more than an empty GPU. As the load grows, fewer PMs can be emptied, and the reduction of OrigaMIG falls to 6.8% at a load of 0.85 and 2.8% at 1.0. Paired by seed, OrigaMIG keeps fewer PMs active than TC in 29 of 30 runs, by 0.4% to 3.7% depending on the load. At high load, the requests compete for GPUs. At a load of 1.0, OrigaMIG admits 91.5% of the requested memory slices, against 83.7% for FF, 87.0% for MFI, and 90.8% for TC. An admission call rearranges GIs to fit a request that the arrival rule could not place, and the admitted requests wait 1.5 s on average. As OrigaMIG and TC admit more work at high load, they also use more energy there than FF (Table 8). Per admitted GPU-hour, OrigaMIG uses the least energy at every load, 4.0% less than FF at a load of 0.5 and 2.9% less at 1.0. It migrates 9.1 VMs per hour at a load of 0.5 and 11.5 at 1.0, against 12.7 and 20.2 for TC, that is, 29% to 49% fewer across the loads (Section 6.6). In exchange, it switches PMs on more often than the other policies.

Limit reached, final gap

Time to optimality (s)

(a) Increasing PMs 103

9.8%

limit (20 min) 2%

14.3%

27.7%

×6.9

102 10

×7.2

1

100 16 32

32 64

64 128

128 256

256 512

PMs |M| (top) and GPUs (bottom)

Time to optimality (s)

(b) Increasing VMs 103

limit (20 min)

×61

102 101

×6.6

100 8

16

32

64

128

VMs |N| on |M| = 32 PMs (64 GPUs)

6.5. Robustness We vary one factor of the workload or the hardware at a time, at a load of 0.85 (Table 9); the other factors keep the values of Sections 6.1 and 6.2. For the trace variant, we map the Alibaba GPU trace of 2023 [41] to A100 profiles. A pod that requests a share f of a GPU gets the smallest profile that has at least ⌈7 f ⌉ compute slices and ⌈8 f ⌉ memory slices. A pod that requests one or two GPUs gets one or two 7g.40gb GIs. We drop the pods without a GPU and those that request more than two. The trace ends with a list of the pods still alive, so we keep only the pods created in its last 34 days. We compress the timeline so that the offered load is 0.85, and seed s starts the trace at (s − 1)/5 of its length. Of the resulting GIs, 77% are 7g.40gb. Fig. 5 shows the gains of MFI, TC, and OrigaMIG over FF. The gains in acceptance follow the rejections of FF. With smaller profiles, one GI per VM, lognormal lifetimes, or the trace, FF admits more than 98%, and no policy gains a full percentage point. With two GIs per VM and with 10% tenants, FF admits 92.4% and 91.9%, and TC admits 5.3 and 5.4 percentage points more. TC keeps fewer PMs active than FF under every variant, and MFI gains less than TC under every variant but one. OrigaMIG keeps fewer PMs active than TC in seven of the eleven variants, about as many in one, and more in three. Its largest lead comes when the CPU and the RAM of the PMs run out before their GPUs. FF then admits only 70.3%, and neither MFI nor TC admits more, as both rank PMs by the state of their GPUs. The BILP of OrigaMIG also constrains the cores and the RAM (Eqs. (6) and (7)), so OrigaMIG admits 2.6 percentage points more than FF and keeps 2.6% fewer PMs active, against 0.7% for TC, with 9.4 migrations per hour against 18.1. With smaller profiles, with one GI per VM, and with 10% or 60% tenants, OrigaMIG also keeps fewer PMs active than TC and

Figure 3: Time to solve one interval to optimality as the numbers of PMs and VMs increase. Each point is the median of three seeds, and the error bars show the minimum and the maximum. The dotted line shows how the time would grow if it only doubled at each step, as the size of the model does. In (a), the dashed line keeps 3/4 of the memory slices occupied, so that the number of VMs grows with the number of PMs. A cross marks a point at which most solves reached the time limit, together with the median final gap.

GPU from an active PM when one has an idle GPU, so that a compaction does not switch on a PM. Each VM moves at most once in a compaction, and a GPU that receives a VM is not vacated later in it. The executor of Section 5.4 runs the moves of TC as live migrations, at the same cost as those of OrigaMIG, and no request is placed on the PMs of a compaction until its moves end. In addition, to establish an upper bound, we report Optimal (OPT), which solves the BILP of Section 4 over the whole data center from a given state, which bounds the value any placement can reach from that state (Section 6.8). Of the online policies compared, only OrigaMIG and TC migrate. The other works in Table 2 are not used as baselines because they schedule jobs or inference services on homogeneous clusters or single nodes, whereas OrigaMIG places VMs across a heterogeneous, multi-host data center. 6.4. Comparison with the Baselines We compare OrigaMIG with FF, MFI, and TC as the offered load grows from 0.5 to 1.2 (Fig. 4 and Table 8). Each value is a mean over five seeds, and Fig. 4 shows the 95% confidence intervals. At low load, the data center admits nearly every request, so the policies differ in the PMs they keep active. At a load of 11

90 80 70 0.75

1.0

1.2

100 80 60

0.5

0.75

1.0

1.2

95 90 85 0.5

Offered load

Offered load

OrigaMIG

(c) Packing density Occupied slices (%)

100

0.5

TC

(b) Active PMs Share of the PMs (%)

Admitted slices (%)

(a) Acceptance

MFI

0.75

1.0

1.2

kWh per admitted GPU-hour

FF

(d) Energy per GPU-hour 0.45 0.44 0.43 0.42 0.5

0.75

1.0

1.2

Offered load

Offered load

Figure 4: FF, MFI, TC, and OrigaMIG on 128 PMs as the offered load grows, over five seeds. The error bars show the 95% confidence intervals. Table 8: Results at two offered loads, over five seeds Load 0.75

1.0

Policy FF MFI TC OrigaMIG FF MFI TC OrigaMIG

Accept. (%) 98.5 99.4 99.7 99.5 83.7 87.0 90.8 91.5

Active PMs 109.5 106.9 100.3 99.0 125.4 125.6 123.3 122.0

Active GPUs (%) 83.1 78.2 72.6 76.7 95.8 93.1 89.6 94.6

Table 9: Variants of the workload and the hardware Factor Profile mix VMs with two GIs Lifetimes Tenants PMs Cores and RAM of a PM Requests

Default uniform 50% exponential 30% 96 A100, 32 A30 80, 512 GB synthetic

Packing (%) 84.0 90.1 97.3 92.1 86.2 91.5 97.5 92.9

Energy (MWh) 5.57 5.57 5.47 5.43 6.52 6.67 6.76 6.75

Switch./h 5.2 2.8 4.8 9.9 4.1 2.1 4.3 8.7

Migr./h 0 0 17.3 11.4 0 0 20.2 11.5

Wait (s) 0 0 0 0.1 0 0 0 1.5

6.6. Cost of Migrations

Variants larger profiles half or twice as likely 0%, 100% lognormal, σ = 1.5, same means 10%, 60% 128 A100; 128 A30 32, 256 GB Alibaba trace on 128 A100 PMs

At a load of 0.85, we vary the migration penalty δi of OrigaMIG from 0 to 40, and we run TC with a compaction every 15 min or every hour (Fig. 6 and Table 10). For δi ≥ 12.5, switching off a PM no longer outweighs the cost of two migrations between PMs, so the second relation of Section 5.2 no longer holds. A migration between PMs copies the RAM of the VM and the memory of its GIs at half the 25 Gbit/s speed of a PM.

migrates fewer VMs. With smaller profiles, for instance, it keeps 4.1% fewer PMs active than FF, against 2.7% for TC, with 9.8 migrations per hour against 29.9. On the trace, most GIs take a whole GPU, so MFI and TC find little fragmentation to remove, and TC keeps 1.4% fewer PMs active than FF. OrigaMIG keeps 7.5% fewer with about as many active GPUs, at the cost of 61.3 migrations and 8772 GB per hour, against 10.7 and 615 GB for TC. With A100 PMs only, the two keep about as many PMs active, 5.6% and 5.7% fewer than FF, and OrigaMIG migrates 9.3 VMs per hour against 18.5. TC keeps fewer PMs active than OrigaMIG with larger profiles, with two GIs per VM, and with A30 PMs only, where the VMs are large relative to their GPUs. Its reductions over FF are 4.5%, 7.8%, and 6.0%, against 2.3%, 4.7%, and 3.4% for OrigaMIG (Section 7).

The penalty sets the trade-off between migrations and active PMs. Without it, δi = 0, OrigaMIG migrates 142.5 VMs per hour, or 4.05 per admitted VM, and copies 21106 GB per hour, for 8.0% fewer PMs active than FF. With δi = 5 and 10, it migrates 12.3 and 12.8 VMs per hour, about a tenth as many, and keeps 6.3% and 6.5% fewer PMs active. With δi = 10, it copies 1316 GB per hour, or 0.36 migrations per admitted VM, and a migration between PMs takes 70 s on average. With δi = 20, OrigaMIG migrates 6.2 VMs per hour for 4.3% fewer PMs, and with δi = 40, it almost never migrates and keeps as many PMs active as FF. TC migrates 19.9 VMs per hour with a compaction every 15 min, for 4.8% fewer PMs, and 10.0 with a compaction every hour, for 3.1%. For each period of TC, a value of δi thus makes OrigaMIG migrate fewer VMs and keep fewer PMs active than TC (Fig. 6).

With lognormal lifetimes and the same means, many tenants outlive the simulated days, so the demand stays below the offered load. Over the measured days, the GIs occupy the memory slices of 160 GPUs, about as many as at a load of 0.65 in Setup 1 (158). The reductions under this variant, 11.2% for OrigaMIG and 9.4% for TC, are close to those of Setup 1 at that load, 11.8% and 9.8%, so the shape of the lifetimes changes them little.

The call times of Table 10 depend on δi through the neighborhoods. A consolidation call takes a PM as a source only if emptying it outweighs the penalties of its VMs (Algorithm 1). With δi ≤ 5, lightly loaded sources fill half of the neighborhood, and a call holds about 11 VMs, against 44 to 58 with δi ≥ 10. 12

MFI

TC

OrigaMIG

(a) Acceptance

(b) Active PMs

Default Smaller profiles Larger profiles One GI per VM Two GIs per VM Lognormal lifetimes 10% tenants 60% tenants A100 PMs only A30 PMs only Fewer cores and RAM Alibaba trace 0

−5

10

5

0

Gain (pp)

5

10

15

Reduction (%)

Figure 5: Gains of MFI, TC, and OrigaMIG over FF under each variant of Table 9, at a load of 0.85, over three seeds. The error bars show the 95% confidence intervals. Table 10: Migrations and gains at a load of 0.85. The call time is the median runtime of a call

Fewer active PMs than FF (%)

Policy TC, every 15 min TC, every hour OrigaMIG, δi = 0 OrigaMIG, δi = 5 OrigaMIG, δi = 10 OrigaMIG, δi = 20 OrigaMIG, δi = 40

Seeds 3 3 3 3 3 3 3

Migr./h 19.9 10.0 142.5 12.3 12.8 6.2 0.1

Migr. per VM 0.56 0.28 4.05 0.35 0.36 0.18 0.00

GB/h 1085 530 21106 1272 1316 713 2

δδii ==510

6 δi = 20

4

15 min

60 min

2 0

OrigaMIG TC

δi = 40

10−1

100

101

Active PMs 113.4 115.4 109.6 111.6 111.4 114.0 119.2

Energy (MWh) 6.19 6.22 6.14 6.17 6.16 6.16 6.13

Call (s) – – 4.10 0.35 5.64 4.98 4.92

Both kinds of calls are needed. Without consolidation calls, OrigaMIG keeps 119.5 PMs active, as many as FF with 119.1, and admits 96.5% of the requested slices instead of 99.5%. Without admission calls, it keeps as few PMs active but admits only 97.8%. With the timer, a class may wait up to 15 min for its next call, so OrigaMIG migrates half as many VMs but keeps 114.1 PMs active. Random neighborhoods do as well as Algorithm 1, with 110.0 active PMs against 111.4, so at this load, the gains come from the restricted BILP rather than from the choice of its PMs. The neighborhood must be large enough to empty a PM. With Mmax = 4, OrigaMIG keeps 118.8 PMs active, as many as FF, and with Mmax = 8, 114.8. With Mmax = 32, the median call takes 10.25 s, so most calls stop at the time limit, and OrigaMIG keeps 113.1 PMs active, more than with Mmax = 16. The time limit matters up to 10 s. A limit of 1 s keeps 117.0 PMs active, 5 s keeps 112.3, and 30 s keeps 111.2, against 111.4 with 10 s. The threshold matters little. With θ = 2 and 4, OrigaMIG keeps 111.7 and 112.3 PMs active, and θ = 4 lowers the calls from 44.7 to 38.0 per hour. We then grow the data center from 128 to 4096 PMs at the same load per PM, with a quarter of the PMs carrying A30 GPUs, and simulate one day with a single seed (Fig. 7). OrigaMIG starts at most one call per 10 s step, that is, 360 calls per hour, while the calls it needs grow with the data center. The simulations shared one machine, so a call may take longer than on eight dedicated cores. From 128 to 1024 PMs, the calls grow

δi = 0

8

Accept. (%) 98.55 98.04 98.68 99.46 99.46 97.33 94.66

102

Migrations per hour Figure 6: Reduction in active PMs over FF against the migration rate, at a load of 0.85. The labels give the migration penalty δi of OrigaMIG and the period of TC.

6.7. Ablation and Scale We disable one component of OrigaMIG at a time and vary its parameters, at a load of 0.85 (Table 11). Without admission calls, a request that the arrival rule cannot place is rejected. Without consolidation calls, OrigaMIG only admits pending VMs. The timer variant starts a consolidation call for each class every 15 min instead of when the threshold is reached. The random variant selects the PMs of a call at random, within Mmax and Nmax , instead of using Algorithm 1. Without any call, OrigaMIG reduces to FF. We vary Mmax from 4 to 32 with Nmax = 4Mmax , the time limit from 1 to 30 s, and θ from 1 to 4. 13

Table 11: Ablation and sensitivity of OrigaMIG at a load of 0.85 Variant OrigaMIG without admission calls without consolidation calls timer instead of threshold random neighborhoods without calls (FF) Mmax = 4 Mmax = 8 Mmax = 32 time limit 1 s time limit 5 s time limit 30 s θ=2 θ=4

200

5

PMs 8 16 32

median 95th pct.

100

128

512 1k

PMs

2k

4k

0

128

512 1k

2k

Energy (MWh) 6.16 6.11 6.20 6.16 6.17 6.12 6.16 6.14 6.19 6.17 6.15 6.14 6.17 6.18

Migr./h 12.8 11.5 0.9 6.2 13.5 0 2.0 6.4 11.6 3.8 9.6 12.0 12.1 10.7

Calls/h 44.7 43.4 1.1 8.8 41.7 0 38.6 41.4 41.8 39.6 42.9 44.0 43.2 38.0

Table 12: Optimality gap and runtime of OrigaMIG against OPT, with the settings of Section 6.1 (Mmax = 16). The optimality gap is given as the additional active PMs of OrigaMIG relative to OPT and as the relative gap in Eq. (5), (OPT − OrigaMIG)/OPT. The runtime is the median wall-clock time of one OrigaMIG call and of one OPT solve.

10

Seconds

Calls per hour

Active PMs 111.4 111.0 119.5 114.1 110.0 119.1 118.8 114.8 113.1 117.0 112.3 111.2 111.7 112.3

at most 360

300

0

Accept. (%) 99.5 97.8 96.5 97.5 99.5 94.6 95.3 97.0 98.5 96.4 98.2 98.9 99.1 98.7

(b) Runtime of a call

(a) Calls 400

Seeds 3 3 3 3 3 3 3 3 3 3 3 3 3 3

4k

VMs 19 30 65

Optimality gap Active PMs Eq. (5) 3.9% 0.54% 4.1% 0.43% 3.4% 0.33%

Runtime OrigaMIG call OPT 0.3 s 0.3 s 0.9 s 1.7 s 1.1 s 1692 s

PMs

at 2.1 per hour per 8 PMs, 70% transient jobs (mean 2 h) and 30% tenants (mean 24 h), and one or two A100 GIs per VM. As OPT solves are costly, we run multiple seeds where feasible and report the worst-case gap. The solver proves the optimality of every OPT solve. The calls of OrigaMIG use the settings of Section 6.1. Optimality gap. Table 12 and Fig. 8(a) show that OrigaMIG uses at most 3–4% more active PMs than OPT, with no trend in the size of the data center. The relative gap in Eq. (5) is at most 0.54%, because the shared acceptance term dominates the objective. At 8 and 16 PMs a call already covers the whole data center, so the gap stems from when OrigaMIG calls the solver and which PMs it selects, not from the size of the neighborhood. A smaller neighborhood widens the gap. With Mmax = 8, OrigaMIG uses up to 5.4% more active PMs than OPT at 16 PMs and 8.1% at 32 PMs, and with Mmax = 4, up to 10.4% at 8 PMs and 14.7% at 16 PMs. Runtime. The size of the restricted BILP is proportional to P |N̂|(| M̂| + j∈ M̂ |K j |) (Section 5.3), which Mmax and Nmax bound by a constant. The solve time of a call is therefore O(1) in the size of the data center once it exceeds Mmax PMs, apart from the single pass over the PMs that selects the neighborhood. It varies only with the VMs a neighborhood holds, and its median is 0.9 s at 16 PMs and 1.1 s at 32 PMs (Fig. 8(b)). The model P of OPT grows as O(|N|(|M| + j∈M |K j |)), and its runtime grows faster than the model, from 0.3 s at 8 PMs to 28 min at 32 PMs (Section 6.9). These times exceed those of Fig. 3 at the same number of VMs, because a VM here requests one or two GIs instead of one, which enlarges the BILP. A single solve takes up to 115 min. At 32 PMs, a OrigaMIG call is about 1500 times faster than OPT, at an optimality gap of 3.4% more active PMs. For one snapshot at 48 PMs with 94 VMs, OPT took 85 min and found no better placement than that of OrigaMIG, whose calls

Figure 7: OrigaMIG as the data center grows, at a load of 0.85, over one day and one seed.

from 44.7 to 207.8 per hour, and the median call from 4.26 s to 9.97 s, close to the time limit. From 1024 PMs on, FF admits every request, so OrigaMIG can gain only through fewer active PMs. Its reduction over FF falls from 2.8% with 128 PMs and 2.1% with 512 PMs to 1.0% with 1024 PMs, and it stays below 0.5% with 2048 and 4096 PMs, where OrigaMIG starts 284.9 and 334.5 calls per hour. One instance of OrigaMIG thus serves up to about 1024 PMs in our workload. A larger data center can run one instance per partition of its PMs, as large-scale allocators partition their optimization problems [54, 55]. Each constraint of the BILP involves one PM, one GPU, or one VM (Section 5.5), so calls on disjoint neighborhoods can also run in parallel. 6.8. Optimality Gap and Runtime OrigaMIG solves each call on a neighborhood of at most Mmax = 16 PMs instead of the whole data center, trading solution quality for runtime. We quantify this trade-off against OPT, the optimal solution of the BILP over the whole data center, in terms of the optimality gap and the runtime of OrigaMIG and of OPT. Method. We simulate OrigaMIG from an empty data center and take snapshots every 4 h from 48 h to 96 h. At each snapshot, we solve the BILP over the whole data center from the current state, keeping every running VM placed, and compare its solution with the placement of OrigaMIG in Eq. (5). OPT is the best placement from that state, so it upper-bounds the value OrigaMIG can reach in that state, but not over the whole run. The workload follows Section 6.2, with Poisson arrivals 14

only for small data centers.

Additional active PMs (%)

(a) Optimality gap against runtime Mmax =2

20

8 PMs

7. Discussion

16 PMs 32 PMs 4

Where OrigaMIG helps. OrigaMIG gains more than TC when the CPU and the RAM of the PMs run out first, with smaller profiles, with either share of tenants, and on the trace (Section 6.5). Its BILP places the GIs, the cores, and the RAM of a VM together, whereas TC ranks PMs by their GPUs alone, so with fewer cores and RAM, OrigaMIG admits 2.6 percentage points more than FF while TC admits fewer. TC gains more with larger profiles, with two GIs per VM, and with A30 PMs only. A PM then hosts few VMs, so a neighborhood of 16 PMs holds only 10 to 17 VMs, and the solver proves each call optimal in less than one second. Here the number of PMs per call, and not the time limit, bounds the gains, while TC compacts all GPUs of a class at once. Bounding a neighborhood by its VMs instead of its PMs would let it grow in these cases, and the time limit would still bound each call. Choosing the migration penalty. The penalty δi sets how many migrations OrigaMIG spends to save an active PM (Section 6.6). For each period of TC, a value of δi gives both fewer migrations and fewer active PMs, so an operator can derive δi from a migration budget instead of tuning a period. The cost of a migration grows with the memory of the VM. On the trace, where most VMs hold a whole GPU, OrigaMIG copies 8772 GB per hour, against 615 GB for TC. Setting δi in proportion to the memory of VM i would move large VMs less often. Neighborhood selection. At a load of 0.85, random neighborhoods keep as few PMs active as Algorithm 1 (Section 6.7). The gains therefore come mainly from solving the BILP on several PMs at once, and a cheaper selection may suffice. Whether this holds at higher loads and in larger data centers remains to be tested. Deployment at scale. One instance of OrigaMIG starts at most one call per 10 s step. Its reduction in active PMs over FF falls from 2.8% with 128 PMs to 0.2% with 2048 PMs, where it starts 284.9 of its 360 possible calls per hour. A large data center should therefore run one instance per partition of its PMs, such as a row or a pod, as large-scale allocators do [54, 55], and calls on disjoint neighborhoods can run in parallel (Section 6.7). A call of a few seconds is short next to a migration between PMs, which takes 70 s on average, and at a load of 1.0, admitted requests wait 1.5 s on average. Limitations. We evaluate OrigaMIG in simulation. Each run starts from an empty data center, and tenants live 24 h on average, so the demand reaches 89% of its steady value when the three measured days start and 96% on average over them. All policies see the same demand. The energy model switches empty PMs off at no cost and makes the power of a GPU linear in its compute slices in use. A migration copies the memory of the VM once, without further pre-copy rounds or downtime, and GIs do not interfere, as MIG isolates them. The workloads are synthetic, apart from one trace mapped to A100 profiles, and each setting runs three to five seeds. The calls ran on a shared machine, so their runtimes may be longer than on dedicated

OPT

4

10

8 8 8

0

8 PMs

10

−2

10

−1

16

16

16 PMs

10

0

32 PMs

10

1

10

2

103

104

Median runtime of a decision (s) (b) Runtime as the data center grows 104

Runtime (s)

10

OPT solve OrigaMIG call, Mmax =16

3

model size of OPT

102 101

≈ 1500× 10 s limit of a OrigaMIG call

100 10−1 8 19

16 30

32 65

PMs |M| (top) and VMs |N| (bottom) Figure 8: (a) The optimality gap of OrigaMIG against the median runtime of its calls, for each data-center size and neighborhood limit Mmax (labels); OPT has no gap and sits on the x-axis at its own runtime. A larger neighborhood trades runtime for a smaller gap. (b) Median runtime as the data center grows, with Mmax = 16; the dotted line shows how OPT would grow if its runtime only followed the size of its model. Whiskers in (b) show the 5th to 95th percentile.

took a median of 1.5 s; for the next snapshots, with 99–105 VMs, OPT did not finish within 16 h. 6.9. Scalability of the BILP We now measure how the time to solve one interval to optimality grows with the number of VMs and the number of PMs. Each PM has two A100 40GB GPUs, 80 cores, and 512 GB of RAM. Each VM requests one GI with a profile drawn uniformly at random from Table 5, together with 4 cores and 16 GB of RAM per compute slice. The resident VMs are placed by FF. Then, some of them are removed and replaced by new ones to fragment the GPUs, and a batch of new VMs arrives. The weights are those of Section 6.1. CP-SAT runs on eight dedicated CPU cores, starts from the current placement, and stops after 20 minutes. Fig. 3 doubles one of |M| and |N| while the other is fixed. Each doubling of |N| or |M| approximately doubles the size of the model, but Fig. 3 shows that the solve time grows much faster. In Fig. 3(b), the last two doublings of |N| multiply the solve time by 6.6 and 61, and 128 VMs on 64 GPUs already take 17 minutes. In Fig. 3(a), the number of PMs also increases the solve time, even though the added PMs are idle. Beyond about a hundred VMs on a hundred GPUs, the solver proves optimality within the limit in only 2 of 15 solves. The BILP can therefore be solved to optimality in every interval 15

cores. A deployment on a real cluster, with measured migration times and power, is the next step.

[4] M. Amaral, J. Polo, D. Carrera, S. Seelam, M. Steinder, Topology-aware GPU scheduling for learning workloads in cloud environments, in: SC17: International Conference for High Performance Computing, Networking, Storage and Analysis, 2017, pp. 1–12.

8. Conclusion

[5] X. Zhu, L. Gong, Z. Zhu, X. Zhou, Vapor: A GPU sharing scheduler with communication and computation pipeline for distributed deep learning, in: IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), 2021, pp. 108–116.

This article set out to tackle the challenges introduced by MIG technology in cloud data centers, particularly the fragmentation and inefficiency stemming from rigid placement rules. We showed that the default GI placement policy puts each GI where it maximizes CF, and that 67% of the configurations of an A100 arrange their GIs suboptimally. We formulated a BILP model to capture the complexities of acceptance maximization, resource consolidation, and reduced migration overhead. Building on it, we developed OrigaMIG, which places each request with a fast greedy rule and solves the BILP on a small neighborhood of PMs when a request cannot be placed or the GPUs of a class become fragmented. In simulations of 256 GPUs in 128 PMs, OrigaMIG kept fewer PMs active than TC, the stronger of two state-of-the-art MIG-aware policies, in 29 of 30 paired runs while migrating 29% to 49% fewer VMs, and it used the least energy per admitted GPU-hour of all policies. Against the default placement, it kept up to 12.5% fewer PMs active and admitted up to 7.8 percentage points more of the requested GPU memory. Across eleven variants of the workload and the hardware, it kept fewer PMs active than TC in seven, while TC did better when the VMs were large relative to their GPUs. One instance served up to about 1024 PMs, so larger data centers need one instance per partition of their PMs. On small data centers, OrigaMIG stayed within 4.1% of the optimal number of active PMs. Future research could extend OrigaMIG by incorporating more advanced prediction models for request patterns, admitting preemptible low-priority VMs into the idle slices that consolidation leaves on active GPUs, or integrating network topology considerations. As MIG becomes increasingly prevalent in modern cloud and HPC deployments, the insights and techniques described in this paper provide a foundation for enhanced GPU resource management in data centers.

[6] B. Li, T. Patel, S. Samsi, V. Gadepally, D. Tiwari, MISO: Exploiting Multi-Instance GPU capability on multi-tenant GPU clusters, in: Proceedings of the 13th Symposium on Cloud Computing, 2022, pp. 173–189. [7] NVIDIA Multi-Instance GPU User Guide, release r580, 14 November 2025. Accessed: 3 September 2026 (2025). URL https://docs.nvidia.com/datacenter/ tesla/mig-user-guide [8] M. Lee, S. Seong, M. Kang, J. Lee, G.-J. Na, I.-G. Chun, D. Nikolopoulos, C.-H. Hong, ParvaGPU: Efficient spatial GPU sharing for large-scale DNN inference in cloud environments, in: International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE, 2024, pp. 1–14. [9] NVIDIA Virtual GPU (vGPU) Software, published 17 June 2025, last updated 24 March 2026. Accessed: 3 September 2026 (2026). URL https://docs.nvidia.com/vgpu [10] M. Zambianco, L. Fasol, R. Doriguzzi-Corin, An online fragmentation-aware GPU scheduler for multi-tenant MIG-based clouds (2025). arXiv:2511.18906, doi: 10.48550/arXiv.2511.18906. [11] B. Turkkan, P. Murali, P. Harsha, R. Arora, G. Vanloo, C. Narayanaswami, Optimal workload placement on multi-instance GPUs (2024). arXiv:2409.06646, doi: 10.48550/arXiv.2409.06646.

References [1] X. Hou, J. Han, Y. Zhao, H. Wang, Unveiling the landscape of LLM deployment in the wild: An empirical study (2025). arXiv:2505.02502, doi:10.48550/ arXiv.2505.02502.

[12] A. Alashaikh, E. Alanazi, A. Al-Fuqaha, A survey on the use of preferences for virtual machine placement in cloud data centers, ACM Comput. Surv. 54 (5) (May 2021).

[2] A. Siavashi, M. Momtazpour, gVMP: A multi-objective joint VM and vGPU placement heuristic for API remoting-based GPU virtualization and disaggregation in cloud data centers, Journal of Parallel and Distributed Computing 172 (2023) 97–113.

[13] A. H. T. Dias, L. H. A. Correia, N. Malheiros, A systematic literature review on virtual machine consolidation, ACM Computing Surveys (CSUR) 54 (8) (Oct. 2021). [14] M. Imran, M. Ibrahim, M. S. U. Din, M. A. U. Rehman, B. S. Kim, Live virtual machine migration: A survey, research challenges, and future directions, Computers and Electrical Engineering 103 (2022) 108297.

[3] W.-C. Chung, J.-S. Tong, Z.-H. Chen, A fine-grained GPU sharing and job scheduling for deep learning jobs on the cloud, The Journal of Supercomputing 81 (2) (2025) 361. 16

[15] K. Saidi, D. Bardou, Task scheduling and VM placement to resource allocation in cloud computing: challenges and opportunities, Cluster Computing 26 (5) (2023) 3069–3087.

[27] C. Wei, Z.-H. Hu, Y.-G. Wang, Exact algorithms for energy-efficient virtual machine placement in data centers, Future Generation Computer Systems 106 (2020) 77–91. [28] R. Shaw, E. Howley, E. Barrett, An energy efficient anti-correlated virtual machine placement algorithm using resource usage predictions, Simulation Modelling Practice and Theory 93 (2019) 322–342.

[16] J. Lin, W. Lin, W. Wu, W. Lin, K. Li, Energy-aware virtual machine placement based on a holistic thermal model for cloud data centers, Future Generation Computer Systems 161 (2024) 302–314.

[29] C.-H. Hong, I. Spence, D. S. Nikolopoulos, GPU virtualization and scheduling methods: A comprehensive survey, ACM Computing Surveys (CSUR) 50 (3) (2017) 1–37.

[17] Y. Alahmad, A. Agarwal, Multiple objectives dynamic VM placement for application service availability in cloud networks, Journal of Cloud Computing 13 (1) (2024) 46. [18] H. Xu, C. Jian, A meta reinforcement learning-based virtual machine placement algorithm in mobile edge computing, Cluster Computing 27 (2) (2024) 1883–1896.

[30] A. Siavashi, M. Momtazpour, GPUCloudSim: an extension of CloudSim for modeling and simulation of GPUs in cloud data centers, The Journal of Supercomputing 75 (5) (2019) 2535–2561.

[19] R. Regaieg, M. Koubàa, Z. Ales, T. Aguili, Multi-objective optimization for VM placement in homogeneous and heterogeneous cloud service provider data centers, Computing 103 (2021) 1255–1279.

[31] A. K. Kulkarni, B. Annappa, GPU-aware resource management in heterogeneous cloud data centers, The Journal of Supercomputing 77 (11) (2021) 12458–12485.

[20] H. Talebian, A. Gani, M. Sookhak, A. A. Abdelatif, A. Yousafzai, A. V. Vasilakos, F. R. Yu, Optimizing virtual machine placement in IaaS data centers: taxonomy, review and open issues, Cluster Computing 23 (2020) 837–878.

[32] A. Garg, U. Kurkure, H. Sivaraman, L. Vu, Virtual machine placement solution for VGPU enabled clouds, in: International Conference on High Performance Computing & Simulation (HPCS), IEEE, 2019, pp. 897–903.

[21] M. Masdari, S. Gharehpasha, M. Ghobaei-Arani, V. Ghasemi, Bio-inspired virtual machine placement schemes in cloud computing environment: taxonomy, review, and future research directions, Cluster Computing 23 (4) (2020) 2533–2563.

[33] H. Sivaraman, U. Kurkure, L. Vu, TECN: task selection and placement in GPU enabled clouds using neural networks, in: International Conference on High Performance Computing & Simulation (HPCS), IEEE, 2019, pp. 890–896.

[22] Y. Kong, Y. He, K. Abnoosian, Nature-inspired virtual machine placement mechanisms: A systematic review, Concurrency and Computation: Practice and Experience 34 (11) (2022) e6900.

[34] H. Sivaraman, U. Kurkure, L. Vu, Task assignment in a virtualized GPU enabled cloud, in: International Conference on High Performance Computing & Simulation (HPCS), IEEE, 2018, pp. 895–900.

[23] Sudhakar, Saravanan, A survey and future studies of virtual machine placement approaches in cloud computing environment, in: Proceedings of the 2021 6th International Conference on Cloud Computing and Internet of Things, 2021, pp. 15–21.

[35] C. Tan, Z. Li, J. Zhang, Y. Cao, S. Qi, Z. Liu, Y. Zhu, C. Guo, Serving DNN models with Multi-Instance GPUs: A case of the reconfigurable machine scheduling problem, arXiv preprint arXiv:2109.11067 (2021).

[24] D. Saxena, I. Gupta, J. Kumar, A. K. Singh, X. Wen, A secure and multiobjective virtual machine placement framework for cloud data center, IEEE Systems Journal 16 (2) (2021) 3163–3174.

[36] E. Arima, M. Kang, I. Saba, J. Weidendorfer, C. Trinitis, M. Schulz, Optimizing hardware resource partitioning and job allocations on modern GPUs under power caps, in: Workshop Proceedings of the 51st International Conference on Parallel Processing, 2022, pp. 1–10.

[25] L. Caviglione, M. Gaggero, M. Paolucci, R. Ronco, Deep reinforcement learning for multi-objective placement of virtual machines in cloud datacenters, Soft Computing 25 (19) (2021) 12569–12588.

[37] Multi-Process Service, release r590, 5 December 2025. Accessed: 3 September 2026 (2025). URL https://docs.nvidia.com/deploy/mps

[26] E. Torre, J. J. Durillo, V. De Maio, P. Agrawal, S. Benedict, N. Saurabh, R. Prodan, A dynamic evolutionary multi-objective virtual machine placement heuristic for cloud data centers, Information and Software Technology 128 (2020) 106390.

[38] U. Saroliya, E. Arima, D. Liu, M. Schulz, Hierarchical resource partitioning on modern GPUs: A reinforcement learning approach, in: IEEE International Conference on Cluster Computing (CLUSTER), IEEE, 2023, pp. 185–196. 17

[39] B. Zhang, S. Li, Z. Li, MIGER: Integrating Multi-Instance GPU and Multi-Process Service for deep learning clusters, in: Proceedings of the 53rd International Conference on Parallel Processing, ICPP ’24, Association for Computing Machinery, New York, NY, USA, 2024, p. 504–513.

placement in cloud data centers with multi-instance GPU technology (2025). arXiv:2502.01909, doi:10.48550/arXiv.2502.01909. [50] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979.

[40] Y. Tang, W. Sun, H. Ting, M. Chen, I. Chung, J. Chou, Pcie bandwidth-aware scheduling for Multi-Instance GPUs, in: Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region, HPC Asia 2025, Hsinchu, Taiwan, February 19-21, 2025, ACM, 2025, pp. 43–51.

[51] P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, in: Principles and Practice of Constraint Programming – CP98, Vol. 1520 of Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 1998, pp. 417–431. doi:10.1007/ 3-540-49481-2_30.

[41] Q. Weng, L. Yang, Y. Yu, W. Wang, X. Tang, G. Yang, L. Zhang, Beware of fragmentation: Scheduling GPU-sharing workloads with fragmentation gradient descent, in: USENIX Annual Technical Conference (USENIX ATC 23), 2023, pp. 995–1008.

[52] D. Pisinger, S. Ropke, Large neighborhood search, in: M. Gendreau, J.-Y. Potvin (Eds.), Handbook of Metaheuristics, Springer, Boston, MA, 2010, pp. 399–419. doi:10.1007/978-1-4419-1665-5_13.

[42] A. Saraha, Y. Li, C. Porter, S. Pande, Managing multi instance GPUs for high throughput and energy savings (2025). arXiv:2508.18556, doi:10.48550/arXiv. 2508.18556.

[53] L.-M. Perron, V. Dupont, OR-tools, Accessed: September 2026 (2021). URL https://github.com/google/or-tools

21

[54] A. Newell, D. Skarlatos, J. Fan, P. Kumar, M. Khutornenko, M. Pundir, Y. Zhang, M. Zhang, Y. Liu, L. Le, B. Daugherty, A. Samudra, P. Baid, J. Kneeland, I. Kabiljo, D. Shchukin, A. Rodrigues, S. Michelson, B. Christensen, K. Veeraraghavan, C. Tang, RAS: Continuously optimized region-wide datacenter resource allocation, in: Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, SOSP ’21, ACM, 2021, pp. 505–520. doi:10.1145/3477132.3483578.

[43] H.-T. Ting, J. Chou, M.-H. Chen, I.-H. Chung, An online fragmentation-aware scheduler for managing GPU-sharing workloads on multi-instance GPUs (2025). arXiv:2512.16099, doi:10.48550/arXiv.2512. 16099. [44] J. Villarrubia, L. Costero, F. D. Igual, K. Olcoz, Leveraging multi-instance GPUs through moldable task scheduling, Journal of Parallel and Distributed Computing 204 (2025) 105128. arXiv:2507.13601, doi:10. 1016/j.jpdc.2025.105128.

[55] D. Narayanan, F. Kazhamiaka, F. Abuzaid, P. Kraft, A. Agrawal, S. Kandula, S. Boyd, M. Zaharia, Solving large-scale granular resource allocation problems efficiently with POP, in: Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, SOSP ’21, ACM, 2021, pp. 521–537. doi:10.1145/3477132.3483588.

[45] J. Villarrubia, L. Costero, F. D. Igual, K. Olcoz, Solving the task scheduling and GPU reconfiguration problem on MIG devices via deep reinforcement learning, Future Generation Computer Systems 176 (2026) 108145, available online September 2025. doi:10.1016/j. future.2025.108145.

[56] Standard Performance Evaluation Corporation, SPECpower_ssj2008 Result, Hewlett Packard Enterprise ProLiant DL380 Gen10 Plus (Intel Xeon Platinum 8380), Result power_ssj2008-20210528-01098, tested 28 May 2021. Accessed: 30 September 2026 (2021). URL https://spec.org/power_ssj2008/results/ res2021q2/power_ssj2008-20210528-01098.html

[46] F. Lettich, E. Carlini, F. M. Nardini, R. Perego, S. Trani, Power- and fragmentation-aware online scheduling for GPU datacenters (2024). arXiv:2412.17484, doi:10. 48550/arXiv.2412.17484. [47] Q. Wu, P. Chen, Y. Wang, Defragmentation scheduling with deep reinforcement learning in shared GPU clusters, in: Proceedings of the 2025 ACM Symposium on Cloud Computing (SoCC ’25), ACM, 2025, pp. 402–415. doi: 10.1145/3772052.3772242. [48] M. Kim, I. Yeom, Y. Kim, Flex-MIG: Enabling distributed execution on MIG (2025). arXiv:2511.09143, doi: 10.48550/arXiv.2511.09143.

[57] NVIDIA A30 GPU Accelerator, Product Brief, PB-10418-001_v03, March 2022. Accessed: 30 September 2026 (2022). URL https://www.nvidia.com/content/dam/ en-zz/Solutions/data-center/products/ a30-gpu/pdf/a30-product-brief.pdf

[49] A. Siavashi, M. Momtazpour, A multi-objective framework for optimizing GPU-enabled VM

[58] M. Cornelius, G. Cross, Shilpika, M. T. Dearing, Z. Lan, Extracting practical, actionable energy insights from 18

supercomputer telemetry and logs (2025). arXiv:2505. 14796. [59] NVIDIA A100 40GB PCIe GPU Accelerator, Product Brief, PB-10137-001_v03, September 2020. Accessed: 30 September 2026 (2020). URL https://www.nvidia.com/content/dam/ en-zz/Solutions/Data-Center/a100/pdf/ A100-PCIE-Prduct-Brief.pdf [60] A. Siavashi, M. Momtazpour, GPU cluster dynamics: insights from Alibaba’s 2023 trace release, Computing 107 (1) (2024) 4. [61] G. Pan, V. Chodnekar, A. Roy, H. Wang, A cost-benefit analysis of on-premise large language model deployment: Breaking even with commercial LLM services (2025). arXiv:2509.18101, doi:10.48550/ arXiv.2509.18101.

19

Related documents

• OrigaMIG: MIG-Aware VM Placement with a Neighborhood-Restricted BILP and Live Migration#1215741
• FlexNPU: Transparent NPU Virtualization for Dynamic LLM Prefill-Decode Co-location#259433
• Nexus: Depth-Adaptive KV-Cache Splicing and Retrieval-Decoupled Tool Routing for Agentic LLMs on Unified Memory#658973
• Nexus: Depth-Adaptive KV-Cache Splicing and Retrieval-Decoupled Tool Routing for Agentic LLMs on Unified Memory#656837
• EvoMem-VLA: State-Evolution Memory for Long-Horizon Robot Manipulation#1201431