简介

Schemdraw 是一个用 Python 绘制电路原理图的库。使用时逐一添加元件并设置其朝向与标签，库按添加顺序维护画笔位置，自动完成连线衔接，最终导出 SVG 或 PNG。

与 KiCad、Fritzing 等图形化工具不同，Schemdraw 没有交互式编辑器，图形完全由代码生成。这一特点使它天然适合需要版本控制与可复现性的场景——文档、讲义、论文附图等，图形随代码一起纳入版本管理。

1

pip install schemdraw

放置元件前，可先对照官方图示了解各符号的外形与默认朝向：Basic Elements（electrical）。

核心对象：Drawing 与 Element

画图时主要打交道的是两个类：

Drawing 支持上下文管理器（with ... as d）：进入时创建画布，退出时按配置显示或保存。常用写法：

1
2
3
4
5
6
7
8

import schemdraw
import schemdraw.elements as elm

with schemdraw.Drawing() as d:          # d 是 Drawing 实例
    d.config(fontsize=12, color='black', bgcolor='white')
    r = d.add(elm.Resistor().right().label('1k'))   # 构造 Element，再加入画布
    d.add(elm.Capacitor().down().at(r.end).label('10uF'))
    d.save('out.svg')

要点：

1. elm.Resistor() 等只构造符号对象（可链式设置朝向、标签），尚未上画布。
2. d.add(...) 才真正放置：按入笔（Placement）/ 出笔（Drop）更新 d.here，并返回已放置的元件，便于用 r.end、MP.gate 等锚点继续布线。
3. 整张图的画笔状态（d.here、全局样式）在 Drawing 上；单个符号的几何与锚点在 Element 上。后续各节（坐标系、朝向、链式接口）均在说明这两者如何配合。

坐标系与画笔

Drawing 维护一个全局画笔坐标 d.here。每次 d.add() 放置元件时，有两件独立的事情发生：

顺序串联时只需逐个 d.add：每颗元件的出笔（drop）自动成为下一颗的入笔，d.here 链式推进。跨支路或非串联走线时，用 .at(锚点) 显式指定位置，独立于 d.here。

Placement（入笔）

• 未指定时，放置点为当前 d.here（上一元件的出笔，或画布初始位置）。
• .at(p) 将放置点设为坐标或另一元件的锚点（如 M.drain），相当于跳过默认入笔、改钉别处。
• .anchor(name) 指定以该引脚对齐到放置点（即「用哪个端子入笔」）。

典型默认放置锚点：二端元件为 start；PFet 为 source；NFet 为 drain。

Drop（出笔）

元件加入画布后，d.here 更新为该元件 drop 端子的坐标。

官方文档一般不标注 “drop”，仅给出锚点名称。推断规则：

1. 二端元件（Element2Term：电阻、电容、二极管、导线等）：默认 drop = end，即沿绘制方向的出口端（.right() 时在右端，.down() 时在下端）——与包围盒的「最右」「最下」无关，取决于绘制方向。
2. 多端元件：默认 drop 由库内 elmparams['drop'] 决定，需对照锚点或运行时验证。

常见多端默认（元件默认朝向）：

可覆盖默认行为：

1
2

d.add(elm.PFet().right().reverse().drop('gate'))  # 出笔改到栅极（下一默认入笔亦在此）
d.add(elm.Resistor().right().hold())              # 不出笔：d.here 保持入笔处

运行时核对：

1
2

print(d.here)
print(m.source, m.drain, m.gate)

朝向：旋转与镜像

Placement / Drop 回答「从哪入、从哪出」；朝向回答「符号在纸面上怎么转」。.right() / .up() / .left() / .down() 设置元件旋转角 θ，参考系为画布 x 正半轴（θ = 0°）：

等价写法：.theta(角度)。

语义说明：

• 二端元件本地几何沿 +x 定义，故 .right() 表示主体沿 +x 延伸。
• PFet / NFet 在本地坐标中沟道沿 −y 方向。θ = 0 意为不旋转，沟道保持竖直，所以对这两种元件 .right() 的外观是竖直沟道——「right」只代表旋转角为 0°，并非表示沟道朝右延伸。
• .reverse() 为沿元件轴向的镜像（MOS 上常用于切换栅极左右）；.flip() 为另一方向翻转。二者与 θ 旋转相互独立。

改变 θ 后，drop 仍绑定同一命名端子，其在纸面上的方位会随旋转改变。

常用 API 接口

构造 Element 时常用的方法：

非串联连接时，优先用已放置元件的锚点绝对坐标（.at / .to），不必依赖 d.here 顺序。

示例：CMOS 反相器

结构：电源侧 PFet 与地侧 NFet 串联，栅极共接 IN，中间节点引出 OUT。下面脚本把前述对象与规则串起来：Drawing 作画布，PFet / NFet / Line 等为 Element，串联靠入笔 / 出笔衔接，跨支路靠锚点 .at / .to。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 用 schemdraw 绘制 CMOS 反相器：PFet 上拉 + NFet 下拉，标注 VDD / GND / IN / OUT，并导出 SVG。
import schemdraw
import schemdraw.elements as elm

with schemdraw.Drawing() as d:
    d.config(fontsize=12, color='black', bgcolor='white')

    # PFet: placement at source; θ=0 → vertical channel; reverse → gate on left
    MP = d.add(elm.PFet().right().reverse())
    d.add(elm.Line().down().at(MP.drain).length(0.4))
    # NFet: align drain to current pen for series stack
    MN = d.add(elm.NFet().right().reverse().anchor('drain'))

    d.add(elm.Line().up().at(MP.source).length(0.6))
    d.add(elm.Label().label('VDD'))
    d.add(elm.Ground().at(MN.source))

    d.add(elm.Line().at(MP.gate).to(MN.gate))
    mid = 0.5 * (MP.gate + MN.gate)
    d.add(elm.Dot().at(mid))
    d.add(elm.Line().left().at(mid).length(1).label('IN', loc='left'))

    d.add(elm.Dot().at(MP.drain))
    d.add(elm.Line().right().at(MP.drain).length(1).label('OUT', loc='end'))

    d.save('schemdraw-basics-01.svg')

1

python3 schemdraw-basics-01.py

生成的 CMOS 反相器原理图如下：

与上述概念的对应关系：

1. elm.PFet().right().reverse()：θ = 0（竖直沟道），.reverse() 将栅极置于左侧；默认自 source 入笔，出笔（drop）至 drain。
2. elm.NFet(...).anchor('drain')：以 drain 对齐当前笔尖（上一出笔），完成漏极侧串联。
3. Line().at(MP.gate).to(MN.gate) 与中点引出：基于锚点坐标布线，独立于画笔串联的入/出笔路径。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L21 注解幻灯片。

源网页：21.1 Annotated Slides | Parallel Processing

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L21：并行处理（Parallel Processing）

本讲从单核性能公式出发，讨论更深/更宽流水线、ILP、乱序超标量的极限；再转向 DLP（向量/GPU）与 TLP（多核）；用 Amdahl’s Law 框定加速比；最后讲共享内存多核的缓存一致性：sequential consistency、MESI snoopy 协议与 barrier。

1. 处理器性能（Processor Performance）

程序运行时间 = 指令数 × 平均每指令周期（CPI）× 时钟周期 $t_{\mathrm{CLK}}$。指令数由 ISA/编译器决定；本讲聚焦后两项。流水线减小 $t_{\mathrm{CLK}}$。理想 5 级 Beta 每周期完成 1 条 → $\mathrm{CPI}_{\mathrm{ideal}}=1$，但分支、紧接使用 LD、cache miss 引入 NOP bubble → $\mathrm{CPI}_{\mathrm{stall}}$。

2. 五级流水线处理器（5-Stage Pipelined Processors）

经典 5 级是 $t_{\mathrm{CLK}}$ 与 $\mathrm{CPI}_{\mathrm{stall}}$ 的折中。局限：每级同时只处理一条 → $\mathrm{CPI}_{\mathrm{ideal}}=1$；慢操作（乘、大 cache）迫使 $t_{\mathrm{CLK}}$ 变长；流水线内指令顺序固定——LD 在 MEM 因 miss 停住时，前面无关指令也被拖住。如何放松这些约束？

3. 改进五级流水线性能（Improving 5-Stage Pipeline Performance）

加深流水：拆瓶颈（如 MEM1/MEM2），可缩短时钟，但 LD 数据冒险需更多 bubble → $\mathrm{CPI}_{\mathrm{stall}}$ 升。更深意味着更多指令并行执行。

4. 流水线深度的极限（Limits to Pipeline Depth）

每级额外开销 $O$：寄存器 $t_{\mathrm{PD}}$/setup/hold、clock skew、工作量不均的浪费。原周期 $T$、$N$ 级后周期 $\approx T/N+O$；大 $N$ 时加速比逼近 $T/O$——开销主导。Intel Core-2（Nehalem）约 14 级执行流水。

5. 继续改进清单（Improving 5-Stage Pipeline Performance）

• 多发射：独立指令并行 → 提高 $\mathrm{CPI}_{\mathrm{ideal}}$，级更复杂
• Out-of-order：冒险阻塞时允许后续无关指令越过
• 更深更宽放大控制冒险代价 → 需 branch prediction 降低 $\mathrm{CPI}_{\mathrm{stall}}$

可并行/可重排的指令量合称 instruction-level parallelism（ILP）。

6. 指令级并行（Instruction-level Parallelism (ILP)）

阶乘循环例：同行可并发；BF 下方指令仅在未跳转时有效（可投机执行但须能丢弃）。约束：

• RAW（红）：读依赖先前写——旁路可解，但仍需产生结果的指令先执行
• WAW（绿）、WAR（蓝）：可用寄存器重命名消除

本例中 BF 后潜在并发其实不少。

7. 更宽或超标量流水线（Wider or Superscalar Pipelines）

并行执行 $N$ 条时，$\mathrm{CPI}_{\mathrm{ideal}}=1/N$。不同功能单元（ADD/SHIFT、整/浮点、LD/ST 地址单元）易并行；多加法器、多端口寄存器堆/内存支撑并发。Nehalem 每周期最多完成约 4 个 micro-op（≈ 简单 RISC 指令）。

8. 现代乱序超标量（A Modern Out-of-Order Superscalar Processor）

取指/译码一次多条；强依赖分支预测。译码时 register renaming，再派发到功能单元队列，操作数齐则执行——顺序可不同于程序序。结果广播唤醒等待者，并进 reorder buffer 按正确顺序 retire。电路量大；相对单发按序，平均加速约 2×（理想上界约 4）。

9. 单处理器性能极限（Limits to Single-Processor Performance）

再加深：$t_{\mathrm{CLK}}$ 收益不抵 $\mathrm{CPI}_{\mathrm{stall}}$/开销上升；再加宽乱序亦然；功耗涨得比性能快；分支预测与并发硬件愈发复杂。结论：乱序超标量难再大幅跃进 → 转向 DLP 与 TLP。

10. 数据级并行（Data-Level Parallelism）

音频向量、图像像素矩阵常对每元素做相同运算。复制 datapath，共享译码控制 → 向量处理器：块取存（似 cache line），总线一次送多字。一条指令 ≈ 标量机 $N$ 条，并行性“编进”程序，无需乱序发现。

11. 向量代码例（Vector Code Example）

16 路向量机做向量加：Beta 循环约 9 指令/10 周期 ×16 ≈ 160 周期；向量码约 4 周期 → 加速约 40（理想情况）。关键是能否 vectorize；音视频与 DSP 通常可以。内存块访问也摊薄开销。

12. 数据相关的向量操作（Data-Dependent Vector Operations）

条件执行：各 datapath 设本地 predicate；CMPLT.V 并行比较并置谓词；ADDC.V.iftrue 仅谓词为真时执行。Predication 在非向量 ISA 也用于避免短条件分支的误预测代价（x86 CMOV、ARM 条件执行）。

13. 向量处理实现（Vector Processing Implementations）

现代 CPU 常有 SIMD/向量扩展（128/256/512-bit 打包 8–64-bit 元素）。GPU 是极端多 datapath，专长 3D 渲染中“尴尬并行”的浮点变换/着色/纹理；亦用于生物信息、大数据、深度学习等。DLP 在多种场景显著加速，未来 ISA 几乎都会保留向量支持。

14. 多核处理器（Multicore Processors）

单核成本–性能曲线陡：半性能可能只需 1/4 成本。任务可拆成独立子任务时，多个更小核可达相近总性能且更便宜；并行可扩展时性能近似随核数线性。最优点数受分发/聚合开销制约，但“更多更高效小核”仍有吸引力。

15. Amdahl 定律（Amdahl’s Law）

Gene Amdahl（1967）：加速任务中比例 $F$ 的部分 $S$ 倍，整体加速比 $=1\big/\big((1-F)+F/S\big)$。应优先加速占比大的部分（做大 $F$）。

16. Amdahl 与并行（Amdahl’s Law and Parallelism）

并行部分 $F$ 可任意加速时，整体加速上界 $1/(1-F)$。90% 可并行 → 最多 10×；想在 1000 核上拿 500×，需并行化约 99.8%。多核最适合天然高并行任务。

17. 线程级并行（Thread-Level Parallelism）

TLP：每核跑独立线程，比向量的锁步更灵活。少核时常 共享内存 通信；数十/数百核则共享内存带宽成瓶颈，改用消息网络（片上 mesh、集群 MPI / InfiniBand）。以下聚焦共享内存多核问题。

18. 多核缓存（Multicore Caches）

