五份 Tutorial，
十七道题，全部拆到底

先把算法想清楚，再翻译成状态转移表。

① 二进制减一的本质

小端序（little-endian）意味着磁带最左边那一格是最低位，读写头初始就停在这一格——这对我们极其有利，因为减一恰好是从最低位开始处理的。

十进制里 ...000 − 1 要借位；二进制的规则更简单：从最低位往高位扫，把遇到的每一个 0 改成 1，直到遇见第一个 1，把它改成 0，然后就结束了，更高位一律不动。

验证一下：n = 12，大端 1100，小端写成 0011。从左（最低位）扫：0→1、0→1，遇到第一个 1→改成 0，停。得到小端 1101，还原成大端就是 1011 = 11 = 12−1。✓

那 n = 0 怎么办？全是 0，一路把它们都翻成了 1，却始终没遇到 1——扫到磁带末尾的空白 − 时才发现。所以需要一个撤销阶段：往回走，把刚才翻出来的 1 全部改回 0。

② 还有一个容易漏掉的约束

课程的 TM 定义里，输出是运行结束时读写头所在格子往后的那串二进制。所以不能"算完就地停下"——必须把读写头送回最低位那一格再停机，否则输出会少几位。这就是下面 B、C 两个"回程"状态存在的理由。

③ 状态转移表

一共 3 个工作状态 + 1 个终止状态，转移表 7 条。注意状态 B 里不需要区分读到 0 还是 1——因为经过状态 A 之后，左边的格子要么是被翻成 1 的，要么是那个刚被改成 0 的格子，两种情况都只需要路过。

④ 三种情况各走一遍

RAM 模型的约定：开始时 reg[0] = n（输入个数），输入放在 mem[0..n)，指令只有三类——[条件]跳转、基本运算、内存读写（reg[k] ← mem[reg[j]] / mem[reg[j]] ← reg[k]，注意地址必须先放在某个寄存器里）。

// reg[0] = n（输入个数，已给定）
// reg[1] = i（当前下标）   reg[2] = max（当前最大值）
// reg[3],reg[4],reg[5] = 临时

reg[1] ← 0
reg[2] ← mem[reg[1]]      // max := mem[0]，先拿第一个元素打底
reg[1] ← reg[1] + 1       // i := 1

maxloop:
reg[3] ← reg[1] < reg[0]  // i < n ?
goto done if reg[3] = 0
reg[4] ← mem[reg[1]]      // x := mem[i]
reg[5] ← reg[2] < reg[4]  // max < x ?
goto skip if reg[5] = 0
reg[2] ← reg[4]           // max := x
skip:
reg[1] ← reg[1] + 1       // i := i+1
goto maxloop

done:
mem[reg[1]] ← reg[2]      // 此刻 reg[1] 恰好 = n，所以写的就是 mem[n]

• 为什么要先取 mem[0] 打底，而不是把 max 初始化成 0？因为输入可能全是负数，初始化成 0 会得到错误答案。用"第一个元素"打底对任何取值范围都安全。
• 边界情况：n = 0 时不存在最大值，上面的程序会读 mem[0]（越界读一个没定义的值）。严谨的写法应在开头加一句 goto end if reg[0] = 0。考试时写一句注释说明即可。
• 复杂度：循环体是常数条指令，执行 n−1 轮，Θ(n) 时间、O(1) 额外空间。注意 RAM 模型里 mem[reg[1]] 这种"随机访问"只算一步——这正是模块 08.3 说的"完全非局部"，也是 RAM 比 TM 高效得多的根本原因（同样一道求最大值，TM 需要来回搬运比特，远不止 Θ(n)）。

核心思路一句话：把一个"胖节点"拆成一小棵由"瘦节点"搭成的树，原来指向胖节点的指针改成指向树根。

① 为什么这件事一定做得到

关键前提：字段数 f 是由原 PM 的程序固定下来的常数，不随输入规模变化。这是 PM 模型定义的一部分（"节点有固定数量的字段"）。正因为 f 是常数，下面所有"多花几步"的开销都是常数倍，不会改变任何算法的渐进复杂度。

