Can MIG-aware VM placement with neighborhood-restricted BILP reduce GPU fragmentation?

What OrigaMIG actually optimizes

OrigaMIG is a MIG-aware placement optimizer for virtual machines whose GPU demand is expressed as MIG GPU instances (GIs). Each VM receives a GI as a MIG-backed vGPU, and the profile is set by the workload the VM hosts rather than by the scheduler. The paper formalizes MIG-aware VM placement as a binary integer linear programming (BILP) problem with three simultaneous aims: maximizing request acceptance, consolidating resources, and reducing migration overhead.

The three aims are not collapsed into one number. Acceptance is the share of requested memory slices the data center admits, so a large request counts more than a small one. Active PMs and active GPUs are time averages of how many PMs host a VM and how many GPUs hold a GI. Migrations are counted per hour, and the migration penalty δi sets the cost of a migration rather than a cap on how many are allowed, so the model migrates whenever the gain in acceptance or consolidation outweighs that cost.

Because the BILP includes bin packing as a special case, it is strongly NP-hard, and the paper states that no exact algorithm can solve it in polynomial time unless P=NP. That hardness is the reason the design does not solve the full problem on every arrival.

Why MIG placement rules create fragmentation

MIG partitions a GPU into isolated instances with dedicated memory and compute slices, but it enforces rigid slice alignment and profile placement rules. On an A100 40GB, the GPU has 7 compute slices and 8 memory slices of 5 GB each, and the six supported GI profiles combine specific numbers of compute and memory slices. A profile can only start at particular slices, and the slices it occupies must all be free.

The paper measures the resulting flexibility with configuration flexibility (CF), the total number of possible placements for all supported profiles within the current GPU configuration. The default GI placement policy observed with NVIDIA driver R530 positions a profile to maximize CF, breaking ties by the lowest slice. The paper's analysis of all possible MIG memory configurations on a single A100 shows that default allocations frequently end up suboptimal, which is the fragmentation the placement problem has to fight.

This matters for reading the results: fragmentation here is a property of slice alignment and start-slice rules on a GPU, not simply a measure of how full a GPU is. A GPU can hold GIs and still leave memory slices unusable for the profiles that arrive next.

Greedy first, solver only on a neighborhood

OrigaMIG places each arriving request immediately with a lightweight greedy rule. It calls the solver only when a request cannot be placed or when the GPUs of a class become fragmented. Each call solves the BILP on a small neighborhood of physical machines, keeps the rest of the data center fixed, and executes the solution as live migrations.

In the evaluated configuration, each call runs CP-SAT from Google OR-Tools on eight threads with a 10 s time limit, and the neighborhood holds at most Mmax = 16 PMs and Nmax = 64 VMs. OrigaMIG checks every 10 s whether to start a call. The consolidation threshold is θ = 1, the smallest value the paper's analysis allows.

The weights are chosen so that migrations happen only for a reason: ai = 100, bj = 50, ejk = 20, wp = 1 for every profile, and the migration penalty δi = 10 for a placed VM and 0 for a new one. The paper states these satisfy four relations, including that a migration made only to raise CF must gain more than δi/wp = 10 in CF, more than half the CF of an empty A100. The practical consequence is that OrigaMIG migrates only to admit a VM or to switch off a PM or a GPU.

Fewer active PMs and fewer migrations

The headline comparison is against the stronger of two state-of-the-art MIG-aware policies. On 256 A100 and A30 GPUs in 128 PMs, OrigaMIG keeps fewer PMs active than that 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, which the paper calls First-Fit, OrigaMIG 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.

These numbers answer different questions and should not be merged. The 29-of-30 paired-run result is a win count on active PMs against one baseline; the 29% to 49% range is a migration reduction; the 12.5% and 7.8 percentage-point figures are gains over the default placement; and the 4.1% figure is an optimality gap on small data centers. The comparison spans six loads, eleven variants of the workload and hardware, and data centers of up to 4096 PMs, all in simulation.

Where the neighborhood bound helps and hurts

