照着真题的骨架，
把每个考点再打一遍

(i) CMOS 天生只能直接做反相逻辑，所以正确做法是先做 NOR3，再串一级反相器：

• NOR3 的下拉网络：3 个 NMOS 并联接到 GND——任何一个输入为 1，输出就被拉低到 0。
• NOR3 的上拉网络：3 个 PMOS 串联接到 VDD——只有三个输入全为 0 时才导通，输出被拉高到 1。
• 这 6 个管子构成 NOR3，输出接一个反相器（1 PMOS + 1 NMOS）得到 OR3。

(ii) 两个 2 输入 OR 级联的代价：每个 OR2 = NOR2(4 管) + NOT(2 管) = 6 管，两个就是 12 管；信号要依次穿过 NOR→NOT→NOR→NOT，共 4 级门延迟。

所以更省面积、更省功耗，而且快一倍。

直接做意味着 NOR32：下拉是 32 个 NMOS 并联，上拉是 32 个 PMOS 串联。问题集中在串联这一侧：

• 上拉电阻是单管的 32 倍，输出从 0 翻到 1 的时间被拉长几十倍——整个门的延迟完全由这条路径决定，慢到不可用。
• 面积暴涨：为了把上拉速度补回来，每个串联 PMOS 都得做得很宽，而 PMOS 本来就需要比 NMOS 更大的宽度才能达到同样驱动力。
• 输入电容变大：每个输入要驱动一个 NMOS 加一个（被加宽的）PMOS 的栅极，前一级的负载因此变重——大扇入直接转化成上一级的大扇出负担。
• 体效应（body effect）：串联链中间的管子源极电位被抬高，阈值电压上升，导通能力进一步变差，越靠上越慢。
• 并联侧的漏电流叠加：32 个 NMOS 的亚阈值漏电加在一起，静态功耗上升、噪声容限下降。

用多级小扇入的门拼出来。例如四输入一组：8 个 NOR4 → 结果再送进 2 个 NAND4 → 再一个 NOR2 …… 每个门的扇入都只有 4，各自都很快；而总延迟从"一级但极慢"变成 log₄32 ≈ 2–3 级正常速度的门。

这就是模块 05 讲快加法器时同一条原则的另一次应用：把 Θ(n) 的串联结构换成 Θ(log n) 的树形结构。

2 选 1：输入 W、X，控制位 S。

• TG₁ 接在 W 与输出之间，NMOS 栅极接 S′、PMOS 栅极接 S ⇒ S=0 时导通；
• TG₂ 接在 X 与输出之间，栅极接法相反 ⇒ S=1 时导通；
• 一个 NOT 门产生 S′。两个 TG 的输出直接短接——控制互补，任意时刻恰好一条通路导通，不会冲突。

8 选 1：控制位 A、B、C（A 为最高位）。摆成三层二叉树：

第 1 层：4 个 2:1 MUX，全部由 C 控制 → 把 8 路收成 4 路
第 2 层：2 个 2:1 MUX，全部由 B 控制 → 收成 2 路
第 3 层：1 个 2:1 MUX，由 A 控制       → 收成 1 路

传播延迟：信号要穿过 3 层传输门 = 3 级门延迟。生成 A′/B′/C′ 的 NOT 门与数据路径并行，只在最开始加 1 级，所以从控制信号稳定算起总延迟约 4 级门。

64 位宽：唯一的瓶颈是控制信号的扇出

64 位就是把上面这个 1 位选择器原样复制 64 份并排放，第 i 份负责第 i 位。数据线完全各走各的——某一路输入的第 i 位只进第 i 份切片，扇出 = 1，毫无问题。

麻烦只出在 A、B、C 三根控制线上：64 份切片共用同一组控制信号，直接连的话一根线要带 64 个负载，扇出 = 64 ≫ 8。

