并行编程框架：OpenMP、TBB 与任务图¶

难度：⭐⭐⭐⭐ | 建议用时：2 周 | 前置要求：线程管理与互斥同步线程与互斥，原子操作与内存模型原子与内存模型，C++语言核心/Eigen基础与SLAM数学预备 Eigen 数据结构，C++语言核心/Concepts与Policy Concepts 与 Policy 设计

前置自测¶

答不出两题以上，建议先复习线程生命周期、临界区、数据竞争、缓存局部性和泛型接口。并行编程框架不是“自动加速按钮”。它只是把任务划分、调度、同步和归约包装成更高层的接口。如果底层不变量没有想清楚，框架会把错误放大到更多线程上。

一个 for 循环满足什么条件才能安全并行？
如果每个循环迭代都向同一个 std::vector 里 push_back，为什么加上 parallel_for 后会出错？
sum += residual; 为什么在并行循环里不是线程安全的？reduction 解决了什么问题，又没有解决什么问题？
为什么点云最近邻搜索常常比图优化线性求解更适合简单数据并行？
schedule(static) 和 schedule(dynamic) 的差别是什么？它们分别适合均匀负载还是不均匀负载？
TBB 的任务调度为什么比“手写固定线程数 + 平均分块”更适合不均匀任务？
并行浮点归约为什么可能让结果与串行版本有微小差异？
嵌套并行为什么可能导致线程过度订阅？
在 SLAM 系统里，哪些任务追求吞吐，哪些任务追求延迟？
如果一个并行实现比串行慢，应该先测什么，而不是先换框架？

本章目标¶

学完本章，你将能够：

用工作量、依赖关系、数据共享和同步开销判断一个算法是否适合并行化。
区分任务并行、数据并行、流水线并行和向量化，并能把它们映射到机器人软件中的具体模块。
使用 OpenMP 编写并行循环、归约、分块调度和最小临界区。
使用 TBB 编写 parallel_for、parallel_reduce、blocked_range、并发容器和受控并行域。
理解任务图框架适合表达“特征提取、匹配、优化、发布”这类有依赖关系的流程。
解释为什么并行归约会改变浮点求和顺序，并设计可重复性更好的聚合方式。
识别并行程序里的假共享、过细粒度、嵌套并行、异常传播和取消边界。
为点云体素下采样、残差评估、最近邻批查询、局部地图更新选择合适的并行策略。
完成 Mini SLAM Parallel Processing Layer：统一串行、OpenMP、TBB 三种执行策略，并给出可测量的加速比。
了解 C++26 std::execution（Senders/Receivers）的设计方向和 SYCL 异构并行的概念。

知识树：

并行编程框架
├── 并行化前提判断 ⭐⭐⭐
│   ├── 读写集合分析
│   ├── Amdahl 定律
│   └── 吞吐 vs 延迟
├── 并行模式分类 ⭐⭐⭐
│   ├── 数据并行（逐点变换）
│   ├── 任务并行（阶段流水线）
│   ├── 归约（残差汇总）
│   └── 向量化（SIMD）
├── OpenMP ⭐⭐⭐⭐
│   ├── pragma parallel for
│   ├── schedule(static/dynamic/guided)
│   ├── reduction 子句
│   ├── critical / atomic
│   └── OpenMP 5.2 任务依赖与 target
├── TBB（oneTBB） ⭐⭐⭐⭐
│   ├── parallel_for / parallel_reduce
│   ├── blocked_range 与 grain size
│   ├── task_arena 与组合性
│   ├── concurrent_hash_map
│   └── flow graph
├── C++ 标准并行 ⭐⭐⭐
│   ├── std::execution（C++17 执行策略）
│   ├── C++26 Senders/Receivers 展望
│   └── std::mdspan 与并行数据访问
├── 异构并行 ⭐⭐⭐⭐
│   ├── SYCL 概述
│   └── GPU offloading 边界
├── 框架选型决策 ⭐⭐⭐⭐
│   ├── 代码形态决定框架
│   ├── 负载均匀性决定调度
│   └── 依赖约束决定后端
├── 工程陷阱 ⭐⭐⭐⭐
│   ├── 假共享 / 过细粒度
│   ├── 嵌套并行 / 线程爆炸
│   └── 浮点归约不确定性
└── 并行性能分析 ⭐⭐⭐⭐
    ├── perf / 火焰图
    ├── Intel VTune / AMD uProf
    └── 加速比与并行效率度量

本章在课程中的位置：线程管理与互斥同步讲”多个长期线程如何协作”，原子操作与内存模型讲”跨线程可见性如何被 C++ 定义”。本章讨论另一类问题：当某个算法内部有大量相似计算时，如何把它拆成许多短任务并交给框架调度。线程管理关注生命周期。并行框架关注工作划分。两者都属于并发，但抽象层级不同。

19.1 并行化之前先问：算法真的有可并行部分吗 ⭐⭐⭐¶

这一章讨论的是什么层次的问题？¶

线程管理与互斥同步讲的是"多个长期线程如何协作"——Tracking 线程、Mapping 线程、LoopClosing 线程各自运行在独立的执行流中，通过队列和锁交换数据。原子操作与内存模型讲的是"跨线程可见性如何被 C++ 定义"——atomic 和 memory order 保证一个线程的写入能被另一个线程看到。

本章讨论一个**不同层次**的问题：当某个算法内部（比如 Tracking 的特征匹配、Mapping 的残差评估、点云下采样）有大量相似计算时，如何把它拆成许多短任务并交给框架调度。

直觉类比：线程管理与互斥同步像一家公司的部门划分——市场部、研发部、客服部各自独立运转，通过内部邮件（队列）协调。本章像一个部门内部的工作分配——研发部收到一个"评估 10 万个残差"的任务，组长把它拆成 8 份分给 8 个工程师同时做，做完后汇总结果。部门划分关注的是**模块间协作**，工作分配关注的是**单个任务的加速**。两者都属于并发，但抽象层级不同——混淆这两个层级是机器人系统并行设计中最常见的概念错误。

工程问题：机器人软件里很多慢点并不是同一种慢¶

一个 SLAM 或控制系统的性能瓶颈可能来自很多地方：

慢点	典型原因	适合的优化方向
点云逐点滤波慢	每个点独立处理	数据并行
最近邻批查询慢	每个查询点近似独立	数据并行或任务并行
后端线性求解慢	稀疏矩阵结构复杂	专用线性代数库
地图更新慢	共享哈希表写入多	分区、合并、并发容器
回环检测慢	数据库查询和几何验证混合	任务图或后台线程
ROS2 回调延迟大	线程调度和队列阻塞	执行器配置与实时路径隔离

如果把这些慢点都叫“需要多线程”，容易开错药。数据并行适合大量独立样本。任务并行适合几个不同阶段可以同时运行。向量化适合单个循环内部的 SIMD。算法替换适合复杂度本身过高的情况。

反面失败：把串行依赖强行套进并行循环¶

看一个看似简单的位姿更新循环：

Pose pose;
for (const auto& measurement : measurements) {
    pose = integrate(pose, measurement);
}

每一步都依赖上一步输出。如果强行并行：

#pragma omp parallel for
for (int i = 0; i < static_cast<int>(measurements.size()); ++i) {
    pose = integrate(pose, measurements[i]);
}

这段代码同时有两个问题：

多个线程同时读写 pose，产生数据竞争。
即使用锁保护 pose，积分顺序也不是原来的时间顺序。

这不是 OpenMP 的问题。这是算法依赖关系不允许直接并行。真正的改法可能是分段预积分，再按段归并。也可能是接受这部分串行，把并行预算放到特征提取、残差评估或最近邻查询上。

抽象不变量：并行循环的每次迭代必须有清楚的读写边界¶

判断一个循环能不能并行，先写出每次迭代的读写集合：

iteration i:
    read:  input[i], config, immutable_map
    write: output[i]

如果所有迭代只读共享不可变数据，并且写不同位置，就天然适合并行。例如点云逐点去畸变：

iteration i:
    read:  raw_points[i], imu_trajectory
    write: undistorted_points[i]

如果多个迭代写同一个对象，就必须继续分类：

iteration i:
    read:  residual[i]
    write: total_cost

这类写共享对象通常需要归约。归约不是“随便加锁”，而是把多个局部结果合并成一个全局结果。

如果每个迭代既读又写共享结构：

iteration i:
    read/write: voxel_hash_map

这时要考虑分区、线程本地容器、并发容器或两阶段合并。直接在循环里加一个大锁，往往会让并行版本比串行更慢。

规则推导：Amdahl 定律给并行加速设置上限¶

假设程序中比例为 \(p\) 的部分可以无限并行，剩余 \(1-p\) 必须串行。使用 \(N\) 个线程时，理想加速比为：

\[ S(N)=\frac{1}{(1-p)+\frac{p}{N}} \]

如果只有 80% 时间可并行：

线程数	理想加速比
2	1.67
4	2.50
8	3.33
无限多	5.00

这说明一个残酷事实：并行框架无法消除串行瓶颈。如果 SLAM 系统每帧 50ms，其中 20ms 花在线性求解、10ms 花在锁等待、20ms 花在点云处理，那么把点云处理并行到 5ms，整帧也只是从 50ms 到 35ms。继续优化点云处理，收益会迅速下降。

工程边界：吞吐提高不等于延迟降低¶

并行框架常常提高吞吐：

每秒处理更多点
每秒评估更多残差
每秒完成更多候选匹配

但机器人系统还关心延迟：

这一帧能不能在 30ms 内发布
控制指令能不能在 1ms 内计算
回调能不能避免长尾卡顿

如果并行任务启动开销、调度排队、线程抢占导致尾延迟变大，平均速度变快也可能不适合实时路径。本章讨论的是高性能并行框架，不等同于硬实时设计。硬实时约束会在实时约束与高性能数据传递单独展开。

代码验证：先建立串行基准¶

任何并行化都应从清晰的串行版本开始。下面用一个简单的残差评估作为基准：

#include <cmath>
#include <cstddef>
#include <vector>

struct Point3D {
    double x = 0.0;
    double y = 0.0;
    double z = 0.0;
};

double pointToPlaneResidual(const Point3D& p, const Point3D& n, double d) {
    return p.x * n.x + p.y * n.y + p.z * n.z + d;
}

double serialCost(const std::vector<Point3D>& points,
                  const Point3D& normal,
                  double d) {
    double cost = 0.0;
    for (const Point3D& p : points) {
        const double r = pointToPlaneResidual(p, normal, d);
        cost += r * r;
    }
    return cost;
}

串行版本的作用不是“保守”。它提供三个东西：

正确性参照。
性能基线。
并行划分的最小语义。

没有串行基准，后面的加速比和数值误差都没有意义。

本质洞察：并行化的本质不是"让代码跑在多个核心上"，而是**把一个计算的读写边界描述清楚，然后让调度器自由安排执行顺序**。如果读写边界不清楚，并行只会把串行的 bug 放大到 N 个线程上。

⚠️ 编程陷阱：在并行循环中使用全局静态变量 错误做法：循环体内读写 static 或文件域变量，认为"每次调用只跑一次应该没事"。现象：多线程并发执行时，静态变量被多个线程同时修改，产生不可复现的错误结果。 根本原因：static 变量的生命周期跨越所有调用，但 C++ 不会自动保护它在多线程下的一致性。 正确做法：把状态放进循环体内的局部变量，或显式使用 thread_local。

💡 概念误区：认为"并行化 = 多线程" 新手想法："我的代码用了 std::thread，所以已经是并行的了。" 实际上：std::thread 只是创建了一个线程。如果这个线程在等锁、等 I/O、等另一个线程，它就不是在并行计算。并行化是把工作拆分成可以同时执行的独立部分，而不是简单地创建线程。

🧠 思维陷阱：先并行化再测量 新手想法："这段代码看起来很慢，直觉告诉我应该并行化。" 实际上：瓶颈可能在内存带宽、锁竞争、算法复杂度或 I/O 等待上。不加测量就并行化，可能解决了不存在的问题，同时引入了新的同步 bug。 正确思维：先 profiling 找到真正的热点，确认热点是计算密集且可拆分的，然后才考虑并行。

练习¶

[分析题] 给定一个 SLAM 系统每帧耗时分布：特征提取 15ms、匹配 5ms、优化 25ms、发布 5ms。如果只并行化特征提取使其降到 5ms，整帧加速比是多少？如果把特征提取和匹配同时并行化到极限，Amdahl 定律给出的理论最大加速比是多少？
[代码题] 写一个函数，接受 std::vector<Point3D> 和一个变换矩阵，先写出串行版本，然后分析其读写集合，判断是否适合直接并行。
[设计题] 你有一个位姿链 p0 -> p1 -> p2 -> ... -> pn，其中 p_{i+1} = f(p_i, measurement_i)。这个计算能否直接并行？如果不能，有什么替代方案可以部分利用并行？

19.2 数据并行、任务并行、流水线并行与向量化 ⭐⭐⭐¶

计算模型的理论基础：为什么并行有不同形态¶

在深入讨论四种并行形态之前，有必要从计算模型的角度理解它们为什么存在、为什么不能互相替代。

并行计算的两个根本维度。任何并行程序都可以从两个正交维度来分析：（1）工作分解（work decomposition）——把总工作量切成小块的方式；（2）通信模式（communication pattern）——小块之间需要交换多少信息。这两个维度的组合决定了并行效率的理论上限。

数据并行的工作分解方式是”相同操作，不同数据”。100 万个点的坐标变换可以分给 8 个核心，每个核心处理 12.5 万个点，核心之间不需要任何通信——这是最理想的并行形态，通信开销为零。任务并行的工作分解方式是”不同操作，可能操作相同或不同的数据”。特征提取和描述子计算是不同的算法逻辑，它们可以同时执行，但可能需要交换中间结果——通信开销取决于任务之间的数据依赖。

为什么需要区分这些形态？ 因为不同形态对应不同的硬件利用模式和软件抽象。数据并行最容易映射到 SIMD 硬件和 GPU（CUDA基础与Thrust），因为所有执行单元执行相同指令。任务并行更适合多核 CPU 的 MIMD 架构，因为每个核心可以运行完全不同的代码路径。流水线并行是任务并行的特殊形式——任务之间有严格的时序依赖，前一个阶段的输出是后一个阶段的输入，但不同帧的不同阶段可以重叠执行。向量化则是最底层的并行——发生在单条指令内部，由硬件的 SIMD 单元实现。

这四种形态不是竞争关系，而是互补关系——一个优秀的机器人系统通常会同时使用多种。例如 ORB-SLAM3 的架构：Tracking/Mapping/LoopClosing 三个长期线程构成流水线并行；Tracking 内部的特征提取使用数据并行（OpenCV 的 parallel_for_）；Eigen 矩阵运算内部使用向量化；如果引入 GPU 加速，还会用到更大规模的数据并行。理解每种形态的适用条件和代价，是正确组合它们的前提。

从 work-span 模型理解并行效率的理论极限。并行算法理论中有一个基本模型叫做 work-span model（也叫 work-depth model），它用两个量刻画并行算法的本质特征：

Work \(W\)：算法在串行执行时的总操作数。这就是串行时间。
Span \(S\)（也叫 depth 或 critical path length）：如果有无限多处理器，算法仍然需要的最短时间——由最长的依赖链决定。

使用 \(P\) 个处理器时，并行执行时间 \(T_P\) 满足：

\[T_P \geq \max\left(\frac{W}{P},\ S\right)\]

这个下界有两个分量：\(W/P\) 是”把总工作平均分给 \(P\) 个处理器”的理想时间，\(S\) 是”即使有无限处理器也必须串行等待的时间”。并行度（parallelism） 定义为 \(W/S\)——它是使用更多处理器还能继续获得加速的理论上限。当 \(P \ll W/S\) 时，增加处理器能近似线性加速；当 \(P \gg W/S\) 时，额外处理器完全浪费。

这个模型如何指导实践？以 SLAM 残差计算为例：\(W = n \times c\)（\(n\) 个匹配对，每个耗时 \(c\)），\(S = c\)（所有匹配对完全独立，关键路径只有一个操作的长度）。并行度 \(W/S = n\)——如果有 10 万个匹配对，理论上可以用 10 万个处理器获得接近 10 万倍加速。这正是 GPU 数据并行高效的理论依据。再看位姿链积分：\(W = n \times c\)，但 \(S = n \times c\)（每一步依赖上一步），并行度 \(W/S = 1\)——无论多少处理器，都不可能加速。这不是框架的问题，而是算法本身的串行依赖决定的。