② 构造：把 f 个字段挂到一棵二叉树的叶子上

新 PM 的节点统一有 3 个字段，我们把它们用作 (left, right, value)。对原来那个有 f 个字段的节点：

• 造一棵有 ⌈f⌉ 个叶子的完全二叉树，深度 d = ⌈log₂ f⌉。内部节点只用 left/right 两个字段，value 空着；
• 第 j 个叶子的 value 字段，存原节点第 j 个字段的内容（原字段存的是字还是指针都无所谓——PM 允许一个字段存字或指针）；
• 原来任何"指向该节点"的指针，现在一律改成指向这棵树的根。

③ 指令怎么翻译

• 读/写字段 j：原来是一步，现在变成"从根出发，按 j 的二进制位依次走 left/right，走 d 步到叶子，再读/写它的 value"。因为 j 是指令里写死的常数，这条路径也是固定的——编译期就能展开成 d+1 条指令，没有循环、没有判断。
• 新建一个节点：原来一步，现在变成新建 2f−1 个 3 字段节点并把 left/right 接好——同样是固定长度的一段代码。
• 指针的比较与赋值：完全不变。PM 里指针只能"存储"和"判等"，而两个原节点相等 ⟺ 它们的树根相等，所以判等语义自动保持。
• 寄存器：走路径时需要几个临时寄存器存中间指针。PM 允许固定数量 c 个寄存器，把 c 增大一个常数即可。

④ 代价

每一步原指令 → 至多 d+1 = ⌈log₂ f⌉+1 步新指令。f 是常数 ⇒ 这是 O(1) 的常数倍减速，任何算法的渐进复杂度完全不变。空间上从 f 个字段变成约 2f 个字段，也是常数倍。

穿孔卡片（IBM 80 列卡是事实标准，一张卡 80 个字符 ≈ 80 字节）是第 1～3 代计算机的主力输入介质。评价它要放回当时的语境：那个年代机时极其昂贵，而人力和纸张便宜。

这题的意义远大于题面：只有能把 TM 编码成字符串，才可能有通用图灵机（UTM），也才有"程序可以被当作数据"这件事——模块 08.5 那一跃的技术基础就在这里。

① 要编码的东西

一台 TM 由这些成分决定：状态集合 Q、转移函数 δ、初始状态、终止状态。磁带字母表固定为 {0, 1, −}，移动方向为 {左, 右, 停}。

② 关键技巧：用固定顺序消灭分隔符

最省事的做法是给转移表规定一个标准顺序，这样就不必编码"这条转移属于哪个状态、读到什么符号"——位置本身已经说明了一切：

• 把状态编号为 1…|Q|，约定状态 1 是初始状态、状态 |Q| 是终止状态（终止状态没有转移），这样两者都不用额外编码。
• 按 (状态 1, 读到 0) , (状态 1, 读到 1) , (状态 1, 读到 −) , (状态 2, 读到 0) , … 的顺序，依次列出每条转移的输出部分。一共 3(|Q|−1) 条。

③ 每条转移的比特布局

④ 完整串的格式

E(M) =  ⟨|Q|⟩  ‖  T₁,₀ T₁,₁ T₁,−  ‖  T₂,₀ T₂,₁ T₂,−  ‖ … ‖  T|Q|−1,−

其中 ⟨m⟩ 是 m 的自定界编码，例如一元码：m 个 1 后跟一个 0
     （读到第一个 0 就知道 |Q| 是多少，于是 k = ⌈log₂|Q|⌉ 也确定了，
      后面每条转移的长度 4+k 就固定了，整串可以无歧义地切开）

总长度 = |Q| + 1 + 3(|Q|−1)(4+k) = O(|Q| log |Q|)。

⑤ 举个完整的例子

用 T1·Q1 那台减一 TM：状态 A=1（初始）、B=2、C=3、H=4（终止），|Q|=4 ⇒ k=2。按标准顺序列出 3×3 = 9 条转移：

* 4 号状态在 2 比特里写成 00（按模 4 编号，或把 k 取 3 位写成 100——只要发送方和接收方约定一致即可，这是编码方案的自由度）。

