[迁移说明] 本文最初发布于 blog.zzw4257.cn，现已迁移并在本站进行结构化整理与增强。

第四章：DLP（数据级并行）与 TLP（线程级并行）

📋 前置知识回顾
存储层次结构与技术趋势: 处理器-存储器性能差距，局部性原理（时间局部性、空间局部性）。
Cache 基础: 命中/缺失，设计四大问题（块放置、块识别、块替换、写策略）。
Cache 性能: AMAT（平均内存访问时间）、存储停顿周期，优化目标（减少缺失率、减少缺失代价、减少命中时间）。
CPU 漏洞与 Cache 安全: Meltdown、Spectre，缓存侧信道攻击。

1. Flynn 计算机体系结构分类法

Flynn 分类法根据指令流和数据流的数量对计算机体系结构进行分类。

SISD (Single Instruction, Single Data - 单指令流单数据流): 传统的冯·诺依曼结构。
SIMD (Single Instruction, Multiple Data - 单指令流多数据流):
- 向量处理器 (Vector Processors)
- 阵列处理器 (Array Processors)
MIMD (Multiple Instruction, Multiple Data - 多指令流多数据流):
- 共享存储器 (Shared Memory)
- 消息传递 (Message Passing)
MISD (Multiple Instruction, Single Data - 多指令流单数据流): 实践中罕见（例如，某些容错系统、脉动阵列）。

ℹ️ 本章重点
本章主要关注 SIMD 和 MIMD 体系结构。

2. SIMD: 单指令流多数据流

一条指令同时操作多个数据单元。

2.1. 向量处理器 (Vector Processors)

一种流水线处理器，设计用于高效处理大规模数据数组（向量）。

向量处理器 vs. 标量处理器:
- 向量处理器: 具有向量数据表示和相应的向量指令。
- 标量处理器: 没有向量数据表示或指令。
向量流水线的特殊性: 向量中的元素在操作期间很少相关。
向量操作的处理方法 (例如 D = A × (B + C)):
1. 横向处理: 对每个 i，执行 d_i = a_i * (b_i + c_i)。
  - 问题: 每个元素计算内部存在 RAW 相关，如果使用静态多功能流水线则需要频繁切换流水线。吞吐率低，不适合。
2. 纵向处理 (按列): K <- B + C (所有元素)，然后 D <- A × K (所有元素)。
  - 优点: 数据相关少（示例中为1次），功能切换少（示例中为2次）。首选方法。
3. 纵向和横向结合 (分组处理): 将向量分成若干组，每组按纵向方式处理。
向量处理器结构:
- 存储器-存储器结构 (Memory-Memory): 源/目标向量在存储器中。中间结果也送回存储器。(例如 STAR-100, CYBER-205)
  - 存储器 -> 缓冲器 -> 流水线 -> 缓冲器 -> 存储器
- 寄存器-寄存器结构 (Register-Register): 向量寄存器存储源、目标和中间结果。算术部件与向量寄存器相连。(例如 CRAY-1) 访问速度更快。

2.1.1. CRAY-1 向量处理器 (寄存器-寄存器结构的示例)

主要特点:
- 开创性的超级计算机。
- 约 100 MFLOPS，时钟周期 12.5 ns。
- 多个向量寄存器 (例如 V0-V7 共8个，每个寄存器64个元素，每个元素64位)。
- 多个单功能流水线化的功能部件 (例如加法器、乘法器、求倒数器、移位器、逻辑运算器)。
- 标量寄存器和标量功能部件。
- 指令缓冲寄存器。
CRAY-1 中的并行性:
- 每个向量寄存器 Vi 有独立的总线连接到功能部件。
- 每个功能部件也有总线将结果送回向量寄存器。
- 只要没有 Vi 冲突（并行工作的向量指令的源或结果向量使用同一个 Vi）和功能部件冲突（并行工作的向量指令使用同一个功能部件），各 Vi 和各功能部件就可并行工作。
  - Vi 冲突示例:
    - 写后读: V0 <- V1 + V2 然后 V3 <- V0 * V4 (V0 冲突)
  - 功能部件冲突示例: (两者都需要乘法器)
    - V3 <- V1 * V2
    - V5 <- V4 * V6
指令类型: 向量-向量，向量-标量，向量-存储器 (加载/存储)。

2.1.2. 提高向量处理器性能的方法

