多处理器系统是现代计算机体系结构的核心组成部分，它通过并行处理技术提升系统性能。本章将深入探讨多处理器系统的基本概念、互连网络、缓存一致性、同步机制以及多核技术等关键内容，为理解现代高性能计算系统奠定基础。
并行计算(Parallel Computing)是指同时使用多种计算资源解决计算问题的过程。其基本思想是将复杂任务分解为多个可同时执行的子任务，通过并行执行来缩短总体执行时间。
并行计算的主要形式包括：
加速比(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)，计算机系统可分为四类：
现代多处理器系统主要基于MIMD架构，可进一步细分为：
按内存组织方式分类：
按耦合程度分类：
均匀内存访问(UMA, Uniform Memory Access)架构中，所有处理器访问任何存储单元的时间相同。典型的SMP系统采用UMA架构，具有以下特点：
UMA的优势在于编程简单，所有处理器看到一致的内存视图。但当处理器数量增加时，总线带宽成为瓶颈。
非均匀内存访问(NUMA, Non-Uniform Memory Access)架构中，处理器访问本地内存快于访问远程内存。NUMA系统的特点：
CC-NUMA（缓存一致性NUMA）通过硬件机制维护缓存一致性，使NUMA系统对程序员透明。
集中式共享内存将所有物理内存集中在单一位置，通过高速互连供所有处理器访问。适用于处理器数量较少的系统（通常<32个）。
分布式共享内存(DSM, Distributed Shared Memory)将内存分布在多个节点上，但向程序员呈现统一的共享地址空间。DSM的实现方式：
互连网络是多处理器系统的核心组件，负责处理器、内存和I/O设备之间的数据交换。关键性能指标包括：
静态互连网络适用于直接连接处理器的网络，拓扑结构固定：
动态互连网络使用开关元件动态建立连接路径，适用于共享资源的访问。
线性阵列(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 |
总线(Bus)：所有设备共享一组公共信号线，结构简单但带宽受限。当多个设备同时请求时产生冲突，需要仲裁机制。
交叉开关(Crossbar)：$N \times M$个交叉点，可建立$\min(N,M)$个同时连接。无阻塞但成本为$O(N \times M)$，适用于小规模系统。
多级互连网络(MIN, Multistage Interconnection Network)：使用多个开关级联，在成本和性能间取得平衡。常见类型包括：
在多处理器系统中，多个处理器的缓存可能保存同一内存块的不同副本，产生缓存一致性(Cache Coherence)问题。
当处理器$P_1$写入缓存块$X$时，其他处理器缓存中的$X$副本将变为无效。如果不加处理，将导致数据不一致。
缓存一致性协议需要解决三个问题：
监听协议适用于基于总线的多处理器系统，所有缓存控制器监视总线事务。
写直达(Write-through)与写回(Write-back)：
MSI协议是最基本的监听协议，每个缓存块处于三种状态之一：
状态转换由处理器操作和总线事务触发：
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)：
这是RISC架构常用的原子操作原语。
Ticket锁：使用票号系统避免不公平竞争，先到先服务。
MCS锁：基于链表的队列锁，每个处理器在本地变量上自旋，避免缓存一致性流量风暴。
屏障(Barrier)用于同步一组处理器，所有处理器到达屏障后才能继续执行。
集中式屏障：使用计数器记录到达的处理器数，最后一个到达者唤醒所有等待者。
树形屏障：采用树形结构减少竞争，处理器在树的叶节点开始向上汇合。
组合树屏障：将处理器分组，组内先同步，组间再同步，可扩展性好。
例题13.4：比较自旋锁和阻塞锁的适用场景。假设锁的持有时间分别为10个周期和10000个周期，上下文切换开销为500个周期，哪种策略更优？
解答：
锁持有10个周期：
锁持有10000个周期：
无锁算法(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拓扑：
硬件多线程(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）组合，动态调度任务。
1. 为什么在大型多处理器系统中不采用总线监听协议？目录协议如何解决这个问题？ 2. 分析阿姆达尔定律对多核处理器设计的启示。 3. 比较写直达和写回策略在缓存一致性协议中的优缺点。 4. 讨论SMT技术如何提高处理器资源利用率。 5. 为什么无锁算法在并发编程中越来越受关注？