附加章九：并行计算基础

复习

指令流水线：CPU 按周期执行指令，并可用流水线提高吞吐
缓存一致性：多核之间需要处理缓存一致性问题

TL;DR

并行就是“让多个人同时干活”，但协调和通信本身也有成本
并行分好几个层次：位级、指令级、数据级、任务级
阿姆达尔定律告诉我们：串行部分决定了并行加速的上限
共享内存和分布式内存是两种主要的并行系统架构

正文

　　前几章里，我们一直想方设法让一个 CPU 更快：流水线、缓存、乱序执行……但再快也有物理极限，怎么办？

　　计算机科学的老办法又来了：既然一个人干不快，那就多叫几个人——并行计算。

并行的几个层次

　　“并行”这个词很宽泛，从最底层到最高层，至少有四层：

位级并行：一次处理更多位。8 位加法器一次算 8 位，32 位一次算 32 位
指令级并行：多条指令同时执行，比如指令流水线、超标量
数据级并行：同样的操作，作用在一大批数据上。比如向量加法，一次算 8 个元素
任务级并行：不同的任务分给不同核心。比如一个核心处理图像、一个处理音频

　　越往上，粒度越粗，软件要操心的协调也越多。

两种系统架构

　　多个人一起干活，得先决定“东西放哪”。并行系统主要分两种：

共享内存：所有 CPU 共用一块内存，谁都能访问同一份数据。编程方便，但人多了容易抢，还要处理缓存一致性
分布式内存：每个 CPU 有自己的内存，彼此靠网络通信。扩展性好，但传数据要走网络，开销大

　　可以把共享内存想象成一间公共办公室，大家随手就能拿到资料；分布式内存则像几间独立办公室，要资料得打电话让对方送过来。

阿姆达尔定律

　　多叫几个人，活儿就能快几倍吗？不一定。这就引出了阿姆达尔定律：

加速比 = 1 / (串行部分比例 + 并行部分比例 / 处理器数)

　　举个例子：一个程序 95% 的部分可以并行，5% 必须串行。哪怕你用 4 个处理器：

加速比 = 1 / (0.05 + 0.95/4) ≈ 3.48

　　就算处理器增加到无穷多个，那 5% 的串行部分仍然会把加速比死死压在 20 倍以内。

　　结论很朴素：一个人必须自己干的那部分，决定了团队能快多少。 想真正提速，往往得先想办法减少“串行部分”。

粒度的权衡

　　并行还有个绕不开的取舍——粒度，也就是“一次分多大的任务”：

分得太细：每个子任务很快干完，但协调、通信的开销反而占了大头
分得太粗：通信少了，但容易出现“有人累死、有人闲着”的负载不均

　　最好的粒度，是让每个处理器分到的工作量差不多，同时通信开销又不太高。这没有标准答案，得看具体问题。

别忘了缓存一致性

　　还记得前面提过的缓存一致性问题吗？在多核并行里，它变得更关键。缓存一致性协议负责协调同一内存位置在不同核心缓存中的副本，让各核心对这个位置的写入顺序形成一致认识。但这并不自动保证多次内存操作的先后关系，也不能把“读取、计算、写回”这样的复合操作变成不可分割的一步。

　　因此，并行程序除了“分任务”，还要处理同步和内存顺序。多个线程在没有同步的情况下同时读写同一变量，可能形成数据竞争；常见办法包括用互斥锁保护临界区、用原子操作更新简单状态、用屏障协调阶段。信号量主要用于计数或协调资源，只有二元信号量在特定用法下才类似互斥锁。同步用得好能保证正确性，用得不好则会拖慢程序，甚至引发死锁（这会在操作系统部分细讲）。

思考题