返回总复习页 流水线专题 存储专题 互连网络专题 练习库
互动问答整理

计算机系统结构：问答补充与考试判定表

把复习时反复追问的“为什么、怎么判断、考试写哪一步”抽出来，做成独立题型卡。它不替代讲义，而是补上讲义里默认你已经懂的那一层直觉。

定量分析流水线ILP分支预测Cache/TLBRAID互连网络多处理器
15复习专题
80+判定规则
考前可直接查

1. 怎么用本页

本页专门回答“我看到题目不知道怎么下手”的问题。考试时优先记流程，而不是背整段解释。

先把题目归类：流水线、Cache/TLB、RAID、互连函数、同步、多处理器。
再找触发条件：谁写谁读、是否有 forwarding、分支预测策略、写回还是写直达、是否有冗余。
最后代入判定表或公式，写出必要中间量，避免只给一个数字。

2. 单位与速算

这类题不是难，是容易被单位绊倒。先把 Hz、周期、ns、us 这几个互相换清楚。

写法含义常用换算
2GHz每秒 2 × 109 个时钟周期周期 = 1 / 2GHz = 0.5ns
1ns10-9s，纳秒2GHz 的半个周期是 0.25ns；一个周期是 0.5ns
10-6s微秒1us = 1000ns
200ns / 0.5ns把访存时间换成周期数远程访问开销 = 400 个时钟周期
CPI = 基本 CPI + 远程访问率 × 远程访问开销周期数

例如基本 CPI 为 0.5，0.2% 指令需要远程访问，远程访问 200ns，处理器 2GHz，则实际 CPI = 0.5 + 0.002 × 400 = 1.3。

3. 基本概念与定量分析

第一章到总览类题最容易考“概念 + 公式”。别背散句，记住每个术语在问什么量。

系统结构、组成、实现

层次问的是什么例子
系统结构程序员可见的机器属性。指令系统、寄存器、寻址方式、数据类型、中断异常。
组成系统结构怎样用硬件部件组织出来。流水线级数、Cache 层次、总线宽度、控制器设计。
实现具体物理与工艺怎么做。芯片工艺、封装、布线、器件速度。

Flynn 分类

类型含义典型例子
SISD单指令流、单数据流。普通单处理器。
SIMD单指令流、多数据流。向量机、GPU 中的许多数据并行场景。
MISD多指令流、单数据流。实际少见，考试一般知道概念即可。
MIMD多指令流、多数据流。多处理器、多核、集群。

性能公式

CPU 时间 = 指令条数 IC × CPI × 时钟周期时间 = IC × CPI / 时钟频率
平均 CPI = Σ(某类指令比例 × 该类 CPI)
加速比 S = 改进前时间 / 改进后时间
Amdahl：S = 1 / ((1 - f) + f / s)

做 Amdahl 题时，f 是“可改进部分原来占总时间的比例”，s 是这一部分自身加速了几倍。不可改进部分永远拖住总加速比，所以不要把局部加速倍数直接当总加速倍数。

MIPS 与 MFLOPS

指标公式坑
MIPS指令条数 / (执行时间 × 106) = 时钟频率 / (CPI × 106)不同 ISA 指令复杂度不同，不能简单横比。
MFLOPS浮点操作次数 / (执行时间 × 106)要看题目给的是浮点指令数还是浮点操作数。

设计原则

  • 以经常性事件为重点：高频部分值得优化。
  • 局部性原理：时间局部性与空间局部性支撑 Cache、预取、块传送。
  • 并行性开发：流水线、向量、SIMD、MIMD、ILP 都是在找可重叠工作。
  • 瓶颈意识：性能、存储墙、功耗墙、可靠性、通信和同步都可能成为限制。

4. MIPS 停顿判断

先固定五段：IF 取指，ID 读寄存器，EX 计算，MEM 访存，WB 写回。判断停顿时只问一句：后面的指令要用的值，前面的指令准备好了吗？

场景有正常定向无定向人话解释
普通计算后立刻被普通计算用停 0紧邻通常停 2ALU 结果出得早，有定向时能直接递给下一条。
LW 后立刻使用读出的寄存器停 1紧邻通常停 2Load 的数据到 MEM 后才出来，下一条 EX 要得太早。
LW 中间隔一条再用停 0通常停 1中间那条独立指令替你拖了一拍。
ALU 结果给 SW 要存的数据通常停 0紧邻通常停 2有 store-data forwarding 时可直接送到存储阶段。
SUB/ALU 后紧跟 BNZ 读条件寄存器本课按停 1紧邻通常停 2BNZ 在 ID 判断，条件值要得太早。
画图口径自己考试画图时，可以统一把等待画成 IF 后的 S。关键不是 S 在格子里的名字，而是后续 ID/EX 被推迟到正确周期。

题 3.11 的三种结果

