Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 5: Program Optimization 1: Work Distribution and Scheduling（程序优化（一）：工作分配与调度）（日期：Oct 07）

目录 · ← l4 · l6 →

Lecture 5: Program Optimization 1: Work Distribution and Scheduling（程序优化（一）：工作分配与调度）（日期：Oct 07）

概述：本讲聚焦并行程序性能优化的第一个维度——把工作”喂饱”所有执行单元。核心目标（彼此矛盾）有三：负载均衡（workload balance）、减少通信、减少并行开销（overhead）。讲义先讲静态/动态/半静态分配与任务粒度（task granularity）的取舍，随后深入剖析 fork-join 并行模式的调度：以 Cilk Plus 的 cilk_spawn/cilk_sync 为例，详细讲解 work stealing（工作窃取） 调度器如何用”每线程一个 dequeue + 空闲线程随机窃取”实现低开销、高局部性的动态负载均衡，包括 child stealing vs continuation stealing 的选择、sync 的 block descriptor 实现，以及 greedy join 调度策略。

注意：本讲与 Assignment 2（”Scheduling Task Graphs on a Multi-Core CPU”，截止 Oct 16）直接相关——讲义中”work queue 中的任务不必相互独立”、enqueue_task(foo, bar_handle) 的显式依赖正是该作业任务图调度库的核心思想。

一、核心概念与定义

1. Workload Balance（负载均衡）与 Load Imbalance（负载不均）

  • 定义：理想情况下，程序执行的每一刻所有处理器都在计算，且同时完成各自的工作。只要少量负载不均，就会显著限制最大加速比——因为最后完成的那个处理器决定了整个程序的运行时间，超出的那部分时间相当于串行执行（受 Amdahl’s Law 约束）。
  • 现实类比：搬家时四个人搬箱子，一个人搬的箱子是别人的两倍重——整个搬家时间被最慢的人拖住，其余三个人提前干完也只能干等。
  • 公式/图示：
      时间 ──────────────────►
P1:   ████████████░░░░░░░░░░  （干完了，闲着）
P2:   ████████████░░░░░░░░░░
P3:   ████████████░░░░░░░░░░
P4:   ████████████████████████  ← 2 倍工作 → 2 倍时间
      └───── 50% 的运行时间是"串行"的（只有 P4 在干活）───┘
      （串行部分约占全程序工作的 1/5，即 Amdahl 公式中 S ≈ 0.2）

2. Static Assignment（静态分配）

  • 定义：工作的分配不依赖运行时动态行为。注意”静态”不等于”编译期确定”：只要在”工作量与 worker 数量已知”时就能确定的分配都算静态（可以依赖运行时参数，如输入规模、线程数）。优点是简单、分配开销几乎为零（本例只有一点索引计算）。
  • 现实类比：老师开学第一天就把全班座位按名单排好——之后不再变动。
  • 公式/图示：适用场景——工作量可预测：12 个等代价任务，静态分给 4 个处理器各 3 个；代价不等但已知/平均可预测时，按任务个数平分也可（平均意义上均衡）。
12 个相同代价任务：  T0 T0 T0 | T1 T1 T1 | T2 T2 T2 | T3 T3 T3
                   └─P1─┘    └─P2─┘    └─P3─┘    └─P4─┘

3. Semi-Static Assignment（半静态分配）

  • 定义：近期的执行代价可预测（”最近的过去是近未来的好预测器”）。应用周期性 profile 自己的执行并重新调整分配；分配在两次调整之间保持”静态”。典型场景：自适应网格（adaptive mesh，物体移动导致网格密度变化但变化缓慢）、粒子模拟（粒子缓慢移动时定期重分配）。
  • 现实类比：快递站根据每天的包裹量变化，每周重新划分一次配送片区，但一周之内片区固定。
  • 公式/图示：无（机制描述）。