The paper reports that OrigaMIG gains more than the Turkkan Compaction policy when the CPU and RAM of PMs run out first, with smaller profiles, with either share of tenants, and on the mapped trace. The stated reason is that its BILP places the GIs, cores, and RAM of a VM together, whereas TC ranks PMs by their GPUs alone; with fewer cores and RAM, OrigaMIG admits 2.6 percentage points more than First-Fit while TC admits fewer.

The advantage reverses in other conditions. TC gains more with larger profiles, with two GIs per VM, and with A30 PMs only. In those cases a PM hosts few VMs, so a neighborhood of 16 PMs holds only 10 to 17 VMs, and the solver proves each call optimal in under a second. The paper notes that here the number of PMs per call, not the time limit, bounds the gains, and suggests that bounding a neighborhood by its VMs instead of its PMs would let it grow while the time limit still bounds each call.

Neighborhood selection itself appears not to be the main lever: at a load of 0.85, random neighborhoods keep as few PMs active as the paper's own selection algorithm. The authors conclude the gains come mainly from solving the BILP on several PMs at once, and that a cheaper selection may suffice, while noting this remains untested at higher loads and in larger data centers.

Solver time limits optimality to small data centers

The BILP can be solved to optimality in every interval only for small data centers. In the scalability study, each doubling of the number of VMs or PMs roughly doubles the model size, but solve time grows much faster: the last two doublings of the VM count multiply solve time by 6.6 and 61, and 128 VMs on 64 GPUs already take 17 minutes. Beyond about a hundred VMs on a hundred GPUs, the solver proves optimality within the limit in only 2 of 15 solves.

The neighborhood design is the response to this. At 32 PMs, one OrigaMIG call is about 1500 times faster than solving the full problem optimally, at a gap of 3.4% more active PMs. For one snapshot at 48 PMs with 94 VMs, the optimal solver took 85 minutes and found no better placement than OrigaMIG, whose calls took a median of 1.5 s; for the next snapshots, with 99 to 105 VMs, the optimal solver did not finish within 16 h.

The paper also reports that a larger neighborhood trades runtime for a smaller optimality gap, which is the explicit trade-off an operator would tune.

Scale and simulation bound the claims

Deployment at scale changes the picture. One OrigaMIG instance starts at most one call per 10 s step, and its reduction in active PMs over First-Fit 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. The paper's recommendation is to run one instance per partition of PMs, such as a row or a pod, with calls on disjoint neighborhoods running in parallel.

The evaluation is entirely in simulation, using GPUCloudSim. Each run starts from an empty data center, and because tenants live 24 h on average, demand reaches 89% of its steady value when the three measured days begin and 96% on average over them. The energy model switches empty PMs off at no cost and makes GPU power linear in the compute slices in use. A migration copies the VM's memory once, without further pre-copy rounds or downtime, and GIs are assumed not to interfere because MIG isolates them.

The workloads are synthetic apart from one Alibaba trace mapped to A100 profiles, and each setting runs three to five seeds. The paper states that a deployment on a real cluster, with measured migration times and power, is the next step. The migration penalty is also a tunable, not a fixed constant: the paper notes that on the trace, where most VMs hold a whole GPU, OrigaMIG copies 8772 GB per hour against 615 GB for TC, and that setting δi in proportion to VM memory would move large VMs less often.

The decision that matters is the neighborhood size

The most useful way to read this paper is as a trade-off curve rather than a single verdict. OrigaMIG's advantage over the default placement is largest where CPU and RAM run out before GPUs and where profiles are small, because its BILP places GIs, cores, and RAM together. Its advantage over the stronger MIG-aware policy is measured on active PMs and migrations at 128 PMs, and it shrinks to 0.2% fewer active PMs over First-Fit at 2048 PMs.

The variable that governs both the runtime and the quality of each decision is the neighborhood size, Mmax, together with the 10 s call limit. A larger neighborhood buys a smaller optimality gap at higher runtime, and the paper's own scalability results show why the full BILP is not an option beyond roughly a hundred VMs on a hundred GPUs. For an operator deciding whether this approach fits, the paper's evidence points to the partition-level deployment it recommends and to the migration penalty δi as the knob that converts a migration budget into fewer active PMs, rather than to any claim that the solver can be run globally.

Sources used in this answer