从存储墙到流水线冒险，
把 CPU 的两大提速手段吃透

7.1 冯·诺依曼结构与它的瓶颈

冯·诺依曼结构的核心是存储程序（stored-program）：指令和数据放在同一个主存里。它由这几部分组成：

• CPU：控制单元（CU）负责取指和控制指令执行；ALU 负责算术和逻辑运算。
• 主存：同时存程序和数据，按字节编址（每个地址存 1 个字节）。
• 系统总线：在 CPU、内存、I/O 之间传数据、地址和控制信号。
• I/O 设备和辅存（硬盘、SSD，非易失）。

问题出在"共享"上：指令和数据走同一个存储器、同一条通路。CPU 处理数据的速度远快于数据在总线上搬运的速度，于是 CPU 经常停下来等，这就是冯·诺依曼瓶颈。

讲义里的 DRAM 数据：1980 年 64 Kb、250 ns，到 1995 年 64 Mb、120 ns。容量涨了 1000 倍，周期时间只缩短一半。CPU 与 DRAM 之间越拉越大的差距被称为存储墙（memory wall）。

怎么缓解瓶颈（讲义列了五条）

• 缓存与存储层次：把常用数据放在离 CPU 近的地方。这是本课和接下来两课的主线。
• 哈佛或混合结构：指令和数据走分开的通路，带宽翻倍。
• 并行与专用化：多核、GPU、向量机、AI 加速器。
• 存内/近存计算（PIM）：把处理器和 RAM 做在同一芯片上，减少数据搬运。
• 更快的互连与存储：例如 3D 堆叠的高带宽内存 HBM。

7.2 存储层次与局部性原理

硬件上有个绕不开的事实：大的存储器慢，快的存储器小。存储层次的思路是把几种存储器叠起来，让程序"看起来"拥有一块又大、又快、又便宜的内存。

• 任何时刻，数据只在相邻两层之间复制。靠近 CPU 的叫上层（小、快、贵），远的叫下层（大、慢、便宜）。
• 层与层之间搬运的基本单位叫块（block）；块放进缓存后占据的位置叫缓存行（cache line）。本课程里 block 和 line 混用。

层次结构之所以有效，靠的是局部性原理：程序在任一时刻只访问地址空间里很小的一部分（"90/10 规则"：10% 的代码占 90% 的执行时间）。局部性分两种：

主存和缓存到底是什么、在哪里

以一台常见的游戏本为例（Intel Core Ultra 7 处理器、16 GB 内存、2 TB SSD）：

┌──────────── CPU 芯片（一小块硅片） ────────────┐
│  核 0: 寄存器 + L1    核 1: 寄存器 + L1    …    │
│  L2（每个核或每组核一个）                        │
│  L3（所有核共用）              ← 这些都是"缓存"  │
└───────────────────┬────────────────────────────┘
                    │ 内存总线（芯片外面的导线）
          ┌─────────┴─────────┐
          │   内存条 DRAM     │   ← 这就是"主存"
          └─────────┬─────────┘
                    │ PCIe / NVMe
          ┌─────────┴─────────┐
          │   SSD / 硬盘      │   ← 辅存，关机后数据还在
          └───────────────────┘

• 主存放"原件"：正在运行的程序和它的全部数据。打开程序时，系统先把它从 SSD 读进主存；断电就清空。
• 缓存放"常用的复印件"：只是主存里最近用过的一小部分的副本（上例 L3 只有 30 MB，约为主存的 1/500）。CPU 读某个地址时先查 L1，没有再查 L2、L3，都没有才去主存；从主存取回时把整块复制进缓存，下次再用就快了。
• 速度差得很远：L1 约 1 ns（几个周期）；主存约 50–100 ns（几百个周期）；SSD 约 50–150 μs，比主存再慢上千倍。

注意：日常说的"手机内存 256 GB"其实是存储空间，相当于这里的辅存；课程里的主存（内存）专指 RAM。考试题默认只有"一级缓存 + 主存"两层，不用管 L2、L3。

补充：显存（GPU 内存）在哪一层

显存在层次图上和主存是同一层：它本身就是 DRAM，只是不属于 CPU 这座金字塔，而是 GPU 自己那座金字塔里"主存"的位置。

• 技术上它就是 DRAM。它和主存一样处在"片外、大、比 SRAM 慢"那一层，区别是为带宽设计：数据位宽更宽、频率更高。例如一块 8 GB GDDR7 的笔记本显卡，带宽有几百 GB/s；CPU 的双通道 DDR5 约 80–100 GB/s。单次访问的延迟并不比主存短，GPU 靠几千个线程同时访存把延迟藏起来。
• 两座金字塔之间隔着 PCIe。CPU 不能像用自己的主存那样透明地用显存，数据要显式拷过去（例如 cudaMemcpy）。PCIe 只有几十 GB/s，远低于显存带宽。这条通路就是 7.1 节冯·诺依曼瓶颈在 CPU 和 GPU 之间的翻版，所以跑深度学习时要尽量让数据一直留在显存里。
• 集成显卡没有独立显存。核显（以及苹果 M 系列的统一内存）的"显存"就是从主存里划出来的一块，和 CPU 共用同一层 DRAM。
• 和讲义的联系。7.1 节"怎么缓解瓶颈"里的"GPU 等并行加速器"和"3D 堆叠的 HBM"指的就是这一套：HBM 是贴在 GPU 旁边堆叠起来的显存。

7.3 命中、缺失与 AMAT（课程约定）

本课程默认只有两级：缓存和主存。访问缓存找到了叫命中（hit），没找到就要去主存取块，叫缺失（miss），CPU 为此多等的周期叫存储停顿（memory stall）。几个时间量要分清：

讲义例子：缓存 1 周期，主存 50 周期，命中率 80%。命中时间 1，缺失代价 50，缺失时间 51，缺失率 0.2，所以 AMAT = 0.8×1 + 0.2×51 = 11 周期。

加速比（speedup）是什么

加速比衡量一项改进让同一件事快了多少倍：

• 大于 1 表示变快了：加速比 4 就是快了 4 倍，时间变成原来的 1/4；小于 1 表示反而变慢了。
• 前后必须是同一个任务（同一个程序、同一批数据），否则比较没有意义。

