Lecture 8: Performance Optimization I: Work Distribution and Scheduling
Lecture 8: Performance Optimization I: Work Distribution and Scheduling
1. 章节标题与概述
Lecture 8: Performance Optimization I: Work Distribution and Scheduling（性能优化 I：工作分配与调度）
本讲核心问题：当一个并行程序已经把工作分解（decomposition）成许多小块之后，“把哪一块交给哪个执行上下文、什么时候交” 就成了决定性能的关键。本讲要回答的是：在”让所有处理器一直有活干”与”少付调度/同步的额外开销”这对互相冲突的目标之间，如何选择静态分配（static assignment）、半静态分配（semi-static）、动态分配（dynamic assignment），以及工作窃取（work stealing），并把任务粒度（task granularity） 调到合适的位置。
- 涉及的主要硬件/软件机制：
- 硬件侧：多核/SMT 的执行上下文（execution context） 数量、共享内存的缓存行（cache line）迁移与争用（一个被 8 个核反复读-改-写的计数器行是串行化瓶颈）、片间/跨 socket 的相干性延迟（实证约 0.3–0.5 µs 一次争用原子操作）、NUMA 与内存带宽对”分到工作后跑得动跑不动”的约束。
- 软件侧：共享工作队列（shared work queue）、每线程双端队列（per-worker dequeue）、原子取号（
atomic_incr/fetch_add）与锁（lock/unlock）、Cilk Plus 的cilk_spawn/cilk_sync抽象、worker 线程池（worker pool）、continuation stealing（偷连续体）与 child stealing（偷子任务）、greedy join scheduling（贪婪汇合调度）、同步点描述符（sync descriptor，用 spawn/done 计数实现cilk_sync）。
在并行计算知识体系中的角色：本讲是第 7 讲”并行编程基础（decomposition / assignment / orchestration 三步法）”的直接延续，也是全课程中唯一一次系统地讲”调度器内部怎么工作”。它把前面学到的 Work/Span、Amdahl 定律 从”分析工具”变成”设计工具”：负载不均是用 Amdahl 惩罚你，粒度过细是用同步开销惩罚你，两者之间的最优解取决于你的工作负载与你的机器（这也是课程反复强调的”must know your workload, and your machine”）。后续的性能优化 II（局部性、缓存分块、伪共享）、同步与锁、无锁数据结构、以及异构调度（ISPC task、CUDA block 调度）都建立在本讲的概念上。
- 配套材料：
lectures/07_progperf1.pdf（抽取文本extracted/07_progperf1.txt，共 48 页）：已公开，可在 https://www.cs.cmu.edu/~418/lectures/ 公开下载。Fall 2026 日程表（https://www.cs.cmu.edu/~418/schedule.html）把 Sep 11 排为第 8 讲 “Performance Optimization I”，对应这份讲义。讲义首页写的是 “Lecture 5: Performance Optimization Part 1: Work Distribution and Scheduling” 与 “CMU 15-418/15-618, Fall 2025”：这是讲义沿用历史学期版本的正常现象（讲次编号与学期字样随年度重排），不是错误。cs149_supp/perfopt1.txt：Stanford CS149（Fall 2025）Lecture 5 同名讲义的已公开补充材料（共 63 页），已公开。它比 CMU 版多出关键的两块：cilk_sync的实现细节（sync descriptor 的 spawn/done 计数演化，slide 51–61） 与 Cilk 的 greedy join scheduling 策略（slide 62–63），本笔记对同步实现的描述以它为准。注意：两份讲义中同名示例给出的数字略有差异（例如”失衡的处理器多做了多少工作”一处是 20%、一处是 2 倍），本笔记在 §4 把两个版本都作为算例列出。- 讲课录像（Panopto / YouTube）：Fall 2026 日程表中被注释隐藏，属未发布（历史学期在 YouTube 上有存档，但不在 Fall 2026 公开日程中）。
- Ed 讨论区、Autolab、Canvas：需登录，非公开。
- 部分讲座在 Fall 2026 尚未发布公开讲义（Performance Analysis / Profiling、Transactional Memory、AI in System Design 等）；其历史学期 PDF 位于
/afs/cs/academic/class/15418-*/public/之下，需要 CMU 登录，属未公开。 - Fall 2026 授课教师为 Brian Railing 与 Dimitrios Skarlatos；课程由 Kayvon Fatahalian 创建。
2. 核心概念与硬件/软件架构图解
2.1 全部问题的来源：三个互相冲突的目标
- 定义与目的：讲义的出发点是（slide 2/48）：优化并行程序性能，是对 decomposition、assignment、orchestration 三者反复精化的迭代过程，而其中三个目标天生互相冲突：
- Balance workload（把工作均衡地铺到可用执行资源上）；
- Reduce communication（减少通信，避免停顿 stall）；
- Reduce extra work / overhead（减少为了获得并行性、管理分配、减少通信而额外做的工作）。 你不可能同时把三者都做到最优：要让负载均衡，就得多切任务、多通信、多管理；要少管理，就得任务粗、但容易失衡。
- 直观解释（”它是什么？”）：把它想成餐厅后厨的分菜问题。菜（工作）总量固定：
- 想”人人不闲着”（balance），就得把菜切得很碎、谁空了谁再来端一盘，代价是每个人要不停跑传菜窗口排队（communication + overhead）；
- 想”少跑动”（reduce communication），就让每个人端着大盆菜不动（任务粗），代价是有人早早吃完、有人还在啃（imbalance）；
- 想”少做无用功”（reduce extra work），就提前把菜分好放到各人灶台（static assignment），代价是一旦量估错就失衡。 调度策略的选择，本质上就是在这三者之间挑一个你能接受的折中点。
- 图解（图 1）：三目标张力与”先简单后测量”的工作流
并行性能优化的三个目标（互相拉扯）
Balance workload
/\
/ \
/ \
冲突区域 → / ◇ \ ← 越往一个顶点走，
/ \ 另两个越差
/__________\
Reduce communication ---- Reduce extra work
(少通信/少停) (少做调度开销)
迭代式优化流程（讲义 TIP #1：先把最简单的方案写出来，再测，再决定要不要更复杂）
+--------------------------------------------------------------------------------+
| 1. 最简实现 2. 测量 3. 诊断瓶颈 4. 只改瓶颈 回到 2 |
| (static/粗粒度) → (时间/加速比) → (失衡? 同步? 带宽?) → (换分配策略/粒度) |
+--------------------------------------------------------------------------------+
| ^
| "My solution scales" = 你的代码恰好按你需要的规模扩展 |
+-------------------------------------------------------------------+
- 关键操作与性能特征：讲义明确给出 TIP #1：总是先实现最简单的版本，然后测量，再决定是否需要做得更好。”我的方案可扩展”这句话的正确含义是”在我的目标机器规模上可扩展”。如果预知只会跑低核数机器，为了实现”能产生成百上千块独立工作”的复杂方案而付出的代价，可能完全不必要。
2.2 负载不均如何被 Amdahl 定律放大惩罚
定义与目的：负载不均（load imbalance） 指程序执行期间并非所有处理器都在同时计算、或它们并非同时完成各自的份额。理想情况是”所有处理器在整个执行期间都在计算，并且同时完成”。
直观解释（”它是什么？”）：类比四人划船。三个人划 100 下就靠岸了，第四个人需要划 120 下。船不会在 100 下时到岸，也不会因为多了一个人而变快：最后 20 下只有一个人在划，其余三人把桨收起来看。这段”只有一个人在划”的时间，在 Amdahl 定律里等价于串行执行段——即使它只占全部工作量的 5%，在 64 核上也只能跑到 15.4 倍（理想是 64 倍），而在 1024 核上依然只能跑到 19.6 倍（渐近上限 20 倍）。
图解（图 2）：负载不均的 Gantt 图与 Amdahl 折算
时间 →
|---- 全部处理器并行计算 ----|---- 尾部只有 P4 在跑 ----|
P1 ████████████████████████████████|
P2 ████████████████████████████████|
P3 ████████████████████████████████|
P4 ████████████████████████████████████████████| ← 多做 20% 的工作
^ ^
| |
理想完成点 实际完成点
讲义的说法：实际运行时间 = 1.2 × 理想运行时间 ⇒ 运行时间的 ~20% 是"串行段"
（更精确地按下面 5% 的串行工作量算：1 + w(P-1)/W = 1 + 0.05×3 = 1.15×，
串行段占运行时间 17% —— 与讲义的 ~20% 同量级）
折算：若串行段工作量 w 占总工作 W 的 5%（S=0.05），4 核加速比上限
Speedup ≤ 1 / (S + (1-S)/P) = 1/(0.05 + 0.95/4) = 3.48x （P=4）
1/(0.05 + 0.95/64) = 15.42x （P=64，理想是 64x）
1/(0.05 + 0.95/1024) = 19.64x（P=1024，渐近上限 1/S = 20x）
讲义 slide 4/48 的另一种表述：P4 做 20% 更多的工作 → 慢 20% 完成；
CS149 版 slide 5/63 的表述：某处理器做 2 倍工作 → 运行时间 50% 是串行 → S=0.2。
- 性能特征：注意放大器效应：失衡本身只是”多一点工作”，但它被 Amdahl 折算成”串行段”，于是核数越多惩罚越重：S=0.05 时，4 核上限 3.48x、64 核上限 15.42x（相对理想的 64x 只剩 24% 效率）、1024 核上限 19.64x（渐近上限就是 1/S = 20x）。这就是”只有很小的负载不均就能显著限制最大加速比”的定量含义。
2.3 静态分配：blocked 与 interleaved
- 定义与目的：静态分配指工作到线程的映射预先确定。注意它不一定是编译期决定的：只要”工作量与工人数已知时映射就固定”，就叫静态（可以由输入规模、线程数等运行期参数算出）。讲义回顾了网格求解器示例的两种经典静态划分：
- blocked（块状）：把连续的一段网格单元分给同一个线程；
- interleaved（交错/循环）：按
i % P把单元分给 P 个线程。
- 直观解释（”它是什么？”）：blocked 像把一条街分成 4 段包干——每人守一段，各扫各的，不需要说话（通信少、局部性好），但如果某段特别脏就有人先收工；interleaved 像扑克发牌——每人轮流拿一张，工作量自动被摊得很均匀，但每个人手里的牌散落全街，来回跑（局部性差、缓存行利用率低）。
- 适用条件（讲义 slide 6–7/48）：
- 工作的成本与数量可预测，程序员能提前算出好的分配；
- 最简单的情形：所有工作成本相同（例如 12 个任务、4 个处理器 → 每人 3 个）；
- 成本不均但已知（或统计上已知，例如”平均成本相同”）→ 按成本做加权划分即可（如 LPT，见 §2.5）。
- 优点：简单、运行期开销几乎为零（额外工作只是一点索引运算）。
- “半静态”（semi-static）：当工作的成本只在近期未来可预测时（”最近的过去是最近未来的好预测”），程序可以周期性自我剖析（profile）并重调分配，两次重调之间分配是”静态”的。典型场景：自适应网格（adaptive mesh）——物体移动或流场变化使网格缓慢变化，按变化后的网格重新着色；粒子模拟——粒子在模拟中缓慢漂移，只需间歇性地重新分配。此时的关键判据是变化的速率：变化慢，重分配就不必频繁。
表 1：工作分配策略谱（静态 → 半静态 → 动态 → 窃取）
| 策略 | 谁决定映射 | 需要的先验知识 | 运行期开销 | 负载均衡能力 | 典型场景 |
|---|---|---|---|---|---|
| 静态 blocked | 程序员（预先算） | 工作量与成本可预测 | 近零（索引运算） | 差（成本不均时） | 规则网格、均匀成本任务 |
| 静态 interleaved | 程序员（预先算） | 成本统计上均匀 | 近零 | 中（摊平慢变化） | 成本近似均匀的循环体 |
| 半静态 | 程序周期性重算 | 短期可预测 | 周期性重分配成本 | 中上好 | 自适应网格、粒子模拟 |
| 动态（共享计数器/队列） | 运行期调度逻辑 | 无需 | 每次取活都要同步 | 好 | 成本不可预测的任务集 |
| 工作窃取（分布式队列） | 运行期调度器 | 无需 | 仅窃取时付代价 | 好 | fork-join 递归分解 |
2.4 动态分配：共享计数器与共享工作队列
- 定义与目的：动态分配指程序在运行期决定工作到处理器的分配，以保证负载被良好铺开——它适用于任务执行时间或任务总数不可预测的情形。讲义用”素性测试”的例子对比：串行版本直接
for (i=0;i<N;i++) is_prime[i] = test_primality(x[i]);，而并行版本用一把锁保护一个共享计数器：
LOCK counter_lock; int counter = 0; // 共享变量
while (1) {
int i;
lock(counter_lock);
i = counter++; // 等价于原子操作 atomic_incr(counter)
unlock(counter_lock);
if (i >= N) break;
is_prime[i] = test_primality(x[i]); // 执行时间未知的工作
}
- 直观解释（”它是什么？”）：共享工作队列像医院挂号窗口：所有病人（worker 线程）在一个窗口前排队领号（取一件工作），领完号各自去诊室（执行工作）。柜台本身是串行的：窗口一次只能服务一个人，队伍再长也没用——这就是”临界区（critical section）”。
- 图解（图 3）：共享队列 + 临界区时间轴（细粒度 vs 粗粒度）
共享工作队列（Shared Work Queue）——"一个窗口"
+-------------------------------------------------+
| task0 | task1 | task2 | task3 | task4 | ... | ← 每件工作独立
+-------------------------------------------------+
^ ^ ^ ^
| | | | （取走一件工作 = 一段临界区）
T1 T2 T3 T4
Worker 线程：从共享队列拉取工作；产生新工作时再推回队列
时间轴（细粒度：1 task = 1 element）
T1 |CS|work 0 |CS|work 4 |CS|work 8 |
T2 |CS|work 1 |CS|work 5 |CS|work 9 |
T3 |CS|work 2 |CS|work 6 |
T4 |CS|work 3 |CS|work 7 |
^^^^ 每个 CS 都是串行的（同一把锁），它们是"串行程序里不存在的额外工作"
且 CS 之间互相排队 → 按 Amdahl：运行时间下限 = 任务数 × 临界区长度
时间轴（粗粒度：1 task = 10 elements，临界区进入次数少 10 倍）
T1 |CS|work 0..9 |CS|work 40..49 |
T2 |CS|work 10..19 |CS|work 50..59 |
^^^^ CS 次数下降 → 同步开销下降；但每件工作变长 → 可能出现负载不均
- 性能特征：细粒度（1 task = 1 element）的优点是负载均衡好（任务多、每件都小），缺点是同步开销可能极高（临界区串行化，加上”串行程序里不存在的额外工作”）；粗粒度（例如
GRANULARITY = 10）的好处是临界区进入次数减少 10 倍，坏处是每件工作变长，负载不均风险上升。讲义在这里提出一个关键反问：“So… IS IT a problem?”（所以，这真的是问题吗？）——答案是”取决于临界区开销与每件工作成本的比值”，这正是 §4.4 用实测数据定量回答的问题。 - 选择任务粒度的两个反向力量（讲义 slide 13/48）：
- 想任务数 ≫ 处理器数（很多小任务 → 动态分配才能获得好的负载均衡）→ 激励小粒度；
- 想任务数尽量少（减少管理分配的开销）→ 激励大粒度；
- 理想粒度取决于许多因素：必须了解你的工作负载和你的机器。
2.5 更聪明的调度：长任务优先（LPT）
- 定义与目的：动态分配本身不解决“长杆（long pole）”问题。讲义给出 16 个任务的例子：如果系统按从左到右的顺序把它们派给 worker，而最长的那个任务排在最后，那么当其它三个处理器都完成时，最后一个任务才刚开始 → 尾部出现大块空洞（slop）。两种解法：
- 把工作切得更细：希望”长杆”相对整体执行时间变短。代价：可能增加同步开销；也可能根本做不到（也许这件工作本质上是串行的，不可再分）。
- 更聪明的调度：长任务优先（Longest Processing Time first, LPT）：让执行长任务的线程做的任务件数更少，但总工作量与其他线程近似相同。代价：需要一些关于工作负载的知识（成本要有一定可预测性）。
- 直观解释（”它是什么？”）：装箱/排队论里的经典技巧：超市结账时，先让买得最多的人去排队——因为他的结账时间最长，越早开始越不会成为最后一个离店的人；如果让他最后来，所有人都在等他一个人。等价地：先放大石头，再往缝里塞沙子。
- 图解（图 4）：顺序决定 makespan
长任务最后（动态队列按输入顺序派发）
时间 →
P1 |t0|t4|t8 |t12| Idle ...................................
P2 |t1|t5|t9 |t13| Idle ...................................
P3 |t2|t6|t10|t14| Idle ...................................
P4 |t3|t7|t11| |========= 长任务 t15（60 单位）=========|
^ 完成时刻 = makespan 84
长任务最前（LPT）
P1 |===== 长任务 t15 =====|t4|t8 |t12|
P2 |t1|t5|t9 |t13|t16|
P3 |t2|t6|t10|t14|
P4 |t3|t7|t11|t17|
^ 完成时刻 = makespan 60 （§3.4、§4.2 有完整的数值仿真：49 理想 / 84 / 60 / 50）
- 性能特征：长任务优先把”尾部空洞”从 84 单位 压到 60 单位（理想值 49），折算出的串行段从 S=0.417 降到 S=0.183，Amdahl 加速比上限从 1.78x 升到 2.58x。若进一步把长任务一分为二并且仍然长任务优先，makespan 可到 50 单位（S=0.020，上限 3.77x）——“拆分”与”排序”是两种互补手段，叠加使用最有效。
2.6 用分布式队列降低同步开销：工作窃取
- 定义与目的：共享队列的痛点是所有 worker 都要在同一把锁上同步。解法是给每个 worker 一个自己的队列：
- worker 优先从自己的队列取工作、向自己的队列推新工作；
- 当自己的队列空了（且没别的活），去别的队列”窃取（steal）”。
- 为什么这样更好（讲义 slide 18/48）：
- 昂贵的同步/通信只在窃取时发生，而窃取只在必要时发生（为了负载均衡），不是每次取工作都要付；
- 局部性提升：常见情形是”线程处理自己创建的任务”（生产者-消费者局部性，producer-consumer locality）；
- 实现挑战（讲义明确列出）：从谁那里偷？偷多少？如何检测程序终止？以及”在保证互斥的前提下，让本地队列访问足够快”。
- 直观解释（”它是什么？”）：四条装配线各自的”待办筐”。每个工人先干自己筐里的活（不需要和任何人打招呼）；只有当自己的筐空了，才去同事的筐里抓一把活回来。因为”筐空了”是少数时刻，平时大家都在闷头干活，只有偶尔一次的”抓活”需要沟通。
- 图解（图 5）：每线程 dequeue 与”本地尾部 / 窃取头部”
T0（忙） T1（空闲） T2（空闲） T3（忙）
+------------------------+ +------------+ +------------+ +-------------+
| cont: 101-200 | 窃取 | <------ | 队列为空 | | 队列为空 | | cont:151-200|
| cont: 51-100 | 窃取 | <------------------------ | | | |
| 正在做 工作 0-25| | +------------+ +------------+ +-------------+
+------------------------+
^ ^
tail 端 head 端
owner 在这里 push/pop 窃取者在这里取走整件工作
（LIFO 后进先出： （FIFO 先进先出：
拿最近创建的、最深的 拿最早创建、调用树里
工作 → 保局部性） 最大的一块 → 摊薄窃取成本）
为什么这样切分？（讲义 slide 46/48 + CS149 slide 49/63）
(1) 减少争用：本地线程与窃取线程访问的是 dequeue 的**不同端**，不做同一个元素的 CAS；
(2) 摊薄窃取成本：头部的工作是调用树里"更大"的一块，窃取一次的代价被更长的未来计算摊薄；
(3) 最大化局部性：配合"先跑子任务"，本地线程总在自己那片调用树上工作。
(4) 高效的无锁 dequeue 实现是存在的（Chase-Lev，见 §3.3）。
(5) 受害者的选择：空闲线程**随机**挑一个线程去尝试窃取。
- 性能特征：大部分时间线程只在本地 dequeue 上 push/pop（几乎免费），只有窃取时才付原子操作与缓存行迁移的代价。因此”偷大块”是设计原则：一次窃取（0.1–1 µs 量级）必须被后面几百微秒的计算摊薄，否则窃取开销会像细粒度锁一样吃掉收益（§4.5 有算例）。
2.7 队列里的工作不必互相独立：任务依赖 DAG
- 定义与目的：任务管理系统中，工作项可以带显式依赖；只要一件任务的依赖没有全部满足，它就不会被取出交给 worker。讲义给出 API 形态的例子：
foo_handle = enqueue_task(foo); // 入队 foo（与之前所有任务无关）
bar_handle = enqueue_task(bar, foo_handle); // 入队 bar，但必须等 foo 完成才能运行
- 直观解释（”它是什么？”）：流水线上的工序卡。一张卡上写着”本工序必须在 3 号件完工之后才能开始”，调度员（task management system）负责检查依赖是否满足，满足才把卡发给工人；工人也可以在干活的过程中提交新的工序卡（并声明依赖）。
- 性能特征：依赖关系通常构成一张 DAG（有向无环图）；调度器的自由度只来自”当前所有依赖已满足”的任务集合（ready set），因此任务图的关键路径（span）直接决定运行时间下限——这正是 §4 的 work-span 模型的适用对象。
2.8 Fork-join 抽象：cilk_spawn / cilk_sync
- 定义与目的：分治算法（quicksort、归并、树遍历……）天然含有大量互相独立的工作，fork-join（分叉-汇合） 是表达它们的自然方式。本讲的代码示例语言是 Cilk Plus（MIT 起源、后成为开放标准，曾被 GCC、Intel ICC 支持）：
cilk_spawn foo(args);语义：调用 foo，但与普通函数调用不同，调用者可以异步地继续执行（”fork”，创建一个新的逻辑控制流）；cilk_sync;语义：当本函数派生的所有调用都完成后才返回（”join”，与派生调用汇合）；- 重要细节：任何包含
cilk_spawn的函数末尾都有隐式的cilk_sync。含义是：当一个 Cilk 函数返回时，它关联的所有工作都已经完成。
- 抽象 vs 实现（讲义 slide 28/48，CS149 slide 30/63）：
cilk_spawn不规定被派生调用如何、何时被调度执行，只规定它可以与调用者（以及调用者派生的其它调用）并发执行；cilk_sync构成对调度的约束：所有派生的调用必须在cilk_sync返回前完成。- CS149 由此提了一个很好的判断题：如果某个 Cilk 实现把
cilk_spawn foo()完全当成普通函数调用，它还是正确的实现吗？ 答案见 §7 思考题 1。
- 直观解释（”它是什么？”）：
cilk_spawn像把一件事顺手写进”待办便签”：”这件事可以交给别人做，也可以我自己做，反正它和接下来的事没有先后约束”。cilk_sync像下班前清空所有便签：”便签上没做完的事全部做完，我才能接着往下走”。 - 图解（图 6）：fork-join 的调用树与 DAG
代码： 调用树（含串行省略）：
cilk_spawn foo(); main
bar(); ├── foo() ← 派生出的"子"
cilk_sync; └── bar() ← 连续体 continuation
（cilk_sync 汇合）
bar(); foo 与 bar 可以并发执行
foo()
更一般地，三个 spawn 一个调用：
cilk_spawn foo(); main
cilk_spawn bar(); ├── foo()
cilk_spawn fizz(); ├── bar()
buzz(); ├── fizz()
cilk_sync; └── buzz() ← 四个调用可并行，代价是 3 次 spawn 管理
DAG 视角（节点=一段工作，边=依赖）：
[main 前半]
/ | \
[foo] [bar] [fizz]
\ | /
[buzz + 后半] ← cilk_sync 汇合点
Work W = 所有节点工作量之和；Span S = 最长路径；并行度 = W/S
- 性能特征：并行开销随 spawn 次数增长。讲义特意指出：用两次 spawn 表达”与一个 spawn 相同量的独立工作”，运行时开销可能更高（多一次 spawn 的管理）。所以”派生多少”要按 parallel slack（并行冗余度） 来定（见 §4.3）：要有比执行能力更多的独立工作以利于负载均衡（实践上 ~8 倍），但不能多到粒度太细。
2.9 从抽象到实现：worker 线程池 + 每线程工作队列
- 先看一个”天真”的实现：把每个
cilk_spawn翻译成一次pthread_create，把cilk_sync翻译成相应的pthread_join。会出什么问题？- spawn 操作过于重量级（线程创建是微秒级、内核参与）；
- 并发运行的线程数远多于核数（SMT/调度器被压垮）；
- 上下文切换开销；
- 工作集（working set）比需要的更大，缓存局部性变差。
- 正确的做法：worker 线程池（pool of worker threads）：
- Cilk Plus 运行时维护一个 worker 线程池，可以（近似地）理解为”所有线程在程序启动时创建”；
- worker 线程数恰好等于机器上的执行上下文数（讲义给的例子：4 核 8 超线程的笔记本 → 8 个 worker）；
- 每个 worker 的主循环就是：有活就取一件、跑掉：
while (work_exists()) {
work = get_new_work();
work.run();
}
- 现实实现是惰性的：worker 线程在第一次 Cilk spawn 时才初始化（ISPC 对跑 ISPC task 的 worker 线程也是同样策略）。
- 直观解释（”它是什么？”）：常驻的 8 个工人 + 每人一个待办筐（而不是”每来一件事就雇一个人”）。雇人很贵，所以固定雇 8 个（等于机器的执行上下文数），让待办筐承担所有调度弹性。
- 图解（图 7）：worker 池 + 每线程工作队列 + 窃取
Cilk Plus 运行时的 worker 线程池（8 个 worker，对应 8 个执行上下文）
+--------+--------+--------+--------+--------+--------+--------+--------+
|Thread 0|Thread 1|Thread 2|Thread 3|Thread 4|Thread 5|Thread 6|Thread 7|
+--------+--------+--------+--------+--------+--------+--------+--------+
| | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
|deque| |deque| |deque| |deque| |deque| |deque| |deque| |deque| ← 每线程一个
| 0 | | 1 | | 2 | | 3 | | 4 | | 5 | | 6 | | 7 |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
^ ^
| |
本地 push/pop（快） 空闲时随机选受害者窃取（慢，但少）
执行 cilk_spawn foo(); bar(); 时的三个时刻（对应讲义 slide 35–38/48）：
(a) 串行实现（天真）：Thread 0 用普通函数调用跑 foo()，
连续体 bar() 隐式存在 Thread 0 的调用栈里。
Thread 1 此时空闲 —— 它本可以在跑 bar()！
(b) 到达 cilk_spawn 时（run child first）：
Thread 0 stack: [ ... foo() ... ] Thread 0 queue: [ cont: bar() ]
Thread 1 stack: [ 空 ] Thread 1 queue: [ 空 ] ← 空闲线程
(c) Thread 1 发现自己的队列为空，去"忙"线程的队列找活：
1. 查看 Thread 0 的队列 2. 把工作搬到自己的队列 3. 恢复执行 bar()
Thread 0 queue: [ 空 ] Thread 1 queue: [ 空 ]
Thread 0: 执行 foo()… Thread 1: 执行 bar()… ← 并行起来了
2.10 关键设计选择：偷”子任务”还是偷”连续体”？
- 定义与目的：在
cilk_spawn foo(); bar();处，调用线程面临二选一：- 先跑子任务（run child first）：把连续体（continuation，即
bar()及其之后）登记起来供别人窃取 → 称为 continuation stealing（偷连续体）； - 先跑连续体（run continuation first）：把子任务
foo()登记起来供别人窃取 → 称为 child stealing（偷子任务）。
- 先跑子任务（run child first）：把连续体（continuation，即
- 讲义（与 CS149）选择的是 continuation stealing。用一个循环来说明为什么：
for (int i = 0; i < N; i++) { cilk_spawn foo(i); }
cilk_sync;
- child stealing（先跑连续体）：调用线程会先把所有迭代的 spawn 都登记完，才开始执行任何一个。相当于对调用图做广度优先遍历，需要 O(N) 的空间（最大空间），而且如果没有窃取发生，执行顺序与”删掉 cilk_spawn”的程序差别巨大（先登记完 0..N-1，再执行）。队列里堆满
foo(0), foo(1), …, foo(N-1)。 - continuation stealing（先跑子任务）：调用线程只创建一件可被窃取的东西——代表”所有剩余迭代”的连续体（
cont: i=1）。如果没有窃取发生，线程不断从队列弹出连续体、执行foo(i)、再把i加 1 的连续体入队，于是执行顺序与”删掉 spawn”的程序完全一致（深度优先遍历）。 - 空间界的可证明结论（讲义 slide 42/48）：continuation stealing 下，T 个线程的系统的工作队列总存储不超过单线程执行栈存储的 T 倍。
- 直观解释（”它是什么？”）：BFS vs DFS 的取舍。child stealing 像”先把所有待办便签都写下来贴在墙上（墙会爆）”；continuation stealing 像”只写一张便签：剩下的活“，撕一张做一张（墙永远只有几张便签），而且没人帮忙时我做的事跟单线程一模一样——这带来极好的缓存局部性与可调试性。
- 图解（图 8）：两种策略的队列状态对比
child stealing（先跑连续体）—— 讲义未采用
循环体会先把所有迭代登记完：
Thread 0 queue (tail → head):
[ foo(N-1) | foo(N-2) | ... | foo(2) | foo(1) | foo(0) ] ← O(N) 空间，广度优先
无窃取时执行顺序： foo(0) 最后才跑（顺序与串行版不同）
continuation stealing（先跑子任务）—— Cilk 采用
每一步只登记"剩下的迭代"这一张连续体：
时刻 1: Thread 0 queue: [ cont: i=1 ] Thread 0 正在执行 foo(0)
时刻 2: Thread 1 窃取 cont:i=1 →
Thread 1 queue: [ cont: i=2 ] Thread 1 正在执行 foo(1)
Thread 0 queue: [ 空 ] Thread 0 继续做自己的事
无窃取时执行顺序： foo(0), foo(1), ..., foo(N-1) ← 与删掉 spawn 的程序一致（深度优先）
空间上界：T 个线程的总队列存储 ≤ T × 单线程栈存储
- 注意一个容易误解的细节（讲义 slide 47/48 明确强调）：“子任务优先”的窃取调度器是为分治并行性设计的，而朴素的 spawn 循环并不能很快地把机器填满：把
for (i…) cilk_spawn foo(i);与递归对半拆分的写法相比，后者的代码才是”并行地产生工作”：每层递归都把整棵右半子树作为连续体入队，窃取者一次拿走的就是一整棵还能继续向下分裂的子树（工作块更大 → 窃取次数更少 → 每次窃取被更长的计算摊薄，并且偷来的子树可以继续分裂给更多线程），而朴素循环只沿调用链逐个产生”下一个迭代”级别的细碎可窃取项。讲义原文结论是：递归版本”能更快地把机器填满“。
递归产生工作（能快速填满机器） 朴素 spawn 循环（沿调用链逐个产生）
void recursive_for(int start,int end){ for (int i=0;i<N;i++) cilk_spawn foo(i);
while (start <= end - GRANULARITY){ cilk_sync;
int mid = (end-start)/2;
cilk_spawn recursive_for(start,mid); 调用链展开，每一步只多一个"下一个迭代"级别的
start = mid; 细碎可窃取项：foo(0)→foo(1)→foo(2)→…
} 可窃取工作沿调用链**线性地**逐个出现
for (int i=start;i<end;i++) foo(i);
}
先跑子任务 + 每层递归都把"右半子树"作为连续体入队：
第 1 层：队列里出现 (N/2, N) 这棵**子树**
第 2 层：出现 (N/4, N/2) 子树……
窃取者一次拿到的就是**一整棵可再分裂的子树**（块大 → 窃取次数少 → 成本被摊薄），
而且偷来的子树还能继续向下分裂给更多线程 → 迅速把机器填满
2.11 cilk_sync 是怎么实现的：sync descriptor 与贪婪汇合
- 定义与目的：
cilk_sync必须知道”本块里派生的调用是否都完成了“。Cilk 的实现方式是给每个”包含 spawn 的块”配一张描述符（descriptor），记录两个计数：- spawn 计数：这个块里已经派生出去的调用总数；
- done 计数：其中已经完成的个数。 当且仅当
spawn == done时，同步满足。
- 关键实现要点（CS149 slide 52–62/63）：
- 如果没有任何工作被别的线程偷走，那么
cilk_sync处无事可做——它是一个 no-op（线程自己按深度优先顺序把所有派生的调用都跑完了）； - 只有当发生了窃取，才需要”块描述符”记账：被偷走的连续体由窃取线程继续执行，它在该块里继续派生的新调用仍然登记到同一张描述符上（CS149 示例中
id=A块的 spawn 计数按 1 → 2 → 3 … 10 增长，对应foo(0)、foo(1)、…、foo(9)分别被不同线程接手，被偷走的任务在受害者队列里被标为STOLEN (id=A)）； - 每个被偷走的任务要标明它属于哪个块（
STOLEN (id=A)），完成后把 done 计数加一； - 最后一个完成的派生调用把
done推到与spawn相等（例如spawn: 10, done: 10），同步条件满足，此时当初发起 spawn 的那个线程可能并不是执行cilk_sync之后代码的线程——谁最后完成谁继续； - 完成之后 块描述符被释放（可以复用），继续执行
bar()。
- 如果没有任何工作被别的线程偷走，那么
- 贪婪汇合（greedy join scheduling）策略（CS149 slide 62/63）：
- 所有线程只要没事干就尝试窃取；
- 只有当系统里真的没有可窃取的工作时，线程才空闲（idle）；
- 发起 spawn 的 worker 未必是执行
cilk_sync之后逻辑的 worker； - 记住：记录窃取与管理同步点的开销只在发生窃取时出现；只要偷走的是大块工作，窃取就很稀有；绝大多数时间线程只是在本地 dequeue 上 push/pop。
- 直观解释（”它是什么？”）：descriptor 像团建活动的签到表：”这个街区派出去 10 个人，签到 10 个才算人齐”。没人被别的队伍借走时，签到表根本不用拿出来（no-op）；一旦有 3 个人被借走，就要靠”借出登记 + 归还登记”来数人头。人齐之后，谁最后一个回来就由谁宣布散会（不一定是队长）。
- 图解（图 9）：sync descriptor 状态机
描述符生命周期（block id = A，记录 spawn / done 两个计数）
+-------------+ 第一次发生窃取 +---------------------------+
| IDLE | -----------------> | ACTIVE |
| （无 spawn | "descriptor for | spawn=N, done=M (M < N) |
| 或已释放） | block A created" | 每被偷一个任务: spawn++ |
+-------------+ | 每完成一个任务: done++ |
^ +---------------------------+
| |
| | 某线程到达 cilk_sync，
| spawn == done | 检查：spawn == done ?
| ⇒ 释放描述符 v
| +--------------------------------+
| | spawn > done 时**不阻塞等待** |
| | greedy join：立刻去找别的活 |
| | （去偷 / 去执行其它任务） |
| +--------------------------------+
| |
+-------------+ | 最后一个完成者把 done 推到 N
| COMPLETE | <-------------------------------+
| done = N | ← 由"最后完成者"接手执行 sync 之后的代码
+-------------+ （未必是当初发起 spawn 的那个线程）
反例（务必避免）：把 cilk_sync 与"某个特定线程"绑定
（例如假设发起 spawn 的线程一定执行 sync 之后的代码）会死锁
无窃取路径（fast path）：IDLE --(没有任何窃取发生)--> IDLE
cilk_sync 是 no-op：线程自己已按深度优先把派生调用全跑完
- 性能特征：同步几乎零成本是这套设计的核心优点：开销只在窃取时产生，与”每次取工作都进入临界区”的共享队列方案（§2.4）形成鲜明对比。这也解释了为什么 fork-join 系统（Cilk、OpenMP task、TBB、ISPC task）能在极细粒度的递归分解上工作。
3. 代码示例与性能分析
下面四个示例都在同一台机器上实测过（AMD EPYC 7V13，128 个硬件执行上下文，2 socket × 64 核；除注明外均用 8 个执行上下文；共享机器，重复测量存在波动，§3.1 末尾专门讨论了这件事）。
3.1 示例 1：fork-join 并行快排（Cilk Plus 原版 + 可运行的 OpenMP 等价版）
(A) 讲义原版（Cilk Plus）
// 讲义 slide 29/48 的并行快排（Cilk Plus）
// 编译（历史/受支持的编译器）：g++ -fcilkplus -O3 -lcilkrts qsort.cilk.cpp -o qsort （GCC 5–7）
// icc -O3 qsort.cilk.cpp -o qsort （Intel 编译器）
// 说明：Cilk Plus 的 C/C++ 扩展自 GCC 8 起被移除；若工具链不支持，请使用下面的
// OpenMP task 版本，或使用基于 Clang 的开源后继 OpenCilk（-fopencilk）。
void quick_sort(int* begin, int* end) {
if (begin >= end - PARALLEL_CUTOFF)
std::sort(begin, end); // 串行省略（serial elision）
else {
int* middle = partition(begin, end); // 串行划分（关键路径所在）
cilk_spawn quick_sort(begin, middle); // fork：左半可以并行
quick_sort(middle + 1, end); // 当前线程继续做右半（连续体）
} // 函数末尾有隐式 cilk_sync
}
(B) 可运行的等价版本（OpenMP task，已实测）
// qsort_omp.cpp —— fork-join 并行快排（Cilk Plus 示例的可移植 OpenMP 等价实现）
// 编译（release）: g++ -O3 -fopenmp -std=c++17 qsort_omp.cpp -o qsort_omp
// 运行: OMP_NUM_THREADS=8 ./qsort_omp 20000000
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <omp.h>
#include <random>
#include <vector>
static const long PARALLEL_CUTOFF = 8192; // 小于该长度就串行排序（串行省略）
// Hoare 划分：返回切分点 p，保证 begin < p < end，且 [begin,p) 的元素 <= [p,end) 的元素
static int* hoare_partition(int* begin, int* end) {
int* mid = begin + (end - begin) / 2;
if (*mid < *begin) std::swap(*mid, *begin); // 三数取中
if (*(end - 1) < *begin) std::swap(*(end - 1), *begin);
if (*(end - 1) < *mid) std::swap(*(end - 1), *mid);
int pivot = *mid;
int* i = begin - 1;
int* j = end;
while (true) {
do { ++i; } while (*i < pivot);
do { --j; } while (*j > pivot);
if (i >= j) return j + 1; // 关键：切分点严格落在 (begin, end) 内
std::swap(*i, *j);
}
}
// 对应讲义的 cilk_spawn quick_sort(begin, middle); quick_sort(middle, last);
static void quick_sort(int* begin, int* end) {
const long n = end - begin;
if (n <= PARALLEL_CUTOFF) { // 串行省略：划分到足够小就交给 std::sort
std::sort(begin, end);
return;
}
int* mid = hoare_partition(begin, end);
#pragma omp task firstprivate(begin, mid) // 左半：交给 task 池，可被其它线程"窃取"
quick_sort(begin, mid);
quick_sort(mid, end); // 右半：当前线程立刻继续（连续体留在本地）
#pragma omp taskwait // 对应 cilk_sync：等待本 task 派生的所有子 task
}
static bool is_sorted(const int* a, long n) {
for (long i = 1; i < n; ++i)
if (a[i - 1] > a[i]) return false;
return true;
}
int main(int argc, char** argv) {
const long N = (argc > 1) ? atol(argv[1]) : 20000000L;
std::vector<int> a(N), ref;
auto t0 = std::chrono::steady_clock::now();
std::mt19937 rng(12345);
for (long i = 0; i < N; ++i) a[i] = (int)rng();
auto t1 = std::chrono::steady_clock::now();
const double gen_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
ref = a; // 串行基线
t0 = std::chrono::steady_clock::now();
std::sort(ref.begin(), ref.end());
t1 = std::chrono::steady_clock::now();
const double serial_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
t0 = std::chrono::steady_clock::now();
#pragma omp parallel
{
#pragma omp single nowait
quick_sort(a.data(), a.data() + N);
}
t1 = std::chrono::steady_clock::now();
const double par_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
std::printf("N=%ld threads=%d gen=%.1f ms T_serial(1 thread)=%.1f ms T_par(%d)=%.1f ms speedup=%.2fx sorted=%s\n",
N, omp_get_max_threads(), gen_ms, serial_ms, omp_get_max_threads(), par_ms,
serial_ms / par_ms, is_sorted(a.data(), N) ? "yes" : "NO");
return is_sorted(a.data(), N) ? 0 : 1;
}
实测（N = 20,000,000 个随机 int，PARALLEL_CUTOFF = 8192，一次代表性运行）：
| 线程数 P | 1（并行代码） | 1（std::sort 基线） | 2 | 4 | 8 |
|---|---|---|---|---|---|
| 时间 (ms) | 1620.5 | 1657.3 | 876.0 | 560.6 | 442.5 |
| 加速比 | 1.02x | 1.00x | 1.84x | 2.88x | 3.65x |
【代码做什么？】
main用固定种子的std::mt19937生成 N 个随机int；另存一份副本用std::sort串行排序作为基线，并记录时间。- 进入
#pragma omp parallel并行区，用#pragma omp single nowait让一个线程发起顶层quick_sort；递归内部派生出的 task 会由整个线程池执行。 quick_sort对长度 ≤ 8192 的区间直接调用std::sort（串行省略：派生开销超过潜在并行收益时不再派生）；否则先做 Hoare 划分（返回j+1，保证切分点严格位于区间内部，左右两半都非空，递归一定终止）。- 左半用
#pragma omp task提交为可延迟执行的任务（firstprivate按值捕获begin/mid），右半由当前线程直接递归——这就是”先跑一个、把另一半登记出去”的 fork-join 结构；#pragma omp taskwait对应cilk_sync，等待本任务派生的子任务全部完成。 - 排序结束后用
is_sorted校验正确性（并作为退出码），保证测量的是”正确的排序”。
【并行机制与性能解说】
- 硬件上如何并行：OpenMP 运行时在第一次 task 构造时初始化一个 worker 线程池，线程数 =
OMP_NUM_THREADS（这里 8，等于 8 个执行上下文）。每个 worker 有自己的任务队列；当一个 worker 在当前任务上遇到taskwait而子任务尚未完成、或自己的队列为空时，它会去别的 worker 的队列窃取（steal）任务。firstprivate(begin, mid)让两个指针作为任务私有数据被搬走——被窃取的是”一段区间的排序工作”这块粗粒度任务，而不是每元素级别的细活。 - Work（总工作量）：以”元素操作”计。若划分大致均衡，
W(n) = 2W(n/2) + Θ(n)，递推到串行省略阈值 C 之后叶子各自做Θ(C log C)：W = Θ(n log n)。取 n = 2×10⁷、C = 8192：内部各层划分工作量合计约n·log₂(n/C) ≈ 2×10⁷ × 11.2 ≈ 2.2×10⁸，叶子排序约(n/C)·C log C ≈ 2441 × 8192 × 13 ≈ 2.6×10⁸，所以 W ≈ 4.8×10⁸ 元素操作。 - Span（关键路径）：划分是串行的，关键路径沿”每次取一半”向下延伸：
D(n) = D(n/2) + Θ(n)，其中Θ(n)是划分成本，几何级数求和给出 D ≈ 2n ≈ 4.0×10⁷ 元素操作（叶子std::sort的 span 相对可忽略）。 - 并行度 = W / Span ≈ 4.8×10⁸ / 4.0×10⁷ ≈ 12。这是本讲最重要的一个数字：快排的并行度只有 Θ(log n) 量级。也就是说，即使有 128 个核，这个算法的加速比上限大约在 12 倍附近（对应”元素操作”粒度）；8 个核还没有触到这个天花板（8 < 12），所以效率损失不是并行度不足造成的，而是下面这些：
- 额外工作（extra work）：并行版本比串行
std::sort多做了log₂(n/C) ≈ 11层的划分。实测T_par(1) = 1620 ms与T_serial = 1657 ms几乎相等，说明这份多出来的工作与std::sort在小规模上的优势大致抵消——“并行代码在 1 线程下不比串行慢”是一个好的信号（如果慢很多，说明额外工作太多）。 - 负载不均的尾部：叶子任务的大小是 8192 个元素，最后几个叶子任务无法再切分，尾部必然有一段”不足 8 个线程在干活”的时间。任务数 =
n/C ≈ 2441，相对 8 个线程的 parallel slack ≈ 305，远大于讲义建议的 ~8，所以尾部只占很小一部分。 - 共享内存子系统的吞吐/延迟：4 → 8 线程只带来 1.27x（560.6 → 442.5 ms），这是典型的共享资源饱和特征（不是同步开销的特征——同步开销会随线程数线性恶化）。n = 2×10⁷ 个
int= 80 MB，完整一层划分至少要读写 ~160 MB 流量；log₂(n/C) ≈ 11层合计约 1.8 GB 流量；在 442 ms 内跑完相当于 ~4 GB/s 的有效流量。这个数字本身远低于现代服务器的 DRAM 带宽，但 Hoare 划分是带分支、低 MLP（memory-level parallelism）的指针追赶式扫描（i/j两个游标、每步一次不可预测的分支），真正的限制是延迟与访存并行度，而非带宽。可用三个实验验证这个诊断：(i) 把PARALLEL_CUTOFF调大以减少划分层数；(ii) 把 N 缩小到能装进 LLC，看加速比是否改善；(iii) 用perf stat看 LLC-miss 与跨 socket 访存比例。
- 额外工作（extra work）：并行版本比串行
- 测量纪律：这台机器是共享的。同一份代码重复运行时，8 线程的实测加速比在 2.6x–3.7x 之间波动（负载高时串行基线本身也从 1657 ms 涨到 2000 ms 以上）。这正是讲义 TIP #1 的实践含义：先测量，并记录测量条件；报告”我的方案可扩展”时必须带上机器状态与规模。
3.2 示例 2：共享计数器 + chunk —— 动态分配的粒度旋钮
// chunked_counter.cpp —— 动态工作分配：共享计数器 + chunk（任务粒度粗化）
// 编译（release）: g++ -O3 -pthread -std=c++17 chunked_counter.cpp -o chunked_counter
// 运行: ./chunked_counter
#include <atomic>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <mutex>
#include <thread>
#include <vector>
static int g_threads = 8; // 8 个执行上下文（可改）
// 一件"工作"：对种子做 iters 次乘加（纯计算，成本可控）
static inline uint64_t busy(uint64_t seed, int iters) {
uint64_t acc = seed | 1;
for (int i = 0; i < iters; ++i) {
acc = acc * 6364136223846793005ULL + 1442695040888963407ULL;
acc ^= acc >> 29;
}
return acc;
}
struct Result { double ms, max_work, avg_work; long min_tasks, max_tasks; };
// 所有线程反复用"领号"的方式从共享计数器取 chunk 件工作
static Result run(const std::vector<int>& cost, int chunk, bool use_mutex) {
const long M = (long)cost.size();
std::atomic<long> counter{0};
std::atomic<long> next_locked{0};
std::mutex mtx;
std::atomic<uint64_t> sink{0};
std::vector<double> work(g_threads, 0.0);
std::vector<long> tasks(g_threads, 0);
std::atomic<int> ready{0};
std::atomic<bool> go{false};
auto worker = [&](int tid) {
ready.fetch_add(1, std::memory_order_release);
while (!go.load(std::memory_order_acquire)) { /* 起跑线自旋 */ }
while (true) {
long i;
if (use_mutex) { // 讲义里的 lock(counter_lock) ... unlock(counter_lock)
mtx.lock(); i = next_locked.load(); next_locked.store(i + chunk); mtx.unlock();
} else { // 等价但更便宜的原子取号（atomic fetch-add）
i = counter.fetch_add(chunk, std::memory_order_relaxed);
}
if (i >= M) break;
const long end = (i + chunk < M) ? i + chunk : M;
uint64_t acc = 0;
for (long j = i; j < end; ++j) { acc += busy((uint64_t)j, cost[j]); work[tid] += cost[j]; }
sink.fetch_xor(acc, std::memory_order_relaxed);
tasks[tid] += (end - i);
}
};
std::vector<std::thread> th;
for (int t = 0; t < g_threads; ++t) th.emplace_back(worker, t);
while (ready.load(std::memory_order_acquire) != g_threads) { /* 等所有线程就位 */ }
auto t0 = std::chrono::steady_clock::now(); // 计时不含线程创建
go.store(true, std::memory_order_release);
for (auto& x : th) x.join();
auto t1 = std::chrono::steady_clock::now();
Result r{};
double sum = 0, mx = 0; long tmin = M, tmax = 0;
for (int t = 0; t < g_threads; ++t) {
sum += work[t]; if (work[t] > mx) mx = work[t];
if (tasks[t] < tmin) tmin = tasks[t];
if (tasks[t] > tmax) tmax = tasks[t];
}
r.ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
r.avg_work = sum / g_threads; r.max_work = mx;
r.min_tasks = tmin; r.max_tasks = tmax;
(void)sink.load();
return r;
}
int main() {
struct Regime { const char* name; long M; int lo, hi; };
const Regime regimes[2] = {
{"LIGHT", 200000, 4, 32}, // 每件工作 4~32 次迭代：同步开销会被放大
{"HEAVY", 2048, 5000, 40000}, // 每件工作 5000~40000 次迭代：粒度粗化会暴露负载不均
};
for (const Regime& R : regimes) {
std::vector<int> cost(R.M);
for (long i = 0; i < R.M; ++i) { // 成本不可预测：最大/最小相差 8 倍
int spread = (int)((i * 2654435761u) % 4);
cost[i] = (R.lo << spread) < R.hi ? (R.lo << spread) : R.hi;
}
std::printf("\n===== %s workload: %ld tasks, cost %d~%d iters, %d threads =====\n",
R.name, R.M, R.lo, R.hi, g_threads);
std::printf("%8s | %11s %11s | %14s | %13s | %9s\n",
"chunk", "T_atomic/ms", "T_mutex/ms", "max_work/avg_work", "tasks min/max", "T vs chunk=1");
auto best = [&](int chunk, bool use_mutex) { // 取 3 次最小值，抑制共享机器的噪声
Result b = run(cost, chunk, use_mutex);
for (int k = 0; k < 2; ++k) { Result r = run(cost, chunk, use_mutex); if (r.ms < b.ms) b = r; }
return b;
};
Result base = best(1, false);
for (int chunk : {1, 4, 16, 64, 256, 1024, 2048, 4096, 16384, 65536}) {
if (chunk > R.M) break;
Result ra = best(chunk, false);
Result rm = best(chunk, true);
std::printf("%8d | %11.3f %11.3f | %14.3f | %6ld/%-6ld | %8.2fx\n",
chunk, ra.ms, rm.ms, ra.max_work / ra.avg_work,
ra.min_tasks, ra.max_tasks, base.ms / ra.ms);
}
}
return 0;
}
实测（8 线程，每个配置取 3 次最小值）：
表 2：LIGHT 负载（200,000 件工作，每件 4/8/16/32 次迭代，8 线程）
| chunk | 原子取号 (ms) | 互斥锁 (ms) | max_work/avg_work | 任务数 min/max | 相对 chunk=1 |
|---|---|---|---|---|---|
| 1 | 99.519 | 44.583 | 2.740 | 14865 / 68743 | 0.82x |
| 4 | 18.436 | 24.950 | 1.122 | 23824 / 28044 | 4.44x |
| 16 | 4.808 | 10.378 | 1.129 | 23776 / 28224 | 17.03x |
| 64 | 0.990 | 3.045 | 1.103 | 22528 / 27584 | 82.75x |
| 256 | 0.619 | 0.645 | 1.014 | 24064 / 25344 | 132.31x |
| 1024 | 0.573 | 0.597 | 1.024 | 24576 / 25600 | 142.87x |
| 2048 | 0.577 | 0.598 | 1.065 | 24576 / 26624 | 141.86x |
| 4096 | 0.603 | 0.600 | 1.119 | 24576 / 27968 | 135.72x |
| 16384 | 0.693 | 0.696 | 1.311 | 16384 / 32768 | 118.12x |
| 65536 | 1.383 | 1.337 | 2.621 | 0 / 65536 | 59.21x |
表 3：HEAVY 负载（2,048 件工作，每件 5000/10000/20000/40000 次迭代，8 线程）
| chunk | 原子取号 (ms) | 互斥锁 (ms) | max_work/avg_work | 任务数 min/max | 相对 chunk=1 |
|---|---|---|---|---|---|
| 1 | 9.555 | 9.522 | 1.007 | 252 / 262 | 1.00x |
| 4 | 9.480 | 9.504 | 1.000 | 256 / 256 | 1.00x |
| 16 | 9.470 | 9.482 | 1.000 | 256 / 256 | 1.00x |
| 64 | 9.471 | 9.500 | 1.000 | 256 / 256 | 1.00x |
| 256 | 9.497 | 9.477 | 1.000 | 256 / 256 | 1.00x |
| 1024 | 37.526 | 37.497 | 4.000 | 0 / 1024 | 0.25x |
| 2048 | 74.890 | 74.883 | 8.000 | 0 / 2048 | 0.13x |
【代码做什么？】
- 两种负载各做一轮实验：LIGHT（200,000 件工作、每件 4–32 次乘加迭代）与 HEAVY（2,048 件工作、每件 5,000–40,000 次迭代）。每件工作的成本按
(i × 大奇数) % 4取值，成本相差 8 倍且不可预测——正是动态分配要处理的场景。 run()启动 8 个 worker 线程；线程创建完成后由主线程在起跑线上放开（go）并开始计时，因此计时不含线程创建开销（这是让 LIGHT 负载的微小工作时间可被观测的关键）。- 每个 worker 反复”领活”：用
chunk件为一单位向共享计数器取号；取号有两种实现——互斥锁（讲义里的lock/unlock写法）与原子fetch_add（等价且更便宜）。取到i >= M时退出循环。 - 每个 worker 分别累计自己完成的工作量与件数，
run()汇总出max_work/avg_work（负载不均指标）、每线程件数 min/max（动态分配是否真的把活摊开了）与总时间。 - 每个配置跑 3 次取最小值（抑制共享机器的噪声），并在两张表里扫过 chunk = 1 … 65536，把”粒度”这个旋钮的整个曲线打出来。
【并行机制与性能解说】
- 硬件上如何并行：8 个 worker 线程（8 个执行上下文）各自计算，唯一的共享可写数据是那个 8 字节计数器所在的缓存行。
fetch_add是一条原子读-改-写（RMW）指令：执行时该缓存行必须处于该核的 Exclusive/Modified 状态，于是同一行在 8 个核（甚至两个 socket）之间来回迁移，每次迁移都要走相干性协议（跨 socket 时约 0.3–0.5 µs）。临界区里的那几行代码，就是”串行程序里不存在的额外工作”，而且它本身就是串行执行（Amdahl）。 - Work 与 Span：设成本数组之和为
W_task = Σ cost[i]（单位：迭代次数），取号次数为M/chunk。总工作量 = W_task + (M/chunk)·c_sync，其中c_sync是”全局串行化意义下”的一次取号成本。关键路径（Span）包含两部分：最长单件工作的成本，以及被串行化的取号链——(M/chunk)·c_sync。当(M/chunk)·c_sync与并行部分W_task/P同量级时，程序就变成”取号驱动”的。 - 为什么 chunk=1 会输得这么惨（LIGHT）：200,000 次取号，实测耗时 99.5 ms。用全局串行化成本反推：
c_sync ≈ (99.5 ms − 0.573 ms) / 200,000 ≈ 494 ns/次。也就是说，在这种饱和争用下，一次原子取号等价于把整个程序串行推进 0.5 µs；200,000 次就是 100 ms，与实测几乎完全一致。这不是”开销百分比”问题，而是”程序被彻底串行化”的问题：此时运行时间 = Span，Amdahl 的 S≈1。 - 为什么 HEAVY 下 chunk=1 却没问题：同样 chunk=1，HEAVY 只有 2,048 次取号，若每次 500 ns 也只有 ~1 ms，而总工作是 9.5 ms，并且取号与计算重叠（线程取完号就去算 28 µs，计数器有足够时间”冷静”下来，单次成本回落到 ~50–100 ns）。实测 chunk=1 与 chunk=256 的差异 < 1%。结论：同步开销不是常数，而是争用强度的函数——这正是”必须测量”的最好例证。
- 为什么 HEAVY 下 chunk 太大会输（表 3 最后两行）：
chunk=1024时整个问题只剩 2 件工作分给 8 个线程，max_work/avg_work = 4.0（有 6 个线程完全没活干，tasks min/max = 0/1024）；chunk=2048只剩 1 件工作，退化为串行，max_work/avg_work = 8.0，时间 ×7.9。这就是讲义”very large tasks can lead to load balancing issues”的量化形态。 - 可扩展性上限：这条曲线的最优区间（LIGHT：256–4096；HEAVY：1–256）由两个约束夹出来，见 §4.4 的公式与推导。任务数相对处理器的 slack（冗余度）才是可扩展性的真正来源：只有
M/chunk ≫ 8P，动态分配才能吸收成本波动。
3.3 示例 3：Chase-Lev 工作窃取双端队列 + 迷你 Cilk 运行时
// ws_deque.cpp —— 迷你 Cilk：Chase-Lev 工作窃取双端队列 + 并行快排
// 编译（release）: g++ -O3 -pthread -std=c++17 ws_deque.cpp -o ws_deque
// 运行: ./ws_deque 20000000 8
#include <algorithm>
#include <atomic>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <random>
#include <thread>
#include <vector>
// ---------------------------------------------------------------------------
// 1) Chase-Lev 工作窃取双端队列：本地线程在 tail(bottom) 端 push/pop，
// 窃取线程在 head(top) 端 steal。8 字节的 T 在 x86-64 上天然无锁。
// ---------------------------------------------------------------------------
struct Range { uint32_t lo, hi; }; // 一件工作 = 一个待排序区间
static_assert(std::atomic<Range>::is_always_lock_free, "Range must be lock-free");
template <typename T>
class ChaseLevDeque {
public:
explicit ChaseLevDeque(size_t log_cap = 10) : top_(0), bottom_(0) {
array_.store(new CircularArray(log_cap), std::memory_order_relaxed);
}
~ChaseLevDeque() { delete array_.load(); for (auto* a : retired_) delete a; }
// 仅由 owner 线程调用：向 tail 端压入
void push(T v) {
size_t b = bottom_.load(std::memory_order_relaxed);
size_t t = top_.load(std::memory_order_acquire);
CircularArray* a = array_.load(std::memory_order_relaxed);
if (b - t > a->capacity() - 1) { // 队列满：扩容
a = a->grow(t, b);
array_.store(a, std::memory_order_release);
}
a->store(b, v);
std::atomic_thread_fence(std::memory_order_release);
bottom_.store(b + 1, std::memory_order_relaxed);
}
// 仅由 owner 线程调用：从 tail 端弹出（LIFO，保局部性）
bool pop(T& out) {
size_t b = bottom_.load(std::memory_order_relaxed);
if (b == 0) return false; // 空
CircularArray* a = array_.load(std::memory_order_relaxed);
b -= 1;
bottom_.store(b, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
size_t t = top_.load(std::memory_order_relaxed);
if (t <= b) {
out = a->load(b);
if (t == b) { // 只剩一个：必须与窃取者竞争
if (!top_.compare_exchange_strong(t, t + 1, std::memory_order_seq_cst,
std::memory_order_relaxed)) {
bottom_.store(b + 1, std::memory_order_relaxed);
return false; // 被别人偷走了
}
bottom_.store(b + 1, std::memory_order_relaxed);
}
return true;
}
bottom_.store(b + 1, std::memory_order_relaxed);
return false;
}
// 由任意线程调用（窃取者）：从 head 端取走一件工作
bool steal(T& out) {
size_t t = top_.load(std::memory_order_acquire);
std::atomic_thread_fence(std::memory_order_seq_cst);
size_t b = bottom_.load(std::memory_order_acquire);
if (t < b) {
CircularArray* a = array_.load(std::memory_order_relaxed);
out = a->load(t);
if (!top_.compare_exchange_strong(t, t + 1, std::memory_order_seq_cst,
std::memory_order_relaxed))
return false; // 竞争失败：本次窃取放弃
return true;
}
return false;
}
private:
struct CircularArray { // 大小为 2 的幂，环形索引
size_t cap, mask, log_cap;
std::unique_ptr<std::atomic<T>[]> buf;
explicit CircularArray(size_t lc)
: cap(size_t(1) << lc), mask(cap - 1), log_cap(lc),
buf(new std::atomic<T>[cap]) {}
size_t capacity() const { return cap; }
T load(size_t i) const { return buf[i & mask].load(std::memory_order_relaxed); }
void store(size_t i, T v) { buf[i & mask].store(v, std::memory_order_relaxed); }
CircularArray* grow(size_t t, size_t b) const {
auto* na = new CircularArray(log_cap + 1);
for (size_t i = t; i < b; ++i) na->store(i, load(i));
return na;
}
};
alignas(64) std::atomic<size_t> top_; // 窃取端（head）
alignas(64) std::atomic<size_t> bottom_; // 本地端（tail）
std::atomic<CircularArray*> array_;
std::vector<CircularArray*> retired_; // 旧数组延迟回收（此处只到退出时才释放）
};
// ---------------------------------------------------------------------------
// 2) 迷你运行时：每线程一个 deque + 全局未完成任务计数（用于判定终止）
// ---------------------------------------------------------------------------
static int* g_base = nullptr; // 待排序数组基址
static long g_N = 0;
static const long CUTOFF = 8192; // 串行省略阈值
static std::vector<std::unique_ptr<ChaseLevDeque<Range>>> g_deques;
static std::atomic<long> g_unfinished{0}; // 排队中 + 正在执行的任务数
static std::atomic<long> g_steal_attempts{0}, g_steal_success{0}, g_tasks_run{0};
static int* hoare_partition(int* begin, int* end) {
int* mid = begin + (end - begin) / 2;
if (*mid < *begin) std::swap(*mid, *begin);
if (*(end - 1) < *begin) std::swap(*(end - 1), *begin);
if (*(end - 1) < *mid) std::swap(*(end - 1), *mid);
const int pivot = *mid;
int* i = begin - 1; int* j = end;
while (true) {
do { ++i; } while (*i < pivot);
do { --j; } while (*j > pivot);
if (i >= j) return j + 1;
std::swap(*i, *j);
}
}
// 执行一件工作：左半就地继续（continuation 留在本地），右半作为新任务压入本地队列
static void run_task(Range r, int tid) {
int* begin = g_base + r.lo;
int* end = g_base + r.hi;
if (end - begin <= CUTOFF) { std::sort(begin, end); return; }
int* mid = hoare_partition(begin, end);
Range right{(uint32_t)(mid - g_base), r.hi};
g_unfinished.fetch_add(1, std::memory_order_relaxed); // 新任务入账
g_deques[tid]->push(right); // 可被其它线程 STEAL
run_task(Range{r.lo, (uint32_t)(mid - g_base)}, tid); // 派生的"子"先跑
}
static void worker(int tid) {
Range r{};
while (true) {
if (g_deques[tid]->pop(r)) { // 1) 先看自己的队列
run_task(r, tid); g_tasks_run.fetch_add(1, std::memory_order_relaxed);
g_unfinished.fetch_sub(1, std::memory_order_relaxed);
continue;
}
const int T = (int)g_deques.size();
bool got = false;
for (int k = 1; k < T && !got; ++k) { // 2) 随机挑受害者去窃取
int victim = (tid + 1 + (int)((unsigned)(tid * 7919 + k * 104729) % (T - 1))) % T;
if (victim == tid) continue;
g_steal_attempts.fetch_add(1, std::memory_order_relaxed);
if (g_deques[victim]->steal(r)) {
g_steal_success.fetch_add(1, std::memory_order_relaxed);
run_task(r, tid); g_tasks_run.fetch_add(1, std::memory_order_relaxed);
g_unfinished.fetch_sub(1, std::memory_order_relaxed);
got = true;
}
}
if (got) continue;
if (g_unfinished.load(std::memory_order_acquire) == 0) break; // 3) 全局无任务：退出
std::this_thread::yield(); // 已有任务在途，稍后重试
}
}
static bool is_sorted(const int* a, long n) {
for (long i = 1; i < n; ++i) if (a[i - 1] > a[i]) return false;
return true;
}
int main(int argc, char** argv) {
g_N = (argc > 1) ? atol(argv[1]) : 20000000L;
const int T = (argc > 2) ? atoi(argv[2]) : 8;
std::vector<int> a(g_N), ref;
std::mt19937 rng(2024);
for (long i = 0; i < g_N; ++i) a[i] = (int)rng();
ref = a;
auto t0 = std::chrono::steady_clock::now();
std::sort(ref.begin(), ref.end());
auto t1 = std::chrono::steady_clock::now();
const double serial_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
g_base = a.data();
for (int t = 0; t < T; ++t) g_deques.emplace_back(new ChaseLevDeque<Range>(10));
g_unfinished.store(1, std::memory_order_relaxed); // 根任务
g_deques[0]->push(Range{0, (uint32_t)g_N});
std::atomic<int> ready{0}; std::atomic<bool> go{false};
std::vector<std::thread> th;
for (int t = 0; t < T; ++t)
th.emplace_back([&, t] {
ready.fetch_add(1, std::memory_order_release);
while (!go.load(std::memory_order_acquire)) {}
worker(t);
});
while (ready.load(std::memory_order_acquire) != T) {}
t0 = std::chrono::steady_clock::now();
go.store(true, std::memory_order_release);
for (auto& x : th) x.join();
t1 = std::chrono::steady_clock::now();
const double par_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
std::printf("N=%ld T=%d serial=%.1f ms work-stealing=%.1f ms speedup=%.2fx sorted=%s\n",
g_N, T, serial_ms, par_ms, serial_ms / par_ms, is_sorted(a.data(), g_N) ? "yes" : "NO");
std::printf(" tasks run=%ld steals attempted=%ld succeeded=%ld (成功率 %.1f%%)\n",
g_tasks_run.load(), g_steal_attempts.load(), g_steal_success.load(),
100.0 * (double)g_steal_success.load() / (double)(g_steal_attempts.load() ? g_steal_attempts.load() : 1));
return is_sorted(a.data(), g_N) ? 0 : 1;
}
实测（N = 3,000,000，CUTOFF = 8192，每个配置取 5 次最小值；所有运行都通过了 is_sorted 校验）：
| 线程数 T | 1 | 2 | 4 | 8 |
|---|---|---|---|---|
| 时间 (ms) | 216.2 | 113.2 | 62.6 | 38.2 |
| 相对 1 线程 | 1.00x | 1.91x | 3.45x | 5.66x |
| 8 线程下的窃取统计 | — | — | — | 执行任务 645 件；窃取尝试 ~336,000 次；成功 ~150 次（成功率 0.04%） |
【代码做什么？】
- Chase-Lev dequeue（
ChaseLevDeque<T>）：一个”双端队列”，owner 在bottom（tail）端push/pop（LIFO，取最近压入的任务 → 深度优先 → 局部性好），窃取者在top（head）端steal（FIFO，取最早压入的任务 → 标的是调用树里更大的一块）。缓冲区是一个大小为 2 的幂的环形数组，用top/bottom两个size_t索引，索引按位与（i & mask）取模；队列满时grow()申请翻倍的数组并把[top, bottom)的元素搬过去（旧数组不立即释放，因为可能还有窃取者正在读它——这是工作窃取里经典的”内存回收”难题）。 - 消除伪共享：
top_与bottom_都用alignas(64)对齐——owner 高频写bottom_，窃取者高频读top_，若两者在同一缓存行就会互相失效（下一讲会专门讲这个坑）。 - 迷你运行时：每线程一个 dequeue；
g_unfinished统计”排队中 + 正在执行”的任务总数，是终止检测的依据；worker 主循环三步走：先 pop 本地 → 本地空则随机挑受害者 steal → 都没有且全局无在途任务则退出，否则yield()后重试。 - 任务拆分体现”先跑子任务”（continuation stealing 的等价写法）：
run_task对区间做 Hoare 划分，把右半压入本线程的 dequeue（它就是”可被偷的连续体”），然后就地递归左半（”子任务先跑”）；小于CUTOFF时直接std::sort。 - 计数不变式：根任务使
g_unfinished = 1；每压入一件新任务+1，每完成一件任务−1（出队与窃取都不改变计数，因为任务只是从”排队”变成”执行”）。因此g_unfinished == 0当且仅当所有任务（含正在执行的）都已完成，worker 可以安全退出。 main用一个起跑线（ready/go）让所有 worker 同时开始，并在计时区间之外完成std::sort串行基线、数组初始化与线程创建；结束时校验有序性。
【并行机制与性能解说】
- 硬件上如何并行：T 个 worker 线程各自绑定一个 dequeue（每个 dequeue 的头部/尾部各占一条缓存行）。绝大多数操作是 owner 对自己 dequeue 尾部的普通 load/store——
push走的是 relaxed store + release fence，pop只剩一次可能的 CAS 比较；没有原子 RMW、没有锁。只有当某个 worker 空手时才发起steal：一次 acquire load + 一次compare_exchange，并伴随缓存行所有权从受害者到窃取者的迁移。 - Work / Span / 并行度：与 §3.1 的快排完全同构。取 n = 3×10⁶、C = 8192：划分层数
log₂(n/C) ≈ 8.5，划分工作量 ≈3×10⁶ × 8.5 ≈ 2.6×10⁷；叶子排序工作量 ≈(n/C)·C·log₂C ≈ 366 × 8192 × 13 ≈ 3.9×10⁷，所以 W ≈ 6.4×10⁷ 元素操作。Span D ≈ 2n ≈ 6×10⁶ 元素操作（沿”每次取一半”的划分链求和）。并行度 W/D ≈ 11：8 个线程已经逼近这个上限，因此 5.66x（效率 71%）已是相当好的结果，而不是”调度没做好”。任务总数 = 内部节点 + 叶子 ≈ 365 + 366 ≈ 731（实测同一量级：645 件任务被执行），所以 parallel slack = 645/8 ≈ 80，远大于讲义建议的 ~8，负载均衡不是瓶颈。这也是为什么 8 线程能拿到 5.66x：任务足够粗（叶子是 8192 个元素的排序，约 100 µs 量级），而调度开销只在 150 次成功窃取里付出。 - 窃取成本被摊薄（讲义的核心论断在这里被量化）：150 次成功窃取 × ~1 µs ≈ 0.15 ms，相对 38.2 ms 的运行时间只有 0.4%——”只要偷走的是大块工作，窃取就很稀有”得到验证。对比一下：如果叶子任务不是 8192 个元素而是 1 个元素（成本 ~2 ns），那么每次窃取的 1 µs 开销相当于 500 倍的窃取/计算比，整个系统会被窃取路径压垮。这就是”任务粒度不能太细”在窃取式调度器里的具体形态。
- 本实现写得很”贪”的窃取路径暴露了另一个成本：
worker在没活干时会对全部 T−1 个受害者各试一次，然后yield()再重试——实测 336,000 次窃取尝试只换来 150 次成功（成功率 0.04%）。每次尝试至少两条原子 load + 一次 CAS 尝试 + 一次 fence，粗估 336,000 × ~50 ns ≈ 17 ms 的 CPU 时间（摊到 8 个线程约 2 ms，占 38 ms 的 ~5%），而且这些访问在受害者 dequeue 的头部缓存行上，会干扰受害者的本地操作。生产级调度器（Cilk、TBB）对此的处理是指数退避 + 随机化 + 适时睡眠；这解释了 CS149 讲到的”greedy join”必须配一个高效的窃取路径，而不是无脑自旋。 - 终止检测不是免费的：本示例用”全局未完成任务计数 + 自旋/让出”实现终止检测，这是讲义列出的四个实现挑战之一（”如何检测程序终止？”）。真实系统（Cilk 的 join counter + 全局空闲位、Java ForkJoinPool 的
quiescence检测）都要处理”某个线程暂时没活但系统里还有活”与”真的全干完了”的区分。
3.4 示例 4：调度策略的确定性仿真（长任务优先 vs 粒度）
// sched_sim.cpp —— 调度策略仿真：任务顺序 / 静态分配 / 粒度 对 makespan 的影响
// 编译: g++ -O2 -std=c++17 sched_sim.cpp -o sched_sim
// 运行: ./sched_sim
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <queue>
#include <vector>
struct Row { double makespan, ideal, imbalance, serial_frac, amdahl_bound; };
// 动态分配：P 个工人，从共享队列按给定顺序取活（谁的活干完谁再取）
static Row simulate_queue(const std::vector<int>& order, int P) {
std::priority_queue<double, std::vector<double>, std::greater<double>> free_at;
for (int i = 0; i < P; ++i) free_at.push(0.0);
for (int c : order) { double t = free_at.top(); free_at.pop(); free_at.push(t + c); }
double makespan = 0, total = 0;
for (int i = 0; i < P; ++i) { makespan = std::max(makespan, free_at.top()); free_at.pop(); }
for (int c : order) total += c;
Row r;
r.makespan = makespan;
r.ideal = total / P;
r.imbalance = makespan / r.ideal;
r.serial_frac = (makespan - r.ideal) / makespan; // 尾部"slop"占运行时间的比例
r.amdahl_bound = 1.0 / (r.serial_frac + (1.0 - r.serial_frac) / P);
return r;
}
// 静态分配：第 i 个工人拿 order[i], order[i+P], ...（blocked）
static Row simulate_static(const std::vector<int>& order, int P) {
std::vector<double> load(P, 0.0);
for (size_t i = 0; i < order.size(); ++i) load[i % P] += order[i];
double makespan = *std::max_element(load.begin(), load.end());
double total = std::accumulate(load.begin(), load.end(), 0.0);
Row r;
r.makespan = makespan; r.ideal = total / P; r.imbalance = makespan / r.ideal;
r.serial_frac = (makespan - r.ideal) / makespan;
r.amdahl_bound = 1.0 / (r.serial_frac + (1.0 - r.serial_frac) / P);
return r;
}
static void report(const char* name, const Row& r, int P) {
std::printf("%-34s | %8.1f | %8.1f | %8.3f | %9.3f | %8.2fx\n",
name, r.makespan, r.ideal, r.imbalance, r.serial_frac, r.amdahl_bound);
}
int main() {
const int P = 4; // 4 个执行上下文
// 16 件工作，成本不可预测：有一根"长杆"（60），另有一件中等（24），其余为 8
std::vector<int> cost = {8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 24, 60};
std::vector<int> as_given = cost; // 长杆排最后
std::vector<int> lpt = cost;
std::sort(lpt.begin(), lpt.end(), std::greater<int>()); // 长任务优先 (LPT)
std::vector<int> chunked; // 粗化粒度：拆成半尺寸任务
for (int c : cost) { chunked.push_back(c / 2); chunked.push_back(c - c / 2); }
std::vector<int> long_first_chunked = chunked;
std::sort(long_first_chunked.begin(), long_first_chunked.end(), std::greater<int>());
std::printf("P=%d, 16 tasks, total work = %d, ideal makespan = %.1f\n\n",
P, std::accumulate(cost.begin(), cost.end(), 0),
std::accumulate(cost.begin(), cost.end(), 0) / (double)P);
std::printf("%-34s | %8s | %8s | %8s | %9s | %8s\n",
"scheduling policy", "makespan", "ideal", "max/avg", "serial S", "Amdahl");
std::printf("-----------------------------------+----------+----------+----------+-----------+---------\n");
report("static blocked, long task last", simulate_static(as_given, P), P);
report("dynamic queue, long task last", simulate_queue(as_given, P), P);
report("dynamic queue, long task first (LPT)", simulate_queue(lpt, P), P);
report("dynamic queue, halves, long last", simulate_queue(chunked, P), P);
report("dynamic queue, halves, long first", simulate_queue(long_first_chunked, P), P);
return 0;
}
实测输出（确定性，无噪声）：
表 4：同一组 16 件工作在 4 个执行上下文下的 makespan（理想 49.0）
| 调度策略 | makespan | 理想值 | max/平均 | 串行段 S | Amdahl 上限 |
|---|---|---|---|---|---|
| 静态 blocked，长任务最后 | 84.0 | 49.0 | 1.714 | 0.417 | 1.78x |
| 动态队列，长任务最后 | 84.0 | 49.0 | 1.714 | 0.417 | 1.78x |
| 动态队列，长任务优先（LPT） | 60.0 | 49.0 | 1.224 | 0.183 | 2.58x |
| 动态队列，对半拆分，长任务最后 | 58.0 | 49.0 | 1.184 | 0.155 | 2.73x |
| 动态队列，对半拆分，长任务优先 | 50.0 | 49.0 | 1.020 | 0.020 | 3.77x |
【代码做什么？】
simulate_queue用一个小顶堆模拟动态分配：堆里是 P 个工人的”下次空闲时刻”，每来一件工作就把它交给最早空闲的工人（这正是”谁的活干完谁再取”的等价模型），最后取所有工人完成时刻的最大值作为 makespan。simulate_static模拟静态 blocked 分配：第 i 个工人固定拿第 i、i+P、i+2P… 件工作，各人的负载直接求和。- 两者都输出理想时间（总工作 / P）、失衡比 makespan/ideal、折算出的串行段 S = (makespan − ideal)/makespan，以及 Amdahl 加速比上限 1/(S + (1−S)/P)。
main对同一组成本构造五种调度方案：按输入顺序（长杆最后）、LPT（长任务优先）、把每件工作对半拆分、拆分后再 LPT——从而把”排序“与”拆细“两个手段的影响分离开。
【并行机制与性能解说】
- Work / Span / 并行度：总工作量
W = 196，关键路径由最长的任务链决定（这里是”长杆”60 加上它前面必须串行的部分）。并行度 = W / Span：长杆最后且必须串行时 span 至少包含 60 单位，W/Span ≈ 196/84 ≈ 2.3——并行度只有 2.3，却有 4 个核，多出来的核只能空转，这就是 makespan 84 的来源。LPT 并不改变 W，但它让长杆尽早开始，使 span 不再”叠加在尾部”；对半拆分则同时降低 span（60 → 30）并提高 W（196 → 196，这里恰好不变；真实系统里拆分通常会增加管理开销）。 - “动态分配 ≠ 负载均衡”：表 4 前两行完全相同（84 对 84）。动态分配只是”有空就取活”，它并不理解任务的长短；当长杆排在最后时，动态与静态一样无能为力。这是讲义把”更聪明的调度”单列一节的原因。
- 瓶颈是 Span，不是 Work：最优方案（拆分 + LPT）的 makespan 50 已经贴着理想值 49（效率 98%），此时再优化调度策略的收益趋近于零——剩下的 1 个单位就是”16 件工作无法被 4 整除”的颗粒度残差。反过来说，当 imbalance ≈ 1.0 时继续调调度器是浪费精力，应该去优化局部性或减少额外工作（下一讲的主题）。
4. 性能模型与复杂度分析
4.1 Work-Span 模型与贪心调度界（本讲分析工具的基础）
- 定义：把并行计算看成一张 DAG。
- Work（W，总工作量）：所有节点的工作量之和 = 单个处理器串行执行的时间
T₁； - Span（S，关键路径长度）：DAG 中最长依赖路径的工作量 = 无限多处理器下的执行时间
T∞； - 并行度（Parallelism）= W / S：机器再快也无法突破的平均并行上限。
- Work（W，总工作量）：所有节点的工作量之和 = 单个处理器串行执行的时间
- 两个必须记住的界（Graham / Brent）：
- 任何调度器都有
T_P ≥ max(W/P, S)； - 贪婪调度器（greedy scheduler，只要有可运行任务就绝不空闲）满足
T_P ≤ W/P + S。 第二个不等式是”贪婪”类调度器的性能保证：这正是 Cilk 的 greedy join scheduling 与工作窃取的价值所在——它把”调度质量”问题变成了”任务粒度/额外工作”问题。
- 任何调度器都有
- 对具体算法的应用：分治算法
W(n) = a·W(n/b) + Θ(n^d)，S(n) = S(n/b) + Θ(n^d)：
| 算法 | Work W | Span S | 并行度 W/S | 结论 |
|---|---|---|---|---|
| 并行快排（本次实现） | Θ(n log n) | Θ(n) | Θ(log n) | 并行度只有对数级，是”核多了也快不了”的根源 |
| 并行归约（树形） | Θ(n) | Θ(log n) | Θ(n/log n) | 极好的并行度，但每级同步/带宽受限 |
| 并行矩阵乘（分块） | Θ(n³) | Θ(n) | Θ(n²) | 并行度极高（第 6 讲） |
| 并行扫描（scan） | Θ(n) | Θ(log n) | Θ(n/log n) | 但 Work 常数大（Blelloch） |
4.2 数值算例 A：5% 串行工作如何锁死 64 核
假设参数：P 个处理器；总工作折算为串行时间 100 单位，其中串行段占 5%（S = 0.05）。 按 Amdahl：T_P = S + (1−S)/P，Speedup(P) = 1/(S + (1−S)/P)。
| P | 4 | 8 | 16 | 64 | 256 | 1024 |
|---|---|---|---|---|---|---|
| S = 0.05 的上限 | 3.48x | 5.93x | 9.14x | 15.42x | 18.62x | 19.64x |
| S = 0.20 的上限（CS149 版算例） | 2.50x | 3.33x | 4.00x | 4.71x | 4.92x | 4.98x |
| S = 0.001 的上限 | 3.99x | 7.94x | 15.76x | 60.21x | 203.98x | 506.18x |
读法：S = 0.05 时，64 核只能拿到 15.42x（理想 64x 的 24%），从 256 核加到 1024 核只多 5%（18.62x → 19.64x），渐近上限就是 1/S = 20x；S = 0.20 时，核数超过 16 之后几乎完全没有收益（16 核 4.00x → 1024 核 4.98x，渐近上限 5x）。所以讲义反复强调：“只有很小的负载不均就能显著限制最大加速比”，而”我的方案可扩展”必须限定规模。
4.3 数值算例 B：并行冗余度（parallel slack）该取多少
假设：8 个执行上下文；任务的执行时间不可预测，且负载不均的代价按 Amdahl 折算。定义 slack = 独立工作件数 / 机器的并行执行能力。
- 下界（填满机器）：至少要有 ≥ P 件工作，否则总有核闲着；考虑成本波动，讲义给出实践值 ~8，即至少 8P = 64 件独立工作。
- 上界（不要细到开销失控）：任务更细 → 需要更多次调度/同步。给定”每件任务的调度开销占比 ≤ ε”的要求，任务成本
t_task与单次管理成本c_mgmt必须满足c_mgmt / t_task ≤ ε。 - 算例：
c_mgmt = 494 ns（§3.2 实测的争用原子取号成本），要求调度开销 ≤ 5%，则单件任务至少要做494/0.05 ≈ 9.9 µs的工作。若单件工作只有 22.9 ns（LIGHT 负载），chunk 必须 ≥ 9.9 µs / 22.9 ns ≈ 432 件——与表 2 实测的”256–4096 平台区”吻合（chunk=64 时已比最优慢 73%，chunk=1 时慢 143 倍）。 - 结论（可扩展性的两个边界）：
独立工作件数 N_task 必须落在窗口内： N_task ≥ slack × P （下界：负载均衡 / 填满机器） N_task ≤ W_total / (c_mgmt/ε) （上界：调度开销不能吃掉收益） 且 N_task ≈ 数十倍 P 时，成本波动才能被吸收（表 3：chunk=1024 → 只有 2 件工作 → max/avg = 4.0）
4.4 数值算例 C：粒度选择公式与实测对照
模型：设工作总成本 W（单线程时间），每件任务平均成本 t = W/M，一次”取活”的全局串行化成本 c，chunk = k 件任务，P 个处理器。
总运行时间估算： T ≈ max( W/P , (M/k)·c ) + 尾部失衡
└─ 并行部分 ─┘ └─ 取号串行链 ─┘
下界（同步主导）： (M/k)·c ≤ W/P ⇒ k ≥ c·P/t
上界（失衡主导）： 件数 M/k ≥ slack·P ⇒ k ≤ M/(slack·P)
代入 §3.2 的 LIGHT 负载实测参数：W ≈ 4.58 ms（= 0.573 ms × 8 线程），M = 200000，
t = W/M = 22.9 ns，c ≈ 494 ns，P = 8，slack = 8：
k ≥ c·P/t = 494 ns × 8 / 22.9 ns ≈ 173
k ≤ M/(slack·P) = 200000/64 ≈ 3125
窗口 ≈ [173, 3125] 实测平台区 = [256, 4096]，最优 chunk = 1024（0.573 ms）
预测与实测一致；预测下界 173 略低于实测下界 256，是因为模型把"取号"当成完全串行，
实际取号与计算部分重叠，因此真实下界更靠右一点。
代入 HEAVY 负载：t = W/M ≈ (9.47 ms × 8)/2048 ≈ 37.0 µs，c ≈ 494 ns：
k ≥ 494 ns × 8 / 37.0 µs ≈ 0.11 ⇒ k = 1 就已足够（实测 chunk 1…256 全平）
k ≤ 2048/64 = 32 ⇒ 实测 chunk=1024 只剩 2 件 → 失衡 4.0，时间 ×4
结论：最优粒度不是”越细越好”或”越粗越好”，而是由 c·P/t 与 slack·P 夹出的窗口。工作越贵（t 越大）→ 窗口越宽、可以越粗；同步越贵（c 越大）→ 窗口右移、必须更粗。
4.5 数值算例 D：窃取开销必须被摊薄
假设：一次成功窃取的成本 c_steal ≈ 1 µs（跨 socket 的原子 CAS + 缓存行迁移 + 队列元数据更新），窃取到的任务成本 t_task。
- 窃取开销占比
= c_steal / t_task。 - 若偷到的是叶子任务（§3.3 中 8192 个元素的排序，实测约 100 µs）：占比 1%，可接受。
- 若偷到的是单个元素的工作（~2 ns）：占比 500 倍——系统被窃取路径彻底压垮。
- 实测印证：§3.3 中 150 次成功窃取 × 1 µs = 0.15 ms，占 38.2 ms 的 0.4%；而 336,000 次失败的窃取尝试（每次约两条原子读 + 一次 CAS 尝试 + fence，粗估 ~50 ns）合计约 17 ms CPU 时间——若这些周期全部从有用计算中”偷”走，相当于整体多出约 2 ms（占 8 线程 38 ms 运行时间的 ~5%，实际影响更小，因为空闲线程本来也没有有用工作可做，但它会争用内存/相干性资源并干扰受害者的本地快路径）。两条数字合起来给出本讲最重要的工程准则：
成功窃取要"少而大" → 从 dequeue 头部拿（调用树里更大的那块） 失败尝试要"便宜" → 退避 + 随机化 + 适时让出/睡眠，而不是无脑自旋 - 摊销公式：若把任务粒度缩小为 1/g，则为了维持同样的窃取开销占比，窃取次数必须同比例减少，而这与”任务数增多 → 需要更多次再平衡”直接矛盾。这就是细粒度 fork-join 需要高效（无锁）窃取路径的根本原因，也解释了 §2.6 里”偷头部”的三条理由。
4.6 数值算例 E：内存带宽与算术强度（为什么”分配得好”仍然可能跑不快）
即使调度完美，内存层次仍会给并行程序设一个上限。这是下一讲的主题，但本讲的两个示例已经撞上了它：
- 纯带宽算例：一个 256 MB 的数组，机器可持续带宽 20 GB/s，则单次遍历至少需要
256 MB / 20 GB/s = 12.8 ms；若要读+写（例如B[i] = f(A[i])），流量 512 MB → 25.6 ms。这段时间与线程数无关：8 个线程、64 个线程都一样，因为带宽是共享资源。上面 §3.1 的 8 线程快排只有 3.65x（而不是 8x），正是这类”共享资源饱和”的形态：4 → 8 线程只涨 1.27x。 - 算术强度/屋顶线（Roofline）：若某内核每字节访存做
AI次浮点运算，则性能上限 = min(峰值算力, AI × 带宽)。- 算例：16 核 × 3.0 GHz × 8 宽 SIMD × 2（FMA）= 768 GFLOPS 峰值；带宽 100 GB/s、AI = 0.25 FLOP/B → 内存上限 25 GFLOPS，即峰值算力只能兑现 3%。要让计算受限，需要
AI ≥ 768/100 = 7.7 FLOP/B。 - 对调度策略的启示：把一个内存受限的内核切成更多任务、交给更多线程，并不会缩短时间（带宽不变），只会增加调度开销；此时正确的优化方向是提高数据复用（缓存分块），而不是继续调调度器。“先把瓶颈找对，再决定要不要动调度”——这是 TIP #1 之后最重要的一条纪律。
- 算例：16 核 × 3.0 GHz × 8 宽 SIMD × 2（FMA）= 768 GFLOPS 峰值；带宽 100 GB/s、AI = 0.25 FLOP/B → 内存上限 25 GFLOPS，即峰值算力只能兑现 3%。要让计算受限，需要
- 临界区/共享状态的带宽算例：一个 8 字节计数器被 8 个线程各做
10⁶次 RMW（x86 的lock前缀指令在争用时表现为串行化的缓存行搬运，约 0.3–0.5 µs/次）→ 总时间 ≈8×10⁶ × 0.4 µs = 3.2 s：一个 8 字节变量把 8 个核变成了一条串行流水线。修法（下一讲 + 同步讲）：分片累加（per-thread/per-socket 计数）+ 最后归约，或减少 RMW 频率（chunk…就是本讲的内容！）。
4.7 表 5：本讲各方案的定量对照（综合前面所有算例）
| 方案 | Work 变化 | Span / 关键路径 | 主要开销来源 | 实测（本机 8 线程） | 适用判据 |
|---|---|---|---|---|---|
| 静态 blocked/interleaved | 不变（+索引运算） | 由最长分片决定 | 近零 | — | 工作量与成本可预测 |
| 共享计数器 + chunk=1 | 不变，但串行化 | Span = 任务数 × c_sync | 争用原子（~494 ns/次） | 99.5 ms（LIGHT，最差） | 只有在 t_task ≫ c_sync·P 时用 |
| 共享计数器 + chunk=1024 | 不变 | Span 大幅缩短 | 取号 ~0.1 ms | 0.573 ms（LIGHT，最优） | 窗口 [c·P/t, M/(slack·P)] |
| 共享队列 + 长任务优先 | 不变 | 尾部 slop 缩短 | 每次取活都同步 | 仿真：84 → 60（P=4） | 成本有可预测性（或可估计） |
| 分布式队列 + 工作窃取 | 不变 | 由任务图 span 决定 | 仅窃取时（~150 次成功窃取 = 0.4%） | 38.2 ms / 5.66x（N=3M） | 递归分解、任务边界动态生成 |
| 粒度再细分（对半拆） | 增加（管理开销） | span 减半 | 更多调度事件 | 仿真：58 → 50（P=4） | 长杆无法被顺序手段消除时 |
5. 关键要点
- 本讲的全部内容都是”三个互相冲突的目标”之间的取舍：负载均衡、减少通信、减少额外工作。先写最简方案、测量、再只优化真正的瓶颈（TIP #1）；”我的方案可扩展”必须限定在具体的机器规模与工作负载上。
- 负载不均按 Amdahl 定律被放大：串行段 S = 0.05 就能让 64 核只拿到 15.42x（理想 64x 的 24%），渐近上限 1/S = 20x；S = 0.2 时超过 16 核几乎没有收益（上限 5x）。因此”分配策略”不是工程细节，而是加速比上限的直接决定因素。
- 静态 → 半静态 → 动态 → 工作窃取是一个连续谱，不是二选一：能用先验知识就用（静态/半静态的开销近零）；只能运行时才知道就用动态；只有在任务边界由递归分解动态产生时，每线程 dequeue + 随机窃取才是对的工具。极限情形（系统全知）就是完全静态分配。
- 任务粒度是核心旋钮，且最优值由公式给出：下界来自同步成本（
k ≥ c·P/t），上界来自负载均衡（k ≤ M/(slack·P)），实践上要求任务数远多于处理器数（slack ~8），同时每件任务的调度开销远小于任务本身。实测：同一负载下 chunk=1 与 chunk=1024 相差 143 倍；而同一 chunk 在”贵任务”负载下可能毫无差别——因为同步开销是争用强度的函数，不是常数。 - 工作窃取的精髓在于”本地快、窃取少而大”：owner 在自己的 dequeue 尾部 push/pop（LIFO、无锁、保局部性），窃取者从头部拿（减少争用、偷到调用树里更大的块、最大化局部性），受害者随机选择；成功的窃取很稀有（实测 150 次 / 645 件任务，开销 0.4%），但失败的尝试必须便宜（实测 33.6 万次尝试 ≈ 5% 运行时间）——这正是 Cilk 用 continuation stealing + greedy join + descriptor 记账，把同步开销压到”只在窃取时出现”的原因。
6. 常见陷阱与注意事项
- 把
cilk_spawn（或#pragma omp task）当成”工作已经并行执行了”：它只是许可，不是命令。若独立工作总量不足以填满机器（缺 parallel slack），或者任务图事实上是一条链，程序照样串行跑满全程；在 1 个线程上跑一遍，确认”没有窃取时执行顺序 = 串行顺序”，是验证 fork-join 代码正确性的第一道关。 - 任务粒度太细：把 O(1) 的工作用
cilk_spawn/task包起来，调度与同步开销立刻压过收益——实测同一负载下 chunk=1 比 chunk=1024 慢 143 倍，程序从”并行”退化为”以 Span 为运行时间的串行程序”。任务至少要”贵”到能摊薄一次取活成本（几百 ns 到几 µs）。 - 反过来把粒度做得太粗 / 把长任务放在最后：只剩 2 件工作分给 8 个线程时
max_work/avg_work = 4.0，时间 ×4；只剩 1 件时= 8.0，时间 ×7.9（表 3）。“动态分配”不等于”负载均衡”：它只会让空着的工人去取活，不会把一件巨长的活切开——长任务必须优先派发（LPT）或预先拆分。 - 假定同步开销是常数：同一个原子取号在”8 个线程饱和争用”时约 494 ns，在”每 37 µs 才取一次号”时回落到 50–100 ns。用常数去算 Amdahl 会得出错误的粒度结论；必须用你的工作负载在你的机器上实测这条曲线（这也解释了为什么表 2 与表 3 的最优 chunk 相差三个数量级）。
- 伪共享（false sharing）：多个线程的独立变量落在同一条缓存行上（例如每线程一个计数器放在同一个数组里、或
alignas(64)漏掉 dequeue 的top_/bottom_），每次写都让对方的核心缓存失效，性能可以比串行还差。规则：凡是”不同线程高频写”的数据，都要按缓存行（通常 64 字节）隔离或按线程私有化；本讲示例中的alignas(64) std::atomic<size_t> top_/bottom_就是这个规则的最小示例。 - 把有依赖的工作塞进工作队列：队列里放”互相有依赖但未声明”的工作是数据竞争，且结果不可复现（依赖时序）。要用讲义中的
enqueue_task(bar, foo_handle)形式显式声明依赖，或确保任务真正独立——当任务之间有依赖时，运行时间由关键路径（span）而非总工作量决定，此时加线程数毫无帮助。 - 过度自旋/忙等：本讲示例中 336,000 次窃取尝试只成功 150 次（成功率 0.04%），浪费约 17 ms 的 CPU 时间（粗估相当于整体运行时间的 ~5%），还会干扰受害者本地队列的缓存行。空闲等待要用退避（backoff）、让出（yield）或阻塞，而不是无脑重试；终止检测也要避免”全系统轮询一个全局变量”成为新的争用点。
7. 思考题（带答案）
思考题 1：如果某个 Cilk 实现把 cilk_spawn foo() 实现成普通函数调用，它还正确吗？这对我们理解”抽象 vs 实现”有什么意义？
【答案】 正确。 cilk_spawn 的抽象语义只承诺一件事：”被派生的调用可以与调用者并发执行“——它是一个许可（permission），不是”必须并行执行”的命令。把 spawn 当成普通调用（即所谓的 serial elision / 串行省略：把 cilk_spawn 与 cilk_sync 直接删掉）是一个合法的调度（所有工作仍通过原来的依赖顺序完成，结果是确定的），因此该实现是正确的。它只是性能上退化为串行（加速比 = 1）。
这个问题的意义有三点：
- 抽象与实现的分离：程序文本只表达”哪些工作可以并行”，而”何时、由哪个线程执行”完全属于实现（调度器）的自由。Cilk 的所有示例代码都可以先在单线程下调试，正确性由调度无关性（determinacy）来保证。
- 性能不是语义：正确性与可扩展性是两个独立维度；”删掉 spawn 后跑出正确结果”不能说明程序并行得动。
- 反过来说，
cilk_sync是硬约束：它必须在所有派生调用完成后才返回，因此实现不能随意重排跨越同步点的工作——这也是 sync descriptor（spawn/done 计数）存在的原因。如果你的程序语义依赖”某个 spawn 真的与 bar() 同时运行”（例如依赖竞态的读-改-写），那程序本身就是错的，因为合法实现（串行省略）会给出不同结果。
思考题 2：给定机器 8 个执行上下文、实测一次争用原子取号成本约 500 ns。你的任务集有 100 万件工作，其中 90% 的成本是 100 ns、10% 的成本是 20 µs，件数多到足以让分配均匀。请给出 chunk 的合理取值并说明推导；再用表 2/表 3 的实测结论验证你的推理。
【答案】 用 §4.4 的两个约束夹出窗口。
- 同步成本下界：平均任务成本
t = 0.9×100 ns + 0.1×20 µs = 90 ns + 2 µs = 2.09 µs。要求一次取号开销占单件任务成本不超过 ε = 5%：k ≥ c/(ε·t) = 500 ns / (0.05 × 2.09 µs) = 500/104.5 ≈ 4.8→ k ≥ 5（取 k = 8 更稳妥，留出安全边际）。若不做”平均”而按最便宜的任务算（保守）：k ≥ 500/(0.05×100) = 100，这是”连便宜任务也不吃亏”的取值。 - 负载均衡上界：
k ≤ M/(slack·P) = 10⁶ / (8×8) = 15625，且为了让那 10% 的昂贵任务（20 µs）不要集中在少数 chunk 里造成尾部失衡，chunk 越小越好（但受 1 约束）。 - 结论：取 k ≈ 8–100（推荐 k = 64：同步开销占比
500/(64×2.09 µs) ≈ 0.4%，同时仍有10⁶/64 ≈ 15625个 chunk，slack ≈ 1950 ≫ 8，足以吸收成本波动）。注意 k=1 一定错：它把 100 万次争用原子操作（≈ 0.5 s 的串行化时间）压到程序的关键路径上。 - 与实测对照：
- 表 2（LIGHT，t = 22.9 ns）的窗口是
[173, 3125]，实测最优 chunk = 1024（0.573 ms），而 chunk = 1 时因为 20 万次 × 494 ns 的串行化，耗时 99.5 ms（慢 143 倍）——验证了”同步成本下界”这一侧。 - 表 3（HEAVY，t = 37 µs）的下界只有
k ≥ 0.11，实测 chunk 在 1…256 之间完全平坦（差异 <1%），而一旦越过上界（chunk = 1024 → 只剩 2 件工作），失衡比飙到 4.0、时间 ×4 —— 验证了”负载均衡上界”这一侧。 - 这道题的负载
t = 2.09 µs介于两者之间，正好落在”两边都要照顾”的区域，所以答案是一个区间而不是一个数：最优粒度取决于工作负载的成本分布与机器的争用特性，必须实测确认（本讲的实测表就是最基本的测量方法）。
- 表 2（LIGHT，t = 22.9 ns）的窗口是
思考题 3：为什么工作窃取要”本地在尾部 push/pop、窃取者从头部偷”？如果改成窃取者也从尾部偷，会出现哪些具体问题？另外，为什么空闲线程要随机选受害者？
【答案】
（1）为什么 owner 用尾部、窃取者用头部？
- 减少争用：两方访问同一个 dequeue 的不同端（各自的索引与缓存行位置不同），因此不需要对同一个元素做 CAS，也不需要同一把锁。若双方都动尾部，
bottom索引就成了双方争抢的同一个热点缓存行：owner 每次 push/pop 都要写它，窃取者每次偷也要改它，双方的核心缓存不停失效（cache line ping-pong），本地快路径（本应”几乎免费”）会退化成”每次都要走一次相干性协议”。 - 偷到更大的工作、摊薄窃取成本：配合”先跑子任务（continuation stealing）”，最近压入尾部的是最深、最小的调用树节点，而头部保留的是调用树里最早、最大的一块（例如整个”剩下的迭代”或”半棵树”）。从头部偷 = 一次窃取的 1 µs 被后面几百微秒的工作摊薄（§4.5）；若从尾部偷，偷到的往往是 owner 马上就要做的最小一块，窃取立刻变得频繁而昂贵。
- 最大化局部性：owner 沿深度优先在自己那片调用树里工作（尾部 LIFO），窃取者从头部拿走一整棵子树并在自己的栈里继续深度优先——两边各自”抱着一棵子树”跑，各自的访问模式与数据局部性都好。这就是讲义所说的”in conjunction with run-child-first policy, local thread works on local part of call tree“。
（2）若窃取者也从尾部偷，具体会出什么问题？
- 与 owner 抢同一件工作：最坏情况下窃取者拿走了 owner 即将 pop 的那一个任务，owner 白跑一趟再去找活，双方反复”抢-让”，本地快路径彻底失效；
- 数据竞争风险剧增：两端同时修改同一个索引，Chase-Lev 的双索引协议（owner 写
bottom、thief 用 CAS 改top）不再适用，必须退回”两端共享一把锁/一个 CAS”，也就丢掉了”高效无锁 dequeue”这一整块设计； - 粒度最优化被破坏：偷到的常常是刚创建的最细碎的任务，窃取次数上升、每次收益下降，与”粒度不能太细”的原则直接冲突。
（3）为什么随机选受害者？
- 避免热点与同步：如果所有空闲线程都去偷”同一个最忙的线程”（例如固定偷 0 号），那么该线程的 dequeue 头部就成了新的争用点，而且多个窃取者会互相竞争同一个头部元素（大量 CAS 失败白白浪费——§3.3 实测的成功率就只有 0.04%）；
- 统计学上的均衡与可扩展性：随机化把窃取请求均匀散布到所有 worker 上，符合 Cilk 的理论分析（随机窃取 + 贪婪策略下，期望运行时间接近
W/P + O(S)），也不需要任何全局协调或中心化的负载信息； - 实现代价低：随机受害者只需要一个线程私有的伪随机数发生器加一次取模，不需要维护全局负载表（那又会引入共享状态与新争用）。实践中常配指数退避与”偷不到就先挑下一个/稍后再试”的策略，进一步压低无效尝试的比例。