方案关键停顿每轮总周期
无定向 + 排空4 个 RAW 各停 2；分支排空1515 × 99 + 3 = 1488
有定向 + 预测分支失败LW-use 停 1；SUB-BNZ 停 1；实际跳转时错取顺序指令99 × 99 + 3 = 894
有定向 + 指令调度 + 延迟分支用独立指令填空，SW 放入延迟槽66 × 99 + 4 = 598
调度后：LW R1,0(R2); ADDI R2,R2,#4; SUB R4,R3,R2; ADDI R1,R1,#1; BNZ R4,LOOP; SW R1,-4(R2)

为什么 `SW` 变成 `-4(R2)`：因为 `R2` 已提前加 4，当前 `R2 - 4` 才是本轮原来的地址。

考试画时空图的步骤

  1. 先一条指令一行，默认每条下一拍进入 IF。
  2. 遇到后者读前者写的同一个寄存器，判断有没有定向；没有就等到前者 WB 后，后者才能 ID 读到。
  3. 有定向时，ALU 结果通常不等 WB；Load-use 仍要等 1 拍；分支若在 ID 判断，条件寄存器太早用，通常还要停。
  4. 分支处理看题目：排空流水线就是等分支确定再取下一轮；预测分支失败就是先取顺序下一条，发现实际跳转后冲掉。
  5. 最后一轮通常还要把最后一条真正执行完，所以会出现 `每轮周期 × (循环次数) + 尾巴`。
IF 后停还是 ID 后停本质上是同一个等待被画在不同阶段。课件有时把指令卡在 IF，有时卡在 ID。你考试只要保证“读寄存器那一拍不能早于数据可用”，周期数对，通常就能得分。

5. 流水线公式与调度

流水线分类

分类维度类型怎么认
功能多少单功能 / 多功能只能做一种任务，或同一流水线可做多种任务。
连接方式静态 / 动态静态使用前固定连接；动态可在运行中改变连接。
级间时间等时 / 非等时各段耗时是否相同；非等时通常受最慢段限制。
结构形态线性 / 非线性线性只一路向前；非线性可能回流、跳段、复用功能段。

线性流水线性能

完成 n 个任务总时间：Tk = (k + n - 1)Δt
吞吐率：TP = n / Tk，最大吞吐率约为 1 / Δt
加速比：S = 串行时间 / 流水线时间
效率：E = 实际占用的时空面积 / 总时空面积 = S / k

如果各段时间不等，Δt 取最慢段时间，或者题目会让你加锁存器开销。流水线不是让单个任务更快，而是让多个任务重叠后吞吐率提高。

相关与冲突

名字含义处理方法
结构冲突同一时刻多条指令抢同一个硬件资源。增加资源、分离 I/D Cache、停顿。
RAW后者要读前者写出的值，真相关。定向、停顿、指令调度。
WAR后者写，前者还没读，名相关。寄存器重命名；五段顺序 MIPS 通常不出现。
WAW两条都写同一寄存器，写回顺序可能错。寄存器重命名；乱序/多发射中常见。
控制冲突分支导致下一条取哪条不确定。预测、延迟分支、BTB、清空错误路径。

非线性流水线调度

看到预约表、禁止表、冲突向量，就是非线性流水线题。做题顺序固定：

  1. 从预约表中同一行任意两个 X 的列距，得到禁止延迟集合 F。
  2. 把禁止延迟写成冲突向量 C，某位为 1 表示这个启动间隔不能用。
  3. 画状态转移图：每次选一个允许延迟，右移冲突向量并按规则合并。
  4. 找平均延迟最小的循环，平均延迟越小，吞吐率越高。
考试够用版不会画完整状态图时，至少把禁止表、冲突向量、可选延迟和一个可行循环写出来，通常能拿过程分。

6. ILP 与多发射

ILP 是 instruction-level parallelism，指令级并行。它问的是：一串指令里，有多少条可以重叠或并行执行。

概念直白解释图上怎么看
指令流出/发射处理器把指令送去执行单元，等于“这条指令正式开工”。n 流出表示一拍最多发射 n 条。
标量流水每拍最多启动 1 条指令。同一列通常只有一条新 IF。
超标量硬件一拍可发射多条普通指令。同一时刻多条指令并列进入执行。
超长指令字 VLIW编译器把多条可并行小指令打包成一条长指令。题中常说 12 条小指令组装成 3 条长指令。
超流水线把流水级切得更细，用更短时钟周期启动指令。每 1/n 个原周期启动一条，但单条经过更多小阶段。
普通 k 段流水执行 n 条任务：T = (k + n - 1) Δt

如果题目把 12 条小指令按 ILP=4 打成 3 条长指令，那这里的 n 就从 12 变成 3，所以 `T = (3 + 3 - 1)Δt = 5Δt`。这不是说原来 12 条消失了，而是 4 条一组被包装成 1 条长指令。

