静态划分
适合规则网格、稠密矩阵和固定迭代次数。优点是确定、可复现、局部性强；缺点是无法应对成本估计误差。
CS267 · 第 25b 课
当任务数量、执行时间或依赖结构直到运行时才知道，静态划分就不再可靠。本课从负载不均衡的测量出发，逐步推导 self scheduling、guided scheduling、work stealing，并解释为什么“本地 LIFO、远端 FIFO、随机选择 victim”成为现代任务运行时的经典设计。
并行程序在 barrier 前等待，并不自动意味着负载不均衡。它也可能来自锁竞争、串行瓶颈、网络抖动或操作系统噪声。平均运行时间会掩盖慢节点，因此应记录每个 worker 的独立时间，并观察分布和尾部。
设第 (i) 个 worker 的运行时间为 (t_i)，平均时间为 (ar t)，可用下面的归一化指标快速定位问题：
\[I = \frac{\max_i t_i - \bar t}{\bar t}\]
(I) 越大，说明最慢 worker 与整体平均值的差距越明显。但它不能区分应用负载、硬件故障和系统噪声，需要配合时间直方图与性能工具继续分析。
| 现象 | 可能原因 | 验证方式 |
|---|---|---|
| 所有线程同时变慢 | 内存带宽、共享锁、系统服务 | 硬件计数器、锁等待、节点级时间线 |
| 少数线程长期更慢 | 任务分配不均、持久硬件噪声 | 逐线程直方图，而非总体平均 |
| 偶发超长尾 | 云平台抖动、中断、调度抢占 | 关注 p99/p99.9，而非中位数 |
| 大量 barrier 等待 | 负载不均或前序串行区 | 比较 barrier 前的独立执行时间 |
如果任务数量和成本都能提前估计，静态划分通常有最低的运行时开销和最好的数据局部性。但一旦任务成本不同，最优静态分配会接近 bin packing，而 bin packing 是 NP-hard 的。
适合规则网格、稠密矩阵和固定迭代次数。优点是确定、可复现、局部性强；缺点是无法应对成本估计误差。
适合 Mandelbrot、树搜索、自适应网格、稀疏和非规则任务。优点是能吸收不确定性；代价是队列、同步和任务迁移开销。
负载越均衡，任务迁移通常越多；迁移越多，缓存和 NUMA 局部性越容易被破坏。
最简单的动态方案是维护一个共享任务队列：worker 完成任务后从队列取下一个任务。它能得到细粒度均衡，却可能让共享队列成为新的串行瓶颈。
while True:
task = shared_queue.pop()
if task is None:
break
execute(task)每次领取 (K) 个任务可减少锁竞争。大 chunk 开销低但容易造成尾部不均衡；小 chunk 均衡好但队列访问频繁。
GSS 让 chunk 随剩余工作递减。若第 (i) 次访问任务池时还有 (R_i) 个任务、共有 (p) 个 worker，则：
\[K_i = \left\lceil \frac{R_i}{p} \right\rceil\]
执行前期用大 chunk 摊薄调度成本，接近尾部时自动缩小 chunk，提高收尾阶段的均衡性。OpenMP 的 guided schedule 就体现了这一思想。
共享队列仍然会集中竞争。Work stealing 为每个 worker 配置私有 deque：正常情况下只访问自己的队列；空闲时才从其他 worker 窃取任务。
def worker_loop(me):
while not globally_finished():
task = me.deque.pop_local() # 本地端：LIFO
if task is None:
victim = choose_random_worker()
task = victim.deque.steal_oldest() # 远端：FIFO
if task is not None:
execute(task)| 设计问题 | 经典选择 | 原因 |
|---|---|---|
| 本地取哪个任务？ | LIFO / deque 顶部 | 刚生成的任务更可能复用当前缓存和工作集 |
| 窃取哪个任务？ | FIFO / deque 底部 | 较老任务往往代表更大的剩余子树，单次窃取能搬走更多并行工作 |
| 向谁窃取？ | 随机 victim | 避免热点和确定性最坏情况，在未知负载下提供高概率保证 |
| 邻居还是远端？ | 分层或拓扑感知随机 | 近邻有局部性，远端有更强均衡能力，实际系统常分阶段选择 |
如果算法的 critical path 很长，或者就绪任务数量始终小于处理器数量，再聪明的调度器也无法填满机器。调度解决的是“已有并行工作如何分配”，不是“如何凭空产生并行工作”。
把任务看作球、worker 看作桶。若把 (n) 个任务随机放入 (p) 个 worker，当 (n > p\log p) 时，最大负载以高概率接近：
\[\frac{n}{p} + \Theta\!\left(\sqrt{\frac{n\log p}{p}}\right)\]
当 (n=p) 时，最大负载约为：
\[\Theta\!\left(\frac{\log n}{\log\log n}\right)\]
随机分配并不完美，但它在几乎没有先验信息的情况下避开了集中冲突。对动态任务图，经典 work-stealing 分析进一步给出接近：
\[T_P \approx \frac{T_1}{P} + O(T_\infty)\]
其中 (T_1) 是总 work，(T_\infty) 是 critical path（span）。这说明性能同时受总工作量和依赖链长度约束。
任务相互独立时，调度器只需分配现成工作；对于树或 DAG，任务在运行过程中才产生。DFS 使用显式栈，内存小、局部性好，但并行度有限；BFS 暴露大量同层任务，却可能占用巨大内存。
本地 worker 深度优先展开最新子任务，保持工作集紧凑；窃取者从另一端拿走最老的高层任务，相当于切走一棵较大的子树。一个 deque 同时兼顾了 DFS 的局部性与 BFS 式的并行暴露。
现代运行时会显式维护任务依赖或数据依赖。OpenMP tasks、Cilk、oneTBB、Charm++、PaRSEC、Legion、StarPU、Dask 都在不同抽象层上解决这个问题：发现 ready task、映射到设备、移动数据并监控长尾。
Charm++ 不把“一个 MPI rank”视为不可移动的负载单位，而是把应用分解成远多于处理器数量的 migratable objects（chares）。运行时周期性收集负载，重新映射对象。
Q1：为什么只看所有 worker 的平均运行时间容易漏掉负载不均衡？
Q2：Guided Self Scheduling 为什么让 chunk 逐渐变小？
Q3：经典 work stealing 为什么从 victim deque 的另一端窃取？
Q4：公式 (T_P \approx T_1/P + O(T_\infty)) 中，(T_\infty) 表示什么？
并行性能由最慢 worker 决定。先测逐 worker 时间和尾部分布，再判断是否真的需要负载均衡。
私有队列消除共享热点；本地 LIFO 保局部性，远端 FIFO 窃取大子树。
随机 victim 在未知负载下避免集中冲突，并让 work stealing 接近 work/span 理论下界。
任务粒度、依赖、迁移成本和拓扑共同决定 static、guided、stealing 或混合策略。