第 1 层： A 驱动 8 个 NOT 门        → 得到 8 份 A′   （A 的扇出 = 8 ✓）
第 2 层： 每份 A′ 各驱动 8 个 NOT → 得到 64 份 A（每个门扇出 = 8 ✓）
叶　子： 每份 A 各带 1 个切片            （扇出 = 1 ✓）

8 × 8 = 64 —— 一层不够、三层多余，正好两层。

还有个漂亮的副产品：两层 = 偶数次取反，极性自动还原，叶子拿到的正好还是 A 本身，不需要再额外配缓冲器。A′ 则在每个切片内部用一个本地 NOT 门生成（它的扇出只有切片里那几个传输门，完全合规）。

为什么每一层必须是 NOT 门——"隔离"到底在隔离什么

这是这道题真正的考点，必须答出来：

• 传输门是无源开关，自己不产生任何驱动力。它导通时只是把输入端和输出端连通，输出的驱动能力完全来自上游那个源。
• 所以让一根线直接挂 64 个传输门的栅极，就是把 64 个栅电容全部叠加在同一个节点上——上升/下降沿会被拖得又平又慢，严重时下游根本判不出高低电平。
• NOT 门是有源 CMOS 门：它不转发输入的电流，而是从 VDD / GND 重新取电流去驱动下一级，顺手把被拖平的边沿恢复成满幅度、陡边沿。
• 这就是"隔离"的含义——把"1 个源带 64 个负载"这件做不到的事，拆成三级"1 个源带 8 个负载"，每一级都由一个全新的驱动器重新发力。

传播延迟

控制路径 = 2（缓冲树两层）+ 1（切片内本地生成 A′/B′/C′） = 3 门延迟
数据路径 = 3 层传输门                                        = 3 门延迟
                                              总计 = 6 个门延迟

（若是 4 选 1，数据路径只有 2 层传输门，总计就是 5 个门延迟。）

扇入检查：NOT 门扇入 1；传输门只有 1 个数据输入；2 选 1 MUX 的输出节点上并接 2 个传输门——全部 ≤ 8 ✓

这类题有一套完全机械的五步流程，照做即可，不需要任何灵感。

第 1 步 · 把状态图抄成次态真值表

三个触发器的输出就是 X、Y、Z（当前态）；要求的是它们的次态 X′、Y′、Z′。状态图里没出现的状态（001、010、100）标成无关项 d——这是关键，它给了化简的自由度。

第 2 步 · 对每一位次态单独化简

X′：只有在 111 时为 0，其余有定义的行全是 1。把三个无关项都取 1，得到最简形式：

X′ = ¬( X · Y · Z )        // 一个 3 输入 NAND 门

Y′：看有定义的五行——000→0、011→0、101→1、110→1、111→1。观察到它每次都等于当前的 X：

Y′ = X                     // 根本不需要门，一根导线

Z′：只有 101 这一行为 0。若把无关项 001 也取 0，两者可以合并成同一项 ¬Y·Z：

Z′ = ¬( ¬Y · Z ) = Y + ¬Z  // 一个 NOT 门 + 一个 OR 门

第 3 步 · 接线

三个 D 触发器共享同一个时钟。把上面三个表达式的输出分别接到对应触发器的 D 端，触发器的 Q 端就是 X、Y、Z，同时反馈回组合逻辑。

第 4 步 · 验证（一定要写在卷子上）

(i) sltiu $9, $5, −1　I 型，opcode = 001011。格式是 sltiu $rt, $rs, imm，所以 rt = $9、rs = $5。

opcode  rs      rt      immediate
001011  00101   01001   1111111111111111    // −1 的 16 位补码 = 0xFFFF

→ 0010 1100 1010 1001 1111 1111 1111 1111

(ii) srav $7, $8, $3　R 型，opcode = 000000，funct = 000111。格式是 srav $rd, $rt, $rs，所以 rd = $7、rt = $8、rs = $3（rs 提供移位量）。

