====== 第十三章 多处理器系统 ======

===== 本章导学 =====

多处理器系统是现代计算机体系结构的核心组成部分，它通过并行处理技术提升系统性能。本章将深入探讨多处理器系统的基本概念、互连网络、缓存一致性、同步机制以及多核技术等关键内容，为理解现代高性能计算系统奠定基础。

===== 13.1 多处理器系统概述 =====

==== 13.1.1 并行计算的基本概念 ====

**并行计算(Parallel Computing)**是指同时使用多种计算资源解决计算问题的过程。其基本思想是将复杂任务分解为多个可同时执行的子任务，通过并行执行来缩短总体执行时间。

并行计算的主要形式包括：

  * **位级并行(Bit-level Parallelism)**：增加处理器字长，一次处理更多数据位
  * **指令级并行(Instruction-level Parallelism, ILP)**：同时执行多条指令
  * **数据级并行(Data-level Parallelism, DLP)**：对大量数据执行相同操作（如SIMD）
  * **任务级并行(Task-level Parallelism)**：独立任务并发执行
  * **线程级并行(Thread-level Parallelism, TLP)**：多线程同时执行

**加速比(Speedup)**是衡量并行计算效果的重要指标，定义为：

$$S = \frac{T_1}{T_p}$$

其中，$T_1$为串行执行时间，$T_p$为使用$p$个处理器的并行执行时间。