每核私有 cache（写回）降低平均访存；miss 才打共享主存。目标：一核对共享变量的修改应对所有核可见。例：核 0/1 各跑线程 A/B，共享 $X=1$、$Y=2$，并已缓存在两核。

19. 可能的结果？（What Are the Possible Outcomes）

各线程只更新本地 cache：打印结果可一致（A 打 2、B 打 1），但结束后两核对 $X,Y$ 的缓存副本可分歧——不再像单一共享内存。去掉 cache 又会毁掉多核性能。

20. 单处理器结果（Uniprocessor Outcome）

正确性基准：同一分时单核上交错执行的可能结果集。程序员知结果不唯一，需用 semaphore 等加约束。简单多核出现的 (2,1) 不在该交错结果表中。

21. 顺序一致性（Sequential Consistency）

Sequential consistency：并行执行 $N$ 线程 ≡ 某次单核交错。简单多核两败：① 共享变量副本不一致；② 因而也不满足顺序一致性。需要修复。

22. 顺序一致性的替代？（Alternatives to Sequential Consistency?）

Weak consistency：只保证单线程内发出的访存按该线程顺序对外可见（写 X 再写 Y → 无人会看到新 Y 旧 X）；他线程操作可任意重叠。私有写回 cache 连弱一致性也不自动保证（脏 Y 可能先于脏 X 写回）。乱序核提供 BARRIER：屏障前访存完成才执行屏障后访存。各商用多核语义各异——须读 ISA 手册。

23. 修复：侦听缓存一致性（Fix: “Snoopy” Cache Coherence Protocol）

缺通信：改共享变量时他核不知。在共享总线上让各 cache snoop，更新本地状态 → cache coherence protocol。希望仅在真正共享时才付通信开销。

24. 例：MESI 协议（Example: MESI Cache Coherence Protocol）

每 cache line 状态：

读 miss：无他核 → 自内存装入置 E；他核有 E/S → 供应数据并标 S；他核有 M → 供应脏数据并写回内存，双方标 S。写：若 S 则发 INVALIDATE 使他核失效后独占再改；已是 E 则可本地改而无广播。

25. Cache 有两位“顾客”！（The Cache Has Two Customers!）

硬件服务两路请求：CPU 侧（含 store 队列，miss 时 CPU 可继续；读须先看 store 队列）与 snoopy 总线侧（失效/供应/改状态）。STORE_BARRIER 等到 store 队列空；READ_BARRIER 等到 invalidate 队列空。“read with intent to modify” = READ 紧接 INVALIDATE。

26. MESI 活动图（MESI Activity Diagram）

流程图（字极小）给出 CPU/总线事务如何改状态。Intel 另加 F 态，在多份 SHARED 中指定谁响应读请求。下面用前述例子走一遍 MESI。

27. 缓存一致性实战（Cache Coherence in Action）

$X,Y$ 初始 SHARED。顺序 (1)–(4)：

1. A 写 $X=3$：发 INVALIDATE → 独占改写；核 1 失去 $X$
2. B 写 $Y=4$：同理独占 $Y$
3. B 读 $X$：miss → 核 0 供应新值，双方标 S，主存更新
4. A 读 $Y$：对称事务

结果与同序单核交错一致；两核最终对 $X,Y$ 看法一致。其他交错同样保持顺序一致性与共享语义——一致性协议尽责。

28. 并行处理小结（Parallel Processing Summary）

单核流水深度与乱序超标量已近收益递减；GPU 继续为专用负载演进，但不取代通用计算。系统趋势是更多核 + 新算法挖并行。展望：大脑用很慢的机制完成非凡认知——靠大规模并行，还是不同计算模型（如神经网络）？认知类应用仍有架构与技术新边疆。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L20 注解幻灯片。

源网页：20.1 Annotated Slides | System-level Communication

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L20：系统级通信（System-level Communication）

本讲从“接口比实现更长久”出发，回顾背板 bus 的电气与时序困境（传输线、反射、clock skew），总结网络经验：单驱动、点对点、差分、时钟恢复（8b/10b）；再看 PCIe/QPI 等串行链路，并以渐近复杂度比较 ring / mesh / hypercube 等拓扑。

1. 计算机系统中的技术（Computer System Technologies）

系统拼合多种技术；各部件有功能与接口规格。设计者按规格集成，不必深究内部实现。技术换代（更小更快更省电）时，接口不变即可几乎无痛替换——架构中真正长久的是接口。

2. 接口天长地久（Interfaces Last Forever）

长寿接口靠有用抽象：可靠字节流网络、窗口图形、日志文件系统等，屏蔽包/错误恢复/存储阵列细节。晶体管翻倍、网络 1→10 GHz、内存×4 时，不能每次从零重写。

反例：

• Endianness：IBM big-endian vs Intel little-endian——本地方便，联网传数值却终身麻烦（“一时方便，终身后悔”）
• 早期 IBM PC 扩展总线直接暴露当时 x86 引脚与协议——与特定 CPU 绑定，后续升级痛苦

3. 系统接口与模块化（System Interfaces & Modularity）

演进：机柜间 ad-hoc 线缆 → 背板插板模块化（厂商互不兼容）→ 标准化背板促进竞争 → 性能再涨，背板带宽不够 → 又回到专用通道林立。工程现实最终推向 通用单向点对点 通道；异步点对点大体取代早期同步多信号总线。系统级通信多为线传，速率从 kHz 到 GHz 带来新电气问题。

4. 总线、互连，然后呢？（Buses, Interconnect, So…?）

电路理论里导线是等势节点：电压处处相同、变化瞬时传到各端，距离被抽象掉。当电压变化速率相对电磁波渡越时间不再“慢”时，该模型失效。Heaviside 的电报方程早已说明信号沿导线有限速传播——高速下导线是 transmission line，长度与传播必须计入。

5. 真实导线的电气模型（Electrical Model for Real Wires）

无穷小段模型参数：$R$（电阻）、$L$（自感）、$C$（对参考的电容）、$G$（绝缘泄漏）。高速、芯片/板级距离下近似无损传输线，特征阻抗 $Z_0$，波速 $\sim 1/\sqrt{LC}$。PCB 约 $Z_0\sim 50\,\Omega$，传播约 18 cm/ns。

电压阶跃沿导线传播；末端若不吸收能量会反射回波。需用匹配 $Z_0$ 的电阻端接；双向传播则两端都要端接。

6. 现实后果（Real-world Consequences）

残留能量会污染后续传输。通用药方是给更多时间稳定——高性能系统不可接受，故须减小储能效应：端接不准→反射；阻抗不连续→处处小回波；容性负载限制翻转速率→runt pulse；LC ringing 需等阻尼到合法电平。精心设计布线与驱动可把性能损失压到最低。

7. 空间与时间约束（Space & Time Constraints）

信息沿时间保持 → storage；送到另一部件 → communication。通信耗时，时序预算必须计入：传播速度上限、部件间距、翻转过快引发的效应。时序模型要显式包含 wire delay。

8. 门、线与延迟（Gates, Wires, & Delays）

早期模型给门固定 $t_{\mathrm{PD}}$；实际输出延迟依赖负载。Jade 会按负载算有效传播延迟。减负载或加 buffer 驱动重载可加速。优化时常追踪重载慢线。以下转向系统级互连设计。

9. 接口标准：背板总线（Interface Standard: Backplane Bus）

可扩展性经典做法：主板插槽连接附加卡。信号含电源、时钟，以及：

• 地址线：选端点（内存、控制寄存器等）
• 数据线：传数据（早期常多比特并行）
• 控制线：事务起止与应答

多槽可并联同一组线，靠地址区分目标。合称 system bus——按既定协议传数据的一组线。

10. 并行总线事务（A Parallel Bus Transaction）

CLK 的 assertion 边沿放信号、sample 边沿采样；周期须够传播并稳定。发起者 bus master“拥有”总线（可转移所有权）；指明操作、地址、写数据。Slave 在 sample 边沿认地址后执行，完成时用控制线应答，可读回数据。无响应时总线逻辑可超时报错。事务率不太高（如 <50 MHz）时此架构很实用。

11. 总线线即传输线（Bus Lines as Transmission Lines）

提速后问题放大：周期太短，主设备驱动→长总线传播→各接收端建立时间不够；clock skew 导致一卡新周期开驱动、另一卡仍在驱动 → 冲突噪声；连接器阻抗不连续产生多路小反射——像在大峡谷里喊话，回声淹没内容。总线最终留给低速，高速另寻他法。

12. 与此同时，箱外……（Meanwhile, Outside the Box…）

网络连接米级距离：比特组成带目的地址与校验的 packet，可请求重传。协议栈分层：物理层收发包并检错；网络层寻址路由；传输层提供可靠字节流与 flow control。关键思想：在 “best effort” 包网上堆可靠通道——上层可恢复下层错误，比每层 100% 可靠更便宜稳健。

13. 经验：单驱动、点对点（Lessons learned: Single driver; point-to-point）

共享线上多驱动/多接收电气问题多；减速能缓解但高性能不许。网络经验：point-to-point（单驱动↔单接收）最快最干净。差分信号测两线电压差，共模噪声抵消——几乎所有高速链路都用。

14. 经验：时钟恢复（Lessons learned: Clock recovery）

不必另送时钟：接收端用跳变推断部分边沿，再以标称周期 + PLL 生成本地时钟。包前加 training sequence；特殊分隔序列标数据起点。为保足够跳变，常用 8b/10b（8 消息比特→10 传输比特，保证至多每 6 bit 时间有跳变）。真正只需一路比特流即可同时恢复时钟与数据。

15. 串行点对点通信（Serial, Point-to-point Communications）

局域网从共享介质变为点对点（如 BaseT 收发各一对差分线），经交换机/路由器多跳转发。系统内互连同理：点对点 + 交换路由。各链路独立，多链路可并行提供大带宽；交换机少量缓冲处理短暂争用。

16. 改进总线（Improving on the Bus）

串行点对点取代并行总线：无共享、无 clock skew、电气环境可控 → GHz 级。要更高吞吐可多 lane 并行，用逻辑重组分包。扩展卡仍插主板，但接到的是点对点链路而非并行总线。

17. 当今计算机中的通信（Communications in Today’s Computers）

例：Intel Core i7 系——CPU 直连内存求带宽；其余经 QPI（每向 20 路差分，可达每向每秒 64 亿次 20-bit 传输）。USB、PCIe、网口、SATA、音频等亦为串行链路。有了足够强的通用互连，何必堆一堆专用通道——有如魔戒“一戒御众”。

18. 串行链路例：PCI Express（Example serial link: PCI Express (PCIe)）

PCIe Gen2 单 lane：5 Gb/s，LVDS，约 100 Ω 特征阻抗。物理层：训练序列 + 起止定界 + 载荷；链路层用序号与 CRC 检丢包并重传、做流控；事务层重组多 lane、按头识别接收方。8 lane 可达约 4 GB/s，够显卡等高性能外设。主板通信已从并行总线转向少量串行点对点——更快、更可靠、更省电、更紧凑。

19. 通信拓扑（Communication Topologies）

连接 $N$ 个需互发消息的部件（如多核）。约定：每点对点链路代价 1、传一跳时间 1、链路可并行。渐近看吞吐、最坏延迟、硬件代价。

• 总线：吞吐 $O(1)$，延迟 $O(1)$，代价 $O(n)$
• Ring：吞吐/代价 $O(n)$，最坏延迟 $O(n)$——适合流水线或延迟不敏感场景

20. 二次代价拓扑（Quadratic-cost Topologies）

• 完全图：链路 $O(N^2)$ → 吞吐与代价 $O(N^2)$，延迟 1
• Crossbar：每时隙每行/列一条消息，吞吐 $O(n)$、延迟 1，开关数 $N^2$ → 代价仍 $O(N^2)$

21. 网格拓扑（Mesh Topologies）

2D/3D mesh：每节点连固定邻居 → 链路数 $\propto N$，吞吐与代价 $O(n)$。最坏延迟：2D 为 $O(\sqrt{n})$，3D 为 $O(\sqrt[3]{n})$。布局规整、每节点硬件常量、延迟适中 → 实验多核常用 2D 四邻接 mesh。

22. 对数延迟网络（Logarithmic-latency Networks）

Hypercube、tree 提供对数级延迟。CM-1 Connection Machine 用超立方连接多达 65536 个简单处理器（各连 16 邻）；后期改树，且靠近根的链路容量更大。

23. 通信技术：延迟（Communication Technologies: Latency）

三维世界中部件最坏距离下界 $O(\sqrt[3]{N})$，平面布局 $O(\sqrt{N})$——延迟应反映物理距离。总线/crossbar 上 $N$ 个连接的容性负载也抬高下界。Mesh 随 $N$ 增长不必强行加长线，对连接上千处理器的高容量片上网络很有吸引力。

24. 通信的未来（Communications Futures）

总结：点对点已成系统级主流；超高带宽内存通道仍用多信号并行但工程极谨慎。无线连接移动设备，并研究自动发现附近外设。多核将有数十到数百核，片上网络拓扑（高带宽 + 低延迟）仍是活跃研究——未来十年对片上网络工程师很有戏。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L19 注解幻灯片。

源网页：19.1 Annotated Slides | Concurrency and Synchronization

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L19：并发与同步（Concurrency and Synchronization）

本讲以 producer–consumer 为线索，引入 precedence constraint、FIFO 缓冲，以及 Dijkstra 的 semaphore（WAIT/SIGNAL）；覆盖资源分配、互斥临界区、多生产者/消费者，以及用 SVC 或 TCLR（test-and-clear）实现 semaphore；最后讨论 deadlock（Dining Philosophers）与全局资源序 / 检测恢复。