opcode  rs      rt      rd      shamt   funct
000000  00011   01000   00111   00000   000111

→ 0000 0000 0110 1000 0011 1000 0000 0111

注意两点：shamt 必须填 0（移位量来自寄存器，不用这个字段）；而且 srav 的汇编书写顺序是 rd, rt, rs，和编码顺序 rs, rt, rd 正好是反的——这是最高频的失分点。

解码的固定第一步：展开成二进制，取最前面 6 位看 opcode，由它决定后面 26 位怎么切。

(i) 0x01095022

0000 0001 0000 1001 0101 0000 0010 0010

opcode = 000000  → R 型，看最后 6 位
rs     = 01000   = 8   → $8
rt     = 01001   = 9   → $9
rd     = 01010   = 10  → $10
shamt  = 00000
funct  = 100010  → sub

(ii) 0xae2b0010

1010 1110 0010 1011 0000 0000 0001 0000

opcode = 101011  → sw，I 型
rs     = 10001   = 17  → $17（基址）
rt     = 01011   = 11  → $11（要存的数据）
imm    = 0000000000010000 = 16（最高位是 0，正数）

(iii) 0x0c100004

0000 1100 0001 0000 0000 0000 0000 0100

opcode = 000011  → jal，J 型
address 字段（剩余 26 位）= 00 0001 0000 0000 0000 0000 0100 = 1048580

J 型存的是目标地址右移 2 位之后的值，所以实际跳转目标 = 1048580 × 4 = 4194320 = 0x00400010。

(i) 根本矛盾：立即数字段只有 16 位，寄存器却是 32 位。

I 型指令的 immediate 字段固定 16 位，所以任何单条指令最多只能携带 16 位的常数信息。逐个看现有手段：

• addi $t, $0, imm：符号扩展，只能得到 [−32768, 32767] 范围内的值；
• ori $t, $0, imm：零扩展，只能得到 [0, 65535] 范围内的值。

两者都覆盖不到需要高 16 位的常数。没有 lui 时并非完全做不到——可以借助移位拼三条：

ori $t, $0, 0x1234     // $t = 0x00001234
sll $t, $t, 16         // $t = 0x12340000
ori $t, $t, 0x5678     // $t = 0x12345678

所以准确的说法是：没有 lui 要花三条指令，有了 lui 只要两条。装载 32 位常数在真实代码里极其频繁（每个全局变量地址、每个大立即数都要），省下的这一条指令是实打实的。

(ii) 标准两条指令写法：

lui $t, 0x1234         // $t = 0x12340000，低 16 位自动补 0
ori $t, $t, 0x5678     // $t = 0x12345678

如果低 16 位的最高位是 1，addi 会把它当成负数，向高位借位，把 lui 刚放好的高 16 位改掉。举个会出错的例子——要装载 0x1234FFFF：

两个原因叠加：ori 用零扩展（不会把高位污染成全 1），而且是按位或（不会产生进位）。高低两半因此完全独立。

解这类题的唯一方法是画出每条指令的开始周期。设第一条 M/D 在周期 0 开始，则它的结果在周期 30 可用。每条指令的开始时刻 = max(前一条指令开始 + 1, 该指令自身的依赖就绪时刻)。

(i) 原始顺序

一个循环 = 5 条指令，占 34 个周期
CPI = 34 / 5 = 6.8

(ii) 把 3 条普通指令提到 MFHI 之前

M/D      : 周期 0
普通 #1   : 周期 1     // 利用 M/D 的等待期干活
普通 #2   : 周期 2
普通 #3   : 周期 3
MFHI     : max(4, 30) = 30
下一 M/D  : 周期 31

CPI = 31 / 5 = 6.2

只改善了 0.6。原因很直白：只有 3 条独立指令可填，而空窗有 29 个周期——填不满。

(iii) 要完全隐藏需要多少条

