# 第五章 线程级并行 - 考试考点精细化梳理

---

## 考点分级

### 【必考核心考点】

#### 1. Amdahl定律在多处理机中的应用（计算题必考）

**核心考法**：计算题（★★★★★）

**标准公式**：
```
加速比 = 1 / [S + (1-S)/N]

其中：
- S：串行部分比例
- N：处理器数量
- (1-S)：可并行部分比例
```

**逆运算类型**：
- 已知加速比和N，求S
- 已知加速比和S，求N

**典型例题**：
> 假设想用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？

**解题步骤**：
```
解：根据Amdahl定律
80 = 1 / [S + (1-S)/100]

80 = 1 / (S + 0.01 - 0.01S)
80 = 1 / (0.01 + 0.99S)
80(0.01 + 0.99S) = 1
0.8 + 79.2S = 1
79.2S = 0.2
S = 0.2/79.2 ≈ 0.0025

答：串行部分最多占0.25%，即并行比例约99.75%
```

**常见陷阱**：
- 混淆"S"（串行比例）和"(1-S)"（并行比例）
- 计算时忘记括号优先级

**易错易混点**：
- 当N很大时，加速比趋向于 1/S
- 即使用100个处理器，要达到80加速比也需要99.75%并行

**答题模板**：
```
解：根据Amdahl定律
加速比 = 1 / [S + (1-S)/N]

代入已知条件：加速比=__，N=__
列方程：__ = 1 / [S + (1-S)/__]
求解：S ≈ ___
并行比例 = 1 - S ≈ ___

答：串行部分最多占___%。
```

**踩分细则**：
- 正确写出Amdahl公式：1分
- 代入正确参数：2分
- 解方程过程正确：4分
- 最终答案正确：1分

---

#### 2. 多处理机分类（选择题/填空题高频）

**核心考法**：选择题、填空题、简答题（★★★★★）

**五种分类**：

| 分类 | 全称 | 特点 | 代表 |
|------|------|------|------|
| PVP | 并行向量处理机 | 专用向量处理器 | Cray |
| SMP | 对称多处理机 | 共享内存，均匀访问 | 多核服务器 |
| MPP | 大规模并行处理机 | 分布式内存，不共享 | 超算 |
| DSM | 分布式共享内存 | 物理分布，逻辑共享 | NUMA |
| COW | 工作站集群 | 商用互连，商品组件 | Beowulf |

**考试重点**：
- 给定描述能识别属于哪类多处理机
- 理解SMP和DSM的区别（内存访问是否均匀）
- 理解PVP、MPP、SMP的主要区别

**常见陷阱**：
- 混淆SMP和DSM（都是共享内存，但访问延迟不同）
- 混淆MPP和COW

**答题话术**：
```
多处理机按硬件和互连结构分为五类：

1. PVP（并行向量处理机）：配备专用向量处理器，通过 Crossbar 连接
2. SMP（对称多处理机）：多个相同处理器通过高速总线或交叉开关连接，共享内存，内存访问均匀（UMA）
3. MPP（大规模并行处理机）：数百至上万个处理器，分布式内存，不共享，通过专用互连网络连接
4. DSM（分布式共享内存）：物理上分布内存，逻辑上共享，内存访问不均匀（NUMA）
5. COW（工作站集群）：用商品工作站和商用网络构建，编程模型是消息传递

关键区别：
- 内存访问：SMP是UMA，DSM是NUMA
- 内存物理分布：MPP是完全分布式，DSM是共享但分布式
```

---

#### 3. Cache一致性协议（选择题/分析题必考）

**核心考法**：选择题、填空题、分析题（★★★★★）

**两种协议类型**：

| 协议 | 原理 | 优点 | 缺点 |
|------|------|------|------|
| 监听协议（Snooping） | 总线监听所有Cache请求 | 实现简单，延迟低 | 总线带宽瓶颈 |
| 目录协议（Directory） | 集中式目录跟踪共享状态 | 可扩展性好 | 延迟高，需要额外内存 |

**写策略对比**：
| 策略 | 原理 | 数据传输量 |
|------|------|------------|
| 写作废（Write Invalidate） | 写时使其他Cache副本无效 | 只需发无效信号 |
| 写更新（Write Update） | 写时更新其他Cache副本 | 需传输数据 |

**一致性状态机（MSI/MESI/MOESI）**：

| 状态 | 含义 | 转换条件 |
|------|------|----------|
| M（Modified） | 已修改，独家 | 写操作时 |
| S（Shared） | 干净，共享 | 读操作时 |
| E（Exclusive） | 干净，独家 | 独占读时 |
| I（Invalid） | 无效 | 收到无效请求时 |
| O（Owned） | 脏，共享 | 写操作时 |