最后一行是通式：每条指令的平均时间 = CPI × 时钟周期，CPU 时间之比就是这两项乘积之比，前面几行都是它的特殊情况。

7.4 存储停顿与实际 CPI

理想 CPI 是"所有取指和取数都命中缓存、没有流水线冒险、没有分支代价、不等 I/O"时每条指令平均需要的周期数，代表处理器理论上最好的表现。现实中缺失会带来停顿：

先分清：取指 vs 取数

取指（instruction fetch）：把指令本身从存储器读出来。CPU 按 PC 里的地址读出那 32 位指令编码，放进指令寄存器 IR，然后 PC 加 4。取数（data access）：指令执行时，去存储器里读或写它要处理的数据。

例：LW R1, 8(R2) 存在地址 1000，R2 = 500。取指：读 Mem[1000]，得到这条指令的编码；取数：读 Mem[500 + 8] = Mem[508]，把值放进 R1。这一条指令访问了两次存储器。ADD R1, R2, R3 只有取指（操作数都在寄存器里）；SW R3, 8(R2) 是取指加一次写数据。

• 访存次数 = 1（取指）+ load/store 比例（取数）。
• 缺失率要分别乘：指令停顿 = 1 × I-缺失率 × 代价；数据停顿 = load/store 比例 × D-缺失率 × 代价。
• 结构冒险：指令和数据共用一个单端口存储器时，一条指令在 IF 取指、另一条在 MEM 取数，同一周期抢同一个存储器（Lesson 12）。分开的指令/数据缓存（哈佛结构的思路）可以解决。

"load/store 占 40%"是什么意思

这叫指令构成（instruction mix）：程序运行时执行的所有指令里，有 40% 是 load 或 store（两者合起来算，比如 25% load + 15% store），其余 60% 是算术逻辑、分支这类不访问数据存储器的指令。

情形 1：取指和取数的缺失率、缺失代价相同

课程默认每条指令都要取指一次（I = 1），只有 load/store 才访问数据存储器。讲义例子：理想 CPI 2.0，load/store 占 40%，缺失率都是 2%，代价 25 周期 → 访存次数 1.4，停顿 1.4×0.02×25 = 0.7，实际 CPI 2.7，比全命中慢 2.7/2.0 = 1.35 倍。如果根本没有缓存，每次访存都要 25 周期：停顿 1.4×25 = 35，CPI = 37。

情形 2：指令缓存和数据缓存的参数不同

讲义例子：理想 CPI 1.1，指令构成 50% 算术、30% load/store、20% 控制。数据缺失率 10%，代价 50。只算数据缺失：0.3×0.1×50 = 1.5，CPI = 2.6，有 1.5/2.6 = 58% 的时间在等内存。再加上 1% 的指令缺失（0.01×50 = 0.5），CPI = 3.1，停顿占 2.0/3.1 = 64.5%。

7.5 循环访存计时题

讲义用一个循环说明缓存为什么有效：循环 10 次访问数组 a[i]，缓存访问 1 ms，RAM 访问 10 ms（夸张的数字，只为好算）。约定如下：

• 每次引用 a[i] 算一次访存；sum、i 都在寄存器里，不产生访存。
• 整个数组在同一个块里：第一次访问缺失，把块从 RAM 搬进缓存；之后全部命中。

8.1 性能指标与 AMAT 公式

把 MT = HT + MP 代进 Lesson 7 的 AMAT 定义，就得到最常用的形式：

两个式子结果相同，Tutorial 8.6 就要求你用两种写法各算一遍来验证。讲义例子：HT = 1，MP = 100，HR = 97%，AMAT = 1 + 0.03×100 = 4 周期。缺失率只有 3%，但缺失代价太大，平均访问时间就从 1 涨到了 4。

8.2 缓存设计四问与三种映射

1. 怎么判断命中？比较标签（tag）：地址里的标签和缓存行里存的标签相同（且有效位为 1）就是命中。
2. 新块放在哪？映射方式：全相联、直接映射、组相联。
3. 候选位置都满了踢谁？替换策略：LRU（最近最少使用）、FIFO、随机。
4. 块里的哪个字节？用地址最低的偏移位（offset）选。

讲义的统一例子：主存 64 字节（地址 0–63，需要 6 位地址），块大小 4 字节，所以主存有 16 个块；缓存 16 字节，即 4 行。下面点切换，看同一个内存块在三种方式下能去哪：

8.3 全相联 + LRU：最灵活的放法

全相联（fully associative）：任何内存块都可以放进任何一行。地址只分两段：

偏移位数 = log₂(块大小) = log₂4 = 2；标签位数 = 地址位数 − 偏移位数 = 6 − 2 = 4（也等于 log₂(主存块数) = log₂16）。每行除了数据，还要存标签和替换用的 LRU 信息。讲义用 TSLR（time since last referenced，距上次访问的次数）记录 LRU：每访问一次，所有有效行的 TSLR 加 1，被访问的行清零；要替换时踢 TSLR 最大的那行。

判断 HIT 还是 MISS：每一步问三个问题

判断命中只看一件事：这个地址所在的"块"，此刻是不是在缓存里。和这个地址本身以前有没有被访问过无关。

1. 它属于哪个块？块大小 4 字节，块从 4 的倍数开始：块起点 = 地址 ÷ 4 取整再 × 4。例如 24 → 24–27，20 → 20–23，04 → 4–7，45 → 44–47。
2. 这个块现在在缓存里吗？全相联时，4 行里任何一行有它都算。
3. 在 → HIT，记下它刚被用过。不在 → MISS，把整块搬进来：有空行放空行；4 行都满了，踢掉最久没被用过的那一块（LRU）。

讲义例题逐步走：序列 24, 20, 04, 12, 20, 44, 04, 24, 44

表中括号里记的是这一块最后一次被用到是第几步，要踢的时候踢括号里数字最小的。

讲义里的 TSLR 记的是"距上次使用过了几次访问"，数字最大的就是最久没用的；上表记"最后使用在第几步"、取最小的。两种记法说的是同一件事，方向相反而已。

"在不在缓存里"到底怎么看