M/D 在周期 0 开始，结果在周期 30 可用。要让 MFHI 在周期 30 开始时恰好不必等待，它前面必须已经连续发射满周期 1 到 29，也就是需要 29 条独立普通指令。此时：

M/D          : 周期 0
普通 #1..#29 : 周期 1..29      // 把 29 个空窗周期全部填满
MFHI         : max(30, 30) = 30 // 不再需要等待
下一 M/D      : 周期 31

指令数 = 1 + 29 + 1 = 31 条，占用 31 个周期
CPI = 31 / 31 = 1.0

设主存访问时间为 1，则缓存访问时间为 1/k（k = 速度倍数 = 20）。命中走缓存，未命中走主存：

平均访问时间  T = h·(1/k) + (1−h)·1
加速比        S = 1 / T = 1 / ( h/k + 1 − h )

(i) 代入 h = 0.9、k = 20：

T = 0.9/20 + 0.1 = 0.045 + 0.1 = 0.145
S = 1 / 0.145 = 6.90

(ii) 令 S = 8，反解 h：

h/20 + 1 − h = 1/8 = 0.125
1 − 0.95h = 0.125
0.95h = 0.875
h = 0.921

注意这个数字的含义：命中率只提高 2.1 个百分点（90% → 92.1%），加速比却从 6.90 涨到 8.00——在高命中率区间，每一个百分点都极其值钱，因为决定性能的是"未命中的那一小撮"，而它的绝对数量在快速缩小。

(iii) 令 h → 1：

T → 1/k = 1/20 = 0.05
S → 20

原因很直观：即使每次都命中，访问也仍然要花掉缓存自己的时间。缓存再怎么用，也不可能比缓存本身更快。这正是阿姆达尔定律的又一次体现——被优化部分的极限速度，就是整体加速比的天花板。

先算两个与组织方式无关的量：

块内偏移位数 = log₂(块大小) = log₂64 = 6 位
总块数       = 128 KB / 64 B = 2048 块

(i) 直接映射——每块只能放在唯一确定的位置，所以"组数 = 块数"。

索引位数 = log₂2048 = 11 位
标记位数 = 32 − 6 − 11 = 15 位
额外存储 = 2048 × 15 = 30720 位 = 3840 字节 = 3.75 KB
XOR 门数 = 每次只需比较 1 个标记 = 15 个

(ii) 8 路组相联——每组 8 块，所以组数变成块数的 1/8。

组数     = 2048 / 8 = 256
索引位数 = log₂256 = 8 位
标记位数 = 32 − 6 − 8 = 18 位
额外存储 = 2048 × 18 = 36864 位 = 4608 字节 = 4.5 KB
XOR 门数 = 同一组的 8 个标记必须并行比较 = 8 × 18 = 144 个

空间局部性——访问了彼此相邻的地址：

• 2C10 → 2C14 → 2C18 → 2C1C：第 1、2、4、6 次访问，每次地址 +4。这是典型的顺序遍历一个 32 位整数数组的足迹。
• 4B80 → 4B84：第 7 和第 9 次访问，同样相差 4，是另一个数组（或结构体的相邻字段）。

时间局部性——同一个地址在不久之后被再次访问：

• 9F00：第 3 次和第 5 次访问，中间只隔了一次访问。典型的循环里反复读同一个变量（比如累加器、循环上界、或一个基址指针）。
• 2C10：第 1 次和第 8 次访问，间隔较远，属于较弱的时间局部性——可能是第二轮遍历从数组头开始。

两个基本量先算出来：

非流水：一条指令走完全部 5 级 = 25+15+30+28+20 = 118 ns
流水：  时钟周期 = 最慢的那一级 = max(25,15,30,28,20) = 30 ns

关键概念：流水线的时钟周期由最慢的一级决定，其余各级只能"等着"——15 ns 的 ID 级每拍要白白空转 15 ns。

