GPU碎片化率研究

Weng, Q., Yang, L., Yu, Y., Wang, W., Tang, X., Yang, G., & Zhang,
L. (2023). Beware of Fragmentation: Scheduling {GPU-Sharing} Workloads
with Fragmentation Gradient Descent. In2023 USENIX Annual Technical Conference (USENIX ATC 23)(pp. 995-1008).

对于碎片率的基本建模

假设一个节点为$n$,单个任务为$m$,碎片化值设为$F_n$，总的工作流为$M$，任务权重有$\sum_{m \in M}p_m=1$,则有

$$F_n(M)=\sum_{m \in M}p_mF_n(m)$$

单个节点F_n的三种计算情况

资源不足

如果节点没有足够的资源（例如，CPU或GPU不足），那么所有未分配的GPU都被认为是碎片化的。这种情况下，碎片化量计算公式为：

$$F_n(m)=\sum^{G_n}_{g=1}R^{GPU}_{n,g}$$

这里$R$为GPU剩余容量，$G$为节点GPU总量

资源充足

如果节点有足够的资源运行任务mmm，但某些GPU部分未分配，且这些未分配部分不足以运行任务，这些部分的GPU资源也会被认为是碎片化的。此时，碎片化计算为：

$$F_n(m)=\sum^{G_n}_{g=1}R^{GPU}_{n,g}\cdot 1(R^{GPU}_{n,g} < \min(D^{GPU}_m,1))$$

这里的$1$是指示函数，当条件成立时返回1，否则返回0。$D$是任务$m$请求的GPU资源

剩余容量$R>=1$时，不等式右式必然为1，式子恒为0，也就是认为当合理分配时，不会产生碎片量

仅CPU

如果任务不请求GPU（例如仅请求CPU），则节点上的所有未分配GPU都被认为是碎片化的，计算方式同第一种情况。在这里我们忽略这种情况。

定义碎片化率

节点定义：

$$f_n(M)=\frac{F_n(M)}{\sum_{1\leq g\leq {G_n}} R^{GPU}_{n,g}}$$

集群定义:

$$F_N(M)=\sum_{n \in N}F_n(M)$$

$$f_N(M)=\frac{F_N(M)}{\sum_{n \in N}\sum_{1\leq g\leq {G_n}} R^{GPU}_{n,g}}$$

FGD算法

• 遍历节点，计算碎片化量
• 跳过不可用节点
• 假设任务被分配后的碎片化量
• 计算增量

$$\Delta = F_{n'}(M)-F_{n}(M)$$

算法流程

输入: 集群 $N$，任务 $m$，目标工作负载 $M$
输出: 分配的节点 $n^*$

1. 初始化节点得分集合 $S = \emptyset$，输出 $n^* = \emptyset$
2. 并行遍历节点 $n \in N$
   3. 如果节点 $n$ 资源不足或不满足任务要求，则跳过该节点
   4. 假设任务 $m$ 被分配到节点 $n$ 上
   5. 计算碎片化增量 $\Delta = F_n'(M) - F_n(M)$
   6. 将 $(n, \Delta)$ 添加到节点得分集合 $S$ 中
3. 如果 $S \neq \emptyset$
   8. 选择 $\Delta$ 最小的节点 $n^*$，分配任务 $m$ 到节点 $n^*$