Lecture 6: Program Optimization 2: Locality, Communication, and Contention（程序优化（二）：局部性、通信与争用）（日期：Oct 09）

目录 · ← l5 · l7 →

Lecture 6: Program Optimization 2: Locality, Communication, and Contention（程序优化（二）：局部性、通信与争用）（日期：Oct 09）

概述：本讲把”通信”从”机器之间的消息”推广到扩展内存层次结构中的每一级（寄存器 ↔ cache ↔ 内存 ↔ 远程内存），系统讲解降低通信代价的四类技术：减少消息数量与开销（bulk transfer/合并消息）、降低通信延迟（利用局部性）、避免争用（contention）、通信与计算重叠（overlap）。核心工具是 arithmetic intensity（算术强度） 与 inherent vs artifactual communication（固有 vs 人为通信） 的区分；并以 grid solver 为案例演示 1D/2D 分块分配、loop fusion、loop tiling 如何提升算术强度。后半讲介绍性能分析方法论：roofline model（屋顶模型）、high watermark（性能上限水印）实验、硬件 performance counters，以及”固定问题规模测量加速比”的陷阱（超线性加速比之谜）。
注意：本讲与 Written Assignment 1（截止 Oct 9）以及后续 Assignment 2/3 的性能分析部分直接相关——”你是 compute-bound、bandwidth-bound 还是 sync-bound？”的判断方法、roofline 与 high watermark 实验思路将贯穿整个课程。

一、核心概念与定义

1. Message Passing（消息传递模型）

定义：与共享地址空间相对的另一抽象：每个线程运行在自己的私有地址空间中，线程之间只能通过发送/接收消息交换数据。send(X, dest, tag)：把本地变量 X 的内容作为消息发给 dest，并打上标识符 tag；recv(Y, src, tag)：接收来自 src 的、带 tag 的消息并存到本地变量 Y。发送消息是线程 1、2 之间交换数据的唯一方式。
现实类比：讲义中的经典比喻——蜗牛邮件（snail mail）：每个人有自己的邮箱（私有地址空间），要给别人东西只能写信寄过去（send），对方收到信才知道内容（recv）。
公式/图示：

线程1地址空间            线程2地址空间
┌────────────┐          ┌────────────┐
│ Variable X │──send──► │ Variable Y │
└────────────┘  消息+tag └────────────┘
（红色箭头 = 通信操作：唯一的跨线程数据交换途径）

实现层面：硬件不需要实现全局共享地址空间，只需要提供节点间消息机制——因此可以把普通商用机器用网络（如 Infiniband）连成大规模并行机，消息传递是集群与超算的编程模型。

2. Blocking Send/Receive（阻塞式同步收发）

定义：send() 在收到接收方确认（ack）、确认消息数据已进入接收方地址空间后才返回；recv() 在消息数据被拷贝进接收方地址空间并发出 ack 后才返回。语义是”收发双方在消息上同步”。
现实类比：挂号信——寄出方要等到收件人签收回执（ack）才算”寄完”；收件人要拿到信并签收，寄件人才算解脱。
公式/图示：

发送方:  SEND(foo) ──拷贝到网络缓冲──► 发送 ────────► 收到 ack ──► SEND() 返回
接收方:                                 RECV(bar) ──拷贝进地址空间──► 发 ack ──► RECV() 返回

3. Non-Blocking（Asynchronous）Send/Receive（非阻塞异步收发）

定义：send() 立即返回，但调用线程在消息真正发送完成前不得修改发送缓冲；recv() 只是”登记”未来要接收的意图并立即返回一个句柄（handle），用 checksend(h)/checkrecv(h) 查询实际完成状态。调用线程可以在等待期间做其他工作——即通信与计算重叠（overlap）。
现实类比：电子邮件——点”发送”就继续干别的（异步），但邮件正文在发送完成前不能改动；收件人也不用一直守在邮箱前，稍后查收即可。
公式/图示：

发送方:  SEND(foo) ──► 返回 handle h1 ──► （继续做别的计算）──► CHECKSEND(h1) 通过后
         （此时才能安全修改 foo）                                 方可修改 foo