1. 进程间通信（Interprocess Communication）

应用常拆成多进程：视频压缩可并行处理宏块；游戏分前端 UI 与后端仿真/渲染。进程封装独立状态，需要时再共享信息。

通信方式：

• 共享内存：同一物理页映射进两进程；配合同步原语（部分 ISA 有专用指令）
• 消息传递：经 OS SVC；开销更大，但编程模型不依赖是否同机

本讲用经典 producer–consumer 作并发同步范例。

2. 同步通信（Synchronous Communication）

单进程内程序计数器决定执行顺序。跨进程还需 precedence constraints（记号 $\prec$）：第 $i$ 次 send 须先于第 $i$ 次 receive；若共享单单元，第 $i$ 次 receive 须先于第 $i+1$ 次 send（防覆盖）。二者使产消紧耦合——消费完才能再生产。下一节用缓冲放松约束。

3. FIFO 缓冲（FIFO Buffering）

$N$ 字符 FIFO：空则消费者等，满则生产者等。覆盖约束放宽为：第 $i$ 次 receive $\prec$ 第 $i+N$ 次 send——生产者最多超前 $N$ 个。

实现：长度 $N$ 的环形数组 + 读/写下标（模 $N$ 递增）；另需计数（图中略）。任意交错执行皆可，只要不满写、不空读。

4. 例：有界缓冲问题（Example: Bounded Buffer Problem）

共享数组与 IN/OUT。SEND 用 IN 写，RCV 用 OUT 读，各自模 $N$ 递增。如图代码未强制任何 precedence——可空读、可满写。需要同步抽象。

5. 信号量（Dijkstra）（Semaphores (Dijkstra)）

Dijkstra 提出 semaphore：共享整数 ≥0；操作：

• WAIT(s)：等 $s>0$ 再减一返回（实现上可忙等或挂起）
• SIGNAL(s)：加一；若有等待者，恰好一个可继续

初值 $K$ 保证：第 $i$ 次 SIGNAL $\prec$ 第 $i+K$ 次 WAIT 完成。本课不允许负值。文献亦称 P/V（荷兰语“测/增”）。

6. 用信号量表达先后（Semaphores for Precedence）

指南：semaphore 初值 0；箭头起点后放 signal(s)，终点前放 wait(s)。例：A2 后 signal、B4 前 wait → 保证 A2 完成才开始 B4。初值 0 强制第一次 signal 先于第一次 wait。

7. 用信号量做资源分配（Semaphores for Resource Allocation）

另一视角：初值 $K$ = 共享资源池大小。SIGNAL 归还/加入资源，WAIT 独占领取；当前值 = 剩余未分配数。WAIT/SIGNAL 可同进程或跨进程。

8. 有界缓冲 + 信号量（Bounded Buffer Problem with Semaphores）

CHARS 初值 0：SEND 写入后 signal(CHARS)；RCV 先 wait(CHARS) 再读。保证消费者不空读。但只实现了两条 precedence 中的一条。

9. 流控问题（Flow Control Problems）

仅有 CHARS 时，生产者仍可写入超过 $N$ 个 → buffer overflow，字符流损坏。还需：第 $i+N$ 次 send 之前必须完成第 $i$ 次 receive。

10. 更多信号量的有界缓冲（Bounded Buffer Problem with More Semaphores）

加 SPACES 初值 $N$：生产者 wait(SPACES) 再写；消费者读后 signal(SPACES)。对称：生产者消费空位、生产字符；消费者反之。单生产者+单消费者至此正确；多对多另有问题。

11. 同时事务（Simultaneous Transactions）

两客户同时从同一账户取 $50。若两次 Debit 完整串行执行：余额减 $100，正确。

12. 但若…（But, What If…）

进程 A 读完余额后被打断，B 完成扣款，A 用过期余额写回 → 只扣了 $50。共享数据上的 LD/修改/ST 构成 critical section，需要 mutual exclusion：同时只有一个进程在临界区内。Semaphore + 临界区 ≈ transaction（期间共享数据不被他进程读写）。

13. 互斥用信号量（Semaphores for Mutual Exclusion）

LOCK 初值 1：进临界区前 WAIT（acquire），出后 SIGNAL（release）。锁的粒度重要：全行一个锁会串行化无关账户；每账户一锁只阻塞真正冲突的事务，吞吐更好。

14. 产消原子性问题（Producer/Consumer Atomicity Problems）

多生产者同时插入时，对 FIFO/IN 的更新可能交错 → 覆盖或下标错误。插入路径是临界区，须原子执行。

15. 再加信号量的有界缓冲（Bounded Buffer Problem with Even More Semaphores）

第三 semaphore LOCK 保护 SEND/RCV 中操作缓冲的临界区。同锁可用于多消费者，但生产者用 IN、消费者用 OUT，共用一把锁引入多余先后约束——可拆成两把锁。

16. 信号量的威力（The Power of Semaphores）

Semaphore 像瑞士军刀：跨进程 WAIT/SIGNAL 保证时序（空不读、满不写）；同进程内可实现临界区原子性（如 IN/OUT 的读改写不被打断）。

17. 信号量实现（Semaphore Implementation）

Semaphore 自身是共享数据，WAIT/SIGNAL 的读改写也是临界区——不能再用 semaphore 实现 semaphore（bootstrap）。出路：

1. 不可中断内核上的 SVC
2. ISA 的 test-and-set / test-and-clear，由内存原子读改写支持
3. 纯软件算法（如 Dekker）仅依赖单次读写原子性

本讲详述前两种。

18. 作为 SVC 的信号量（Semaphores as a Supervisor Call）

内核态 SVC 不可中断 → handler 天然临界区。WAIT：值非零则减一并返回；为零则安排重试 SVC 并 SLEEP。SIGNAL：加一并 WAKEUP 等该 semaphore 的进程。

默认实现无公平性——调度顺序决定谁先拿到；若要公平，WAIT 可维护等待队列。

19. 硬件支持（Hardware Support for Semaphores）

TCLR（test-and-clear）：一次原子操作读内存当前值并清零。自旋：TCLR 得 0 → 别人持锁，重试；得非 0 → 已获取锁（且已把锁置 0）。临界区结束用 ST 写回非 0 释放。

20. 同步的阴暗面（Synchronization: The Dark Side）

转账需拿两账户锁。两人按相反顺序各拿到第一把锁后，都等对方释放第二把 → deadlock（deadly embrace）。多资源同步需额外纪律。

21. 哲学家就餐（Dining Philosophers）

5 哲学家、5 筷；每人需左右两筷。算法：先左后右，吃完归还。典型的“多资源才可完成”设定。

22. 死锁！（Deadlock!）

若人人先拿左筷，则无人能拿右筷 → 死锁。四条件：

1. Mutual exclusion
2. Hold-and-wait
3. No preemption
4. Circular wait

对策：避免，或检测 + 恢复。

23. 一种解法（One Solution）

给筷子唯一编号，按全局序取资源（先低号再高号）。若全部筷子都被拿起，必有人已持有最高号筷，此前也已拿到另一侧低号筷 → 此人可吃并归还，打破 hold-and-wait 环。全系统约定资源全局序并按序获取 → 无环等待死锁。

24. 处理死锁（Dealing With Deadlocks）

转账：先锁低账号，再锁高账号——双方先争同一把“第一资源”，胜者可安全拿齐其余。无法改应用时：OS 的 WAIT 可检测环等待并终止一进程释放资源；数据库则检测冲突、abort 事务并由程序员决定重试，提交前改动只在事务私有副本上，确认后才 commit。

25. 小结（Summary）

• 多进程组织应用常更自然；用 semaphore 保证 precedence 与 mutual exclusion
• 临界区 + 锁实现事务语义
• 多锁可能 deadlock；全局资源序避免，或检测/重启恢复
• 大数据与云上千进程协作时，同步是核心技能

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L18 注解幻灯片。

源网页：18.1 Annotated Slides | Devices and Interrupts

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L18：设备与中断（Devices and Interrupts）

本讲讲 OS 如何用 interrupt 与内核缓冲对接 I/O，以及 blocking SVC（ReadKey）在中断禁用下的实现演进（忙等 → 重试 SVC → Scheduler → sleep/wakeup）；后半转入 hard real-time：latency、weak/strong priority、周期性负载与截止期可满足性。

1. OS 组织：I/O 设备（OS Organization: I/O Devices）

OS 与外设交互分两层：

1. 设备侧：interrupt handler + 内核缓冲，把数据搬进/搬出设备
2. 用户侧：supervisor call（SVC）按用户进程请求访问这些缓冲

难点：SVC 发出时请求未必立刻能完成（缓冲空/满），需要阻塞与唤醒机制。

2. 异步 I/O 处理（Asynchronous I/O Handling）

流程：按键 → 键盘触发 interrupt → 暂停当前进程 → handler 读字符写入拥有键盘焦点进程的内核缓冲 → 恢复被中断进程。人打字远慢于指令执行，及时服务即可跟上。

缓冲满时：覆盖旧字符无意义，通常丢弃新字符并蜂鸣提示。稍后用户程序调用 ReadKey() SVC，OS 从缓冲取字符放入用户 R0。

• blocking I/O：返回时 R0 必有字符；尚无则阻塞
• non-blocking I/O：立即返回状态标志 + 结果，程序自行决定是否稍后重试

3. 基于中断的异步 I/O（Interrupt-based Asynch I/O）

用户程序不轮询键盘，而是 event-driven：设备需要服务时用 interrupt 通知 OS。职责分离优雅——有活才占 CPU，对用户程序透明。

设备访问两种常见方式：

• 专用 I/O 指令（如实验 Beta 的 RDCHAR()、CLICK()）
• memory-mapped I/O：内核地址空间一段映射到设备寄存器，用普通 LD/ST 访问

示意代码用 MMIO：结构体含 status 与 data；handler 读键码写入环形缓冲。实际还要处理 press/release、Shift/Ctrl、CTRL-ALT-DEL 等特殊组合，以及 raw vs cooked 输入模式。

4. ReadKey SVC：尝试 #1（ReadKey SVC: Attempt #1）

ReadKey() 的 opcode 非法 → 异常进入 OS → 识别为 SVC 再分派子 handler。缓冲非空：从进程表找到对应键盘缓冲，字符写入保存的用户 R0，退出后恢复寄存器。

缓冲空时若在 handler 内 while 空转等待：SVC 在 supervisor 模式（PC[31]=1）运行，中断被禁用 → 键盘 interrupt 永远进不来 → 死循环，系统假死。失败。

5. ReadKey SVC：尝试 #2（ReadKey SVC: Attempt #2）

修复：返回前把保存的 XP 减 4。异常时 XP 存的是非法指令的 PC+4；正常 JMP(XP) 会执行 SVC 之后的指令。XP−4 使恢复后重新执行同一条 SVC。

关键差别：重试时有一拍在 user-mode（PC[31]=0）执行，此时若有挂起键盘 interrupt，可抢占并填满缓冲；再进 SVC 就能取到字符。能工作，但空缓冲时忙等重试，浪费 CPU，直到 timer 切到别的进程。

6. ReadKey SVC：尝试 #3（ReadKey SVC: Attempt #3）

空缓冲时：安排重试 SVC 后立刻调用 Scheduler()，主动让出时间片。轮转调度回来再试。代价是打字后重启略有延迟，但时间片通常短于击键间隔，不明显。

对照 timesharing 质疑：10 个各需 1s 的作业，无分时依次完成；有分时则几乎都在 ~10s 后才完——最坏完成时间不更短。但若多数进程在等 I/O，分时把空闲周期送给能干活的进程，整体利用率更好。真实系统里大量进程处于 I/O wait。

7. 更精细的调度（Sophisticated Scheduling）

进程状态加 status：ACTIVE（0）或 WAITING（非零，不同值表示等不同事件）。Scheduler() 只跑 ACTIVE。UNIX 风格原语：sleep(event) / wakeup(event)，参数即 status 标识。

8. ReadKey SVC：尝试 #4（ReadKey SVC: Attempt #4）

缓冲空 → sleep(kbdnum) 设 WAITING 并调度；键盘 handler 写入缓冲后 wakeup(kbdnum)，把所有等该事件的进程标为 ACTIVE。睡着的进程在事件发生前完全不占 CPU——优雅且高效。

9. 例题：Handler 与 OS 配对（Example: Match Handler to OS）

三种 ReadKey 变体 R1/R2/R3，三种系统 Model A/B/C：

• R1（似尝试 #2，但总读键盘 0）：只适合单进程 Model C（分时下会串共享输入）
• R2（似尝试 #1 的 while 空转）：只适合 Model B（SVC 内仍允许设备中断）
• R3（尝试 #3）：配对标准 Model A（内核不可中断）

10. 哪套 Handler 与 OS？#1（Which Handler and OS? #1）

用户报：“编译错误，Scheduler 与 ProcTbl 未定义。” → 非分时系统无这两符号；R2 也不调用 Scheduler → R3 跑在 Model C。

11. 哪套 Handler 与 OS？#2（Which Handler and OS? #2）

“现在总从键盘 0 读所有人输入，而且更浪费 CPU。” → 只有 R1 固定键盘 0；相对旧 handler 明显更费说明以前不是忙等的 R2 → R1 在 Model A。

12. 哪套 Handler 与 OS？#3（Which Handler and OS? #3）

“新系统工作正常，还更省 CPU！” → 排除 R1 在分时（共享键盘可察觉）、R2/R3 在无进程表的 C、R2 在不可中断内核 A → Model B 用户现跑 R3。

