Lecture 2: A Modern Multi-Core Processor (Part I)（日期：Sep 25, 2025）

目录 · ← l1 · l3 →

Lecture 2: A Modern Multi-Core Processor (Part I)（日期：Sep 25, 2025）

概述：本讲从”软件工程师视角”讲计算机体系结构，回答一个问题：现代并行处理器如何获得高吞吐（high throughput）？核心是三种并行执行形式：multi-core（多核，TLP）、SIMD（数据并行，DLP）与hardware multi-threading（硬件多线程，隐藏访存延迟）。课程先复习第 1 讲的指令流、处理器与 cache 基础，然后用同一个 sinx（泰勒展开算 sin）程序贯穿全场：先看它如何用 C++ 线程拆到多核，再看如何用 AVX intrinsics 向量化（SIMD），最后讨论分支导致的分歧执行（divergent execution）与多线程如何用”换线程干活”来隐藏内存停顿。

一、核心概念与定义

1. 复习：Instruction Stream（指令流）与处理器组成

定义：程序编译后就是一条指令流（list of processor instructions）。一个简单处理器由三部分组成：Fetch/Decode（取指/译码，决定下一步执行哪条指令）、Registers（寄存器，保存程序状态/运算输入输出）、Execution Unit / ALU（执行单元，执行指令描述的操作）。简单处理器每时钟执行一条指令。
现实类比：指令流 = 菜谱步骤清单；取指/译码 = 看菜谱决定下一步；寄存器 = 手边备好的食材（中间量）；ALU = 灶台（执行动作）。

公式/图示：

+--------------------------------------------------+
\|  Execution Context (registers R0..R3 + PC)       |
|        ▲                    │                    |
|  Fetch/Decode          Execution Unit (ALU)      |
|  （决定下一条指令）      （执行运算/访存）          |
+--------------------------------------------------+
      ▲
 内存中的指令流：ld r0, addr[r1] → mul r1,r0,r0 → ... → st addr[r2],r0

2. 复习：Superscalar Execution（超标量执行）与 ILP

定义：超标量处理器自动在单条指令流中寻找互不依赖的指令，把它们并行放到多个执行单元上执行（如每时钟译码并执行 2 条指令），由 out-of-order control logic（乱序控制逻辑） 完成调度。关键约束：”respect program order”——乱序调度后程序的输出必须与按原顺序执行完全一致（即只在不改变结果的前提下重排）。
现实类比：流水线上的两道互不相关的工序（贴标签 + 装箱）可以同时进行；但”先贴标签再装箱”的依赖工序必须等标签贴完。

公式/图示：依赖图示例（幻灯片 a=2, b=4 例子）：

程序（按 PC 顺序）              指令依赖图（箭头 = 数据依赖）
a = 2                      00 ─┐
b = 4                      01 ─┤
tmp2 = a + b   // 6        02 ◄─┘ (依赖 00,01)
tmp3 = tmp2 + a // 8       03 ◄─ 02, 00
tmp4 = b + b   // 8        04 ◄─ 01
tmp5 = b * b   // 16       05 ◄─ 01
tmp6 = tmp2 + tmp4 // 14   06 ◄─ 02, 04
tmp7 = tmp5 + tmp6 // 30   07 ◄─ 05, 06
if (tmp3 > 7) ...          08 ◄─ 03

无依赖的指令（如 02 与 04、05）可并行执行；依赖链（00→02→03→08）必须串行。

3. Multi-Core Processor（多核处理器）与 TLP

定义：Idea #1（幻灯片原话）：与其把晶体管花在”让单条指令流跑得更快”的复杂逻辑（乱序、投机、更大 cache、更聪明分支预测、预取器）上，不如用晶体管换更多核。每个核独立取指/译码、运行完全不同的指令流，提供 thread-level parallelism（TLP，线程级并行）。代价：更简单的核跑单条指令流可能更慢（幻灯片例子：每个核慢 25%，双核 = 2 × 0.75 = 1.5 的潜在加速）。
现实类比：与其雇一个”全能超人”（复杂单核），不如雇几个普通员工并行干活（多核）——单个员工略慢，但人多总吞吐更高。

公式/图示：

前多核时代：  [复杂单核: 大 cache + 乱序 + 分支预测 + 预取]  ← 晶体管堆给单条指令流
多核时代：    [核][核][核][核] ...                          ← 晶体管换更多核

关键：软件不表达并行，多核就没有任何收益。若程序仍编译成单线程指令流，它只会跑在其中一个核上，甚至因单核变简单而变慢（25% 更慢）。

4. Data-Parallel Expression（数据并行表达，forall）