读到这里你可能会问：”work-span 模型和 Amdahl 定律是什么关系？” Amdahl 定律是 work-span 模型的一个特例——它假设算法可以清晰地分为”可并行部分”（work \(= p \cdot W\)，span \(= 0\)）和”必须串行部分”（work \(= (1-p) \cdot W\)，span \(= (1-p) \cdot W\)）。Work-span 模型更一般：它允许依赖关系呈任意 DAG 结构，不要求简单的”并行/串行”二分。

工程问题：不同并行形态解决不同层级的问题¶

机器人程序常把”并行”混成一个词。实际至少有四种常见形态：

类型	粒度	例子	主要工具
数据并行	大量同类元素	点云滤波、残差评估	OpenMP、TBB `parallel_for`
任务并行	几个不同任务	特征提取与描述子计算	TBB task、taskflow
流水线并行	阶段连续运行	Tracking、Mapping、LoopClosing	长期线程、队列
向量化	单指令多数据	Eigen 矩阵运算、SIMD 点运算	Eigen、编译器、SIMD intrinsic

OpenMP 和 TBB 最常处理数据并行。 taskflow 这类任务图框架更适合任务依赖。长期线程流水线已经在线程管理与互斥同步讲过。 Eigen 的表达式模板和 SIMD 已在 C++语言核心/Eigen基础与SLAM数学预备讨论。

从 Flynn 分类理解并行的本质¶

上面的四种并行形态并不是随意划分的。它们来自计算机体系结构领域的一个经典分类框架——Michael Flynn 在 1966 年提出的 Flynn 分类（Flynn's taxonomy）。Flynn 从两个维度观察计算系统：指令流的数量**和**数据流的数量，将所有计算架构分为四类：

分类	指令流	数据流	含义	典型硬件
SISD	单	单	传统串行处理器	经典单核 CPU
SIMD	单	多	一条指令同时操作多个数据	SSE/AVX、GPU warp
MISD	多	单	多条指令处理同一数据（罕见）	冗余容错系统
MIMD	多	多	多条指令处理多个数据	多核 CPU、集群

为什么这个分类对机器人工程师重要？ 因为它揭示了”并行”这个词背后的两个根本不同的加速机制：

SIMD（数据并行的硬件基础）：CPU 的 SIMD 单元（SSE 128 位、AVX 256 位、AVX-512 512 位）可以用一条指令同时处理 4 个、8 个甚至 16 个 float。这意味着一个点云坐标缩放循环 x[i] *= scale 如果数据对齐且连续，编译器可以把 8 次乘法合并成 1 条 vmulps 指令。这就是为什么缓存优化与数据布局强调 SoA 布局和数据对齐——它们直接决定 SIMD 能否发挥作用。GPU 的执行模型更进一步：一个 warp 中的 32 个线程以 SIMT（Single Instruction, Multiple Threads）方式执行，本质上也是 SIMD 的变体。

MIMD（任务并行和流水线并行的硬件基础）：多核 CPU 中每个核心独立取指、独立执行，属于典型的 MIMD。当 SLAM 系统同时运行 Tracking 线程和 Mapping 线程时，两个核心在执行完全不同的指令序列——这就是 MIMD。OpenMP 的 parallel for 也属于 MIMD：虽然每个线程执行”相似”的代码，但它们是独立的指令流，只不过恰好执行同一个函数的不同迭代。

**数据并行和任务并行的本质差异**在 Flynn 分类中变得清晰：数据并行更接近 SIMD 思维——同一个操作应用到大量数据元素上，追求的是每个元素的处理成本最小化。任务并行更接近 MIMD 思维——不同的操作同时执行，追求的是多个独立工作流的重叠。把数据并行的问题用任务并行的工具解决（比如为每个点创建一个 task），就像用 MIMD 模拟 SIMD，开销远大于收益。反过来，把任务并行的问题用数据并行的工具解决（比如把 Tracking 和 Mapping 塞进同一个 parallel_for），则根本行不通，因为两个阶段的逻辑完全不同。

**向量化和数据并行的关系**也可以从 Flynn 分类中理解：向量化是硬件层面的 SIMD，由编译器自动利用或程序员手动编写 intrinsic 实现，粒度在单条指令内部（一次处理 4-16 个元素）。数据并行是软件层面的”类 SIMD 思维”，由 OpenMP 或 TBB 在多个核心之间分发，粒度在线程级别（一次处理数千个元素的子集）。两者可以叠加：外层用 parallel_for 把 100 万个点分给 8 个核心，每个核心内部再用 SIMD 一次处理 8 个点——这就是现代高性能点云处理的典型结构。

读到这里你可能会问：”MISD 在机器人中有用吗？” 直接的 MISD 硬件很少见。但在软件层面，冗余容错系统（如三余度 IMU 处理器各自独立运行同一组传感器数据，再做投票表决）和某些流水线处理（同一数据经过多个不同的处理阶段）可以被视为 MISD 的软件变体。不过在本课程的语境中，数据并行（SIMD 思维）和任务并行（MIMD 思维）是最常用的两种。

反面失败：用任务图表达每个点¶

假设有 100 万个点要计算残差。如果为每个点创建一个任务图节点：

node_0 -> residual point 0
node_1 -> residual point 1
...
node_999999 -> residual point 999999

调度开销会淹没计算本身。任务图适合表达阶段依赖，不适合表达极细粒度元素。点云逐点处理更适合分块：

block 0: points [0, 4096)
block 1: points [4096, 8192)
...

每个任务处理一段连续数据。这样既减少调度开销，又改善缓存局部性。

抽象不变量：并行粒度要大到能覆盖调度成本¶

并行任务的总耗时大致可以写成：

\[ T_{\text{parallel}} \approx T_{\text{compute}}/N + T_{\text{schedule}} + T_{\text{sync}} + T_{\text{cache}} \]

其中：

\(T_{\text{schedule}}\) 是任务创建、分发、唤醒的成本。
\(T_{\text{sync}}\) 是锁、归约、屏障的成本。
\(T_{\text{cache}}\) 是缓存未命中、假共享、数据迁移成本。

当每个任务计算量很小，调度和同步就会占主导。这就是“线程越多越慢”的常见原因。

规则推导：粒度选择可以从每块耗时估算¶

如果一次点运算约 80ns，单点作为任务一定太细。如果每块 4096 点：

\[ 4096 \times 80\text{ns} \approx 327\mu s \]

这已经足以覆盖常见任务调度成本。实际数值依赖硬件、编译选项、缓存命中率和框架实现。但思路固定：不要让每个任务只做几条指令。

工程边界：并行和向量化可能互相影响¶

有些循环串行时可以被编译器自动向量化。加上复杂 lambda、分支、函数指针或虚函数调用后，向量化可能失效。如果一个循环本来靠 SIMD 很快，粗暴并行未必收益明显。

性能优化顺序通常是：

先确认算法复杂度合理。
再确认数据布局适合缓存。
再确认内层循环能向量化。
最后用多线程扩展到多个核心。

多线程不是第一步。它是把已经清楚的计算结构扩展到更多核心。

并行框架和编译器优化的关系，类似于高速公路和发动机的关系：发动机（向量化/算法优化）让每辆车跑得更快，高速公路（并行框架）让更多车同时通行。如果发动机有问题，修高速公路并不能让单辆车更快；反过来，如果只有一辆车，修再多车道也没有意义。

如果不区分这四种并行形态会怎样？一个常见的后果是：把本应通过向量化加速的内层循环用 parallel_for 拆分，结果调度开销远大于计算本身。另一个后果是：把本应通过任务图表达的阶段依赖，硬塞进数据并行循环，导致逻辑混乱且难以调试。

⚠️ 编程陷阱：parallel_for 粒度过细导致反向加速 错误做法：对一个只有 100 个元素、每个元素只需要 10ns 计算的循环使用 parallel_for。现象：并行版本比串行慢 2-5 倍。 根本原因：100 个元素的总计算量只有 1 微秒，而线程创建/唤醒/同步的开销通常在 10-100 微秒量级。调度成本远超计算本身。 正确做法：只对计算量足以覆盖调度开销的循环并行化。经验法则：每个任务的计算时间至少是调度成本的 10 倍以上。

💡 概念误区：认为"流水线并行 = 数据并行" 新手想法："Tracking 线程和 Mapping 线程同时在跑，这就是数据并行。" 实际上：这是流水线并行——不同阶段处理不同帧的数据。数据并行是同一个操作同时处理大量相同类型的数据元素。它们解决的问题层级完全不同：流水线关注吞吐量的持续性，数据并行关注单个阶段的计算密度。

练习¶

[分类题] 将以下任务分别归类为数据并行、任务并行、流水线并行或向量化：(a) 100 万个点的坐标变换；(b) 同时运行 ORB 提取和 IMU 预积分；(c) Tracking/Mapping/LoopClosing 三线程架构；(d) Eigen 矩阵乘法的 SIMD 加速。
[估算题] 一个点云变换循环每个点大约 80ns。如果调度开销约 50 微秒，至少需要多少个点才能让并行版本比串行快？
[设计题] 一个 SLAM 前端既需要并行处理点云（数据并行），又需要同时运行特征提取和回环检测（任务并行）。画出你的线程和任务分配方案，说明为什么这样划分。

代码验证：分块串行写法¶

在引入框架前，可以先把循环写成分块形式：

#include <algorithm>
#include <cstddef>
#include <vector>

template <class Func>
void forEachBlock(std::size_t n, std::size_t block_size, Func func) {
    for (std::size_t begin = 0; begin < n; begin += block_size) {
        const std::size_t end = std::min(begin + block_size, n);
        func(begin, end);
    }
}

void normalizeIntensities(std::vector<float>& intensity) {
    constexpr std::size_t kBlock = 4096;
    forEachBlock(intensity.size(), kBlock, [&](std::size_t begin, std::size_t end) {
        for (std::size_t i = begin; i < end; ++i) {
            intensity[i] = std::clamp(intensity[i], 0.0f, 1.0f);
        }
    });
}

这个结构对后续迁移很友好。 OpenMP 可以并行外层块。 TBB 可以把 [0,n) 交给 blocked_range。自定义线程池也可以按块分发。

19.3 OpenMP：把规则写进编译器指令 ⭐⭐⭐⭐¶

三大并行框架的设计哲学对比¶

在展开 OpenMP 的具体用法之前，值得从更高的视角理解 OpenMP、TBB 和 C++17 std::execution 这三种主流方案各自的设计哲学。它们解决的是同一个问题——"如何让 C++ 程序员方便地表达并行"——但选择了截然不同的设计路径，这些路径决定了它们各自的能力边界和最佳使用场景。

OpenMP：声明式并行（Declarative Parallelism）。OpenMP 的设计哲学是"最小侵入"——在已有串行代码上添加编译器指令（pragma），由编译器和运行时库负责线程创建、调度和同步。程序员声明"这个循环可以并行"，而不需要显式管理线程。这个设计决策有深远的后果：

优势：已有串行代码几乎不需要改动。去掉 pragma 就回到串行版本，方便调试。学习曲线极低——一个 #pragma omp parallel for 就能获得初步加速。
代价：并行语义隐藏在编译器指令中，IDE 和类型系统看不到它。pragma 不能跨编译单元传递。OpenMP 的运行时模型是"fork-join"——每个并行区域都隐式创建一组线程（或从线程池中取），区域结束时隐式 barrier 同步。这使得嵌套并行和跨库组合变得困难。
适用边界：适合对已有循环的快速并行化试验、科学计算中的规则数组处理、需要 Fortran/C/C++ 跨语言并行的场景。不适合需要精细控制任务依赖、动态任务创建或与其他 C++ 并发机制（std::async、协程）深度集成的场景。

TBB：组合式并行（Composable Parallelism）。Intel TBB（现在是 oneTBB）的设计哲学是"并行是 C++ 库级别的抽象"。并行语义通过 C++ 类型系统表达——blocked_range、parallel_for、parallel_reduce、task_arena 都是普通的 C++ 类和函数模板。这意味着并行操作可以像普通函数一样传递、组合和约束。

优势：组合性——一个库内部使用 TBB 并行化，不会与调用者自己的 TBB 或 OpenMP 并行冲突（通过 task_arena 隔离）。Work-stealing 调度器自动处理负载不均。并行操作是类型安全的——编译器能在使用错误时报告类型错误，而不是产生运行时 bug。
代价：API 比 pragma 复杂。简单循环的 TBB 写法比 OpenMP 冗长。需要链接 TBB 库（部署时多一个依赖）。
适用边界：适合库开发（需要与调用者的并行互不干扰）、负载不均匀的计算（work-stealing 比 static 调度高效得多）、需要在运行时动态控制并行度的场景。不适合极简单的均匀循环（pragma 更便捷）或需要 GPU 加速的场景。

C++17 std::execution：标准化并行（Standardized Parallelism）。C++17 引入了执行策略（execution policy），让标准算法支持并行执行：std::for_each(std::execution::par, ...), std::transform(std::execution::par_unseq, ...)。设计哲学是"并行应该是标准库的一等公民"——不需要第三方库，不需要编译器扩展，用标准 C++ 就能表达并行。

优势：无外部依赖。语法最简洁——只需在标准算法调用中添加一个执行策略参数。par_unseq 策略还允许编译器进行 SIMD 向量化。未来的 C++ 标准（C++23 的 std::mdspan、C++26 的 sender/receiver）会进一步扩展这个方向。
代价：当前实现的功能覆盖有限——只支持标准算法，不支持自定义归约、任务图或显式调度控制。不同编译器的实现质量差异大——GCC 的 libstdc++ 底层用 TBB，Clang 的 libc++ 支持仍不完整，MSVC 用自己的线程池。性能表现目前通常不如直接使用 TBB 或 OpenMP。
适用边界：适合标准算法能直接表达的场景（transform、reduce、sort、for_each）、追求代码可移植性和未来兼容性的项目。不适合需要自定义调度策略或当前编译器实现不成熟的场景。

三者的关系与选择策略：

维度	OpenMP	TBB	`std::execution`
抽象层级	编译器指令	C++ 库	C++ 标准库
学习成本	极低	中等	低
组合性	差（嵌套困难）	好（arena 隔离）	中等
调度策略	静态/动态/guided	work-stealing	实现定义
归约支持	reduction 子句	parallel_reduce	std::reduce
任务图	sections/task（有限）	task_group/flow_graph	不支持
GPU 扩展	target offloading	不直接支持	C++23 sender/receiver
部署依赖	编译器内置	libtbb.so	标准库

在机器人项目中，一个常见的实践是：对简单热点循环用 OpenMP 快速试验；对库级别的可复用并行代码用 TBB 确保组合安全；对标准算法能表达的操作用 std::execution 保持代码简洁。三者可以在同一个项目中共存。

工程问题：已有串行循环需要快速并行试验¶

OpenMP 的优势是低侵入。许多点云处理代码已经是 for 循环。如果迭代相互独立，加一条 pragma 就能做快速试验：

#pragma omp parallel for
for (int i = 0; i < n; ++i) {
    output[i] = process(input[i]);
}

这非常适合教学、原型和已有 C++ 工程中的局部热点。它的代价是并行语义隐藏在编译器指令里。如果团队成员没有认真看 pragma，可能误以为这只是普通循环。

反面失败：在并行循环里写共享容器¶

错误写法：

#include <vector>

struct Point {
    float x = 0.0f;
    float y = 0.0f;
    float z = 0.0f;
};

std::vector<Point> filterPositiveX(const std::vector<Point>& points) {
    std::vector<Point> result;

    #pragma omp parallel for
    for (int i = 0; i < static_cast<int>(points.size()); ++i) {
        if (points[i].x > 0.0f) {
            result.push_back(points[i]);
        }
    }

    return result;
}

std::vector::push_back 会修改 size、capacity 和元素存储。多个线程同时调用会产生数据竞争。即使用 critical 包住 push_back：

#pragma omp critical
result.push_back(points[i]);

循环也可能因为每个保留点都争抢同一把锁而变慢。更好的做法是两阶段：

每个线程写自己的局部结果。
循环结束后合并。

抽象不变量：OpenMP 不改变 C++ 对象的线程安全性质¶