接收方:  RECV(bar) ──► 返回 handle h2 ──► （继续做别的计算）──► CHECKRECV(h2) 通过后
         （此时才能安全读取 bar）                                 方可读取 bar
（红色文字 = 与应用程序线程并发执行的通信过程）

4. NUMA（Non-Uniform Memory Access，非均匀内存访问）

定义：多插槽（multi-socket）等现代系统中，不同核心访问同一内存地址的延迟可能不同（取决于内存控制器与核心的相对位置），且带宽也可能不同。Intel 的 ring interconnect（四环：request/snoop/ack/data，6 个节点，理论峰值约 435 GB/s）与 SUN Niagara 2 的 crossbar（面积约等于一个核）都是片上互连的实现例子。
现实类比：住在不同宿舍楼的学生去同一个图书馆——离图书馆近的宿舍（本地内存）走得快，远的（远端内存）走得慢，即使去的是同一本书。
公式/图示：

      ┌── Core1..4 ── Memory Controller ── Memory ◄── X（核心1-4 访问快）
片上网络┤
      └── Core5..8 ── Memory Controller ── Memory    （核心5-8 访问 X 慢）

5. Arithmetic Intensity（算术强度）

定义：算术强度 = 计算量（如指令数）/ 通信量（如字节数）。讲义也给出”amount of computation / amount of communication”的公式：若分子是计算的执行时间，比值就是代码的平均带宽需求。1 / 算术强度 是 communication-to-computation ratio（通信计算比）。由于现代并行处理器”计算能力/可用带宽”的比值很高（回忆第 3 讲逐元素向量乘的例子），必须有高算术强度才能高效利用它们。
现实类比：算术强度像”一次进货能支撑多少道菜”——进货（通信）一次很贵，所以要尽量让每次取回来的数据（cache line/消息）被多次计算使用。
公式/图示：

算术强度 = amount of computation（指令数）/ amount of communication（字节数）
  · 高算术强度（低通信计算比）：计算密集，好！
  · 低算术强度（高通信计算比）：带宽受限，差！

例（讲义 loop fusion）：add 循环 = 2 load + 1 store per 1 次运算 → 算术强度 1/3
                          fused 循环 = 4 load + 1 store per 3 次运算 → 算术强度 3/5

6. Inherent Communication（固有通信）与 Artifactual Communication（人为通信）

定义：固有通信是并行算法中必须发生的通信，是算法的根本属性（如消息传递 grid solver 中发送 ghost rows）；人为通信是除此之外的一切通信，源于系统实现的实际细节（缓存行粒度、缓存容量有限、无效加载等）。减少固有通信要靠好的 assignment（分配）；减少人为通信要靠局部性优化。
现实类比：固有通信像”两家分店必须互相调货”（业务必需）；人为通信像”每次调货必须整车发货，哪怕只需要一件”（运输系统的浪费）。
公式/图示：人为通信的三个来源（讲义）：
1. 最小传输粒度：程序只 load 1 个 4 字节 float，但整条 64 字节 cache line 必须从内存传来——多传了 16 倍；
2. 系统操作的冗余：连续 store 16 个 4 字节 float，整条 cache line 被”load → 整体覆盖 → store 回内存”，load 是多余的（2 倍开销）；
3. 有限复制容量：缓存太小，同一数据在两次访问之间被逐出，导致重复通信（capacity miss，容量缺失）。

7. Temporal Locality（时间局部性）与 Loop Tiling/Blocking（循环分块）

定义：时间局部性指”刚访问过的数据很快会被再次访问”。Blocking（tiling，分块） 通过重排计算顺序减少 capacity miss：把计算组织成小块，让小块内的邻域数据在 cache 中存活到被再次使用。讲义例子：cache line = 4 个网格元素、cache 容量 = 24 个元素时，row-major 逐行遍历在第二行开头需要为每 4 个输出元素加载 3 条 cache line；分块后每 6 个输出元素只需加载 2 条 cache line。
现实类比：去仓库取料——与其每次只取一件（来回跑），不如把接下来要用的料一次搬回工位（分块），减少往返次数。
公式/图示：

朴素 row-major 遍历（红线 = 必须重新从内存加载）：
  行0: [████] [████] [████] [████] [████] [████]  （cache 24 元素 = 6 行块）
  行1: 更新时上一行数据已被逐出 → 每 4 个输出元素 load 3 条 cache line