设置多个功能部件，并使它们并行工作。
- CRAY-1 有4组共12个单功能流水线部件（向量、浮点、标量、地址）。
采用向量链接 (Chaining) 技术。
- 特点: 对于有先写后读关系（一条指令的结果是下一条指令的操作数）的两条指令，在功能部件和源向量均无冲突的情况下，可以将前一条指令的结果在其产生后立即送往后一条指令的功能部件，而不必等待前一条指令全部执行完毕。
- 本质: 将流水线思想引入到向量执行过程中。
- **📝 考题示例：向量链接计算” 问题描述: 计算 D = A * (B + C)。向量长度 N <= 64。B 在 V0，C 在 V1。指令序列:
  1. V3 <- memory (将 A 加载到 V3)
  2. V2 <- V0 + V1 (B + C 存入 V2)
  3. V4 <- V2 * V3 ( (B+C) * A 存入 V4) 假设: 向量寄存器到功能部件、存储器到功能部件取数各需 1 拍。浮点加法需 6 拍，浮点乘法需 7 拍。
  - 串行执行: 时间 = (1 + 访存延迟 + N-1) + (1 + 加法延迟 + N-1) + (1 + 乘法延迟 + N-1) (假设访存延迟与功能部件延迟相似，例如 6 拍) 时间 = (1+6+N-1) + (1+6+N-1) + (1+7+N-1) = 3N + 22 (根据幻灯片数据)
  - V3 和 V2 并行，然后执行 V4: 时间 = max{(1+6+N-1), (1+6+N-1)} + (1+7+N-1) = 2N + 15 (根据幻灯片数据)
  - 向量链接 (V2 -> V4): V3 和 V2 可以并行。V4 在 V2 产生结果后即可开始使用。 V4 的启动受 V2 延迟的影响。在 V3 的最后一个元素准备好并且 V2 的最后一个元素准备好进入 V4 的功能部件后，链接操作经过 (N-1) 拍完成。更简单地理解：最长的 V3 或 V2 的时间 + V4 功能部件的延迟 + V4 额外的 (N-1) 个元素处理时间。时间 = max7 + (1+7+N-1) = N + 16 (根据幻灯片数据，简化为“第一个结果输出时间 + (N-1)个元素时间”) 关键在于 V4 可以在 V2 产生第一个结果且 V3 就绪后开始处理。
分段向量 (Vector Strip Mining，向量分条)。
- 若向量长度大于向量寄存器长度，则必须将长向量分成固定长度的段（条带），每段长度为最大向量寄存器长度，然后循环处理。对程序员透明。
采用多处理机系统。
- CRAY-2: 包含4个向量处理机。
- CRAY Y-MP, C90: 最多可包含16个向量处理机。

2.1.3. RV64V (RISC-V 向量扩展)

大致基于 CRAY-1。
32 个 62 位向量寄存器。
向量功能部件（全流水线）。
向量加载/存储部件。
示例：DAXPY (a*X + Y) 在 RV64V 中的实现远比标量 RISC-V 简洁。
多通道 (Multiple Lanes): 允许每个时钟周期处理多个元素，通过设置多个并行的硬件通道。寄存器 A 的元素 n 与寄存器 B 的元素 n 进行操作。

2.2. 阵列处理器 (Array Processors / 并行处理机)

N 个处理单元 (PE) PE_0 到 PE_\{N-1\}。
以特定方式互连形成阵列。
在单一控制单元的控制下，所有 PE 对其分配的数据并行完成同一条指令所规定的操作。
示例: ILLIAC IV (8x8 阵列的 PE，每个 PE 有自己的存储器 PEM)。

2.2.1. 阵列处理器的基本结构

分布存储器式 (Distributed Memory): 每个 PE 有其自己的私有存储模块 (PEM)。PE 之间通过互连网络 (ICN) 通信。(主流)
- [PEM_i] <-> [PE_i] <-> ICN
集中共享存储器式 (Centralized Shared Memory): PE 通过 ICN 访问一组共享存储模块 (MM)。
- [PE_i] <-> ICN <-> [MM_k]
- 与分布存储器式的区别: 存储器的分布方式不同，互连网络的作用不同 (PE-MM vs PE-PE)。

2.2.2. 阵列处理器的互连网络 (ICNs)

挑战: n 个 PE 之间的直接连接需要 C(n,2) = n(n-1)/2 对连接。难以实现，故采用间接路径。
通信体系结构是核心:
- 底层的互连网络。
- 由高级语言、编译器、操作系统等提供支持。
ICN 定义: 由交换单元按照一定的拓扑结构和控制方式构成的网络，用以实现计算机系统内部多个处理器或多个功能部件之间的互连。
ICN 组成: CPU、存储器、接口 (如网卡)、链路 (电缆、光纤)、交换节点 (信息交换和控制站，具备数据缓冲和路径选择功能)。
ICN 设计关键点:
- 拓扑结构 (Topology): 静态或动态。
- 定时方式 (Timing Mode): 同步 (统一时钟，如 SIMD 阵列) 或异步 (无统一时钟)。
- 交换方式 (Exchange Method): 电路交换或分组交换。
- 控制策略 (Control Strategy): 集中式 (全局控制器) 或分布式 (无全局控制器)。

静态网络 (Static Networks): 连接路径固定，在程序执行期间不变。