手算时，看你自己记下的缓存内容。缓存里有什么完全由前面的步骤决定，所以手算时每一步都要把当前缓存里的块记下来（上表最右一栏）。判断第 n 步时，只看第 n − 1 步那一行：要找的块在里面就是 HIT。例如第 8 步访问 24（块 24–27），第 7 步后缓存里是 44–47、20–23、4–7、12–15，没有 24–27，所以 MISS。

硬件上，比较标签（tag）。硬件不存"24–27"这种范围，而是在每一行存一个标签，再加一个有效位（这一行有没有装东西）：

1. 把地址拆开：本例地址 6 位，最低 2 位是偏移；全相联没有索引，高 4 位全是标签，标签其实就是块号。
2. 拿地址的标签和缓存里存的标签逐个比较。
3. 某一行标签相同且有效位为 1 → HIT；一个都不同 → MISS。空行有效位是 0，永远不会命中。

这也解释了 09 为什么在 08 之后命中：08 = 0010|00，09 = 0010|01，标签都是 0010，只是偏移不同。偏移只决定从块里取哪个字节，不影响命中判断。

缓存模拟器每一格里显示的就是存的标签（"tag 0101"），下方表格的"二进制拆分"一栏给出地址的标签，对照着看就能看清每一步在比什么。

8.4 直接映射：每个块只有一个家

全相联每次都要比较所有行，大缓存里还要维护 LRU，硬件代价高。直接映射（direct-mapped）让每个内存块只能放在固定的一行：用地址中间几位做索引（index）直接选行。

查找三步：用 index 选中一行 → 比较这一行存的 tag 和地址的 tag → 相同则命中，从行里按 offset 取字节；不同则缺失，从主存取块覆盖这一行。

同一个序列在直接映射下：24（行 10）、20（行 01）、04（行 01，踢掉 20）、12（行 11）、20（行 01，踢掉 04）、44（行 11，踢掉 12）、04（行 01，踢掉 20）、24 命中、44 命中，只有 2 次命中。20 和 04 都映射到行 01，互相把对方踢出去，这就是冲突缺失。

直接映射和全相联到底差在哪

两者看起来像：都要存标签、比标签，讲义例题结果也差不多（全相联 3 次命中，直接映射 2 次）。根本区别只有一个：一个块能放在哪里。

打个比方：直接映射像按学号尾号分配的储物柜，你的东西只能放 3 号柜，3 号柜被人占了就得把他的拿走，哪怕旁边柜子全空着；全相联像随便用哪个空柜子，空间利用最好，但找东西时要把所有柜子都看一遍。

一个差别很大的例子：主存 64 字节、块 4 字节、缓存 4 行，访问 0, 16, 0, 16, 0, 16。地址 0 是块 0，地址 16 是块 4，直接映射下行号都是 0 mod 4 = 4 mod 4 = 0，两块抢同一行。

直接映射另外 3 行从头到尾空着，两个块却在第 0 行来回互踢（冲突缺失，见 8.6 节）。两者真正结果一样的情况：访问的块刚好落在不同的行、彼此不冲突时；以及缓存只有 1 行时。两者都是组相联的特例：直接映射是每组 1 行（1 路），全相联是所有行一组。可以在下面的缓存模拟器里亲手试：主存 64、行数 4、块大小 4，序列填 0, 16, 0, 16, 0, 16，切换"直接映射"和"全相联"各运行一次对比。

8.5 组相联：两者的折中

k 路组相联（k-way set-associative）把缓存行分成若干组，每组 k 行。索引选中一组，块可以放在组内任意一行，组内满了按 LRU 替换。

讲义例题：4 行的 2 路组相联

把 4 行缓存两两分成一组：组 0 两行、组 1 两行。规则只有两条：每个块只能进一个固定的组（像直接映射）；进组之后组里两行随便放，组满了踢组里最久没用的那块（像全相联）。所以说它是两者的折中。

换个算法也一样：块号 = 地址 ÷ 4，组号 = 块号 mod 2，标签 = 块号 ÷ 2。所以有个好用的结论：块号是偶数进组 0，是奇数进组 1。Index 恰好就是块号的最低位。

20、04、12、44 四个块全挤进组 1，而组 1 只有 2 行；只有 24 进组 0。逐步走时，每一步先算组号，只在那个组里找。括号里是"最后一次被用到是第几步"，要踢时踢数字小的：

结果 2 次命中、7 次缺失：5 次是第一次访问（强制缺失），第 5、7 步是冲突缺失。讲义第 64 页把第 4 步（12 第一次被访问）标成 conflict，按定义应算 compulsory，口径问题同 8.3 节。

硬件上怎么判断命中：用 Index 位选出一组（例如 20 的 Index = 1，选组 1）；把地址的 Tag 和组内两行存的 Tag 同时比较，需要 2 个比较器（直接映射 1 个，全相联 4 个）；有一行相同且有效位为 1 就命中。缺失时每组用 1 个 LRU 位记住哪一路最近用过，决定踢谁。

一般来说，每组放几块？

要分清两件事：每组最多同时装几块是硬件定死的；主存里哪些块会被分到这一组由地址决定。

• 每组最多同时装 k 块，固定不变。k 路组相联每组有 k 行。本例 4 行 2 路：组数 = 4 ÷ 2 = 2，组 0、组 1 各 2 行，各自最多同时装 2 块。组与组之间不能互相借位。
• 主存的块平均分给各组，而且交替排列。组号 = 块号 mod 组数。主存 64 字节共 16 块，偶数块归组 0，奇数块归组 1，每组"负责" 8 个块，但同一时刻只有 2 个座位。
• 某次运行里各组实际装了几块，看访问序列。本例 1 块去组 0、4 块去组 1，所以组 1 挤得不停踢；如果顺序访问 0, 4, 8, 12, 16…，块号奇偶交替，两组会用得差不多平均。

Tutorial 8.8 有 4 组，组号是块号除以 4 的余数，不再是看奇偶。那题的块号 5、9、13、17 除以 4 都余 1，全进了组 1，和本例是同一种"挤在一组"的情况。

8.6 3C 缺失分类

冲突缺失到底是什么意思

缓存其实装得下，但映射规则规定这个块只能去某一行（或某一组），偏偏那里被别的块占了，只好把它踢出去；后来再访问被踢掉的块，就缺失了。一句话：不是缓存太小，是座位分配规则太死。

