邻域受限 BILP 的 MIG 感知虚拟机放置能减少 GPU 碎片吗？

OrigaMIG 实际优化的是什么

OrigaMIG 是一个面向虚拟机的 MIG 感知放置优化器，这些虚拟机的 GPU 需求以 MIG GPU 实例（GI）表示。每个虚拟机获得一个 GI 作为 MIG 支持的 vGPU，其配置由虚拟机承载的工作负载决定，而不是由调度器决定。论文把 MIG 感知的虚拟机放置形式化为一个二进制整数线性规划（BILP）问题，同时追求三个目标：最大化请求接纳、整合资源、降低迁移开销。

这三个目标没有被合并成一个数字。接纳率是数据中心接纳的所请求内存切片占比，因此大请求比小请求权重更大。活跃物理机和活跃 GPU 是承载虚拟机的物理机数量与持有 GI 的 GPU 数量的时间平均值。迁移按每小时计数，迁移惩罚 δi 设定的是迁移的成本，而不是允许迁移数量的上限，因此只要接纳或整合带来的收益超过该成本，模型就会迁移。

由于该 BILP 把装箱问题作为特例包含在内，它是强 NP 难的，论文指出除非 P=NP，否则没有精确算法能在多项式时间内求解它。正是这种难度，使得该设计不会在每次到达时都求解完整问题。

MIG 放置规则为何产生碎片

MIG 把一块 GPU 划分为多个隔离实例，每个实例拥有专用内存和计算切片，但它强制执行严格的切片对齐和配置放置规则。在一块 A100 40GB 上，GPU 有 7 个计算切片和 8 个各 5 GB 的内存切片，六种受支持的 GI 配置组合了特定数量的计算切片和内存切片。一个配置只能从特定切片开始，且它占用的切片必须全部空闲。

论文用配置灵活性（CF）来衡量由此产生的灵活性，即在当前 GPU 配置下所有受支持配置的可能放置总数。在 NVIDIA 驱动 R530 下观察到的默认 GI 放置策略会把配置放在使 CF 最大的位置，若并列则选最低切片。论文对单块 A100 上所有可能 MIG 内存配置的分析表明，默认分配经常落入次优状态，这正是放置问题必须对抗的碎片。

这对理解结果很重要：这里的碎片是 GPU 上切片对齐和起始切片规则的性质，而不只是 GPU 有多满的度量。一块 GPU 可以持有 GI，却仍让内存切片对随后到达的配置不可用。

先贪心，只在邻域上求解

OrigaMIG 用轻量贪心规则立即放置每个到达的请求。只有当请求无法放置，或某类 GPU 出现碎片时，它才调用求解器。每次调用在一小片物理机邻域上求解 BILP，保持数据中心其余部分不变，并把解作为实时迁移执行。

在评估配置中，每次调用在八个线程上运行 Google OR-Tools 的 CP-SAT，时间限制为 10 秒，邻域最多包含 Mmax = 16 台物理机和 Nmax = 64 台虚拟机。OrigaMIG 每 10 秒检查一次是否发起调用。整合阈值为 θ = 1，这是论文分析允许的最小值。

权重被设定为让迁移只在有理由时发生：对每个配置，ai = 100、bj = 50、ejk = 20、wp = 1，已放置虚拟机的迁移惩罚 δi = 10，新到达虚拟机为 0。论文指出这些取值满足四个关系，其中包括仅为提高 CF 而进行的迁移必须在 CF 上获得超过 δi/wp = 10 的收益，即超过空 A100 的 CF 的一半。实际后果是，OrigaMIG 只在接纳虚拟机或关闭物理机或 GPU 时才迁移。

更少的活跃物理机与更少的迁移

核心比较是针对两种最先进 MIG 感知策略中更强的那一种。在 128 台物理机上的 256 块 A100 和 A30 GPU 上，OrigaMIG 在 30 次配对运行中有 29 次比该更强策略保持更少活跃物理机，同时迁移的虚拟机少 29% 到 49%，并且在每个负载下每已接纳 GPU 小时的能耗最低。

相对于论文称为 First-Fit 的默认放置，OrigaMIG 最多减少 12.5% 的活跃物理机，并最多多接纳 7.8 个百分点的所请求 GPU 内存。在小型数据中心上，它与最优活跃物理机数量的差距在 4.1% 以内。

这些数字回答的是不同问题，不应合并。29/30 的配对运行结果是对一个基线的活跃物理机胜出次数；29% 到 49% 是迁移减少幅度；12.5% 和 7.8 个百分点是相对默认放置的增益；4.1% 是小型数据中心上的最优性差距。该比较覆盖六个负载、十一种工作负载与硬件变体，以及最多 4096 台物理机的数据中心，全部在仿真中进行。

邻域边界在哪里有利、哪里不利

