第一章 · OpenMP

为什么我们需要并行？

现代 CPU 通常都包含多个核心（Core），每一个核心在同一时刻只能执行一条指令（Instruction）。你之前写过的各种程序，在默认情况下都只运行在一个线程（Thread）中，而操作系统通常只会把这个线程分配到一个 CPU 核心上执行。这意味着，如果你什么都不做，即使你的电脑上有 8 个、16 个甚至更多的核心，事实上只有一个核心在执行你写的程序，其余的处于空闲状态。

这确实很令人难过，一方面是因为花钱买了电脑却发现只用了它一点点性能；另一方面，有些时候它真的跑的很慢！

比如你可能有一个有趣的功能，我们就暂时称它为 do_something_good() 吧，你可能真的会想对 1000 个输入进行你有趣的操作？所以出于直觉你一下子就写出了你最擅长的 for 循环（相信大部分人应该更喜欢写 for 吧），熟练的填上大一就写烂的 i++，编译执行！

int sum = 0;

for (int i = 0; i < 1000; i++) {
    sum += do_something_good(i);
}

然而大部分时候它看起来也是在瞬间完成的，就像你在大一的时候写的 C 语言作业一样快。

毕竟你写的 do_something_good() 应该也没有多复杂就是了。你的电脑还是没有那么笨的，但是并不代表它真的一直都很聪明。总有一天你发明出了一些比较复杂的函数，比如一个自动完成你作业的函数 do_my_homework()，用在操作系统每周的作业上，学习通有那么多题，写一题要 10 秒的话，写 50 题就需要快九分钟！

for (int i = 0; i < 50; i++) {
    do_my_homework(); // 10 秒一次
}

如果你还记得一些计算机组成原理的知识的话，或许你已经忘了，你应该知道 CPU 的一个核心一个时候只能做一件事情。哪怕忘了也没有关系，希望你对做实验的那台上古电脑和仪器有点印象，从 PC 程序计数器出来的东西一次只有一个，实际上它确实只有一个，所以单核心的 CPU 和人脑一样，它一次也只能做一道题。

你买电脑的时候肯定看过吧，至少知道电脑有几个核心，或者起码知道它肯定不是单核的。反正你突然觉得如果可以让我的电脑的好几个核心同时帮我写作业应该是一件很酷的事情，但是还是不要去破解学习通哈。

从手动并行到 OpenMP

我们当然可以手动创建和管理多个线程（例如使用 std::thread 或 pthread）。这种方式虽然非常灵活，但需要自己处理线程创建、任务划分、数据同步等问题，代码复杂容易出错。我们不希望自己分配，学会高效偷懒是进步的开始，创建线程，四五个可能还好，那几十个呢？

所幸，OpenMP 可以为我们创建这些处理线程的程序，它也是一套编译器指令（Compiler Directives），通过在代码里加入 #pragma omp 开头的指令，编译器会自动完成，创建数量合适的线程、循环迭代分配并处理线程同步。

最基础的用法是在 for 循环前添加 parallel for 指令：

#pragma omp parallel for
for (int i = 0; i < 1000; i++) {
    // 一些比较慢的操作
    // 比如做 1000 次 printf()
}

此时，编译器会在生成的程序中为你创建并管理线程，把这 1000 次任务均匀分给它们；操作系统就会调度这些线程到 CPU 核心上去执行。

为什么需要 Reduction ？

看起来很完美对吧？但如果我们直接把刚才求和的代码加上这句魔法：

int sum = 0;

#pragma omp parallel for
for (int i = 0; i < 1000; i++) {
    sum += calculate_complex_math(i);
}

程序会算出一个完全错误的随机数！为什么？

我们虽然只写了一句 sum += calculate_complex_math()，但是在硬件执行时，分为了Load + Add + Store三步。

让我们复习一下计组课上的知识希望你还没忘光：计算机中所有的数据和指令都存放在内存中，CPU 硬件电路里有一个 PC（程序计数器） 指针，指向当前要执行的指令在内存中的位置。每执行完一条指令，PC 就自动 +1，指向下一条。变量 sum 的值也在内存中，Load 指令会把它从内存加载到 CPU 的寄存器中，加法器执行 Add 指令将两个寄存器中的数相加，最后 Store 指令把结果写回内存保存。

当两个线程同时对 sum 进行"Load → Add → Store"时，混乱就发生了。假设下面的指令按时间顺序依次发生：