静态调度 vs 动态调度

方法谁负责考试关键词
静态调度编译器在运行前重排指令。指令调度、循环展开、软件流水、延迟槽。
动态调度硬件运行时决定何时发射/执行。记分牌、Tomasulo、保留站、重排序缓冲。
寄存器重命名硬件或编译器给“名字”换物理位置。消除 WAR、WAW；不能消除 RAW。

多发射题怎么读

题目说 n 流出、n 发射、每拍启动 n 条，本质都是一拍最多让 n 条指令进入执行。真正能不能达到 n 倍，还要看数据相关、结构冲突、分支预测准确率和访存延迟。

理想 CPI 下限约为 1 / 发射宽度；实际 CPI = 理想 CPI + 各类停顿

7. 分支预测、BHT/BHD 与 BTB

BHT/BHD

管“跳不跳”。它记录分支过去的方向历史，用来预测 taken 或 not taken。

BTB

管“跳去哪”。它用分支指令 PC 作标识，保存目标地址，有些实现也顺便保存预测位。

情况CPU 怎么做结果
BTB 命中且预测跳下一拍直接取 BTB 给出的目标地址若实际也跳，分支代价可降到很低。
BTB 命中但实际不跳清掉错误目标路径指令，改取 PC+4老式简化图可能会删除该 BTB 项。
BTB 不命中但实际跳先按顺序取，发现错后加入 BTB下次遇到同一分支可直接得到目标地址。
预测分支失败就是预测不跳。循环分支前若干轮通常实际跳回循环开头，所以会错取 BNZ 后面的顺序指令；如果顺序下一条是 `halt`，图里就会出现一个被冲掉的 `halt IF`。

BTB 命中后才谈预测错误

BTB 是“我知不知道这条分支的目标地址”。如果 BTB 不命中，流水线通常只能先顺序取指，之后发现这是分支再付出 BTB miss 开销；这时还没用 BTB 给出的目标路径，所以不再额外算“BTB 命中后的预测错误”。

CPI = 基本 CPI + 分支比例 × [(1 - BTB 命中率) × BTB 不命中开销 + BTB 命中率 × (1 - 预测精度) × 预测错误开销]

例如条件分支 5%，基本 CPI=1，BTB 命中率 80%，不命中 4 拍，预测精度 90%，预测错 8 拍：额外 CPI = `0.05 × (0.2×4 + 0.8×0.1×8) = 0.072`，总 CPI = 1.072。若 BTB 命中率升到 90%，总 CPI = 1.056。

一位预测器为什么循环会错两次

一个循环 10 次，前 9 次跳，最后 1 次不跳。一位预测器只记上一次结果。上轮循环退出时留下“不跳”，所以下轮第一次会错；本轮前面一直跳，最后退出时又会错。成功率 90%，预测准确率却是 8/10 = 80%。

Branch Folding

普通 BTB 只存目标地址；改进版还可以缓存目标地址处的一条或多条指令。这样预测跳转时，不必再去目标地址取指，可以直接把目标指令送入流水线。无条件分支在理想情况下可做到零延迟。

“所有指令和保存的标识都不要”这句话说的是预测错后，把错误路径上已经取来的指令作废，同时 BTB/预取缓冲里与这次错误预测对应的标识项也可以删掉或更新。不是删除程序里的指令。

8. Cache/TLB 计算

Cache 地址字段

映像方式地址拆分块能放哪里
直接映像标记 Tag + 索引 Index + 块内偏移 Offset每个主存块只能放 Cache 中唯一一行。
组相联Tag + 组号 Set + Offset每个主存块映射到某一组，组内任选一路。
全相联Tag + Offset任何主存块可放任意 Cache 行。

块内偏移位数由块大小决定；索引/组号位数由行数或组数决定；剩下的是标记位。地址题先把单位都化成字节，再取 log2。

两级 Cache：什么时候减命中时间

AMAT = L1 命中时间 + L1 不命中率 × (L2 命中时间 + L2 局部不命中率 × L2 不命中开销)

如果题目问平均访存时间，不减 L1 命中时间。若题目问“每次访问导致的停顿时间”，且基本 CPI 已经包含正常 L1 命中访问，则要用 AMAT 减去 L1 命中时间。

问法写法
平均访存时间直接算 AMAT。
每次访存平均停顿AMAT - L1 命中时间。
每条指令平均停顿(AMAT - L1 命中时间) × 每条指令平均访存次数。

TLB 是并进去还是额外加

如果题解把 TLB miss 放进 Cache miss penalty 里，写成 `主存延迟 + 传输块时间 + TLB miss 率 × TLB miss penalty`，就不要再给同一批 Cache miss 重复加一次。若题目明确“每次取指/每次数据访问都可能 TLB miss”，才额外加正常访问的 TLB stall。