定义：用 forall 声明”循环迭代互相独立“（幻灯片中的虚构语言；ISPC 的 foreach 是它的真实实现）。迭代之间无数据依赖 → 编译器/运行时可以自动生成多线程代码、或向量指令。
现实类比：批改 100 份相同试卷——每份独立评分（迭代独立），可同时交给多个老师批。

公式/图示：

forall (int i from 0 to N) {   // 声明：迭代互相独立
    y[i] = sinx(x[i]);          // 每个迭代对不同的数据做相同操作
}

5. SIMD Execution（单指令多数据执行）与 DLP

定义：Idea #2（幻灯片原话）：把管理一条指令流的成本（取指/译码）摊薄到多个 ALU 上——同一条指令广播（broadcast）给所有 ALU，所有 ALU 同时对不同数据执行该操作。这利用的是 data-level parallelism（DLP，数据级并行）：同一序列的指令作用在大量不同数据上。现代 CPU 实例：Intel AVX2（256 位，8×32 位 float）、AVX512（512 位，16×32 位）、ARM Neon（128 位，4×32 位）。
现实类比：老师对全班喊”翻到第 50 页”——一条指令同时指挥 40 名学生（40 个”数据”）。比挨个单独通知省 40 倍的”控制成本”。

公式/图示：

      一条 SIMD 指令：mul v1, v0, v0   （8-wide，256-bit）
      ┌───────────────────────────────────┐
 Fetch/Decode ──► ALU0 ALU1 ... ALU7      │ 8 个 ALU 同时执行"乘"
      └───────────────────────────────────┘
 标量版：mul r1, r0, r0 执行 8 次（8 条指令）
 向量版：mul v1, v0, v0 执行 1 次（1 条指令，同时算 8 个元素）

6. Explicit SIMD vs Implicit SIMD（显式 / 隐式 SIMD）

定义：
- Explicit SIMD（显式 SIMD）：向量化发生在编译期——编译器把标量循环编译成向量指令（vloadps、vmulps、vstoreps 等），可以检查二进制里看到 SIMD 指令。来源有三种：程序员用 intrinsics 显式请求；用并行语言语义（如 forall/foreach）传达；或编译器对循环做依赖分析后自动向量化（auto-vectorizing）。
- Implicit SIMD（隐式 SIMD）：编译器生成的是标量指令的二进制，但硬件总是同时运行 N 份程序实例，由硬件（而非编译器）负责把多个实例的相同指令放到 SIMD ALU 上同时执行。现代 GPU 采用这种模式，SIMD 宽度通常为 8–32。
现实类比：显式 SIMD = 你（程序员）明确吩咐”一次算 8 个”；隐式 SIMD = 你只管写”算 1 个”，老板（硬件）看到 8 个员工都在做同一件事，就把他们合并成一组一起做。
公式/图示：无公式；理解”谁负责发现并行”是关键差异——显式：编译器；隐式：硬件运行时。

7. Coherent Execution 与 Divergent Execution（一致执行与分歧执行）

定义：
- Instruction stream coherence（coherent execution）：程序的同一段指令序列适用于大量数据元素的性质。它是 SIMD 资源被高效利用的必要条件（但不是多核并行的必要条件——每个核可以独立取指，跑不同指令流）。
- Divergent execution（分歧执行）：缺乏指令流一致性。在 SIMD 上表现为：同一个 if/else 分支里，部分 ALU 走真分支、部分走假分支。硬件会顺序执行两个分支、用 mask 掩蔽（丢弃）不对应 ALU 的输出——不是所有 ALU 都在做有用功，最坏情况只有 1/8（8-wide）甚至 1/32（GPU）的峰值性能。
现实类比：全班一起念课文（coherent）；突然有人读到”如果 t>0 读 A 句否则读 B 句”，老师只好先带大家念 A 句、再念 B 句，念 A 句时不需要 B 句的学生只能干等（mask 掉）。

公式/图示：

时间(时钟)  ALU1 ALU2 ALU3 ALU4 ALU5 ALU6 ALU7 ALU8   （8-wide SIMD）
t>0.0?       T    T    T    F    F    F    F    F
1-2:  t=t*t 分支：只有 ALU1-3 的结果被保留（其余掩蔽）
3-4:  t=t*50 分支：只有 ALU4-8 的结果被保留（其余掩蔽）
5:    恢复无条件代码：8 个 ALU 全部满速
分支区间有效利用率 = max(3,5)/8 → 最坏 1/8

8. 复习：Cache、Cache Line、Miss 类型与 Locality