分块遍历：先算左上角小块（含其邻居），邻居在 cache 中 → 每 6 个输出元素 load 2 条 cache line

8. Loop Fusion（循环融合）

定义：把多个依次遍历同一数组的循环合并成一个循环，让同一批数据在一次遍历中被多次使用，提高算术强度。讲义例子：E = D + (A+B)*C 用三个独立循环（add/mul/add，各算术强度 1/3）vs 融合成一个循环（4 load + 1 store per 3 运算，算术强度 3/5）。模块化的代码（如 NumPy 式数组库）更好读，但融合版性能好得多。
现实类比：一次购物跑三家店（三个循环）vs 在一家店买齐（融合）——后者少跑路（少重复加载数据）。
公式/图示：见代码示例 3。

9. Contention（争用）与 Hot Spot（热点）

定义：资源（内存、通信链路、服务器……）有固定吞吐（单位时间事务数）。当很短时间窗口内大量请求涌向同一资源时，资源成为热点（hot spot），请求排队，整体操作时间变长。减少争用：复制被争用的资源（本地副本、细粒度锁）、错开访问时间、用树形通信结构（降低争用但无争用时延迟更高）vs 扁平通信（无争用时低延迟但有争用风险）。
现实类比：讲义的办公室答疑例子——Kayvon 3:00–3:20 答疑，多个学生同时从 Bytes Cafe 走来（各 5 分钟路程），到办公室后排成一队：第一个学生 10 分钟搞定，排在后面的学生要 23 分钟；而如果大家预约错开（3:00、4:30），每个人都是 10 分钟。问题不在”教授答疑”本身，而在同时到达导致的排队。
公式/图示：

扁平通信（更新共享变量）:         树形通信（reduce）:
   P1─┐                            P1──┐
   P2─┼─► 共享变量（热点!）           P2──┼──► 部分和 ──┐
   P3─┼─►                          P3──┼──► 部分和 ──┼──► 最终结果
   P4─┘                              P4──┘            │
   高争用风险，无争用时延迟低         争用少，但无争用时延迟更高

10. Roofline Model（屋顶模型）与 High Watermark（性能上限水印）

定义：Roofline 是分析程序性能受何限制的模型：横轴是算术强度，纵轴是最大可达指令吞吐——水平区（高算术强度）是 compute limited（计算受限），对角区（低算术强度）是 memory bandwidth limited（带宽受限），屋顶曲线即机器能力上限。High watermark 是性能分析的实验方法：通过修改程序建立”最优情况”的上界——如把所有数组访问改成 A[0]（局部性收益上界）、删除所有原子/锁操作（同步开销收益上界）、删掉大部分数学运算但保留同样数据加载（判断内存瓶颈）、或添加数学指令看执行时间是否线性增长（判断是否指令率受限）。
现实类比：屋顶模型像限速牌——车（程序）在平路（计算密集）能跑多快看发动机（计算能力），在上坡（通信密集）能跑多快看坡度（带宽）——永远到不了屋顶之上。
公式/图示：

       吞吐
        │╱╲ 屋顶 = 机器上限
        │ ╲   （水平区：compute limited）
        │  ╲
        │   ╲ （对角区：bandwidth limited）
        └───────► 算术强度

11. Ghost Cell（幽灵单元/镜像单元）

定义：消息传递模型中，每个线程的私有数组只保存自己负责的那部分网格；计算边界单元时需要邻居线程的数据，于是把远端地址空间的数据复制一份到本地数组的边缘（ghost cells）。这些数据”归”其他线程所有（owned by other threads）。
现实类比：两个邻国各自维护一份”边境地图”——边境线对面 1 公里内的地形是复制的（ghost），不归自己管，但规划时需要看。
公式/图示：见代码示例 1。

12. Super-Linear Speedup（超线性加速比）