13. 对“实时”的需求（The Need for “Real Time”）

分时给每进程独立虚拟机的错觉，利用率好，但无法保证完成时间——取决于其他进程占用。OS 把 interrupt 事件暂存与用户态处理（经 SVC）分离，更难保证在 deadline 前处理完。

汽车 ESC（电子稳定控制）等控制系统有硬截止期：测力/转向/轮速 → 判是否失控 → 单轮制动纠正航向。错过截止期可能危及安全。

14. 中断延迟（Interrupt Latency）

Interrupt latency $L$：从请求运行某代码到代码真正开始执行的时间。服务时间 $S$、截止期 $D$ 时，最大允许延迟满足 $L_{\max}+S=D$。必须始终 $L < L_{\max}$ 的约束称 hard real-time constraints。

15. 延迟来源（Sources of Interrupt Latency）

贡献因素：保存进程状态、切内核、分派 handler；不可中断的长时段（复杂多周期指令如 block move——ISA 应可中断重启）；以及已在内核处理另一 interrupt（中断禁用）时的等待。

目标：界住并最小化 $L$——优化取中断路径、避免数据相关长指令、缩短内核态时间；必要时允许内核内仍可被更高优先级中断。

16. 多设备调度（Scheduling of Multiple Devices）

三设备服务时间：键盘 800 µs、磁盘 500 µs、打印机 400 µs。请求稀少、任意到达。FCFS 下最坏延迟 = 另两设备服务之和：键盘 900、磁盘 1200、打印机 1300 µs。长 handler 拖累他人——有无更好调度？

17. 弱（非抢占）优先级（Weak (Non-preemptive) Priorities）

Weak / nonpreemptive priority：当前任务跑完才按优先级选下一个；新到的更高优先级也不能打断。最坏延迟 ≈ 任意其他设备最长服务时间 + 所有更高优先级服务时间。

例：优先级 磁盘 > 打印机 > 键盘 → 键盘仍 900；磁盘只需等当前最长者（键盘）→ 800 µs；打印机最坏 800+500=1300 µs。

18. 设定优先级（Setting Priorities）

硬实时下：Earliest Deadline——按截止期排序，越早截止优先级越高。若存在能满足所有截止期的优先级赋值，EDF 也能满足。机场安检先办最早航班的比喻。过载时最小化“误机人数”则更复杂，超出本讲范围。

默认：未另行规定时，$D$ 取为到同一设备下一次请求的时间，避免系统越落越远。

19. 需要抢占（The Need for Preemption）

弱优先级下最坏延迟总含“当前最长其他任务”。若磁盘截止期 800 µs、$S=500$ → 允许 $L_{\max}=300$ µs，但弱优先级只能保证 800 µs → 不够。

引入 strong / preemptive priority：高优先级可打断低优先级 handler。同优先级序下：磁盘 $L=0$，打印机 500，键盘仍 900——磁盘截止期可满足。

20. 强优先级实现（Strong Priority Implementation）

Beta 改造：PC[31] 单比特 supervisor 改为 PC[31:29] 的 3-bit PRI（8 级）。设备请求带自己的优先级 $P_{\mathrm{DEV}}$；优先级编码器选出最高请求，仅当 $P_{\mathrm{DEV}} > \mathrm{PRI}$ 才接受中断。接受后旧 PC+PRI 存入 XP，新 PRI 设为 $P_{\mathrm{DEV}}$。高优先级最坏延迟不再受低优先级服务时间影响。

21. 重复中断（Recurring Interrupts）

加上最大请求频率：打印机每 1 ms、磁盘 2 ms、键盘 10 ms。强优先级下磁盘立即服务、打印机可抢占键盘。键盘开始延迟仍可 ≤900 µs，但不断被抢占，完成可能晚到请求后 3 ms——说明实时约束应用 deadline 表达，而非仅看 latency。周期需求过紧时 CPU 周期根本不够。

22. 中断负载（Interrupt Load）

周期负载：键盘 $800\,\mu\mathrm{s}/10\,\mathrm{ms}=8\%$，磁盘 25%，打印机 40%，合计 73%，剩 27% 给用户态。总负载 >100% 必失败。

截止期窗口内还要为更高优先级留预算：磁盘需 $500/800\approx 67.5\%$；打印机有效截止 1000 µs 内需 500+400=900 µs。键盘若 $D=2000$ µs 需 500+2×400+800=2100 > 2000 → 不可行；$D=3000$ 时 2×500+3×400+800=3000 → 刚好。

23. Mr. Blue 访问 ISS（Mr. Blue Visits the ISS）

国际空间站三任务 SSG / G / CP；先分析 弱优先级：

1. CP 最大服务时间：G 的 $L_{\max}=10$ ms → 任何其他 handler ≤10 ms
2. EDF 序：G > SSG > CP
3. 负载：SSG 5/30≈16.7%，G 25%，CP 10% → 合计 ~51.7%，空闲 ~48.3%
4. 最坏完成：SSG 等 CP+G 再加自身 → 25 ms；G 等 CP+自身 → 20 ms；CP 等 SSG+G+自身 → 25 ms

24. Mr. Blue 访问 ISS（续）（Mr. Blue Visits the ISS (cont’d.)）

改 强优先级（同序 G > SSG > CP）：

1. CP 可被抢占 → 不再受高优先级 $L_{\max}$ 限制；100 ms 窗口内最多 4 次 SSG + 3 次 G = 50 ms，故 CP 服务可达 50 ms
2. CP 占 50% + 其余 → 总约 91.7%，空闲 ~8.3%
3. 最坏完成：G = 自身服务时间；SSG ≤ 一次 G + 自身 = 15 ms；CP 按设计刚好压在 100 ms 截止期

25. 小结（Summary）

• 用户与设备交互拆成：设备侧 interrupt + 内核缓冲；应用侧 SVC
• 阻塞 I/O：经 XP−4 重试、Scheduler、最终 sleep/wakeup，避免空转
• Hard real-time：latency、service time、deadline；weak vs strong priority
• 实践中常多级强优先级，同级内再用弱优先级仲裁——足以应对多数 I/O 实时约束

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L17 注解幻灯片。

源网页：17.1 Annotated Slides | Virtualizing the Processor

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L17：处理器虚拟化（Virtualizing the Processor）

本讲在虚拟内存之上引入 process 与 虚拟机 抽象：用定时器中断做 timesharing、在 kernel/user 模式间切换保存恢复状态；并用非法指令异常做指令仿真与 SVC（supervisor call）系统调用。

1. 回顾：虚拟内存（Review: Virtual Memory）

上讲引入虚拟内存与 MMU：CPU 虚地址 → 主存物理地址，多程序可各享独立大地址空间。虚/实空间都按页划分；例：页 $2^{12}$ 字节、32 位地址 → $2^{20}$ 页，高 20 位页号、低 12 位偏移。

MMU 用页表把 VPN 映到 PPN（常多层，仅驻留活跃部分）；TLB 缓存近期翻译。已分配虚存内容在辅存；不在主存则 page fault，OS 装页。实践中每程序仅活跃页驻留主存。

2. MMU 地址翻译（MMU Address Translation）

先查 TLB；未命中再 walk 分层页表；不驻留则 page fault。映射 context 由两寄存器控制：context-number（TLB 可见哪些映射）与 page-directory（页目录所在物理页）。重载二者即可换 context。

多 context 需要够大的 TLB 同时缓存各进程热点映射，以及若干物理页存放页目录/页表段。例：两端各约 1024 页的两级页表用 3 页即可覆盖约 8MB 代码/栈/堆——对许多简单程序足够。

3. Context（Contexts）

页表构造虚→实翻译所需的 context。多任务希望支持多 context 并快速切换，从而共享物理内存：两程序都可把虚地址 0 当入口，却落到不同物理页。换程序时做 context switch。接下来弄清如何共享 CPU。

4. 构建虚拟机（Building a Virtual Machine (VM)）

抽象 process（进程）= 正在运行的程序及其资源（CPU、MMU、I/O 等）。进程状态包括：

• CPU 硬件状态：寄存器与 PC
• 虚地址空间内容：代码、数据、栈、堆对象（可在主存或辅存）
• MMU 状态：context-number、page-directory，以及分层页表占用的页
• I/O 相关：文件读写位置、网络缓冲、键盘/鼠标事件等

特权进程 OS 跑在 kernel context，记账并周期调度各进程，提供文件、网络、窗口等服务。换用户进程须保存/恢复完整状态（主存中已有部分、内核数据结构、CPU/MMU 硬件）。目标：让每进程以为独占一台独立 虚拟机，高效共享一台物理机。

5. 每进程一台 VM（One VM For Each Process）

底层是物理机：CPU + 主存，外加外设（timer、辅存、USB、网络、显示器/键鼠等）。OS 在特权 kernel context 管理外设与 MMU，为每进程造出虚拟机。

用户代码直接在物理 CPU 上跑，但可被 timer 打断，使 OS 保存当前进程、切换下一进程。经 MMU，每进程有隔离的虚地址空间。OS 提供的虚拟外设屏蔽共享细节（窗口像素、键盘焦点归属哪个进程等）：进程看到的是 I/O 事件流，而非直接操纵设备。

6. 进程：多路复用 CPU（Processes: Multiplexing the CPU）

从进程 #0 切到 #1：用户态执行被 yield 或更常见的 timer interrupt 打断 → 进内核（PC+4 存入 XP）。OS 把 #0 状态写入内核表，再装入先前保存的 #1 状态，JMP 回到用户态——#1 从上次被打断处继续。轮转各进程。

对进程而言，虚拟时间只是指令序列；若不看实时钟，感觉不到偶尔被挂起。从外部看，真实时间在进程间与 OS 切换间穿梭。CPU 时间多路复用称 timesharing。

7. 关键技术：定时器中断（Key Technology: Timer Interrupts）

外设断言 Beta 的 IRQ。若在 user mode（PC 中 supervisor 位为 0），识别中断的那拍：强制部分控制信号——PCSEL=4 选内核入口（timer 为 0x80000008，同时 PC[31]=1 进入 kernel）；WASEL/WDSEL/WERF 把 PC+4 写入 XP（R30）；MWR=0 以正确中止可能正在进行的 ST。下一拍从中断处理程序第一条指令开始。

8. Beta 中断处理（Beta Interrupt Handling）

硬件极简：存 PC+4 到 XP，并把 PC 设为依中断类型而定的入口。其余由软件完成：把 R0–R30 存入内核结构 UserMState，再调 C 处理函数；返回后从 UserMState 恢复，XP 减 4 指向被打断指令，JMP(XP) 回用户态。

简单 Beta 把各类中断入口放在连续字（reset→0，非法指令→4，timer→8…），第一条常是跳到真正处理代码；PC[31]=1。也可在已知地址放向量表，由硬件取入口——功能等价。因保存/恢复完整状态，中断对用户程序透明。

9. 例：定时器中断处理（Example: Timer Interrupt Handler）

先用 timer 更新 OS 中的 TOD（time of day），设每 1/60 秒中断一次。用户程序无需特殊处理；周期进入内核时钟处理再恢复，宛如未发生。若需 TOD，向 OS 发服务请求。汇编桩负责保存/恢复状态，中间调 C 过程。

10. 中断处理代码（Interrupt Handler Coding）

C 侧声明 TOD、UserMState 与递增 TOD 的过程。地址 8 的 BR 转到 CLOCK_H：保存寄存器（R31 恒 0 可不存）、建内核栈、调 C；返回后恢复寄存器，XP-=4，JMP(XP)。

与分时的联系：在 timer handler 里每隔若干次（如 QUANTUM）调用 Scheduler()——分时魔法发生处。

11. 简单分时调度（Simple Timesharing Scheduler）

UserMState 暂存中断期间的用户寄存器；PCB（process control block）数组为每进程长期保存完整状态：寄存器副本、MMU 状态、I/O（如虚拟控制台编号）等。CUR 指向当前进程。

Scheduler()：把暂存状态写入当前 PCB → CUR 轮转到下一进程（到尾回 0）→ 从新 PCB 装入暂存区并配置 MMU → 返回后 clock handler 把更新后的状态装回 CPU 并恢复执行。于是换到新进程。

12. OS 组织：进程（OS Organization: Processes）

再走一遍：timer 打断用户程序 → 进 clock handler → 寄存器进 UserMState →（若调用）Scheduler 写入当前 PCB、装入下一进程暂存 → handler 装回 CPU → 从新进程继续。

13. 一次一个中断（One Interrupt at a Time）

内核 supervisor 位为 1 时关中断，避免嵌套中断覆盖 UserMState。因此 OS 代码须极度小心：死循环无法被打断，机器像“冻住”，只能断电重启。用户态允许中断，失控程序仍可被键盘等打断；OS 常有热键挂起当前进程并可选保存现场供调试。

14. 异常硬件（Exception Hardware）

OS 还处理“非法”操作码（硬件未直接实现的操作，也称 UUO）。行为类似中断，但是 CPU 自身触发：挂起当前指令，把 PC+4 写入 XP，PC←0x80000004（含 supervisor 位），进入内核处理。可用软件仿真扩展指令集。

15. 异常处理（Exception Handling）

类似实验用 TinyOS：地址 0 起是各类中断/异常的分支；非法指令走位置 4 的 BR(I_IllOp)。其后分配 OS 栈、UserMState、进程表等数据结构。

16. 实用宏（Useful Macros）

汇编里用宏展开重复序列。例：从 32 位数提取比特域 $[N..M]$（bit 31 为 MSB）。另有宏把 CPU 寄存器批量保存到 / 从 UserMState 恢复。

