Lecture 24: 线程级并行 (Thread-Level Parallelism)

目录 · ← l23 · l25 →

Lecture 24: 线程级并行 (Thread-Level Parallelism)

讲义对应：CMU 15-213 Lecture 24 — Thread-Level Parallelism（素材：F25-24-parallelism.txt） 教材对应：CS:APP3e 第 12 章 12.6 Parallelism（含 12.6 的并行求和与并行快排案例） 关联 Lab：L8 SFS Lab；本讲同时是 CMU 15-418 / CS149 并行体系结构课的衔接点

24.1 概述

前面几讲我们用线程应对 I/O 延迟（一个客户端一个线程，避免互相阻塞），这一讲把线程用在完全不同的目的上： 把一个”算得慢”的大任务切成多个可以同时执行的子任务，用多核硬件真正缩短墙钟时间（wall-clock time）。 本讲的核心问题有三个：多核硬件长什么样（多核、超线程、缓存一致性、内存一致性模型）？怎么把程序切开并度量收益（加速比、效率、Amdahl 定律）？ 以及一个最容易被忽视的问题——并行不等于正确，也不等于更快：共享内存会带来真共享与伪共享的代价，同步会成为新的串行瓶颈。

在知识地图上，本讲收束了第 21–23 讲的并发与同步：并发关注”多个逻辑流如何正确交错”，并行关注”如何让它们同时跑并且更快”； 同时它复用第 9–10 讲的缓存与局部性知识，并通向 15-418/CS149 的并行体系结构与 GPU 编程。

24.2 核心概念与底层机制图解

24.2.1 共享内存多核处理器（Shared-Memory Multicore）

• 定义与目的：多核（multicore）处理器把多个完整的处理器核（core）集成在同一块芯片上， 它们通过互连网络（interconnect）访问统一的物理地址空间，因此对内存有一致的视图（coherent view of memory）。
• 直观解释：把单核想象成一个独居的学者，所有资料都在他手边的书架（L1/L2）和图书馆（主存）里。 多核就是在一个办公室里放了 64 位学者：他们共用同一个图书馆，但每人有自己的书架。 谁会最快？——各自读自己的资料，偶尔才去图书馆。这就是并行程序设计的全部直觉来源。
• 底层机制图解：

+--------------------------------------------------------------------------+
|                         Multicore Chip (Socket 0)                        |
|                                                                          |
|   +---------------------------+      +---------------------------+       |
|   |          Core 0           |      |         Core n-1          |       |
|   |  +---------+ +---------+  |      |  +---------+ +---------+  |       |
|   |  | Regs A  | | Regs B  |  |      |  | Regs A  | | Regs B  |  |       |
|   |  +----+----+ +----+----+  |      |  +----+----+ +----+----+  |       |
|   |    L1i 32K     L1d 32K    |      |    L1i 32K     L1d 32K    |       |
|   |  +---------------------+  |      |  +---------------------+  |       |
|   |  |  L2 unified 512 KB  |  |      |  |  L2 unified 512 KB  |  |       |
|   |  +----------+----------+  |      |  +----------+----------+  |       |
|   +-------------+-------------+      +-------------+-------------+       |
|                 |                                  |                     |
|        +--------+----------------------------------+-------+             |
|        |        L3 unified cache (shared)                  |             |
|        +---------------------------+-----------------------+             |
+------------------------------------+-------------------------------------+
                                     |
                          +----------+-----------+
                          |      Main Memory     |
                          |  (coherent view for  |
                          |   all cores/nodes)   |
                          +----------------------+

• 与机器码/硬件的对应：对程序员而言，多核不需要任何新指令——同一份 addq/movq 代码在不同核上跑。 硬件负责的是缓存一致性（coherence）：L1/L2 私有，L3 共享，主存是最终一致点。 代价是：任何被多个核读写的缓存行都必须在核之间搬运，这就是本讲后面所有性能故事的总根源。

24.2.2 超线程（Hyperthreading / Simultaneous Multithreading, SMT）

• 定义与目的：超线程在一个物理核上复制指令控制逻辑与寄存器组（典型 K=2），使单个核能同时处理 K 个指令流； 功能单元（functional units）与缓存是共享的。
• 直观解释：一个厨师（功能单元）同时看两份菜谱（寄存器组）。切菜时盯着第一份，等水烧开（访存延迟）时就去看第二份—— 厨师的手没变快，但闲着的时间被填满了。
• 底层机制图解：

           无 SMT (K = 1)                        超线程 / SMT (K = 2)

     +---------------------------+        +-----------------------------------------+
     |    Instruction Control    |        |        Instruction Control (×K)         |
     |  PC | Registers | OpQueue|        | PC_A Reg_A OpQ_A  |  PC_B Reg_B OpQ_B   |
     +-------------+-------------+        +------------------+----------------------+
                   |                                     |
     +-------------v-------------+        +--------------v--------------------------+
     |    Functional Units       |        |       Functional Units  (共享!)        |
     |  Int  Int  FP  Load/Store |        |   Int   Int   FP   Load/Store          |
     +---------------------------+        +-----------------------------------------+
     |      Data Cache (L1d)     |        |           Data Cache (L1d)  (共享)      |
     +---------------------------+        +-----------------------------------------+