定义：加速比超过 P（处理器数）的现象。原因通常是工作集（working set）变小后装进了 cache：处理器多了，每个处理器分到的数据块小到能放进自己的 cache，消除了大量内存访问；同理，问题太大时单机工作集装不进内存（thrashing 到磁盘），换大机器（内存更多）会显得加速比”惊人”。这提示：固定问题规模评估机器是有问题的——问题规模与机器规模之间存在复杂交互（影响负载均衡、开销、算术强度、局部性）。
现实类比：一个人搬 100 箱货需要来回跑很多趟仓库（每次货太多堆不下只能放仓库）；10 个人时每人只需搬 10 箱，全都能放在各自的推车上——每个人”搬得快了”（工作集进了 cache），总加速比超过 10。
公式/图示：

258×258 网格在 32 处理器上（每处理器仅 ~310 格）：无收益甚至变慢（通信/计算比太高）
1K×1K 网格在 32 处理器上（每处理器 ~32K 格）：正常加速
大网格 + 足够多处理器：每处理器块变小 → 装进 cache → 超线性加速比

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

示例 1：消息传递版 grid solver——ghost rows 交换与死锁

背景：回顾第 4 讲的 grid solver（red-black 更新）。消息传递模型下，网格被分成 P 份私有数组，每份含 rows_per_thread+2 行（上下各加一行 ghost cells）。每轮迭代，线程需要邻居刚更新的边界行（inherent communication）。

代码 A（MPI 风格，同步/阻塞收发，会死锁！）：

// 编译：mpicc -o solver solver.c   运行：mpirun -np 4 ./solver
// 伪代码整理自讲义；localA[i,j] 记法表示扁平数组 localA[i*(N+2)+j]
// MSG_ID_ROW 等为消息标识常量
int N, tid = get_thread_id();
int rows_per_thread = N / get_num_threads();
float* localA = allocate(rows_per_thread + 2, N + 2);  // 含 ghost rows（上下各一行）

void exchange_ghost_rows_deadlock() {
    int bytes = sizeof(float) * (N + 2);   // 一整行的字节数
    // 每个线程先"发送"再"接收" —— 使用同步 send/recv 时必然死锁！
    if (tid != 0)
        send(&localA[1][0],     bytes, tid - 1, MSG_ID_ROW);  // 把第 1 行发给上邻居
    if (tid != get_num_threads() - 1)
        send(&localA[rows_per_thread][0], bytes, tid + 1, MSG_ID_ROW); // 把最后一行发给下邻居
    if (tid != 0)
        recv(&localA[0][0],     bytes, tid - 1, MSG_ID_ROW);  // 从上邻居收 ghost row
    if (tid != get_num_threads() - 1)
        recv(&localA[rows_per_thread+1][0], bytes, tid + 1, MSG_ID_ROW);
}

【代码做了什么？】：每个线程想把”自己负责区域的最上一行/最下一行”发给邻居，同时从邻居接收它们的最上行/最下行，填入自己的 ghost cells。但使用同步 send 时，send 要等接收方确认；所有线程都先阻塞在自己的 send 上、还没执行到 recv——循环等待（circular wait），死锁。

代码 B（死锁修复：奇偶交错收发）：

// 偶数线程：先 send 后 recv；奇数线程：先 recv 后 send
// 打破"所有线程同时阻塞在 send"的循环等待
void exchange_ghost_rows_fixed() {
    if (tid % 2 == 0) {          // 偶数线程
        sendDown(); recvDown();  // 先发下行，再收上行
        sendUp();   recvUp();
    } else {                     // 奇数线程
        recvUp();   sendUp();    // 先收上行，再发下行
        recvDown(); sendDown();
    }
}

【并行机制解说】

数据如何共享/通信：通信显式发生在消息收发中；一次收发一整行（bulk transfer，批量传输一整行而不是逐个元素发消息）；数组下标相对于本地地址空间。
同步方式：消息收发本身即同步原语——讲义指出，互斥、barrier、flag 都可以用消息实现（例如把”汇总 diff”实现为所有线程 send 自己的 my_diff 给线程 0，线程 0 计算全局 diff 后广播 done 标志）。
死锁如何避免：同步收发下，”所有线程先 send 再 recv”会死锁（发送方等接收方，接收方还没到 recv）。修复：奇偶线程交错顺序（偶数先发后收、奇数先收后发），保证同一时刻至少有一方的 recv 在等待对方的 send——这是教科书级的死锁避免（打破循环等待）。
对应概念：message passing、blocking send/recv、ghost cell、inherent communication、deadlock。