8.5 节的 2 路组相联例子里，第 5、7 步就是冲突缺失：第 4 步 12 进组 1 时把 20–23 踢掉，第 5 步再访问 20 就 MISS；第 5 步又把 4–7 踢掉，第 7 步访问 04 也 MISS。这两次缺失时组 0 都还空着一行，总容量是够的。

判断方法，按顺序问两步：

1. 这个块是第一次被访问吗？是 → 强制缺失，不管它有没有引起替换。
2. 不是第一次的话，换成同样行数的全相联缓存（也用 LRU）跑同一个序列，这一步会命中吗？会命中 → 冲突缺失（全相联装得下，是映射规则害的）；也缺失 → 容量缺失（缓存本身太小，怎么放都装不下）。

验证：全相联在第 4 步后装着 24–27、20–23、4–7、12–15，第 5 步访问 20 会命中，所以 2 路这里的缺失是冲突缺失。反过来，全相联自己第 8 步访问 24 缺失，它没有映射限制，只能怪 4 行装不下，所以是容量缺失。标准 3C 模型里每次缺失只归入一类。冲突缺失只出现在直接映射和组相联里，全相联没有冲突缺失；这也是提高相联度能降低缺失率的原因。

8.7 比较器的硬件代价

判断命中靠等值比较器：把存储的标签和地址标签逐位异或（XOR），全部为 0 且有效位为 1 才算命中。一个 T 位比较器需要 T 个 XOR（"位比较"）。

讲义例子：4 位标签、8 行。直接映射 1 个比较器、4 次位比较；全相联 8 个比较器、32 次位比较。注意同一个缓存换组织方式时 T 也会变（全相联没有索引位，标签最长），Tutorial 8.7 则直接给定了 T = 6。

9.1 减少缺失：容量与相联度

• 强制缺失：第一次访问，躲不掉；程序跑几百万条指令时，这部分可以忽略。
• 冲突缺失：办法 1 是加大缓存（每行被更少的地址共享），办法 2 是提高相联度（每组多几行）。
• 容量缺失：缓存装不下程序用到的所有块（例如缓存 64 KB、程序 64 MB），只能加大缓存。

讲义的统计图给了两条经验：缺失率随缓存变大和相联度变高而下降；4 路组相联的缺失率约等于两倍大的直接映射缓存。从直接映射到 2 路收益最大，在很多情况下缺失率能降 20% 以上；再往 4 路、8 路走，收益越来越小，而硬件复杂度和访问时间却在增加。

9.2 块大小的权衡

讲义演示：2 组、8 字节块的直接映射缓存，访问 24 时整个 24–31 块进入缓存，随后访问 28 直接命中，尽管 28 从没被访问过。这就是块大小带来的空间局部性收益。Tutorial 9.6 用一个只有一块的缓存把这个效果量化：块 8 B 时缺失率 50%，16 B 时 37.5%，32 B 时 25%。

9.3 地址位划分通用方法

缓存由三个参数决定：组数、相联度（每组块数）、块大小。

块数怎么算：容量 ÷ 块大小

块数就是缓存一共能放多少个块，也就是缓存有多少行。关键是先把两个数换成同一单位（字节），再写成 2 的幂。以 Exercise 9.1（32 KB 缓存、256 B 块）为例：

1. 把 32 KB 换成字节：1 KB = 1024 = 2¹⁰，32 = 2⁵，所以 32 KB = 2⁵ × 2¹⁰ = 2¹⁵ = 32768 字节。
2. 块大小写成 2 的幂：256 = 2⁸。
3. 2 的幂相除就是指数相减：2¹⁵ ÷ 2⁸ = 2⁷ = 128 块。直观地说，32768 字节的数据区切成每份 256 字节，正好 128 份，每份一行、放一个块。

后面几步都从这个 128 出发：Offset = log₂256 = 8（一块 256 字节，编号 0–255 要 8 位）；组数 = 128 ÷ 相联度（直接映射 128、4 路 32、全相联 1）；Index = 7、5、0；Tag = 32 − Index − 8 = 17、19、24。

有了这张表，"容量 ÷ 块大小"就是指数相减：64 KB ÷ 64 B = 2¹⁶⁻⁶ = 1024 块（T9.5）；256 KB ÷ 64 B = 2¹⁸⁻⁶ = 4096 块（T8.5）。

Offset 选块内字节，Index 选组，Tag 确认组里存的是不是要找的块。讲义两个例子（32 位地址、64 KB、32 B 块）：

9.4 写策略：主存怎么拿到正确的值

写和读不一样：写不一定要让 CPU 等（可以用写缓冲），但写会修改缓存，于是缓存和主存可能暂时存着同一数据的不同版本；有些 I/O 设备（DMA）还会绕过缓存直接读主存。四种机制：

为什么"写"会带来麻烦

读只是把数据复制一份到缓存，缓存和主存内容一样，不会出问题。写会改值：缓存里有块 100–103 = A B C D，主存也是 A B C D；CPU 把 X 写到 101，缓存那份变成 A X C D，主存那份改不改？不改的话，同一个地址在两处就是两个不同的值。主存的值在这几种时候要紧：

• 块被踢出缓存时：缓存里的新值若没写回主存，就永远丢了。
• I/O 设备（DMA）直接读主存时：它绕过缓存，会读到旧值。
• 多核时：别的核读到的也可能是旧值。

写策略要解决的就是"什么时候、怎么把新值交给主存"。

写命中：写直达 vs 写回，逐步对比

"写命中"指要写的块已经在缓存里。依次执行 Store X → 101、Store Y → 102、Store Z → 101，最后这个块被替换出缓存（Tutorial 9.4）：

• 写直达（write-through）：每次写，缓存和主存同时更新。好处是主存永远最新、简单可靠，块被踢时直接丢掉；坏处是每次写都要访问慢速的主存，流量大。上例写了 3 次主存，第一次写的 X 后来还被 Z 覆盖，等于白写。
• 写回（write-back）：写的时候只改缓存，等这个块被踢出缓存时才一次性写回主存。好处是同一块的多次写合并成一次，流量小、速度快（上例 X 根本没写到主存）；坏处是主存有一段时间是旧的，控制更复杂，踢块时若要先写回会多花时间。