定义：cache 是芯片上保存内存子集副本的存储；按 cache line 粒度工作（如 4 字节/行），LRU 替换。课堂示例（8 字节总容量、2 行 4 字节）展示了：
- Cold miss（冷缺失）：某行第一次被访问，必须从 DRAM 装入；
- Hit（命中）：目标地址已在 cache 中；
- Capacity miss（容量缺失）：工作集超出 cache 容量，旧行被逐出，再次访问时重新装入——即”第二遍读 0x0 为什么不是 hit”的答案：访问序列 0x0→0xF 一遍后，2 行的 cache 只装得下最后 2 行（0x8、0xC），0x0 早已被逐出。
- 空间局部性：装一行顺带预载相邻地址；时间局部性：重复访问同一地址。
现实类比：桌面（cache 行）上只能摊开 2 张地图；翻完 4 张地图再看第 1 张，必须回抽屉（DRAM）重拿。

公式/图示：

访问序列: 0x0 0x1 0x2 0x3 \| 0x4 0x5 0x6 0x7 \| 0x8 ... 0xF \| 0x0 ...
cache(2行): [0x0] 命中*4 → [0x0][0x4] → 逐出0x0装[0x8] → 逐出0x4装[0xC]
→ 第二遍读 0x0：capacity miss（0x0 早被 0x8 逐出）
*若 cache 有 4 行：整个 16 字节数组全部驻留，第二遍全部命中

9. 复习：Stall（停顿）、Prefetching（预取）与不可预测访问

定义：指令依赖未完成的访存 → 处理器 stall。缓解手段：
- Data prefetching（数据预取）：现代 CPU 有硬件逻辑动态分析程序访存模式并预测未来地址，提前把数据装入 cache，让后续 load 变成 cache hit。代价：预测错了会浪费带宽、污染 cache，反而降低性能。
- 但若数据”最近没被读过、且下一个地址不可预测”（如 int x = some_function(); int y = A[x]; 的随机访存），预取无能为力——这是下一节多线程登场的动机。
现实类比：好餐厅会提前把常点菜备好（预取命中）；但客人随机点冷门菜（不可预测），备了也白备（带宽浪费）。

公式/图示：

无预取:  ld r0,mem[r2]  (miss → 等 ~248 周期) → add 停顿
有预取:  [提前装入 cache] → ld 变成 hit → add 立刻执行
不可预测: int y = A[x];  ← 不知道 x 就不知道地址，预取器无能为力

10. Hardware Multi-Threading（硬件多线程）

定义：Idea #3（幻灯片原话）：在同一个核上交错执行多个线程以隐藏停顿——”当前线程无法推进？那就去执行另一个线程的指令”。两种实现：
- Interleaved multi-threading（交错多线程，aka temporal）：每个时钟，核从多个线程中选一个，取其一条指令在 ALU 上执行；
- Simultaneous multi-threading（SMT，同时多线程）：每个时钟，核从多个线程同时选指令放到不同 ALU 上执行——Intel Hyper-threading（超线程，每核 2 线程） 就是 SMT。
现实类比：等洗衣机转（访存延迟）时去叠衣服（另一线程的算术）——机器（核心）不空转。

公式/图示：

单线程核心:   [线程1: 算术 算术 算术 \|←——等待 load 12 周期——→\| 算术 ...]  20% 利用率
多线程核心:   [线程1: 算术 算术 算术 \|     等待中...      \| 算术 ...]
              [线程2:               \| 算术 算术 算术      \|         ]
              ↑ 线程1 停顿期间，核心执行线程2 的算术 → 利用率提高

11. Latency Hiding 与利用率计算（核心定量结论）

定义：多线程不改变访存延迟本身，只是让延迟不再导致处理器利用率下降（”the latency of the memory operation is not changed by multi-threading, it just no longer causes reduced processor utilization”）。课堂定量练习：线程每轮做 3 条算术 + 1 条 12 周期延迟的 load：
- 1 个线程：每 15 周期忙 3 周期 → 利用率 3/15 = 20%；
- 2 个线程：6/15 = 40%；
- 5 个线程：15/15 = 100%（再多线程无额外收益）；
- 若改为 6 条算术 + 12 周期 load（算术/访存比更高）：只需 3 个线程即可 100%。
现实类比：流水线上每个人做 3 秒的活然后等 12 秒的料——需要 5 个人接力才能让工位永不空转；每人干的活越多（6 秒），需要的人越少（3 人）。

公式/图示：

每轮: 3 条算术(3 时钟) + load(12 时钟等待) → 周期 = 15 时钟
所需线程数 × 每线程忙时钟数 ≥ 周期长度
3 算术: 5 × 3 = 15 → 5 线程达 100%
6 算术: 3 × 6 = 18 → 3 线程达 100%   （算术越多，隐藏延迟所需线程越少）

12. Execution Context 是有限资源（No Free Lunch）