!!! question “潜在考题：静态网络特性” “描述一个包含 N 个节点的 [线性/环形/二叉树/星型/网格/二维环面/超立方体/带环立方体] 网络的特性（规模、度、直径、宽度、对称性、链路数）。” (具体公式请参考幻灯片中的总结表格)。

拓扑结构	规模	度	直径	宽度	对称性	链路数
线性	N	2	N-1	1	否	N-1
环形	N	2	floor(N/2)	1(单)/2(双)	是	N
二叉树	N	3	2(floor(logN)-1)	1	否	N-1
星型	N	N-1	2	N/2 ? (1)	否	N-1
网格 (r*r)	N=r^2	4	2(r-1)	r (sqrt(N))	否	2(N-sqrt(N)) 或 2N-2r
二维环面(r*r)	N=r^2	4	2*floor(r/2)	2*sqrt(N) ? (r)	是	2N
超立方体	N=2^n	n	n	N/2 ? (n/2)	是	nN/2
带环立方体	N=k*2^k	3	2k-1+floor(k/2)	N/2^k ?	是	3N/2
(注意: 幻灯片中的宽度值可能需要根据具体定义来理解)

树形阵列的扩展: 带环树形，胖树 (Binary fat tree，越往上链路越宽)。
超立方体 (n-cube / Hypercube): N = 2^n 个节点，分布在 n 维空间。直径=n，度=n。

动态网络 (Dynamic Networks): 由交换开关组成，可以动态改变连接。(总线、交叉开关、多级互连网络)。
- 总线 (Bus): 一组导线/插座。一次只能有一对源和目的进行数据传输。需要仲裁。CPU 数量多时竞争严重 (通常 <=32)。
  - 线性阵列 vs. 总线: 线性阵列允许不同部分并发使用；总线是分时复用。
- 交叉开关 (Crosspoint Switches / Crossbar):
  - 开关的网格结构，允许任何输入连接到任何空闲的输出。
  - N x M 需要 N*M 个开关。对于 N x N，需要 N^2 个开关。
  - 无阻塞 (如果输出空闲)。
- 多级互连网络 (MINs - Multi-stage Interconnection Networks):
  - 目标: 以比交叉开关更少的开关数量（少于 N^2）实现良好的连通性。
  - 交换单元 (Switch Unit): 基本构建模块，例如 2x2 交换单元。
    - 一个 m x m 交换单元有 m^m 种合法状态和 m! 种交换连接。
    - 2x2 交换单元: 2 种合法状态，2 种交换连接 (直送 Straight, 交换 Exchange)。
  - 实现连接:
    - 循环互连网络: 单级网络多次循环使用。
    - 多级互连网络: 多个单级互连网络串联。
  - 交换单元功能 (2x2):
    - 双功能: 直送, 交换。
    - 四功能: 直送, 交换, 上播 (Upper Broadcast), 下播 (Lower Broadcast)。
  - MINs 的拓扑结构:
    - 单级立方体互连网络 (Cube Single-Stage ICN):
      - N 个输入/输出用 n 位二进制码编码 (n = log2N)。
      - n 种不同的互连函数: Cube_i(P_\{n-1\}...P_i...P_0) = P_\{n-1\}...~P_i...P_0 (反转第 i 位)。
      - 一个三维立方体最多通过 3 次传送即可实现任意两个 PE 间的数据传送。
      - 超立方体互连网络: 维数 n > 3。最多经过 n 次传送即可实现任意两个 PE 间的数据传送。
    - 单级 PM2I 互连网络 (Plus Minus 2^i):
      - 互连函数 (共 2n 种): PM2_{+i}(j) = (j + 2^i) mod N 和 PM2_{-i}(j) = (j - 2^i) mod N。
      - ILLIAC IV 阵列处理机使用 PM2_\{±0\} 和 PM2_\{±n/2\} (实际是 PM2_\{±1\} 和 PM2_\{±sqrt(N)\} 来实现其二维网格结构)。
    - 单级混洗交换网络 (Shuffle Exchange Network):
      - 两部分: 混洗 (Shuffle) + 交换 (Exchange)。
      - 混洗函数 (n 维): shuffle(P_\{n-1\}P_\{n-2\}...P_1P_0) = P_\{n-2\}...P_1P_0P_\{n-1\} (循环左移)。
      - 对于 N=2^n 个 PE，经过 n 次混洗后，所有 PE 恢复到初始排列顺序。
      - 最大距离: n 次交换和 n-1 次混洗。
    - 多级立方体互连网络 (Multi-stage Cube):
      - n = log2N 级。每级使用 N/2 个双功能交换单元。
      - 第 i 级实现 Cube_i 功能（或其排列）。
      - 级间连接遵循特定模式。
      - **📝 考题示例：三级立方体网络 (N=8)” 给定输入，根据控制信号 (K2K1K0，其中 K_i=0 表示直送，K_i=1 表示在实现 Cube_i 的第 i 级交换) 追踪到输出的路径。
        N=8 示例: 控制信号 000 为恒等变换。001 实现 Cube0。110 实现 Cube2 + Cube1。
      - 类型: 交换网络 (如 STARAN 的 Flip 网络), 间接二进制 n-cube 网络。
    - 多级混洗交换网络 (Omega Network):
      - n = log2N 级。
      - 每级由一次混洗互连后接 N/2 个四功能交换单元构成。
      - 控制方式: 单元控制 (每个交换单元独立设置)。
      - !!! tip “Omega 网络 vs. n-cube 多级网络对比”
        级号表示: Omega 从输入到输出为 n-1..0，n-cube 为 0..n-1。
        交换单元功能: Omega 用四功能，n-cube 用双功能。
        广播: Omega 可实现一对多广播，n-cube (用双功能开关时) 不能。
        若 Omega 网络的交换单元限制只能用“直送”和“交换”功能，则它变成 n-cube 网络的逆网络。
    - Benes 网络: 一种多级全排列网络的例子。可以由两个背靠背的 Omega 网络（或 n-cube 网络及其逆网络）构成。共 2n-1 级。无阻塞。