脏位（dirty bit）是什么

脏位是缓存每一行上额外的 1 个比特，标记"这一行被改过没有"。"脏"的意思是这份副本已经被改动，和主存里的原件不一样了。

• 每一行（每个块）1 位，不是每个字节 1 位。块里哪怕只改了一个字节，整行就算脏，写回时整块一起写。
• 什么时候变：块从主存搬进缓存时 D = 0；对这一行写（store）时 D = 1；只读不改变 D；被踢出时看 D 决定要不要写回。
• 只有写回策略才需要脏位：写回在写时不改主存，必须记住哪些行的主存副本已经过期。只读过的块 D 一直是 0，踢出时不用白写一次主存，这也是写回省流量的地方。写直达每次都同时改主存，行永远是"干净"的，不需要脏位。
• T9.4(c) 问每次操作后的脏位：初始 0，三次写之后都是 1、1、1，直到块被写回、踢出。

写缓冲：让写直达不那么慢

写和读不一样：读时 CPU 必须拿到数据才能继续算；写时 CPU 不需要拿回任何东西。所以可以加一个小队列：CPU 把"地址 + 数据"往缓冲里一放就继续执行，缓冲在后台慢慢写进主存，好比把信投进邮筒就走，不用等邮递员送到。只有缓冲满了（写得太快，主存来不及消化），CPU 才要停下来等。写缓冲通常和写直达搭配。

缓存一致性是多核的问题：每个核有自己的缓存，核 1 改了 x，核 2 缓存里还是旧的 x，需要 MESI（Modified / Exclusive / Shared / Invalid）这类协议来通知和作废旧副本。讲义说超出本课程范围，知道名字即可。

写缺失时怎么办

写缺失：要写的地址所在的块不在缓存里。例如执行 Store X → 205，块 204–207 不在缓存里，有两种处理：

数主存被写了几次：写直达 = 写的次数；写回 = 被踢出时脏块的个数。

9.5 缺失代价被 CPU 放大

改进缓存性能有三个方向：降低命中时间、降低缺失率、降低缺失代价。讲义用一个例子说明为什么 CPU 越快，缓存越重要。

超标量处理器每拍可以完成多条指令，CPI_ideal 可以小于 1。另一种情况是时钟频率翻倍而内存不变：同样 50 ns 的主存访问现在要花两倍的周期数，MP 从 100 变成 200，停顿变成 4 + 2.88 = 6.88，CPI = 8.88。内存延迟本身没变，但 CPU 每次缺失等待的周期数翻倍。

9.6 多级缓存 公式不考

只有一级缓存时，L1 缺失就得直接去主存，一次要等 100 个周期；L1 又不能做大，做大了就变慢。办法是在 L1 和主存之间再加一层更大一点、稍慢一点的 L2（芯片面积够时还有 L3）：

• L1 缺失先找 L2：L2 有，只付 L2 的时间（比如 19 或 25 周期），不用去主存；L2 也没有，才去主存。
• L2 通常是统一缓存：指令和数据共用一个 L2；L1 则分成指令缓存和数据缓存两个。

下面所有公式都从一个办法推出来：数一数一共多少次访问、每次花多少时间，加起来再除以访问次数。

用 1000 次访问数一遍（Tutorial 9.3 的数据）

L1 命中 1 周期、缺失率 5%；L2 命中 19 周期、缺失率 2%；从主存取一块 50 周期。CPU 一共发出 N = 1000 次访问：

平均每次访问 = 2000 ÷ 1000 = 2 周期，这就是 AMAT。把这张表写成公式：

括号里正好是 L2 自己的 AMAT：L1 一旦缺失，平均还要再花 20 个周期才能拿到数据。所以"L1 的缺失代价就是 L2 的平均访问时间"。公式和一级缓存完全一样，只是 L1 的缺失代价不再是主存时间。这就是 Tutorial 9.3(a)(b)：AMAT_L2 = 20，AMAT_L1 = 2。

局部缺失率 vs 全局缺失率

还是那 1000 次访问：L1 缺失 50 次，L2 缺失 1 次。

• 对 L1 两者一样，因为所有访问都先到 L1；对 L2 差别很大，L2 只看得到 L1 漏下来的那 50 次。
• 全局 = 局部₁ × 局部₂ = 5% × 2% = 0.1%（讲义写作 n1/N × n2/n1 = n2/N）：CPU 的所有访问里，最终有多少要跑到主存。
• L2 的局部缺失率常常看起来不低，因为它接到的都是 L1 搞不定的"难"访问，不代表 L2 没用。衡量 L2 的效果要看全局缺失率。

讲义的 CPI 例子，逐项拆开

接着 9.5 节：理想 CPI 2，load/store 36%，L1 指令缓存缺失率 2%、数据缓存 4%。L1 缺失后去 L2 要 25 周期；加了 L2 之后，只有 0.5% 的访问最终去主存（全局缺失率），去主存 100 周期。每次访存的平均停顿分两部分：

省在哪里：原来每次 L1 缺失都要等 100 周期；现在大部分 L1 缺失在 L2 就解决了，只付 25 周期，只有 0.5% 的访问还要付 100 周期。

读法：越往下越大（L2 比 L1 大十几到上百倍）、越慢、块越大；L1 的缺失代价是去 L2 的时间，L2 的缺失代价是去主存的时间；L2 一栏写的是全局缺失率，所以数字很小。

9.7 虚拟内存与 TLB 不考

先抓住一句话：程序用的地址是"假的"（虚拟地址），每次访存前都要翻译成"真的"（物理地址）。TLB 是为了让这个翻译变快而加的小缓存。

为什么需要虚拟内存

电脑里同时跑着几十个程序，共用一块物理内存。如果每个程序直接用物理地址：程序得知道自己被放在内存哪里，两个程序都想用地址 1000 就打架；程序比内存大就没法运行；一个程序写错地址，可能改坏别的程序甚至操作系统。

虚拟内存是一层间接映射：每个程序都以为自己独占一整片从 0 开始的地址空间（32 位就是 4 GB），程序里写的都是虚拟地址，由硬件和操作系统偷偷翻译成物理地址。讲义列的三个问题就这样解决了：