• 与机器码/硬件的对应：SMT 是吞吐（throughput）优化，不是延迟优化——单线程的 CPE 不会因为开了超线程而下降。 讲义中 Shark 机器是 Intel Xeon E5520 @ 2.27 GHz、8 核、每核 2 路超线程，因此”理论上一次可执行 16 个线程，理论加速比 16×， 但讲义明确写道 never achieved in our benchmarks“——超线程带来的额外吞吐取决于线程的访存/分支行为，通常远低于 2×。

24.2.3 共享内存 vs 消息传递（Shared Memory vs Message Passing）

• 定义与目的：这是并行程序的两种基本编程模型。共享内存：所有线程访问同一地址空间，靠读写共享变量通信，靠同步保证正确性； 消息传递：每个执行体有私有地址空间，只能通过显式 send/recv（如 MPI）交换数据。
• 直观解释：共享内存像一块共用的白板，谁都能直接擦写，快但容易打架；消息传递像发微信， 各自笔记互不可见，必须复制一份发过去，慢但边界清晰、天然避免竞态。
• 底层机制图解：

     共享内存 (Shared Memory)               消息传递 (Message Passing)
  +---------+          +---------+      +---------+          +---------+
  | Thread0 |          | Thread1 |      | Proc 0  |          | Proc 1  |
  | 私有栈  |          | 私有栈  |      | 私有内存|          | 私有内存|
  +----+----+          +----+----+      +----+----+          +----+----+
       \                    /                |  send(msg)         ^
        \                  /                 +--------------------+
   +-----v------------------v-----+          |                    |
   |   Shared Heap / Globals      |          |   recv(msg)        |
   |  (需要 mutex/sem 保护)       |          +--------------------+
   +------------------------------+         互连网络（复制数据，无共享写）

• 与机器码/硬件的对应：共享内存模型对应多核 + 缓存一致性协议（本机：x86-64 多核，pthread）； 消息传递模型对应集群/多节点 + 网络（MPI），也是 GPU 上”主机内存与设备内存必须显式 cudaMemcpy“的根源。 CS:APP 只讲共享内存（pthread），消息传递由 15-418/CS149 展开。

24.2.4 并行性的三个层次：TLP / ILP / DLP

• 定义：线程级并行（Thread-Level Parallelism, TLP）——多个线程/进程在多个核上同时执行； 指令级并行（Instruction-Level Parallelism, ILP）——单个指令流内部，处理器用超标量（superscalar）发射与乱序执行（out-of-order execution） 让多条无依赖指令同时完成；数据级并行（Data-Level Parallelism, DLP）——同一条操作作用于一批数据， 硬件形式是 SIMD（SSE/AVX 向量指令）与 GPU。
• 直观解释：TLP 是”多请几个工人”，ILP 是”一个工人左右手同时干活”，DLP 是”一台压面机一次压一整排面皮”。
• 底层机制图解（乱序执行结构，讲义原图）：

   +-----------------------+
   |   Instruction Control |  PC ──► 取指 ──► 译码 ──► 操作队列 (Op. Queue)
   |  (动态调度/寄存器重命名)|        把程序动态转换成"操作流"
   +-----------+-----------+            并把无依赖的操作并行映射到功能单元
               |
   +-----------v----------------------------------------------------+
   |  Functional Units                                              |
   |  +----------+ +----------+ +----------+ +------------------+   |
   |  | Int Arith| | Int Arith| | FP Arith | |  Load / Store    |   |
   |  +----------+ +----------+ +----------+ +------------------+   |
   +----------------------------------------------------------------+
        ▲ 指令缓存 (L1i)                │ 数据缓存 (L1d)

• 与机器码/硬件的对应：ILP 由硬件自动挖掘，程序员只需避免长依赖链（例如把 sum 拆成多个累加器做循环展开， 详见 Lecture 15）；DLP 需要程序员或编译器把标量循环向量化；TLP 需要程序员显式创建线程。 三者的一个关键区别是：ILP 不需要改代码语义，TLP 会引入竞态，因此本讲的正确性问题只属于 TLP。

24.2.5 缓存一致性与内存一致性模型（Coherence & Consistency）

• 定义：缓存一致性（cache coherence）保证同一地址的读最终能看到最近的写（硬件协议，如 MESI 嗅探协议 snoopy protocol）； 内存一致性模型（memory consistency model）规定不同地址的读写在不同线程看来允许出现的顺序。
• 直观解释：一致性是”每个人都最终知道白板上写了什么“；一致性模型是”你写字和你看白板的先后顺序是否可以让别人看出来“。 前者保证不丢数据，后者决定”先写标志位还是先写数据”这种程序逻辑是否成立。
• 底层机制图解（讲义的非一致缓存与嗅探缓存对比）：

  没有协调的写回缓存 (Non-Coherent)              嗅探缓存 (Snoopy, 每行带状态)

  Main Memory: a:1  b:100                      Main Memory: a:1  b:100
  +------------------+  +------------------+   +------------------+  +------------------+
  |  Thread1 Cache   |  |  Thread2 Cache   |   |  Thread1 Cache   |  |  Thread2 Cache   |
  |   a: 2           |  |   b: 200         |   |   a:2  [M]       |  |   b:200 [M]      |
  |   (看不到 b 的更新)|  |   (看不到 a 的更新)|  |   b:200 [S]      |  |   a:2  [S]       |
  +------------------+  +------------------+   +------------------+  +------------------+
   T1 打印 1, T2 打印 100 (错)                  M = 可写副本, S = 可读共享, I = 无效
                                                看到对该行的请求就由缓存供给数据, 并置 S