块传输平均时间 = 40 + 32B/4B + 0.2% × 20 = 48.04
写回且 50% 脏块：平均 miss penalty = 1.5 × 48.04 = 72.06
CPI = 基本 CPI + 每条指令访存次数 × Cache miss 率 × miss penalty

如果额外统计指令 TLB miss，每条指令再加 `1 × 0.2% × 20 = 0.04`；如果所有 1.2 次访存都查 TLB，则额外加 `1.2 × 0.2% × 20 = 0.048`。

64B 块、8 个存储体、总线 8B/拍那类题

先别急着把 8 个存储体乘起来。题目说“每个存储体固定延迟 32 拍准备数据，8 个存储体能完全并行传输”，意思是准备阶段并行，所以固定延迟还是 32 拍；传输阶段受总线限制，64B / 8B 每拍 = 8 拍。因此一次调入 64B 块的读事务开销是 `32 + 8 = 40` 拍。

情况miss penaltyCPI 口径
理想 TLB，写回，50% 脏块平均 `1.5 × 40 = 60` 拍`CPI = 1.4 + 1.2 × miss率 × 60`
TLB miss 只在 Cache miss 取块地址时算，TLB miss 率 0.2%，额外 40 拍平均 `1.5 × (40 + 0.002 × 40) = 60.12` 拍`CPI = 1.4 + 1.2 × miss率 × 60.12`

所以 64KB miss 率 1.5% 时，理想 TLB 的 CPI 是 `1.4 + 1.2×0.015×60 = 2.48`；实际 TLB 按这份卷子的标准口径是 `2.48216`。128KB miss 率 1% 时，对应是 `2.12` 和 `2.12144`。

局部不命中率与全局不命中率

概念定义例子
L1 局部/全局不命中率L1 misses / 总访存次数1000 次访存，L1 miss 40 次，L1 miss rate = 4%。
L2 局部不命中率L2 misses / L1 missesL1 miss 40 次，L2 miss 20 次，L2 局部 miss rate = 50%。
L2 全局不命中率L2 misses / 总访存次数20 / 1000 = 2%。

分离 Cache 和混合 Cache

分离 Cache 要把指令访问和数据访问分开加权。若 75% 是取指，25% 是数据访问，则总体平均时间按 75% 与 25% 加权。混合 Cache 若题目说 load/store 会额外增加 1 个周期，就只给数据访问那 25% 加这个额外周期。

分离 Cache 平均时间 = 0.75 × 指令 Cache 时间 + 0.25 × 数据 Cache 时间
混合 Cache 数据访问 = 命中时间 + 结构冲突额外周期 + miss 率 × miss penalty

虚拟存储与 TLB

概念作用考试怎么用
页表把虚拟页号翻译成物理页号。页表在内存里，访问慢。
TLB页表项的高速缓存。TLB hit 时快速得到物理页号；TLB miss 要查页表。
页失效页面不在主存，需要从外存调入。开销远大于 Cache/TLB miss，通常单独给。
虚拟 Cache / 物理 Cache用虚拟地址或物理地址访问 Cache。可能考别名、同义、TLB 与 Cache 并行访问。
TLB 会不会算指令取指也要地址翻译，所以严格讲指令地址也可能 TLB miss。题解若只按 Cache miss 产生的地址算 TLB，就跟题解；若题目明确每次取指和数据访问都查 TLB，就把指令访问也算进去。

9. Cache 设计题

关联度题怎么比较

提高关联度一般会降低失效率，但会增加命中时间，也可能拉长处理器时钟周期。题目问“哪个平均访存时间小”，就比较：

平均访存时间 = 命中时间 + 失效率 × 失效开销
设计好处代价
直接映像命中时间短，硬件简单。冲突失效多。
组相联冲突失效少。比较器更多，命中时间可能增加。
全相联位置最灵活。硬件代价大，查找慢。

伪相联 Cache

先按直接映像位置查；如果没中，再去另一个候选位置查。第二个位置命中叫伪命中，要多花额外周期，但比真正 miss 便宜。

平均时间 = 直接命中时间 + 伪命中率 × 伪命中额外周期 + 真失效率 × 真失效开销

替换与写策略

问题选项记法
替换哪一块随机、FIFO、LRULRU 通常失效率低但实现复杂。
写命中怎么办写直达、写回写直达立刻写下一级；写回只改 Cache 置 dirty。
写不命中怎么办写分配、不写分配写回常配写分配；写直达常配不写分配。

读写事务决策树

读没有“写回/写直达”的选择：读命中就直接从 Cache 读，读不命中就从下一级把整块调入 Cache。写才分两层判断：先看写命中还是写不命中；写命中看写直达/写回，写不命中看写分配/不写分配。