OpenMP 负责创建线程、分配迭代和同步屏障。它不会让普通 C++ 容器自动变成线程安全。它也不会修复悬空引用、迭代器失效、非原子共享写入。

并行循环里的变量要逐个判断：

变量类型	默认风险	常见处理
输入数组	多线程只读通常安全	保持不可变
输出数组	每个线程写不同下标安全	预分配
累加标量	共享写不安全	`reduction`
临时对象	每次迭代独立安全	放进循环体
容器追加	共享结构修改不安全	局部容器后合并
配置对象	只读安全	`const` 引用

规则推导：`parallel for` 的基本语义¶

OpenMP 并行循环大致可以理解为：

进入 parallel region
把迭代空间划分给多个线程
每个线程执行自己的迭代子集
循环末尾默认有 barrier
离开 parallel region

默认屏障很重要。如果后续代码依赖所有输出已经完成，默认行为正合适。如果某些场景不需要等待，可以使用 nowait，但那会把同步责任交给程序员。

代码验证：OpenMP 并行残差评估¶

#include <cmath>
#include <vector>

struct Point3D {
    double x = 0.0;
    double y = 0.0;
    double z = 0.0;
};

double residual(const Point3D& p, const Point3D& n, double d) {
    return p.x * n.x + p.y * n.y + p.z * n.z + d;
}

double openmpCost(const std::vector<Point3D>& points,
                  const Point3D& normal,
                  double d) {
    double cost = 0.0;

    #pragma omp parallel for reduction(+:cost)
    for (int i = 0; i < static_cast<int>(points.size()); ++i) {
        const double r = residual(points[static_cast<std::size_t>(i)], normal, d);
        cost += r * r;
    }

    return cost;
}

这里 reduction(+:cost) 的含义不是“每次加法都加锁”。更接近：

每个线程有一个私有 cost
线程内部串行累加
并行区域结束时把私有 cost 合并

这通常比 critical 快很多。

`schedule(static)`：均匀任务的低开销调度¶

如果每个迭代耗时差不多，静态划分最简单：

#pragma omp parallel for schedule(static)
for (int i = 0; i < n; ++i) {
    output[i] = processUniform(input[i]);
}

典型适用场景：

场景	原因
强度归一化	每个点计算量几乎相同
坐标变换	每个点一次矩阵乘法
简单阈值过滤第一阶段	判断成本均匀
预计算投影	每个点固定公式

静态调度的好处是开销低、数据连续性好。坏处是无法处理严重负载不均。

调度策略的理论分析：static、dynamic 与 guided 的权衡空间¶

调度策略（schedule）的选择不是一个凭经验猜测的问题——它有清晰的理论分析框架。三种 OpenMP 调度策略本质上对应了负载均衡理论中的三种经典方案，每种都在**调度开销**和**负载均衡质量**之间做出不同的权衡。

static 调度的形式化分析。schedule(static) 在编译时或运行时初始化时将 \(N\) 个迭代均匀分给 \(P\) 个线程：线程 \(k\) 处理迭代 \([k \cdot \lceil N/P \rceil,\ \min((k+1) \cdot \lceil N/P \rceil, N))\)。这个分配是确定性的——给定相同的 \(N\) 和 \(P\)，每次运行的分配完全一致。

假设每个迭代的执行时间为随机变量 \(X_i\)，均值 \(\mu\)，方差 \(\sigma^2\)。线程 \(k\) 的总执行时间 \(T_k = \sum_{i \in \text{block}_k} X_i\)。由中心极限定理，当块大小足够大时，\(T_k\) 近似正态分布。并行执行时间 \(T_{\text{parallel}} = \max_k T_k\)。

当所有 \(X_i\) 相同（\(\sigma = 0\)，均匀负载）时，\(T_{\text{parallel}} = N\mu/P\)——完美线性加速。当 \(\sigma > 0\) 时，\(T_{\text{parallel}}\) 取决于 \(P\) 个正态随机变量的最大值的期望，这随 \(P\) 增加而增大——线程越多，最慢的那个线程越可能显著慢于平均。具体来说，\(P\) 个独立正态变量的最大值期望大约为 \(\mu + \sigma \sqrt{2 \ln P} / \sqrt{N/P}\)。

这个分析的实际含义：如果迭代耗时的变异系数（\(\sigma/\mu\)）很小（比如 < 0.1），static 调度下的负载不均衡可以忽略。但如果变异系数很大（比如最近邻搜索中某些查询点需要 10 倍于平均的时间），static 调度会导致严重的"长尾线程"问题——一个线程的总耗时可能比其他线程大几倍，所有其他线程都在空等。

dynamic 调度的机制与代价。schedule(dynamic, chunk) 使用一个全局原子计数器作为任务分发器。每个线程每次从计数器领取 chunk 个迭代，完成后再来领取。这个机制天然实现了负载均衡——先完成的线程会领取更多工作，不会空等。

但 dynamic 调度有两个代价：（1）原子操作开销——每次领取都需要一次原子 fetch-add，在高竞争下可能需要 50-200 纳秒。如果 chunk 太小（比如 1），总共需要 \(N\) 次原子操作，这个开销可能超过计算本身。（2）缓存局部性损失——不同线程领取的迭代范围不连续，预取器无法预测下一批数据在哪里，L1/L2 cache hit rate 下降。

chunk 大小的选择是 dynamic 调度的关键参数。chunk 太小：调度开销占主导。chunk 太大：接近 static 调度，负载均衡失效。最优 chunk 大致满足：单个 chunk 的计算时间应远大于一次原子操作的开销（至少 10 倍以上），但又要足够小以允许有意义的负载再分配。

guided 调度：两者的折中。schedule(guided, min_chunk) 是一个自适应策略：每次领取的块大小从"剩余迭代数 / 线程数"开始，随着剩余迭代减少而逐步缩小，但不低于 min_chunk。早期分配的大块利用缓存局部性，后期分配的小块实现负载均衡——兼顾了 static 和 dynamic 的优点。

guided 的块大小序列大致为：\(b_k \approx \frac{N_{\text{remaining}}}{P}\)，其中 \(N_{\text{remaining}}\) 是剩余未分配的迭代数。这意味着前几批块很大（接近 \(N/P^2\)），后面的块越来越小。数学上可以证明，guided 调度的负载不均衡上界为 \(O(P \cdot \text{min\_chunk})\)——如果 min_chunk 设得合理，这比 static 好很多，同时原子操作次数远少于 schedule(dynamic, 1)。

三种调度策略的决策框架：

特性	static	dynamic,chunk	guided,min
原子操作次数	0（编译时确定）	\(N/\text{chunk}\)	\(\approx P \cdot \ln(N/P)\)
负载均衡	完全取决于迭代均匀性	好（chunk 足够小时）	中等偏好
缓存局部性	最好（连续块）	取决于 chunk 大小	前期好，后期差
确定性	完全确定	不确定	不确定
最佳场景	均匀负载	严重不均匀负载	中度不均匀负载

在 SLAM 工程中的映射：点云坐标变换（均匀）用 static；KD-Tree 最近邻查询（极度不均匀）用 dynamic；体素滤波中的点到体素映射（中度不均匀）用 guided 或 dynamic。但最终选择应该基于 profiling 验证，而不是理论预测——因为实际的缓存行为、NUMA 效应和操作系统调度干扰难以精确建模。

`schedule(dynamic)`：不均匀任务的负载均衡¶

如果每个迭代耗时差异很大，动态调度更合适：

#pragma omp parallel for schedule(dynamic, 64)
for (int i = 0; i < n; ++i) {
    output[i] = processVariableCost(input[i]);
}

例如最近邻搜索里，不同查询点附近地图密度不同。某些点很快找到邻居，某些点需要检查更多节点。动态调度可以让先完成的线程继续领取新的块。

代价是调度开销更高，数据局部性也可能变差。块大小 64 不是固定答案。它需要通过测量选择。

`num_threads`：线程数不是越多越好¶

OpenMP 可以显式指定线程数：

#pragma omp parallel for num_threads(4)
for (int i = 0; i < n; ++i) {
    output[i] = process(input[i]);
}

但线程数应该来自系统预算，而不是 CPU 核数的机械复制。机器人系统里，CPU 同时服务：

传感器驱动。
ROS2 执行器。
Tracking。
Mapping。
控制循环。
日志与可视化。

如果每个模块都使用“全部核心”，系统会过度订阅。表面上每个模块都在并行，实际上所有线程都在抢 CPU。

工程边界：OpenMP 与异常¶

不要让异常跨出 OpenMP 并行区域。不同编译器和运行时的行为细节需要查对应文档。更稳妥的模式是在线程内部捕获，记录错误标志，并在并行区域外处理。

#include <atomic>
#include <exception>
#include <mutex>

std::exception_ptr first_error;
std::mutex error_mutex;
std::atomic<bool> failed{false};

#pragma omp parallel for
for (int i = 0; i < n; ++i) {
    if (failed.load(std::memory_order_relaxed)) {
        continue;
    }

    try {
        processIndex(i);
    } catch (...) {
        std::lock_guard<std::mutex> lock(error_mutex);
        if (!first_error) {
            first_error = std::current_exception();
        }
        failed.store(true, std::memory_order_relaxed);
    }
}

if (first_error) {
    std::rethrow_exception(first_error);
}

这不是零开销写法。但它表达了一个重要边界：并行框架不应让异常传播语义变得含糊。

OpenMP 的 pragma 模式和 C 语言的宏有相似之处：它们都在编译器看见你的代码之前改变语义。宏改变的是文本替换，pragma 改变的是循环调度。两者的共同风险是**语义隐藏**——读代码的人如果不仔细看 pragma 行，可能完全不知道这个循环是并行的。

如果 OpenMP 不做任何变量默认分类会怎样？每个变量都需要程序员手动声明 shared 或 private，代码会变得极其冗长。但反过来，OpenMP 的"聪明默认"（循环变量 private、其他 shared）也会让人忘记显式思考每个变量的归属。这就是为什么很多项目在复杂循环中使用 default(none) —— 强制程序员为每个变量做出显式决定。

⚠️ 编程陷阱：忘记 reduction 子句导致数据竞争 错误做法：#pragma omp parallel for 后直接写 cost += r * r;，没有加 reduction(+:cost)。现象：结果每次运行不同，有时接近正确值，有时偏差很大。 根本原因：多个线程同时读-改-写同一个 double，产生数据竞争。由于 double 的写入在某些架构上不是原子操作，中间值可能被撕裂。 正确做法：使用 reduction(+:cost) 让每个线程维护私有副本，最后合并。

💡 概念误区：认为 OpenMP 让容器自动线程安全 新手想法："我加了 #pragma omp parallel for，框架应该会处理好线程安全。" 实际上：OpenMP 只负责循环调度和同步屏障。它不会修改 std::vector、std::map 或任何 C++ 容器的线程安全性质。在并行循环里对共享容器做 push_back、insert、erase 仍然是未定义行为。

🧠 思维陷阱：认为 schedule(dynamic) 总是比 static 好 新手想法："dynamic 调度能自动均衡负载，为什么不总是用 dynamic？" 实际上：dynamic 调度有更高的运行时开销——每次领取新块都需要原子操作和缓存同步。对于均匀负载，static 的零开销调度通常更快。选择调度策略应该基于负载分布的测量，而不是"dynamic 听起来更高级"。 正确思维：均匀负载用 static，不均匀负载用 dynamic，不确定时先用 static 再看 profiling。

练习¶

[调试题] 下面的代码有什么问题？修复它。#pragma omp parallel for / for (int i = 0; i < n; ++i) { results.push_back(compute(input[i])); }
[性能题] 一个最近邻搜索循环中，不同查询点的搜索时间差异可达 10 倍。应该选择 schedule(static) 还是 schedule(dynamic, 64)？解释原因，并说明 64 这个块大小应该如何调整。
[跨章综合题] 结合线程管理与互斥同步的线程生命周期和本节的 OpenMP 线程模型，解释为什么 OpenMP 并行区域内的线程不需要手动 join，而 std::thread 必须 join 或 detach。

19.4 OpenMP 归约：不只是把 `+=` 变安全 ⭐⭐⭐⭐¶

工程问题：残差、Hessian、统计量都需要聚合¶

SLAM 和优化里到处都是归约：

聚合量	来源	合并方式
总 cost	每个残差块	加法
有效点数量	每个匹配结果	整数加法
最大残差	每个残差	max
Hessian	每个雅可比块	矩阵加法
梯度向量	每个雅可比块	向量加法
体素质心	每个点	sum 与 count

归约的核心是“先局部，再合并”。它同时解决线程安全和性能问题。

反面失败：用 `critical` 做每个点的 Hessian 累加¶

错误模式：

#pragma omp parallel for
for (int i = 0; i < n; ++i) {
    Eigen::Matrix<double, 6, 6> H_i = computeHessian(i);
    Eigen::Matrix<double, 6, 1> b_i = computeGradient(i);

    #pragma omp critical
    {
        H += H_i;
        b += b_i;
    }
}

每个点都进入临界区。如果 computeHessian 很轻，锁竞争会成为主要耗时。更好的结构是每个线程维护局部 H_local 和 b_local，最后再合并。

抽象不变量：归约操作应尽量满足结合律¶

理想归约操作满足：

\[ (a \oplus b) \oplus c = a \oplus (b \oplus c) \]

整数加法在不溢出的数学模型下满足。浮点加法不严格满足，因为舍入误差依赖顺序：

(1e16 + -1e16) + 1 = 1
1e16 + (-1e16 + 1) = 0

并行归约会改变合并顺序。因此浮点结果与串行版本有微小差异是正常的。教学和测试中不要要求逐 bit 完全一致，除非专门设计确定性归约。

规则推导：矩阵归约的两阶段实现¶

OpenMP 对标量归约支持很好。对 Eigen 小矩阵，更清楚的写法是手动线程本地累加。

#include <Eigen/Dense>
#include <omp.h>
#include <vector>

struct NormalEquation {
    Eigen::Matrix<double, 6, 6> H = Eigen::Matrix<double, 6, 6>::Zero();
    Eigen::Matrix<double, 6, 1> b = Eigen::Matrix<double, 6, 1>::Zero();
    double cost = 0.0;
    int count = 0;
};

NormalEquation openmpNormalEquation(int n) {
    const int threads = omp_get_max_threads();
    std::vector<NormalEquation> local(static_cast<std::size_t>(threads));

    #pragma omp parallel
    {
        const int tid = omp_get_thread_num();
        NormalEquation& acc = local[static_cast<std::size_t>(tid)];

        #pragma omp for schedule(static)
        for (int i = 0; i < n; ++i) {
            const auto item = computeItem(i);
            acc.H.noalias() += item.H;
            acc.b.noalias() += item.b;
            acc.cost += item.cost;
            acc.count += item.count;
        }
    }

    NormalEquation total;
    for (const NormalEquation& part : local) {
        total.H.noalias() += part.H;
        total.b.noalias() += part.b;
        total.cost += part.cost;
        total.count += part.count;
    }
    return total;
}

这段代码有一个微妙点：local 中相邻元素可能落在同一 cache line。如果线程频繁写自己的 NormalEquation，可能发生假共享。可以用 padding 或每个线程分配独立对象缓解。

工程边界：可重复性比极限速度更重要的场景¶

某些场景要求结果尽量可重复：

教学单元测试。
回归测试。
离线 benchmark。
论文实验复现。
安全策略验证。

这时可以牺牲一点速度，固定归约顺序：

每个块内部串行累加
块结果按块编号排序
主线程按固定顺序合并

这样并行部分仍然加速大部分计算，最终合并顺序保持确定。

代码验证：确定性分块归约¶

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <vector>

struct BlockSum {
    std::size_t begin = 0;
    double value = 0.0;
};

double deterministicBlockSum(const std::vector<double>& values,
                             std::size_t block_size) {
    const std::size_t blocks =
        (values.size() + block_size - 1) / block_size;
    std::vector<BlockSum> partial(blocks);

    #pragma omp parallel for schedule(static)
    for (int b = 0; b < static_cast<int>(blocks); ++b) {
        const std::size_t begin = static_cast<std::size_t>(b) * block_size;
        const std::size_t end = std::min(begin + block_size, values.size());
        double local = 0.0;
        for (std::size_t i = begin; i < end; ++i) {
            local += values[i];
        }
        partial[static_cast<std::size_t>(b)] = BlockSum{begin, local};
    }

    double total = 0.0;
    for (const BlockSum& p : partial) {
        total += p.value;
    }
    return total;
}