**考试重点**：
- 理解监听协议和目录协议的工作原理
- 能画出状态转换图
- 理解写作废和写更新的区别

**常见陷阱**：
- 混淆"写更新"和"写作废"
- 不理解O状态和M状态的区别

**答题话术**：
```
Cache一致性协议确保多个处理器Cache中的数据保持一致：

监听协议：
- 每个Cache监听总线上的所有请求
- 当检测到其他处理器写操作时，自身副本失效或更新
- 优点：延迟低，实现简单
- 缺点：总线带宽受限，不适合大规模系统

目录协议：
- 维护一个集中式目录，记录每个内存块的共享状态
- 处理器需先查询目录，再进行数据访问
- 优点：可扩展性好，适合大规模系统
- 缺点：延迟高，需要额外内存开销

写策略：
- 写作废：写时使其他Cache副本失效，节省带宽
- 写更新：写时更新其他Cache副本，保证数据新鲜
```

---

### 【高频考点】

#### 4. CPI与远程访问影响（计算题高频）

**核心考法**：计算题（★★★★☆）

**公式**：
```
实际CPI = 基本CPI + 远程访问率 × 远程访问开销

远程访问开销 = 远程访问时间 / 时钟周期时间
```

**典型例题**：
> 32台处理器，远程访问时间200ns，时钟频率2GHz，基本CPI=0.5，0.2%指令需远程访问。求速度比。

**解题步骤**：
```
解：
1. 计算时钟周期时间：1/2GHz = 0.5ns
2. 计算远程访问开销：200ns / 0.5ns = 400周期
3. 计算实际CPI：0.5 + 0.2% × 400 = 0.5 + 0.8 = 1.3
4. 计算速度比：1.3 / 0.5 = 2.6

答：前者比后者快2.6倍。
```

**常见陷阱**：
- 混淆"远程访问率"和"本地访问率"
- 单位不统一（ns vs ps vs 周期）

---

#### 5. 同步机制

**核心考法**：选择题、简答题（★★★★☆）

**基本同步原语**：
- 原子读-改-写操作（Atomic Read-Modify-Write）
- 忙等（Busy Wait）vs 阻塞等待

**同步实现机制**：
- 自旋锁（Spin Lock）
- 屏障（Barrier）

**常见考题**：
- 解释同步的重要性
- 分析忙等 vs 阻塞的适用场景

---

### 【了解考点】

#### 6. 目录协议的三种结构

**考法**：选择题、填空题

| 结构 | 特点 |
|------|------|
| 全集中式目录 | 单节点维护所有目录，开销大 |
| 分布式目录 | 目录分布在各节点，开销小 |
| 链式目录 | 指针链方式跟踪共享，内存开销小 |

---

## 本章核心公式速记

```
1. Amdahl定律：加速比 = 1 / [S + (1-S)/N]
2. 远程访问开销 = 远程访问时间 / 时钟周期时间
3. 实际CPI = 基本CPI + 远程访问率 × 远程访问开销
4. CPI = 1 / (S + (1-S)/N) （另一种形式）
5. 多处理机分类：PVP/SMP/MPP/DSM/COW
6. Cache一致性：监听协议 vs 目录协议，写作废 vs 写更新
7. MESI状态：Modified/Shared/Exclusive/Invalid
8. MOESI增加：Owned状态
```

---

## 典型计算题解题示范

**例题1**：
> 假设想用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？

**标准答案**：
```
解：根据Amdahl定律
加速比 = 1 / [S + (1-S)/N]

80 = 1 / [S + (1-S)/100]
80(S + 0.01 - 0.01S) = 1
80(0.01 + 0.99S) = 1
0.8 + 79.2S = 1
S = 0.2/79.2 ≈ 0.0025

答：串行部分最多占0.25%，即并行比例约99.75%。
```

**例题2**：
> 32台处理器，远程访问200ns，时钟频率2GHz，基本CPI=0.5，0.2%指令远程访问。求速度比。

**标准答案**：
```
解：
时钟周期 = 1/2GHz = 0.5ns
远程访问开销 = 200ns / 0.5ns = 400周期

实际CPI = 0.5 + 0.2% × 400 = 1.3

速度比 = 1.3 / 0.5 = 2.6

答：没有远程访问时机器速度是有0.2%远程访问的机器的2.6倍。
```

---

## 常见易错易混点总结

| 易错点 | 正确理解 |
|--------|----------|
| SMP vs DSM | SMP是UMA，DSM是NUMA，访问延迟不同 |
| 监听 vs 目录 | 监听适合小规模，目录适合大规模 |
| 写作废 vs 写更新 | 写作废只发信号，写更新传数据 |
| MESI vs MOESI | MOESI多Owned状态，可读脏数据 |
| 并行比例99.75% | 极其难达到，说明高加速比需要极高并行度 |