4. Dynamic Assignment（动态分配）

  • 定义：程序在运行时动态决定分配，以保证负载分布良好（任务执行时间或任务总数未知/不可预测时使用）。典型实现：共享计数器（counter）或共享 work queue（工作队列）——worker 取走下一个未完成的任务。
  • 现实类比：外卖平台接单——骑手完成一单后从平台”抢”下一单，谁抢到谁送（任务到达时间不可预测）。
  • 公式/图示：见代码示例 1。

5. Work Queue（工作队列）与 Task Granularity（任务粒度）

  • 定义：work queue 是”待做任务”的列表，worker 线程从队列取任务、产生新任务时再推入。任务粒度指单个任务包含多少工作量：细粒度（1 任务 = 1 元素）负载均衡好但同步开销高（临界区被频繁进入）；粗粒度（1 任务 = 10 元素）同步次数减少 10 倍但均衡性变差。
  • 现实类比：切西瓜——切得越小（细粒度），每个人分到的大小越均匀，但切西瓜本身（分配开销）耗时越多；切得太大块则有人吃不完有人不够吃。
  • 公式/图示：
细粒度（每任务 1 元素）:   [临界区] [工作] [临界区] [工作] [临界区] ...  同步开销高
粗粒度（每任务 10 元素）:  [临界区] [10×工作] [临界区] [10×工作] ...    同步开销低

选择任务大小的原则：任务数应远多于处理器数（利于动态分配下的均衡）→ 倾向小粒度；同时任务数尽量少以最小化管理分配的开销 → 倾向大粒度。理想粒度取决于工作负载与机器（本课程反复出现的主题）。

6. Parallel Slack（并行松弛）

  • 定义：独立工作（可并行工作）与机器并行执行能力的比值。实践中 ~8 是好的比值：既保证良好的负载均衡（有足够的”余量”让调度器填满所有核），又不至于因任务过细而产生过多管理开销（slack 太大 = 任务粒度太小）。
  • 现实类比：自助餐厅备餐——备的菜量是客流量的 8 倍左右，高峰期不会有人饿肚子，但也不用备 100 倍造成浪费。
  • 公式/图示：
parallel slack = 独立工作总量 / 机器并行执行能力   （实践中 ≈ 8）

7. Fork-Join Parallelism（分叉-汇合并行）与 Cilk

  • 定义：用”分叉（fork，创建新的逻辑控制流）→ 汇合（join，等待其完成）”来表达分治算法（divide-and-conquer）中天然存在的独立工作。本讲代码用 Cilk Plus（C++ 语言扩展，源自 MIT，现为 GCC/Intel ICC 支持的开源标准）：
    • cilk_spawn foo(args); —— 调用 foo，但调用者可以异步地与 foo 的执行并行继续；
    • cilk_sync; —— 等到当前函数所有已 spawn 的调用完成；每个含 cilk_spawn 的函数末尾有隐式 cilk_sync（函数返回即代表其所有工作完成）。
  • 现实类比：老板派两个下属分头去两个城市调研（fork），回来一起开汇报会（join）——下属之间互不依赖，老板不必等第一个回来才开始派第二个。
  • 公式/图示：
cilk_spawn foo();  cilk_spawn bar();  fizz();  cilk_sync;

        ┌─ foo() ─┐
主线程 ──┤─ bar() ─├── 汇合（sync）──► 继续
        └─ fizz() ┘
（抽象：spawn 不规定"何时、由哪个线程"执行，只规定"可以并行"；sync 是调度约束：必须全部完成）

8. Work Stealing（工作窃取）调度

  • 定义：每个 worker 线程有自己的 work queue（dequeue）。线程优先从自己的队列取工作（本地 push/pop，无争用）；当自己队列为空时，随机选择一个 victim（受害者）线程，从其队列”偷”走一部分工作。工作队列中的任务可以不必相互独立（依赖由任务管理系统维护）。
  • 现实类比：几个收银员各有各的顾客队伍；某收银员队伍空了，就从别的收银员队伍里”拉”几个顾客过来结账，而不是大家一起抢一个队。
  • 公式/图示：