有五个层次的理由，第一个是决定性的，其余是加成。

① 消除结构冒险：同一拍里要取两次

这是最根本的原因。在流水线 CPU 里，IF（取指令）阶段和 MEM（访存）阶段是同时工作的：当第 4 条指令在取指时，第 1 条 lw 正好在访存。如果只有一块统一缓存、一个访问端口，这两件事必须排队——也就是每遇到一条 load/store 就要停一拍。这种因为硬件资源不够而被迫停顿的情况叫结构冒险（structural hazard）。拆成两块物理独立的缓存 = 两个独立端口，取指和访存各走各的，冲突从根上消失。

② 两种访问模式的特性完全不同，可以分别优化

③ 互相不干扰，避免"数据把代码冲掉"

设想一个遍历大数组的循环：如果共用一块缓存，数据流会像洪水一样把整个缓存冲刷一遍，连循环体自己的指令都会被挤出去，于是每一轮迭代都要重新取指令——这叫缓存颠簸（thrashing）。分开之后，数据流量再大也碰不到指令缓存，循环体的指令能稳稳驻留。

④ 物理布局：线更短，频率更高

I-Cache 可以直接放在取指单元旁边，D-Cache 放在访存单元旁边，两段导线都很短。共用一块缓存则必须放在两者之间，两边都要拉长线——在 GHz 级频率下，导线延迟是实打实的时钟周期限制（回想模块 12.5 那条"线越长越难同步"的物理规律）。

⑤ 总带宽直接翻倍

两块缓存各有自己的通路，每拍能同时供给一条指令和一个数据字，聚合带宽是统一缓存的两倍。

① 为什么非猜不可

流水线 CPU 在分支指令还没算出结果时，就必须决定下一拍取哪条指令。等结果出来意味着流水线要空转好几拍（分支惩罚）。所以只能猜——猜对了零代价，猜错了才付出清空流水线的代价。

② 循环是"几乎完全可预测"的完美案例

一个执行 n 轮的循环，它末尾那条向后跳的分支会被执行 n 次，其中 n−1 次跳转、只有最后 1 次不跳。也就是说结果的规律性高达 (n−1)/n——n=100 时是 99%。而循环恰恰占据了程序绝大部分执行时间，所以"把循环分支猜准"几乎等于"把整个程序猜准"。

③ 1 位预测器：每进一次循环错两次

最朴素的做法是记住"上次跳没跳"，这次就照做。对循环而言：

• 最后一轮：预测器说"跳"（因为上次跳了），实际不跳 → 错 1 次；
• 预测器因此被改写成"不跳"。等下次再进入这个循环（比如外层循环的下一轮）时，第一轮它说"不跳"，实际要跳 → 又错 1 次。

所以每执行一遍循环要错 2 次。对于跑在外层循环里的内层循环，这个代价会被放大 m 倍。

④ 2 位饱和计数器：每进一次循环只错一次

用 2 个比特记 4 个状态，跳转就加一、不跳就减一，到两端就饱和不再变；预测结果只看最高位。

现在重看循环：跑了几轮之后，计数器早已饱和在 11（强跳）。循环退出时那唯一一次"不跳"只把它拉到 10（弱跳）——最高位仍然是 1，仍然预测跳转。于是下次再进入这个循环时，第一轮预测"跳"，正确。

① 把时间轴摊开看

中断发生时，硬件必须做一件事：把 PC 改成中断处理程序的入口地址，否则处理程序根本不会被执行。问题在于，PC 只有一个，一旦写进新值，被中断程序的"下一条指令地址"就被覆盖掉了。

假设保存 PC 是操作系统（软件）的责任，那么这段保存代码只可能出现在中断处理程序的开头。但等到处理程序的第一条指令开始执行时，PC 里装的已经是处理程序自己的地址了。软件根本没有任何一个指令槽可以插进"跳转之前"这个时刻——那个时刻在定义上就不属于软件。

② 中断是"非自愿"的，被中断方也没机会自救

