10、多处理机与并行计算补充

这一部分根据新增资料 计组-多处理机.pptx、subject_作业七 多处理器.xlsx，并结合 06、互连网络与并行计算模型.md 补充。06 主要讲 SIMD 互连函数、静态网络、动态网络、BSP/PRAM，本文件重点补多处理机结构、Cache 一致性和多处理机性能模型。

教材查阅：系统结构教材第 168 页以后可查多处理机，第 187 页以后可查多处理机性能模型，第 203 页以后可查并行算法和编程基础。

---

一、多处理机属于 MIMD

多处理机通常属于 MIMD 系统。

MIMD 是 Multiple Instruction Multiple Data，即：

多指令流多数据流

它和 SIMD 的区别是：

项目	SIMD	MIMD
指令流	一个控制器发同一条指令	多个处理机可执行不同指令
数据流	多个数据并行处理	多个任务/数据独立处理
典型应用	向量、矩阵、图像规则并行	多任务、服务器、并行程序

---

二、集中式和分布式存储器多处理机

按处理机与存储器关系，多处理机可分为两大类。

1. 集中式共享存储器多处理机

多个处理机共享同一主存地址空间。

特点：

编程相对方便
处理机访问共享存储器
容易出现访存冲突
可用多模块交叉存储减少冲突

集中式共享存储器多处理机又可分为：

• 对称式多处理机 SMP。
• 非对称式多处理机。
• 同构多处理机。
• 异构多处理机。

2. 分布式存储器多处理机

每台处理机有自己的本地存储器。

通信方式：

• 共享地址空间的分布式共享存储。
• 消息传递的分布式非共享存储。

---

三、UMA、NUMA、NORMA

新增 PPT 明确列出这三个模型。

模型	全称	特点
UMA	Uniform Memory Access	统一存储访问，访问各存储模块时间基本相同
NUMA	Non-Uniform Memory Access	非统一存储访问，访问本地和远程存储时间不同
NORMA	No Remote Memory Access	无远程存储访问，不能直接访问远程存储器，靠消息传递

记忆：

UMA：大家访问内存一样远
NUMA：本地近，远程远
NORMA：不能直接访问远程内存

---

四、Cache 一致性问题

多处理机中，每个处理机常有自己的 Cache。当多个 Cache 保存同一主存块的副本时，就可能产生一致性问题。

新增 PPT 中列出的原因有三类：

共享可写数据
进程迁移
绕过 Cache 的 I/O 操作

典型例子：

P1 和 P2 的 Cache 中都有变量 x
P1 修改了 x
如果 P2 的 Cache 副本没有更新或失效
P2 再读 x 时就可能读到旧值

---

五、监听一致性协议

当多个处理机的 Cache 都连接到公共总线时，可以使用监听一致性协议。

核心思想：

每个 Cache 控制器监听总线上的读写请求
发现其他处理机对共享块操作时，更新或失效自己的副本

两类基本策略：

策略	做法
写无效协议	一个处理机写共享块时，让其他 Cache 中对应副本失效
写更新协议	一个处理机写共享块时，把新值广播给其他 Cache

写无效协议减少广播数据量，是很多协议的基础。

---

六、MESI 协议

MESI 是一种典型的写无效协议。

MESI 四种状态：

状态	英文	含义
M	Modified	已修改，该块只在本 Cache 中有效，主存是旧值
E	Exclusive	独占，该块只在本 Cache 中有效，且与主存一致
S	Shared	共享，多个 Cache 可有副本，且与主存一致
I	Invalid	无效，该 Cache 块内容不可用

容易考英文缩写：

M：Modified
E：Exclusive
S：Shared
I：Invalid

---

七、目录协议

当系统规模很大，不能依赖单一共享总线监听所有 Cache 操作时，可以使用基于目录的协议。

目录记录：

某个主存块当前在哪些 Cache 中有副本
这些副本是否有效
该块是否允许写

目录结构常见类型：

• 全映射目录。
• 有限目录。
• 链式目录。

---

八、程序划分和调度

多处理机并行程序执行时，需要解决：

任务怎么划分
任务分配给哪些处理机
通信和同步怎么安排
总执行时间怎么算

新增 PPT 中提到静态多处理机调度过程：

构造细粒度程序图
调度细粒度程序图
进行任务合并
再进行粗粒度调度

---

九、SISD、SIMD、MIMD 点积时间

题库中多次出现点积：

$$S=\sum_{i=1}^{n}A_iB_i$$

1. SISD 串行系统

若乘法时间为 $t_{multi}$，加法时间为 $t_{add}$，串行计算 $n$ 个乘积并求和：

$$T_{SISD}=n t_{multi}+(n-1)t_{add}$$

2. SIMD 环形结构

一般思路：

每个 PE 先做局部乘法和局部累加
再通过环形网络归约

若题目给出课程公式，则优先代公式：

$$T_S=\left\lceil\frac{n}{N}\right\rceil t_1+ \left(\left\lceil\frac{n}{N}\right\rceil-1\right)t_2+ m t_2+ 通信项$$

其中：

$$N=2^m$$

通信项要看网络：

双向环：m t_3
单向环：(2m-1)t_3
全连接：(2^m-1)t_3

---

例题1：SISD 点积时间

计算：

$$S=\sum_{i=1}^{64}A_iB_i$$

若乘法需要 $4$ 拍，加法需要 $2$ 拍，SISD 串行系统所需时间为多少？

串行系统需要 $64$ 次乘法和 $63$ 次加法：

$$T=64\times4+63\times2$$ $$T=256+126=382$$

答案：

$$382\text{ 拍}$$

---

十、BSP 和 PRAM 模型再理解

1. PRAM

PRAM 是 Parallel Random Access Machine，并行随机访问机。

特点：

理想共享存储模型
通常忽略通信开销
适合分析并行算法

常见访问冲突模型：

• EREW：互斥读互斥写。
• CREW：并发读互斥写。
• CRCW：并发读并发写。

2. BSP

BSP 是 Bulk Synchronous Parallel，块同步并行模型。

一个 BSP 超步通常包括：

局部计算
通信
全局同步

所以 BSP 比 PRAM 更接近真实机器，时间公式里会出现通信和同步开销。

---

例题2：BSP 与 PRAM 对比

在有 $16$ 个处理器的 BSP 和理想 PRAM 计算机上计算同一表达式。若 BSP 总时间为 $10400ns$，PRAM 总时间为 $5200ns$，串行时间为 $76800ns$，求加速比。

BSP 加速比：

$$S_{BSP}=\frac{76800}{10400}\approx7.38$$

PRAM 加速比：

$$S_{PRAM}=\frac{76800}{5200}\approx14.77$$

结论：

PRAM 忽略通信同步开销，所以理想加速比更高；
BSP 考虑真实通信和同步，因此加速比较低。

---

十一、本章高频考法

1. 概念辨析

常考：

SIMD 与 MIMD 区别
UMA、NUMA、NORMA 区别
集中式共享存储与分布式存储区别

2. Cache 一致性

常考：

Cache 不一致产生原因
写无效和写更新区别
MESI 四状态含义
监听协议和目录协议适用场景

3. 并行时间计算

常考：

SISD 串行点积时间
SIMD 环形/全连接归约时间
BSP/PRAM 时间和加速比