访问命中写直达写回
读命中0 次下级事务，直接读 Cache。
读不命中从下级读入整块。块 128B、事务 64B 时，就是 2 次读事务。
写命中写 Cache，同时写下级；若一次事务 64B，通常按 1 次写事务。只写 Cache，置 dirty，暂时 0 次下级事务。
写不命中，写分配先读入整块，再写 Cache 和下级；128B 块加 64B 事务时通常是 2 读 + 1 写。先读入整块；若被替换块脏，还要先写回旧块。

例：90% 访存命中，30% 是写，块 128B，事务 64B，写失效采用写分配。写直达平均事务数为 `0.9×0.3×1 + 0.1×0.7×2 + 0.1×0.3×3 = 0.50`。写回且 20% 脏块时，只有 miss 才访问下级：`0.1 × (2 + 0.2×2) = 0.24`。

三类失效 3C

类型为什么发生常见降低方法
强制失效 compulsory第一次访问这个块。预取、增大块。
容量失效 capacityCache 总容量不够。增大 Cache。
冲突失效 conflict多个块争同一位置或同一组。提高相联度、victim buffer。

块大小、总线宽度、多体交叉

改动影响做题口径
块变大空间局部性变好，失效率可能下降；但 miss 时要搬更多字。miss penalty 常乘以块内字数。
总线/存储器宽度加倍一次可传更多字。块传输拍数减半。
多体交叉存储多个存储体交错工作，连续取多个字更快。题目给访问时间时，按“首字延迟 + 后续交错传输”算。

写回法什么时候写回

写回法不是每次 store 都写主存，而是在脏块被替换、别的处理器请求该块、一致性协议要求回写、或系统主动刷回时才写回。平时只改 Cache 并置 dirty 位。

降低失效开销与命中时间

技术解决什么关键句
请求字优先miss 时先返回 CPU 急需的字。先继续执行，再慢慢补齐块。
提前重启动请求字回来就重启 CPU。不等整块传完。
非阻塞 Cachemiss 期间允许后续命中继续。hit under miss。
预取提前把可能要用的块调入。预取准确才有用，错误预取会污染 Cache。
写缓冲写直达不让 CPU 等主存。读 miss 要检查写缓冲。
Victim Buffer减少刚被替换块又被访问的冲突失效。读 miss 时要查 victim buffer。

10. I/O、可靠性与 RAID

Write Buffer

写直达 Cache 中，CPU 把写请求先放进写缓冲，不必等主存写完。读失效时要先检查写缓冲，避免读到旧值。

Victim Buffer

写回 Cache 中，被替换出去的脏块先放到 victim buffer。读失效时也要查它，因为要读的块可能刚被挤出去。

I/O 系统基本词

词意思考试关注
可靠性 Reliability系统在一段时间内不失效的概率。常用 MTTF 表示平均失效前时间。
可用性 Availability系统处于可服务状态的比例。A = MTTF / (MTTF + MTTR)。
可信性 Dependability可靠、可用、可维护、安全等综合概念。概念题知道范围比可靠性更大。
吞吐率单位时间完成的 I/O 请求数。磁盘阵列、并行 I/O 常考。
响应时间一个 I/O 请求从发出到完成的时间。随机小请求尤其关注。

串联、并联与混联系统

串联可靠度：R = R1R2...Rn
并联可靠度：R = 1 - Π(1 - Ri)

串联是“全都好才好”，并联是“至少一个好就好”。混联系统先把局部串并联化简，再整体组合。

RAID 判断表

级别识别词核心区别
RAID 0条带化、无冗余快但不可靠，坏一块就丢数据。
RAID 1镜像每份数据有副本，容量利用率低。
RAID 3/4专用校验盘RAID 3 粒度更小，RAID 4 按块；校验盘容易成瓶颈。
RAID 5分布式校验校验信息分散在各盘，缓解专用校验盘瓶颈。
RAID 6双校验能容忍两块盘失效，写开销更大。
RAID 10先镜像再条带镜像对之间条带化，通常比 RAID 01 更可靠。
RAID 01先条带再镜像条带组整体镜像，一个盘坏后容错能力下降更快。

可靠性公式

指数分布且独立时：系统失效率 = 各串联必要部件失效率之和；MTTF = 1 / 系统失效率

串联系统任何一个必要部件坏就坏，因此失效率相加；并联系统要所有副本都坏才失败，可靠度通常写成 `1 - 全坏概率`。

例：10 块盘每块 MTTF 为 1,000,000 小时，外加控制器 500,000 小时、电源和风扇各 200,000 小时、SCSI 线 1,000,000 小时。失效率为 `10/1000000 + 1/500000 + 1/200000 + 1/200000 + 1/1000000 = 23/1000000`，所以 MTTF 约为 `1000000/23 = 43500` 小时。

RAID10 可靠性真题怎么写