17. IllOp 处理（Illop Handler）

标准开头：保存用户寄存器、初始化 OS 栈。取出非法指令——保存的 PC+4 是用户虚地址，须经 MMU 例程换成物理地址再读。用 opcode 索引 dispatch table（64 项）跳到对应处理：多数进 UUOError；opcode 1 作 supervisor call；opcode 2 仿真 SWAPREG。表驱动分派通常比长串比较更省时省空间。

18. 访问用户地址（Accessing User Locations）

基于上讲 VtoP：把 VPN 与偏移按约定压栈，返回物理地址于 R0，再以物理地址读主存中的用户位置。

19. 真正非法操作码（Handler for Actual Illops）

对真正非法的 opcode：打印错误信息并崩溃（如 Windows “蓝屏”）。更好做法：把进程状态写入调试文件（历史称 core dump），终止该进程并提示用户，稍后再用调试器查 dump——而非拖垮整机。

20. 仿真指令：swapreg（Emulated Instruction: swapreg(Ra,Rc)）

SWAPREG 交换两寄存器。先让汇编器把 swapreg(ra,rc) 编成类似 ADDC 的二进制（literal=0，opcode=2）。仿真：从指令取出 RA/RC，换成 UserMState 数组字节偏移，交换暂存中的用户寄存器值；返回时装回 CPU，程序仿佛硬件执行了该指令。

21. 与 OS 通信（Communicating with the OS）

用户与 OS 不同 MMU context，不能直接碰 OS 代码/数据（也不应绕过安全策略）。需要在明确入口调用 OS，经寄存器或用户虚存传参——即 supervisor call / SVC，构成受控 API（如 POSIX）。

约定：opcode=1 的非法指令作 SVC，低位字段索引具体服务。

22. OS 组织：SVC（OS Organization: Supervisor Calls）

用户程序执行不同索引的 SVC → 硬件当非法指令进 IllOp → 保存状态 → 按 opcode 分派；SVC 子处理可读用户寄存器或用户虚地址，返回值可写回暂存（如覆盖保存的 R0）→ 恢复寄存器，从 SVC 下一条继续。

23. SVC 处理（Handler for SVCs）

opcode=1 的子处理再用指令低位索引第二张 dispatch 表（TinyOS 仅少数简单服务）。真实 OS 会有文件、网络、虚存、创建进程等大量 SVC。

24. 返回用户态（Returning to User-mode）

完成则恢复寄存器并对 XP 指向的下一条 JMP。若暂时无法完成（如 ReadCh 尚无字符）→ 转 I_Wait：安排下次再执行该 SVC，并 Scheduler() 让其他进程跑。

同套代码也实现：Yield() 主动放弃本时间片；Halt() 名不副实——每次被调度到都重做 Halt SVC 再调度别人，后续指令永不执行，表现为停机。

25. 添加新 SVC（Adding New SVCs）

步骤：为用户程序定义新 SVC 宏（如 get/set TOD）；微调 SVC 分派范围；在 dispatch 表末尾加项。

26. 新 SVC 处理程序（New SVC Handlers）

处理程序经 UserMState 读写用户 R0 等，几条指令即可完成。SVC 提供受控的 OS 服务入口；且在 supervisor 模式关中断，处理程序不可被打断——若需 LD/ADDC/ST 原子递增主存变量，可封装为 SVC。本讲为简单分时 OS 打下基础；下讲继续看 OS 如何与外部 I/O 设备交互。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L16 注解幻灯片。

源网页：16.1 Annotated Slides | Virtual Memory

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L16：虚拟内存（Virtual Memory）

本讲把存储层次从 cache/主存延伸到辅存（secondary storage）：用 MMU 做虚实地址翻译、按页（page）管理主存、用 page fault 按需装入，并用 TLB 加速页表访问；同时引入多程序 context 与保护的雏形。

1. 回顾：典型存储层次（Reminder: A Typical Memory Hierarchy）

回到《The Memory Hierarchy》里的基本权衡：容量越大，访问时间往往越长。要同时做到大容量与小平均访问时间，靠夹在 CPU 与主存之间的 cache 体系。现代 CPU 常有多级 cache：一级容量不大、接近 CPU 速度；更高级容量更大、延迟更长。

2. 回顾：硬件 Cache（Reminder: Hardware Caches）

Cache 对少量地址提供快速访问，用相联寻址装下 CPU 最近常用的位置；内容由硬件自动管理。有效性依赖局部性：访问 $X$ 后不久常访问邻近地址。组织上用简单索引选出候选行；引入相联度提高命中率，并讨论块大小、替换策略、写策略。本讲把层次再往下扩，会再次遇到同类设计选择。

3. 回顾：存储层次再往下（Reminder: A Typical Memory Hierarchy）

此前未谈主存数据从何而来。Flash / 硬盘等辅存容量更大且非易失：关机仍保留数据。开机时数据都在辅存；需要时再搬到主存（primary storage）。可把主存看成辅存之上的又一级 cache，并构建虚拟内存：按需自动从辅存装入主存，并控制程序可访问哪些数据——这是安全多道程序的垫脚石。

4. 扩展存储层次（Extending the Memory Hierarchy (continued)）

在 L14 的 cache + 主存之上加上辅存。好处：容量极大（台式机 TB 级，云可达 PB，$1\,\mathrm{PB}=10^{15}$ 字节）。坏处：磁盘访问可比 DRAM 慢约 $10^5$ 倍——从 DRAM 到盘的跳变远大于 cache 到 DRAM。盘上连续块的边际代价更低，因此一次读较大块。主存 miss 的代价极高，虚拟内存必须把主存 miss 率压得极低（相对指令执行率）。

5. 巨大 Miss 惩罚的含义（Impact of Enormous Miss Penalty）

因此对“主存作辅存的 cache”要求：

• 高相联度：工作集能放进主存时，应尽量避免无谓冲突
• 大块（页）：摊薄盘访问固定开销，并利用局部性
• write-back：仅在脏页被替换时才写回辅存

miss 延迟极长带来一个好处：可用软件管理主存组织与盘 I/O——即便处理 miss 要执行数千条指令，仍远快于盘访问。策略：命中用硬件，miss 用软件 → MMU 硬件可较简单，miss 处理可很聪明。

6. 虚拟内存（Virtual Memory）

CPU 产生的地址称虚地址（virtual address），主存用物理地址。中间插入 MMU（memory management unit），用页表 / page map 把虚地址翻译成物理地址（本讲暂忽略 cache，末尾再谈二者并存）。

页表允许某虚地址映射到主存任意处；正常时两虚地址不宜映到同一物理地址；允许某些虚地址无翻译——表示尚未装入主存，MMU 发存储管理异常，由 CPU 分配物理页并从辅存装入。

页表还带来控制力：换程序时换页表即可分时；一程序可见的物理页可对另一程序不可见；可用异常做按需装入，只需保证工作集在主存。

7. 实现：分页（Virtual Memory Implementation: Paging）

逐地址映射表过大，故把虚、实地址空间都切成固定大小的页，大小 $2^p$ 字节。低 $p$ 位为页内偏移（page offset），其余为页号。典型 $p=12\sim 14$（4KB～16KB）。

例：32 位虚地址、$p=12$ → 高 20 位 VPN（virtual page number），低 12 位偏移。物理地址同理拆成 PPN + 偏移。MMU 按页管理：整页从辅存搬入主存。偏移取自低位，使邻近数据多在同一页。

翻译：用 VPN 索引页表；表项指示是否在主存，若在则给出 PPN，再与偏移拼成物理地址。若不在 → page fault，由 OS 装页并更新映射。主存作页 cache 的方案称 paging / demand paging。

8. 按需分页（Demand Paging）

初始：程序各虚页在辅存，MMU 无驻留映射。CPU 每次访存经 MMU；命中则主存完成访问；不命中 → page fault → page fault handler：分配物理页、从辅存装入、更新页表。

若无空闲物理页，选一驻留页替换（如近期未用）：脏页先写回，再标为不驻留，腾出物理页。工作集经一串 fault 装入后，若程序行为良好，fault 频率可接近零；不断 fault 称 thrashing，因辅存极慢，程序会“爬行”。

9. 简单页表设计（Simple Page Map Design）

每个虚页一条表项。例：32 位虚地址、$2^{12}$ 字节页 → VPN 20 位 → $2^{20}$ 条表项。

每项至少含：

• R（resident）：1 表示在主存；0 则访问触发 page fault
• PPN：R=1 时给出物理页号
• D（dirty）：刚从辅存装入时 clean（D=0）；CPU 写入后置 D=1；替换脏页须先写回

还可有只读位等：写只读页触发异常，利于保护代码页。

10. 例：虚→实翻译（Example: Virtual → Physical Translation）

简化例：虚地址 12 位 = 4 位 VPN + 8 位偏移（16 个虚页）；物理地址 11 位 = 3 位 PPN + 8 位偏移（8 个物理页）。页表 16 项 ×（D+R+3 位 PPN）= 80 比特。物理页上虚页号可任意打乱——取决于 fault 时哪页空闲。

例：LD 访问虚地址 0x2C8 → VPN=2，偏移=0xC8。表项 2：R=1，PPN=4 → 物理地址 0x4C8。偏移在翻译中不变。

11. Page Fault（Page Faults）

访问 R=0 的虚页 → page fault → 挂起程序，进入 handler。找空闲物理页，或选一在用页腾出：若 D=1 则写回，再把被替虚页标为不驻留。

限制：不能换出 handler 自身所在页（wired）；也不宜换出即将继续执行的代码页。理想是换“最远将来才再用”的页，但需未来信息；实践中有多种替换算法（如 aging，近似最优且实现代价适中）。

然后把目标虚页读入选定物理页，更新其 R/PPN，再重执行触发 fault 的指令——此时映射已就绪，访问成功。

12. 例：Page Fault（Example: Page Fault）

同一设定下，ST 访问虚地址 0x600（VPN 6）。表项 R=0 → fault。设选 LRU 页 VPN 0xE 替换：其 D=1，故写回 PPN 0x5 内容，再标 0xE 不驻留。从辅存把 VPN 6 装入 PPN 0x5，更新表项。恢复执行并重做 ST：0x600 → 物理 0x500，且因写入将 D 置 1。

13. CS 视角（Virtual Memory: the CS View）

把 MMU 工作看成两个过程。页表信息可视为数组：R[]、D[]、PPN[]、DiskAdr[]。

• VtoP：每次访存调用；若虚页不驻留则调 PageFault；再取 PPN，与偏移拼接得物理地址
• PageFault：选替换页、脏则写回、标不驻留、从辅存读入目标页并更新映射

14. 硬件 / 软件分工（The HW/SW Balance）

VtoP 用硬件（每次访存都要）；PageFault 用异常进软件。通则：快路径硬件，罕发异常软件。所谓“软件”仍跑在 CPU 上，实质是专用硬件（MMU）与通用硬件（CPU）的权衡——应对“真正常见且性能关键”的操作才上专用硬件。

15. 页表参数算术（Page Map Arithmetic）

三个架构参数：$p$（页偏移位数）、$v$（VPN 位数）、$m$（PPN 位数）；其余由此导出。页大小常在 4KB～16KB：太大浪费装入无用字，太小摊不薄盘开销。

虚地址宽度由 ISA 定：从 32 位（4GB）迈向 64 位（约 $2^{64}$ 字节，$\mathrm{exa}=10^{18}$）。虚地址过小曾导致许多 ISA 消亡。物理地址宽度可随实现代际调整（嵌入式约 30 位，服务器 40+ 位）；程序员用虚地址，由 MMU 屏蔽物理容量差异——功能不变，性能可变。

16. 算术例（Example: Page Map Arithmetic）

设虚 32 位、物理 30 位、页 4KB：$p=12$，$v=20$，$m=18$。物理页数 $2^{18}$，虚页数 $2^{20}$，页表项数约 $10^6$。每项约 $m+2=20$ 比特 → 页表约 20 Mbit。若用专用大 SRAM 存整表会很贵。

17. 页表放主存（RAM-Resident Page Maps）

何必专用存储器？用页表指针寄存器指向主存中的页表数组，页表占若干物理页。用 VPN 做数组下标取表项即可。代价：一次虚访问需两次物理访问——先读页表项，再访问目标。

18. TLB（Translation Look-aside Buffer (TLB)）

引入专用小而快的 cache——TLB，缓存 VPN→PPN。常全相联以提高命中、避免冲突。TLB 命中则可省掉读页表，虚访问回到一次物理访问。命中率常 $>99\%$：短期工作集页数不多。基本策略不变，细节可有多种变体。

19. MMU 地址翻译流程（MMU Address Translation）

流程：先查 TLB；命中则直接访主存。未命中则读页表：若页驻留，用 PPN 完成翻译并填入 TLB；若不驻留 → page fault，交 handler。

20. 综合例：带 TLB 的 MMU（Putting it All Together: MMU with TLB）

例：$p=10$，$v=22$，$m=14$。

• 物理页数 $2^{m}=2^{14}$
• 页表项数 $2^{v}=2^{22}$
• 每项 $m+2=16$ 比特
• 页表总字节约 $2^{23}$，占 $2^{13}$ 页
• 同时可驻留比例 $2^{m}/2^{v}=1/2^{8}$

翻译例：虚 0x1804 → 偏移 0x004，VPN 0x6，TLB 命中 PPN 0x2 → 物理 0x804。虚 0x1080：TLB 未命中，页表给出 PPN 5 → 0x1480。虚 0x0FC：TLB/页表均显示不驻留 → page fault。注意：替换虚页时把页表 R 置 0 后，也须使对应 TLB 项失效。

