IE4756 考前速查

IE4756 考前速查

Tutorial 1–5 全部结论 · 必背公式 · 易错点清单 · 考场动作
范围：讲义 1–6 Q1 数字电路 Q2 MIPS 编码 Q3 Cache 超纲 Q4 流水线 超纲 考前请以 NTULearn 公告为准

必背公式Formulas

这七张卡片覆盖了三年真题里全部需要算数的题型。

性能三件套讲义 5

CPI = 总周期数 ÷ 总指令数
CPU 时间 = IC × CPI ÷ f
MIPS rating = f ÷ (CPI × 10⁶)
MIPS 下降 ≠ 变慢。编译器删掉便宜指令会让平均 CPI 上升，但 IC 降得更多，时间反而变短。只认 IC × CPI ÷ f。

加速比与 Amdahl讲义 5

加速比 = 旧时间 ÷ 新时间
改进占比 f、快 k 倍 ⇒ 1 ÷ ((1−f) + f/k)
上限（k→∞）= 1 ÷ (1−f)
快用除、慢用乘。「3 倍快」是时间 ×1/3，「2 倍慢」是时间 ×2。写反整题作废。

磁盘延迟讲义 6 · 第 15 页

Queue + Ctrl + Seek + Rotate │ Transfer
每转
60000 ÷ RPM　(ms)
旋转延迟
每转 ÷ 2（平均等半圈）
Latency
Seek + Rotate，不含 Transfer
15000 RPM → 250 RPS → 4 ms/转 → 平均旋转 2 ms。没给传输率就只算到 Latency，并写明这一点。

加法器门延迟讲义 3 · 27–29 页

行波进位
每位 2 级；32 位 = 3 + 2×31 = 65；Θ(n)
快加法器
1 + 5×2 + 5×2 + 1 = 22；Θ(log n)
面积
Θ(n) 对 Θ(n log n)
n ≤ 4 时快加法器反而更慢（9 对 10），固定开销摊不开——这句能拿分。

MIPS 三种格式讲义 4

R = 6-5-5-5-5-6　op rs rt rd shamt funct
I = 6-5-5-16　　 op rs rt immediate
J = 6-26　　　　 op address ÷ 4
R 型
$rd, $rs, $rt
I 型
$rt, $rs, imm
移位
$rd, $rt, sha　源是 rt，rs 填 0
零扩展
andi · ori · xori · lui
符号扩展
addi · slti · lw · sw · beq · bne

晶体管计数讲义 3 + 课件

TG 锁存器
2 TG + 2 INV = 8 T
主从 D-FF
2 锁存器 + 时钟反相器 = 18 T
2:1 MUX
2 TG + 1 INV = 6 T
带 Enable
18 + 6 = 24 T
AND3
NAND3 + INV = 8 T，2 级
两个 AND2
12 T，4 级（更差）

三个抽象机讲义 2

TM
完全局部；判 x+x 要 Ω(n²)；无实用实现
RAM
任意地址一步到；二分 O(log n)；贴近真机
PM
只能顺指针走；指针只能判等；能证排序 Ω(n·log n)
PM 的价值来自它禁止了地址算术——堵死基数排序，下界才证得出来。

Tutorial 逐题结论One line each

星数 = 出现在笔试里的可能性。标「自学」的是讲义没讲、tutorial 自己让你查 Wikipedia 的题。