这里并行调度不会改变最终块合并顺序。块内部的顺序也固定。它仍然不等于高精度求和。如果需要更小误差，可以引入 Kahan 求和或 pairwise summation。

归约操作的本质和数据库中的聚合函数（SUM、MAX、COUNT）是一样的：都是把大量局部结果合并成一个全局结果。数据库通过分区并行计算再合并来加速聚合查询，并行归约用的是完全相同的策略。

如果不使用两阶段归约，而是每个线程直接用 atomic 累加会怎样？对于整数计数，atomic 性能可以接受。但对于 double 累加，atomic 通常需要 CAS 循环实现，在高竞争场景下性能极差——每个线程大部分时间都在重试 CAS，而不是在计算。两阶段归约把竞争从 N 个线程降低到合并阶段的 T 个线程（T 是线程数），这通常减少了 1000 倍以上的竞争。

⚠️ 编程陷阱：线程本地累加器的假共享 错误做法：std::vector<NormalEquation> local(threads); 中，相邻元素可能位于同一 cache line。现象：增加线程数后加速比不升反降，CPU 利用率显示各核心都很忙但吞吐低。 根本原因：多个线程高频写相邻内存地址，导致 cache line 在核心之间反复传递（false sharing），每次写操作都触发缓存一致性协议。 正确做法：对线程本地累加器使用 alignas(std::hardware_destructive_interference_size) 或手动添加 padding，确保不同线程的数据位于不同 cache line。

💡 概念误区：认为浮点归约的顺序差异是 bug 新手想法："并行版本和串行版本的 cost 不完全一样，一定是并行代码写错了。" 实际上：浮点加法不满足严格结合律。(a+b)+c 和 a+(b+c) 在 IEEE 754 下可能给出不同结果。并行归约改变了加法顺序，因此结果与串行版本有微小差异是数学必然，不是 bug。差异通常在 \(10^{-12}\) 到 \(10^{-9}\) 量级。

练习¶

[实现题] 为 Eigen 6x6 矩阵实现一个两阶段并行归约：每个线程维护局部 H_local 和 b_local，循环结束后按固定顺序合并。确保线程本地结构不发生假共享。
[分析题] 如果并行归约使用 critical 保护每次累加，而每次累加只需要 20ns，但 critical 的锁开销是 200ns，那么 8 线程并行后预期加速比是多少？解释为什么 reduction 子句能避免这个问题。
[设计题] 设计一个确定性分块归约方案，使得无论线程数和调度顺序如何变化，最终结果的浮点值始终一致。说明这会牺牲什么性能。

19.5 TBB：把并行当作 C++ 库组合 ⭐⭐⭐⭐¶

工程问题：复杂 C++ 工程需要比 pragma 更强的组合性¶

OpenMP 的优势是简单。 TBB 的优势是组合性。它以 C++ 库形式提供并行算法、任务调度、并发容器和受控并行域。

这很适合现代机器人 C++ 项目：

算法已经用模板、lambda、policy 组织。
需要在库内部提供串行、OpenMP、TBB 多种策略。
需要把并行算法作为普通函数对象传递。
需要控制某一段代码的最大并行度。
需要与其他 C++ 库在同一进程内共存。

反面失败：手写固定分块线程池¶

很多项目会先写一个简单分块：

for (int t = 0; t < num_threads; ++t) {
    launchThread([&, t] {
        const int begin = t * n / num_threads;
        const int end = (t + 1) * n / num_threads;
        for (int i = begin; i < end; ++i) {
            process(i);
        }
    });
}

如果每个迭代成本完全均匀，这样能工作。但最近邻查询、体素插入、鲁棒核残差筛选都可能负载不均。某些线程早早完成，另一些线程还在处理复杂块。总耗时由最慢线程决定。

TBB 的调度器会把任务拆成可窃取的块，让空闲线程继续执行剩余工作。这不是魔法。它的本质是动态负载均衡。

深入理解 work-stealing：为什么 TBB 比手写分块更灵活¶

TBB 的核心调度算法叫做 work-stealing（工作窃取），它是并行调度领域最重要的算法之一，值得深入理解。

为什么需要 work-stealing？ 考虑一个最简单的并行策略：把 N 个任务平均分给 P 个线程，线程 k 处理第 [k*N/P, (k+1)*N/P) 段。这就是 OpenMP schedule(static) 的做法。当所有任务耗时相同时，这个策略接近最优——没有调度开销，数据局部性也好。但现实中，SLAM 系统的任务耗时往往极不均匀：某些体素中有 5 个点，某些体素有 500 个点；某些查询点附近地图稀疏，搜索几步就结束，另一些查询点附近地图密集，需要遍历大量候选。如果用静态分块，最慢的线程决定总耗时，其他线程全在空等——这就是**负载不均衡（load imbalance）**问题。

work-stealing 的基本思想：每个线程维护一个本地双端队列（deque），自己的任务从队列底部取出执行。当一个线程的队列为空（它完成了自己的所有任务），它会**随机选择另一个线程**，从那个线程的队列顶部窃取任务来执行。这个看似简单的策略有深刻的理论保证。

具体过程如下：

初始：主线程把整个迭代范围 [0, N) 作为一个大任务放入自己的队列。
分裂：当线程从队列取出一个任务时，如果任务范围大于 grainsize（最小粒度），它会把范围一分为二——执行一半，把另一半放回队列。这使得队列中总有"足够大"的任务等待被执行或被窃取。
执行：线程处理自己队列底部的小范围任务。由于总是先处理最近放入的子任务，这保持了**时间局部性**（最近切分的数据更可能还在缓存中）。
窃取：空闲线程从另一个线程的队列**顶部**窃取。窃取到的通常是较早放入的、较大的任务块。这个不对称设计（自己从底部取、别人从顶部偷）减少了竞争：正常执行和窃取操作发生在队列的不同端，大多数时候不需要同步。

为什么随机窃取而不是确定性调度？ 这个问题值得深入思考。确定性调度（如 OpenMP schedule(guided)，每次取剩余范围的固定比例）需要一个共享计数器来协调所有线程——这个计数器在高线程数下成为竞争热点。随机窃取则完全去中心化：每个线程独立决策，不需要全局状态。数学上可以证明，随机 work-stealing 的期望总执行时间为 \(T_1/P + O(T_\infty)\)，其中 \(T_1\) 是串行执行时间，\(P\) 是处理器数量，\(T_\infty\) 是关键路径长度（最长的依赖链）。这意味着只要关键路径不太长，work-stealing 能接近理想的线性加速。

work-stealing 与 OpenMP dynamic 的对比：

特性	OpenMP `schedule(dynamic, chunk)`	TBB work-stealing
调度方式	集中式：从共享队列领取固定大小块	分布式：每线程本地队列 + 随机窃取
竞争点	共享队列的原子计数器	只在窃取时竞争（概率较低）
任务粒度	固定 chunk 大小	自适应分裂（大任务自动变小）
缓存友好度	取决于 chunk 大小和数据分布	倾向于处理本地连续数据
嵌套并行支持	容易导致线程爆炸	自然支持，复用同一线程池
适用场景	简单循环的负载均衡	复杂递归并行、嵌套并行、异构任务

work-stealing 在机器人项目中的实际影响：考虑一个点云体素下采样任务——体素内点数分布高度不均匀（室内墙面体素可能有几百个点，空旷区域体素可能只有几个点）。用静态分块，某些线程处理密集区域耗时是稀疏区域的 50 倍，整体加速比远低于线程数。用 TBB work-stealing，密集区域的任务在执行过程中被分裂成小块，空闲线程从其他线程窃取这些小块继续处理，最终所有线程几乎同时完成。这种自适应性是 TBB 在不均匀负载场景下显著优于静态分块的根本原因。

读到这里你可能会问："既然 work-stealing 这么好，为什么不总是用 TBB？" 因为 work-stealing 有自己的开销：双端队列维护、随机选择目标线程、窃取失败时的重试。对于均匀负载的简单循环（比如点云缩放 x[i] *= s），OpenMP schedule(static) 的零调度开销反而更优。选择调度策略的正确方式不是"哪个更高级"，而是"我的任务负载分布是什么样的"。

抽象不变量：把迭代空间交给框架，而不是把线程编号写死¶

TBB 的常见写法：

#include <tbb/parallel_for.h>
#include <tbb/blocked_range.h>

void tbbProcess(std::size_t n) {
    tbb::parallel_for(tbb::blocked_range<std::size_t>(0, n),
                      [&](const tbb::blocked_range<std::size_t>& r) {
        for (std::size_t i = r.begin(); i != r.end(); ++i) {
            processIndex(i);
        }
    });
}

程序员描述的是“如何处理一个范围”。框架决定如何切分范围、如何调度任务。这比写死线程编号更可组合。

规则推导：`blocked_range` 的分裂模型¶

blocked_range 代表一个半开区间 [begin, end)。 TBB 可以把大范围递归分裂成小范围。每个任务处理一个范围。

[0, 1024)
  -> [0, 512), [512, 1024)
  -> [0, 256), [256, 512), ...

粒度由 range 和调度器共同决定。程序员可以传入 grainsize：

tbb::blocked_range<std::size_t>(0, n, 4096)

grainsize 表达的是“不要把任务切得太小”。它不是每个任务的严格大小。

代码验证：TBB 并行残差评估¶

#include <tbb/blocked_range.h>
#include <tbb/parallel_reduce.h>
#include <vector>

struct Point3D {
    double x = 0.0;
    double y = 0.0;
    double z = 0.0;
};

double residual(const Point3D& p, const Point3D& n, double d) {
    return p.x * n.x + p.y * n.y + p.z * n.z + d;
}

double tbbCost(const std::vector<Point3D>& points,
               const Point3D& normal,
               double d) {
    return tbb::parallel_reduce(
        tbb::blocked_range<std::size_t>(0, points.size(), 4096),
        0.0,
        [&](const tbb::blocked_range<std::size_t>& r, double local) {
            for (std::size_t i = r.begin(); i != r.end(); ++i) {
                const double e = residual(points[i], normal, d);
                local += e * e;
            }
            return local;
        },
        [](double a, double b) {
            return a + b;
        });
}

这段代码把三个概念分开：

范围如何表示。
每个范围如何计算局部结果。
两个局部结果如何合并。

这比隐式 pragma 更啰嗦。但在复杂库代码中，这种显式性有价值。

`parallel_for`：没有归约时更简单¶

#include <tbb/parallel_for.h>
#include <vector>

void transformPoints(const std::vector<Point3D>& input,
                     std::vector<Point3D>& output,
                     const Eigen::Matrix4d& T) {
    output.resize(input.size());

    tbb::parallel_for(std::size_t{0}, input.size(), [&](std::size_t i) {
        output[i] = transformOne(input[i], T);
    });
}

这个例子安全的关键不是 TBB。关键是每个迭代只写 output[i]。如果改成 output.push_back(...)，仍然不安全。

`task_arena`：限制局部并行度¶

复杂系统里，库函数内部可能使用 TBB。如果上层也使用 TBB，嵌套并行可能导致过度订阅。 TBB 提供受控并行域：

#include <tbb/global_control.h>
#include <tbb/task_arena.h>

void runMappingWithLimitedParallelism() {
    tbb::task_arena arena(4);
    arena.execute([&] {
        runParallelMappingStep();
    });
}

全局限制也可以使用 global_control：

tbb::global_control limit(
    tbb::global_control::max_allowed_parallelism,
    4);
runSystem();

具体 API 名称和行为以所用 TBB 版本官方文档为准。教学重点是：并行度是系统资源，不是单个函数的私有决定。

并发容器：降低锁粒度，不消除设计责任¶

TBB 提供并发容器，例如并发哈希表、并发向量等。它们可以减少手写锁。但并发容器不等于业务不变量自动正确。

例如体素地图插入：

point -> voxel key
voxel key -> voxel accumulator
accumulator 更新 sum 和 count

即使 map 是并发的，单个 voxel accumulator 的更新也要定义清楚：

是否允许多个线程同时更新同一 voxel？
更新 sum 和 count 是否必须一致？
是否需要固定输出顺序？
是否允许近似统计？

容器只解决一部分同步。算法不变量仍然由你负责。

TBB 和 OpenMP 的关系，类似于 C++ 标准库和 C 语言宏的关系：TBB 把并行语义编码在类型系统中（blocked_range、parallel_reduce），而 OpenMP 把并行语义编码在编译器指令中（#pragma）。类型系统的优势是可以组合、传递和约束；指令的优势是侵入性低、上手快。两者不是替代关系，而是适合不同场景。

本质洞察：TBB 的 blocked_range + parallel_reduce 实际上在做一件事：把"如何处理一段数据"和"如何合并两段结果"分离。这个分离正是函数式编程中 map-reduce 范式的体现——你定义局部操作和合并操作，框架决定怎么分割和调度。

⚠️ 编程陷阱：TBB parallel_for 的 lambda 捕获悬空引用 错误做法：在 parallel_for 的 lambda 中捕获局部变量的引用，而该变量在并行区域结束前被销毁。现象：偶发崩溃或结果错误，在 Debug 模式下可能不复现。 根本原因：TBB 的任务调度可能在任意时间点执行 lambda，如果捕获的引用指向已销毁的栈变量，就是悬空引用。 正确做法：确保被捕获的对象生命周期覆盖整个并行区域，或按值捕获小对象。

🧠 思维陷阱：认为 TBB 自动负载均衡就不需要考虑粒度 新手想法："TBB 有 work-stealing，所以我不需要设置 grainsize。" 实际上：work-stealing 解决的是线程之间的负载不均，但如果每个任务太小（grainsize 太细），stealing 本身的开销就会成为瓶颈。grainsize 决定了"任务能被切多碎"的下界——设太小会导致过多任务切换，设太大会让 stealing 失去意义。 正确思维：用 profiling 找到 grainsize 的平衡点。起始值可以参考"每个任务至少 100 微秒计算量"。

练习¶

[对比题] 用 OpenMP 和 TBB 分别实现同一个点云距离过滤。比较两者的代码长度、可读性和策略可切换性。
[设计题] 如果一个库需要同时支持串行、OpenMP 和 TBB 三种后端，task_arena 应该由库内部创建还是由调用者传入？解释各自的优缺点。
[性能题] 一个 TBB parallel_reduce 使用默认 grainsize 处理 10000 个元素，每个元素计算 50ns。估算调度开销是否可能超过计算本身，并建议合适的 grainsize。

19.6 taskflow 与任务图：表达阶段依赖 ⭐⭐⭐⭐¶

工程问题：SLAM 流程不是所有任务都能同时开始¶

一个简化的 LiDAR SLAM 前端可能有这些阶段：

读取点云
去畸变
体素下采样
最近邻匹配
残差构建
位姿优化
地图更新
发布结果

有些阶段必须按顺序。有些阶段可以并行。例如点云去畸变和 IMU 预积分可能在不同数据上并行。描述子计算和候选回环检索也可能并行。

如果只用 parallel_for，很难表达阶段依赖。任务图框架的价值在这里。

反面失败：用一串手写 future 拼依赖¶

错误倾向：

auto a = std::async(readCloud);
auto b = std::async([&] { return undistort(a.get()); });
auto c = std::async([&] { return downsample(b.get()); });
auto d = std::async([&] { return match(c.get()); });

这段代码看起来异步，实际可能每一步都在等待前一步。依赖关系藏在 lambda 里的 get() 调用中。调试、可视化和取消都很困难。

任务图更明确：

read -> undistort -> downsample -> match -> optimize -> publish

如果有分支：

              -> compute descriptors ->
downsampled                         -> loop check
              -> nearest neighbor  ->

图结构能直接表达。

任务图的理论基础：DAG 调度与关键路径¶

任务图框架的数学基础是**有向无环图（DAG）调度理论**。理解这个理论有助于判断"任务图能给系统带来多少加速"以及"任务图的瓶颈在哪里"。

DAG 模型。一个任务图可以形式化为一个加权 DAG \(G = (V, E, w)\)：节点 \(v \in V\) 是任务，边 \((u, v) \in E\) 表示任务 \(u\) 必须在任务 \(v\) 之前完成，\(w(v)\) 是任务 \(v\) 的执行时间。