21. Context（Contexts）

页表提供解释虚地址的 context：同一虚地址 0 在不同程序映到不同物理位置。多程序可各有独立虚地址空间并共享物理内存。换程序即换 context（重载页表相关状态）。

22. Context 预告：分时与 OS（Contexts: A Sneak Preview）

分时系统周期性地在程序间切换 CPU，造成“各有一台虚拟机”的错觉——切换时同时切换 CPU 状态与 MMU context。特权代码 OS 运行在 kernel context：管理物理内存与异常；用户程序在 user mode。异常进入 kernel mode；处理完再回 user mode。内核可访问 MMU、I/O 等特权寄存器；用户要通过 OS 请求盘等服务。下讲展开。

23. 内存管理与保护（Memory Management & Protection）

用户程序仿佛独占整个虚地址空间，常遵守相同约定（入口、栈初值等）；OS 靠不同 context 隔离。典型布局：虚页 0 不可访问（抓空指针）；接着只读代码（及共享库）；再读写静态数据；其余由向高地址增长的栈与向低地址增长的堆对向扩张。区域增长时 fault handler 可分配新页；若中部相遇则虚存耗尽。

24. 多级页表（Multi-level Page Maps）

扁平页表占大量物理页；多 context 时更糟。分层页表：虚地址高若干位索引 page directory，得到该段页表所在物理页；页表段本身也可在虚存中、不必全部驻留。栈与堆之间未分配区在 directory 中标不驻留，无需为“全不驻留”的海量表项占空间。代价是 walk 多一次访存，但 TLB 使额外开销通常可忽略。

25. 快速 Context 切换（Rapid Context Switching）

换 context 时重载页表指针相当于换掉整张表，常需冲刷 TLB，随后命中率骤降。改进：引入 context-number 寄存器，与 VPN 一起作 TLB 查询（tag 含 context）。切换时重载 context-number 与页表指针即可；其他 context 的 TLB 项自然不匹配，无需 flush。TLB 容量够时，多 context 映射可并存，切换对平均访存时间冲击小。

26. Cache 与虚拟内存（Using Caches with Virtual Memory）

• 虚地址 cache（CPU 与 MMU 之间）：仅 miss 时付翻译代价；但 context 切换改变虚存含义，常需冲刷 cache，切换代价大
• 物理地址 cache（MMU 与主存之间）：切换不使 cache 语义失效；但须先翻译再查 cache，略增平均延迟

27. 并行：两全其美（Best of Both Worlds: Overlapped Operation）

若 cache 的 line index 完全落在页偏移内，则这些位不受 MMU 影响，可与 TLB/翻译并行启动查 cache；再用物理地址 tag 做比较。TLB 命中时，物理地址与 cache tag 大致同时就绪 → 物理寻址 cache，几乎无翻译惩罚。

推论：增大 cache 容量时，若要保持 index⊆偏移，不能单靠增加 line 数或块大小（会吃掉偏移位），往往靠提高相联度。

28. 小结（Summary: Virtual Memory）

MMU 提供虚→实映射的 context；切换 context 可造出多个虚地址空间，多程序共享 CPU 与物理内存而不互扰。页表做 VPN→PPN；页表放主存，用 TLB 省掉多数页表访问；不驻留页触发 page fault，由 OS 公平管理物理页。Context 是迈向虚拟机 / 处理器虚拟化的第一步——即下一讲主题。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L15 注解幻灯片。

源网页：15.1 Annotated Slides | Pipelining the Beta

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L15：Beta 流水线（Pipelining the Beta）

本讲把早先的电路流水技术用到 32 位 Beta：经典 5 级流水（IF/RF/ALU/MEM/WB），并用 stall、bypass（forwarding）、speculation 处理 data hazard 与 control hazard，以及异常/中断下的正确性。

1. 回顾：单周期 Beta（Reminder: Single-Cycle Beta）

单周期 Beta 每拍执行一条指令：周期初装入新 PC → 取指 → 译码控制 → 读寄存器 → ALU；访存类再用 ALU 结果当地址，LD 的数据在周期末写回寄存器文件；也可写回 PC+4 或 ALU 结果。$t_{\mathrm{CLK}}$ 由整条执行路径累计延迟决定。问题：如何更快？

2. 单周期性能（Single-Cycle Beta Performance）

程序时间 ≈（动态指令数）×（CPI）×（$t_{\mathrm{CLK}}$）。CPU 设计者主要能动 CPI 与 $t_{\mathrm{CLK}}$；改指令数需动 ISA 或编译器。单周期 Beta 的 CPI=1，但 $t_{\mathrm{CLK}}$ 取最坏路径：LD 需 $t_{\mathrm{IFETCH}}+t_{\mathrm{RF}}+t_{\mathrm{ALU}}+t_{\mathrm{MEM}}+t_{\mathrm{WB}}$。简单指令也被拖慢。是否让复杂指令多拍、简单指令一拍？本讲用流水重叠执行来提吞吐。

3. 流水实现（Pipelined Implementation）

把执行拆成多级、每级少几个部件 → 时钟可更短；多条指令重叠 → 吞吐提高。单条延迟可能略增，但理想下每拍仍完成一条指令的末级。经典 5 级：

4. 为何不是 20 分钟讲完？（Why Isn’t This a 20-Minute Lecture?）

组合电路流水：画轮廓、交叉处插流水寄存器即可。但 CPU 有状态（寄存器/存储器），后级结果会影响前级（如 WB 写寄存器文件影响 RF 读）——存在指令间依赖，须专门处理。

5. 流水线冒险（Pipeline Hazards）

两类问题依赖：

• Data hazard：当前指令要用更早指令产生的数据（如读 R0 依赖先前写 R0）
• Control hazard：分支/跳转/异常改变执行顺序

当被依赖指令仍在流水线中即触发 hazard。计划：先做无 hazard 序列正确的 5 级流水 → 修 data hazard → 再修 control hazard。

6. 简化单周期数据通路（Simplified Unpipelined Beta Datapath）

为便于加流水：先只谈顺序执行，去掉分支地址与 PC MUX（总是 PC+4；control hazard 时再加回）。寄存器文件画两次：上方组合读口（RF），下方时钟写口（WB）——物理上仍是同一组 32 个寄存器。

7. 五级流水数据通路（5-Stage Pipelined Datapath）

插入流水寄存器后，无 data hazard 时信息自上而下流动，重叠正确。每拍五级各处理不同指令。数据访存可跨近两拍启动/返回；存储器本身也可流水，同时结束上一访问并开始下一访问。控制逻辑如何按级拆分？

8. 流水控制（Pipelined Control）

每级带指令寄存器，由本级 opcode 产生本级控制；编码指令随流水向前传。RF 需 RA/RB/literal，WB 需 RC。逻辑与单周期类似，只是拆到各级；处理 hazard 时还要加额外控制。

9. 流水执行例（Pipelined Execution Example）

六条指令读写不同寄存器、无分支 → 无潜在 data/control hazard，可安全重叠。逐步跟踪。

10. 例：第 1 拍（Example: Cycle 1）

IF 用 PC 取绿色 LD，周期末写入 RF 级指令寄存器；同时算 PC+4（下一蓝指令地址）。用颜色标注各级正在处理的指令。

11. 例：第 2 拍（Example: Cycle 2）

RF：绿指令读 R1；LD 使 ASEL=0、BSEL=1，选操作数写入 A/B 寄存器。IF 同时取蓝指令并更新 PC。

12. 例：第 3 拍（Example: Cycle 3）

绿指令在 ALU：R1+4，结果写入 Y_MEM。

13. 例：第 4 拍（Example: Cycle 4）

四条指令重叠。MEM 为绿 LD 启动读；读数据要到 WB 才对 CPU 可用，本拍尚不可用。

14. 例：第 5 拍（Example: Cycle 5）

WB 把上拍启动的读数据写入 R2，绿 LD 完成。MEM 同时为蓝 LD 启动读。单指令延迟 5 拍，吞吐 1 指令/拍——与单周期同 CPI，但 $t_{\mathrm{CLK}}$ 更短。注意：R2 新值在第 5 拍末上升沿才写入，第 6 拍起才对其它指令可见——这就是 data hazard 的温床。

15. 流水线图（Pipeline Diagrams）

数据通路图每拍要一张；更紧凑的是流水线图：行=流水级，列=周期，格内为指令。正常时指令沿对角线穿过五级。读寄存器在 RF，写在 WB 末。例：首条 LD 第 2 拍读 R1，第 5 拍末写 R2。

16. Data Hazard（Data Hazards）

ADDC 写 R2，紧接 SUBC 读 R2——read-after-write。ADDC 第 5 拍末才写 R2，SUBC 第 3 拍已在 RF 读 → 读到旧值。流水结果须与单周期语义一致，必须修复。

17. 解决冒险策略 I（Resolving Hazards I）

三种通用策略：

1. Stall：在 RF 卡住直到依赖满足；更早各级一并停。可靠但伤吞吐
2. Bypass / forwarding：结果已在后级数据通路中则直接前递，常可免 stall
3. Speculation：先猜，猜错再回退；适合 control hazard

18. 用 Stall 解 Data Hazard（Resolving Data Hazards I）

SUBC 在 RF stall 三次，到第 6 拍才从寄存器文件读到新 R2；IF 同步 stall。RF 停时向 ALU 塞入 NOP（如目的为 R31 的 OP/OPC）——流水中的 bubble。检测：比较 RF 的 RA/RB 与 ALU/MEM/WB 的 RC（注意：有的指令不读两寄存器；ST 的 RC 含义不同；R31 恒可“匹配忽略”）。Stall 提高有效 CPI。

19. Stall 逻辑（Stall Logic）

STALL=1：禁止 IF/RF 输入流水寄存器装载；MUX 向 ALU 送 NOP，否则送当前 RF 指令。硬件不多；权衡是 CPI↑ vs $t_{\mathrm{CLK}}$↓。

20. 用 Bypass 解 Data Hazard（Resolving Data Hazards II）

ADDC 在第 3 拍 ALU 已算出将写入 R2 的值，恰可供给同拍 RF 中的 SUBC。若 RF 的源寄存器号匹配 ALU 的 RC，用 ALU 输出代替寄存器文件陈旧读值——红箭头即 bypass。

21. Bypass 逻辑（Bypass Logic）

在读口加多路 MUX，可从 ALU/MEM/WB 前递。多路同时匹配时选最近指令：优先 ALU，再 MEM，再 WB，最后才是寄存器文件（注意 R31）。

22. 全 Bypass 流水线（Fully Bypassed Pipeline）

分支/跳转写回 PC+4，故 PC+4 路径也要 bypass。前递发生在周期末（如 ALU 算完后），MUX 的 $t_{\mathrm{PD}}$ 略拉长 $t_{\mathrm{CLK}}$。可折中：只 bypass ALU 级结果，其余靠 stall。全 bypass 后还要不要 STALL？

23. Load-to-Use Stall（Load-to-Use Stalls）

Load-to-use：紧接使用 LD 结果。LD 数据要到 WB 才在通路中可用，即便全 bypass，SUBC 仍须在 RF stall（例中 stall 到第 5 拍，插入 2 个 NOP）；若无 WB bypass 则更久。

24. 小结：带 Data Hazard 的流水（Summary: Pipelining with Data Hazards）

Stall：硬件简单，bubble 抬高 CPI。Bypass：硬件更多，一般不抬 CPI；但仍须 stall 处理 load-to-use。级数越多同拍在飞指令越多，hazard/stall 更频繁，CPI 压力更大。

25. 编译器可帮忙（Compilers Can Help）

重排无关指令可拉开 load-to-use 距离：把独立的 MUL/XOR 挪到 SUBC 前，使 LD 到 WB 时使用方才到 RF → 零 stall。前提是找得到可移动的独立指令。

26. 懒办法：改 ISA（Or Take the Lazy Route…）

把“写回延迟 3 条指令”写进 ISA，让程序员/编译器显式插 NOP——硬件省、软件苦；改流水深度还得再改 ISA。成功 ISA 寿命长，不宜绑定短期实现折中。

27. Control Hazard I（Control Hazards I）

BNE 后执行谁取决于 R3 是否非零。显式控制转移使下一条依赖当前指令执行结果——对流水意味着什么？

28. Control Hazard II（Control Hazards II）

分支下一 PC 依赖 opcode、当前 PC（算偏移）与 RA；JMP 依赖 opcode 与 RA；其它指令多为 PC+4。异常也改 PC（后文）。问题在于：JMP/分支在 RF 才读到 RA（bypass 可保证 RA 值正确），但同拍 IF 已在取“下一条”——取谁？

29. 解决 Control Hazard（Resolving Control Hazards）

对 JMP 与 taken 分支，IF 在 RF 算出目标前不知道该做什么。一策：stall IF 直至 RF 算完。

30. 用 Stall 解 Control Hazard（Resolving Control Hazards with Stalls）

RF 中为 JMP/BEQ/BNE 时 stall IF 一拍，插入 NOP；RF 确定目标后再继续。例中循环还叠加 data hazard，靠 bypass 从 MEM 取 R3。3 指令循环实际 4 拍一轮 → 有效 CPI=$4/3$（约 +33%）。

31. Control Hazard 的 Stall 逻辑（Stall Logic for Control Hazards）

IF 指令路径加 MUX，由 IRSrc_IF 控制：RF 为 JMP/BEQ/BNE 时选 NOP，annul 刚取出的指令；同时 PCSEL 选正确下一 PC。上标表示控制逻辑所在流水级。