示例 2：MPI 非阻塞收发（通信与计算重叠）

代码（MPI，MPI_Isend/MPI_Irecv）：

// 编译：mpicc -o solver solver.c   运行：mpirun -np 4 ./solver
#include <mpi.h>

void exchange_ghost_rows_async() {
    int bytes = sizeof(float) * (N + 2);
    MPI_Request reqs[2];
    int nreq = 0;

    // 1. 发布（post）收发请求：立即返回，不等待完成
    if (tid != 0) {
        MPI_Isend(&localA[1][0], bytes, MPI_FLOAT, tid - 1, MSG_ID_ROW,
                  MPI_COMM_WORLD, &reqs[nreq++]);
        MPI_Irecv(&localA[0][0], bytes, MPI_FLOAT, tid - 1, MSG_ID_ROW,
                  MPI_COMM_WORLD, &reqs[nreq++]);
    }
    // ... 对下邻居同理 ...

    // 2. 在通信进行的同时，执行与 ghost rows 无关的计算（overlap！）
    compute_interior_without_borders();

    // 3. 需要用到收发结果时，才等待完成
    MPI_Waitall(nreq, reqs, MPI_STATUSES_IGNORE);
    // 此时才能安全读取 localA[0][*]（接收缓冲）、修改发送缓冲
}

【代码做了什么？】

MPI_Isend/MPI_Irecv 只”登记”通信请求并返回 handle，函数立即返回。
在等待消息期间，线程执行不依赖 ghost data 的计算（如内部区域更新）——通信与计算重叠，隐藏通信延迟。
MPI_Waitall 在所有请求完成后返回；此后才可安全访问接收缓冲（recv 缓冲未就绪时读取是未定义行为）与修改发送缓冲（消息可能尚未拷贝完）。

【并行机制解说】

对比阻塞版本：阻塞收发把”等待通信完成”变成线程的停顿（stall）；非阻塞收发把这段等待时间填满计算。讲义总结的”增加通信/计算重叠”手段：应用侧用异步消息；硬件侧用流水线（pipelining）、多线程、预取（prefetching）、乱序执行（out-of-order execution）——但需要应用有足够的额外并发（并发度要大于执行单元数）。
对应概念：non-blocking send/recv、overlap、pipelining（重叠/流水思想的软件形态，硬件流水见讲义总结）、communication latency hiding。

示例 3：提高算术强度——循环融合（loop fusion）

代码（C）：

// 目标：E = D + (A + B) * C，数组长度 n

// ── 版本 A：三个独立循环（模块化，例如 NumPy 式数组库的写法）──
void add(int n, float* A, float* B, float* C) {
    for (int i = 0; i < n; i++)
        C[i] = A[i] + B[i];
}
void mul(int n, float* A, float* B, float* C) {
    for (int i = 0; i < n; i++)
        C[i] = A[i] * B[i];
}

float *A, *B, *C, *D, *E, *tmp1, *tmp2;   // 假设已分配
add(n, A, B, tmp1);      // tmp1 = A + B
mul(n, tmp1, C, tmp2);   // tmp2 = (A+B) * C
add(n, tmp2, D, E);      // E = (A+B)*C + D

// ── 版本 B：循环融合（fused）──
void fused(int n, float* A, float* B, float* C, float* D, float* E) {
    for (int i = 0; i < n; i++)
        E[i] = D[i] + (A[i] + B[i]) * C[i];   // 每个元素一趟读完所有输入
}
fused(n, A, B, C, D, E);

【代码做了什么？】

版本 A：tmp1、tmp2 两个临时数组，数据被反复读写——tmp1 被写一次、读一次；每次循环都要把 A、B、C、D 各自重新从内存加载。
版本 B：单个循环，每个输出元素一次性读入 A[i]、B[i]、C[i]、D[i]，在寄存器里完成加乘加，一次写出。同一批数据只进 cache/寄存器一次。

【并行机制解说】