题一句话结论权重
T1-1小端减一 TM：S0 读 0 写 1 右移找第一个 1；找到写 0 停；撞空白说明 n=0，进 S1 一路写 0 左移复原。3 个状态。★★
T1-2RAM 求最大：t 初值取 mem[0]（不能取 0，否则全负数出错），i 从 1 起，结尾 mem[reg[0]] ← t。全程不动 reg[0]。★★
T1-3PM 压成 3 字段：f 字段节点 → 深度 ⌈log₂f⌉ 的二叉树，叶子存原字段。字段号是编译期常数，路径写死，无需指针算术。开销常数倍。★★
T1-4打孔卡：一张 80 字节。缺点全部源于程序不是可寻址数据；冯·诺依曼架构是对此的回答。★ 偏
T2-1TM 编码：状态编号 0…N−1（0 初始、N−1 终止）+ 固定宽度字段 + 规范顺序让位置代替键 + 一元码头部自定界。长度 O(N log N)。★★
T2-2分离 I/D cache：首要原因是取指与访存的结构冒险（一个端口撞车）；其次访问模式不同、I-cache 免写回逻辑、互不污染、布局更近。等于在 L1 做哈佛架构。★★★
T2-32 位饱和计数器：迟疑让循环退出那次只把 11 拉到 10，最高位不变 ⇒ 每遍只错 1 次而非 2 次。★ 自学
T2-4CPU 必须存 PC：跳转动作本身毁掉 PC；没有任何指令能读 PC；保存与跳转必须原子。三条理由各自都够。★★
T2-5中断返回指令：只读标志位软件写不回去，需要一条被特许、只能复原快照、且原子完成的指令。与 T2-4 是同一原理的两半。★★
T3-P165 级 对 22 级；Θ(n) 对 Θ(log n)；面积 Θ(n) 对 Θ(n log n)；下树回传是为了避免 32 的扇出。★★★
T3-P2-1带 Enable 的 D 触发器 = D 前面加一个 2:1 MUX，另一路接 Q 自反馈。共 24 个晶体管。★★
T3-P2-2计数器：Enable = 低位全 1，D = ¬Q。这就是 2025-26 Q1(c) 状态机的骨架。★★★
T3-P2-3PC = 32 个带 Enable 的 FF + 快加法器（第二输入 1）成环。Enable 用于停顿，跳转要再加一个 MUX。★
T4-1a0x00000000 = sll $0,$0,0 = NOP。全零字无害是刻意设计：跑飞进清零内存只会滑过去。★★★
T4-1b0x8c82fffc = lw $2, -4($4)　（0xfffc 符号扩展 = −4）★★★
T4-2asw $1,-4($4) = 0xAC81FFFC　与 1b 低 16 位完全相同，只差 opcode 和 rt。★★★
T4-2badd $3,$1,$4 = 0x00241820★★★
T4-3shamt 扩容：(64 − 3) × (32 − 1) = 1891 条。定长编码的浪费同时也是扩展余量。★★
T4-4递归 eq/lt：eq = eqH·eqL，lt = ltH + eqH·ltL，32 位 11 级。与快加法器同构：eq↔propagate，lt↔generate。★★★
T5-1分支预测准确率 a = 90%。盈亏平衡 60%，理论上限 1.3636。1 位预测器 80% 只够 1.15×。★★★
T5-2700 ms。每文件 5 + 2 = 7 ms，×100。「每个 1 MB」是干扰项——没给传输率。★★★
T5-3文档→闪存；备份→磁带（10 TB/卷，顺序访问不碍事）；游戏→光盘分发 / SSD 运行；相机→SD（抗震·小·省电）；医学影像→光盘 R（归档寿命 + 不可篡改）+ 磁带。★★

易错点Traps

这十二条每一条都真的有人栽过

考场动作Procedures

三套照着做就不会错的流程。紧张的时候不要临场想，按步骤走。

编码 / 译码

  1. 查表拿 opcode（R 型再拿 funct）
  2. 看表里的参数顺序，别按汇编的书写顺序猜
  3. 寄存器写成 5 位，立即数写成 16 位（负数取补码）
  4. 按 6-5-5-5-5-6 或 6-5-5-16 拼成 32 位
  5. 重新按 4 位切开，读成 8 个十六进制数字
译码反着走：先摊成 32 位二进制，取高 6 位定格式，000000 就去看低 6 位 funct。

状态机设计

  1. 数一数循环有几个状态，够不够用输出位表示
  2. 不够就加位：先用二进制计数器数拍子
  3. 写转移表 → 标出无关项 → 逐位化简
  4. 化简结果就是各触发器的 D 输入
  5. 回代验证：把每个状态代进去走一圈
译码输出是状态的纯函数（Moore 型）：状态负责计时，输出只是状态的函数。

CPI 时间线

  1. 找出唯一会「等」的那条规则（通常是数据依赖）
  2. 把第一条指令的开始时刻设为 0
  3. 逐条算：start = max(前一条 start + 1, 依赖就绪时刻)
  4. 一轮周期 ÷ 一轮指令数 = CPI
  5. 检查最坏情况：换指令条数、换排列顺序，取最大值
用不上的数据（比如非 M/D 的 3 周期）是故意的干扰项——要能说出它为什么用不上。