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

并行计算(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倍加速。

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

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

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

按内存组织方式分类：

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

按耦合程度分类：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

线性阵列(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维超立方体的直径和对分带宽。

解答：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

内存一致性模型(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)，因为这要求两个读取都发生在写入之前，违反顺序一致性。

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

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

同步机制需要满足：

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

自旋锁(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锁：基于链表的队列锁，每个处理器在本地变量上自旋，避免缓存一致性流量风暴。

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

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

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

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

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

解答：

锁持有10个周期：

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

锁持有10000个周期：

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

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

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

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

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

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

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

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

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

常见NoC拓扑：

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

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

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

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

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

SMT的优势：

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

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

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

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

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

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

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

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

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

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版