一、并行计算基础
各位同学好，今天我们来聊聊并行计算的基础知识。这部分内容，说白了就是整个执行引擎并行化设计的理论根基。我个人习惯先把概念理清楚，再动手做设计，这样后面踩坑会少很多。
1.1 并行计算概念
什么是并行计算？简单说，就是同时用多个计算资源去解决一个问题。你想想看，一个任务如果一个人干要10小时，那10个人一起干是不是理论上1小时就能搞定？当然，现实没这么理想，但思路就是这个思路。
我在项目中遇到过不少同学，把「并发」和「并行」搞混了。这里我简单区分一下：
- 并发（Concurrency）：多个任务在同一个时间段内交替执行，看起来像同时进行。比如单核CPU上跑多线程。
- 并行（Parallelism）：多个任务在同一个时刻真正同时执行。比如多核CPU上跑多线程。
核心要点：并发是逻辑上的同时，并行是物理上的同时。我们的执行引擎并行化，追求的是真正的并行。
并行计算通常分为三个层次：
- 位级并行：处理器字长增加，一次能处理更多位数据。比如从32位到64位。
- 指令级并行：处理器在一个时钟周期内执行多条指令。比如流水线、超标量。
- 线程级/进程级并行：多个线程或进程同时执行。这是我们今天讨论的重点。
1.2 并行计算模型
并行计算模型，说白了就是「多个计算单元怎么协同工作」。我把它分成两大类：共享内存和分布式内存。这两种我都实际用过，各有各的坑。
1.2.1 共享内存模型
共享内存模型，就是所有处理器共享同一个地址空间。大家都能读写同一块内存。听起来很方便对吧？但问题也出在这里。
- 优点：编程相对简单，数据共享方便，通信开销低。
- 缺点：扩展性受限，容易出现竞争条件，需要锁机制来保护共享数据。
举个例子，OpenMP就是典型的共享内存编程模型。我曾经在一个图像处理项目里用OpenMP做并行加速，效果确实不错，但调试死锁问题差点让我崩溃。
避坑指南：共享内存模型下，一定要注意缓存一致性问题。我曾经因为忽略了CPU缓存行对齐，导致多核性能反而比单核还差。嗯，这个教训挺深刻的。
1.2.2 分布式内存模型
分布式内存模型，每个处理器有自己的私有内存，通过消息传递来通信。MPI（Message Passing Interface）是典型的代表。
- 优点：扩展性好，可以构建大规模集群，没有内存竞争问题。
- 缺点：编程复杂，数据需要显式地在节点间传输，通信开销大。
我建议你在设计执行引擎时，先想清楚你的场景更适合哪种模型。如果是单机多核，共享内存模型更合适；如果是集群环境，分布式内存模型是必然选择。
注意：分布式内存模型下，通信开销往往是性能瓶颈。我曾经在一个项目中，计算只花了10ms，但数据同步花了200ms。这种时候，减少通信次数比优化计算更重要。
下面我用一张SVG图来展示这两种模型的区别：
1.3 并行计算性能指标
做并行化设计，你得知道怎么衡量效果好不好。不然你辛辛苦苦改了代码，结果性能没提升，那不是白干了吗？这里我重点讲两个指标：加速比和效率。
1.3.1 加速比（Speedup）
加速比的定义很简单：加速比 = 串行执行时间 / 并行执行时间
举个例子，一个任务串行跑要100秒，用4个处理器并行跑用了30秒，那加速比就是100/30 ≈ 3.33。理想情况下，4个处理器应该达到4倍的加速比，但现实往往达不到。
为什么会这样？这里有个著名的定律——阿姆达尔定律（Amdahl's Law）。它告诉我们：
阿姆达尔定律：加速比的上限受限于程序中必须串行执行的部分。如果程序中有10%的部分必须串行执行，那即使有无穷多个处理器，最大加速比也不会超过10。
公式是这样的：
加速比 ≤ 1 / (串行比例 + 并行比例 / 处理器数量)当处理器数量趋于无穷大时，加速比趋近于 1 / 串行比例。
我在项目中遇到过这样的情况：一个看起来很适合并行的任务，实际加速比只有理论值的60%。后来一分析，发现是数据同步和锁竞争消耗了大量时间。嗯，这就是串行开销在作怪。
1.3.2 效率（Efficiency）
效率衡量的是处理器资源的利用程度：效率 = 加速比 / 处理器数量
还是刚才的例子，加速比3.33，用了4个处理器，效率就是3.33/4 ≈ 0.83，也就是83%。
效率越接近1，说明处理器资源利用得越好。如果效率很低，比如只有50%，那说明有一半的处理器时间都浪费在了通信、同步或者等待上。
| 处理器数量 | 理想加速比 | 实际加速比 | 效率 |
|---|---|---|---|
| 1 | 1.00 | 1.00 | 100% |
| 2 | 2.00 | 1.85 | 92.5% |
| 4 | 4.00 | 3.33 | 83.3% |
| 8 | 8.00 | 5.71 | 71.4% |
| 16 | 16.00 | 8.89 | 55.6% |
个人经验：我一般把效率低于50%作为警戒线。如果效率掉到50%以下，说明并行化的收益已经很小了，这时候应该回头看看是不是设计上出了问题，而不是盲目增加处理器数量。
1.3.3 可扩展性（Scalability）
可扩展性衡量的是：随着处理器数量增加，系统性能能否线性提升。分为两种：
- 强可扩展性：问题规模固定，增加处理器数量，看加速比能否线性增长。
- 弱可扩展性：每个处理器的负载固定，增加处理器数量的同时增加问题规模，看执行时间能否保持不变。
我建议你在设计执行引擎时，优先考虑弱可扩展性。因为实际业务中，数据量往往是增长的，而不是固定不变的。
注意：不要被「理论加速比」迷惑。我曾经见过一个团队，理论计算说用32个处理器能达到30倍加速比，结果实际跑出来只有8倍。原因就是忽略了通信开销和负载不均衡。记住，理论是理想情况，现实总有各种开销。
好了，并行计算的基础知识就讲到这里。这些概念虽然基础，但非常重要。后面的章节我们会基于这些理论，一步步设计出高效的并行执行引擎。
公众号:蓝海资料掘金营，微信deep3321