关键路径（Critical Path） 是 DAG 中从入口到出口的最长路径（按权重之和计算）。关键路径的长度就是前面提到的 span \(S\)——即使有无限多处理器，系统也不可能比关键路径更快。任何不在关键路径上的任务都有"松弛时间"（slack）——延迟这些任务不影响总完成时间。

以上面的 SLAM 前端为例，假设各阶段耗时如下：

阶段	耗时	依赖
读取点云 (A)	2ms	无
IMU 预积分 (B)	1ms	无
去畸变 (C)	8ms	A, B
体素下采样 (D)	5ms	C
描述子计算 (E)	3ms	D
最近邻匹配 (F)	10ms	D
回环检查 (G)	4ms	E, F
位姿优化 (H)	15ms	F
发布 (I)	1ms	G, H

关键路径是 A -> C -> D -> F -> H -> I = 2+8+5+10+15+1 = 41ms。串行执行总时间是 2+1+8+5+3+10+4+15+1 = 49ms。理论最大加速比 = 49/41 = 1.20——只有 20% 的加速空间，因为关键路径已经占总工作量的 84%。

这个分析告诉我们：不是所有任务图都能显著加速。如果关键路径上的一个任务（如 15ms 的位姿优化）占据了大部分时间，任务图能提供的加速很有限——应该优先优化关键路径上的任务本身（如用 GPU 加速位姿优化），而不是寄望于并行化非关键路径的小任务。

抽象不变量：节点表示任务，边表示必须先发生的关系¶

任务图里有两个核心对象：

节点：一个可执行任务。
边：任务之间的先后依赖。

如果 A -> B，含义是 B 不能在 A 完成前开始。它不一定表示 A 和 B 在同一个线程。也不一定表示它们共享数据。它只表示调度约束。

代码验证：任务图伪代码¶

不同任务图库 API 会变化。下面只展示结构：

TaskGraph graph;

auto read = graph.emplace("read", [&] {
    cloud = readCloud();
});

auto undistort = graph.emplace("undistort", [&] {
    undistorted = undistortCloud(cloud, imu);
});

auto downsample = graph.emplace("downsample", [&] {
    filtered = voxelDownsample(undistorted);
});

auto match = graph.emplace("match", [&] {
    correspondences = findCorrespondences(filtered, map);
});

auto optimize = graph.emplace("optimize", [&] {
    pose = solvePose(correspondences);
});

auto publish = graph.emplace("publish", [&] {
    publishPose(pose);
});

read.precede(undistort);
undistort.precede(downsample);
downsample.precede(match);
match.precede(optimize);
optimize.precede(publish);

Executor executor;
executor.run(graph).wait();

真实 taskflow 或其他任务图库的 API 以官方文档为准。关键不是记函数名，而是学会把依赖从代码调用栈中显式拿出来。

工程边界：任务图不是长期状态机的替代品¶

任务图适合一次处理流程：

一帧点云的处理图
一次重定位请求的处理图
一次离线批处理任务

长期运行的 SLAM 系统仍需要模块状态：

Tracking 是否丢失
Mapping 是否暂停
LoopClosing 是否正在优化
地图版本号是多少
传感器缓冲是否溢出

这些状态不是单个任务图能自然表达的。它们需要状态机、队列、线程生命周期和资源所有权设计。

⚠️ 编程陷阱：用 std::async 链 .get() 伪装异步 错误做法：auto b = std::async([&]{ return undistort(a.get()); }); 中 a.get() 在 lambda 内部阻塞。现象：代码看起来像异步提交，实际上每个阶段都在等待前一个阶段完成，执行流和串行完全一样。 根本原因：future::get() 是阻塞调用。在 lambda 中调用 get() 意味着这个任务无法启动直到前置任务完成。 正确做法：使用任务图显式声明依赖关系，让调度器决定执行顺序，而不是在 lambda 内部手动等待。

💡 概念误区：认为任务图适合所有并行场景 新手想法："任务图能表达依赖关系，它一定比 parallel_for 更好。" 实际上：任务图适合表达少量异构任务之间的依赖。如果有 100 万个相同计算（如点云变换），为每个点创建一个图节点会让调度开销远大于计算。数据并行用 parallel_for/blocked_range，阶段依赖才用任务图。

练习¶

[设计题] 为一个 LiDAR SLAM 前端画出任务图：包含读取点云、IMU 预积分、去畸变、下采样、配准、地图更新、发布结果。标注哪些边是必须的依赖，哪些阶段可以并行。
[分析题] 比较 std::async 链式调用和任务图框架在错误传播、取消支持和可视化调试方面的差异。
[代码题] 用伪代码写出一个任务图，其中"描述子计算"和"最近邻搜索"可以并行，但都依赖"下采样"完成，最终汇合到"配准"阶段。

19.7 体素下采样：从串行到并行的完整拆解 ⭐⭐⭐⭐¶

工程问题：点云下采样既有独立计算，也有共享写入¶

体素下采样的基本流程：

每个点计算体素坐标。
同一个体素内的点聚合。
每个体素输出一个代表点。

第一步天然并行。第二步有共享写入。第三步遍历体素表，通常也可以并行或串行。

难点在第二步。多个点可能落到同一个体素。并行插入同一个哈希表会产生同步问题。

反面失败：每个点直接锁全局 map¶

std::mutex mutex;
std::unordered_map<VoxelKey, Accumulator, VoxelHash> voxels;

#pragma omp parallel for
for (int i = 0; i < static_cast<int>(points.size()); ++i) {
    const VoxelKey key = computeKey(points[i], leaf_size);
    std::lock_guard<std::mutex> lock(mutex);
    voxels[key].add(points[i]);
}

这段代码大概率正确，但性能很差。所有线程都争抢同一把锁。哈希表扩容还可能导致长时间持锁。并行化变成了“很多线程排队执行串行插入”。

抽象不变量：共享写入要么分区，要么局部化¶

常见方案：

方案	思路	优点	缺点
全局锁	一个 map，一把锁	简单	竞争严重
分片锁	多个桶，多把锁	降低竞争	实现复杂
线程本地 map	每线程一个 map，最后合并	热路径无锁	合并成本
排序后分段	key 排序，相同 key 连续	确定性好	排序成本
并发哈希表	容器内部同步	代码清楚	仍需理解 value 更新

教学实现通常推荐线程本地 map。它把共享写入变成局部写入，再在合并阶段处理冲突。

规则推导：线程本地聚合的成本模型¶

总成本大致是：

\[ T = T_{\text{key}}/N + T_{\text{local insert}}/N + T_{\text{merge}} \]

如果点很多、体素数量相对少，合并成本可以接受。如果每个线程产生的体素几乎完全不同，合并也比较快。如果所有点都落在同一个体素，合并会退化，但这种数据本身也不适合哈希并行。

代码验证：串行体素下采样¶

#include <cmath>
#include <cstdint>
#include <unordered_map>
#include <vector>

struct PointXYZ {
    float x = 0.0f;
    float y = 0.0f;
    float z = 0.0f;
};

struct VoxelKey {
    int x = 0;
    int y = 0;
    int z = 0;

    bool operator==(const VoxelKey& other) const {
        return x == other.x && y == other.y && z == other.z;
    }
};

struct VoxelHash {
    std::size_t operator()(const VoxelKey& key) const {
        std::size_t h = 1469598103934665603ull;
        auto mix = [&](int v) {
            h ^= static_cast<std::size_t>(v);
            h *= 1099511628211ull;
        };
        mix(key.x);
        mix(key.y);
        mix(key.z);
        return h;
    }
};

struct Accumulator {
    double x = 0.0;
    double y = 0.0;
    double z = 0.0;
    int count = 0;

    void add(const PointXYZ& p) {
        x += p.x;
        y += p.y;
        z += p.z;
        ++count;
    }

    void merge(const Accumulator& other) {
        x += other.x;
        y += other.y;
        z += other.z;
        count += other.count;
    }

    PointXYZ centroid() const {
        const double inv = 1.0 / static_cast<double>(count);
        return PointXYZ{
            static_cast<float>(x * inv),
            static_cast<float>(y * inv),
            static_cast<float>(z * inv)};
    }
};

VoxelKey voxelKey(const PointXYZ& p, float leaf) {
    return VoxelKey{
        static_cast<int>(std::floor(p.x / leaf)),
        static_cast<int>(std::floor(p.y / leaf)),
        static_cast<int>(std::floor(p.z / leaf))};
}

std::vector<PointXYZ> voxelDownsampleSerial(const std::vector<PointXYZ>& points,
                                            float leaf) {
    std::unordered_map<VoxelKey, Accumulator, VoxelHash> voxels;
    voxels.reserve(points.size() / 4);

    for (const PointXYZ& p : points) {
        voxels[voxelKey(p, leaf)].add(p);
    }

    std::vector<PointXYZ> output;
    output.reserve(voxels.size());
    for (const auto& [key, acc] : voxels) {
        (void)key;
        output.push_back(acc.centroid());
    }
    return output;
}

OpenMP 版本：线程本地 map 后合并¶

#include <omp.h>

std::vector<PointXYZ> voxelDownsampleOpenMP(const std::vector<PointXYZ>& points,
                                            float leaf) {
    const int threads = omp_get_max_threads();
    using Map = std::unordered_map<VoxelKey, Accumulator, VoxelHash>;
    std::vector<Map> local(static_cast<std::size_t>(threads));

    #pragma omp parallel
    {
        const int tid = omp_get_thread_num();
        Map& map = local[static_cast<std::size_t>(tid)];

        #pragma omp for schedule(static)
        for (int i = 0; i < static_cast<int>(points.size()); ++i) {
            const PointXYZ& p = points[static_cast<std::size_t>(i)];
            map[voxelKey(p, leaf)].add(p);
        }
    }

    Map merged;
    for (const Map& part : local) {
        for (const auto& [key, acc] : part) {
            merged[key].merge(acc);
        }
    }

    std::vector<PointXYZ> output;
    output.reserve(merged.size());
    for (const auto& [key, acc] : merged) {
        (void)key;
        output.push_back(acc.centroid());
    }
    return output;
}

这段实现牺牲了输出顺序确定性。如果测试只比较点集大小和几何误差，问题不大。如果需要逐点完全一致，就要对 key 排序后输出。

体素下采样并行化的核心困难，和数据库的并发插入是同构问题：多个写者同时向同一个哈希结构插入数据。数据库用分区（sharding）和事务隔离解决这个问题；并行下采样用线程本地 map 加合并解决。两者的设计思路完全一致——把共享写入变成局部写入再合并。

如果不用线程本地 map，而是直接用一把全局锁保护哈希表会怎样？所有线程每插入一个点都要获取锁。如果 computeKey 只需 10ns，而锁获取需要 100ns，那 90% 的时间都在等锁。8 个线程并行的实际吞吐甚至可能低于单线程串行——因为除了锁等待，还有 cache line 在核心间的传递成本。

⚠️ 编程陷阱：哈希表在并行 push_back 中扩容导致崩溃 错误做法：并行循环中多个线程同时向 std::unordered_map 插入，触发 rehash。现象：偶发 segfault，在不同输入数据下崩溃位置不同。 根本原因：rehash 会重新分配内存并移动所有桶，这期间其他线程的迭代器和指针全部失效。 正确做法：使用线程本地 map，或在并行开始前 reserve 足够容量（但 reserve 也不能保证 rehash 永远不发生，因为负载因子可能仍然触发）。

练习¶

[性能分析题] 线程本地 map 方案中，如果有 8 个线程、每个线程产生 5000 个体素，合并阶段需要遍历 40000 个体素条目。估算合并阶段的耗时占比，并讨论何时合并成本会超过并行收益。
[设计题] 除了线程本地 map，还可以用"排序后分段"的方式并行化体素下采样。描述这种方案的流程，并与线程本地 map 方案对比各自的优缺点。
[代码题] 修改 OpenMP 体素下采样版本，使输出点按体素 key 排序后输出，保证结果完全确定性。

TBB 版本：以 range 为单位构造局部结果¶

TBB 的 parallel_reduce 可以把“局部 map + 合并”写成对象：

#include <tbb/blocked_range.h>
#include <tbb/parallel_reduce.h>

class VoxelReduction {
public:
    using Map = std::unordered_map<VoxelKey, Accumulator, VoxelHash>;

    VoxelReduction(const std::vector<PointXYZ>& points, float leaf)
        : points_(points), leaf_(leaf) {}

    VoxelReduction(VoxelReduction& other, tbb::split)
        : points_(other.points_), leaf_(other.leaf_) {}

    void operator()(const tbb::blocked_range<std::size_t>& r) {
        for (std::size_t i = r.begin(); i != r.end(); ++i) {
            const PointXYZ& p = points_[i];
            voxels_[voxelKey(p, leaf_)].add(p);
        }
    }

    void join(const VoxelReduction& other) {
        for (const auto& [key, acc] : other.voxels_) {
            voxels_[key].merge(acc);
        }
    }

    const Map& voxels() const {
        return voxels_;
    }

private:
    const std::vector<PointXYZ>& points_;
    float leaf_ = 0.1f;
    Map voxels_;
};

std::vector<PointXYZ> voxelDownsampleTBB(const std::vector<PointXYZ>& points,
                                         float leaf) {
    VoxelReduction reduction(points, leaf);
    tbb::parallel_reduce(
        tbb::blocked_range<std::size_t>(0, points.size(), 4096),
        reduction);

    std::vector<PointXYZ> output;
    output.reserve(reduction.voxels().size());
    for (const auto& [key, acc] : reduction.voxels()) {
        (void)key;
        output.push_back(acc.centroid());
    }
    return output;
}

这段代码比 OpenMP 版本长。但它把局部状态和合并逻辑封装成一个对象。在库代码中，这种封装更容易复用。

19.8 策略选择：OpenMP、TBB、任务图和串行后备 ⭐⭐⭐¶

并行后端抽象的设计理论¶

在讨论策略选择之前，有必要从软件工程角度理解”为什么要抽象并行后端”。这个问题的答案涉及**依赖倒置原则（Dependency Inversion Principle）**在并行编程中的应用。

问题的本质：并行框架是一种**环境依赖**——就像操作系统、文件系统或网络库一样，它是算法正确运行所需要但又不属于算法本身逻辑的外部基础设施。如果算法代码直接依赖具体的并行框架（比如在循环中直接写 #pragma omp parallel for），那么更换并行框架就需要修改算法代码——这违反了”高层模块不应依赖低层模块”的原则。

策略模式（Strategy Pattern）在并行中的应用。解决方案是定义一个抽象的”并行执行策略”接口，让算法依赖接口而非具体实现。不同的并行后端（串行、OpenMP、TBB、CUDA）各自实现这个接口。这样算法代码只调用 policy.parallel_for(range, body)，具体由哪个框架执行取决于运行时注入的策略对象。

C++17 的 std::execution 正是这个方向的标准化尝试——std::execution::seq、std::execution::par、std::execution::par_unseq 就是预定义的执行策略对象。但标准库的策略粒度太粗（只有三种），无法表达”使用 TBB 的 4 线程 arena”或”使用 CUDA stream 2”这样的细节。工程实践中通常需要自定义策略层。

策略切换的性能边界。通过函数指针或虚函数分派策略会引入间接调用开销（约 2-5ns），但这个开销在并行循环的整体耗时中可以忽略——它只发生一次（进入并行区域时），而不是每个迭代都发生。真正的性能差异来自框架本身的调度策略和线程管理，而不是分派机制。

工程问题：一个库不应把用户锁死在单一并行后端¶

机器人基础库常被不同项目复用。有些项目只允许标准库。有些项目已经启用 OpenMP。有些项目统一使用 TBB。有些嵌入式平台不希望引入额外运行时。

因此，库层最好把”算法逻辑”和”执行策略”分开。这和 C++语言核心/Concepts与Policy 的 Policy 思想一致。

反面失败：算法内部硬编码 OpenMP¶

template <class PointCloud>
Result align(const PointCloud& source, const PointCloud& target) {
    #pragma omp parallel for
    for (int i = 0; i < static_cast<int>(source.size()); ++i) {
        // ...
    }
    return result;
}

这段代码的问题：

用户无法在不支持 OpenMP 的环境中使用。
上层无法限制并行度。
单元测试难以强制串行路径。
与 TBB 项目共存时可能过度订阅。
算法和执行后端耦合。

