图划分 = 负载均衡 + 通信最小化
NP-complete 问题，需要启发式算法。METIS、SCOTCH、KaHIP 是主流工具。多重网格加速是核心思想：粗化 → 划分 → 扩展 → 改进。
CS267 · 第 25 课
如何将计算任务均衡地分配到多个处理器上，同时最小化通信开销？这是并行计算中最核心、也最困难的问题之一。本课从图划分的数学理论出发，深入讨论 Kernighan/Lin、谱划分、多重网格加速等经典算法，并介绍动态负载均衡中的 work stealing 技术。
给定一个图 G = (N, E, WN, WE)，其中：
图划分的目标是找到 N 的一个划分 N = N1 ∪ N2 ∪ ... ∪ NP，使得：
当 P = 2 时，称为图二分（Graph Bisection），这是构建更多划分的递归基础。
将图划分类比为"切蛋糕"：节点是蛋糕上的"葡萄干"（带重量），边是连接葡萄干的"丝带"。我们要用刀把蛋糕切成 P 块，使得：（1）每块上的葡萄干总重量相等，（2）切断的丝带总长度最短。这正是负载均衡与通信最小化的权衡。
将 n 个节点恰好切成两半的可能方案数为：
C(n, n/2) = n! / ((n/2)!)² ≈ (2/(πn))^(1/2) × 2^n这是一个指数级的搜索空间。更重要的是，图划分问题是 NP-complete 的——意味着除非 P=NP，否则不存在多项式时间精确算法。我们必须依赖启发式算法。
NP-complete 意味着图划分与已知的困难问题（如旅行商问题、SAT 问题）一样难。目前已知的精确算法在最坏情况下需要指数时间。因此，所有实际使用的划分工具都采用启发式方法，追求"足够好"的解而非最优解。
| 应用 | 节点 N | 边 E | 权重含义 |
|---|---|---|---|
| SpMV (y = Ax) | 矩阵行/列 | 非零元素的关联 | WN=行非零元数, WE=1 |
| PDE 求解 | 网格单元 | 相邻关系 | WN=计算成本, WE=通信量 |
| VLSI 布局 | 芯片单元 | 连线 | WE=连线长度 |
| 数据挖掘聚类 | 数据点 | 相似度 | WE=相似度分数 |
| DNA 物理图谱 | 基因片段 | 重叠关系 | WE=重叠程度 |
| 电话网络设计 | 交换机 | 通信线路 | WE=线路容量 |
// 每个处理器 P 本地计算
y_local = y_local + A_local * x_local
// 获取远程处理器所需的 x 的部分
for all procs P needing part of x_local
send(needed part of x_local, P)
// 接收远程 x，完成计算
for all procs P owning needed x_remote
receive(x_remote, P)
y_local = y_local + A_remote(P) * x_remote图划分有两种互补的视角：
| 概念 | 定义 | 代价度量 |
|---|---|---|
| Edge Separator (Es) | 边集 E 的子集，移除后图分裂为两个近似等大的连通分量 | 被切割边的权重和 |
| Vertex Separator (Ns) | 节点集 N 的子集，移除后（及关联边）图分裂为两个近似等大的连通分量 | 分隔节点的权重和 |
相互转换：
当图具有空间坐标时（如有限元模型中的节点位于 (x, y, z) 空间），可以利用几何信息高效划分。
选择一个通过图"中心"的划分平面，使得平面两侧的节点数大致相等。对于二维图，可以选择一条直线（如沿主轴），将节点投影后在中位数处切分。
定理 (Tarjan, Lipton, 1979): 若 G 是平面图（可在平面上绘制且边不相交），则存在顶点分隔集 Ns，使得：
例如：m × m 网格有 m² 个节点，仅需 m = |N|1/2 个分隔节点。这比任意图的 O(|N|) 分隔好得多！
| 优点 | 缺点 |
|---|---|
| 高效（通常 O(|N| log |N|)） | 依赖节点的空间最近邻连接假设 |
| 不需要知道实际边的位置 | 对"长程连接"图效果差（如 WWW 图） |
| 可作为后续算法的初始猜测 | 可能产生次优划分，尤其当图结构复杂时 |
Kernighan/Lin (1970) 是最早的图划分启发式算法之一，通过迭代改进初始划分来降低切割代价。
给定划分 N = A ∪ B，定义代价 T = cost(A,B) = Σ W(e)（跨越 A 和 B 的边）。选择子集 X ⊆ A 和 Y ⊆ B（|X| = |Y|），考虑交换它们：
newA = (A - X) ∪ Y
newB = (B - Y) ∪ X
newT = cost(newA, newB) < T交换节点 a 和 b 的收益：
gain(a,b) = D(a) + D(b) - 2 × W(a,b)
newT = T - gain(a,b)计算初始代价 T = cost(A,B) // O(|N|²)
Repeat
计算所有节点的 D(n) // O(|N|²)
标记所有节点为未移动
While 还有未移动节点 // |N|/2 轮
在未移动节点中找到 (a,b) 最大化 gain(a,b) // O(|N|²)
标记 a 和 b（但不实际交换）
更新所有未移动节点的 D(n) // O(|N|)
EndWhile
// 找到最佳前缀 (a1,b1)...(am,bm) 使累计 Gain 最大
选择 m 最大化 Gain = Σ gain(k) // O(|N|)
If Gain > 0
执行交换，更新划分和 T
Until Gain <= 0时间复杂度：O(|N|³)（瓶颈在未标记节点的配对搜索）。
FM 算法将复杂度降至 O(|E|)，关键改进：
谱划分由 Fiedler (1970s) 提出，Pothen/Simon/Liou (1990) 推广，基于图的 Laplacian 矩阵的特征向量。
将图想象为一根振动的弦：节点是质量块（质量），边是弹簧。弦有不同的振动模式（谐波），第二阶模式的正负号自然地将弦分为两部分！
对于图 G(N,E)，定义 |N| × |N| 对称矩阵：
L(G)(i,i) = node i 的度数（关联边数）
L(G)(i,j) = -1 （若 i ≠ j 且存在边 (i,j)）
L(G)(i,j) = 0 （其他情况）定理：
1. 计算 L(G) 的第二特征向量 v₂（对应 λ₂）
2. 对于每个节点 n：
若 v₂(n) < 0 → 放入分区 N⁻
否则 → 放入分区 N⁺Fiedler 定理 (1975): 若 G 连通，按 v₂ 符号划分的 N⁻ 和 N⁺ 各自连通。图中"薄弱连接"处的节点在 v₂ 中接近 0，自然成为分隔点。
有趣的循环依赖： 为了优化 SpMV，需要图划分；为了图划分，需要特征向量；为了特征向量，需要做稀疏矩阵向量乘法（SpMV）！循环并非无意义——先用慢的 SpMV 学出结构，再加速后续计算。
对于大型稀疏矩阵，使用 Lanczos 迭代法计算 v₂，其每步仅需一次稀疏矩阵-向量乘法（SpMV）。
这是科学计算中反复出现的核心思想：当图太大无法高效划分时，先粗化、再划分、再细化。
(N⁺, N⁻) = Multilevel_Partition(N, E)
if |N| 很小
(1) 直接划分 G = (N,E)，返回
else
(2) 粗化 G 得到近似图 Gc = (Nc, Ec)
(3) (Nc⁺, Nc⁻) = Multilevel_Partition(Nc, Ec) // 递归
(4) 将 Gc 的划分"扩展"为 G 的初始划分
(5) 用 K/L 或类似方法改进划分
返回
endif这形成一个 V-cycle：递归向下粗化 → 在最粗层划分 → 逐层向上扩展并改进。
匹配：边集 Em ⊆ E，其中任意两边不共享端点。
极大匹配：无法再添加边而不破坏匹配性质。
// 贪心构造极大匹配
Em = ∅
标记所有节点为未匹配
for i = 1 to |N| // 任意顺序访问节点
if i 未匹配
if 存在边 (i,j) 且 j 未匹配
将 (i,j) 加入 Em
标记 i 和 j 为已匹配
endif
endfor粗化过程：将匹配的每对节点坍缩为一个超节点，权重相加；未匹配节点直接保留。
将粗图 Gc 的划分扩展到细图 G：
对于每个节点 j in N:
if j 也是 Nc 中的节点
v(j) = vc(j) // 直接使用粗特征向量
else
v(j) = 邻居节点 vc(k) 的平均值 // 插值
endif然后使用 Rayleigh 商迭代改进特征向量（三次收敛速度）。
在粗层上，图的规模小，划分快；粗划分的质量足以作为细层的良好初始猜测。这类似于多重网格求解 PDE：在粗网格上消除低频误差，在细网格上消除高频误差。
| 软件 | 算法 | 特点 |
|---|---|---|
| METIS / ParMETIS | Multilevel K/L | 最流行的图划分库，github.com/KarypisLab/METIS |
| SCOTCH / PT-SCOTCH | Multilevel + 谱方法 | INRIA 开发，支持分布式并行 |
| Chaco | Multilevel Spectral | Sandia 国家实验室，获 SC'14 Test of Time Award |
| Zoltan | 多种方法集合 | Sandia，支持超图和几何划分 |
| KaHIP | 多种高级方法 | Karlsruhe，当前质量最佳之一 |
| meshpart (Matlab) | 几何 + 谱方法 | Gilbert/Tang/Li 实现，教学友好 |
传统图模型中，一条边只连接两个节点。但 SpMV 中，一个矩阵列可能涉及多行的通信——这需要超图建模。
关键优势：若同一列的非零元被分到不同处理器，只需通信一次该列的 x 值！传统图模型会重复计数。
// SpMV 示例：P1 需要 x(7) 来计算 y(4) 和 y(5)
// 图模型：两条边 (4,7) 和 (5,7) → 通信 x(7) 两次
// 超图模型：一个超边同时包含 4,5,7 → 通信 x(7) 一次！| 维度 | 图划分 | 超图划分 |
|---|---|---|
| 非对称矩阵 | A+AT 丢失信息 | 精确建模通信 |
| 通信估计 | cut size ≠ 通信量 | connectivity-1 度量更准确 |
| 2D 网格 SpMV | 通信量 64 | 通信量 58（更优） |
| 计算成本 | 快（METIS） | 慢 5-20×（PaToH） |
PaToH 等超图划分器比 METIS 慢 5-20 倍，但对非对称矩阵和精确通信建模的场景，这个代价是值得的。Zoltan 和 HMETIS 也支持超图划分。
Bruce Hendrickson 提出的六个图划分 myths：
| # | Myth | 现实 |
|---|---|---|
| 1 | Edge cut = 通信代价 | 总通信量 ≠ 最大通信量；最大值可能更关键 |
| 2 | 简单图足够 | 超图/有向图才能精确建模 |
| 3 | Edge cut 是正确度量 | 不同架构需要不同度量（如最大 vs 总和） |
| 4 | 现有工具解决了问题 | 动态、流式、超图场景仍需新方法 |
| 5 | 关键是找到正确划分 | 有时划分速度比质量更重要 |
| 6 | 图划分是已解决的问题 | 非平凡——分布式图、动态图仍是挑战 |
一种更轻量、可扩展的替代方案：
1. 随机初始化每个节点的标签（共 n 个标签）
2. 迭代更新：每个节点取邻居中最多的标签（平局随机打破）
3. 可选：加入平衡约束（限制每部分节点/边数）
4. 迭代在约束和目标之间交替优化PULP 等软件实现了带约束的标签传播，适用于 PowerGraph、GPS 等图处理系统的流式划分。
负载不均衡来自两个层面：
性能噪声（performance variability）来自硬件或操作系统：
使用 CrayPat、HPC Toolkit、TAU 等工具分析性能时要注意：测量本身可能改变程序行为！负载不均衡不一定是应用问题，系统噪声同样严重。
| 难度 | 特征 | 示例 |
|---|---|---|
| 简单 | 等成本、固定数量 | 规则网格、稠密矩阵、直接 N-body |
| 中等 | 不同但可估计的成本 | 自适应网格、稀疏矩阵、树 N-body |
| 困难 | 成本/数量执行中才知 | 搜索（UTS）、不可预测机器 |
| 方法 | 适用场景 | 优点 | 缺点 |
|---|---|---|---|
| 静态 | 问题规模已知（n, nnz...） | 简单、无运行时开销 | 估算/优化成本高（图划分） |
| 动态 | 工作成本未知 | 自适应性强 | 需要运行时调度开销 |
关键权衡：负载均衡与数据局部性经常矛盾——追求完美均衡可能破坏缓存局部性。
当任务之间无依赖时（如简单的 for 循环），动态调度策略包括：
所有处理器从共享队列逐个取任务。简单但队列竞争严重。
每次取 K 个任务作为一块，减少队列访问次数：
// Chunk 大小 K 的权衡
// K 太大 → 负载不均衡（最后几块可能空闲）
// K 太小 → 队列竞争开销大动态调整 chunk 大小：第 i 次从任务池取 Ki = ⌈Ri/p⌉ 个任务，其中 Ri 是剩余任务数。
// GSS 示例：100 个任务，4 个处理器
// 第 1 次：取 ⌈100/4⌉ = 25 个
// 第 2 次：取 ⌈75/4⌉ = 19 个
// 第 3 次：取 ⌈56/4⌉ = 14 个
// ...逐渐减小，保证后期细粒度均衡GSS 前期取大块减少开销，后期取小块保证均衡。就像分蛋糕：开始时每人拿大块（快速推进），到最后几块时仔细分配（避免有人没分到）。
更高效的方案：每个处理器维护自己的本地队列，空闲时去"偷"别人的任务。
| 操作 | 策略 | 原因 |
|---|---|---|
| 取自己的任务 | LIFO（栈，从顶部取） | 最大化缓存局部性（最近创建的任务数据可能在缓存中） |
| 窃取他人任务 | FIFO（队列，从底部取） | 窃取"较老"的任务——通常是更大的子树，提供足够工作 |
随机选择窃取目标避免了"羊群效应"（多个处理器同时窃取同一目标）。理论证明：随机 work stealing 的期望调度开销仅为 O(p × T∞)，其中 p 是处理器数，T∞ 是关键路径长度。
经典概率结果为随机化调度提供理论保证：
定理：将 n 个球随机投入 p 个桶，最大桶的负载（以极高概率）为：
若 n > p log p: Θ(n/p) + Θ(√(n log(p)/p))
若 n = p: Θ(log n / log log n)当 n >> p 时，最大负载接近最优 n/p！这意味着随机化在任务远多于处理器时效果极好。
每次随机选 d 个桶，放入最空的那个：最大负载降至 O(log log n / log d)。这是随机化带来的指数级改进！
实际任务通常构成有向无环图（DAG），需要更复杂的调度策略。
| 难度 | 结构 | 示例 |
|---|---|---|
| 简单 | 就绪任务集合 | 矩阵乘法、域分解 |
| 中等 | 链 / 树 / 图 | 时间循环、分治算法、直接求解器 |
| 困难 | 运行时才知结构 | 游戏树搜索、离散事件模拟 |
搜索问题（如棋类、N-queens、VLSI 布局、Gröbner 基）的特点是：
理论结果 (Blumofe & Leiserson, 1994)：对于固定任务树、变成本任务，Cilk 的 work stealing 策略：
Karp & Zhang (1996)：对于动态展开的单位成本任务树，随机推送（pushing children to random processors）也是期望最优的。
Cilk 语言使用 "work-first" 原则：优先保持本地任务执行的快速性，仅在空闲时窃取。其调度器被称为 "work-stealing scheduler"，是 Intel TBB、OpenMP 等后续系统的基础。
Charm++ 采用过度分解（over-decomposition）策略：
1. 常规时间步：收集性能数据（instrumented timesteps）
2. 详细负载均衡：激进调整 chares 分布
3. 细化负载均衡：微调优化
4. 拓扑感知：考虑机器拓扑（节点内/节点间）成功应用：
对于稠密线性代数等具有规则 DAG 结构的计算，专用调度器可以高效管理任务依赖：
| 调度器 | 类型 | 特点 |
|---|---|---|
| DAGuE | 库 | 支持稠密线性代数，符号化 DAG 解释 |
| StarPU | 库 | 支持 GPU，分布式数据管理 |
| PLASMA / QUARK | 编译器/库 | 动态调度 DAG 前沿 |
| OpenMP 4.0 | 语言扩展 | task depend 子句，GCC 4.9+ |
| Cilk / TBB | 库 | fork-join 图专用 |
对于 n × n 矩阵、b × b 分块的稠密线性代数：
任务数 = O((n/b)³) = 1,000,000 （当 n=10000, b=100）创建和调度整个 DAG 不可行！解决方案：
POTRF + TRTRI + LAUUM (对称正定矩阵求逆):
- Span (关键路径) = 7(n/b) - 3 = 25 (当 n/b = 4)
- Cholesky 单独: 3(n/b) - 2
- Pipelined: 3(n/b) + 6 = 18Q1：图划分问题的计算复杂度是什么？
Q2：在谱划分中，使用 Laplacian 矩阵的哪个特征向量来划分图？
Q3：在 Task Stealing 中，为什么本地任务用 LIFO、窃取任务用 FIFO？
Q4：超图划分相比图划分的优势是什么？
Q5：关于 Balls-in-bins 理论，当 n = p 时，随机分配的最大负载是多少？
NP-complete 问题，需要启发式算法。METIS、SCOTCH、KaHIP 是主流工具。多重网格加速是核心思想：粗化 → 划分 → 扩展 → 改进。
谱划分基于 Laplacian 的第二特征向量，理论优雅但计算代价高。K/L 和 FM 算法更实用，常作为改进模块使用。超图模型对 SpMV 通信建模更准确。
本地 LIFO + 窃取 FIFO + 随机选择目标：理论证明期望意义最优。Cilk、TBB、Charm++ 均采用此策略。过度分解让 Charm++ 支持层次化、拓扑感知的负载均衡。
追求完美均衡可能破坏缓存局部性。理解应用特征（任务成本、依赖结构、通信模式）是选择静态/动态/混合策略的关键。