✅ SIMD 的优点

能有效利用显著的数据级并行性（矩阵计算、媒体处理）。
比 MIMD 更节能（每个数据操作只需取一次指令）。
允许程序员（通常）继续顺序思考，向量化由编译器或显式向量指令处理。

2.3. 补充1：GPU 中的数据级并行 (DLP in GPUs)

基本思想:
- 异构执行模型: CPU 是主机 (host)，GPU 是设备 (device)。
- 为 GPU 开发类 C 的编程语言 (例如 NVIDIA 的 CUDA, OpenCL)。
- 将 GPU 并行性统一为 CUDA 线程 (NVIDIA)。
- 编程模型: SIMT (Single Instruction, Multiple Thread - 单指令多线程)。
CUDA (Compute Unified Device Architecture - 计算统一设备架构):
- GPU 本质上是多线程 SIMD 处理器。一个线程块 (block of threads) 在一个 SIMD 处理器上执行。
层次结构: 网格 (Grid) -> 线程块 (Thread Blocks) -> 线程 (Threads):
- 一个线程与每个数据元素相关联。
- 线程被组织成线程块。块内线程可以协作（共享存储器、同步）。
- 线程块被组织成一个网格。
GPU 存储结构:
- GPU 显存 (全局存储器 Global Memory): 所有网格共享。容量大，但延迟高。
- 局部存储器 (每个线程块的共享存储器 Shared Memory per Block): 线程块内所有线程共享。延迟低。
- 私有存储器 (每个线程的寄存器 Registers, L1 cache per thread): 单个 CUDA 线程私有。延迟最低。
GPU 组织结构 (例如 Pascal GPU):
- 指令缓存 -> Warp 调度器 -> 指令寄存器
- 多个 SIMD 线程调度器，每个控制多个 SIMD 通道 (线程处理器)。
- 每个 SIMD 通道有 ALU, DP/SP 单元, 特殊功能单元 (SFU)。
- 寄存器堆, L1 缓存, 纹理缓存。
- 局部存储器 (例如每个 SM 64KB)。
- 连接到全局存储器。
!!! comparison “NVIDIA GPU 与向量机对比”
- 相似之处: 适用于数据级并行问题，支持离散/聚合传输 (Scatter-gather)，屏蔽寄存器 (Mask registers)，大容量寄存器堆。
- 不同之处 (GPU):
  - 无标量处理器 (标量部分依赖 CPU)。
  - 使用多线程隐藏存储延迟。
  - 拥有许多功能单元 (相对于向量处理器中少量深度流水线化的单元)。

2.4. 补充2：循环级并行 (LLP - Loop-Level Parallelism)

程序中的循环是许多并行类型的源泉。
发现和操作循环级并行对于利用 DLP、TLP 以及更激进的静态 ILP 方法至关重要。
关注点: 判断后续迭代中的数据访问是否依赖于先前迭代中产生的数据值（循环携带相关 - loop-carried dependence）。

**📝 LLP 示例与练习”