(i) n 条指令的流水耗时 = (n + 级数 − 1) × 周期，其中"−1"之外的额外级数是填满流水线所需的启动开销：

流水   = (1000 + 5 − 1) × 30 = 1004 × 30 = 30120 ns
非流水 = 1000 × 118 = 118000 ns
加速比 = 118000 / 30120 = 3.92

(ii) 单条指令的延迟：

流水线下   = 5 × 30 = 150 ns
非流水线下 = 118 ns

因为每一级都被拉长到最慢那级的 30 ns，快的级只能干等。流水线提升的是吞吐量（throughput），不是单条指令的延迟（latency）——它让指令一条接一条地流出来，而不是让每一条跑得更快。这是流水线最核心的概念，几乎每年都有一小问在考它。

(iii) n → ∞ 时，启动开销可以忽略：

理想加速比 = 118 / 30 = 3.93  （而不是 5）

达不到 5 的原因是各级不均衡。理想情况下 5 级流水的加速比应为级数 5，前提是每级耗时完全相等（各 118/5 = 23.6 ns）。而现在 EX 级要 30 ns，成为瓶颈；每拍都有 5×30 − 118 = 32 ns 被浪费在各级的等待上，占 21%。

改进方向：把最慢的 EX 级再拆开（比如拆成两个 15 ns 的子级，变成 6 级流水），新周期就降到 28 ns（此时瓶颈变成 MEM）。这正是 1990 年代 CPU 流水线越做越深的动机——不过级数太深又会放大分支预测失败的代价，所以有个最优点。

(i) RAW（写后读）数据冒险 —— 转发即可解决，无需停顿

sub 要读 $3，而 $3 是前一条 add 的结果；or 同时依赖 add 的 $3 和 sub 的 $5。按正常流程，add 要到 WB 级才把结果写回寄存器堆，那时 sub 早就过了读寄存器的时刻。

解决：转发 / 旁路（forwarding / bypassing）。add 的结果其实在 EX 级末尾就已经算出来了，不必等写回——直接从 EX/MEM 流水寄存器拉一条线，送回 EX 级的输入端。这样 sub 和 or 都能及时拿到值，一拍都不用停。

(ii) load-use 冒险 —— 转发也救不了，必须停顿 1 拍

这是 (i) 的关键反例，也是最常考的一问。lw 的数据要到 MEM 级结束才从内存取回来，而下一条 add 在 它自己的 EX 级就需要这个值——而这两个时刻恰好是同一拍，数据还没到，转发无从转起（不可能把数据送回过去）。

更好的办法是让编译器在 lw 和 add 之间调度一条无关指令填进去，这样停顿周期被有用工作占满，代价归零——和卷二第 (d) 题的思路完全一样。

(iii) WAR（读后写）—— 在这条流水线上不构成冒险

表面上看 sub 要读 $2，而后面的 add 要写 $2，像是有冲突。但在顺序发射、顺序完成的 5 级流水线里：sub 在第 2 拍的 ID 级读 $2，add 最早也要到第 6 拍的 WB 级才写 $2——读永远发生在写之前，顺序天然不会被破坏。

所以正确答案是：这是一个"名字依赖"（name dependence），不是真依赖，基本流水线无需任何处理。只有在乱序执行的处理器里，后面的指令可能提前执行，这时才需要寄存器重命名来消除它。同理 WAW（写后写）也是名字依赖。

(i) 平均 CPI = 理想 CPI + 各类停顿的期望值：

CPI = 1 + 0.15×1 + 0.05×2
    = 1 + 0.15 + 0.10
    = 1.25

加速比 = 非流水 CPI / 流水 CPI = 5 / 1.25 = 4.0

(ii) 加速比要同时考虑 CPI 和时钟周期两个因子：

加速比 = (CPI_非流水 / CPI_流水) × (周期_非流水 / 周期_流水)
       = (5 / 1.25) × (1 / 1.1)
       = 4.0 / 1.1 = 3.64