定义：硬件多线程需要为每个线程保存一份执行上下文（寄存器 + PC），这些上下文存在片上的 Context storage（或 L1 cache 区域）中，是有限资源。许多小上下文（如 16 个硬件线程，每线程小工作集）= 高延迟隐藏能力；少数大上下文（如 4 个线程，每线程大工作集）= 低延迟隐藏能力。设计权衡：吞吐 vs 每线程性能。
现实类比：办公室工位总数固定——工位多（16 个小隔间）能容纳更多员工同时办公（隐藏更多等待），但每个人空间小；工位少（4 个大办公室）每个人舒服但能同时办公的人少。

公式/图示：

16 个硬件线程: [ctx1][ctx2]...[ctx16]  每线程小工作集 → 高 latency hiding
4 个硬件线程:  [ctx1][ctx2][ctx3][ctx4] 每线程大工作集 → 低 latency hiding

13. 三种并行形式总结（Superscalar / SIMD / Multi-core）

定义（幻灯片总结页原文要点）：
- Superscalar：单指令流内的 ILP——同一指令流的不同指令并行（核内）；并行由硬件在执行期自动发现。
- SIMD：多个 ALU 由同一条指令控制（核内）；对数据并行负载高效（摊薄控制成本）；向量化由编译器（显式）或硬件运行时（隐式）完成。
- Multi-core：多个核；每个核同时执行完全不同的指令流（TLP）；软件通过线程 API 创建线程来向硬件暴露并行。
现实类比：三个层面的”并行”：一条流水线上多道工序同时做（ILP）；一个广播同时指挥多个人（SIMD）；多条流水线同时开工（multi-core）。

公式/图示（幻灯片三个处理器对比）：

单核超标量:    每时钟从 1 条指令流取 ≤2 条独立指令
双核:          每时钟每核从各自指令流取 1 条
SIMD 四核:     每时钟每核执行 1 条 8-wide SIMD 指令

14. GPU 的 SIMT（Single Instruction, Multiple Thread）

定义：现代 GPU 执行的硬件线程指令流只有标量指令；GPU 核检测到多个硬件线程正在执行同一条指令时，用 SIMD ALU 同时执行最多 SIMD-width 个线程；执行不同指令的线程（divergent）被 mask 掉。即”硬件把标量线程流动态合并成 SIMD”。
现实类比：阅兵方阵——教官（取指）喊”齐步走”，本来每人各自走着（独立线程），一旦动作一致就自动合并成整齐方阵（SIMD）；有人走错（divergent）就先被”晾着”（mask）。
公式/图示：见第 7 条 mask 图；GPU 上 SIMD 宽度 8–32，写不好的代码可能只有 1/32 峰值性能。

二、代码示例与详细解说（本讲重点）

示例 1：std::thread 把 sinx 拆到两个核（TLP / multi-core）

代码（cpp）：

// multi_core_sinx.cpp —— 演示 TLP / multi-core（幻灯片原版思路，补齐可编译外壳）
// 编译运行：g++ -O2 -std=c++11 multi_core_sinx.cpp -o multi_core_sinx -pthread
#include <iostream>
#include <cmath>
#include <thread>
#include <vector>

// 课堂贯穿示例：用泰勒展开计算 sin(x)，逐元素处理数组
// sin(x) = x - x^3/3! + x^5/5! - x^7/7! + ...
void sinx(int N, int terms, float* x, float* result) {
    for (int i = 0; i < N; i++) {
        float value = x[i];
        float numer = x[i] * x[i] * x[i];   // 分子初值 x^3
        int denom = 6;                      // 分母初值 3!
        int sign = -1;
        for (int j = 1; j <= terms; j++) {
            value += sign * numer / denom;  // 累加第 j 项
            numer *= x[i] * x[i];           // 下一项分子：x^(2j+3)
            denom *= (2*j+2) * (2*j+3);     // 下一项分母：(2j+3)!
            sign *= -1;
        }
        result[i] = value;
    }
}

// 幻灯片中的线程参数打包结构体
typedef struct {
    int N;
    int terms;
    float* x;
    float* y;
} my_args;

void my_thread_func(my_args* args) {
    sinx(args->N, args->terms, args->x, args->y);   // 新线程做前半段
}

void parallel_sinx(int N, int terms, float* x, float* y) {
    std::thread my_thread;
    my_args args;
    args.N = N / 2;                                 // 拆一半工作给线程
    args.terms = terms;
    args.x = x;
    args.y = y;
    my_thread = std::thread(my_thread_func, &args);  // 启动工作线程
    sinx(N - args.N, terms, x + args.N, y + args.N); // 主线程做后半段
    my_thread.join();                                // 同步：等待线程完成
}