T1 ──► 自己的队列  ◄── 本地 push/pop（无争用）
T2 ──► 自己的队列  ◄── 本地 push/pop
T3 ──► 自己的队列  ◄── 本地 push/pop
T4 ──► 自己的队列     （空！）── steal! ──► 随机挑一个 victim 的队列偷工作

9. Continuation Stealing（延续窃取）与 Child Stealing（子任务窃取）

  • 定义：遇到 cilk_spawn foo() 时，调用线程必须二选一：
    • Run child first（先执行子任务，continuation stealing）：把”调用者剩余的代码”（continuation）放入工作队列，自己立即执行 foo()。若无人窃取，线程不断从队列弹出 continuation、更新其状态（如 i 自增）再入队——执行顺序与去掉 spawn 的串行程序完全一致（depth-first 遍历调用图）；若被窃取，窃取者从 continuation 继续执行。空间保证：T 线程系统的工作队列存储不超过单线程栈存储的 T 倍。
    • Run continuation first（先执行延续，child stealing）：把 foo() 入队，自己继续执行。调用者会先把循环里所有 spawn 的工作都生成完（breadth-first），O(N) 空间存储已 spawn 的工作；且无人窃取时执行顺序与串行程序差异很大。
    • Cilk 选择 continuation stealing（run child first）。
  • 现实类比：深度优先像”一个人埋头做到底，做不完就整包留给别人接着做”（continuation 是”剩下全部”的一整块）；广度优先像”先把所有材料摊满桌子，别人来拿现成的”（每个 spawn 都是独立一份）。
  • 公式/图示：
for (i=0; i<N; i++) cilk_spawn foo(i); cilk_sync;

child stealing（先跑 continuation）:
  线程0 队列: foo(N-1) foo(N-2) ... foo(0)   ← 先造出 N 个任务项，O(N) 空间

continuation stealing（先跑 child）:
  线程0 队列: [cont: i=1]                     ← 只有一个"剩余工作"项
  执行 foo(0)…  完成后把 cont 更新为 i=2 再入队（深度优先，执行顺序同串行）

10. Dequeue（双端队列）与 Victim（受害者）

  • 定义：工作队列实现为每 worker 一个 dequeue（double-ended queue）：本地线程从 tail（底部） push/pop；远程（窃取）线程从 head（顶部） steal。偷顶部的好处：① 偷到的是最大的一块工作（减少窃取次数）；② 与”先跑 child”结合时，每个线程执行的工作局部性最大（自己始终处理最近产生的、数据最”热”的工作）；③ 窃取线程与本地线程不争抢同一端元素，可用无锁（lock-free）实现。
  • 现实类比：每个人从自己这摞纸的最上面取纸（本地取），有人没纸了就从别人那摞纸的最下面抽走一摞——互不打扰，抽走的还是一大摞。
  • 公式/图示：
        每个 worker 的 dequeue：
        ┌────────────────────────────┐
head ──►│  (窃取线程从这里偷)         │
        │   [cont:151-200] [cont:26-50] ... │
tail ──►│  (本地线程在这里 push/pop)   │
        └────────────────────────────┘

11. Greedy Join Scheduling（贪心汇合调度）

  • 定义：Cilk 的调度策略：所有线程只要没事做就尝试窃取；只有当系统中完全没有可窃取的工作时线程才空闲。汇合（sync）时线程不傻等——立即去寻找其他可做的工作。窃取/同步簿记（bookkeeping）的额外开销只在发生窃取时才产生；大部分时间线程只是在自己本地 dequeue 上 push/pop。
  • 现实类比：加班到一半的同事不会干等别人交材料，而是马上去找别的活干；只有全公司都没活了才下班。
  • 公式/图示：无（策略描述）。注意：发起 spawn 的线程不一定是执行 cilk_sync 之后代码的线程（continuation 可能已被窃取）。

二、代码示例与详细解说（本讲重点）