4 块盘 RAID10 可以看成“两组镜像再条带”。一组镜像里两块盘至少有一块好即可，所以一组可靠度是 `1 - (1 - R3)^2`；两组都要好，所以平方。双控制器是并联，通道适配器是串联必要部件。

R = [1 - (1 - R1)^2] × R2 × [1 - (1 - R3)^2]^2

代入 R1=0.9、R2=0.95、R3=0.95：`R = 0.99 × 0.95 × 0.9975² = 0.9358`，保留两位百分数就是 93.58%。画可靠性框图时就是：控制器并联，接一个通道适配器，再接两个镜像磁盘组串联。

RAID 容量与小写

级别可用容量粗算小写代价
RAID 0N 块盘容量全可用。无校验，写简单。
RAID 1约一半容量。写两个副本。
RAID 4/5(N - 1) 块盘容量。小写常需读旧数据、读旧校验、写新数据、写新校验。
RAID 6(N - 2) 块盘容量。双校验，小写更贵。
RAID 10约一半容量。可靠性和性能通常较好。

11. 互连网络与同步

网络指标

指标含义怎么考
结点度一个结点直接连多少条边。环为 2；n 维超立方体为 n。
直径任意两点最短路的最大值。衡量最坏通信距离。
等分宽度/对剖宽度把网络分成两半至少切断多少链路。衡量整体带宽瓶颈。
链路带宽单条链路单位时间能传多少数据。总带宽还要看有多少可并行链路。
寻径距离源点到目的点经过多少跳。函数题和拓扑题常要求最短路径。

互连网络怎么分类

类别直观含义例子
静态互连网络处理器之间的线固定，运行时不改连接。环、网格、Illiac、超立方体。
动态互连网络中间有开关，连接状态可变。总线、交叉开关、多级互联网络。
多级立方体网络多级 2×2 开关按立方体函数连接。STARAN、间接二进制 n 方体。
Omega 网络混洗-交换网络，级间常用 perfect shuffle。按目标地址逐位路由。

静态网络常用结论

网络形状常考结论
线性阵列一条线端点度 1，中间度 2，直径 N - 1。
环首尾相连度 2，直径约 N/2。
二维网格m × n 方格距离常用曼哈顿距离。
超立方体N = 2n 个结点，n 位编号相邻点只差一位，距离是二进制编号的汉明距离。
Illiac4×4 环绕连接用 ±1、±4 这类 PM2 函数理解横竖连接。

PM2 和 Illiac

`PM2±i(x) = x ± 2^i mod N`。在 4×4、N=16 的 Illiac 网络里，垂直方向常对应 `±4 mod 16`，水平方向螺线常对应 `±1 mod 16`。判断要连一条还是两条边，可看函数是否互为逆或是否自反。

函数题要背什么

函数考试动作要不要反算
Cubei把二进制编号的第 i 位取反。自反，算一次即可，双向互连。
PM2+i`x + 2^i mod N`。通常还要看 PM2-i，方向相反。
PM2-i`x - 2^i mod N`。和 PM2+i互为逆。
σ循环左移或右移，按课件定义。通常要反算谁能连到目标点。

STARAN、多级立方体、Omega

它们都属于多级互联网络，图上都是若干级 2×2 开关。区别主要看级间连线和控制方式。

网络核心特征容易混的点
STARAN多级立方体网络，可做级控制，也可做部分级控制。级控制常实现交换功能，部分级控制常实现移数功能。
间接二进制 n 方体也是多级立方体思想，用 2×2 开关间接连接输入输出。和 STARAN 的图可能相似，重点看题目给的控制/连线定义。
Omega每级后接 perfect shuffle，按目标地址位逐级选择上/下出口。考试常考按目标二进制位寻径。

2×2 开关最基础的两种状态是直连和交换。直连就是上进上出、下进下出；交换就是上进下出、下进上出。有些课件扩展成更多模式，但做基础路由题先认这两个。

Omega 网络寻径

Omega 网络常按目的地址二进制位逐级决定 2×2 开关走上出口还是下出口。N=8 时有 3 级，目标地址有 3 位；每级看一位。若多个输入在同一级同一个开关想走同一个出口，就发生阻塞。

目的地址逐位寻径 vs 源地址异或目的地址寻径

这两种写法不是在说两张完全不同的网，而是在说“控制每一级开关时看哪串控制位”。直接看目的地址，适合课件里标准 Omega 的逐级目标位路由；看 `源地址 ⊕ 目的地址`，是在一些混洗/立方体式路由题里用差异位决定每级是否交换。

方法控制位含义做题动作
目的地址逐位寻径第 k 级看目的地址某一位，决定走上出口或下出口。从输入端沿图走，逐级按目标位选出口；若两路抢同一出口则阻塞。
源地址 ⊕ 目的地址寻径异或结果中为 1 的位表示源和目的在这一位不同，需要在相应级改变路径。先把源和目的写成二进制，异或得到控制码，再逐级检查开关冲突。