示例 1 (无循环携带相关): c for (i=999; i>=0; i=i-1) x[i] = x[i] + s; // 可并行化
示例 2 (有循环携带相关): c for (i=0; i<100; i=i+1) { A[i+1] = A[i] + C[i]; /* S1: A[i+1] 依赖于前一次迭代的 A[i] */ B[i+1] = B[i] + A[i+1]; /* S2: B[i+1] 依赖于前一次迭代的 B[i]; B[i+1] 依赖于同一次迭代中 S1 的 A[i+1] */ } // 由于 A[i] 和 B[i] 的存在，不能直接并行化
示例 3 (可通过变换并行化): c for (i=0; i<100; i=i+1) { A[i] = A[i] + B[i]; /* S1 */ B[i+1] = C[i] + D[i]; /* S2 */ } /* S1 使用的 B[i] 可能是*前一次*迭代中 S2 写入的 B[i+1] (即 B[i])。如果展开或仔细使用 S2 的值，这种相关性在*单次迭代内*不是循环的，因此可以并行。幻灯片展示了通过剥离首次/末次迭代并重排来进行变换： A[0] = A[0] + B[0]; for (i=0; i<99; i=i+1) { B[i+1] = C[i] + D[i]; A[i+1] = A[i+1] + B[i+1]; // A[i+1] 现在使用新的 B[i+1] } B[100] = C[99] + D[99]; */ // 这种变换比较复杂，关键在于 S1 使用的是*前一次*迭代 S2 的 B[i]。循环是可并行的。
练习题 (识别相关性): c for (i=0; i<100; i=i+1) { Y[i] = X[i]/c; /* S1 */ X[i] = X[i] +c; /* S2: X[i] 使用 S1 读取的 X[i]，写入新的 X[i] */ Z[i] = Y[i] +c; /* S3: Z[i] 使用 S1 的 Y[i] */ Y[i] = c - Y[i]; /* S4: Y[i] 使用 S1 的 Y[i]，写入新的 Y[i] */ } // 相关性: // S1 -> S3 (Y[i]) - 真相关 (RAW) // S1 -> S4 (Y[i]) - 真相关 (RAW) // S1 读 X[i], S2 写 X[i] - 如果 S2 在 S1 之前，则为反相关 (WAR)。(此处不是) // S2 读 X[i], S1 读 X[i] - 无相关。 // S3 用 Y[i], S4 写 Y[i] - 如果 S4 在 S3 之前，则为反相关 (WAR)。(此处不是) // S1 写 Y[i], S4 写 Y[i] - 输出相关 (WAW) // *对于不同的 `i`，没有循环携带相关。* 循环是可并行的。 // 变换以消除迭代内的 WAW 和 WAR (如果重排): // T[i] = X[i]/c; // P[i] = X[i] +c; // Z[i] = T[i] +c; // Y[i] = c - T[i]; // X[i] = P[i]; // 如果 X 需要为下一次迭代保留

3. MIMD: 多指令流多数据流

多个处理器执行不同的指令流，操作不同的数据流。

历史背景: 单核速度提升的收益递减定律（1960年代中期）。摩尔定律推动了多核发展。
TLP (Thread-Level Parallelism - 线程级并行): 由软件/程序员识别。线程包含许多指令。
- TLP 意味着存在多个程序计数器 (PC)。
- TLP 主要通过 MIMD 来利用。

3.1. MIMD 体系结构类型

多处理机系统 (共享存储器):
- 所有处理器共享一个唯一的地址空间。
- 共享地址空间可以是物理共享的，也可以是带有硬件/软件支持的分布式存储器。
多计算机系统 (消息传递):
- 每个处理器拥有自己的私有/本地存储器。
- 处理器通过发送消息进行通信。
- NORMA (No-Remote Memory Access - 无远程存储访问): 存储器是本地的；远程数据通过消息访问。

3.1.1. MIMD 多处理机系统中的存储访问模型

UMA (Uniform Memory Access - 均匀存储访问):
- 物理存储器被所有处理器均匀共享。任何处理器访问任何存储单元的时间相同。
- 处理器可以有私有 Cache/存储器。
- ICN 可以是总线、交叉开关或多级网络。
- 也称为 SMP (Symmetric Multi-Processors - 对称多处理器) 或集中式共享存储多处理机。
NUMA (Non-Uniform Memory Access - 非均匀存储访问):
- 访问时间取决于存储单元相对于处理器的位置。访问本地存储器比远程存储器快。
- 所有 CPU 共享一个（逻辑上的）地址空间。
- 使用 LOAD/STORE 指令访问远程存储器。
- NC-NUMA (Non-Cache Coherent NUMA - 非 Cache 一致性 NUMA): 无 Cache，或 Cache 不保持一致。
- CC-NUMA (Cache Coherent NUMA - Cache 一致性 NUMA): Cache 保持一致，通常使用基于目录的协议。
- 也称为 DSP (Distributed Shared-Memory Multiprocessor - 分布式共享存储多处理机)。
COMA (Cache-Only Memory Access - 纯 Cache 存储访问):
- NUMA 的一种特例。处理器节点中没有主存层次结构；所有 Cache 构成一个统一的地址空间。
- 数据迁移到使用它的 Cache 中。使用分布式 Cache 目录。

3.1.2. MIMD 多计算机系统的进一步划分