中断与函数调用有本质区别：函数调用是程序自己发起的，所以 jal 可以顺手把返回地址存进 $31。而中断是异步的，可能发生在任意两条指令之间，被中断的程序完全不知情、也没做任何准备，当然不可能提前保存什么。

③ 还必须是原子的

"保存 PC"和"载入处理程序地址"这两步必须不可分割。如果它们之间存在任何一个可被打断的间隙，另一个中断恰好在此时到达，就会把刚保存的 PC 覆盖掉，被中断的程序永远回不去了。只有硬件能提供这种原子性——它在取指周期的边界上一次性完成整个动作序列（压栈保存 PC 与状态字、关中断、载入向量地址），中间不存在任何"指令边界"。

先说清楚"只读标志位"指什么：CPU 内部有一批状态位——中断使能位、特权/内核模式位、条件码等——它们对普通指令而言是不可写的，软件读得到、改不了。

① 中断进入时，硬件改动了这些标志位

接受中断时硬件不只改 PC，还会顺手：关闭中断使能（免得处理程序刚开头就被再次打断）、切到内核/特权模式。所以要正确返回，必须把这些标志位连同 PC 一起恢复原样。

② 它们是只读的 ⇒ 根本没有普通指令能写回去

这是最直接的理由：既然没有任何一条普通指令能改写这些位，就必须专门提供一条指令，它的定义就是"把先前保存的标志位和 PC 一起恢复"。这条指令就是 return-from-interrupt（MIPS 的 eret、x86 的 iret）。

③ 就算能分开写，拆成两条指令也必然出错

这是更深一层、也是考试最想看到的论证。假设我们有"恢复标志位"和"跳回去"两条独立指令，无论怎么排都是坏的：

结论：恢复标志位与恢复 PC 必须在同一个不可分割的步骤里完成，而这正是 return-from-interrupt 这条指令存在的全部意义。

① 慢加法器（行波进位 ripple-carry）的结构

地基是全加器：输入 aᵢ、bᵢ、cᵢ，输出

sᵢ    = aᵢ ⊕ bᵢ ⊕ cᵢ
cᵢ₊₁  = (aᵢ · bᵢ) + (cᵢ · (aᵢ ⊕ bᵢ))     // 两个都为1必进位；恰一个为1则把进位传下去

把 32 个全加器串成一排，cᵢ₊₁ 接到下一位的 cᵢ，最低位的 c₀ 接 0（或减法时接 1）。

关键路径在进位链上：aᵢ⊕bᵢ 在第 0 级就能算好（不依赖进位），所以每一级从 cᵢ 到 cᵢ₊₁ 只经过 AND → OR 两级门。32 级串联：

延迟 ≈ 1 (先算所有 aᵢ⊕bᵢ) + 2×32 (进位链) + 1 (末位求和的 XOR) ≈ 66 级门延迟，即 Θ(n)

② 快加法器（进位超前 / 并行前缀）的结构

课程的表述是定义 carry(k,m,c) = "第 k 位到第 m 位这一段，在外部进位为 c 的假设下产生的进位"，并同时预先算出 c=0 和 c=1 两个答案。合并公式是

carry(k,m,c) = carry(k,p, carry(p+1,m,c))      // p 是区间中点

硬件上，这个"合并"就是一个 2 选 1 MUX：用低半区在外部进位 c 下的输出，去选择高半区两个预算好的答案之一。等价的经典写法是生成/传播对：

gᵢ = aᵢ · bᵢ          // generate：本位必定产生进位
pᵢ = aᵢ ⊕ bᵢ          // propagate：本位会把进位原样传下去

合并：  G = G_hi + P_hi · G_lo          P = P_hi · P_lo

因为这个合并操作满足结合律，32 位可以排成一棵平衡二叉树：自底向上 log₂32 = 5 层算出所有区间的 (G,P)，再自顶向下 5 层把真实进位分发到每一位。

延迟 ≈ 1 (算 g/p) + 2×5 (上行合并) + 2×5 (下行分发) + 1 (求和 XOR) ≈ 22 级门延迟，即 Θ(log n)

③ 两者对比

