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