示例 1：动态分配——共享计数器 vs 增大任务粒度（素性测试）

代码（C++，SPMD 线程）：

#include <thread>
#include <mutex>
#include <vector>
#include <algorithm>
#include <cstdio>

const int N = 1024;
int x[N];               // 输入数据（已初始化）
bool is_prime[N];       // 输出结果
std::mutex counter_lock;
int counter = 0;

bool test_primality(int v) {   // 执行时间不可预测（大素数很慢）
    if (v < 2) return false;
    for (int d = 2; d * d <= v; d++)
        if (v % d == 0) return false;
    return true;
}

// 细粒度版本：1 任务 = 1 个元素
void worker_fine() {
    while (true) {
        int i;
        counter_lock.lock();
        i = counter++;            // 从共享计数器领取下一个任务
        counter_lock.unlock();
        if (i >= N) break;        // 没有任务了，退出
        is_prime[i] = test_primality(x[i]);
    }
}

// 粗粒度版本：1 任务 = GRANULARITY 个元素
const int GRANULARITY = 10;
void worker_coarse() {
    while (true) {
        int i;
        counter_lock.lock();
        i = counter;
        counter += GRANULARITY;   // 一次领取 10 个元素
        counter_lock.unlock();
        if (i >= N) break;
        int end = std::min(i + GRANULARITY, N);
        for (int j = i; j < end; j++)
            is_prime[j] = test_primality(x[j]);
    }
}

int main() {
    for (int i = 0; i < N; i++) x[i] = i * i + 1000;
    std::vector<std::thread> pool;
    for (int t = 0; t < 4; t++)
        pool.emplace_back(worker_fine);   // 换成 worker_coarse 对比
    for (auto& t : pool) t.join();
    std::printf("primes found: %d\n",
                (int)std::count(is_prime, is_prime + N, true));
    return 0;
}

【代码做了什么？】

  1. 串行版本就是把 test_primality(x[i]) 循环跑一遍；但由于每个数的素性测试时间不可预测（大质数要试除很多因子），静态分配（每人固定 1/4 区间）会导致负载不均。
  2. 动态分配：多个 worker 共享一个 counter，每次加锁取一个（或一组）下标。先到先得，谁的块大谁自然多做——完成快的线程自动多干活，实现良好负载均衡。
  3. 细粒度（每任务 1 元素）与粗粒度（GRANULARITY=10）的唯一差别是临界区进入频率：粗粒度版本临界区次数减少 10 倍。

【并行机制解说】

  • 线程如何创建：std::thread 创建 4 个 worker，所有 worker 执行同一个 SPMD 函数（worker_fine），靠共享 counter 区分工作——这正是第 4 讲的 shared address space 模型。
  • 工作如何分配：动态分配（dynamic assignment）。锁保护的临界区（counter++）是分配机制本身，它引入的串行化是串行程序中不存在的额外开销（overhead），且是串行执行（受 Amdahl 定律约束）——这就是”细粒度同步开销”的量化来源。
  • 对应概念：dynamic assignment、work queue（此处为计数器形式）、task granularity、overhead、critical section。
  • 课堂讨论：细粒度同步开销到底是不是问题？答案取决于任务工作量与临界区开销之比——若每个任务本身很重，临界区开销占比就小，细粒度没问题；若任务很轻，就应增大粒度（讲义给出了粗粒度版本）。

示例 2：共享工作队列（work queue）与任务依赖（Assignment 2 预告）

代码（C++，共享工作队列 + 显式依赖的任务系统）：

#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <functional>
#include <vector>
#include <cstdio>