分页：按"页"来翻译

一个字节一个字节地翻译太费，所以把内存切成固定大小的页（page），常见是 4 KB。翻译只管"哪一页"，页内第几个字节原样保留：

Tutorial 9.7：32 位虚拟地址、30 位物理地址、4 KB 页 → 偏移 log₂4096 = 12 位，VPN = 32 − 12 = 20 位，PPN = 30 − 12 = 18 位。

为什么要有 VPN 和 PPN 两个编号

一句话：VPN 是"程序以为的页号"，PPN 是"这一页在内存条上实际的位置"，页表负责把前者换成后者。

为什么不能只用一个编号？因为"程序以为的位置"和"实际放的位置"本来就不一样，而且必须允许它们不一样：

1. 程序不用管自己被放在哪：A、B 都从第 0 页开始写代码，操作系统放到哪都行，A 的连续几页在内存里可以东一块西一块（7、2）。
2. 同样的 VPN 互不干扰：A 的第 0 页和 B 的第 0 页翻译到不同的 PPN（7 和 5），彼此看不到对方，这就是隔离和保护。
3. 不是每一页都要在内存里：A 的第 2 页可以暂时在磁盘上，用到时才调进来。

如果程序直接用物理页号，这三点都做不到。打个比方：订酒店时确认单写"你的第 1 间房"（VPN），每个客人都从 1 开始编；前台的分配表（页表）写着"张三的第 1 间 = 512 号房"，512 是真实房号（PPN）；房间里的床位号就像页内偏移，不需要翻译。

虚拟地址位数、物理地址位数和页的关系

关键只有一点：虚拟页和物理页一样大，所以两边的偏移位数相同，虚拟地址和物理地址的位数差全部落在页号上。

物理页只有虚拟页的 1/4：一个程序的 4 GB 空间如果全用满，最多只有 1/4 能同时待在内存里，其余只能放在磁盘上，用到时再调进来。这就是有些页表项有效位为 0、会发生页缺失的根本原因：虚拟空间比物理内存大，装不下。这也说明了页表为什么在主存里：每个程序的页表有 2²⁰ 项，按每项 4 字节算就要 4 MB，芯片里放不下；每次都去主存查又太慢，所以要有 TLB。

做题步骤：① 偏移 = log₂(页大小)，两边相同；② VPN = 虚拟地址位 − 偏移，PPN = 物理地址位 − 偏移；③ 翻译时把 VPN 换成 PPN、偏移照抄，结果自然是物理地址的位数。

页表与地址翻译

页表（page table）存放在主存里，每个程序一张，每一项记录一个虚拟页。真实的页表项还有脏位、引用位（用来近似 LRU）和访问权限（只读、可写等）。Tutorial 9.7 的页表：

翻译 0x12345678：

1. 4 KB 页的偏移是 12 位，正好是最后 3 个十六进制位：偏移 = 678，VPN = 12345。
2. 查页表：VPN 0x12345 → PPN 0x1A234，有效位 1。
3. 拼起来：物理地址 = 0x1A234 拼接 678 = 0x1A234678。

同理 0x12346ABC → 0x0B567ABC，0xABCDEFFF → 0x1F890FFF。偏移为什么不变：虚拟页和物理页大小一样、都按页对齐，翻译只是把"第几页"换掉，字节在页里的位置不变。

页表里的有效位是什么

有效位回答一个问题：这一个虚拟页现在在不在物理内存里，也就是这一行写的 PPN 能不能用。

• 为什么需要它：PPN 字段里总会有某个二进制数，没有有效位的话，硬件分不清它是真的物理页号还是没用的旧值。有效位是给硬件看的开关：只有它是 1，才相信这一行的 PPN。
• 什么时候变：操作系统把一页从磁盘调进内存时，填好 PPN、有效位置 1；内存不够、把某一页换出到磁盘时，有效位置 0（这一页在磁盘的位置由操作系统另外记录）。
• Tutorial 9.7(c)：访问 0x22222000，VPN 0x22222 的有效位是 0 → 硬件不用这一行的 PPN，触发页缺失 → 操作系统调页、填 PPN、置 1 → 重新执行指令。

页缺失（page fault）

访问 0x22222000 时，VPN = 0x22222，页表有效位是 0，这一页不在内存里，就是页缺失：

1. 硬件发现有效位为 0，触发异常（精确中断），交给操作系统。
2. 操作系统从磁盘把这一页读进某个空闲物理页（内存满了就先换出一页）。
3. 填好页表：写上 PPN，有效位置 1。
4. 回到那条指令重新执行，这次就能翻译成功。

磁盘太慢，一次页缺失要几毫秒，也就是几百万个周期。有效位的作用：标记"这一项的翻译能不能用"，防止用到无效的 PPN。

和缓存对比：同一套思路，换了一层

块放哪、怎么找、缺失时替换谁、写怎么处理，这四个问题对缓存、TLB、虚拟内存都适用，区别只在参数。缺失代价越大，就越值得用更聪明但更贵的办法，所以虚拟内存选全相联加写回。

TLB：翻译结果的"缓存"

问题：页表在主存里，CPU 每次读写内存都得先去主存读一次页表项才知道物理地址，访存次数直接翻倍。解决办法是 TLB（Translation Lookaside Buffer，快表）：CPU 里一个很小、很快的缓存，专门存最近用过的几条翻译（VPN → PPN）。一般不超过 128–256 项，比数据缓存还快；和普通缓存一样可以是全相联、组相联或直接映射。每项含有效位、VPN（当作标签）、PPN、脏位、引用位、访问权限。

CPU 发出虚拟地址
   │
   ├─ 查 TLB ── 命中 ──→ 直接得到物理地址 → 去缓存/主存取数据     （最常见，几乎不花时间）
   │
   └─ TLB 缺失 → 去主存读页表
                 ├─ 有效位 = 1 → 把这条翻译装进 TLB，重试       （几十个周期）
                 └─ 有效位 = 0 → 页缺失，操作系统从磁盘调页     （几百万个周期）

