异构调度：基于最大独立集的多卡 GPU 亲和度调度算法-尧图网络科技

异构调度：基于最大独立集的多卡 GPU 亲和度调度算法

一、异构 GPU 调度面临的挑战与痛点

大模型和深度学习对 GPU 算力的需求持续增长。实际部署中，Kubernetes 集群常混合不同型号的 GPU 硬件。即使是同一型号，因物理插槽位置和主板设计差异，通信带宽也可能相差很大。

例如，有些 GPU 通过 NVLink 实现高速互联，有些则只能通过 PCIe 总线通信。多卡分布式训练时，若调度器随机分配无高速通道的 GPU，大部分时间会浪费在卡间数据同步上。

传统 Kubernetes 调度器默认只关注资源数量，只要节点有空闲卡就分配任务。这种粗粒度方式忽略了底层物理拓扑，导致计算效率不稳定。调度系统需要感知 GPU 间的亲和度拓扑，在节点内找出通信效率最高的卡组。

二、最大独立集算法与多卡亲和度模型

为在单机内选出物理连接最紧密的 GPU 组合，可将 GPU 连接关系抽象为图论模型。

设节点内所有 GPU 为顶点集合。若两张 GPU 间无 NVLink 高速互联，则在它们之间建立边。此图中，边代表"低速通信阻碍"。

寻找彼此有高速互联的 GPU 集合，等价于找顶点子集，使子集中任意两点无边相连。这正是"最大独立集"问题。

在"冲突图"中求解最大独立集，可保证选中 GPU 间存在高速通道，降低通信延迟。若需分配卡数小于最大独立集基数，可挑选子集；若大于，则说明该节点无法提供完美互联，调度器可对该节点扣分或转向其他节点。

最大独立集属 NP 完全问题，但单机 GPU 数量通常不超过 16 张。此规模下，回溯算法可在微秒级得出结果，不影响调度器响应速度。

三、基于 Go 原生标准库的算法实现

Go 语言中需先定义节点内 GPU 拓扑表示方法。可用邻接矩阵存储卡间是否存在"低速连接"（冲突边）。以下代码通过递归回溯求解最大独立集，在模拟 8 卡异构节点上选出最佳 GPU 卡组。

package main import ( "fmt" ) // GPU 代表单张 GPU 卡的元信息 type GPU struct { ID int Model string } // FindMaxIndependentSet 求解最大独立集 // graph[i][j] == true 表示 GPU i 和 GPU j 之间没有高速互联（存在冲突边） func FindMaxIndependentSet(graph [][]bool, gpus []GPU) []int { n := len(gpus) var bestSet []int var backtrack func(index int, currentSet []int) backtrack = func(index int, currentSet []int) { // 剪枝：当前集合 + 剩余可选顶点数 ≤ 已知最佳解，直接返回 if len(currentSet)+(n-index) <= len(bestSet) { return } if index == n { if len(currentSet) > len(bestSet) { bestSet = make([]int, len(currentSet)) copy(bestSet, currentSet) } return } // 决策1：不选当前 GPU backtrack(index+1, currentSet) // 决策2：选择当前 GPU（需与已选集合无冲突） canSelect := true for _, u := range currentSet { if graph[u][index] { canSelect = false break } } if canSelect { nextSet := append(currentSet, index) backtrack(index+1, nextSet) } } backtrack(0, []int{}) return bestSet } func main() { // 模拟 8 卡节点，部分卡间有 NVLink 互联，部分无 gpus := []GPU{ {ID: 0, Model: "A100"}, {ID: 1, Model: "A100"}, {ID: 2, Model: "A100"}, {ID: 3, Model: "A100"}, {ID: 4, Model: "A100"}, {ID: 5, Model: "A100"}, {ID: 6, Model: "A100"}, {ID: 7, Model: "A100"}, } n := len(gpus) graph := make([][]bool, n) for i := range graph { graph[i] = make([]bool, n) } // 模拟拓扑：0-3 和 4-7 分别属于两个 NVLink 环，组间仅 PCIe 通信 for i := 0; i < 4; i++ { for j := 4; j < 8; j++ { graph[i][j] = true graph[j][i] = true } } // GPU 2 硬件故障，与 0,1,3 失去高速互联 graph[2][0] = true graph[0][2] = true graph[2][1] = true graph[1][2] = true graph[2][3] = true graph[3][2] = true best := FindMaxIndependentSet(graph, gpus) fmt.Printf("最大高速互联 GPU 集合 ID: %v\n", best) // 输出：[4 5 6 7] }

算法核心是回溯剪枝策略。通过计算剩余可选顶点上限，可在搜索树早期砍掉无用分支。更大规模拓扑可引入启发式算法近似求解，保证调度效率。

四、基于 Mermaid 的调度时序与架构解析

在 Kubernetes 生态中，该算法通常封装为自定义调度器插件，运行于 Filter 和 Score 阶段。

当需多张 GPU 且要求高带宽的 Pod 到达时，调度器先过滤物理卡数不足的节点（Filter 阶段）。随后在 Score 阶段，插件分析节点空闲 GPU 的物理拓扑，构建冲突图并运行最大独立集算法。

若最大独立集大小满足 Pod 请求，节点得高分；若不足，则降分。工作负载因此被引导至拓扑最匹配的节点。

sequenceDiagram autonumber participant APIServer as K8s API Server participant Scheduler as 调度器内核 participant GPUPlugin as GPU 拓扑调度插件 participant Node as 工作节点 APIServer->>Scheduler: 监听并获取待调度 Pod (请求 4 张 GPU) Scheduler->>GPUPlugin: 触发 Filter 阶段，过滤卡数不足的节点 GPUPlugin-->>Scheduler: 返回候选节点列表 Scheduler->>GPUPlugin: 触发 Score 阶段，评估节点 GPU 亲和度 rect rgb(240, 240, 240) Note over GPUPlugin: 1. 获取节点空闲 GPU 列表<br/>2. 构建“无高速互联”冲突图<br/>3. 求解最大独立集 end GPUPlugin-->>Scheduler: 返回节点评分 Scheduler->>APIServer: 绑定 Pod 到最优节点 APIServer->>Node: 派发容器启动指令，携带选定 GPU ID 列表