抽象不变量：执行策略只负责“怎样遍历”，算法负责“遍历时做什么”¶

策略接口可以非常小：

struct SerialPolicy {
    template <class Func>
    void parallelFor(std::size_t begin, std::size_t end, Func func) const {
        for (std::size_t i = begin; i < end; ++i) {
            func(i);
        }
    }
};

算法只依赖这个接口：

template <class Policy, class Func>
void forEachIndex(const Policy& policy,
                  std::size_t n,
                  Func func) {
    policy.parallelFor(0, n, func);
}

OpenMP 和 TBB 可以各自实现同样语义。

代码验证：三种执行策略¶

#include <cstddef>

struct SerialPolicy {
    template <class Func>
    void parallelFor(std::size_t begin, std::size_t end, Func func) const {
        for (std::size_t i = begin; i < end; ++i) {
            func(i);
        }
    }
};

struct OpenMPPolicy {
    int threads = 0;

    template <class Func>
    void parallelFor(std::size_t begin, std::size_t end, Func func) const {
        const int n = static_cast<int>(end - begin);
        if (threads > 0) {
            #pragma omp parallel for num_threads(threads)
            for (int i = 0; i < n; ++i) {
                func(begin + static_cast<std::size_t>(i));
            }
        } else {
            #pragma omp parallel for
            for (int i = 0; i < n; ++i) {
                func(begin + static_cast<std::size_t>(i));
            }
        }
    }
};

struct TBBPolicy {
    std::size_t grainsize = 4096;

    template <class Func>
    void parallelFor(std::size_t begin, std::size_t end, Func func) const {
        tbb::parallel_for(
            tbb::blocked_range<std::size_t>(begin, end, grainsize),
            [&](const tbb::blocked_range<std::size_t>& r) {
                for (std::size_t i = r.begin(); i != r.end(); ++i) {
                    func(i);
                }
            });
    }
};

真实库里还要处理编译开关。例如没有启用 OpenMP 时不编译 OpenMPPolicy。没有链接 TBB 时不提供 TBBPolicy。

工程边界：策略接口不要承诺过多¶

parallelFor 只承诺“每个索引被调用一次”。它不承诺：

调用顺序。
调用线程。
同一线程处理连续索引。
异常传播方式完全一致。
浮点归约结果逐 bit 一致。

如果算法依赖这些行为，接口文档必须写清楚。否则换后端会改变语义。

⚠️ 编程陷阱：算法内部硬编码 #pragma omp parallel for 导致库不可移植 错误做法：在库函数内部直接写 #pragma omp parallel for，没有提供串行 fallback。现象：在不支持 OpenMP 的嵌入式平台上编译失败；在已经使用 TBB 的项目中引起线程过度订阅。 根本原因：并行后端被硬编码进算法逻辑，而不是作为策略注入。 正确做法：使用 policy 模板或运行时策略接口，把"遍历方式"从"遍历逻辑"中分离。

🧠 思维陷阱：因为"新框架更好"而迁移 新手想法："TBB 比 OpenMP 更现代，我们应该把所有 OpenMP 代码迁移到 TBB。" 实际上：迁移框架有巨大的工程成本——构建系统、调试工具、团队知识、性能调参全部要重新来过。如果 OpenMP 版本已经满足性能和稳定性要求，迁移的边际收益可能远小于成本。 正确思维：框架选择应服务于代码形态和工程约束，不服务于"技术先进性"的抽象追求。

练习¶

[设计题] 为一个点云配准库设计执行策略接口，支持 SerialPolicy、OpenMPPolicy 和 TBBPolicy。写出接口定义和串行策略的实现。
[分析题] 一个项目同时使用了 OpenMP（点云滤波）和 TBB（配准库内部），两者默认都使用全部 CPU 核心。在一台 8 核机器上，分析可能出现的问题并提出解决方案。
[跨章综合题] 结合线程管理与互斥同步的线程管理和本节的策略选择，为一个 ROS2 SLAM 节点设计并行预算：控制线程、SLAM 前端、后端优化、可视化各分配多少核心？

19.9 并发容器、局部容器与两阶段合并 ⭐⭐⭐⭐¶

工程问题：并行写入共享结构是性能和正确性的交汇点¶

点云和地图算法经常需要构造索引结构：

体素哈希表。
关键帧倒排索引。
描述子桶。
统计直方图。
邻接表。

这些结构都涉及共享写入。并行化难点不在计算 key，而在写入结构。

反面失败：误以为并发容器能解决所有不变量¶

假设用并发哈希表存体素：

concurrent_map[key] -> Accumulator

并发 map 可以保护“插入 key”。但 Accumulator 里有 sum_x, sum_y, sum_z, count。如果多个线程同时更新同一个 accumulator，仍然要保证这四个字段一致。

如果用四个 atomic 字段，能避免 data race。但读者可能看到 sum_x 已更新、count 未更新的中间状态。如果只有构建结束后读取，可以接受。如果构建过程中也有读者，就不行。

抽象不变量：共享结构分三层考虑¶

容器结构是否线程安全。
元素对象更新是否线程安全。
业务不变量是否在读者可见时成立。

这三层不能混为一谈。很多并发 bug 出现在第三层。

规则推导：两阶段合并的可靠性¶

两阶段合并把问题变成：

阶段 1：每个线程只写自己的局部结构
阶段 2：单线程或受控并行合并局部结构

阶段 1 没有共享写入。阶段 2 的写入顺序可控。这通常比使用复杂并发容器更容易验证。

代价是内存占用增加。如果局部结构巨大，需要分块处理或使用分片合并。

代码验证：线程本地直方图¶

#include <array>
#include <vector>

struct Histogram {
    std::array<std::uint64_t, 64> bins{};

    void add(float intensity) {
        int idx = static_cast<int>(intensity * 64.0f);
        idx = std::clamp(idx, 0, 63);
        ++bins[static_cast<std::size_t>(idx)];
    }

    void merge(const Histogram& other) {
        for (std::size_t i = 0; i < bins.size(); ++i) {
            bins[i] += other.bins[i];
        }
    }
};

Histogram parallelHistogram(const std::vector<float>& intensity) {
    const int threads = omp_get_max_threads();
    std::vector<Histogram> local(static_cast<std::size_t>(threads));

    #pragma omp parallel
    {
        const int tid = omp_get_thread_num();
        Histogram& hist = local[static_cast<std::size_t>(tid)];

        #pragma omp for schedule(static)
        for (int i = 0; i < static_cast<int>(intensity.size()); ++i) {
            hist.add(intensity[static_cast<std::size_t>(i)]);
        }
    }

    Histogram total;
    for (const Histogram& hist : local) {
        total.merge(hist);
    }
    return total;
}

这里没有 atomic。因为每个线程只写自己的 Histogram。合并在并行区域后发生。

⚠️ 编程陷阱：并发容器只保护结构，不保护业务不变量 错误做法：用 tbb::concurrent_hash_map 存体素，认为"容器线程安全了所以一切都安全了"。现象：某个体素的 sum_x 已更新但 count 还没更新时，另一个线程读到不一致的中间状态。 根本原因：容器保护的是自身数据结构（桶、链表、迭代器），不保护 value 对象内部的多字段一致性。 正确做法：对 value 的多字段更新使用局部锁或原子操作，或采用两阶段合并完全避免共享写入。

练习¶

[分析题] 三层不变量——容器结构安全、元素更新安全、业务不变量成立——在一个并行体素构建场景中分别如何验证？
[代码题] 实现一个线程本地直方图收集器，每个线程统计自己处理的点云强度分布，并行结束后合并成全局直方图。确保不使用任何锁。

19.10 性能测量：加速比、效率和尾延迟 ⭐⭐⭐⭐¶

并行性能指标的理论体系¶

在测量并行性能之前，需要明确我们在衡量什么。并行性能有三个互补的指标，各自回答不同的问题：

加速比（Speedup） \(S(P) = T_1 / T_P\)，其中 \(T_1\) 是串行执行时间，\(T_P\) 是 \(P\) 个处理器的并行执行时间。加速比回答”并行比串行快了多少”。理想加速比是 \(P\)（线性加速），实际总是 \(S(P) < P\)，因为存在串行部分、调度开销和通信成本。

并行效率（Efficiency） \(E(P) = S(P) / P = T_1 / (P \cdot T_P)\)。效率回答”每个处理器被利用了多少”。\(E = 1\) 意味着完美利用，\(E = 0.5\) 意味着处理器一半时间在空转。效率随 \(P\) 增大通常下降——这就是”加更多核心的收益递减”的量化表达。

可扩展性（Scalability） 描述 \(S(P)\) 随 \(P\) 增长的趋势。强可扩展性（strong scaling）固定问题规模，增加处理器数——理想是 \(S(P) = P\)。弱可扩展性（weak scaling）固定每个处理器的问题规模，同时增加处理器数和总问题规模——理想是 \(T_P\) 恒定。SLAM 前端通常关心强可扩展性（同一帧点云用更多核心处理更快），而离线建图可能关心弱可扩展性（更大地图用更多核心在相同时间内处理）。

超线性加速比。偶尔会观察到 \(S(P) > P\)——这看起来违反直觉，但有合理的解释：并行版本把数据拆分到多个核心后，每个核心的工作集变小，可能完全放进 L2/L3 缓存，而串行版本的工作集太大导致频繁 cache miss。这种”缓存效应导致的超线性加速”在点云处理中偶尔可见，但不应作为设计依据。

工程问题：并行优化必须用数据说话¶

常见错误是”加了并行代码，感觉应该更快”。正确做法是至少记录：

串行耗时。
并行耗时。
线程数。
输入规模。
加速比。
并行效率。
p50/p90/p99 延迟。
CPU 占用和温度。

嵌入式平台尤其要关注温度和频率。 Jetson 或移动平台在持续高负载下可能降频。第一次运行很快，运行一分钟后变慢，并不罕见。

反面失败：只测一次¶

auto t0 = Clock::now();
runParallel();
auto t1 = Clock::now();
std::cout << duration(t1 - t0) << "\n";

只测一次会混入：

首次内存分配。
缓存冷启动。
动态库加载。
CPU 频率变化。
操作系统调度抖动。

至少要预热，多次运行，报告分位数。

抽象不变量：加速比必须绑定输入规模¶

加速比：

\[ S(N)=\frac{T_1}{T_N} \]

并行效率：

\[ E(N)=\frac{S(N)}{N} \]

如果 1000 个点并行版本更慢，不代表框架没用。输入太小，调度开销占主导。如果 1000 万点并行版本仍然更慢，才要重点检查内存带宽、锁竞争和实现结构。

代码验证：最小 benchmark 工具¶

#include <algorithm>
#include <chrono>
#include <iostream>
#include <vector>

template <class Func>
std::vector<double> benchmark(Func func, int repeats) {
    using Clock = std::chrono::steady_clock;
    std::vector<double> ms;
    ms.reserve(static_cast<std::size_t>(repeats));

    for (int i = 0; i < repeats; ++i) {
        const auto t0 = Clock::now();
        func();
        const auto t1 = Clock::now();
        const double dt =
            std::chrono::duration<double, std::milli>(t1 - t0).count();
        ms.push_back(dt);
    }
    std::sort(ms.begin(), ms.end());
    return ms;
}

double percentile(const std::vector<double>& sorted, double p) {
    const double pos = p * static_cast<double>(sorted.size() - 1);
    const auto idx = static_cast<std::size_t>(pos);
    return sorted[idx];
}

void printStats(const std::vector<double>& ms) {
    std::cout << "p50 " << percentile(ms, 0.50) << " ms\n";
    std::cout << "p90 " << percentile(ms, 0.90) << " ms\n";
    std::cout << "p99 " << percentile(ms, 0.99) << " ms\n";
}

这个工具很朴素，但比单次计时可靠。正式 benchmark 还要控制 CPU 频率、线程绑定、输入固定和编译选项。

⚠️ 编程陷阱：只用 std::chrono::system_clock 做性能计时 错误做法：用 system_clock::now() 计算耗时。现象：偶尔出现负数耗时或异常大的耗时值。 根本原因：system_clock 可能被 NTP 或系统时间调整影响，导致时间戳不单调。 正确做法：使用 std::chrono::steady_clock，它保证单调递增，适合测量时间间隔。

练习¶

[实验题] 写一个 benchmark 脚本，对同一个点云变换函数分别测量 1 次、10 次、100 次运行，报告 p50、p90、p99。解释为什么多次测量的分位数比单次测量更可靠。
[分析题] 在一台 Jetson 平台上持续运行并行 benchmark 5 分钟，前 30 秒和后 30 秒的耗时差异可能来自哪些因素？应该如何控制实验条件？

19.11 浮点误差与可重复性 ⭐⭐⭐¶

工程问题：并行版本正确，但测试失败¶

并行优化常遇到这种现象：

串行 cost: 123.4567890123
并行 cost: 123.4567890118

差异很小，但逐 bit 比较失败。如果测试写成：

assert(serial_cost == parallel_cost);

并行版本会被误判为错误。

反面失败：为了通过测试强行固定所有调度¶

完全固定调度可以提高可重复性，但可能牺牲很多性能。更合理的是区分测试层级：

测试目标	判断方式
API 行为	输出大小、边界条件、异常
数值正确性	绝对误差和相对误差
回归稳定	固定输入下分位数范围
确定性需求	固定归约顺序

不是所有测试都要求 bitwise reproducibility。

抽象不变量：并行归约改变表达式树¶

串行求和：

((((a0 + a1) + a2) + a3) + ...)

并行求和：

(a0 + a1 + ... + a1023) + (a1024 + ... + a2047) + ...

表达式树不同，浮点舍入路径不同。这在数学实数上无差别，在 IEEE 浮点上有差别。

代码验证：误差容忍比较¶

#include <cmath>

bool near(double a, double b, double rel, double abs) {
    const double diff = std::abs(a - b);
    if (diff <= abs) {
        return true;
    }
    return diff <= rel * std::max(std::abs(a), std::abs(b));
}

void testParallelCost() {
    const double serial = runSerial();
    const double parallel = runParallel();
    assert(near(serial, parallel, 1e-9, 1e-12));
}

容忍阈值要结合问题尺度。对位姿优化，最终位姿误差、残差下降趋势和收敛判据往往比单个 cost 的末位更重要。

💡 概念误区：认为并行浮点差异可以通过"更高精度"完全消除 新手想法："用 long double 或补偿求和就能让并行结果和串行完全一致。" 实际上：更高精度可以缩小差异，但只要归约顺序不同，IEEE 浮点下就不可能做到逐 bit 一致。真正的一致性需要固定归约顺序——这会限制调度自由度，通常以牺牲性能为代价。

练习¶

[实验题] 构造一个包含 1e16, -1e16, 1.0 的数组，分别用串行顺序求和和逆序求和，观察结果差异。解释这如何影响并行归约。
[设计题] 对于一个需要逐 bit 可重复的离线 benchmark，设计一个分块确定性归约方案。说明块大小、合并顺序和性能损失之间的权衡。

19.12 嵌套并行与线程过度订阅 ⭐⭐⭐⭐¶

线程过度订阅的理论分析：为什么"线程越多越慢"¶

线程过度订阅（oversubscription）是机器人系统中最常见的并行性能陷阱之一。理解它为什么有害，需要从操作系统调度和 CPU 缓存两个角度分析。

操作系统调度视角。当可运行线程数 \(T\) 超过物理核心数 \(P\) 时，操作系统必须进行时间片轮转——每个线程只运行一小段时间（Linux CFS 的典型时间片约 1-10ms），然后被抢占，让出 CPU 给其他线程。每次上下文切换的开销包括：保存/恢复寄存器（~1 微秒）、刷新 TLB 条目（可能导致后续数十次 TLB miss，每次约 50ns）、调度器选择下一个线程的开销（~0.5 微秒）。当 \(T \gg P\) 时，上下文切换频率与 \(T\) 成正比，调度开销可能达到 CPU 时间的 5-20%。