• 与机器码/硬件的对应：即使有了一致性缓存，写缓冲（write buffer）与乱序执行仍会打乱同线程内对不同地址的可见顺序， 于是出现”非顺序一致”的执行。讲义给出的修法是：在 Wa 与 Rb 之间、Wb 与 Ra 之间插入 SFENCE（store fence）， 或使用正确编写的同步操作（pthread_mutex_lock/unlock 本身起栅栏作用）。 讲义给出的经典程序（两个线程分别写 X/Y 再读对方）在顺序一致性下不可能同时打印出 “Hello” 和 “World”； 这也是后续 15-418 里”内存模型”整章的主题。

24.2.6 伪共享（False Sharing）

• 定义：多个线程写同一个缓存行（cache line）内的不同变量。变量本身互不相干（不是真共享 true sharing）， 但一致性协议以缓存行为粒度，于是该行在核之间反复失效与搬运（cache line ping-pong）。
• 直观解释：两个人住在同一栋楼（同一缓存行）的不同房间。甲要改自己的窗帘，物业（一致性协议）却把整栋楼的钥匙都收回来再发给甲； 乙改灯也一样。两人什么都没共用，却被迫互相排队。
• 底层机制图解（本机实测缓存行为 64 字节）：

  无填充 (adjacent): psum[0..7] 全部落在同一个 64 B 缓存行里

    0x4043c0            Cache line: 64 B (8 个 unsigned long)
    +--------+--------+--------+--------+--------+--------+--------+--------+
    |psum[0] |psum[1] |psum[2] |psum[3] |psum[4] |psum[5] |psum[6] |psum[7] |
    | T0 写  | T1 写  | T2 写  | T3 写  | T4 写  | T5 写  | T6 写  | T7 写  |
    +--------+--------+--------+--------+--------+--------+--------+--------+
         ^                          ^
         |   该行的 M(Modified) 独占权在 8 个核之间来回弹跳
         +==== Core0 ==> Core1 ==> Core2 ==> ... ==> Core0 (ping-pong) ====+

  填充后 (padded, spacing = 8 个元素 = 64 B)：每个线程独占一行

    Thread 0 独占 64 B 行            Thread 1 独占 64 B 行
    +----------------------+         +----------------------+
    | psum[0]  | 7×8 B 填充 |         | psum[8]  | 7×8 B 填充 |
    +----------------------+         +----------------------+
    +----------------------+         +----------------------+
    | Thread 2 独占 64 B 行|   ...   | Thread 3 独占 64 B 行|
    +----------------------+         +----------------------+

• 与机器码/硬件的对应：讲义给出的判据非常直白——“Demonstrates cache block size = 64: 8-byte values, no benefit increasing spacing beyond 8”， 即元素步长超过 8 个 8 字节值后收益消失，反推出块大小就是 64 B。本机用 getconf LEVEL1_DCACHE_LINESIZE 与 /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 双重确认，答案同样是 64。

24.2.7 性能度量：加速比、效率、强/弱扩展与两条定律

• 定义与目的：加速比（speedup） $S_p = T_1/T_p$，$T_1$ 是同一问题规模下最好的串行实现时间， $T_p$ 是 $p$ 个执行体的时间；效率（efficiency） $E_p = S_p/p \in [0,1]$，衡量每个核的”利用率”。 若”加速”来自问题规模也变大了，那是另一种故事，因此必须区分两种扩展方式：