int main() {
    const int N = 1 << 20;
    const int terms = 5;
    std::vector<float> x(N), y(N);
    for (int i = 0; i < N; ++i) x[i] = (i % 100) / 100.0f;  // 小角度输入
    parallel_sinx(N, terms, x.data(), y.data());
    int bad = 0;
    for (int i = 0; i < N; ++i)
        if (std::fabs(y[i] - std::sin(x[i])) > 1e-3f) ++bad;
    std::cout << "checked " << N << " elements, mismatches = " << bad << "\n";
    return bad == 0 ? 0 : 1;
}

【代码做了什么？】

sinx 对数组每个元素计算泰勒展开的 sin 近似值：内部 j 循环逐项累加（分子 numer 每次乘 x²，分母 denom 按阶乘递推，符号交替）。
parallel_sinx 把 N 个元素对半拆开：新线程处理 x[0..N/2)，主线程处理 x[N/2..N)，最后 join() 等待。
main 分配数组、调用并行版本并抽查结果与标准库 std::sin 的一致性（验证并行化没有破坏正确性）。

【并行机制解说】

这段代码演示的是 multi-core 并行 / TLP：两个线程 = 两条完全独立的指令流，由 OS 调度到两个物理核上同时执行（若机器有 2 核）。对应概念：多核时代把晶体管换成了更多核，而软件必须显式创建线程（这里用 std::thread）硬件才能看到并行——幻灯片强调”这个 C 程序若不并行化，编译成单线程指令流只会跑在一个核上，甚至因单核变简单而慢 25%”。
工作分配：args.N = N/2 是”分成两块各干一半”的简单均分（blocked assignment）；两个线程通过 x/y 指针共享整个数组（共享内存模型），各自只读写自己的区间，无冲突，因此不需要任何锁——这是数据并行任务”安全分解”的范例。
同步点：join() 保证主线程在读取/校验结果前，工作线程一定完成——这就是”管理同步使其不成为瓶颈”的最简形式。
若要进一步扩展：拆成 4 份就能用满四核（Assignment 1 的机器）；再配合下一示例的 SIMD，才能逼近 32–40x 的峰值。

示例 2：AVX intrinsics 手写 SIMD 向量化 sinx（DLP / explicit SIMD）

代码（cpp）：

// simd_sinx.cpp —— 显式 SIMD：用 AVX intrinsics 一次处理 8 个元素
// 编译运行（需要支持 AVX 的 x86 CPU）：
//   g++ -O2 -mavx -std=c++11 simd_sinx.cpp -o simd_sinx
#include <immintrin.h>
#include <iostream>
#include <cmath>
#include <cstdlib>

void sinx_avx(int N, int terms, float* x, float* y) {
    float three_fact = 6.0f;                 // 3!
    for (int i = 0; i < N; i += 8) {         // 每轮处理 8 个元素
        __m256 origx = _mm256_load_ps(&x[i]);         // 向量 load：x[i..i+7]
        __m256 value = origx;
        __m256 numer = _mm256_mul_ps(origx, _mm256_mul_ps(origx, origx)); // x^3
        __m256 denom = _mm256_broadcast_ss(&three_fact);                  // 广播 6.0
        int sign = -1;
        for (int j = 1; j <= terms; j++) {
            // value += sign * numer / denom
            __m256 tmp = _mm256_div_ps(
                _mm256_mul_ps(_mm256_set1_ps((float)sign), numer), denom);
            value = _mm256_add_ps(value, tmp);
            numer = _mm256_mul_ps(numer, _mm256_mul_ps(origx, origx));
            float f = (float)((2*j+2) * (2*j+3));     // 下一项分母因子
            denom = _mm256_mul_ps(denom, _mm256_broadcast_ss(&f));
            sign *= -1;
        }
        _mm256_store_ps(&y[i], value);                // 向量 store：y[i..i+7]
    }
}

int main() {
    const int N = 1 << 20;
    const int terms = 5;
    // _mm256_load_ps / store_ps 要求 32 字节对齐
    float* x = (float*)aligned_alloc(32, N * sizeof(float));
    float* y = (float*)aligned_alloc(32, N * sizeof(float));
    for (int i = 0; i < N; ++i) x[i] = (i % 100) / 100.0f;
    sinx_avx(N, terms, x, y);
    int bad = 0;
    for (int i = 0; i < N; ++i)
        if (std::fabs(y[i] - std::sin(x[i])) > 1e-3f) ++bad;
    std::cout << "mismatches = " << bad << "\n";
    free(x); free(y);
    return bad == 0 ? 0 : 1;
}

; 编译后可以看到显式 SIMD 指令（幻灯片"explicit SIMD"：二进制里能找到向量指令）
vloadps  xmm0, addr[r1]    ; 一次装入 8 个 float
vmulps   xmm1, xmm0, xmm0  ; 8 个元素同时平方
vmulps   xmm1, xmm1, xmm0
...
vstoreps addr[xmm2], xmm0  ; 一次写回 8 个 float