// 共享工作队列：worker 取任务、推任务都经过它
class WorkQueue {
    std::queue<std::function<void()>> tasks;
    std::mutex m;
    std::condition_variable cv;
    bool done = false;
public:
    void push(std::function<void()> f) {
        std::lock_guard<std::mutex> lk(m);
        tasks.push(std::move(f));
        cv.notify_one();
    }
    bool pop(std::function<void()>& out) {   // 阻塞取任务
        std::unique_lock<std::mutex> lk(m);
        cv.wait(lk, [&]{ return !tasks.empty() || done; });
        if (tasks.empty()) return false;
        out = std::move(tasks.front());
        tasks.pop();
        return true;
    }
    void finish() {
        std::lock_guard<std::mutex> lk(m);
        done = true;
        cv.notify_all();
    }
};

void worker(WorkQueue& wq) {
    std::function<void()> task;
    while (wq.pop(task)) task();    // 不断取任务执行
}

int main() {
    WorkQueue wq;
    std::vector<std::thread> pool;
    for (int t = 0; t < 4; t++) pool.emplace_back(worker, std::ref(wq));
    for (int i = 0; i < 64; i++)
        wq.push([i]{ std::printf("task %d\n", i); });  // 64 个独立小任务
    wq.finish();
    for (auto& t : pool) t.join();
    return 0;
}

【代码做了什么？】

  1. WorkQueue 用 mutex + condition_variable 实现线程安全队列：push 放入任务并唤醒一个等待线程，pop 在队列空且未结束时阻塞等待。
  2. main 放入 64 个独立小任务，4 个 worker 动态领取执行。执行顺序由调度决定（先到先得），不是确定性的。

【并行机制解说】

  • 工作如何分配：动态分配——所有 worker 争抢同一个队列。讲义指出这种单一共享队列的缺点：所有 worker 都要在同一个队列上同步（争用/contention），临界区成为串行瓶颈。
  • 改进方向（本讲后半部分 + Assignment 2）：分布式队列——每个 worker 有自己的队列，本地 push/pop 无争用；只有本地队列空时才窃取（steal）别人的工作（此刻线程本来就闲着，同步代价可接受）。这直接引出 work stealing。
  • 任务可以不独立（Assignment 2 的核心）：讲义给出带依赖的任务系统 API：
foo_handle = enqueue_task(foo);              // 独立任务
bar_handle = enqueue_task(bar, foo_handle);  // bar 依赖 foo：foo 完成前不能执行

任务管理系统（scheduler）负责在依赖满足后才把任务分配给 worker——这就是 Assignment 2 “Scheduling Task Graphs on a Multi-Core CPU”中任务图（task graph）调度库的抽象。

  • 对应概念：work queue、dynamic assignment、task dependency、task graph、contention（在第 6 讲详述）。

示例 3：Cilk 风格的分治并行——并行 Quicksort

代码（Cilk Plus）：

// Cilk Plus 代码：可用 Intel ICC 或 GCC 的 -fcilkplus 选项编译
// （也可用下方 std::async 近似版本在普通 C++ 环境验证同样的思路）
#include <algorithm>

const int PARALLEL_CUTOFF = 1000;   // 问题规模小于此值时串行排序

void quick_sort(int* begin, int* end) {
    if (begin >= end - PARALLEL_CUTOFF) {
        std::sort(begin, end);              // 足够小 → 串行（spawn 开销超过并行收益）
    } else {
        int* middle = partition(begin, end);      // 划分：选 pivot 并分区
        cilk_spawn quick_sort(begin, middle);     // 左半边：可能并行执行
        quick_sort(middle + 1, end);              // 右半边：当前线程继续执行
        // 函数末尾有隐式 cilk_sync：返回前保证左右两边都完成
    }
}

【代码做了什么？】

  1. 串行 quicksort 递归：quick_sort(begin, middle) 与 quick_sort(middle+1, end) 是相互独立的工作（划分完成后两边互不依赖）。
  2. Cilk 版本只在划分（partition）之后 spawn 左半边，右半边由当前线程直接递归执行——每个线程同时只产生一个可被窃取的”continuation”。
  3. PARALLEL_CUTOFF：问题足够小时退回 std::sort 串行排序——因为此时 spawn 的开销（创建任务、簿记）超过了并行化带来的收益。