缓存污染视角。更严重的是缓存效果。每个线程在运行期间会把自己的工作集加载到 L1/L2 缓存中。当线程被抢占、另一个线程开始运行时，新线程的工作集会把旧线程的数据从缓存中驱逐。当旧线程恢复运行时，它的缓存几乎完全是冷的——需要重新从 L3 甚至主存加载数据。这个"缓存预热"开销远大于寄存器保存/恢复：一个 SLAM 配准线程的工作集可能是数百 KB（KD-tree 节点、点云子集），完全重新加载需要数十微秒到毫秒级。如果 \(T = 4P\)，每个线程实际只能使用 1/4 的时间片，而且每次恢复时都要重新预热缓存——真正用于计算的有效时间可能只有 50-60%。

量化过度订阅的影响。设 \(P\) 核心上有 \(T = kP\) 个计算密集型线程（\(k > 1\)）。如果没有缓存效应，线程的有效计算速率应该是 \(1/k\)（每个线程只获得 \(1/k\) 的 CPU 时间）。加上缓存污染后，实际计算速率更低。经验上，\(k = 2\) 时效率约为理想值的 70-80%，\(k = 4\) 时约为 40-60%，\(k = 8\) 时可能低于 30%。这就是为什么并行框架通常默认创建与核心数相同的线程，而不是更多。

工程问题：每个库都想用全部 CPU¶

一个机器人进程可能同时使用：

OpenMP 点云处理。
TBB 配准库。
Eigen 或 BLAS 线性代数。
ROS2 多线程执行器。
后端优化库内部线程。

如果每一层都默认使用全部核心，系统会创建远超核心数的可运行线程。结果是上下文切换变多，缓存局部性变差，尾延迟变大。

反面失败：外层帧并行，内层点并行¶

#pragma omp parallel for
for (int frame = 0; frame < num_frames; ++frame) {
    processFrameWithInternalParallelism(frame);
}

如果 processFrameWithInternalParallelism 内部也开 OpenMP 或 TBB，就形成嵌套并行。外层 8 个线程，每个内层再开 8 个，理论上可能有 64 个任务争抢。

抽象不变量：一个进程需要统一并行预算¶

并行预算包括：

CPU 核心数。
实时线程预留。
ROS2 回调线程。
后台任务线程。
第三方库线程。

经验规则：

实时路径优先预留
吞吐任务使用剩余核心
库内部并行度可配置
避免外层和内层同时无限并行

工程边界：库函数应提供串行路径¶

如果一个库只提供内部并行版本，上层很难管理预算。更好的设计：

align<SerialPolicy>(data);
align<OpenMPPolicy>(data);
align<TBBPolicy>(data);

上层系统决定在哪里并行。库函数负责正确执行。

嵌套并行就像一家公司每个部门都以为自己可以用全公司的会议室：表面上每个部门都在高效开会，实际上所有会议室被同时占满，很多人在走廊里等空位。在 CPU 上，"会议室"就是核心，"排队等位"就是上下文切换——它不但浪费时间，还会因为频繁切换打乱每个核心的缓存状态。

⚠️ 编程陷阱：外层 OpenMP 嵌套内层 TBB 导致线程爆炸 错误做法：外层 #pragma omp parallel for 启动 8 个线程，每个线程内部调用使用 TBB 的库函数，TBB 默认也启动 8 个线程。现象：系统创建 64 个线程，CPU 使用率 100% 但吞吐不增反降，p99 延迟急剧上升。 根本原因：过度订阅导致大量上下文切换，缓存局部性被摧毁。操作系统在 64 个线程之间快速切换，每次切换都可能让前一个线程在缓存中预热的数据失效。 正确做法：统一并行预算。如果上层已经 8 线程并行，内层库应使用串行策略或限制到 1 个线程。

练习¶

[诊断题] 一个 SLAM 系统运行时 top 显示 CPU 使用率 800%（8 核），但处理频率只有 3Hz（设计频率 10Hz）。列出可能的线程过度订阅来源，并给出排查步骤。
[设计题] 设计一个进程级并行预算分配方案：8 核 CPU 上需要同时运行控制线程（实时）、SLAM 前端、SLAM 后端、ROS2 executor 和可视化。每个模块最多使用几个核心？

19.13 异常、取消与早停 ⭐⭐⭐⭐¶

工程问题：机器人系统不能只考虑成功路径¶

并行任务可能遇到：

输入数据损坏。
数值发散。
内存分配失败。
用户请求停止。
传感器时间戳异常。

串行代码里，抛异常或返回错误码都比较清楚。并行代码里，多个任务可能同时失败。还可能有任务已经失败，其他任务仍在运行。

反面失败：第一个错误出现后其他任务继续写共享输出¶

std::vector<Result> results(n);
bool failed = false;

#pragma omp parallel for
for (int i = 0; i < n; ++i) {
    if (failed) {
        continue;
    }
    results[i] = compute(i);
    if (!results[i].valid) {
        failed = true;
    }
}

failed 是普通 bool，并发读写产生 data race。即使改成 atomic，也只能表达“尽量早停”。已经开始的迭代可能继续运行。

抽象不变量：取消通常是协作式的¶

并行框架很少能安全强杀正在执行的 C++ 任务。更常见的是协作式取消：

共享一个原子停止标志。
每个任务在合适边界检查。
已经开始的任务尽快返回。
并行区域结束后统一处理错误。

代码验证：原子早停标志¶

#include <atomic>
#include <exception>
#include <mutex>
#include <vector>

struct BatchResult {
    std::vector<Result> values;
    std::exception_ptr error;
};

BatchResult computeBatch(int n) {
    BatchResult out;
    out.values.resize(static_cast<std::size_t>(n));

    std::atomic<bool> stop{false};
    std::mutex error_mutex;

    #pragma omp parallel for
    for (int i = 0; i < n; ++i) {
        if (stop.load(std::memory_order_relaxed)) {
            continue;
        }

        try {
            out.values[static_cast<std::size_t>(i)] = computeOne(i);
        } catch (...) {
            {
                std::lock_guard<std::mutex> lock(error_mutex);
                if (!out.error) {
                    out.error = std::current_exception();
                }
            }
            stop.store(true, std::memory_order_relaxed);
        }
    }

    return out;
}

这个设计没有承诺”错误发生后零额外计算”。它承诺的是：不会产生 data race，错误会被带回并行区域外。

⚠️ 编程陷阱：用普通 bool 做并行早停标志 错误做法：bool failed = false; 在 #pragma omp parallel for 内部读写。现象：ThreadSanitizer 报 data race；某些线程看到旧值继续执行，另一些线程看到新值提前退出。 根本原因：普通 bool 的并发读写是未定义行为。即使物理上是”原子”的，C++ 内存模型不保证可见性。 正确做法：使用 std::atomic<bool> 并配合 memory_order_relaxed（早停标志不需要严格顺序保证，只需要最终可见）。

练习¶

[代码题] 实现一个并行批处理函数，支持协作式取消：用 std::atomic<bool> 停止标志让已启动的任务尽快退出，并在并行区域外统一报告第一个错误。
[分析题] 为什么并行框架很少支持”立刻杀死正在执行的线程”？从 RAII 资源管理和栈展开的角度解释。

19.14 OpenMP、TBB 与 taskflow 的选择表 ⭐⭐⭐⭐¶

三种框架的历史演进与设计取舍¶

在给出选择表之前，了解三种框架的历史背景有助于理解它们各自的设计重心为什么不同。

OpenMP（1997 年至今） 源于高性能计算（HPC）社区。HPC 的典型场景是：大型 Fortran/C 科学计算程序已经存在，需要最小改动地并行化。OpenMP 的"pragma 注释"设计完美匹配了这个需求——不改变代码结构，只添加并行提示。OpenMP 的标准由一个多厂商联盟（ARM、AMD、Intel、IBM 等）维护，每个版本都力求向后兼容。这使得 OpenMP 非常稳定，但演进速度较慢。OpenMP 5.0（2018）引入了 target offloading（GPU 支持）和任务依赖，但这些特性的编译器支持参差不齐。

TBB（2006 年至今） 源于 Intel 的并行编程研究。TBB 的设计者认为"并行应该是 C++ 类型系统的一部分，而不是编译器指令"。这个理念导致了完全不同的 API 风格——通过模板、lambda 和函数对象表达并行，而不是通过 pragma。TBB 在 2018 年开源为 oneTBB，成为 oneAPI 的一部分。TBB 的 work-stealing 调度器在不均匀负载场景下表现优秀，这使它在游戏引擎和图形渲染（负载极不均匀）中被广泛采用。

taskflow（2018 年至今） 是最年轻的框架，源于加州大学洛杉矶分校的研究。taskflow 的创新在于用 C++ 流畅接口（fluent API）直接构建任务 DAG，然后交给 work-stealing 执行器运行。它特别适合表达异构 pipeline——同一个任务图中可以包含 CPU 任务和 GPU 任务。taskflow 在电子设计自动化（EDA）领域有较多应用，SLAM 社区的采用还不广泛。

三种框架的设计重心差异：

设计重心	OpenMP	TBB	taskflow
主要目标	最小改动地并行化已有代码	提供可组合的并行基础设施	简洁地表达任务依赖图
假设的使用者	科学计算程序员	C++ 库开发者	系统架构师
核心抽象	并行循环 + 归约	并行算法 + 并发容器	任务 DAG + 条件流
调度哲学	由编译器和运行时决定	work-stealing + 用户可控	work-stealing
错误处理	有限（异常传播困难）	C++ 异常	C++ 异常 + 取消

工程问题：框架选择要服务于代码形态——决策框架而非特性对比¶

OpenMP、TBB、std::execution 不是三个 API 参考手册——而是**三种并行编程哲学**。选择框架不应该从”谁的特性列表更长”出发，而应该从你的实际约束出发。下面的决策流程把选择过程结构化为四个依次回答的问题：

问题一：你的代码是已有的 for 循环，还是从零开始设计？

如果是已有的 C/C++ for 循环（如点云滤波、残差评估），而且迭代之间没有共享写入——OpenMP 是最低侵入的选择。加一行 #pragma omp parallel for 就能做快速试验，去掉 pragma 就回到串行版本，完全不改变代码结构。这个”零侵入”特性在教学和原型阶段极有价值。

如果是从零设计库代码，且需要被不同项目复用——TBB 或 std::execution 更合适，因为并行语义被编码在 C++ 类型系统中，IDE 能看到、编译器能检查。

问题二：你的任务负载均匀吗？

点云坐标变换、强度归一化、投影计算——每个点的计算量几乎相同。这种均匀负载用 OpenMP schedule(static) 就够了，零调度开销，数据连续性最好。

KD-Tree 最近邻查询、体素滤波中密度不均匀的点——不同查询点的计算量可能相差 10-100 倍。这种不均匀负载需要动态调度。OpenMP schedule(dynamic) 可以解决，但 TBB 的 work-stealing 调度器在极端不均匀的场景下通常表现更好——因为它是去中心化的，不依赖共享计数器。

问题三：你需要在库内部使用并行，同时不干扰调用者的并行？

这是 TBB 的核心优势。如果你写的是一个配准库，库内部用 tbb::parallel_for 加速残差评估；调用者的 SLAM 系统也用 TBB 或 OpenMP 做其他并行。TBB 的 task_arena 让库内部的并行限定在独立的线程域中，不会和调用者的线程争抢。OpenMP 缺乏这种组合性——嵌套的 OpenMP 并行区域容易导致线程爆炸。

问题四：你的依赖是否允许第三方库？

嵌入式平台可能不支持 OpenMP（某些交叉编译工具链没有 libomp）。CI 环境可能没有 TBB。如果必须零外部依赖，std::execution（C++17 标准库的一部分）是唯一选择——但目前编译器实现的完整度参差不齐。最保险的策略是提供串行 fallback + 编译时可选的并行后端。

决策流程图：

你的代码是已有的 for 循环吗？
  ├─ 是 → 负载均匀吗？
  │        ├─ 是 → OpenMP schedule(static)
  │        └─ 否 → OpenMP schedule(dynamic) 或 TBB parallel_for
  └─ 否 → 需要库级组合性吗？
           ├─ 是 → TBB（配合 task_arena）
           └─ 否 → 依赖约束允许什么？
                    ├─ 无外部依赖 → std::execution 或串行
                    ├─ 有阶段依赖 → 任务图（taskflow）
                    └─ 长期线程循环 → std::thread / std::jthread

下面是按需求分类的快速参考表：

需求	推荐
给已有 `for` 循环快速并行	OpenMP
库代码需要 C++ 组合性	TBB
不均匀负载和动态调度	TBB 或 OpenMP dynamic
明确阶段依赖	任务图
只需长期模块并发	`std::thread` / `std::jthread`
小矩阵和线性代数	Eigen 或专用库
硬实时控制主循环	谨慎使用，优先静态预算
教学和可移植 baseline	串行策略

反面失败：因为”新”而迁移框架¶

并行框架迁移有成本：

构建系统变化。
依赖管理变化。
调试工具变化。
性能调参重新开始。
团队认知成本。

如果 OpenMP 版本已经满足性能和稳定性要求，迁移到 TBB 不一定有价值。如果代码需要更强组合性和库化，TBB 的价值才明显。

抽象不变量：框架不是架构¶

框架负责调度。架构负责不变量：

数据由谁拥有。
哪些阶段可以并行。
哪些输出必须确定。
哪些路径有实时约束。
失败如何传播。
并行预算由谁控制。

如果架构不清楚，换框架只是换一种方式暴露问题。

练习¶

[选型题] 你正在开发一个跨平台点云处理库，目标平台包括 x86 桌面、ARM 嵌入式和没有 OpenMP 的 CI 环境。应该选择哪种并行策略组合？解释你的理由。
[代码题] 把前面的 SerialPolicy/OpenMPPolicy/TBBPolicy 封装成一个运行时可选的枚举调度器，在编译时自动排除不可用的后端。

19.15 C++26 `std::execution`（Senders/Receivers）与异构并行展望 ⭐⭐⭐¶

为什么当前的并行标准不够¶

C++17 的执行策略（std::execution::par、par_unseq）解决了标准算法的并行化，但有三个根本局限：

只覆盖标准算法：std::for_each、std::transform、std::reduce 等标准算法可以加执行策略，但自定义算法无法使用这套机制。你不能对一个自定义的"点云配准残差评估"直接说"用 par 策略"——只能重新包装成标准算法能接受的形式。
无法表达任务依赖：执行策略只表达"这个算法可以并行"，不能表达"任务 A 完成后才能开始任务 B"这样的依赖关系。SLAM 流水线中"特征提取→特征匹配→位姿估计→地图更新"的阶段依赖无法用执行策略表达。
无法控制执行位置：执行策略不能指定"在 GPU 上执行"或"在特定的线程池中执行"。它把调度完全交给实现，程序员无法控制资源分配。

C++26 的 std::execution（P2300 提案，也称为 Senders/Receivers 框架）正是为了解决这三个问题而设计的。它的核心思想是：把异步操作表达为可组合的值（sender），通过管道连接形成任务图，最后提交给调度器（scheduler）执行。

Senders/Receivers 的核心概念¶

Senders/Receivers 框架引入了三个核心抽象：

概念	角色	类比
Sender	描述一个异步操作（尚未执行）	一份待执行的工作单
Receiver	接收操作的结果（值、错误或取消）	工作完成后的回调
Scheduler	决定操作在哪里执行	指定由哪个部门（线程池/GPU）处理

关键设计是 sender 是惰性的——创建 sender 不会立即执行任何操作，它只是描述"要做什么"。只有当 sender 被 start() 或提交给调度器时，操作才真正开始。这与 std::future/std::async 不同——std::async 在调用时就可能启动线程。

// 伪代码：C++26 senders/receivers 的使用方式
// （截至 2026 年，标准尚未正式发布，语法可能调整）

namespace ex = std::execution;

// 定义一个调度器（比如线程池）
ex::static_thread_pool pool{4};
auto scheduler = pool.get_scheduler();

// 组合异步操作管道
auto pipeline =
    ex::schedule(scheduler)               // 在线程池上开始
    | ex::then([](){ return extractFeatures(); })  // 提取特征
    | ex::then([](auto features){ return matchFeatures(features); })  // 匹配
    | ex::then([](auto matches){ return estimatePose(matches); });    // 位姿估计

// 同步等待结果
auto pose = ex::sync_wait(pipeline).value();

Senders/Receivers 对机器人系统的价值。 SLAM 流水线中的特征提取、匹配、位姿估计、地图更新是一个有明确依赖关系的任务图。当前的做法是用 std::thread + 队列手工编排（线程管理与互斥同步的方式），或用 taskflow 构建 DAG。Senders/Receivers 提供了标准化的任务组合方式，并且天然支持取消（通过 stop_token）和错误传播——这两个特性在机器人系统的优雅停机和异常处理中非常重要。