线程 2 辛辛苦苦算出来的 5 被线程 1 的 Store 直接覆盖了，因为线程 1 在 t1 时刻读到的还是旧值 0，它根本不知道线程 2 已经更新过了。这就是经典的 Lost Update（丢失更新） 问题。

怎么解决？

先退一步想想：sum += x 到底是什么操作？它把一堆值逐步折叠成一个最终结果——1000 个计算结果，经过 1000 次 +，最终变成一个数。这种多变一的操作，在计算机科学里有一个专门的名字：归约（Reduction）。

Reduction 的特征很简洁：

• 有一个二元运算符：+、*、max（取最大值）、min（取最小值） 等等
• 有一个初始值（单位元）：加法是 0，乘法是 1，max 是负无穷...
• 不断把新值和累积结果合并，最终从 $n$ 个值变成 $1$ 个值

初始值是由计算的性质决定的。对于加法：任何数加上初始值 0，都保持原值。对于乘法，任何数乘以 1 也保持原值。max 和 min 同理。

注意，并不是所有的并行循环都需要 reduction。如果你的循环里每次迭代只写自己的数据，比如 result[i] = f(i)，或者只是重复 printf()，各个线程互不干扰，一个简单的 parallel for 就够了。只有当多个迭代需要往同一个共享变量上累积时——也就是做 reduction 操作时——才需要额外处理。

理解了这一点，解法就自然了：既然 reduction 最终要把所有值合并，那就让每个线程先在自己的局部变量上做局部归约，等所有线程都算完了，再把各自的局部结果按运算符合并成最终值。

OpenMP 把这个过程封装成了一个指令：reduction。

#pragma omp parallel for reduction(+:sum) 
for (int i = 0; i < 1000; i++) {
    sum += calculate_complex_math(i);
}

reduction(+:sum) 告诉编译器三件事：

1. 为每个线程创建一个 sum 的局部副本。
2. 因为运算符是 +，所以局部副本的初始值设为 0（加法的单位元。如果是 *，初始值就是 1）。
3. 循环结束后，自动把所有局部副本按 + 合并到最终的 sum 变量里。

为什么还需要调度？

Reduction 解决了数据正确性的问题。但性能呢？

如果这 1000 次 calculate_complex_math(i) 的计算量不均匀——有的是极其复杂的运算，有的几乎瞬间完成——那么 OpenMP 默认的 static（静态分配） 就会出问题：它把 1000 次迭代均分成 4 份，每个线程 250 次。如果线程 A 分到的全是重计算，其他三个线程早就算完了，整个程序的耗时完全被最慢的那个线程拖垮。

怎么解决？

改变分配策略：dynamic（动态分配）。不提前分配了，而是维护一个公共的任务队列。谁先做完手上的迭代，谁就去队列里再领一个。能者多劳。

#pragma omp parallel for schedule(dynamic) reduction(+:sum) 
for (int i = 0; i < 1000; i++) {
    sum += calculate_complex_math(i);
}

注意这里 schedule(dynamic) 和 reduction(+:sum) 可以组合使用——前者管任务怎么分配，后者管共享变量怎么合并，各司其职。

隐藏的性能瓶颈！ 这个公共任务队列本身就是一个临界资源就像寝室里只有一个卫生间，每次只允许一个线程来领任务。如果每做完一次迭代就跑去排队领下一个，排队的开销甚至可能比计算本身还大！

所以我们让每个线程一次领走一块（chunk） 迭代：

#pragma omp parallel for schedule(dynamic, 8) reduction(+:sum) 
for (int i = 0; i < 1000; i++) {
    sum += calculate_complex_math(i);
}

这里的 8 就是 chunk 大小：每次领 8 个迭代回去算，减少排队次数。

除了 schedule(dynamic) 我们还有另一种选择，schedule(guided)。

guided 结合了静态和动态的优点：一开始任务多的时候，一次分一大块（比如 100 次迭代），极大减少排队开销；随着剩余任务减少，每次分的块越来越小（最后可能只分 1 个），防止有线程在最后领了一大堆重计算而其他线程全在等它。 也就是：前期大块分减少排队开销，后期小块分保证负载均衡。

了解了这些，你就会明白："并行"绝不是简单地多加几个 CPU 那么简单。 背后是无数天才工程师在硬件和操作系统层面上做出的精妙妥协。