• TLB 缺失不等于页缺失。TLB 缺失经常发生，大多数时候页其实就在内存里，比页缺失频繁得多。Tutorial 9.7(f)：页缺失 5 ms、TLB 缺失 50 ns，前者是后者的 5×10⁻³ ÷ 5×10⁻⁸ = 100,000 倍。
• TLB 这么小也管用，靠的还是局部性。一页 4 KB 能装 1024 个 4 字节数据，顺序访问一个数组时连续上千次访问都落在同一页，第一次查到之后全部 TLB 命中。
• 软硬件分工（讲义）：TLB 是硬件，TLB 访问时间算在缓存命中时间里（流水线可能为它多留一级）；页缺失触发精确中断，由操作系统处理；硬件负责更新页表里的脏位和引用位。

例题：一次走完 TLB 命中、TLB 缺失和页缺失

在 9.3 节的"地址拆分器"里切到"虚拟地址"标签，点"9.7 节例题"预设，也可以逐个检查这道题每个地址的拆分和翻译（那个工具只查页表，不模拟 TLB；0x1234 会显示页缺失，因为它用的是调页之前的页表）。

10.1 延迟、吞吐与关键路径

• 延迟（latency）：一个工作单位从进入系统到完成所需的时间。
• 吞吐量（throughput）：单位时间内系统能完成的工作单位数。
• 并行的目标：提高吞吐量；有时也能降低延迟。

组合电路的延迟由关键路径决定：从输入到输出所有路径中门延迟之和最大的那条。讲义的 1 位全加器：AND、OR、非门各 t_g，XOR 为 3t_g，关键路径 A → XOR → XOR → S，延迟 6t_g，吞吐量 = 每 6t_g 完成一次加法 = 1/(6t_g)。

10.2 空间并行 vs 时间并行

• 空间并行：多套硬件同时工作，同时处理多个任务。通常直接叫"并行"。
• 时间并行：把任务切成几级（像流水线工厂），不同任务同时处在不同级，执行在时间上重叠。这就是流水线。

讲义的饼干例子：擀饼干 5 分钟，烤 15 分钟。一盘的延迟永远是 20 分钟（1/3 小时），不管用哪种并行。

讲义说本课重点放在流水线，因为它是 CPU 设计的基础，又能自然引出 CPI、冒险这些概念；空间并行还牵涉同步、通信、内存一致性，复杂得多。

10.3 流水线总时间公式

洗衣房例子：4 个人各有一筐衣服，洗 30 分钟、烘 40 分钟、叠 20 分钟。顺序做要 4 × 90 = 360 分钟（6 小时）。流水起来，一台机器空出来就接下一筐：

如果每级时间相同、各占 1 个周期，k 级流水线处理 n 个任务需要 k + n − 1 个周期（Tutorial 10.1：第一个任务 k 个周期出来，之后每周期出一个）。

流水线的几条结论

• 流水线不降低单个任务的延迟，提高的是整批工作的吞吐量。
• 吞吐量受最慢的一级限制。
• 理论最大加速比约等于级数；各级时间不均衡会降低加速比。
• 填充（filling）和排空（draining）流水线的时间也会拉低加速比，任务越多这部分影响越小。

10.4 单周期 vs 流水线处理器

讲义的五级时间：取指 250 ps、译码读寄存器 150、执行 200、访存 250、写寄存器 100。

Tutorial 10.7(d) 问"流水线的单条延迟更长，所以流水线更慢"对不对：不对。延迟只描述一条指令，处理器跑的是成千上万条指令的程序，决定程序运行时间的是吞吐量。

10.5 DLX 寄存器、数据类型与指令

DLX（读作 "deluxe"）是教学用的简化 RISC 处理器，结构和 MIPS 很像，五级流水线：取指、译码、执行、访存、写回。和 MIPS 相比，DLX 指令更少、寻址模式更简单，冒险处理也用教学化的例子。

• 32 个 32 位通用寄存器 R0–R31。R0 恒为 0（只读，写它无效）；R31 是链接寄存器，JAL/JALR 把返回地址存在这里。
• 数据类型：整数 B（8 位字节）、H（16 位半字）、W（32 位字），U 表示无符号；浮点 F（32 位单精度）、D（64 位双精度）；HI/LO 存放扩展结果的高、低 32 位。
• 立即数是 16 位，嵌在 I 型指令里（ADDI、LW 等）。

位操作例子：R1 = 10110011₂，ANDI R2, R1, #254（掩码 11111110）清第 0 位 → 10110010；ORI R2, R2, #8 置第 3 位 → 10111010；XORI R2, R2, #2 翻转第 1 位 → 10111000。

函数调用：JAL SUM 先存 R31 ← PC + 4 再跳到 SUM，函数结尾 JR R31 回到 JAL 的下一条。JALR 用于函数指针、虚函数这类运行时才确定目标的调用。

10.6 寻址模式与 load-store 架构

注意存数指令有两种写法：讲义写 SW R4, 400(R3)，Tutorial 写 SW 20(R2), R3（经典 DLX 语法）。两者意思相同：把寄存器的值存到"基址 + 偏移"处。

10.7 R / I / J 三种指令格式

11.1 五个步骤的微操作

讲义的 MEM 例子：SW R3, 500(R4)，R4 = 100、R3 = 99：EX 算出 ALUOut = 600，MEM 执行 Mem[600] ← 99。LW R1, 30(R2)，R2 = 100、Mem[130] = 55：ALUOut = 130，LMD = 55。BEQZ R4, LOOP，R4 = 0、NPC = 104、偏移 40：ALUOut = 144，Cond = 1，MEM 阶段 PC ← 144。

11.2 补码与符号扩展

I 型指令的立即数只有 16 位，进 ALU 前要扩展成 32 位。符号扩展就是把第 15 位（符号位）复制到高 16 位：正数前面补 0，负数前面补 1，数值不变。

Tutorial 11.2 用的就是 ADDI R5, R2, #-12（R2 = 40）：A = 40，Imm = −12（0xFFFFFFF4），ALUOut = 40 + (−12) = 28，WB 写 R5 ← 28。在下面的实验里选这个预设，可以看到每一位。

11.3 为什么所有指令都要经过 MEM

所以第 4 步全名叫"Memory Access / Branch Completion"。DLX 流水线是固定五级结构，每条指令都占用这一级，即使什么都不做。

11.4 非流水 DLX 的 CPI