• 直观解释：强扩展是”10 个人搬 1 吨砖，多久搬完”；弱扩展是”10 个人各搬 100 kg，每人还是要那么久吗”。 本讲 psum 的实测曲线全部是强扩展：$N$ 固定为 $2^{28}$，线程从 1 加到 16，于是 $T_p$ 下降。
• Amdahl 定律（固定规模的上限）：设 $\alpha$ 为可并行化比例，$\;S_p = \dfrac{1}{(1-\alpha)+\alpha/p}$， $S_\infty = 1/(1-\alpha)$。串行部分是硬天花板：$\alpha=0.9$ 时无论多少核也快不过 10×。 讲义用”PIT→LHR 航班”类比：飞到纽约的 1.5 小时无法被任何技术压缩，所以即使有超光速航班，最好也只有 ~5×。
• Gustafson 定律（固定时间的可扩展规模）：反过来问”给我 p 倍资源、同样的时间，能算多大的问题“。 设串行部分耗时 $s$、并行部分耗时 $q$，则 \(S_p = \dfrac{s + p\,q}{s + q} = p - (p-1)\cdot\dfrac{s}{s+q}\) 当 $s \ll q$ 时 $S_p \approx p$——弱扩展下加速比可以接近线性，这正是超算”算得更大”而非”算得更快”的逻辑。
• 底层机制图解（同一台机器的强/弱扩展对照，$\alpha = 0.9$）：

  S_p
  10 |                        ,--------- S_inf = 10 (Amdahl 上限, 强扩展)
   8 |                 ,--''''            ,--''''''''' Gustafson (弱扩展, 规模随 p 增长)
   4 |        ,--''''  ,-''          ,-'''
   2 |  ,-''''   ,-''          ,-''
   1 *--+---------+---------+---------+---------+---------+----► p
     1         2         4         8        16        32
     强扩展 (本讲 psum): 5.64 (p=8), 7.60 (p=16) —— 早早饱和

• 与机器码/硬件的对应：$T_1$ 必须是最好的串行实现（本机 0.3256 ns/元素）， 而不是”1 线程并行版”。讲义特意警告 “Beware the speedup metric!”——用差的基线会虚报加速比。 实践中还要警惕超线性加速比（$S_p > p$）：它通常只说明串行版数据放不进缓存，而并行版每核的数据片能放进 L2/L3 了 （本讲 psum 中每个线程只需读自己那一段，正是这种情况）。

24.3 代码示例与底层机制分析

24.3.1 实测环境

所有数据都在同一台机器上用 taskset 绑定到空闲 CPU 实测（机器为多用户共享，负载约 12， 故每个数据点取多轮中的最小值并交错执行以抵消干扰）：

24.3.2 示例 1：psum-local（每线程寄存器累加 + 最后归约）

代码 (C)：

/* psum_local.c  ---  编译: gcc -O2 -g -Wall -std=c11 psum_local.c -o psum_local -lpthread */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>

typedef unsigned long data_t;

#define MAXTHREADS 64
#define MAXSPACING 16

static size_t nelems_per_thread;
static const size_t spacing = 16;          /* 16*8B = 128B，跨过 cache line */
static data_t psum[MAXTHREADS * MAXSPACING];
static pthread_t tid[MAXTHREADS];
static int myid[MAXTHREADS];

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + 1e-9 * (double)ts.tv_nsec;
}

static void *sum_local(void *vargp)
{
    int id = *((int *)vargp);
    size_t start = (size_t)id * nelems_per_thread;
    size_t end   = start + nelems_per_thread;
    data_t sum = 0;                        /* 局部累加器 -> 寄存器 */
    for (size_t i = start; i < end; i++)
        sum += i;
    psum[(size_t)id * spacing] = sum;      /* 每个线程只写自己的私有位置 */
    return NULL;
}

int main(int argc, char **argv)
{
    size_t nelems = (argc > 1) ? strtoul(argv[1], NULL, 0) : (1UL << 30);
    size_t nthreads = (argc > 2) ? strtoul(argv[2], NULL, 0) : 1;
    int reps = (argc > 3) ? atoi(argv[3]) : 3;

    if (nthreads < 1 || nthreads > MAXTHREADS) { fprintf(stderr, "bad nthreads\n"); return 1; }
    nelems_per_thread = nelems / nthreads;

    double best = 1e30; data_t result = 0;
    for (int r = 0; r < reps; r++) {
        for (size_t i = 0; i < nthreads; i++) psum[i * spacing] = 0;
        double t0 = now();
        for (size_t i = 0; i < nthreads; i++) {
            myid[i] = (int)i;
            pthread_create(&tid[i], NULL, sum_local, &myid[i]);
        }
        for (size_t i = 0; i < nthreads; i++) pthread_join(tid[i], NULL);
        result = 0;
        for (size_t i = 0; i < nthreads; i++) result += psum[i * spacing];
        for (size_t e = nthreads * nelems_per_thread; e < nelems; e++) result += e;
        double dt = now() - t0;
        if (dt < best) best = dt;
    }
    printf("psum-local  N=%-12zu threads=%-3zu best=%9.6f s  result=%lu expect=%lu %s\n",
           nelems, nthreads, best, result, nelems * (nelems - 1) / 2,
           result == nelems * (nelems - 1) / 2 ? "OK" : "WRONG!");
    return 0;
}

【代码做什么？】

1. 把 $N$ 个元素均分给 nthreads 个线程，每个线程处理 nelems_per_thread 个；余下的尾巴由主线程串行补加（”deal with leftovers”）。
2. pthread_create 时传入 &myid[i]——注意每个线程拿到的是自己那一格的地址，这是讲义反复强调的模式。
3. 线程函数内部用局部变量 sum 累加：编译器把 sum 放进寄存器，整个内层循环零次对共享内存的写。
4. 循环结束后只写一次 psum[id*spacing]，间距 spacing = 16 个元素（128 B）确保跨缓存行。
5. pthread_join 全部结束后，主线程做一次 $O(p)$ 的串行归约，再加上尾巴。

【底层机制透视】 sum += i 编译出的是一段极短的单周期依赖链（见下），因此性能上限完全由指令发射能力决定， 不涉及任何缓存行所有权转移。这个”私有化（privatization）”手法是本讲最重要的优化：把 p 个线程对同一变量的 p×N 次写， 变成 p 次写 + 一次串行归约。

【与汇编 / 硬件的对应】 gcc -O2 下 sum_local 的内层循环（objdump -d -M intel 实测）：

401450:  add    rdx,rax          ; sum += i   (rdx 是累加器, 依赖链长度 = 1 cycle)
401453:  add    rax,0x1          ; i++
401457:  cmp    rcx,rax
40145a:  jne    401450

累加器 %rdx 只出现在一条依赖链上，其余三条指令独立发射——这正是 ILP 在起作用。 实测单线程基线为 0.3256 ns/元素，即 $CPE = 1.00$（由 3.07 GHz 有效频率与 1.0 CPE 互推）， 与 CS:APP 那个 CPE ≈ 1.0 的”最优串行实现”完全对得上——这就是本讲的性能标尺。 （一个有趣的对照：把同样的 10 亿次加法放进 main 里直接写，编译器编译出同样的四条指令， 实测却是 0.651 ns/元素 = $CPE = 2.0$——因为在 main 的内层循环里，循环计数器 %rax 同时也是参与累加的数据， add %rbx,%rax 与 add $1,%rax 构成了一条 2 周期的循环依赖链。这恰好说明了依赖链长度就是 ILP 的上限。）

【实测验证】（N = 2^28 = 268435456，min-of-7，交错执行）：

CPE 从 1.00 一路降到 0.13——这正是讲义”从 CPE ≈ 1.0 到接近串行/超线性区”那张表要传达的事实： 只有当每线程的累加器私有化之后，多核才真正开始工作。

24.3.3 示例 2：psum-mutex（错误示范）

代码 (C)：

/* psum_mutex.c  ---  编译: gcc -O2 -g -Wall -std=c11 psum_mutex.c -o psum_mutex -lpthread */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>

typedef unsigned long data_t;

#define MAXTHREADS 64

static volatile data_t global_sum;
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
static size_t nelems_per_thread;
static pthread_t tid[MAXTHREADS];
static int myid[MAXTHREADS];

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + 1e-9 * (double)ts.tv_nsec;
}

static void *sum_mutex(void *vargp)
{
    int id = *((int *)vargp);
    size_t start = (size_t)id * nelems_per_thread;
    size_t end   = start + nelems_per_thread;
    for (size_t i = start; i < end; i++) {
        pthread_mutex_lock(&mutex);
        global_sum += i;                 /* 临界区: 一次加法 */
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

int main(int argc, char **argv)
{
    size_t nelems = (argc > 1) ? strtoul(argv[1], NULL, 0) : (1UL << 24);
    size_t nthreads = (argc > 2) ? strtoul(argv[2], NULL, 0) : 1;
    if (nthreads < 1 || nthreads > MAXTHREADS) { fprintf(stderr, "bad nthreads\n"); return 1; }
    nelems_per_thread = nelems / nthreads;

    global_sum = 0;
    double t0 = now();
    for (size_t i = 0; i < nthreads; i++) {
        myid[i] = (int)i;
        pthread_create(&tid[i], NULL, sum_mutex, &myid[i]);
    }
    for (size_t i = 0; i < nthreads; i++) pthread_join(tid[i], NULL);
    data_t result = global_sum;
    for (size_t e = nthreads * nelems_per_thread; e < nelems; e++) result += e;
    double dt = now() - t0;

    double per_add_ns = dt / (double)nelems * 1e9;
    printf("psum-mutex  N=%-12zu threads=%-3zu time=%9.6f s  per-element=%8.2f ns  result=%lu %s\n",
           nelems, nthreads, dt, per_add_ns, result,
           result == nelems * (nelems - 1) / 2 ? "OK" : "WRONG!");
    return 0;
}

【代码做什么？】 与示例 1 唯一的结构差别是：累加器是全局变量 global_sum，且每一次加法都被 lock/unlock 包住。 结果是正确的（result 与 $(N-1)N/2$ 完全一致），这正是它危险的地方——它是对的，但慢到不可用。

【底层机制透视】 性能崩溃有三个叠加原因：

1. 临界区串行化：整段计算的 $N$ 次加法被迫排成一列，$p$ 个线程不可能同时进入。
2. 锁操作本身极贵：pthread_mutex_lock 未竞争时也要一次原子 RMW（lock cmpxchg），约 10–20 ns； 竞争时还要系统调用 futex 进入内核挂起/唤醒。
3. 真共享（true sharing）：global_sum 与 mutex 所在缓存行在核之间疯狂弹跳，每次 lock 都会把它抢到本地。 加速比在这里不是变小，而是变成负数——加线程只会更慢。

【实测验证】（N = 2^26 = 67108864，min-of-3；对照串行寄存器基线同 N 需 0.0218 s）：

这与讲义的数据完全同构：讲义说互斥锁版本”2.5 seconds → ~10 minutes”，并注明 “Mutex 3X faster than semaphore” （信号量每次 sem_wait/sem_post 要走完整的 P/V 路径，比互斥锁更慢）， 结论也一样：“Clearly, neither is successful.”

24.3.4 示例 3：伪共享 —— 填充（padding）vs 不填充

代码 (C)：

/* falseshare.c  ---  编译: gcc -O2 -g -Wall -std=c11 falseshare.c -o falseshare -lpthread
 * 用法: ./falseshare <N> <threads> <reps> <pad:0|1> <accum:0|1>
 *       pad=0 相邻(p_sum[i])  pad=1 填充(stride=8 个元素 = 64 B)
 *       accum=1 每次迭代都写共享数组(暴露伪共享)   accum=0 寄存器累加后一次写回 */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>

typedef unsigned long data_t;

#define MAXTHREADS 64
#define MAXPAD     16

static volatile data_t psum[MAXTHREADS * MAXPAD * 16];
static size_t nelems_per_thread;
static size_t stride;                  /* 元素步长: 1 = 紧邻, 8 = 独占 cache line */
static int pad_mode;                   /* 0: 无填充(紧邻), 1: 填充 */
static pthread_t tid[MAXTHREADS];
static int myid[MAXTHREADS];
static int use_accumulate;             /* 1 = 每步都写共享数组, 0 = 寄存器累加后一次写回 */

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + 1e-9 * (double)ts.tv_nsec;
}

static void *worker(void *vargp)
{
    int id = *((int *)vargp);
    size_t start = (size_t)id * nelems_per_thread;
    size_t end   = start + nelems_per_thread;
    size_t idx   = (size_t)id * stride;
    psum[idx] = 0;
    if (use_accumulate) {
        for (size_t i = start; i < end; i++)
            psum[idx] += i;            /* 每步都写内存 -> 伪共享在此显现 */
    } else {
        data_t s = 0;
        for (size_t i = start; i < end; i++)
            s += i;
        psum[idx] = s;
    }
    return NULL;
}

int main(int argc, char **argv)
{
    size_t nelems   = (argc > 1) ? strtoul(argv[1], NULL, 0) : (1UL << 26);
    size_t nthreads = (argc > 2) ? strtoul(argv[2], NULL, 0) : 8;
    int    reps     = (argc > 3) ? atoi(argv[3]) : 3;
    pad_mode        = (argc > 4) ? atoi(argv[4]) : 0;
    use_accumulate  = (argc > 5) ? atoi(argv[5]) : 1;

    if (nthreads < 1 || nthreads > MAXTHREADS) { fprintf(stderr, "bad nthreads\n"); return 1; }
    stride = pad_mode ? (64 / sizeof(data_t)) : 1;   /* 8 个 unsigned long = 64 字节 */
    nelems_per_thread = nelems / nthreads;

    double best = 1e30; data_t result = 0;
    for (int r = 0; r < reps; r++) {
        double t0 = now();
        for (size_t i = 0; i < nthreads; i++) {
            myid[i] = (int)i;
            pthread_create(&tid[i], NULL, worker, &myid[i]);
        }
        for (size_t i = 0; i < nthreads; i++) pthread_join(tid[i], NULL);
        result = 0;
        for (size_t i = 0; i < nthreads; i++) result += psum[i * stride];
        for (size_t e = nthreads * nelems_per_thread; e < nelems; e++) result += e;
        double dt = now() - t0;
        if (dt < best) best = dt;
    }
    printf("%-18s threads=%-3zu best=%9.6f s  result=%lu %s\n",
           pad_mode ? "padded(64B sep)" : "adjacent(unpadded)",
           nthreads, best, result,
           result == nelems * (nelems - 1) / 2 ? "OK" : "WRONG!");
    return 0;
}

【代码做什么？】 同一个程序、同一份工作量，只切换两个开关：pad（步长 1 还是 8 个元素）与 accum （每次迭代写共享数组，还是寄存器累加后只写一次）。于是可以把”伪共享”与”私有化”两个因素干净地分离出来。

【底层机制透视】 accum=1 且 pad=0 时，内层循环（实测汇编）是：

401578:  mov    rdx,QWORD PTR [rcx*8+0x4043c0]   ; 读 psum[idx]  —— 必须独占该缓存行
401580:  add    rdx,rax                           ; 加 i
401587:  mov    QWORD PTR [rcx*8+0x4043c0],rdx   ; 写回 psum[idx] —— 又一次独占

8 个线程的 idx 分别是 0..7，地址只差 8 字节，全在同一个 64 B 行内。 每次写都要向其他 7 个核广播”我要独占这一行”（RFO, read-for-ownership）， 其他核的副本被置为 Invalid；下一轮它们再写又要抢回来。缓存行在 8 个核之间来回弹跳， 每次弹跳的代价是几十到上百个周期——注意：没有一个字节被两个线程真正共享（不是真共享）， 所以这种性能损失对程序员完全不可见，只在硬件里发生。

【实测验证】（N = 2^27 = 134217728，每次迭代都写共享数组，min-of-5）：

关键对照：把 accum 换成 0（寄存器累加）后，填充与不填充的差别完全消失 （8 线程：相邻 0.0059 s vs 填充 0.0057 s，差 < 4%）。 这证明伪共享的唯一来源是对共享缓存行的反复写，而不是数组布局本身； 一旦私有化到寄存器，”相邻”也就无害了——这正是讲义”Use registers whenever possible“的实证。

24.3.5 Amdahl 定律与统一性能总览

同一会话、同一 N = 2^26、8 线程，把所有版本放在一张表里（时间越短越好）：

  加速比 S_p = T_1 / T_p   （横轴对数刻度，每个刻度 = 2 倍；"|" 处为 S_p = 1）

     慢169x   慢13.6x   慢4x    慢2x     1x      2x      4x      8x
        |        |        |       |      |       |       |       |
  psum-mutex(8T)   <####|                                              S_p = 0.006
  psum-array(8T,紧邻)  <#|                                             S_p = 0.074
  串行基线(1T)           |*|                                           S_p = 1.00
  psum-array(8T,填充)    |  |**                                        S_p = 1.93
  psum-local(8T,寄存器)  |   |****                                     S_p = 3.69

用真实数据套 Amdahl 定律：$S_p = \dfrac{1}{(1-\alpha) + \alpha/p}$，其中 $\alpha$ 是可并行化比例。 取 psum-local 的 $S_8 = 5.64$（N = 2^28 那组数据，样本更大）：

于是理论最大加速比 $S_\infty = 1/(1-\alpha) = 16.7\times$，与机器本可以给的核数相比微不足道； 预测 16 线程应得 $S_{16} = 1/(0.0598 + 0.9402/16) = 8.43\times$， 而实测 $S_{16} = 7.60\times$（效率只有 0.475）——实际比 Amdahl 上限还差， 差额来自内存带宽、NUMA 跨节点访问与共享机器上的干扰。这正是”必须给出串行基线、必须测多条曲线”的理由。

24.4 实验关联

本讲直接服务于 L8 SFS Lab（Simultaneous/Sharing File System）：SFS 服务器天然是多线程的， 每个客户端连接一个线程，因此”线程数增加后吞吐是否线性上升”是评分与调优的核心。 本讲给的三条结论在 SFS 里逐条兑现：

• 锁的粒度就是性能：SFS 里若把整个文件系统用一把大锁（global mutex）保护，就像本节 psum-mutex—— 正确但吞吐不涨；正确做法是每文件/每目录一把锁，把临界区缩到最小。
• 私有化优先：每个客户端线程的缓冲区、每个文件描述符的状态都应私有，只在必须共享处加锁。
• 伪共享在 SFS 里真实发生：若把所有连接的状态放在一个数组 conn_t conns[MAX] 里， 相邻连接的引用计数就在同一缓存行；高并发下会出现”加了线程反而不快”的诡异曲线。填充或按连接动态分配可解决。
• L8 还要在有限时间预算下跑完 trace，因此先测基线、再谈优化是必须的工作习惯。

与后续课程：本讲只覆盖共享内存 + pthread 这一小块。OpenMP（#pragma omp parallel for reduction(+:sum)） 把本讲的 psum-local 模式变成一个编译指示，由运行时自动做私有化与归约；MPI 是消息传递模型的代表； CUDA 属于 DLP/GPU 路线（SIMT 执行模型）。这些是 15-418 / CS149 的内容， 本笔记作者的 CMU 15-418 笔记可作为本讲的直接续篇。

24.5 常见错误与调试技巧

• 无同步地写共享累加器（psum-race）：global_sum += i 在多线程下是”读-改-写”三步，会丢更新。 现象：1 个线程结果正确，>1 个线程答案偏小，且每次运行结果不同。 调试：gcc -fsanitize=thread -g 用 ThreadSanitizer（TSan）跑一次，会直接报 data race 与两条冲突栈； 或把 global_sum 声明为 volatile 并不解决问题，只是让编译器不缓存它——竞态是硬件级的，volatile 不是锁。
• 用锁保护单次加法（psum-mutex 反模式）：正确但灾难性慢（实测 169× 慢于串行）。 调试：perf stat -e context-switches,cpu-migrations 会看到大量 futex 引发的上下文切换； strace -f -e trace=futex 显示锁竞争时的内核挂起。
• 伪共享（false sharing）：多个线程写同一缓存行内不同变量。 现象：加速比远低于预期甚至为负，且结果完全正确，容易误判为”多核就这水平”。 调试：perf stat -e L1-dcache-load-misses,LLC-load-misses，或在 perf c2c record/report 下 查看 cache line 争用（HITM 事件）；先确认 getconf LEVEL1_DCACHE_LINESIZE = 64，再把热点变量间距拉到 64 B。
• 把 pthread_create 放在内层循环里：线程创建/销毁成本约 10–20 μs，比一次加法贵 5 个数量级。 调试：perf stat -e sched:sched_process_fork 观察 fork 次数；正确做法是固定线程池 + 任务队列（讲义并行快排用的正是这个模式）。
• 忘记处理 leftover：nelems % nthreads 个元素没人算。现象：结果恒定地少一个固定值。 调试：让程序同时打印 result 与 (N-1)*N/2 并断言相等；用 size_t 参与比较避免 int 溢出。
• 忽略串行瓶颈（Amdahl）：把 8 线程加速比 5.64× 当成”硬件只有 5.6 核”。调试：用不同 p 画 $S_p$ 曲线并拟合 $\alpha$；若 $S_p$ 早早饱和，先怀疑串行段（顶层 partition、单把大锁、主线程归约）而非硬件。
• 在共享机器上直接测时间：本机 load average ≈ 12，一次测量可能偏差 3 倍以上。 调试：taskset -c <idle-cpus> 绑核，多轮取最小值；更严谨的做法是用 perf stat 的指令数/周期数代替墙钟。

24.6 关键要点

• 并行 ≠ 正确：无同步的共享写几乎必然出错，且错误是非确定性的——”加速比测出来了但结果错了”是最常见的事故。
• 并行 ≠ 更快：psum-mutex 实测比串行慢 169×。共享内存的每一次访问都可能触发缓存行所有权转移，同步的开销以百纳秒计。
• 私有化（privatization）是第一法则：每线程用寄存器/局部变量累加、最后单线程归约，把 $p \times N$ 次共享写降到 $p$ 次。 实测 psum-local 从 CPE 1.00 降到 0.13，8 线程拿到 3.69–5.64× 加速。
• 伪共享是”看不见的敌人”：一致性以 64 B 缓存行为单位，不同变量落在同一行就会互相 ping-pong。 实测 8 线程下相邻布局比填充布局慢 20.6×，16 线程慢 39.8×；修复只需把间距拉到 64 B。
• Amdahl 定律是硬上限：$S = 1/((1-\alpha)+\alpha/p)$，由本机实测 $\alpha \approx 0.94$ 推出上限仅 16.7×， 所以”我有 64 核”从来不等于”我能加速 64 倍”；先测串行基线，再谈并行。
• 同步必须留在内层循环之外：讲义原话是 inner loops must be synchronization free——锁在循环内就等于宣布放弃并行。

24.7 思考题（带答案）

题 1（计算题） 某程序串行运行 240 s，其中 216 s 可以完美并行化。求：(a) 用 8 个线程的加速比与效率； (b) 线程数趋于无穷时的最大加速比；(c) 若把串行部分再优化掉一半，8 线程的加速比是多少？

答：$\alpha = 216/240 = 0.9$，串行部分 $1-\alpha = 0.1$。 (a) $S_8 = \dfrac{1}{0.1 + 0.9/8} = \dfrac{1}{0.2125} = 4.71$，$E_8 = 4.71/8 = 0.588$。 (b) $S_\infty = 1/0.1 = 10$。 (c) 串行时间 24 s → 12 s，总时间 228 s，$\alpha^{\prime} = 216/228 = 0.947$， $S_8^{\prime} = \dfrac{1}{0.0526 + 0.947/8} = \dfrac{1}{0.1710} = 5.85$。 注意：优化串行部分（把 0.1 变成 0.05）比多加一倍线程更有效。

题 2（计算题 · 判断伪共享） 在 64 B 缓存行、8 字节对齐的机器上，结构体 struct { long a; long b; long c; long d; long e; long f; long g; long h; } s; 的数组 s[4]。 线程 T0 反复写 s[0].a，线程 T1 反复写 s[1].a，线程 T2 反复写 s[3].h。 问：哪些线程之间会发生伪共享？忽略写之间的其他访问。

答：结构体大小 $8 \times 8 = 64$ B，正好等于一个缓存行；s[i] 的起始地址是 base + 64i，因此每个 s[i] 独占一行。 s[0].a 在行 0，s[1].a 在行 1，s[3].h 在行 3——三者各占一行，不发生任何伪共享。 若把结构体改成 5 个 long（40 B，按 8 字节对齐），则 s[0] 占 [0,40)、s[1] 的 .a 在 [40,48)——同属第 0 个 64 B 行， T0 与 T1 之间就会出现伪共享。结论：判断伪共享的唯一方法是算地址除以 64 的商是否相同，不能凭”变量不是一个”就想当然。

题 3（计算题 · 加速比与效率） 用本讲的真实数据：psum-local 在 $N = 2^{28}$ 时 $T_1 = 0.0874$ s、 $T_4 = 0.0224$ s、$T_{16} = 0.0115$ s。求 $S_4, E_4, S_{16}, E_{16}$，并解释 $E_{16}$ 为什么不到一半。

答：$S_4 = 0.0874/0.0224 = 3.90$，$E_4 = 3.90/4 = 0.975$； $S_{16} = 0.0874/0.0115 = 7.60$，$E_{16} = 7.60/16 = 0.475$。 $E_{16}$ 低的原因是：除 Amdahl 串行段（主线程归约、线程创建/join、尾巴元素）外， 还有共享资源饱和——本机 2 个 NUMA 节点，16 个线程跨节点后要经过互连访问数据， 且机器被多用户共享（load ≈ 12），再加上 64 核的 L3 是分片的，带宽而非核数成为上限。

题 4（找错题） 一位同学写并行求和：每个线程 for (i = start; i < end; i++) psum[myid] += i;， 最后主线程归约 psum[0..p-1]。他测到 8 线程只比 1 线程快 1.3 倍，并断言”这台机器只有 1.3 个有效核”。 他的错在哪？

答：错在把伪共享误判为硬件极限。psum[myid] 是 8 字节，8 个线程的下标 0..7 都落在同一个 64 B 缓存行， 每次 += 都要独占整行，缓存行在 8 个核之间 ping-pong。本讲实测同样的写法在 8 线程下比填充版本慢 20.6×。 修法有两条：(1) 把累加器换成局部变量、循环结束后只写一次（psum-local，最彻底）； (2) 保留数组写，但让间距等于 64 B（psum[myid*8]）。改完以后 8 线程的加速比应接近 4–6×，而不是 1.3×。