位宽越大差距越夸张：n=8 时约 18 : 14，优势还不明显；n=64 时变成 130 : 26，5 倍。这就是为什么现代 64 位 CPU 里绝不可能用行波进位——它会直接锁死整颗芯片的时钟频率。

① Enable 到底是什么电路

先想清楚 Enable 的语义：Enable = 1 时，时钟上升沿把 Data 存进去；Enable = 0 时，上升沿照样发生，但存进去的值必须和原来一样。

注意后半句——触发器每个上升沿总要采样一次，我们没法"取消"时钟沿。所以实现方式不是"挡住时钟"，而是换掉它采样的内容：Enable=0 时，让它采样自己当前的输出 Q，于是存回去的还是同一个值，等效于没变。

这正好是一个 2 选 1 多路选择器：

D_internal = Enable ? Data : Q          // Q 是触发器自己的输出，反馈回来

② 用传输门实现这个 MUX：只要 6 个晶体管

• TG₁ 接在 Data 与内部节点之间：NMOS 栅极接 Enable，PMOS 栅极接 Enable′ ⇒ Enable=1 时导通。
• TG₂ 接在 Q（反馈）与同一个内部节点之间：NMOS 栅极接 Enable′，PMOS 栅极接 Enable ⇒ Enable=0 时导通。
• 一个反相器从 Enable 生成 Enable′（2 个晶体管）。

两个 TG 的输出直接短接成内部节点 D_internal。因为控制信号互补，任意时刻恰好有一个导通、另一个呈高阻——绝不会两个源同时驱动同一个节点，没有冲突。

③ 为什么用传输门而不是 AND/OR 门

这也正是题目提示里说的"just like for the Reset"——Reset 用的是同一招：Reset=1 时用一个传输门把内部节点拉到 0（或选中常量 0 这一路），Reset=0 时让正常通路导通。凡是"二选一"的地方，在晶体管级都优先考虑一对互补传输门。

这两题是同一个模式的小号版和大号版，一起看最清楚：寄存器存"现在"，组合逻辑算"下一步"，时钟沿把"下一步"变成"现在"。这就是所有时序电路的通用骨架。

① 4 位计数器

把 4 个带 Enable 的 D 触发器并排放，它们共用同一个 Clock 和同一个 Enable，构成一个 4 位寄存器，输出记作 Q[3:0]。然后用组合逻辑算出 Q+1，接回各触发器的 Data 端：

D[3:0]  =  Q[3:0] + 1        // 组合逻辑，一个 4 位加一电路

每个上升沿，4 个触发器同时把各自的 D 端锁存进去，于是 Q 整体变成 Q+1。加一电路可以直接写成半加器链（比通用加法器省很多门）：

Q₀′ = ¬Q₀
Q₁′ = Q₁ ⊕ Q₀
Q₂′ = Q₂ ⊕ (Q₀·Q₁)
Q₃′ = Q₃ ⊕ (Q₀·Q₁·Q₂)        // 第 i 位翻转 ⟺ 比它低的位全是 1

② 32 位程序计数器 PC

结构一模一样，只是把规模放大、把"加一电路"换成上一题做好的快加法器：

• 32 个带 Enable 的 D 触发器并排 ⇒ 32 位寄存器 PC，共享 Clock 与 Enable；
• PC 的输出接到快加法器的第一个输入，第二个输入接常量 1（字节寻址的真实 MIPS 里接常量 4，因为每条指令占 4 字节）；
• 加法器的输出接回 32 个触发器的 Data 端。

于是每个上升沿 PC ← PC + 1，程序计数器就诞生了。

解码的第一步永远一样：先看最前面 6 位 opcode，它决定后面 26 位怎么切。

a) 0x00000000

32 位全是 0。opcode = 000000 ⇒ R 型，于是要看最后 6 位 funct = 000000 ⇒ sll（逻辑左移）。其余字段：rs=0, rt=0, rd=0, shamt=0。

逐字翻译是 sll $0, $0, 0，语义为 R[0] := R[0] << 0。而 $0 硬接线为常数 0、写它没有任何效果，移 0 位本身也什么都不做——