32. ISA：简单 vs 复杂分支（ISA Issues: Simple vs. Complex Branches）

Beta 分支在 RF 决策。若 ISA 把决策放到 ALU，须 annul IF 与 RF 两条 → 两 NOP，CPI 更差；但复杂分支可能减少静态指令数。提前各级全部 annul 称 flush——代价大，仅在别无他法保正确时用。

33. 解决冒险策略 II：推测（Resolving Hazards II）

未 taken 时，流水本来按 PC+4 取指就是对的。在不确定时仍开始执行称 speculation；须能在产生副作用（写寄存器/主存）前 annul。副作用在后级，故指令可先走过 IF/RF/ALU 再最终决定。

34. 推测 I（Resolving Hazards with Speculation I）

默认猜下一 PC=PC+4，仅对 JMP/taken 分支错。若 BNE 未 taken：后续 SUB 进入流水，第 4 拍末确认后放行——猜对则零 annul。

35. 推测 II（Resolving Hazards with Speculation II）

若 BNE taken：第 4 拍末 annul SUB，第 5 拍执行 NOP。仅 taken 时插入 bubble，对 CPI 冲击小于“分支一律 stall”。

36. 推测控制逻辑（Speculation Logic For Control Hazards）

数据通路同前，只是更聪明地置 IRSrc_IF=1：不是所有分支，仅 taken 时 annul IF。

37. 分支预测（Branch Prediction）

总猜 PC+4 对 JMP/taken 常错，仿真约抬高有效 CPI ~10%。深流水（如 Nehalem）分支很晚才决出，flush 代价极大。现代做法：非分支仍猜顺序；分支按历史、循环反向偏移、甚至分支间相关做预测，正确率可达 95%–99%。

38. 分支延迟槽 I（Branch Delay Slots I）

改 ISA：跳转/分支后的下一条总是执行（延迟槽）。则猜 PC+4 恒对。把循环中 MUL 放到 BNE 后的 delay slot，可零 CPI 惩罚（若填得满）。

39. 分支延迟槽 II（Branch Delay Slots II）

实践中约一半情况找不到有用指令填槽，只好显式 NOP，代码变大；决策越晚槽越多越难填。分支预测通常优于 delay slot。再次：勿为某一实现改 ISA 语义。

40. 异常（Exceptions）

非法指令或外部中断：存 PC+4 到 XP，PC←相应 handler。异常是隐式控制转移。单周期中异常作用于“当前指令”；流水中须认定哪一条受影响，保证更早指令完成，并 annul 该指令及其后已进流水者。

41. 异常何时发生？（When Can Exceptions Happen?）

RF：非法 opcode；ALU：如 DIV 除 0；MEM：非法地址；IF：取指地址异常。后续已进流水的指令须 annul。好消息：寄存器只在 WB 更新，annul 只需换成 NOP，不必回滚已写值。

42. 处理异常（Resolving Exceptions）

若指令在第 $i$ 级引发异常：用一条副作用仅为把 PC+4 写入 XP 的“魔法” BNE 替换它 → flush 更早各级 → PC←handler。例：LD 在第 4 拍 MEM 异常，第 5 拍起 IF 取 handler。

43. 异常处理逻辑（Exception Handling Logic）

改造指令路径 MUX：可换成 NOP（annul）或魔法 BNE（肇事指令）。

44. 多重异常？（Multiple Exceptions?）

多指令并行时可能同时/先后检出多个异常。例：非法 opcode 在 RF 先被发现，但更早的 LD 随后在 MEM 也异常——应让更早指令（流水中更靠后级）的异常优先，因放弃 LD 后其后指令本就不该执行。同拍多异常：优先流水线中更靠前（更接近完成）的那条。

45. 异步中断（Asynchronous Interrupts）

外部中断也像隐式分支，但可当作作用于 IF 的异常：用魔法 BNE 捕获 PC+4，下一 PC←中断 handler；handler 返回前修正 XP 指向被打断指令（如 SUB）。更早的 ADD/LD 等不受影响。

46. 异常+中断逻辑（Exception + Interrupt Handling Logic）

沿用指令路径 MUX；调整 IRSrc_IF：有中断请求时也为 1。

47. 五级 Beta 最终版（5-Stage Beta: Final Version）

汇总：IF/RF stall + 读口 bypass MUX + stall 时向后塞 NOP；控制上默认推测 PC+4，JMP/taken 时 annul IF；异常/中断在除 WB 外各级可换指令（肇事→魔法 BNE，更早→NOP）。额外电路保证流水语义≡单周期；bypass 与分支预测使 hazard 对有效 CPI 冲击有限，短时钟换来大幅吞吐提升。

48. 回顾：解决冒险（Reminder: Resolving Hazards）

记住三板斧：stall、bypass、speculation。高性能流水设计几乎总能落到其中之一。流水讨论至此；更高性能的其它途径（并行等）留待后续讲座。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L14 注解幻灯片。

源网页：14.1 Annotated Slides | Caches and the Memory Hierarchy

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L14：高速缓存与存储层次（Caches and the Memory Hierarchy）

本讲从“Beta 其实是内存机”出发，纵览 SRAM/DRAM/Flash/硬盘，引入局部性与隐藏的存储层次；再系统讲 cache 命中率与 AMAT、直接映射 / 全相联 / $N$ 路组相联、块大小、替换与写回策略。

1. 我们的内存机（Our Memory Machine）

Beta 结构简单，但三端口主存在面积与周期占比上往往最贵——更像“内存机”而非“计算机”。每条指令先取指；数据最终都经主存进出；寄存器只能留极少热数据。现代机性能常受 CPU↔主存带宽（memory bottleneck）限制。本讲目标：理解瓶颈并尽量用体系结构缓解。

2. 存储技术（Memory Technologies）

容量↑ → 面积↑ → 线长/电容↑ → 更慢：根本的尺寸–性能权衡。将用 SRAM+DRAM 建层次，追求低平均延迟与高容量（依赖访问统计，最坏情况仍可能慢）。Flash 相对 HDD 类似 SRAM 相对 DRAM。

3. 静态 RAM（Static RAM）

SRAM：按地址读写一整行（一个 location）。例：8 行 × 6 列 → 需 3 位地址。译码器拉高一条 wordline 选中一行；该行各单元接到垂直 bitline；读时 sense amp 把模拟差转为数字，写时驱动器把数据打上 bitline。大容量 SRAM 会组织得更复杂以缩短 bitline。

4. SRAM 单元（SRAM Cell）

典型 6T 单元：两 CMOS 反相器正反馈形成双稳态；两侧经 access FET 接一对 bitline。wordline 高 → 接通；低 → 与 bitline 隔离，有电即可保持。

5. SRAM 读（SRAM Read）

先预充 bitline 到 VDD 再浮空；拉高 wordline 后小尺寸反相器缓慢拉低一侧 bitline。Sense amp 检测微小差分电压即出数字结果——读本质是模拟；差分 + 双 bitline 提高抗噪。

6. SRAM 写（SRAM Write）

先把 bitline 驱动到目标值，再开 wordline；大驱动管压过单元内小逆变器，双稳态翻转到新态。几乎由接 0 的大 nFET 下拉完成（克服单元内小 pFET）。尺寸须仔细平衡以保证快且可靠——亦是模拟操作。

7. 多端口 SRAM（Multiported SRAMs）

加套 wordline/bitline/驱动/sense → 多独立端口（寄存器堆常用）。每 bit 需 $N$ 条 wordline、$2N$ 条 bitline、$2N$ 个 access FET；面积大致随端口数平方增长——勿滥加端口。

8. SRAM 小结（Summary: SRAM）

阵列组织；双稳态存 1 bit；读写经 bitline 的模拟操作；每 bit 约 6 MOSFET。能否更少？

9. 1T 动态 RAM 单元（1T Dynamic RAM Cell）

至少 1 个 access FET；用电容电压表示 0/1 → DRAM。沟槽电容增大极板面积而不占单元面积。约比 SRAM 密 20×。电荷会漏（PN 结、亚阈导通）→ 须约每 10 ms refresh（读后写回）。

10. 1T DRAM 读写（1T DRAM Writes and Reads）

写：开 access FET，经 bitline 充/放电。读：bitline 预充中间电压，电荷共享导致微小电压变化，sense amp 检测；读破坏性 → 须写回。常按行（row address）宽读，再用列地址选字；同行后续列访问很快（fast column access）。

11. DRAM 小结（Summary: DRAM）

1T+电容；读后重写 + 周期刷新；容量大、首访慢、同行后续快。断电丢数据 → 长期存储需非易失技术。

12. 非易失：Flash（Non-Volatile Storage: Flash）

电荷存在绝缘良好的浮栅上，可保持数年。有无电荷改变导通阈值；测电流甚至可多电平存多 bit。NOR 读延迟近 DRAM（数十 ns）；NAND 读更慢（~10 µs）；写需高压，慢，且擦写次数有限（$10^5\sim 10^6$）→ 片上地址重映射磨损均衡。相对 HDD：更快但更贵。

13. 非易失：硬盘（Non-Volatile Storage: Hard Disk）

磁性盘片 5400–15000 RPM；磁头寻道 + 旋转等待，平均访问约 10 ms。就位后传输可达 ~100 MB/s；频繁寻道则有效速率骤降。TB 级廉价非易失，代价是慢。

14. 存储技术小结（Summary: Memory Technologies）

容量跨约 10 个数量级，延迟约 8 个。SRAM 跟得上工艺；DRAM/HDD 容量与带宽进步快，首访延迟进步慢；Flash 填补 CPU–HDD 间隙。每层都是：更小更快 vs 更大更慢——能否兼得？

15. 存储层次接口（Memory Hierarchy Interface）

理想：大、快、便宜的统一主存。单技术做不到 → 用不同权衡的层次：常访问数据放快层（SRAM），其余在慢大层，必要时搬移。

16. 存储层次接口（续）（Memory Hierarchy Interface continued）

两条路：

1. 暴露层次：程序员显式搬数据（如 Seymour Cray 向量机）。
2. 隐藏层次：给程序员平坦大地址空间；硬件按访问模式在层间自动搬移。

Cray 曾怀疑自动方案（“you can’t fake what you haven’t got”）。对通用程序，自动层次+局部性往往够好——引出 cache。

17. 局部性原理（The Locality Principle）

希望把频繁访问数据放在快 SRAM，并预测将访问何处；一次搬入的块应被多次命中以摊销搬移开销。局部性（locality of reference）：时刻 $t$ 访问地址 $X$ → 不久很可能会访问附近地址。

18. 访存模式（Memory Reference Patterns）

• 取指：大多顺序；循环反复同一段；调用/分支打断后很快恢复顺序。过程入口后几乎会跑完整过程代码 → 整块搬入 SRAM 有利；DRAM 快列访问摊销首访。
• 栈帧：过程期间密集访问小区域。
• 数据：结构体字段、数组步进、区域间拷贝等也有局部性。

工作集（working set）：某时间窗内访问的不同地址数；窗变大后规模趋于平稳。

19. 高速缓存（Caches）

层次中靠近 CPU 的 SRAM 称 cache。命中（hit）由 SRAM 供数；缺失（miss）从 DRAM 搬入含该地址的块。局部性 ⇒ 命中远多于缺失。可有多级：近 CPU 更小更快，miss 查下一级。浏览器网页缓存是同思想。

20. 典型存储层次（A Typical Memory Hierarchy）

例：片上 L1/L2/L3 SRAM → DRAM 主存 → Flash 作 HDD 缓存。寄存器由编译器管理；片上 cache 与 DRAM 访问由硬件；更慢层常由软件管理。每层都试图对下一慢层的热数据提供更低延迟。

21. Cache 访问（Cache Access）

CPU 发地址：命中则快返回；缺失则请主存、常把新数据写入 cache（可能替换旧块）。例：cache 4 ns、主存 40 ns → 命中 4 ns，缺失约 44 ns。CPU 须处理可变延迟（等待或切线程）。

22. Cache 指标（Cache Metrics）

命中率 + 缺失率 $=1$。平均访存时间：

$$\mathrm{AMAT} = t_{\mathrm{hit}} + \mathrm{miss\_ratio}\times t_{\mathrm{miss\_penalty}}$$

每层可递归套用。更大更慢的下一级：hit time↑，但 miss ratio↓。

23. 例：命中率要多高？（Example: How High of a Hit Ratio?）

cache 4 周期、主存 100 周期：无 cache 恒 100；有 cache：命中 4、缺失 104。AMAT=100（打平）只需约 4% 命中率；目标 AMAT=5 则需约 99% 命中。SPEC CPU2000 上典型 L1 约 97.5%（约 $10^{13}$ 次访问）。

24. 基本 Cache 算法（Basic Cache Algorithm）

每条 cache line = 数据块 + 地址 tag。按 tag 搜索：命中则读返回/写更新（并最终更新主存）；缺失则选一行替换，读则从主存填入，写则更新该行。内容由 CPU 请求塑造；工作集装得下 → AMAT 接近 hit time。关键：如何快速判断 tag 是否在某行。

25. 直接映射 Cache（Direct-Mapped Caches）

每个主存地址映射到唯一一行（DM cache）。用地址低部作 index 选一行，其余与该行 tag 比较；另有 valid 位（上电清 0）。字偏移：字寻址时低 2 位作 byte offset。index 取自低位地址位，使相邻地址映射到不同行，利于局部性。CPU 可 flush 使某些行无效（如 DMA 写入后）。

26. 直接映射示例（Example: Direct-Mapped Caches）