MPP (Massively Parallel Processors - 大规模并行处理机):
- 成百上千个处理器。
- 用于科学计算、工程仿真、商业/网络应用。
- 开发难度大，价格高昂。
- 特点: 标准商用 CPU，高性能专用 ICN (低延迟、高带宽)，强大的 I/O 能力，特殊的容错处理能力。
COW (Cluster of Workstations - 工作站机群):
- 大量 PC/工作站通过商用网络（以太网、Myrinet、ATM）连接。
- 使用市售组件组装 -> 良好的性价比。
- 架构: 微型计算机带网卡，通过高速互联网/网络连接，运行集群系统中间件（单一系统映像、高可用性软件），支持串行和并行应用。

3.2. 并行处理的挑战

程序中有限的并行性。
相对较高的通信成本。
- 两者都可以用阿姆达尔定律 (Amdahl’s Law) 来解释。

**📝 阿姆达尔定律计算”

公式: 总加速比 = 1 / ((1 - 可改进部分比例) + (可改进部分比例 / 该部分加速比))
问题1: 用 100 个处理器实现 80 倍的加速比。原始计算中串行部分的比例可以是多少？令 F_parallel 为可并行化部分（可改进部分）。Speedup_enhanced (该部分加速比) = 100。Speedup_overall (总加速比) = 80。 80 = 1 / ((1 - F_parallel) + (F_parallel / 100)) (1 - F_parallel) + 0.01 * F_parallel = 1/80 = 0.0125 1 - 0.99 * F_parallel = 0.0125 0.99 * F_parallel = 1 - 0.0125 = 0.9875 F_parallel = 0.9875 / 0.99 = 0.99747 串行部分比例 = 1 - F_parallel = 1 - 0.99747 = 0.00253 即 0.253%。 (幻灯片计算略有不同，设串行部分为 Fraction_sequential：(1 - Fraction_sequential) / 100 + Fraction_sequential，得到 F_seq = 0.0025 或 0.25%)

*问题2: 100 处理器系统。95% 的时间使用全部 100 个处理器 (F_100 = 0.95)。剩余 5% 的时间或者使用 50 个处理器 (F_50) 或者 1 个处理器 (串行, F_1)。目标加速比 = 80。剩余 5% 的时间中，必须有多少使用 50 个处理器？ 加速比 = 1 / ( (F_100 / S_100) + (F_50 / S_50) + (F_1 / S_1) ) F_1 = 0.05 - F_50。S_100=100, S_50=50, S_1=1。 80 = 1 / ( (0.95 / 100) + (F_50 / 50) + ((0.05 - F_50) / 1) ) 1/80 = 0.0095 + 0.02*F_50 + 0.05 - F_50 0.0125 = 0.0595 - 0.98*F_50 0.98*F_50 = 0.0595 - 0.0125 = 0.047 F_50 = 0.047 / 0.98 = 0.047959 即 4.8%。这意味着 F_1 = 0.05 - 0.048 = 0.002 即 0.2% 可以是串行的。 (幻灯片计算给出 F_50 = 0.048)

*问题3: 32 处理器系统，远程存储访问延迟 100ns。处理器时钟 4GHz (0.25ns/周期)。基础 CPI (全命中) = 0.5。0.2% 的指令涉及远程通信。如果没有通信，多处理机会快多少？远程请求代价 = 100ns / 0.25ns/周期 = 400 周期。 CPI_带通信 = 基础_CPI + (远程请求率 * 远程请求代价) CPI_带通信 = 0.5 + (0.002 * 400) = 0.5 + 0.8 = 1.3 CPI_无通信 = 基础_CPI = 0.5 无通信时的加速比 = CPI_带通信 / CPI_无通信 = 1.3 / 0.5 = 2.6 如果没有通信，多处理机速度是原来的 2.6 倍。

4. 补充3：共享存储系统中的 Cache 一致性

挑战：多个带有本地 Cache 的处理器可能持有同一内存块的副本，如果一个处理器更新其副本，可能导致不一致。

迁移 (Migration): 数据项可以被移动到本地 Cache 并在那里使用。迁移减少了访问远程分配的数据项的延迟和共享存储器的带宽需求。
复制 (Replication): 当共享数据被同时读取时，Cache 在本地 Cache 中制作数据项的副本。复制减少了访问延迟和对读共享数据项的争用。
存储一致性 (Memory Consistency): 定义处理器看到的存储操作的顺序。
- “一个写操作的值何时能被读操作返回。”
- “如果处理器 P 先写 A 后写 B，任何看到 B 新值的处理器 P’ 也必须看到 A 的新值。”
- 需要一个存储一致性模型 (Memory Consistency Model)。
Cache 一致性 (Cache Coherence): 确保任何处理器的所有读操作都返回最近写入的值。
- “任何两个处理器对同一位置的写操作，被所有处理器以相同的顺序观察到。”
- 确保 Cache 不会通过分析加载和存储的结果使程序员能够确定系统是否有以及在哪里有 Cache，即 Cache 不会引入新的或不同的功能行为。
- 需要一个Cache 一致性协议 (Cache Coherence Protocol)。

4.1. Cache 一致性协议