【并行机制解说】

  • 工作如何分配（调度过程）：假设 200 个元素、3 个线程。线程 0 划分出 [0-100] 与 [101-200]，spawn 左半边后把”cont: 101-200”（continuation）放入自己的 dequeue，然后执行 [0-100] 的划分……线程 1/2 空闲时从线程 0 的 dequeue 顶部偷走一大块（如 “cont: 101-200”），各自继续划分——被偷的 continuation 又会生成新的 continuation 供进一步窃取。
  • 同步点：每个函数末尾的隐式 cilk_sync。被窃取的子任务完成后，通过 block descriptor（见下方示例 4）追踪”还有多少 spawn 未完成”。
  • 对应概念：fork-join、cilk_spawn/cilk_sync、work stealing、continuation stealing、PARALLEL_CUTOFF（任务粒度）、parallel slack。

C++ std::async 近似版本（普通 C++ 环境验证思路）：

#include <future>
#include <algorithm>

void quick_sort_async(int* begin, int* end) {
    if (begin >= end - PARALLEL_CUTOFF) {
        std::sort(begin, end);
    } else {
        int* middle = partition(begin, end);
        std::future<void> left =
            std::async(std::launch::async, quick_sort_async, begin, middle);
        quick_sort_async(middle + 1, end);   // 当前线程做右半边
        left.get();                          // ≈ cilk_sync：等待左半边完成
    }
}

示例 4：child-first 分治 vs 扁平 spawn 循环（工作窃取调度器如何”喂饱”机器）

代码（Cilk Plus）：

// 形式 1：扁平 spawn 循环（breadth-first 生成 O(N) 个任务项）
for (int i = 0; i < N; i++) {
    cilk_spawn foo(i);       // 每个 foo(i) 都是独立任务项
}
cilk_sync;

// 形式 2：child-first 递归分治（depth-first，空间占用 ≈ O(T · 单线程栈)）
void recursive_for(int start, int end) {
    while (start <= end - GRANULARITY) {
        int mid = start + (end - start) / 2;   // 对半切
        cilk_spawn recursive_for(start, mid);  // 先执行左半边（child first）
        start = mid;                           // "剩余工作"成为 continuation
    }
    for (int i = start; i < end; i++)
        foo(i);
}
recursive_for(0, N);

【代码做了什么？】

  1. 形式 1（扁平 spawn 循环）在 Cilk 的 child-first 执行下：线程执行 foo(0)，把”剩余迭代”作为唯一一个 continuation 入队；若该 continuation 被窃取，窃取者执行 foo(1) 后再把 continuation（i=2）入队——任何时刻队列中基本只有 1 个”剩余工作”项，调用图按深度优先遍历，空间占用小（T 线程总存储 ≤ T × 单线程栈）。
  2. 形式 2（递归分治）同样 child-first：线程 0 执行 recursive_for(0,N) 时 spawn recursive_for(0, N/2) 并立即执行它，把 recursive_for(N/2, N) 作为 continuation 入队；下一层递归再把 (N/4, N/2) 入队……队列里是一串大块 continuation（如 (N/2,N)、(N/4,N/2)、…），窃取者拿到任意一块后自己继续细分、又产生新的 continuation——可窃取的工作量随递归深度指数级增长。

【并行机制解说】

  • 为什么 child-first 调度器”预见到”分治：① 空间：任何时刻队列中只有”剩余工作”的 continuation，T 线程的工作队列总存储 ≤ T × 单线程栈存储（可证明）；② 并行度产生速度：扁平循环每次窃取只”释放”一个 foo（并行度线性爬升，机器填不满）；递归分治形式每次窃取都让窃取者继续细分出更多大块工作（并行度指数增长），更快地把并行机器填满——这正是讲义原话 “Code at right generates work in parallel, (code at left does not), so it more quickly fills up parallel machine”（右列代码在并行地产生工作、更快填满机器）；③ 无人窃取时，两种形式的执行顺序都与去掉 spawn 的串行程序一致（利于调试与空间局部性）。
  • 窃取顶部的好处：偷到的是最大的工作块（如 [101-200] 而不是 [1-2]），窃取次数少；每个线程执行的工作局部性最大（深度优先产生的连续区间数据往往在 cache 中相邻）；本地线程与窃取线程操作 dequeue 的两端，可无锁实现。
  • 对应概念：continuation stealing vs child stealing、dequeue、work stealing、parallel slack（”要有比执行能力更多的独立工作，但别多到粒度太细”）。