非流水实现中，每一步用一个时钟周期，用 NPC、IR、A、B、Imm、Cond、ALUOut、LMD 这些临时寄存器保存步与步之间的中间结果。不需要 WB 的指令可以少一个周期：

11.5 流水线寄存器 F/D · D/A · A/M · M/W

流水化以后，原来的临时寄存器变成四组级间缓冲（inter-stage buffer），用边沿触发寄存器实现：时钟沿到来时锁存输入，保持到下一个时钟沿。这样每一级在一个周期结束时把结果交给下一级，多条指令才能同时在流水线里走而互不干扰。讲义类比的器件是 74LS374 边沿触发 D 锁存器。

11.6 流水线性能与要点

理想情况下五级流水线每个周期完成一条指令，CPI = 1。讲义例子：非流水 DLX 时钟 1 ns，ALU 指令 4 周期（40%）、分支 4 周期（20%）、访存指令 5 周期（40%）；流水化额外增加 0.1 ns 时钟开销（寄存器延迟、时钟偏移）。

• 流水线提高的是吞吐量，不减少单条指令的延迟。
• 单端口存储器里，取指（IF）和访存（MEM）要同时用存储器，不同指令会抢同一资源，这就是结构冒险，需要停顿。
• 实际流水线因为冒险，CPI > 1。三类冒险是 Lesson 12 的内容。

12.1 三类冒险与 CPI

例：10% 的指令停顿 1 周期。加权平均 0.9 × 1 + 0.1 × 2 = 1.1，或者 1 + 0.1 × 1 = 1.1，两种算法一样。加速比 5 / 1.1 = 4.54，比理想的 5 低。

12.2 结构冒险

两条或更多指令在同一周期要用同一个硬件资源，资源又不能同时满足，就是结构冒险。例子：寄存器堆只有一个写端口；指令和数据共用一个单端口存储器。解决方法：停顿到资源空出来，或者复制资源（双端口存储器有两套独立的地址、数据和控制信号，一个端口给 IF，一个给 MEM，冲突就消失了）。

讲义例子：LOAD 在第 4 周期处于 MEM，此时第 4 条指令正要 IF，两者都要访问存储器，只能让取指晚一拍。

结论：消除结构冒险往往比小幅提高主频更划算。

12.3 数据冒险：RAW / WAR / WAW

流水线改变了对操作数的读写顺序，如果和顺序执行时的顺序不一致，指令就可能用到错误的值。设指令 i 在前、j 在后：

WAR 和 WAW 在指令延迟不等、乱序执行、超标量处理器里才会出现（例如 ADD 比 LW 先到写回级，LW 后写反而覆盖了 ADD 的结果）。讲义把它们列出来是为了完整。

12.4 寄存器分半周期与转发

序列 ADD R1,R2,R3 后面跟着 SUB R4,R1,R5、AND R6,R1,R7、OR R8,R1,R9、XOR R10,R1,R11。ADD 在第 5 周期（WB）才写 R1：

• 寄存器堆分半周期：一个周期内前半写、后半读。所以和 WB 同一周期的 ID 能读到新值。
• SUB 在第 3 周期读 R1、AND 在第 4 周期读 → 都读到旧值，有冒险。
• OR 在第 5 周期的后半读，正好拿到 ADD 前半写进去的新值 → 无冒险。XOR 更晚，也没问题。
• 结论：没有转发时，只有紧跟其后的两条指令需要停顿。

转发（forwarding，也叫旁路 bypassing）：结果其实在 EX 结束时就已经算出来了，没必要等写回寄存器堆。把 EX/MEM（A/M）和 MEM/WB（M/W）流水线寄存器里的值直接送回 ALU 输入端：

• 硬件：在 ALU 每个输入前加一个 MUX，加上从 EX/MEM、MEM/WB 回来的通路，再加冒险检测逻辑来选输入。
• 正常情况选寄存器堆读出的值；检测到冒险就选转发来的值。
• ADD → SUB、SUB → AND 这类 ALU 到 ALU 的 RAW 全部可以零停顿解决。紧挨着的那条从 EX/MEM 拿值（Exercise 12.10 选 B）。

12.5 Load-use 冒险与硬件互锁

转发不能解决所有 RAW。LW R1,0(R2) 的数据要到 MEM 结束才从存储器读出来，而紧跟的 SUB R4,R1,R6 在下一个周期的 EX 开始就要用，时间上往回倒了，转发也来不及。

硬件流水线互锁（interlock）检测到这种冒险后自动停顿流水线，插入一个气泡（NOP），依赖指令和后面所有指令都推迟一拍，正确性由硬件保证，不需要软件介入：

12.6 编译器调度消除停顿

与其让硬件停顿，不如让编译器把不相关的指令挪进停顿的位置，让 CPU 在等数据的那一拍干点有用的活。只要被移动的指令和周围没有依赖，程序结果就不变。

调度后 ADD 距离 LW Rc 隔了一条，SUB 距离 LW Rf 也隔了一条，两次 load-use 停顿都消失了，不需要额外硬件。

12.7 控制冒险

原始 DLX 在 EX 级才算出分支目标和判断条件。等结果出来时，后面已经有三条顺序指令进了流水线；如果分支跳转，这些指令都不该执行。最简单的办法是停顿：

实测统计：条件分支约占指令的 14–16%；向前分支约 60% 跳转，向后分支（循环）约 85% 跳转，整体约 67% 跳转。分支又多又常跳，所以值得做预测。

12.8 四种分支处理方案

填延迟槽的三种来源

Tutorial 12.3 是一个带修改的 from-before 例子：循环里把 SW 200(R3),R2 挪到 BNEZ 后面的槽里，但它前面的 SUBI R3,R3,#4 已经把 R3 减了 4，所以偏移要改成 SW 204(R3),R2 才能存到原来的地址。

可取消分支（canceling / nullifying branch）：编译器同时给出预测方向，预测对了槽里的指令正常执行，预测错了就把它当 NOP 作废，不会产生错误结果。延迟槽的问题是合适的指令常常找不到、from target / fall-through 不一定安全、流水线一深就要填好几个槽，所以现代 CPU 改用硬件动态分支预测：猜对零代价，猜错冲刷流水线重来。