算术强度对比（讲义原话）：版本 A 的 add 与 mul 都是”per math op: 2 loads + 1 store”，算术强度 = 1/3，总体也是 1/3；版本 B 是”per 3 math ops: 4 loads + 1 store”，算术强度 = 3/5。同样的计算，通信量几乎减半——在带宽受限的机器上，版本 B 可以快接近 2 倍。
代价：版本 A 更模块化、可组合（数组数学库风格）；版本 B 更难维护。性能 vs 模块化的经典权衡。
对应概念：arithmetic intensity、temporal locality、loop fusion、减少人为/固有通信（数据被重复加载属于可避免的通信）。

示例 4：改善时间局部性——grid solver 的循环分块（loop tiling/blocking）

代码（C）：

// Gauss-Seidel 式更新：A[i,j] = 0.2*(A[i,j] + A[i,j-1] + A[i-1,j] + A[i,j+1] + A[i+1,j])
// 假设 row-major 存储：A[i*n + j]
// 讲义参数：cache line = 4 元素，cache 容量 = 24 元素（6 条 line）

// ── 朴素版本：逐行扫描 ──
void gauss_seidel_naive(int n, float* A) {
    for (int i = 1; i < n - 1; i++)
        for (int j = 1; j < n - 1; j++)
            A[i*n + j] = 0.2f * (A[i*n + j] + A[i*n + j-1] +
                                 A[(i-1)*n + j] + A[i*n + j+1] + A[(i+1)*n + j]);
}

// ── 分块版本：把计算组织成 block×block 的小块 ──
void gauss_seidel_blocked(int n, float* A, int block) {
    for (int i0 = 1; i0 < n - 1; i0 += block)
        for (int j0 = 1; j0 < n - 1; j0 += block)
            for (int i = i0; i < i0 + block && i < n - 1; i++)
                for (int j = j0; j < j0 + block && j < n - 1; j++)
                    A[i*n + j] = 0.2f * (A[i*n + j] + A[i*n + j-1] +
                                         A[(i-1)*n + j] + A[i*n + j+1] + A[(i+1)*n + j]);
}

【代码做了什么？】

两个版本做完全相同的计算（浮点顺序略有不同，但都收敛到误差阈值内）。
朴素版本按行推进：更新第 i 行的格子时需要第 i-1 行的邻居。当处理到第 2 行第 1 个格子时，之前访问过的 (0,1)、(1,1)、(2,1)、(0,2)、(2,2) 等元素已被逐出 cache（cache 只有 24 个元素）——讲义指出该程序每 4 个输出元素要加载 3 条 cache line（大量 capacity miss，人为通信）。
分块版本按 block×block 小块推进：小块的邻居行在小块处理期间留在 cache 中——讲义数据：每 6 个输出元素只加载 2 条 cache line。

【并行机制解说】

时间局部性：分块让”刚访问的数据很快再次被访问”（邻居复用），把 cache miss 变成 hit。
为什么是”人为通信”：这些重复加载不是算法必需的（inherent），而是因为 cache 容量有限、数据在两次访问之间被逐出（capacity miss）——属于 artifactual communication，可通过重排计算顺序消除。
与并行化的关系：这个重排与第 4 讲的 red-black 重排目的一致——改变访问/计算顺序换取更好的资源利用（那里换并行度，这里换局部性）。
对应概念：temporal locality、loop tiling/blocking、artifactual communication、capacity miss。

示例 5：生产者-消费者流水线（pipelining：通信与计算重叠的软件形态）

代码（C++，std::thread + 有界队列）：

#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <cstdio>

// 有界阻塞队列：容量 cap 决定流水线深度（缓冲多少"在途"数据）
template <typename T>
class BoundedQueue {
    std::queue<T> q;
    std::mutex m;
    std::condition_variable not_full, not_empty;
    size_t cap;
public:
    explicit BoundedQueue(size_t c) : cap(c) {}
    void push(T v) {
        std::unique_lock<std::mutex> lk(m);
        not_full.wait(lk, [&]{ return q.size() < cap; });
        q.push(std::move(v));
        not_empty.notify_one();
    }
    T pop() {
        std::unique_lock<std::mutex> lk(m);
        not_empty.wait(lk, [&]{ return !q.empty(); });
        T v = std::move(q.front());
        q.pop();
        not_full.notify_one();
        return v;
    }
};