顺带一个设计观察：MIPS 特意让"全 0"这个最容易出现的比特模式恰好是无害的 NOP。这样一来，一段被清零的内存被当作代码执行时不会造成破坏，而且流水线插入气泡时只要往指令寄存器里塞 0 即可，不需要额外电路。

b) 0x8c82fffc

先展开成二进制：

0x8c82fffc = 1000 1100 1000 0010 1111 1111 1111 1100

取前 6 位：100011 = 35 ⇒ lw，这是 I 型指令，按 6-5-5-16 切开：

也就是"把 $4 所指地址往前一个字的内容装进 $2"。−4 这个偏移在真实代码里非常常见：数组元素是 4 字节，−4 就是"前一个元素"，通常出现在倒序遍历或访问栈上的局部变量时。

a) sw $1, -4($4)

sw 的 opcode = 101011，I 型。注意汇编写法 sw $rt, imm($rs) 里，括号里的是基址寄存器 rs，前面那个才是 rt——这是最容易写反的地方。所以 rs = $4，rt = $1，imm = −4 = 1111111111111100。

1010 1100 1000 0001 1111 1111 1111 1100
  a    c    8    1    f    f    f    c

和上一题的 0x8c82fffc（lw $2,-4($4)）对照着看很有意思：两条指令只差 opcode 的一个比特和 rt 字段，因为 lw 和 sw 的寻址方式、立即数处理完全相同，区别只在数据流方向。这正是 RISC 规整编码的体现。

b) add $3, $1, $4

R 型：opcode = 000000，funct = 100000。汇编写法 add $rd, $rs, $rt ⇒ rd = $3，rs = $1，rt = $4。注意编码顺序是 rs, rt, rd，和汇编书写顺序（rd 在最前）正好错开——这是第二个高频失分点。shamt 不用，填 0。

000000 00001 00100 00011 00000 100000
→ 0000 0000 0010 0100 0001 1000 0010 0000
    0    0    2    4    1    8    2    0

这题考的是编码空间的算法：题干已经告诉我们一个事实——除了三条移位指令，所有 R 型指令的 shamt 字段都是 0。这意味着"shamt ≠ 0"的那一整片编码目前是空的，可以拿来当 opcode 的扩展位用。

① 数一数可用的格子

• shamt 是 5 位 ⇒ 共 32 种取值，其中 shamt ≠ 0 的有 31 种。
• funct 是 6 位 ⇒ 共 64 种取值。
• 但 sll (000000)、srl (000010)、sra (000011) 这三个 funct 值不能用——它们的 shamt 字段承载的是真实的移位量，32 种取值全部已被占用。

② 算式

可用的 funct 值 = 64 − 3 = 61
每个 funct 值下 shamt≠0 的编码 = 32 − 1 = 31

新指令数 = 61 × 31 = 1891

③ 两个容易搞错的地方

• 不需要排除已被占用的 funct 值（add、sub、and…）。因为那些指令是以 shamt = 0 的形式定义的，同一个 funct 配上 shamt ≠ 0 是一个完全不同、且当前未使用的比特模式。这正是题干那句"should have shamt = 0"想让你注意到的。
• "3 input registers" 这个条件的作用：它说明我们保留 rs、rt、rd 三个字段原样作为寄存器编号，只把 shamt 挪作他用。如果连某个寄存器字段也牺牲掉，编码空间会大得多，但指令就只剩两个寄存器操作数了。

这个单元的任务是比较两个 32 位数，它出现在 ALU 里是为了实现 slt/sltu，也为分支指令 beq/bne 提供判等结果。库名里的 "no-adder" 是关键提示：它不做减法。

① 为什么必须同时算 eq 和 lt

这是整道题的题眼。假设我们只想要 lt（小于），能不能由两个半区的 lt 合并出来？不能。因为高半区如果平手，结论完全取决于低半区；高半区如果分出胜负，低半区就完全无关。所以"高半区是否相等"这个信息必须一起往上传——于是每个单元输出一对信号：

eq = (左操作数这一段 == 右操作数这一段)
lt = (左操作数这一段 <  右操作数这一段)

② 基本情形（1 位）