真题给 `π=(0)(1,2)(3)(5,6)(4)(7)` 时，只有 1→2、2→1、5→6、6→5 四条非平凡连接。按异或：`001⊕010=011`，`010⊕001=011`，`101⊕110=011`，`110⊕101=011`。它们的控制码相同，容易在同一级争同一开关出口；所以要画每条路径或列每级开关占用，不能只看最终目的是否不同。

动态网络优点代价
总线便宜简单，广播方便。一次通常只能一个事务，扩展性差。
交叉开关可并行建立多组连接。硬件开销 O(N²)。
多级互联网络硬件开销比交叉开关低。可能阻塞，路由更复杂。

LL/SC、旋转锁、屏障

机制一句话易错点
LL/SCLL 盯住某个内存地址，SC 只有在期间无人写该地址时成功。盯的是 `Mem[R1]`，不是寄存器 R1 本身。
旋转锁不停检查锁变量直到可进入临界区。支持 Cache 一致性时可先本地读，发现释放再原子交换。
屏障同步所有进程都到达后，大家一起继续。sense reversing 用 0/1 就够，因为不能跨两轮屏障乱跑。

旋转锁争用题的一问和二问

第一问通常问“所有处理器最终都获得一次锁，总共多少总线事务”。它按锁竞争人数从 n、n-1、...、1 递减求和。第二问问“如果总线公平且要处理完已有请求，处理 10 个请求大概多久”，它更关心时间排队，不只是总事务数。

n 个处理器逐个获得锁的事务数常写成 Σ(2i + 1) = n² + 2n

这里 `i 次 LL + i 次 SC + 1 次释放锁` 的意思是：当前还有 i 个处理器竞争时，它们都可能读锁、都尝试 SC，最后胜者执行完后释放锁。它是教材的总线事务估算模型，不是在模拟真实精确时序。

12. 多处理器与 Cache 一致性

多处理机是一台系统里有多个处理器。分布式共享存储器则是内存物理上分散在各节点，但逻辑上仍像一个共享地址空间。

多处理器分类

分类含义关键词
集中式共享存储 UMA所有处理器访问主存延迟大致相同。小规模 SMP。
分布式共享存储 DSM / NUMA内存分散在节点，本地快、远程慢。远程访问开销、目录协议。
消息传递多计算机每个节点有私有地址空间，通过消息通信。send/receive，程序员显式通信。

并行性能

加速比 = 单处理器时间 / 多处理器时间
效率 = 加速比 / 处理器数
实际 CPI = 本地基本 CPI + 远程访问率 × 远程访问开销 + 同步/一致性停顿

多处理器题常见逻辑：处理器变多不等于线性加速，因为串行部分、通信、同步、负载不均衡和 Cache 一致性都会吃掉收益。

协议怎么知道别人改了数据适用规模
监听协议所有 Cache 监听总线上的读写事务。小规模共享总线系统。
目录协议目录记录每个块在哪些 Cache 中、谁是 owner。较大规模系统，更可扩展。

目录不是一个“总目录本”就完事，而是按内存块维护状态。典型目录项包含状态、共享者位向量、owner。32 个处理器若用全位向量，每个块至少要 32 位记录共享者。

一致性 vs 一贯性

概念问的是什么直觉
Cache 一致性 coherence同一个内存地址的多个副本是否一致。一个变量 x，大家最终看到同一套写入顺序。
存储一贯性 consistency不同地址的读写在全系统中呈现什么顺序。x 和 y 两个变量的操作能否被重排。

写直达作废 vs 写回作废

  • 写直达：写 Cache 同时写内存，内存值始终较新；写某块时作废其他 Cache 副本。
  • 写回：只改 Cache，标记 dirty，内存可能旧；替换、干预或一致性需要时再写回。

作废协议 vs 更新协议

协议写时做什么适合场景
作废 invalidate写者让其他副本失效。一个处理器连续多次写同一块时更省流量。
更新 update写者把新值广播给其他副本。多个处理器频繁读同一共享数据时可能有用。

MSI 三状态

状态含义看到总线事务时
M Modified本 Cache 有唯一且已修改的最新副本，内存旧。别人读时需要提供/写回数据，自己降级。
S Shared可能多个 Cache 有干净副本，内存也是新的。别人写时本副本作废。
I Invalid本 Cache 没有有效副本。本地读写会发总线请求取块。

MSI 状态题按“本地读、本地写、远程读、远程写”逐步更新状态。写共享块时一般要先拿独占权限，让其他副本 I。

目录到底维护多少东西

目录按“内存块”维护，不是按处理器维护。若每个内存块都有一个目录项，那么目录项数量大致等于主存块数。每个目录项至少要能回答：这个块当前状态是什么、哪些处理器有副本、如果是独占/修改状态 owner 是谁。