int main() {
    BoundedQueue<int> q(2);   // 容量 2：最多 2 个"在途"数据项

    std::thread producer([&]{
        for (int i = 0; i < 100; i++) q.push(i);   // 生产阶段
        q.push(-1);                                 // 哨兵：结束信号
    });
    std::thread consumer([&]{
        while (true) {
            int v = q.pop();
            if (v == -1) break;
            std::printf("%d\n", v);                 // 消费阶段
        }
    });
    producer.join();
    consumer.join();
    return 0;
}

【代码做了什么？】

生产者线程不断把数据推入有界队列；消费者线程不断取出处理。队列容量 > 0 意味着生产者不需要等消费者处理完当前项就能生产下一项——两者在时间上重叠。
把多个这样的队列串成链（stage1 → queue → stage2 → queue → stage3）就构成多级流水线：每一级处理完就把结果传给下一级，各级同时工作。

【并行机制解说】

与讲义的对应：讲义在”减少通信代价”的总结中列出：增加通信/计算重叠——应用作者用异步通信；硬件实现者用流水线（pipelining）、多线程、预取、乱序执行。本示例是应用侧”重叠”思想的直接体现：通信（队列传输）与计算（生产/消费）重叠，隐藏通信延迟，与示例 2 的非阻塞消息收发异曲同工。
与工作窃取的联系：第 5 讲的分布式队列 + 窃取同样是”队列”思想——只是那里的队列存”任务”，这里的队列存”数据流”；两者都靠”本地操作 + 有界同步”降低争用。
注意：讲义未把生产者-消费者流水线作为独立主题，本示例用于直观展示讲义中”increase communication/computation overlap”的方法；真实的软件流水线通常与循环分块（示例 4）结合，把”读数据、算、写数据”拆成流水阶段。
对应概念：pipelining（重叠）、non-blocking 通信思想、contention 的缓解（有界缓冲避免无界争用与拥塞）。

三、关键要点

“通信”无处不在：把并行系统看作扩展的内存层次结构（寄存器 → L1 → L2 → L3 → 本地内存 → 远端内存 1 跳 → N 跳），局部性管理在每一级都重要；访问未在本地满足就会触发与下一级的通信。消息传递只是把”跨处理器通信”显式化。
算术强度是核心指标：算术强度 = 计算量/通信量，越高越好；现代并行处理器”计算能力/带宽”比值很高，低算术强度的代码必然带宽受限（回忆第 3 讲：内存 100% 时间在传输，核利用率只由指令吞吐与内存吞吐决定，与延迟/未完成请求数无关）。优化 = 提高算术强度（分块、融合、共享数据）或减少通信量。
区分 inherent 与 artifactual communication：固有通信靠好的 assignment 减少（1D blocked → 2D blocked 的算术强度从 ∝ N/P 提升到 ∝ N/√P，通信随 P 亚线性增长）；人为通信靠局部性优化减少（分块消除 capacity miss、融合消除重复加载）。
消息传递的死锁可以且必须主动避免：同步收发下”全体先 send 后 recv”必然死锁；用奇偶交错顺序或非阻塞收发打破循环等待。非阻塞收发的另一收益是通信与计算重叠。
性能分析要”测量 + 建立上界”：先做最简单的并行方案再测量；用 high watermark 实验判断自己是 compute-bound、bandwidth-bound 还是 sync-bound；用 roofline 模型定位”离屋顶还有多远”；用 performance counters（IPC、L3 hit ratio、bytes read）获取硬数据。警惕固定问题规模的加速比测量：问题太小（通信/计算比高）无加速甚至变慢，工作集装进 cache 会产生超线性加速比——评估时要考虑问题规模与机器规模的匹配。

四、常见陷阱与注意事项

