并行算法与任务调度（parallel algorithms / dependency graph / pipeline）

HPC 工程里「怎么把循环并行起来、怎么表达数据依赖」是高频题。既考标准库 std::execution，也考分治思想与任务图。

一、并行循环 / parallel algorithms（C++17 起）

标准库 <algorithm> 多数算法可加执行策略：

#include <execution>
std::vector<double> a(N), b(N);
// 串行默认
std::transform(a.begin(), a.end(), b.begin(), [](double x){ return x*x; });
// 并行（若底层支持）
std::transform(std::execution::par, a.begin(), a.end(), b.begin(), f);

常用：par（多线程）、par_unseq（多线程 + 允许向量化/C++20 SIMD 提示）、unseq（仅向量）。库如 TBB：tbb::parallel_for、parallel_reduce。

约束（必答）：并行执行策略下对共享状态的数据竞争仍是 UB；谓词须是无数据竞争；避免共享累加器（用 per-element/局部 reduce 再合并），对需要全局归约用 reduce/exclusive_scan 等算法或给 execution 策略的 compatible RNG 等。

// 求和：别写共享 sum，用 parallel_reduce / 局部归并
double sum = std::reduce(std::execution::par, v.begin(), v.end(), 0.0);

二、分治并行：把 work 拆到多少块是对的

• 拆多少：理想块数 ≈ 核数 × 每核可并行重叠（超线程/流水）的若干倍，但不是越细越好——任务切分/派发有开销（任务对象、原子队列、唤醒）。
• 过粗：有的核空转（负载不均、最后一块决定延迟）；过细：调度开销吃掉并行收益。
• 用递归二分 + 阈值转串行（TBB/divide-and-conquer 范式）：if (n < grain) serial else split-halves parallel。经典范例如 parallel_for/parallel_reduce 递归拆分直到 grain。

// 伪：递归并行归约示意
double par_reduce(T* a, size_t n) {
    if (n <= GRAIN) return serialSum(a, n);
    size_t half = n/2;
    // 无共享状态、天然可用 std::async 或 pool 两半并行
    auto f1 = std::async(par_reduce, a, half);
    double r2 = par_reduce(a+half, n-half);
    return f1.get() + r2;
}

大量任务用线程池批量提交更优（见 thread-pool.md）。

三、任务图 / 依赖调度

问题：任务 A 完成 → B、C 可并行；C → D；如何保序且不串行。

思路：

1. 抽象成 DAG（节点=任务，边=依赖）。
2. 调度器维护「就绪集合」= 入度归零节点；任务完成减小依赖方入度，入度归零即入就绪队列。
3. 用 worker 线程 + 工作窃取 并行消费就绪任务；无锁状态机更新完成计数（fetch_sub）。

实现层面知识点：

• continuation 风格（任务回调）+ 引用计数（1 + 依赖数，全部完成才运行 continuation）。
• 无 return 阻塞主控：避免 thread 死等（否则又变串行/活锁），用 future/shared 或计数完成时唤醒主控。

四、流水线（Pipeline）

阶段并行：如 解压 → decode → 变换 → 归约。各阶段需不同 worker 批处理；瓶颈是最慢阶段（吞吐=最慢阶段速率）。 要点：阶段间用有界队列/ring buffer背压（防生产者淹没消费者）、拆分成多路让各阶段错峰。

五、HPC 相关高频追问 & 参考答案

1. 怎么决定某循环要不要并行？
   • 检查是否无交叉迭代依赖 / 归约安全 / 无副作用别名（用 __restrict__ 提示 alias）；
   • 串行快（数据局部性好、cache 顺访）谨慎；大数据块 → 并行基准 vs 串行实测，不要拍脑袋。
2. 内存带宽 vs 计算哪个是墙？
   • 很多算子受内存带宽限制（ALU 用不满）——并行 & 向量化前提是保证访存连续/缓存友好，否则白并行。
3. 为什么要 cache blocking/tiling？
   • 让遍历块在 L2/L1 内可复用，减少 cache miss；与并行结合时块要符合线程亲和。

六、工具速记

• TBB（oneTBB）：parallel_for/reduce/scan、task_group、flow_graph。
• OpenMP：#pragma omp parallel for reduction(+:sum)（简单 HPC 循环，比手写线程池省心）。
• C++17 execution policy：标准但各 lib 支持不一；C++26 有新的 sender/receiver（execution 2）概念。
• 手写 vs 框架：手写线程池可控但易错；框架省心、适配 NUMA/窃取。答「生产用 TBB/自研窃取调度，原型用 OpenMP/execution」最稳。