示例 5：sync 的实现——block descriptor（发生窃取时）

代码/图示（Cilk 运行时行为）：

// 假设 3 个线程执行：
for (int i = 0; i < 10; i++) { cilk_spawn foo(i); }
cilk_sync;
bar();

无窃取情形：cilk_sync 是 no-op —— 所有 foo 都由线程 0 顺序完成，没有跨线程依赖。

有窃取情形：
  线程0 执行 foo(0) (id=A)；线程1 偷走 "cont: i=0 (id=A)" 后执行 foo(1)...
  运行时为代码块 A 创建 descriptor：

        ┌──────────────────┐
        │ id = A           │
        │ spawn: 3, done: 1│   ← 该块已 spawn 3 个、已完成 1 个
        └──────────────────┘

  每当一个 spawn 发生（done 的 continuation 再次 spawn）：spawn+1
  每当一个 foo 完成：done+1
  cilk_sync 返回的条件：spawn == done（该块所有 spawn 的工作全部完成）
  之后：持有 continuation 的线程（可能不是发起 spawn 的线程 0！）继续执行 bar()

【代码做了什么？】

  1. 无窃取时 sync 无需任何簿记——所有 spawn 的工作都在同一线程顺序完成，sync 是空操作（no-op），零开销。
  2. 一旦发生窃取，运行时为每个”包含 spawn 的代码块”创建 block descriptor，记录该块 spawn（已产生的 spawn 数）与 done（已完成数）。每完成一个被窃取/本地执行的子任务更新计数；spawn == done 时 sync 满足。
  3. cilk_sync 之后的代码（如 bar()）由当前持有 continuation 的线程执行——不一定是发起 spawn 的线程。

【并行机制解说】

  • 开销分析（greedy join scheduling 的关键论据）：descriptor 的创建、计数更新等簿记只在发生窃取时才发生；若窃取的是大块工作，窃取应发生得很稀疏。绝大多数时间线程只是本地 dequeue push/pop——这就是 Cilk 调度器”低开销”的来源。
  • 对应概念：cilk_sync 的实现、block descriptor、greedy join scheduling、overhead（簿记开销与窃取频率成正比）。

三、关键要点

  1. 高性能编程的第一条铁律（TIP #1）：先实现最简单的并行方案，测量性能，再决定是否值得优化。不要过早引入复杂的分配/调度机制。
  2. 三个目标互相矛盾：负载均衡（把核喂饱）、减少通信（避免停顿）、减少额外开销（调度/同步/分配机制本身的开销）——优化的本质是在三者之间找平衡点。静态 vs 动态分配不是二选一，而是一个连续谱：尽可能用对工作负载的先验知识减少负载不均与任务管理开销（极限情况下，若系统全知，就用完全静态分配）。
  3. 任务粒度是核心杠杆：任务数要远多于处理器（利于均衡），又要尽量少（降低管理开销）——”任务太多”与”任务太少”都会拖慢程序；PARALLEL_CUTOFF、GRANULARITY、parallel slack ≈ 8 都是这个权衡的具体体现。
  4. Cilk 工作窃取调度器的三件套：① 每线程一个 dequeue，本地从底部 push/pop（无争用、可无锁）；② 空闲线程随机选 victim 从顶部窃取（偷最大块、保持局部性、减少窃取次数）；③ run child first（continuation stealing）——深度优先、空间有界（≤ T×单线程栈）、无窃取时执行顺序与串行一致。
  5. sync 的开销只在窃取发生时产生：greedy join 调度下线程永不空等（没事就偷，偷不到才 idle）；簿记开销与窃取频率成正比，而大块窃取保证了低频率。

