298 lines
8.2 KiB
Markdown
298 lines
8.2 KiB
Markdown
# 第五章 线程级并行 - 考试考点精细化梳理
|
||
|
||
---
|
||
|
||
## 考点分级
|
||
|
||
### 【必考核心考点】
|
||
|
||
#### 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% | 极其难达到，说明高加速比需要极高并行度 | |