根据**阿姆达尔定律(Amdahl's Law)**，加速比上限为：

$$S_{max} = \frac{1}{(1-f) + \frac{f}{p}}$$

其中，$f$为可并行化的比例，$(1-f)$为必须串行执行的比例。

**例题13.1**：某程序90%的代码可以并行化，若使用100个处理器，理论最大加速比是多少？若要达到50倍加速，至少需要多少处理器？

**解答**：

(1) 根据阿姆达尔定律：
$$S = \frac{1}{(1-0.9) + \frac{0.9}{100}} = \frac{1}{0.1 + 0.009} = \frac{1}{0.109} \approx 9.17$$

(2) 设需要$p$个处理器达到50倍加速：
$$50 = \frac{1}{0.1 + \frac{0.9}{p}}$$
$$0.1 + \frac{0.9}{p} = 0.02$$
$$\frac{0.9}{p} = -0.08$$

此方程无解，说明当串行比例为10%时，理论最大加速比为$\frac{1}{0.1} = 10$，无法达到50倍加速。

==== 13.1.2 多处理器系统分类 ====

根据**弗林分类法(Flynn's Taxonomy)**，计算机系统可分为四类：

  * **SISD（单指令流单数据流）**：传统串行计算机
  * **SIMD（单指令流多数据流）**：向量处理器、GPU
  * **MISD（多指令流单数据流）**：容错系统、脉动阵列
  * **MIMD（多指令流多数据流）**：多处理器、多计算机系统

现代多处理器系统主要基于**MIMD**架构，可进一步细分为：

**按内存组织方式分类**：

  * **共享内存多处理器(Shared Memory Multiprocessor, SMP)**：所有处理器共享统一地址空间
  * **分布式内存多处理器(Distributed Memory Multiprocessor)**：每个处理器拥有私有内存，通过消息传递通信

**按耦合程度分类**：

  * **紧耦合系统(Tightly Coupled)**：处理器通过高速总线或互连网络紧密连接
  * **松耦合系统(Loosely Coupled)**：处理器相对独立，通过标准网络连接

===== 13.2 共享内存多处理器系统 =====

==== 13.2.1 UMA与NUMA架构 ====

**均匀内存访问(UMA, Uniform Memory Access)**架构中，所有处理器访问任何存储单元的时间相同。典型的SMP系统采用UMA架构，具有以下特点：

  * 所有处理器对称地共享内存和I/O资源
  * 每个处理器有独立的私有缓存(L1/L2)
  * 通过系统总线或交叉开关连接主存
  * 操作系统将任务分配给任意处理器

UMA的优势在于编程简单，所有处理器看到一致的内存视图。但当处理器数量增加时，总线带宽成为瓶颈。

**非均匀内存访问(NUMA, Non-Uniform Memory Access)**架构中，处理器访问本地内存快于访问远程内存。NUMA系统的特点：

  * 内存物理分布在各个节点上
  * 每个节点包含处理器、缓存和本地内存
  * 通过高速互连网络访问远程节点内存
  * 保持全局地址空间，任何处理器可访问任何内存位置

**CC-NUMA（缓存一致性NUMA）**通过硬件机制维护缓存一致性，使NUMA系统对程序员透明。

==== 13.2.2 集中式与分布式共享内存 ====

**集中式共享内存**将所有物理内存集中在单一位置，通过高速互连供所有处理器访问。适用于处理器数量较少的系统（通常<32个）。

**分布式共享内存(DSM, Distributed Shared Memory)**将内存分布在多个节点上，但向程序员呈现统一的共享地址空间。DSM的实现方式：

  * **硬件实现**：NUMA架构、缓存一致性协议
  * **软件实现**：操作系统或运行时系统管理页面迁移和复制
  * **混合实现**：软硬件协同的分布式共享内存系统

===== 13.3 互连网络 =====

==== 13.3.1 互连网络的基本概念 ====

互连网络是多处理器系统的核心组件，负责处理器、内存和I/O设备之间的数据交换。关键性能指标包括：

  * **带宽(Bandwidth)**：单位时间内传输的数据量，通常用MB/s或GB/s表示
  * **延迟(Latency)**：从发送请求到接收响应的时间
  * **直径(Diameter)**：网络中任意两点间最长最短路径的跳数
  * **对分带宽(Bisection Bandwidth)**：将对分网络所需的最小链路数
  * **成本(Cost)**：链路和开关的数量

**静态互连网络**适用于直接连接处理器的网络，拓扑结构固定：

**动态互连网络**使用开关元件动态建立连接路径，适用于共享资源的访问。

==== 13.3.2 静态互连网络拓扑 ====

**线性阵列(Linear Array)**：$N$个节点排成一行，每个节点与相邻节点连接。直径为$N-1$，对分带宽为1。

**环网(Ring)**：线性阵列首尾相连形成闭合环路。直径为$\lfloor N/2 \rfloor$，节点度数为2。

**网格(Mesh)**：二维排列，每个节点与上下左右邻居连接。$\sqrt{N} \times \sqrt{N}$网格的直径为$2(\sqrt{N}-1)$。

**环面网(Torus)**：二维网格的边界循环连接，消除边界效应。直径减半为$\sqrt{N}$。

**超立方体(Hypercube)**：$N=2^n$个节点，每个节点与$n$个维度上的邻居连接。直径为$n=\log_2 N$，节点度数为$\log_2 N$。

**树形结构(Tree)**：层次化结构，根节点在顶部，叶节点在底部。二叉树直径为$2\log_2 N$，但根节点易成为瓶颈。

**胖树(Fat Tree)**：越靠近根部链路带宽越大，消除带宽瓶颈，是高性能互连网络的常用结构。

**例题13.2**：比较16个节点的环网、$4\times4$网格、$4\times4$环面和4维超立方体的直径和对分带宽。

**解答**：

^ 拓扑结构 ^ 节点数 ^ 直径 ^ 对分带宽 ^
| 环网 | 16 | 8 | 2 |
| 4×4网格 | 16 | 6 | 4 |
| 4×4环面 | 16 | 4 | 8 |
| 4维超立方体 | 16 | 4 | 8 |

==== 13.3.3 动态互连网络 ====

**总线(Bus)**：所有设备共享一组公共信号线，结构简单但带宽受限。当多个设备同时请求时产生冲突，需要仲裁机制。

**交叉开关(Crossbar)**：$N \times M$个交叉点，可建立$\min(N,M)$个同时连接。无阻塞但成本为$O(N \times M)$，适用于小规模系统。

**多级互连网络(MIN, Multistage Interconnection Network)**：使用多个开关级联，在成本和性能间取得平衡。常见类型包括：

  * **Omega网络**：使用$2\times2$开关，通过完美混洗连接各级
  * **Banyan网络**：自路由特性，根据目的地址自动选择路径
  * **Benes网络**：可重排无阻塞网络，但路径设置复杂

===== 13.4 缓存一致性问题 =====

==== 13.4.1 缓存一致性的基本概念 ====

在多处理器系统中，多个处理器的缓存可能保存同一内存块的不同副本，产生**缓存一致性(Cache Coherence)**问题。

当处理器$P_1$写入缓存块$X$时，其他处理器缓存中的$X$副本将变为无效。如果不加处理，将导致数据不一致。

缓存一致性协议需要解决三个问题：

  * **定位问题**：如何找到其他缓存中的副本
  * **传播问题**：如何通知这些副本更新或失效
  * **串行化问题**：如何保证所有处理器看到相同的写操作顺序

==== 13.4.2 监听协议(Snoopy Protocol) ====

监听协议适用于基于总线的多处理器系统，所有缓存控制器监视总线事务。

**写直达(Write-through)**与**写回(Write-back)**：

  * 写直达：同时更新缓存和主存，实现简单但总线负载大
  * 写回：仅更新缓存，替换时才写回主存，减少总线流量

**MSI协议**是最基本的监听协议，每个缓存块处于三种状态之一：

  * **M（修改，Modified）**：块已被修改，与主存不一致，独占该块
  * **S（共享，Shared）**：块有效且与主存一致，其他缓存可能有副本
  * **I（无效，Invalid）**：块无效

状态转换由处理器操作和总线事务触发：

  * 读命中：当前状态不变
  * 读缺失：若其他缓存有M状态的副本，需写回后读取；否则从主存读取
  * 写命中：S状态需使其他副本无效，转换为M状态
  * 写缺失：读取块后使其他副本无效，进入M状态

**MESI协议**增加**E（独占，Exclusive）**状态，优化只读数据的处理。当处理器读取一个未被缓存的块时，进入E状态而非S状态，后续写入无需总线事务。

**MOESI协议**进一步增加**O（拥有，Owned）**状态，支持脏数据的直接转发，减少写回操作。

==== 13.4.3 目录协议(Directory Protocol) ====

对于大规模多处理器系统，总线广播不可扩展，采用目录协议跟踪共享数据的位置。

**全映射目录(Full-Map Directory)**：为每个内存块维护一个位向量，记录哪些处理器缓存了该块。位向量长度为处理器数量，开销随规模线性增长。

**有限目录(Limited Directory)**：限制每个内存块的共享副本数，使用固定数量的指针。当共享数超过限制时需替换策略。

**链式目录(Chained Directory)**：通过链表结构记录共享者，无共享数限制，但遍历链表增加延迟。

目录协议需要处理三种消息：

  * **读缺失**：向目录查询数据位置，目录指示提供者发送数据
  * **写缺失**：使所有其他副本无效，获取独占访问权
  * **写回**：更新主存内容，修改目录状态

==== 13.4.4 内存一致性模型 ====

**内存一致性模型(Memory Consistency Model)**定义了内存操作（读/写）的可见性和排序规则。

**顺序一致性(Sequential Consistency, SC)**：程序执行结果等同于所有处理器按某种顺序执行的结果，且每个处理器的操作保持程序序。实现简单但限制硬件优化。

**处理器一致性(Processor Consistency, PC)**：放宽写-读顺序，允许写操作延迟，但同一处理器的写操作保持顺序。

**弱一致性(Weak Consistency, WC)**：区分普通访问和同步操作，仅在同步操作时保证一致性。

**释放一致性(Release Consistency, RC)**：进一步区分获取(acquire)和释放(release)操作，仅在同步点保证顺序。

**例题13.3**：考虑以下两个处理器执行的程序片段，在顺序一致性模型下，$R1$和$R2$的可能取值是什么？

```
处理器P1:              处理器P2:
  A = 1                  B = 1
  R1 = B                 R2 = A
```

**解答**：

在顺序一致性下，四种可能的执行顺序：

  1. A=1 → R1=B(0) → B=1 → R2=A(1)：R1=0, R2=1
  2. B=1 → R2=A(0) → A=1 → R1=B(1)：R1=1, R2=0
  3. A=1 → B=1 → R1=B(1) → R2=A(1)：R1=1, R2=1
  4. B=1 → A=1 → R2=A(1) → R1=B(1)：R1=1, R2=1

因此，$(R1, R2)$的可能取值为：(0,1)、(1,0)、(1,1)。不可能出现(0,0)，因为这要求两个读取都发生在写入之前，违反顺序一致性。

===== 13.5 同步机制 =====

==== 13.5.1 同步的基本问题 ====

多处理器系统中，多个处理器需要协调对共享资源的访问，避免**竞态条件(Race Condition)**。

**临界区(Critical Section)**是访问共享资源的代码段，需要保证**互斥(Mutual Exclusion)**执行。

同步机制需要满足：

  * **互斥**：同一时刻只有一个处理器进入临界区
  * **进步**：如果没有处理器在临界区且有处理器请求进入，选择应在有限时间内完成
  * **有限等待**：一个处理器请求进入后，在有限时间内获得许可

==== 13.5.2 锁机制 ====

**自旋锁(Spinlock)**：处理器循环测试锁变量直到获得锁。

```c
void acquire(lock *lk) {
    while (test_and_set(&lk->locked) == 1)
        ; // 自旋等待
}

void release(lock *lk) {
    lk->locked = 0;
}
```

**测试并设置(Test-and-Set)**是原子操作：读取内存值并设置为1，返回旧值。

**比较并交换(Compare-and-Swap, CAS)**：比较内存值与期望值，若相等则写入新值，返回是否成功。

```c
int compare_and_swap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}
```

**LL/SC(Load-Linked/Store-Conditional)**：

  * LL：读取内存值并标记该地址
  * SC：若该地址未被修改则写入，否则失败

这是RISC架构常用的原子操作原语。

**Ticket锁**：使用票号系统避免不公平竞争，先到先服务。

**MCS锁**：基于链表的队列锁，每个处理器在本地变量上自旋，避免缓存一致性流量风暴。

==== 13.5.3 屏障同步 ====

**屏障(Barrier)**用于同步一组处理器，所有处理器到达屏障后才能继续执行。

**集中式屏障**：使用计数器记录到达的处理器数，最后一个到达者唤醒所有等待者。

**树形屏障**：采用树形结构减少竞争，处理器在树的叶节点开始向上汇合。

**组合树屏障**：将处理器分组，组内先同步，组间再同步，可扩展性好。

**例题13.4**：比较自旋锁和阻塞锁的适用场景。假设锁的持有时间分别为10个周期和10000个周期，上下文切换开销为500个周期，哪种策略更优？

**解答**：

**锁持有10个周期**：

  * 自旋锁：浪费10周期（等待者自旋）
  * 阻塞锁：上下文切换开销1000周期（切换出+切换回）
  * **自旋锁更优**

**锁持有10000个周期**：

  * 自旋锁：浪费约10000周期
  * 阻塞锁：1000周期开销，但CPU可执行其他任务
  * **阻塞锁更优**

==== 13.5.4 无锁算法与事务内存 ====

**无锁算法(Lock-free Algorithm)**：至少一个线程能在有限步骤内完成操作，避免死锁和优先级反转。

**无等待算法(Wait-free Algorithm)**：每个线程都能在有限步骤内完成操作，更强的不变性保证。

**软件事务内存(STM)**：借鉴数据库事务概念，将一组内存操作作为原子单元执行。事务要么完全提交，要么完全回滚。

**硬件事务内存(HTM)**：硬件支持的事务执行，如Intel TSX（事务同步扩展）。

===== 13.6 多核与多线程技术 =====

==== 13.6.1 多核处理器架构 ====

**多核处理器(Multi-core Processor)**将多个处理核心集成在单一芯片上，共享或部分共享缓存和互连。

**同构多核(Homogeneous Multi-core)**：所有核心结构相同，如Intel Core系列、AMD Ryzen。

**异构多核(Heterogeneous Multi-core)**：核心具有不同特性，如ARM big.LITTLE（高性能核心+能效核心）。

**片上网络(NoC, Network-on-Chip)**：随着核心数增加，总线成为瓶颈，采用包交换网络连接核心和缓存。

常见NoC拓扑：

  * **2D网格**：规则简单，易于实现
  * **2D环面**：消除边界延迟不对称
  * **Spidergon**：兼顾性能和对称性

==== 13.6.2 硬件多线程 ====

**硬件多线程(Hardware Multithreading)**允许单个核心同时执行多个线程的指令。

**粗粒度多线程(Coarse-Grained Multithreading)**：在长时间等待事件（如缓存缺失）时切换线程。

**细粒度多线程(Fine-Grained Multithreading)**：每个周期切换线程，如交错执行两个线程的指令。

**同时多线程(Simultaneous Multithreading, SMT)**：利用超标量处理器的功能单元并行执行不同线程的指令。Intel超线程(Hyper-Threading)技术是典型的SMT实现。

SMT的优势：

  * 提高功能单元利用率
  * 隐藏长延迟操作
  * 支持更多并发线程

==== 13.6.3 处理器设计趋势 ====

**众核处理器(Many-core Processor)**：集成数十至数百个简单核心，如Intel Xeon Phi、NVIDIA GPU。

**领域专用架构(DSA, Domain-Specific Architecture)**：针对特定应用优化，如AI加速器、图形处理器。

**Chiplet技术**：将大芯片分解为多个小芯片(Chiplet)组合封装，提高良率和灵活性。

===== 13.7 实例分析 =====

==== 13.7.1 Intel多处理器系统 ====

**Intel Xeon处理器**采用Mesh或Ring互连架构，支持多达数十核心。

**Ultra Path Interconnect (UPI)**：新一代Intel处理器的处理器间互连技术，替代QuickPath Interconnect。

**Intel Optane持久内存**：在DRAM和SSD之间提供大容量持久存储，改变内存层次结构。

==== 13.7.2 AMD多处理器系统 ====

**AMD EPYC处理器**采用Chiplet设计，多个计算Chiplet围绕I/O Chiplet布置。

**Infinity Fabric**：AMD的片上/片间互连技术，统一连接核心、缓存和I/O。

==== 13.7.3 ARM多处理器系统 ====

**ARM Cortex-A系列**支持多核配置和CCI（缓存一致性互连）。

**big.LITTLE架构**：高性能核心（如Cortex-A78）与能效核心（如Cortex-A55）组合，动态调度任务。

===== 本章重点总结 =====

  * **多处理器分类**：SMP/NUMA、UMA架构特点及应用场景
  * **互连网络**：静态拓扑（网格、超立方体）与动态网络（总线、交叉开关）的性能权衡
  * **缓存一致性**：监听协议（MESI）和目录协议的工作原理
  * **内存一致性**：顺序一致性与弱一致性模型的区别
  * **同步机制**：锁、屏障的实现方式及无锁算法概念
  * **多核技术**：同构/异构多核、SMT技术的优势

===== 思考题 =====

  1. 为什么在大型多处理器系统中不采用总线监听协议？目录协议如何解决这个问题？
  2. 分析阿姆达尔定律对多核处理器设计的启示。
  3. 比较写直达和写回策略在缓存一致性协议中的优缺点。
  4. 讨论SMT技术如何提高处理器资源利用率。
  5. 为什么无锁算法在并发编程中越来越受关注？

===== 参考文献 =====

  * Hennessy, J.L. and Patterson, D.A., "Computer Architecture: A Quantitative Approach", 6th Edition
  * Culler, D.E., Singh, J.P. and Gupta, A., "Parallel Computer Architecture: A Hardware/Software Approach"
  * 唐朔飞，《计算机组成原理》，第3版