监听一致性协议 (Snoopy Coherence Protocols / 总线嗅探协议，用于基于总线的 UMA):
- 所有处理器都“监听”（监视）总线上的存储事务。
- 当一个处理器修改其私有 Cache 中的数据时，它会在总线上广播此信息（例如，无效化或更新其他副本）。
- 写直达 Cache 一致性协议 (通用):
  - 本地读缺失 (Read Miss): 从内存访问数据。
  - 本地读命中 (Read Hit): 使用本地 Cache 数据。
  - 本地写缺失 (Write Miss): 修改内存中的数据（并可能在 Cache 中分配空间 - 写分配 write-allocate）。
  - 本地写命中 (Write Hit): 修改 Cache 和内存。远程 Cache 可能无效化或更新。
  - 远程写命中策略: 更新策略 (Update Strategy) 或 无效策略 (Invalidate Strategy)。
  - 写缺失策略: 写分配 (Write-allocate) 或 不写分配 (No-write-allocate)。
- 监听协议类型:
  - 写无效协议 (Write-Invalidate Protocol): 写操作时，使其他副本无效。（更常见）
  - 写更新/写广播协议 (Write-Update/Broadcast Protocol): 写操作时，更新所有其他 Cache 中的副本。（总线流量较高）
基于目录的协议 (Directory-Based Protocols，用于 NUMA):
- 目录记录系统中哪些处理器拥有某些存储块在 Cache 中的副本。
- 当对共享块进行写操作时，会以“点对点”方式（通过目录）向那些拥有该块副本的处理器发送无效信号，从而使所有其他副本无效。

4.2. MSI 协议 (一种用于写回式 Cache 的写无效监听协议)

每个 Cache 块处于以下三种状态之一:
- M (Modified - 已修改): 该块已在此私有 Cache 中被更新（脏数据）。此 Cache 拥有该块的唯一有效副本。意味着独占所有权。
- S (Shared - 共享): 该块存在于此 Cache 中，也可能存在于其他 Cache 中。它是干净的（与内存一致）。
- I (Invalid - 无效): 该块在此 Cache 中无效。
状态转换 (简化版 - 完整细节请参见幻灯片图示):
- CPU 读命中: 状态不变 (M 或 S)。
- CPU 读缺失:
  - 若另一 Cache 中该块为 M 态: 该 Cache 将块写回内存，其状态变为 S。请求 Cache 从内存加载，状态变为 S。
  - 若其他 Cache 中该块为 S 态 (或无 Cache 持有): 请求 Cache 从内存加载，状态变为 S。
- CPU 写命中:
  - 若为 M 态: 本地写入。状态保持 M。
  - 若为 S 态: 本地写入。广播无效化。状态变为 M。
- CPU 写缺失 (请求独占的读 - Read-For-Ownership / RFO):
  - 广播无效化。若另一 Cache 中该块为 M 态，则其写回。
  - 加载块。本地写入。状态变为 M。
- 总线读请求 (被其他 Cache 监听到):
  - 若本地块为 M 态: 将块写回内存。本地状态变为 S。提供数据。
  - 若本地块为 S 态: 无操作（或按约定提供数据）。
- 总线无效化请求 (被其他 Cache 监听到):
  - 若本地块为 S 或 M 态: 本地状态变为 I。（若为 M 态，必须先写回，或中止操作让请求方在原 M 态持有者写回后从内存获取）。

**📝 MSI 协议追踪考题示例” 设置: 共享存储多处理器系统。每个核心有一个 4 路组相联（幻灯片为4行直接映射）写回式 Cache。使用基本的写无效监听协议 (MSI)。 初始状态: (提供 Core 0, Core 1, Core 2 的 Cache 和内存的表格) 操作格式: C# (核心号), R/W (读/写), <地址 Axxx>, <值 V (用于写)> Cx.y 表示核心 x 的 Cache 行 y。 Memory A100, 0000 -> 0100 表示内存位置 A100 的值从 0000 更新为 0100。

幻灯片示例追踪: 初始状态: (幻灯片快照) Core 0: [0 I A100 0000], [1 S A104 0104], [2 M A108 0208], [3 I A10C 0000] (假设A10C映射到行0，A100也是行0) Core 1: [0 S A100 0000], [1 S A104 0104], [2 I A108 0000], [3 S A11C 011C] Core 2: [0 I A000 0000], [1 S A104 0104], [2 I A108 0000], [3 M A10C 020C] 内存: A100=0000, A104=0104, A108=MEM_VAL_A108 (C0 M态前), A10C=MEM_VAL_A10C (C2 M态前), A11C=011C。(假设内存已被M态更新或是初始值)。

操作 (1): C0, R, A10C (C0 读 A10C)