四、常见陷阱与注意事项

  1. 过度细粒度导致同步成为瓶颈：每个任务都进出临界区，同步开销（串行部分！）可能超过并行收益。先估算”任务执行时间 vs 临界区开销”的比值，再定粒度；粗粒度版本（GRANULARITY）是简单有效的修复。
  2. 负载不均被低估：静态分配下若工作代价不均（P4 做 2 倍工作 → 50% 运行时间串行化，S≈0.2），加速比被 Amdahl 定律锁死。必要时用动态分配/半静态重分配；但动态分配本身有开销——用先验知识（semi-static）往往比纯动态更优。
  3. “长任务最后才被调度”：共享队列按入队顺序（左到右）取任务时，若长任务排在最后，末尾会出现大片空闲（slop）。对策：任务拆小，或先调度长任务（需要一定的工作量可预测性）。
  4. 单一共享队列的争用：所有 worker 抢一个队列，临界区串行化。用分布式队列 + 窃取替代（这也是 Assignment 2 的动机之一）。
  5. 误用 spawn/sync 语义与线程身份假设：cilk_spawn 只保证”可以并行”，不保证”一定并行”——一个只把 spawn 实现成普通函数调用的 Cilk 实现也是正确的（讲义明确提问过这一点）；cilk_sync 才是调度约束。同时不要把”发起 spawn 的线程会在 sync 后继续执行”当成不变量——continuation 可能已被其他线程偷走。跨线程共享状态时，要用 sync 保证依赖，而不是假设线程身份。

五、思考题（带答案）

  1. 问：为什么 Cilk 选择 “run child first”（continuation stealing）而不是 “run continuation first”（child stealing）？给出至少两个理由。 答：① 空间：child stealing 在进入任何工作前就生成 O(N) 个任务项（广度优先），而 continuation stealing 任何时刻队列中只有”剩余工作”一个 continuation，可证明 T 线程系统的工作队列存储不超过单线程栈存储的 T 倍；② 并行度产生速度：continuation stealing 沿递归路径立刻产生可窃取的工作，能更快填满并行机器（recursive_for 例子）；③ 无窃取时执行顺序与去掉 spawn 的串行程序一致（可预测、利于调试与 cache 局部性）。Cilk 采用 child-first，因此称为 continuation stealing。

  2. 问：讲义说”细粒度任务负载均衡好，但同步开销高”。若你的并行程序因临界区争用而变慢，除了增大任务粒度，还有什么办法？ 答：① 减少临界区内的操作（只保护必要状态，把重计算移出临界区）；② 用原子指令替代锁（如 atomic_incr(counter)，讲义动态分配示例的注释）；③ 用分布式队列 + 工作窃取，让本地 push/pop 无争用（本讲后半部分）；④ 若任务是并行的，考虑把”取任务”频率降到最低（每线程一次取一大块，如 GRANULARITY）。核心思想是减少对共享资源的访问频率与串行化时间——这正是第 6 讲”减少争用（contention）”的主题。

  3. 问：实现 cilk_sync 时，为什么”无窃取时它是 no-op”？这如何体现”抽象 vs 实现”？ 答：无窃取意味着该代码块的所有 spawn 工作都由同一线程顺序完成——sync 的语义（”所有 spawn 的工作已完成”）在顺序执行下自动成立，无需任何簿记。运行时只需在”发生窃取”（跨线程产生了真实的并行/依赖）时才创建 block descriptor 追踪 spawn/done 计数。这体现了抽象（cilk_sync 的语义恒定：等待所有 spawn 完成）与实现（是否产生簿记开销取决于具体的调度结果）的分离——也是 Cilk 调度器低开销的关键设计。