【代码做了什么？】

与标量版 sinx 完全相同的算法，只是所有运算换成 256-bit 向量 intrinsics：_mm256_load_ps 一次装入 8 个 float，_mm256_mul_ps/_mm256_add_ps/_mm256_div_ps 对 8 个元素同时运算，_mm256_broadcast_ss 把标量（6.0、阶乘因子、sign）复制到 8 个 lane，_mm256_store_ps 一次写回 8 个结果。
外层循环步长从 1 变成 8：i += 8，每个迭代处理一个 8 元素向量。sign 仍是标量 int（每轮循环翻转）。
编译后的指令流里能看到 vloadps/vmulps/vstoreps 等向量指令——这就是幻灯片说的 explicit SIMD：并行化发生在编译期，程序员用 intrinsics 显式请求。

【并行机制解说】

对应概念：SIMD / DLP。标量程序一条指令处理 1 个元素；向量程序一条指令处理 8 个元素——取指/译码成本被 8 个 ALU 摊薄（Idea #2）。同样是这个 sinx，从”单核每时钟 1 个元素”变成”单核每时钟 8 个元素”，性能最多提升 8 倍（单核内）。
与示例 1 的组合关系：multi-core（多核）与 SIMD（核内）是两个正交的并行维度。16 个 SIMD 核 = 16 条指令流 × 每核 8 个 ALU = 128 个元素并行（幻灯片图示）。Assignment 1 的 32–40x = 4 核 × AVX 8-wide × 超线程等因素的乘积。
两个实现细节值得注意：(a) _mm256_load_ps 要求 32 字节对齐，main 里用 aligned_alloc(32, ...) 保证；(b) 幻灯片原代码中的 _mm256_set1ps(sign) 是笔误，正确 intrinsic 是 _mm256_set1_ps((float)sign)——这类”1 与 _ 的顺序”错误在 AVX 编程里很常见。

示例 3：SIMD 下的条件执行与分歧（divergence / masking）

代码（伪代码，对应幻灯片 forall 语言示例）：

// 伪代码：如果这个循环被编译成 8-wide SIMD，会发生什么？
forall (int i from 0 to N) {
    float t = x[i];
    if (t > 0.0) {
        t = t * t;        // 分支 A：只有 t>0 的元素需要
    } else {
        t = t * 50.0;     // 分支 B：只有 t<=0 的元素需要
    }
    t = t + 100.0;        // 无条件代码
    t = t / 10.0;
    y[i] = t;
}

【代码做了什么？】

每个数组元素：若为正则平方，否则乘 50，然后统一加 100 除以 10。逻辑本身平凡，但注意同一向量里 8 个元素可能同时存在正数和负数——它们需要执行不同的指令序列。

【并行机制解说】

对应概念：coherent vs divergent execution。SIMD 硬件没有”每个 lane 各自跳转”的能力——一条指令要么广播给所有 ALU，要么不广播。所以硬件两条分支都执行，用 mask 决定每个 ALU 的输出是否写回：

时钟 1-2: 执行 t = t*t 分支（3 个 ALU 是 T，保留结果；5 个 ALU 是 F，掩蔽丢弃）
时钟 3-4: 执行 t = t*50 分支（5 个 ALU 是 F，保留结果；3 个 ALU 是 T，掩蔽丢弃）
时钟 5:   执行 t+100、t/10（无条件，8 个 ALU 全速）
分支期间只有 3/8 或 5/8 的 ALU 在做有用功 → 最坏情况 1/8 峰值性能

幻灯片”breakout question”：能否只用一条 if 就构造出 8-wide SIMD 的最坏情况？答案：让分支条件对 8 个 lane 恰好 1 真 7 假（例如 if (t == 0.0)，且数据里恰好 1 个零）——两条分支都要执行，有效 ALU 数 = max(1,7) = 7？不对，是”每分支里做有用功的 lane 数”：真分支 1 个、假分支 7 个，总执行时钟翻倍而有效功只有 8 个 lane 的一次量 → 效率 50%；若更极端——分支体内有两条分支（嵌套 if），或分支条件是 data-dependent 导致每个 lane 都不同（如 if (t == i)），则每条路径只有 1/8 的 lane 有用，最坏 1/8 甚至更低。
这就是为什么幻灯片强调：coherent execution 是 SIMD 高效的必要条件；而多核并行不需要 coherent——每个核独立取指，可以各跑各的分支。GPU（implicit SIMD，宽度 8–32）上 divergence 是头号性能杀手，写不好的代码只有 1/32 峰值。

示例 4：多线程隐藏访存延迟（hardware multi-threading 的动机）

代码（cpp）：