死锁：同步 send/recv 的顺序错误。所有人先 send 后 recv（或先 recv 后 send）会循环等待。修复：奇偶交错（偶数先发后收、奇数先收后发）、或改用非阻塞收发。另一个常见死锁：线程 0 汇总 diff 时，其他线程在等待 MSG_ID_DONE，而线程 0 又在等待 MSG_ID_DIFF——注意消息顺序与匹配（tag）。
异步收发的缓冲使用时机：非阻塞 send 返回后不能马上修改发送缓冲，非阻塞 recv 返回后不能马上读取接收缓冲——必须等 checksend/checkrecv（MPI 中是 MPI_Wait/MPI_Test）确认完成。违反会读到旧数据或发送被破坏的数据。
忽略局部性，把带宽当无限：row-major 扫描导致 capacity miss（每 4 个输出元素 load 3 条 cache line）时，程序是带宽受限的——加核、加频率都救不了；要用分块/融合提高算术强度。模块化的三循环写法（每个算术强度 1/3）在带宽受限机器上比融合版（3/5）慢近一半。
争用被忽视：所有 worker 抢一个共享队列/共享变量（hot spot）时，同步串行化。对策：复制资源（每线程本地副本 + 最后合并）、错开访问、分布式队列 + 窃取（第 5 讲）。
测量陷阱与低估串行开销：① 与”并行算法跑在 1 个核上”比加速比（而不是与最优串行程序比）是自我安慰；② 固定问题规模（258×258 网格在 32 处理器上每处理器仅 ~310 格）通信/计算比太高，无收益甚至变慢；③ 超线性加速比不一定代表算法好——可能只是工作集装进了 cache（或从磁盘 thrashing 变为装入内存）；④ “CPU 使用率”（activity monitor）对性能优化几乎没有帮助，要用硬件 performance counters；⑤ 临界区、阻塞收发、barrier 都是串行执行的时间、都受 Amdahl 定律约束，能用非阻塞/重叠解决的就不要用阻塞等待。

五、思考题（带答案）

问：讲义问”如何从图中看出内存总线已 100% 利用？若内存延迟提高（总线带宽不变、请求可流水化）图示如何变化？若带宽提高呢？” 答：① 内存总线 100% 利用：图中红色”从内存传输数据”的块连续不断、没有空隙（内存永远在忙）；此时核利用率只由指令吞吐与内存吞吐的比值决定，与延迟、未完成请求数无关。② 延迟提高：红色块之间的”请求在途”时间变长（load 指令发出到数据返回的等待更长），但总线仍在满负荷传输（吞吐不变），只是核的空闲时间（红色区域，stall）更多——前提是未完成请求数足够多能持续”喂饱”总线；③ 带宽提高：红色块变短（每条 cache line 传输更快），同样指令序列下核的空闲减少、利用率上升——但若带宽提高到计算成为瓶颈，则进入 compute-limited 区（roofline 的水平区），再加带宽无益。
问：为什么说”1D blocked 分配下算术强度 ∝ N/P，而 2D blocked 分配下 ∝ N/√P”？这对并行机设计意味着什么？答：N×N 网格分给 P 个处理器。1D 分块：每处理器计算 N²/P 个元素，只需与上下两个邻居交换 2 行 ≈ 2N 个元素（通信量不随 P 减少！），算术强度 ≈ (N²/P)/(2N) = N/(2P)；P 增大时通信/计算比线性变差。2D 分块：每处理器计算 N²/P 个元素，与四邻交换的边界长度 ≈ 4N/√P，算术强度 ≈ (N²/P)/(N/√P) = N/√P——通信随 P 亚线性增长。含义：处理器越多，越要选择能捕获算法 2D 局部性的分配；这同时解释了为什么”258×258 小网格在 32 处理器上无收益”（每处理器仅 310 格，算术强度太低）。
问：假设你的程序性能很差。如何用 high watermark 实验判断它是 compute-bound 还是 bandwidth-bound？答：① 把所有数组访问改成 A[0]（消除大部分内存流量）：若执行时间大幅下降，说明程序对内存带宽/延迟敏感（bandwidth/latency-bound），值得投入局部性优化（分块、融合）；若几乎不变，说明瓶颈不在内存。② 删掉大部分数学运算但保留同样的数据加载：若时间下降很少，进一步印证内存瓶颈；若时间大幅下降，则是 compute-bound。③ 反向实验：添加额外数学指令，若时间随运算数线性增长，说明指令率受限（compute-bound）。④ 用 performance counters 直接读数（IPC、L3 miss、bytes read）交叉验证。注意：计算、内存、同步几乎从不完美重叠，单一实验的结论要谨慎，但性能对上述修改的敏感度能很好地指示主导成本。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li