并行与向量化（SIMD）

1. 为什么需要并行：三类并行层级

CS61C 的核心立场是"把一台机器抽象出来给你看"。在"机器"这一层，性能提升几乎都来自并行——让硬件在同一时刻做更多事。并行按粒度从细到粗分成三类：

指令级并行（ILP, Instruction-Level Parallelism）：单条指令内部、或相邻指令之间重叠执行。我们前面讲过的流水线、乱序执行、转发（forwarding）都属于这一类。
数据级并行（DLP, Data-Level Parallelism）：同一份操作，作用在很多个数据点上。典型场景是"对 100 万个像素都加 10""把两个等长数组逐元素相加"。
线程级并行（TLP, Thread-Level Parallelism）：多核，每个核心跑不同的线程，甚至不同程序。

本篇聚焦 DLP，因为它最"便宜"：不需要多核、不需要改算法、不需要加锁，很多时候只把数据组织方式改一改，或者让编译器帮个忙，就能白捡数倍吞吐。

本质一句话：当同一件事要在大量数据上重复做时，就把"一次做一件"升级成"一次做一批"。

2. SIMD 是什么：一条指令，多份数据

传统 CPU 是 SISD（Single Instruction, Single Data）：每个时钟周期，一个 ALU 对一个数据做一次运算。

SIMD（Single Instruction, Multiple Data）则是：一个"宽指令"同时对多个数据做同一运算。比如一条 paddd（packed integer add）指令，能一次性把两个 128 位寄存器里的 4 个 32 位整数分别相加。

下面这张图对比了同样"算 4 个加法"在两种模型下的差别：

SISD 要 4 个周期（4 条 add），SIMD 只要 1 个周期（1 条 paddd）。理想情况下吞吐提升 = 向量里 lane（通道）的数量。

3. 为什么 SIMD 快：三个瓶颈同时被缓解

SIMD 不是"凭空变快"，它同时缓解了你机器上的三个瓶颈：

取指/译码开销被摊薄：原来循环要反复取"add 指令"、译码、自增索引；现在一条宽指令顶 4 次，控制开销降到 1/4。
内存带宽利用率上升：一次从内存/缓存搬 128 位（4 个 int），而不是 32 位。缓存行（通常 64 字节）能被一次吃满，不用反复为单个元素发内存请求。
ALU 利用率上升：向量寄存器里的 4 个 lane 同时算，功能单元不再"饿着"。

在 x86 上，128 位的 XMM 寄存器可装 4 个 int32；到了 AVX/AVX2 的 256 位 YMM，能装 8 个 int32；AVX-512 的 ZMM 更达 16 个。ARM 端的 NEON（128 位）与更新的 SVE 也是同一思想。下面这张图表示一个 128 位向量寄存器是怎么"并排"装下 4 个 32 位整数的：

4. 编译器自动向量化（auto-vectorization）

获取 SIMD 收益最简单的方式：写出"干净"的循环，让编译器在 -O3 下替你生成 SIMD 指令。所谓"干净"，指循环没有数据依赖、没有复杂分支、步长固定、访问连续内存。

下面这段标量代码，人类读起来是"一个一个加"，但 x86 上用 gcc -O3 编译后，循环体里出现的不是 8 条普通 addl，而是一条 paddd（packed integer add）：

#include <stdio.h>
#define N 8

int main(void) {
    int a[N] = {1, 2, 3, 4, 5, 6, 7, 8};
    int b[N] = {10, 20, 30, 40, 50, 60, 70, 80};
    int c[N];

    for (int i = 0; i < N; i++)        // 编译器在 -O3 下会把它向量化成 SIMD
        c[i] = a[i] + b[i];

    printf("c = ");
    for (int i = 0; i < N; i++) printf("%d ", c[i]);
    printf("\n");
    return 0;
}

运行输出：

1	c = 11 22 33 44 55 66 77 88

用 gcc -O3 -S simd_add.c | grep paddd 通常能看到类似 paddd %xmm1, %xmm0 的指令——这就是编译器替你做的 SIMD。对应的 Java 侧，HotSpot 的 C2 编译器对同样干净的 for 循环（如对一个 int[] 做逐元素加法）也会做自动向量化，思想完全一致，只是你写的是 Java 而非 C。

工程经验：现代编译器的自动向量化往往已经接近手写 intrinsics 的水平。所以先写清晰的标量代码，再用性能分析（profiling）找出真热点，最后才考虑手写 intrinsics。不要一上来就手写汇编级代码。

5. 手写向量内在指令（intrinsics）

当编译器"不敢"向量化（比如循环里有数据依赖、有分支、或你明确要榨干某条指令），就用手写 intrinsic（内在函数）。intrinsic 是编译器提供的一组"长得像函数、实际直接映射到单条 SIMD 指令"的接口。下面以 x86 的 SSE2（128 位，4 个 int32）为例，亲手把"加 8 个数"写成 2 趟 SIMD：