目录空间约 = 主存块数 × 每块目录项大小

32 个处理器最直观的共享者记录方式是 32 位 bit vector；如果块很多，这部分目录开销会很大，所以大规模机器会用更复杂的压缩目录或链式目录。

13. 考试清单

临考前按这张表扫一遍：能说出“题型、条件、公式、坑”，基本就能下笔。

专题必须会常见坑
定量分析CPU 时间、平均 CPI、Amdahl、MIPS/MFLOPS。局部加速不要当总加速；比例必须是原执行时间比例。
流水线时空图、RAW 停顿、分支排空/预测/延迟槽、非线性调度。有无定向决定停几拍；最后一轮要加尾巴。
ILP超标量、VLIW、超流水、多发射、BHT/BTB。发射宽度是上限，相关和分支会降低实际并行。
Cache地址字段、AMAT、两级 Cache、局部/全局 miss、写策略、3C。问停顿时可能要减命中时间；TLB 不要重复加。
虚拟存储页表、TLB、页失效、虚拟/物理 Cache。取指也需要地址翻译，除非题解口径只算数据。
I/O/RAID可靠度、MTTF、Availability、RAID 0/1/5/6/10/01。RAID10 与 RAID01 顺序不同；小写要更新校验。
互连网络静态/动态、PM2、Cube、shuffle、Omega、网络指标。函数要注意是否双向、是否要反算连接到目标的源点。
多处理器UMA/NUMA、远程访问 CPI、监听/目录、MSI、LL/SC、屏障。LL/SC 盯内存地址；目录按块维护，不是按处理器维护。

做题通用流程

  1. 先圈出题目问的是时间、CPI、可靠度、地址字段、路由、状态变化还是总线事务。
  2. 把百分比转成小数，把 ns/us/GHz 统一成周期或秒。
  3. 列出“正常基本项 + 额外开销项”，不要一上来代数字。
  4. 若有多级结构，区分局部比例和全局比例。
  5. 若有循环，区分每轮周期、循环次数、最后一轮尾巴。
  6. 最后检查单位：周期、秒、小时、百分比、容量，答案必须和问法一致。

14. 最近真题补丁

这块专门对应最近几次卡住的真题问法：不是新知识，而是“考试卷上它到底想让你算什么”。

BTB CPI

BTB 不命中先算“不知道目标地址”的开销；只有 BTB 命中且用了预测路径后，才算预测错误开销。

写事务数

读 miss 调入整块；写命中由写直达/写回决定；写 miss 再看写分配。事务大小小于块大小时，整块要拆成多次事务。

TLB 口径

卷子若说“Cache 不命中时产生的地址有 0.2% TLB miss”，就把 TLB 额外拍数并进 miss penalty；若说每次取指/数据访问查 TLB，才按所有访存额外加。

Omega/RAID

Omega 题要列每级开关是否争出口；RAID10 可靠性先化简镜像对，再和控制器、适配器串并联组合。

我也单独做了一个练习库：里面有 20 套完整卷、160 道大题和 120 道速测题：打开练习库

15. 小题自测

  1. `LW R1,0(R2)` 后紧跟 `ADD R3,R1,R4`，有正常定向时停几拍？
  2. `SUB R4,R3,R2` 后紧跟 `BNZ R4,LOOP`，本课口径停几拍？
  3. 预测分支失败策略下，循环 99 次的 `BNZ` 前 98 次实际跳转，错几次？
  4. BHT/BHD 和 BTB 分别回答哪两个问题？
  5. 写回法下 50% 脏块，为什么一次 Cache miss 平均要 1.5 次块传输？
  6. RAID10 和 RAID01 的结构顺序分别是什么？
  7. 2GHz 的一个时钟周期是多少 ns？
  8. LL/SC 盯住的是寄存器 R1，还是 R1 指向的内存单元？
  9. PM2+3(13)，N=16，结果是多少？
  10. 目录协议中 32 个处理器用全位向量记录共享者，至少需要几位？
  11. Amdahl 中 f 表示改进后占比还是改进前占比？
  12. L2 局部不命中率的分母是什么？
  13. 写直达通常配写分配还是不写分配？
  14. 超立方体中两个结点距离怎么求？
  15. RAID5 比 RAID4 主要改进了什么？
  16. MSI 中 M 状态说明内存一定是最新的吗？
答案1 拍；1 拍；98 次；BHT/BHD 管跳不跳，BTB 管跳去哪；读新块 1 次 + 平均 0.5 次写回旧脏块；RAID10 是先镜像再条带，RAID01 是先条带再镜像；0.5ns；R1 指向的内存单元；5；32 位；改进前占比；L1 不命中次数；通常不写分配；编号异或后 1 的个数；把校验分布到各盘；不是，M 状态下 Cache 最新、内存可能旧。