// latency_hiding.cpp —— 依赖型访存 + 多线程：演示"换线程干活"隐藏停顿
// 编译运行：g++ -O2 -std=c++11 latency_hiding.cpp -o latency_hiding -pthread
#include <iostream>
#include <vector>
#include <thread>
#include <chrono>

// 每个线程沿自己的"随机跳转表"做依赖型访存：
// 下一次 load 的地址 = 上一次 load 的结果（int y = A[x] 的放大版）。
// 单线程下每个元素都要等满 DRAM 延迟（~数百周期），几乎全程 stall。
void chase(const std::vector<size_t>& next, size_t start, size_t iters) {
    size_t idx = start;
    for (size_t i = 0; i < iters; ++i) idx = next[idx];  // 依赖链上的 load
    volatile size_t sink = idx;   // 防止编译器把整个循环优化掉
    (void)sink;
}

double run(int nthreads, const std::vector<size_t>& next, size_t iters) {
    auto t0 = std::chrono::steady_clock::now();
    std::vector<std::thread> ts;
    for (int t = 0; t < nthreads; ++t)
        ts.emplace_back(chase, std::cref(next), (size_t)t, iters);
    for (auto& th : ts) th.join();
    auto t1 = std::chrono::steady_clock::now();
    return std::chrono::duration<double>(t1 - t0).count();
}

int main() {
    const size_t SIZE = 1 << 24;      // 16M 元素，远超 L3，必然落到 DRAM
    std::vector<size_t> next(SIZE);
    for (size_t i = 0; i < SIZE; ++i)
        next[i] = (i * 2654435761u) % SIZE;   // 伪随机跳转：地址不可预测、无法预取
    const size_t iters = 1 << 22;
    for (int P : {1, 2, 4, 8, 16}) {
        double sec = run(P, next, iters);
        std::cout << "threads = " << P << "  time = " << sec << " s\n";
    }
    return 0;
}

【代码做了什么？】

每个线程从自己的起点出发，沿 next 表做 iters 次依赖型访存：idx = next[idx]——第 k+1 次 load 的地址是第 k 次 load 的结果，地址不可预测（伪随机跳转），因此硬件预取器无能为力（对应幻灯片 int y = A[x] 的场景）。
主程序分别用 1、2、4、8、16 个线程跑同样的总量，打印耗时。典型观察：1 线程极慢（几乎全程 stall），线程数增加后吞吐显著提升，直到内存带宽饱和后不再增长。

【并行机制解说】

对应概念：hardware multi-threading / latency hiding。单线程时，每步 load 都要等满 DRAM 延迟（数百周期），核心利用率很低——幻灯片算过：3 条算术 + 12 周期 load，1 线程利用率只有 20%。多个线程同时跑时，一个线程的 stall 期间，核心去执行另一个线程的算术（”If you can’t make progress on the current thread… work on another one”）。
这是吞吐导向（throughput-oriented）计算的核心权衡：为了让整体吞吐最大化，单线程的完成时间可能变长（它被其他线程”插队”）——幻灯片 Takeaway 1：多线程不改变访存延迟，只是让它不再造成利用率损失。
幻灯片定量结论回顾（配图即可理解）：3 算术 + 12 周期 load → 5 线程 100% 利用率；6 算术 + 12 周期 load → 3 线程即 100%（算术/访存比越高，需要的线程越少——Takeaway 2）。
实现形式：interleaved multi-threading（每时钟选一个线程执行）或 SMT / Intel Hyper-threading（每时钟从多个线程同时选指令）。现代 CPU 如 Intel Skylake/Kaby Lake 核：2-way 多线程、每时钟最多 4 条独立标量 + 3 条 8-wide 向量指令。

三、关键要点

现代高吞吐处理器 = 三个并行维度的组合：multi-core（TLP，多核跑不同指令流）、SIMD（DLP，一条指令驱动多个 ALU）、hardware multi-threading（延迟隐藏，用别的线程填满停顿）。它们可以叠加：多核 × 每核 SIMD × 每核多线程（如 i7-7700K：4 核 × 8-wide SIMD × 3 个向量 ALU × 4.2 GHz ≈ 400 GFLOPs；V100：80 SM × 128 SIMD ALU @1.6 GHz ≈ 16 TFLOPs）。
软件不表达并行，多核毫无用处：普通 C 程序编译成单线程指令流只能跑在一个核上；要获得多核收益必须创建线程（std::thread）；要获得 SIMD 收益必须向量化（intrinsics / 并行语言语义 / 自动向量化）。forall 这类数据并行表达让编译器可以同时生成多核代码与向量指令。
SIMD 高效的前提是 coherent execution：同一指令序列作用于大量数据；分支（divergent execution）会让部分 ALU 空转（masking），最坏 1/8（CPU）甚至 1/32（GPU）峰值。多核并行不需要 coherent——每个核独立取指。
cache 解决”已访问过的数据”，多线程解决”不可预测的数据”：cache/预取处理局部性与可预测访问模式；当数据既不在 cache 又不可预测时（A[x]），唯一办法是硬件多线程——用其他线程填满访存停顿。
隐藏延迟需要”足够的并行工作”：多线程隐藏延迟的效果取决于算术/访存比——算术越多需要的线程越少（6 算术 + 12 周期 load 只需 3 线程）；执行上下文（寄存器 + PC）是有限片上级资源，多而小 = 高隐藏能力，少而大 = 低隐藏能力。