C0: A10C 读缺失 (假设 A10C 映射到行 0，当前是 I 态)。
C0 发出对 A10C 的总线读请求。
C2 监听到: 其 Cache 中有 A10C 且为 M 态 (行 3)。
- C2 将 A10C (值为 020C) 写回内存。Memory[A10C] 变为 020C。
- C2 将其 A10C 的状态从 M 变为 S。C2: [3 S A10C 020C]。
- C2 向 C0 提供数据 020C。
C0: 加载 A10C 数据 020C。状态变为 S。C0: [0 S A10C 020C] (假设A10C映射到行0)。

操作 (2): C1, W, A104, 0204 (C1 写 A104，值为 0204)

C1: A104 写命中 (行 1 为 S 态)。
C1 发出对 A104 的总线无效化请求。
C0 监听到: 其 Cache 中有 A104 且为 S 态 (行 1)。状态变为 I。C0: [1 I A104 ----]。
C2 监听到: 其 Cache 中有 A104 且为 S 态 (行 1)。状态变为 I。C2: [1 I A104 ----]。
C1: 将值 0204 写入其 A104 所在的 Cache 行。状态变为 M。C1: [1 M A104 0204]。 (由于是写回式，Memory[A104] 仍然是 0104)。

操作 (3): C0, W, A118, 0308 (C0 写 A118，值为 0308)

C0: A118 写缺失。(假设 A118 映射到一个可用行，或替换某行)。
C0 发出对 A118 的总线“请求独占的读”(RFO) 或写缺失请求。这表示写意图并请求使其他副本无效。
C1 监听到: 没有 A118。无操作。
C2 监听到: 没有 A118。无操作。
内存提供 A118 的数据 (例如，幻灯片示例中的值 0118)。
C0: 加载 A118 (值为 0118)，将 0308 写入。状态变为 M。C0: [映射到A118的行号 M A118 0308]。

5. 课程整体回顾与知识图谱 (简要)

最后的幻灯片将 DLP 和 TLP 置于计算机系统的更广阔背景下：

计算机系统基础 -> ILP -> 存储层次 (Cache, 主存) -> 文件系统 -> DLP & TLP。
SysIII-Lab 主题: 动态分支预测，带 Cache 的流水线 CPU 设计实现，RV64 虚拟内存管理，RV64 用户模式，RV64 缺页异常处理以及 fork 机制，硬件支持的缺页异常和 MMU，Xpart—RV64 软硬件贯通综合实验。
知识图谱:
- 编程语言 -> 编译器/虚拟机 -> 运行时系统 -> 操作系统/容器 -> CPU/GPU/FPGA/量子计算设备。
- 状态机模型: 程序，指令集，处理器。
- 体系结构优化方法: 缓存，并行，流水线，预测，专用乘除法器。
- 软硬件协同: 应用序，运行时环境，操作系统，指令集，微结构。
- 系统层次: 代码 -> 系统软件 (编译器, OS) -> 体系结构 (ISA) -> 系统硬件 (存储器, CPU, I/O, 逻辑电路) -> 门级电路。
- 高级 CPU 特性如 BPU (分支预测单元), MMU/TLB, ROB (重排序缓冲), RAT (寄存器别名表), CSR (控制状态寄存器), Forwarding Unit (前递单元) 等都建立在这些基础之上。

这个结构应该有助于复习这些材料。“潜在考题”部分是需要重点关注的领域。

Thanks for reading!

计算机系统 III 硬件第四章：DLP与TLP

周二 9月 30 2025 Course

8604 字 · 34 分钟

System III Course Notes 数据级并行 DLP 线程级并行 TLP SIMD MIMD 课程笔记

计算机系统 III 硬件第四章：DLP与TLP

第四章：DLP（数据级并行）与 TLP（线程级并行）

1. Flynn 计算机体系结构分类法

2. SIMD: 单指令流多数据流

2.1. 向量处理器 (Vector Processors)

2.1.1. CRAY-1 向量处理器 (寄存器-寄存器结构的示例)

2.1.2. 提高向量处理器性能的方法

2.1.3. RV64V (RISC-V 向量扩展)

2.2. 阵列处理器 (Array Processors / 并行处理机)

2.2.1. 阵列处理器的基本结构

2.2.2. 阵列处理器的互连网络 (ICNs)

2.3. 补充1：GPU 中的数据级并行 (DLP in GPUs)

2.4. 补充2：循环级并行 (LLP - Loop-Level Parallelism)

3. MIMD: 多指令流多数据流

3.1. MIMD 体系结构类型

3.1.1. MIMD 多处理机系统中的存储访问模型

3.1.2. MIMD 多计算机系统的进一步划分

3.2. 并行处理的挑战

4. 补充3：共享存储系统中的 Cache 一致性

4.1. Cache 一致性协议

4.2. MSI 协议 (一种用于写回式 Cache 的写无效监听协议)

5. 课程整体回顾与知识图谱 (简要)

计算机系统 III 硬件第四章：DLP与TLP

His Smile