在标准正式发布之前，可以通过 stdexec（NVIDIA 开源的参考实现）体验 Senders/Receivers。生产代码中，taskflow 和 TBB flow graph 是当前最成熟的任务图方案。

SYCL：异构并行的统一编程模型 ⭐⭐⭐¶

SYCL（发音同 "sickle"）是 Khronos Group 制定的异构并行编程标准。它让 C++ 代码同时在 CPU、GPU 和 FPGA 上执行，而不需要像 CUDA 那样使用专用语法扩展。SYCL 2020 是当前版本，AdaptiveCpp（原 hipSYCL）和 Intel oneAPI DPC++ 是主要开源实现。

SYCL 与本章讨论的 OpenMP/TBB 的关系是：OpenMP 和 TBB 主要面向 CPU 多核并行；SYCL 面向异构设备并行。在机器人系统中，当点云处理或深度学习推理的计算量大到 CPU 并行无法满足实时约束时，GPU 加速成为必要选项。SYCL 提供了一种比 CUDA 更可移植的 GPU 编程方式。

// SYCL 示例：点云坐标变换（在 GPU 或 CPU 上执行）
#include <sycl/sycl.hpp>

void transformPoints(sycl::queue& q,
                     float* points, std::size_t n,
                     const float* matrix) {
    sycl::buffer<float> buf(points, sycl::range<1>(n * 3));

    q.submit([&](sycl::handler& h) {
        auto acc = buf.get_access<sycl::access::mode::read_write>(h);
        h.parallel_for(sycl::range<1>(n), [=](sycl::id<1> i) {
            // 对每个点应用 3x3 变换矩阵
            std::size_t idx = i[0] * 3;
            float x = acc[idx], y = acc[idx+1], z = acc[idx+2];
            acc[idx]   = matrix[0]*x + matrix[1]*y + matrix[2]*z;
            acc[idx+1] = matrix[3]*x + matrix[4]*y + matrix[5]*z;
            acc[idx+2] = matrix[6]*x + matrix[7]*y + matrix[8]*z;
        });
    });
}

工程边界：SYCL 在机器人社区的采用还处于早期阶段。PCL 和 Open3D 等主流点云库仍以 CPU（OpenMP/TBB）为主要并行后端。CUDA 在深度学习和某些高性能点云处理中仍是事实标准。选择 SYCL 的核心考量是跨设备可移植性——如果你的项目需要同时支持 NVIDIA GPU、Intel GPU 和纯 CPU 环境，SYCL 提供了统一的编程模型。如果只需要 NVIDIA GPU，直接使用 CUDA 生态更成熟。

⚠️ 编程陷阱：盲目追求 GPU 加速 错误做法：听说 GPU 能并行处理上万个线程，把所有计算都搬到 GPU 上。现象：CPU→GPU 数据传输的延迟可能超过计算本身的节省。小规模数据在 GPU 上反而更慢。 根本原因：GPU 并行的收益来自大量独立计算掩盖内存延迟。数据量小于几十万个元素时，PCIe 传输开销和 kernel 启动开销占主导。 正确做法：先 profile 确认计算瓶颈在哪里。只有当 CPU 并行（OpenMP/TBB）无法满足实时约束、且数据量足够大时，才考虑 GPU 加速。

并行性能分析方法论 ⭐⭐⭐⭐¶

并行程序的性能分析比串行程序复杂，因为瓶颈可能来自计算、内存带宽、锁竞争、调度开销或 cache 行为中的任何一个。以下是一个结构化的分析流程：

第一步：建立串行基准。 先用 -O2 编译串行版本，测量基准延迟。如果串行版本已经满足实时约束，不需要并行化。

第二步：测量加速比和并行效率。 加速比 \(S = T_{serial} / T_{parallel}\)，并行效率 \(E = S / N\)（\(N\) 是线程数）。理想情况下 \(E \approx 1\)。如果 \(E < 0.5\)，说明并行化的收益被开销抵消了一半以上——需要分析原因。

第三步：区分瓶颈类型。

瓶颈类型	症状	诊断工具	优化方向
计算瓶颈	CPU 利用率高，线程都在计算	`perf stat`、火焰图	算法优化、SIMD
内存带宽瓶颈	加线程后速度不涨，cache miss 率高	`perf stat -e cache-misses`、`perf mem`	改数据布局、减少内存访问
锁竞争瓶颈	线程等待时间长，CPU 利用率低	`perf lock`、火焰图中 `futex_wait` 占比高	减少共享写、增大粒度、使用无锁结构
调度开销瓶颈	小任务太多，任务切换频繁	`perf stat -e context-switches`	增大 grain size、减少并行层数
假共享瓶颈	改变数组对齐方式后性能显著变化	`perf c2c`（cache-to-cache transfer）	对齐到 cache line 边界

第四步：使用专用工具。 Intel VTune 和 AMD uProf 提供了比 perf 更丰富的并行分析功能——包括线程时间线视图（能直观看到每个线程何时在计算、何时在等待）、锁竞争热点和内存带宽利用率。在有 Intel CPU 的开发环境中，VTune 是分析 TBB 和 OpenMP 程序的首选工具。

练习¶

[分析题]：对比 C++17 执行策略（std::execution::par）和 C++26 Senders/Receivers 在表达能力上的差异。举出 3 个 Senders/Receivers 能表达但执行策略不能表达的并行模式。
[分析题]：一个点云处理算法在 4 线程并行下加速比为 3.2，在 8 线程下加速比为 3.8。计算并行效率，分析为什么线程翻倍但加速比没有翻倍。使用 Amdahl 定律估算串行部分的比例。
[跨章综合题]：线程管理与互斥同步用 std::thread + 队列编排 SLAM 流水线；本节介绍了 taskflow 任务图和 C++26 Senders/Receivers。三种方式分别适合什么规模和复杂度的流水线？画出适用条件对比表。

19.16 Mini SLAM Parallel Processing Layer ⭐⭐⭐⭐¶

累积项目：本章新增模块¶

本章为 Mini SLAM 增加并行处理层，在线程管理与互斥同步的线程管理基础上，为点云算法提供可切换的执行策略。项目进度：线程管理与互斥同步线程安全队列 -> 原子操作与内存模型原子发布 -> 并行编程框架并行执行策略 -> 实时约束与高性能数据传递实时数据通道。

工程问题：把并行能力封装成可切换策略¶

本章项目为 Mini SLAM 增加一个并行处理层。目标不是写最复杂的调度器，而是把三个能力做扎实：

点云逐点变换。
残差并行评估。
体素下采样。

同时支持：

串行策略。
OpenMP 策略。
TBB 策略。

这样可以在同一套算法上比较后端差异。

模块结构¶

mini_slam_parallel/
  include/
    execution_policy.hpp
    point_types.hpp
    residual_evaluator.hpp
    voxel_downsample.hpp
    benchmark.hpp
  tests/
    test_parallel_correctness.cpp
    test_parallel_benchmark.cpp

`point_types.hpp`¶

#pragma once

#include <cstdint>

struct PointXYZI {
    float x = 0.0f;
    float y = 0.0f;
    float z = 0.0f;
    float intensity = 0.0f;
};

struct Plane {
    double nx = 0.0;
    double ny = 0.0;
    double nz = 1.0;
    double d = 0.0;
};

struct ResidualStats {
    double cost = 0.0;
    double max_abs = 0.0;
    std::uint64_t count = 0;
};

`execution_policy.hpp`¶

#pragma once

#include <cstddef>

struct SerialExecution {
    template <class Func>
    void forEach(std::size_t n, Func func) const {
        for (std::size_t i = 0; i < n; ++i) {
            func(i);
        }
    }
};

struct OpenMPExecution {
    int threads = 0;

    template <class Func>
    void forEach(std::size_t n, Func func) const {
        const int count = static_cast<int>(n);
        if (threads > 0) {
            #pragma omp parallel for num_threads(threads)
            for (int i = 0; i < count; ++i) {
                func(static_cast<std::size_t>(i));
            }
        } else {
            #pragma omp parallel for
            for (int i = 0; i < count; ++i) {
                func(static_cast<std::size_t>(i));
            }
        }
    }
};

TBB 策略可以放在单独头文件，只有启用 TBB 时编译：

#pragma once

#include <cstddef>
#include <tbb/blocked_range.h>
#include <tbb/parallel_for.h>

struct TBBExecution {
    std::size_t grainsize = 4096;

    template <class Func>
    void forEach(std::size_t n, Func func) const {
        tbb::parallel_for(
            tbb::blocked_range<std::size_t>(0, n, grainsize),
            [&](const tbb::blocked_range<std::size_t>& range) {
                for (std::size_t i = range.begin(); i != range.end(); ++i) {
                    func(i);
                }
            });
    }
};

`residual_evaluator.hpp`¶

#pragma once

#include <algorithm>
#include <cmath>
#include <vector>

inline double signedDistance(const PointXYZI& p, const Plane& plane) {
    return static_cast<double>(p.x) * plane.nx +
           static_cast<double>(p.y) * plane.ny +
           static_cast<double>(p.z) * plane.nz +
           plane.d;
}

template <class Execution>
ResidualStats evaluateResiduals(const std::vector<PointXYZI>& points,
                                const Plane& plane,
                                const Execution& execution) {
    std::vector<ResidualStats> partial;

    const std::size_t block_size = 4096;
    const std::size_t blocks =
        (points.size() + block_size - 1) / block_size;
    partial.resize(blocks);

    execution.forEach(blocks, [&](std::size_t block) {
        const std::size_t begin = block * block_size;
        const std::size_t end = std::min(begin + block_size, points.size());

        ResidualStats local;
        for (std::size_t i = begin; i < end; ++i) {
            const double r = signedDistance(points[i], plane);
            local.cost += r * r;
            local.max_abs = std::max(local.max_abs, std::abs(r));
            ++local.count;
        }
        partial[block] = local;
    });

    ResidualStats total;
    for (const ResidualStats& item : partial) {
        total.cost += item.cost;
        total.max_abs = std::max(total.max_abs, item.max_abs);
        total.count += item.count;
    }
    return total;
}

这里没有在每个点上做共享归约。外层按块并行。每个块生成一个局部统计。最后按块顺序合并。这兼顾了并行效率和可重复性。

`benchmark.hpp`¶

#pragma once

#include <algorithm>
#include <chrono>
#include <vector>

template <class Func>
std::vector<double> runTiming(Func func, int repeats) {
    using Clock = std::chrono::steady_clock;
    std::vector<double> ms;
    ms.reserve(static_cast<std::size_t>(repeats));

    for (int i = 0; i < repeats; ++i) {
        const auto t0 = Clock::now();
        func();
        const auto t1 = Clock::now();
        ms.push_back(
            std::chrono::duration<double, std::milli>(t1 - t0).count());
    }

    std::sort(ms.begin(), ms.end());
    return ms;
}

正确性测试¶

#include <cassert>
#include <cmath>

bool closeEnough(double a, double b) {
    const double diff = std::abs(a - b);
    return diff <= 1e-9 * std::max({1.0, std::abs(a), std::abs(b)});
}

void testResidualPolicies() {
    const std::vector<PointXYZI> points = makeSyntheticCloud(100000);
    const Plane plane{0.0, 0.0, 1.0, -1.0};

    const ResidualStats serial =
        evaluateResiduals(points, plane, SerialExecution{});
    const ResidualStats omp =
        evaluateResiduals(points, plane, OpenMPExecution{4});

    assert(serial.count == omp.count);
    assert(closeEnough(serial.cost, omp.cost));
    assert(closeEnough(serial.max_abs, omp.max_abs));
}

测试不要求逐 bit 完全一致。它要求统计意义一致。如果项目有确定性需求，可以固定分块合并顺序。

运行建议¶

至少测试这些输入规模：

点数	目的
1k	验证小规模开销
100k	常见实时点云规模
1M	高负载扫描
10M	离线批处理

至少测试这些线程数：

线程数	目的
1	对照
2	基础扩展性
4	常见嵌入式 CPU
8+	桌面或工作站

记录：

p50 延迟。
p90 延迟。
p99 延迟。
加速比。
并行效率。
CPU 温度或频率变化。

🔧 故障排查手册¶

现象	常见原因	检查方法	修复方向
并行版本比串行慢	输入太小或粒度太细	改变 block size	增大粒度或保留串行
线程越多越慢	内存带宽或锁竞争	perf、火焰图、锁统计	分区、局部容器、减少共享写
结果每次略有差异	浮点归约顺序变化	固定输入重复运行	误差容忍或确定性归约
偶发崩溃	共享容器并发写	TSan、代码审查	预分配输出或局部容器
p99 延迟很高	调度抖动或过度订阅	记录分位数和线程数	限制并行度
CPU 满载但速度不涨	内存带宽瓶颈	监控 cache miss	改数据布局
OpenMP 链接失败	编译选项缺失	检查构建日志	添加正确编译和链接选项
TBB 版本不兼容	API 或包名变化	查官方文档	固定依赖版本
嵌套并行卡顿	多层库同时开线程	打印线程数	上层统一预算
单测严格相等失败	浮点误差	改用容忍比较	固定归约或调整阈值

19.17 本章小结¶

并行编程框架的核心不是 API 名字，而是工作划分。 OpenMP 适合快速并行化已有循环。 TBB 适合现代 C++ 库中的可组合并行。任务图适合表达阶段依赖。三者都不能替你判断算法依赖关系，也不能自动修复共享写入。

主题	核心判断
并行前提	先写清楚读写集合，确认迭代间无依赖
Amdahl 定律	串行部分决定加速比上限
OpenMP	最低侵入，适合已有循环，`schedule` 控制负载分配
TBB	C++ 类型系统集成，`task_arena` 提供组合安全性
归约	先局部再合并，接受浮点顺序变化
框架选型	代码形态、负载均匀性、依赖约束决定选择
C++26 Senders/Receivers	标准化异步任务组合，支持依赖图和取消
SYCL	异构并行的统一模型，GPU offloading 的可移植方案
性能分析	先基准、再加速比、再区分瓶颈类型
线程预算	线程数是系统资源，不是单个函数的私有参数

本章的主线可以压缩成五条：

先写清楚串行基准，再谈并行。
每个并行迭代都必须有明确读写集合。
归约要先局部、再合并，并接受浮点顺序变化。
框架选择服务于代码形态，不服务于流行程度。
线程数是系统预算，不是单个函数的私有资源。

从下一章开始，我们会进一步收紧约束。并行框架追求吞吐和平均性能。实时系统追求截止时间、最坏情况和尾延迟。这两种目标经常冲突。实时约束与高性能数据传递将讨论实时约束、高性能数据传递、无分配热路径、优先级反转和 ROS2 执行器边界。

延伸阅读¶

OpenMP 官方规范（openmp.org），重点关注 OpenMP 5.2（2021）的任务依赖和 target offloading。⭐⭐
oneTBB 官方文档（oneapi-src/oneTBB），重点阅读 parallel_for、parallel_reduce、task_arena 和 global_control。⭐⭐
C++ 标准库并行算法文档（cppreference），理解执行策略和异常边界。⭐⭐
P2300R10（C++26 std::execution Senders/Receivers 提案）：了解未来 C++ 异步和并行的标准化方向。⭐⭐⭐⭐
stdexec（NVIDIA 开源的 P2300 参考实现）：在标准发布前体验 Senders/Receivers。⭐⭐⭐⭐
taskflow 官方文档和论文（Huang et al., "Taskflow: A Lightweight Parallel and Heterogeneous Task Graph Computing System", IEEE TPDS 2022）。⭐⭐⭐
SYCL 2020 规范（Khronos Group）和 AdaptiveCpp（原 hipSYCL）文档。⭐⭐⭐⭐
机器人 SLAM 项目中的点云滤波、残差评估、最近邻查询的并行实现（FAST-LIO2、Point-LIO 源码）。⭐⭐⭐
Brendan Gregg, Systems Performance, 2nd Edition：Linux 性能分析的系统教材，含 perf、火焰图、eBPF 的深入讲解。⭐⭐⭐
Intel VTune Profiler 文档：并行程序的线程分析、锁竞争分析和内存带宽分析。⭐⭐⭐