四、常见陷阱与注意事项

把”每时钟一条指令”误解为”一条指令只要 1 周期完成”：处理器流水线里”每时钟一条指令”指的是指令吞吐（throughput），不是延迟（latency）——一条指令从取指到写回可能 4 周期甚至 ~20 周期（流水线深度）。这个区分在 Lecture 3 讲流水线时会再次强调。
以为多核 = 自动加速：不写线程、不向量化，程序只会用到一个核；更糟的是多核时代单核可能比过去的”豪华单核”更简单（如慢 25%），不做任何事反而变慢。并行必须由软件显式表达。
忽视对齐要求：_mm256_load_ps/_mm256_store_ps 要求 32 字节对齐；普通 new float[] 不保证。用 aligned_alloc(32, ...) 或让编译器分配对齐数组，否则运行期崩溃（segfault）。
把分支写进数据并行循环而不考虑 divergence：if/else 在 SIMD 上两条分支都会执行、靠 mask 丢弃，看似”正确”但性能可能只有 1/8。尽量让分支条件对同一向量内所有元素一致（coherent），或改用无分支写法。
忘记 join() / 在 join 前使用线程结果：示例 1 中若去掉 my_thread.join()，主线程可能在 worker 未完成时就校验结果，产生数据竞争。同步点（join）是多线程正确性的底线。
误以为多线程会”加快”单条指令流：hardware multi-threading 是吞吐优化——可能延长单线程完成时间（被插队），换来的是多线程总吞吐提升。衡量指标要看系统吞吐，不是单线程延迟。

五、思考题（带答案）

Q1. 同一个 sinx 程序，为什么”多核化”和”向量化（SIMD）”是两个不同的并行维度？用 16 核 × 8-wide SIMD 的机器说明最大并行度来自哪里。

答案：多核并行（TLP）是”多条指令流同时跑在多个核上”，每个核处理不同的数组片段；SIMD（DLP）是”单条指令流内，一条指令驱动 8 个 ALU 处理 8 个相邻元素”。两者正交：16 核每核 8-wide SIMD = 16 条指令流 × 8 个 ALU = 128 个元素同时处理（幻灯片原图）。最大并行度 = 核数 × SIMD 宽度（再乘多线程数），但前提是程序同时表达出 TLP（线程/forall）和 DLP（向量化/forall）。

Q2. 课堂练习：线程每轮做 3 条算术 + 一条 12 周期延迟的 load。为什么 5 个线程才能 100% 利用核心？如果算术改成 6 条呢？

答案：每轮周期 = 3（算术）+ 12（等待 load）= 15 周期，每个线程每轮只有 3 周期在干活。N 个线程的忙时钟 = 3N；要填满 15 周期需要 3N ≥ 15 → N = 5。算术改为 6 条后周期 = 18、忙 6，需要 6N ≥ 18 → N = 3。结论（Takeaway 2）：程序每访存一次做的算术越多，隐藏延迟所需的线程越少。

Q3. 幻灯片”breakout question”：只用一条 if 语句，如何构造 8-wide SIMD 处理器的最坏情况性能？

答案：用不带 else 的单条 if，并让条件只对 8 个 lane 中的 1 个成立。例如 if (x[i] < 0.0f) { y[i] = x[i] * x[i]; }，输入中恰好 1 个负元素——该分支指令按 mask 执行时只有 1/8 的 lane 在做有用功（其余 7 个 lane 的输出被掩蔽丢弃），效率跌到 1/8 峰值（幻灯片图注”Worst case: 1/8 peak performance”）。若分支带 else，则两个分支体都要执行、每分支平均约一半 lane 有用，效率约 50%（不如单分支极端）。这正说明 divergent execution 对 SIMD 效率的破坏力。

注意：本讲与 Assignment 1 直接相关——作业在四核 Intel CPU（带 AVX SIMD 指令 + hyper-threading）上分析并行程序性能：基线是 -O3 编译的单线程 C 程序，目标程序用上全部并行资源，幻灯片预告约 32–40x 加速。其中 ISPC（数据并行表达 forall/foreach 的真实编译器实现）与”把并行工作映射到多核 + SIMD”正是 Lecture 3 的主题。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li