#include <stdio.h>
#include <emmintrin.h>   // SSE2 头文件：_mm_xxx 系列内在函数

#define N 8

int main(void) {
    int a[N] = {1, 2, 3, 4, 5, 6, 7, 8};
    int b[N] = {10, 20, 30, 40, 50, 60, 70, 80};
    int c[N];

    for (int i = 0; i < N; i += 4) {                 // 每趟处理 4 个 int
        __m128i va = _mm_loadu_si128((__m128i*)(a + i)); // 一次加载 128 位（4 个 int）
        __m128i vb = _mm_loadu_si128((__m128i*)(b + i));
        __m128i vc = _mm_add_epi32(va, vb);           // 一条指令加 4 个 int32
        _mm_storeu_si128((__m128i*)(c + i), vc);      // 一次写回 128 位
    }

    printf("c = ");
    for (int i = 0; i < N; i++) printf("%d ", c[i]);
    printf("\n");
    return 0;
}

运行输出与标量版本完全一致：

1	c = 11 22 33 44 55 66 77 88

关键点都在名字里：_mm_loadu 的 u 表示 unaligned（允许非对齐加载），_epi32 表示 element-of-32-bit integer（按 32 位整数逐通道运算）。这里 8 个元素只循环 2 趟，每一趟一条 paddd 干完 4 个加法：

6. SIMD 的局限与陷阱

SIMD 不是银弹，下面这些"坑"会让你写了代码却没提速，甚至变慢：

数据依赖（carried dependency）：若 c[i] = c[i-1] + a[i]，第 i 个结果依赖第 i-1 个，lane 之间没法并行，编译器只能老老实实标量。
分支发散（branch divergence）：循环体里 if (a[i] > 0) 且每个元素真假不一，SIMD 得"两个分支都算、再用掩码合并结果"，开销反而可能更大。
内存对齐：_mm_loadu 允许非对齐但更慢；若数据按 16 字节对齐，用 _mm_load_si128 更快。数组用 _mm_malloc(..., 16) 或 C11 的 aligned_alloc 保证对齐。
尾部元素（remainder）：元素总数不是向量宽度的整数倍时（如 10 个 int 对 4-lane），最后 2 个要用标量循环"收尾"，否则越界。
可移植性差：SSE/AVX 是 x86 的，NEON 是 ARM 的，指令名和寄存器宽度都不同。跨平台项目要么抽象一层，要么直接交给编译器/库去处理。

一个反直觉的事实：手写 intrinsics 不一定比编译器自动向量化快。编译器知道目标微架构的细节（吞吐、延迟、哪些指令能配对），手工写的"好指令"若不符合流水线特性，反而更慢。所以 intrinsics 是"最后 10% 的优化"，不是起点。

7. 更高层视角：Python / NumPy 与硬件

SIMD 离你写的应用并不远。下面这段 Python 和上面的 C 做的是完全相同的事，但快得多——因为 NumPy 的 a + b 底层就是用 C + SIMD 实现的：

import numpy as np

a = np.array([1, 2, 3, 4, 5, 6, 7, 8], dtype=np.int32)
b = np.array([10, 20, 30, 40, 50, 60, 70, 80], dtype=np.int32)
print("c =", a + b)

输出：

1	c = [11 22 33 44 55 66 77 88]

而如果你用纯 Python 写 for 循环逐元素相加，会慢几个数量级——因为 CPython 的循环本身没有被向量化，每个 a[i] + b[i] 都是解释器层面的标量操作。这正好印证了第 4 节的结论：想提速，要么靠编译器，要么靠底层已经向量化的库（NumPy / BLAS / 各种 SIMD 加速的图像处理库）。

顺带一提：你手头的 RK3588（4×A76 + 4×A55）跑的是 ARM 指令集，它的 SIMD 叫 NEON（128 位，类似 XMM）。同样的"向量加"思想在 ARM 上照样成立，只是 intrinsic 名字换成 vaddq_s32 这类。SVE（Scalable Vector Extension）更进一步，向量长度可变，对异构芯片更友好。

8. 小结：三种"写法"怎么选

维度	标量循环	手写 SIMD（intrinsics）	NumPy / 向量化库
写法难度	最低	高（需懂指令集与对齐）	最低
性能上限	基线 1×	最高（2–8×，视向量宽度）	接近手写 SIMD
可移植性	最高	差（SSE/AVX/NEON 各异）	高
可维护性	高	低	高
编译器能否自动搞定	能（干净循环 + `-O3`）	不需要	已内置

一句话收尾：SIMD 是"用更宽的寄存器 + 一条指令批量算"来压榨数据级并行。日常开发里，先写清晰标量代码交给编译器向量化，热点再用 intrinsics 收口，库调用优先用已向量化的实现——这条路径既稳又快，也最能经得起不同芯片（x86 / ARM）的考验。

🐾 下一篇（2024-11-28）我们聊中断与 I/O：当 CPU 不再只顾算，外部设备怎么"打断"它、数据又怎么搬进搬出。