eq = ¬(a ⊕ c)        // 同或：两位相同则为 1
lt = ¬a · c          // 只有 0 < 1 这一种情况

③ 合并规则（把提示翻译成电路）

设高半区比较的是 A 与 C、低半区比较的是 B 与 D，完整操作数是 A✻B 与 C✻D：

eq = eq_hi · eq_lo                       // 整体相等 ⟺ 两半都相等
lt = lt_hi + ( eq_hi · lt_lo )           // 正是提示里的 (A<C) or (A=C and B<D)

④ 为什么是"递归"、以及它为什么快

合并操作满足结合律——先合并 bit3:2 和 bit1:0 再合并，与从左到右逐位合并，结果完全一样。满足结合律就意味着可以摆成平衡二叉树而不是一条链：32 位只需 log₂32 = 5 层，每层 2 级门，总共约 10 级门延迟。

相比之下，如果用"算 a−b 再看符号位"的办法，就得先付一次完整的 32 位减法（行波的话 66 级），而且还要额外处理溢出。这就是这个库叫 no-adder 的原因：比较大小根本不需要算出差值。

⑤ 有符号 vs 无符号（slt 和 sltu 的差别）

上面的电路直接给出的是无符号比较（sltu）。对补码有符号数，只有最高位的含义相反——符号位为 1 表示负数、反而更小。所以：

slt：若两数符号位不同 ⇒ 结果 = 左操作数的符号位（它是 1 就说明左边是负数，更小）
      若符号位相同 ⇒ 直接用剩下 31 位的无符号比较结果

等价的省事写法：把两个操作数的最高位取反，再做无符号比较。

所以 ALU 里 slt 和 sltu 可以共用同一棵比较树，只在最高位那一级做一点特殊处理——这也是为什么它们在控制表里的 ALU-Ctrl 编码只差一位（0100 与 0101）。

① 建模

把原来的总时间设为 1。其中分支占 0.4，非分支占 0.6（非分支部分完全不受影响，这一点是阿姆达尔定律的核心）。设预测准确率为 p：

• 猜对（概率 p）：该次分支耗时变成原来的 1/3；
• 猜错（概率 1−p）：该次分支耗时变成原来的 2 倍。

新的分支耗时 = 0.4 × [ p × (1/3) + (1−p) × 2 ]
新的总耗时   = 0.6 + 0.4 × [ p/3 + 2(1−p) ]

② 解方程

加速比 1.25 ⇒ 新总耗时 = 1 / 1.25 = 0.8：

0.6 + 0.4 × [ p/3 + 2 − 2p ]  =  0.8
       0.4 × [ 2 − 5p/3 ]      =  0.2
              2 − 5p/3         =  0.5
                   5p/3        =  1.5
                      p        =  0.9

回代验算：p=0.9 ⇒ 0.9/3 + 0.1×2 = 0.3 + 0.2 = 0.5；0.6 + 0.4×0.5 = 0.8；1/0.8 = 1.25 ✓

③ 把整条曲线画出来，能看到两件更重要的事

把 p 当变量，加速比 = 1 / (1.4 − 2p/3)：

① 旋转延迟

15000 RPM = 15000 转/分 = 250 RPS（转/秒）
每转耗时 = 1/250 秒 = 4 ms
平均旋转延迟 = 半转 = 4 ms / 2 = 2 ms

为什么是半转？磁头移到目标磁道之后，目标扇区可能刚好就在磁头下方（等 0），也可能刚刚转过去（要等整整一圈）。位置均匀分布，期望值就是半圈。

② 平均延迟（average latency）

平均延迟 = 寻道 + 旋转延迟 = 5 ms + 2 ms = 7 ms

注意课程对 latency 的定义（模块 12.5）：「要多久才能开始传输」——它由控制器 + 寻道 + 旋转三段构成，本身不包含传输时间。控制器耗时是微秒级，忽略。

③ 总时间

100 个文件 × 7 ms = 700 ms

选型的依据就是模块 12.4 的四个指标——容量、数据率、延迟、成本——再加两个实际因素：访问方式（随机 / 顺序）和耐久性 / 便携性。先把四种介质的性格摆出来：