64 行 DM：地址拆成 offset / index / tag。例：0x400C → index=3、tag=0x40，行 3 tag 匹配 → 命中。0x4008 → index=2，tag 不匹配 → 缺失。由某行的 tag+index 可反推完整缓存地址（如 tag 同为 0x58 的行 0/1/2 → 0x5800/04/08）。

27. 块大小（Block Size）

每行可存 $2^k$ 个字（block size）。缺失时多取几个字，摊销 miss、提高后续命中；tag/valid 开销占比下降（例：4 字块 ~17% vs 1 字块 ~46% 开销）。整块要么全在要么全不在（单 valid）；局部性下通常值得整块装入。

28. 块大小权衡（Block Size Tradeoffs）

块↑ → miss penalty 近似线性↑（DRAM 首访贵，后续列访问缓和）；miss ratio 先降。容量固定时块↑ ⇒ 行数↓ ⇒ 能同时容纳的独立地址区域变少，过大反伤工作集。存在最优块大小；现代常见 64 B（16 字）。用 AMAT 综合选取。

29. DM 的问题：冲突缺失（Direct-Mapped Cache Problem: Conflict Misses）

代码与数据若映射到相同行，会互相踢出 → conflict miss，稳态命中率可从 100% 掉到 0%，程序突然慢一个数量级——破坏“平坦地址空间”抽象。需改进结构。

30. 全相联 Cache（Fully-Associative Cache）

FA：每行都有比较器，并行比所有 tag → 任意块可进任意行，无地址冲突。灵活、命中率高；代价是比较器随行数线性涨（CAM 也难根本解决）。DM 只查 1 行，FA 查全部——中间地带？

31. N 路组相联 I（N-way Set-Associative Cache I）

$N$-way SA：相当于 $N$ 个 DM 子 cache 并行。同一 index 的 $N$ 行组成一个 set；地址冲突最多可容 $N$ 个块。比较器只需 $N$ 个，可有大量行。在冲突敏感的 DM 与昂贵 FA 之间折中。

32. N 路组相联 II（N-way Set-Associative Cache II）

术语：set = 同 index 的 $N$ 行；way = 每个子 cache。路数不必是 2 的幂。管理保证同一地址不会出现在多 way（miss 时只写入一路）。

33. “数一数有几路”（Let me count the ways）

所需路数大致对应时间窗内可能冲突的区域数（代码、栈、数据，拷贝时或需两块数据区）；大时间窗或再加倍。小数目的 way 通常足以消除绝大多数冲突。

34. 相联度权衡（Associativity Tradeoffs）

路数过多：合并 hit 信号的延迟抬高 hit time；miss ratio 在约 4–8 路后收益很小。大容量 8-way SA 常接近同容量 FA。

35. 相联意味着选择（Associativity Implies Choices）

Miss 时选哪一行替换？DM 无选择；SA/FA 有。目标：选对未来命中率损害最小的那一行。

36. 替换策略（Replacement Policies）

最优：换掉最远将来才用（或永不用）的块——需预知未来。实用：LRU（least-recently-used）用过去近似未来。精确 LRU 状态大（8-way：$8!$ 序 → 约 16 bit）且更新逻辑贵 → 常用近似。其他：FIFO、随机。除随机外都可被恶意访问模式打穿；实践中 LRU/近似 LRU 仍合理。

37. 写策略（Write Policy）

• Write-through：写 cache 同时写主存——主存始终新，但写可能成瓶颈；热局部变量反复写浪费带宽。
• Write-behind：CPU 不等写完继续跑，重叠延迟；若随后 miss，仍须等写与填完成。
• Write-back：只改 cache，换出时才写回主存——最少写主存，现代主流。

38. 写回（Write-Back）

写请求只更新 cache。替换时须先把旧行写回主存（若可能已被改过）——否则会写回从未写过的行，浪费带宽。

39. 带 Dirty 位的写回（Write-Back with Dirty Bits）

每行加 dirty 位：填入时清 0；写命中置 1。仅 dirty=1 时换出才写回。CPU 只在 miss（且可能需写回脏行）时等待。

40. 小结：Cache 权衡（Summary: Cache Tradeoffs）

目标：层次存储 → 低 AMAT + 高容量。手段：更多行↓ miss ratio；合适块大小利用 DRAM 列突发；更多 way↓ 冲突；LRU（近似）选替换；write-back + dirty。最终用基准仿真在各项之间取最优组合。

整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L13 注解幻灯片。

源网页：13.1 Annotated Slides | Building the Beta

讲师：Chris Terman。图片直接引用 OCW 原站链接。

L13：构建 Beta（Building the Beta）

本讲增量搭建单周期 Beta：寄存器堆、ALU / 访存 / 分支 / LDR 数据通路，以及异常与中断；并汇总控制信号 ROM 方案。目标是“每时钟一条指令”的可工作 32 位 RISC。

1. CPU 设计权衡（CPU Design Tradeoffs）

正确执行 Beta ISA 是底线；还要权衡：性能（常用 MIPS = Millions of Instructions Per Second）、芯片面积（成本）、性能/价格、性能/瓦特等。Intel 8080（1974）约 0.29 MIPS；现代多核可达 $10^4\sim 10^5$ MIPS。Apple Watch 与高端桌面目标集不同。

2. 处理器性能（Processor Performance）

执行时间 $\propto$ 程序指令数 $\times$ 每条平均时钟数 $\times$ 时钟周期。可减少指令数、降低 CPI、或缩短周期（简化逻辑）。本讲实现每时钟一条指令；组合路径较长，日后可用流水线提吞吐。

3. 回顾：Beta ISA（Reminder: Beta ISA）

32 个 32 位寄存器。两类主要格式：

• opcode 高 2 位 0b10：双寄存器操作数（Ra、Rb）→ Rc
• 高 2 位 0b11：第二操作数为 16 位常量（$-32768\sim 32767$）；助记符加 C；访存与分支也用此格式

操作含算术、比较、布尔、移位。仅两种格式 → 译码/控制简单，许多指令位可直接接到数据通路。

4. 方法：增量加功能（Approach: Incremental Featurism）

顺序：先 ALU 指令 → 访存与分支 → 异常。构件：多位寄存器（上升沿加载）、大量 MUX、Part 1 的 ALU、以及寄存器堆与主存。

5. 多端口寄存器堆（Multi-ported Register File）

32 个带 EN 的寄存器：EN=1 时下一上升沿装入 D；禁止门控时钟（NO GATED CLOCKS）。两套读 MUX（地址 RA1/RA2）独立读；写口用 5 位 WA 译码选中一个 WE。R31 读出恒为 0。封装为双读一写寄存器堆。

6. 寄存器堆时序（Register File Timing）

读：地址稳定后经 $t_{\mathrm{PD}}$ 出数据。写：WA/WD/WE 须满足建立/保持时间。同一周期可读旧值、周期末写入、下一周期才见新值——可同址同周期“读旧写新”。

7. ALU 指令（ALU Instructions）

五步：Fetch（按 PC 取指）→ Decode（opcode→控制）→ Read（Ra/Rb）→ Execute（ALU + 下一 PC）→ Write-back（写 Rc）。时钟上升沿更新寄存器堆与 PC，标志当前指令结束。周期须覆盖五步总延迟；若 $t_{\mathrm{CLK}}=10\,\mathrm{ns}$ → 100 MHz → 100 MIPS。

8. 取指/译码（Instruction Fetch/Decode）

PC → 主存取指；ALU 类下一地址为 PC+4（专用加法器）。RESET 时 MUX 选初始 PC。部分指令字段可直连；其余控制由 opcode 逻辑产生。

9. ALU 操作数据通路 I（ALU Op Datapath I）

Ra/Rb/Rc 字段直连寄存器堆读写地址；读数进 ALU；ALUFN 由 opcode 经控制逻辑（可实现为 $2^6=64$ 项 ROM）给出。ALU 结果回写 Rc；WERF（write-enable register file）=1 时写入。课程吉祥物 Werf 即以此命名。

10. ALU 操作数据通路 II（ALU Op Datapath II）

取指后 Ra/Rb 读出 → ALUFN 选定 → 结果经 WERF=1 写回 Rc。RISC 优势：执行所需数据通路直观。

11. 带常量的 ALU I（ALU Operations with constant I）

第二操作数 = 指令低 16 位符号扩展。加 BSEL MUX：0 选寄存器，1 选常量。符号扩展纯接线：复制 ID[15] 十六次，无需门。

12. 带常量的 ALU II（ALU Operations with constant II）

BSEL=1，其余同双寄存器 ALU。至此已能执行大部分 ISA；剩下访存与分支。

13. Load 指令 I（Load Instruction I）

LD/ST 访问与指令同一主存（图上分画两盒）。地址计算同 ADDC：Ra + 符号扩展字面量，复用 ALU。LD：ALU 结果作地址；MOE=1 读出；经 WDSEL 三选一 MUX（另两路留给分支写回 PC+4 等）写回 Rc。MWE 用于写存。

14. Load 指令 II（Load Instruction II）

操作数选法同 ADDC，ALU 做 ADD；WDSEL=2 选存返回数据写寄存器堆。

15. Store 指令 I（Store Instruction I）

要写的数据来自 Rc，但 Rc 未接读口；ST 不用 Rb → 加 RA2SEL MUX：1 时第二读口地址用 Rc。该读数进主存 WD。ST 不写寄存器堆 → WERF=0。

16. Store 指令 II（Store Instruction II）

地址同 LD；MWR/MWE=1 在周期末写存；WERF=0；WDSEL 为 don’t care（可任选便于逻辑最小化）。注意：MWE 绝不能是 don’t care，以免误写。

17. JMP 指令 I（JMP Instruction I）

PCSEL MUX 选下一 PC：0→PC+4，2→Ra。JMP/分支还把 PC+4 写入 Rc（WDSEL=0）。

18. JMP 指令 II（JMP Instruction II）

WERF=1 写回 PC+4；PCSEL=2 选 Ra。其余多为 don’t care，但 MWR 必须安全为 0。

19. BEQ/BNE 指令 I（BEQ/BNE Instructions I）

偏移加法器：PC+4 +（字面量左移 2 位的符号扩展偏移）。乘 4 靠接线插两个 0；符号扩展复制 ID[15] 十四次。32 位 NOR 得 Z（Ra 全 0）。分支成立 → PCSEL=1 选目标；否则 PCSEL=0。

20. BEQ/BNE 指令 II（BEQ/BNE Instructions II）

PC+4 写 Rc；Z 与偏移加法器结果共同决定 PCSEL。

21. 相对加载 LDR（Load Relative Instruction）

LDR 像 LD，但地址来自分支偏移加法器——用于加载放在代码旁、装不下 16 位字面量的大常量。常量放过程后等位置，且须避免被当作指令执行。

22. LDR 指令 I（LDR Instruction I）

加 ASEL MUX：1 时第一 ALU 操作数来自偏移加法器；ALU 做布尔 “A” 把该值送到地址口。为何不把 ASEL 直接接到存地址？那样 LD/ST 地址会多串一级 MUX，拉长关键路径、拖慢所有指令时钟；ASEL 与 BSEL 延迟重叠则几乎零性能代价。

23. LDR 指令 II（LDR Instruction II）

偏移 → ASEL → ALU(“A”) → 存地址 → 数据经 WDSEL 写 Rc。

24. 异常（Exceptions）

指令无法执行时（非法 opcode / illop、地址越界、除零等）：停止用户程序，转入处理程序——可转储状态、或用软件模拟未实现指令再恢复。外部 I/O 事件则需中断当前程序、处理后无感恢复。硬件把异常当成强制过程调用，保存 PC+4 以便返回。这是用户程序与 OS 接口的关键。

25. 异常处理（Exception Processing）

打断当前程序，如同当前指令变成对 handler 的调用；handler 可用普通过程返回恢复。Exception：由当前程序某指令引起的同步异常。Interrupt：与程序无关的异步外部事件。

26. 异常实现（Exception Implementation）

两类实现相同：硬件表现得像 taken BR 到 0x4（同步）或 0x8（异步）；PC+4 写入 R30 = XP（exception pointer）。用户程序不可用 XP（随时可能被中断覆盖）。例：未实现 DIV → illop → 0x4 → handler 用 XP 取非法指令并模拟，再 JMP(XP) 继续。

27. 异常 I（Exceptions I）

WASEL MUX：1 时写回地址强制为 XP（R30），0 时用 Rc。PCSEL 增加常量输入 0x4 / 0x8。

28. 异常 II（Exceptions II）

PC+4 经 WDSEL 写入 XP；PCSEL=3 或 4 进 handler。被打断指令未执行；若要重试须先对 XP 减 4 再 JMP(XP)。

29. Beta：最终答案（Beta: Our Final Answer）

完整单周期数据通路已齐。硬件量不大，适合实验课亲手完成。现代 CPU 另有流水、多发射、复杂存储层次等（后续讲）。Beta 约 1–2 mm²，现代 Intel 芯片 300–600 mm²——多出来的面积为性能服务。

30. 控制逻辑（Control Logic）

按指令类汇总控制表（含异常与 RESET）；无关信号标 don’t care。MWE 与（多数情况下）WERF 必须有定义值。最简：opcode 索引 ROM；Z 与 IRQ 用少量逻辑修正 ROM 输出。亦可 Karnaugh 图做门级最小化——建议先 ROM 跑通再优化。

31. Beta Inside!

简单编码 + 只做常见操作的硬件；复杂/少见功能交给软件；异常机制在硬件不够时把控制交给软件。完成 Beta 设计是许多 MIT 学生的 “Yes!” 时刻——并收获 “Beta Inside” 贴纸。