论文报告称，当物理机的 CPU 和 RAM 先耗尽、配置较小、租户占比为任一种，以及在映射的 trace 上时，OrigaMIG 的增益超过 Turkkan Compaction 策略。给出的原因是它的 BILP 把虚拟机的 GI、核心和 RAM 一起放置，而 TC 仅按 GPU 对物理机排序；在核心和 RAM 较少时，OrigaMIG 比 First-Fit 多接纳 2.6 个百分点，而 TC 接纳得更少。

在其他条件下优势会反转。TC 在配置较大、每台虚拟机两个 GI、以及仅 A30 物理机时增益更大。在这些情况下，一台物理机承载的虚拟机很少，因此 16 台物理机的邻域只容纳 10 到 17 台虚拟机，求解器在不到一秒内证明每次调用最优。论文指出，此时限制增益的是每次调用的物理机数量而非时间限制，并建议按虚拟机而非物理机来界定邻域，这样邻域可以扩大，而时间限制仍能约束每次调用。

邻域选择本身似乎不是主要杠杆：在负载 0.85 下，随机邻域与论文自己的选择算法保持同样少的活跃物理机。作者得出结论，增益主要来自同时在多台物理机上求解 BILP，更廉价的选择可能就足够，同时指出这一点在更高负载和更大数据中心中尚未测试。

求解时间把最优性限制在小型数据中心

只有在小型数据中心，BILP 才能在每个区间内被求解到最优。在可扩展性研究中，虚拟机数量或物理机数量每翻一倍，模型规模大致翻倍，但求解时间增长快得多：虚拟机数量的最后两次翻倍使求解时间分别乘以 6.6 和 61，64 块 GPU 上的 128 台虚拟机已经需要 17 分钟。超过约一百台虚拟机配一百块 GPU 后，求解器在限制内证明最优的只有 15 次求解中的 2 次。

邻域设计正是对此的回应。在 32 台物理机时，一次 OrigaMIG 调用比把完整问题求解到最优快约 1500 倍，代价是活跃物理机多 3.4% 的差距。对于 48 台物理机、94 台虚拟机的一个快照，最优求解器花了 85 分钟，且没有找到比 OrigaMIG 更好的放置，而 OrigaMIG 的调用中位耗时为 1.5 秒；对于随后 99 到 105 台虚拟机的快照，最优求解器在 16 小时内没有完成。

论文还报告，更大的邻域以运行时间换取更小的最优性差距，这是运维人员会调节的明确权衡。

规模与仿真界定了结论边界

大规模部署会改变图景。一个 OrigaMIG 实例每 10 秒步长最多发起一次调用，其相对 First-Fit 的活跃物理机减少幅度从 128 台物理机时的 2.8% 降到 2048 台物理机时的 0.2%，此时它每小时发起 360 次可能调用中的 284.9 次。论文的建议是按物理机分区（例如一行或一个 pod）运行一个实例，并让不相交邻域上的调用并行执行。

评估完全在仿真中进行，使用 GPUCloudSim。每次运行从空数据中心开始，由于租户平均存活 24 小时，在三个测量日开始需求达到稳态值的 89%，测量期间平均达到 96%。能耗模型以零成本关闭空物理机，并让 GPU 功耗随使用中的计算切片线性变化。一次迁移只复制虚拟机内存一次，没有额外的预复制轮次或停机时间，并且假设 GI 之间不互相干扰，因为 MIG 将它们隔离。

除了一条映射到 A100 配置的阿里巴巴 trace 外，工作负载都是合成的，每个设置运行三到五个种子。论文指出，在真实集群上部署并测量迁移时间和功耗是下一步。迁移惩罚也是可调参数而非固定常数：论文指出，在大多数虚拟机占用整块 GPU 的 trace 上，OrigaMIG 每小时复制 8772 GB，而 TC 为 615 GB，若按虚拟机内存成比例设置 δi，会让大虚拟机迁移得更少。

真正重要的决策是邻域大小

阅读这篇论文最有用的方式，是把它看作一条权衡曲线而非单一结论。OrigaMIG 相对默认放置的优势，在 CPU 和 RAM 先于 GPU 耗尽、配置较小时最大，因为它的 BILP 把 GI、核心和 RAM 一起放置。它相对更强 MIG 感知策略的优势是在 128 台物理机下按活跃物理机和迁移衡量的，而到 2048 台物理机时，它相对 First-Fit 的活跃物理机减少幅度缩小到 0.2%。

同时决定每次决策的运行时间和质量的变量是邻域大小 Mmax，以及 10 秒的调用限制。更大的邻域以更高运行时间换取更小的最优性差距，论文自己的可扩展性结果说明了为什么在超过约一百台虚拟机配一百块 GPU 后，完整 BILP 不是可选项。对于判断该方法是否适用的运维人员，论文证据指向它所建议的分区级部署，以及把迁移预算转化为更少活跃物理机的旋钮——迁移惩罚 δi，而不是任何求解器可以全局运行的断言。

本文引用的文献