计算机系统1

计算机系统一#

0. 总体主线#

数字逻辑与计算机组成可以从两条线一起理解：一条是“硬件从门电路长成 CPU”，另一条是“程序从高级语言落到机器指令并在硬件上运行”。

二进制编码
-> 数字逻辑基础
-> 组合逻辑电路
-> 时序逻辑电路
-> FPGA / Verilog HDL
-> 运算方法和功能部件
-> 指令系统 ISA
-> CPU 微体系结构
-> 存储器层次结构
-> 系统互连与输入/输出
-> 程序编译、链接、加载和运行

抽象层关系#

章节之间的连接#

1. 二进制编码与计算机系统抽象#

冯·诺依曼结构和程序执行#

Von-Neumann 模型#

Von-Neumann 模型把计算机抽象成：

核心思想：

• Stored program：程序也作为二进制数据存放在内存中。
• Binary：指令、数据最后都编码为 0/1。
• CPU 自动执行指令序列，而不是人工设置每一步。

程序表示#

程序语言的层次：

程序执行的典型阶段：

1. Instruction Fetch：从 PC 指向的内存地址取指令。
2. Instruction Decode：解释 opcode 和 operand 字段。
3. Execute：ALU 或控制逻辑执行操作。
4. Memory Access：按需读写数据内存。
5. Write Back：把结果写回寄存器或状态。

计算机系统抽象层和 ISA 位置#

从应用问题到硬件电路，中间有多个抽象层：

应用问题
-> 算法
-> 高级语言程序
-> 操作系统 / 虚拟机
-> 指令集体系结构 ISA
-> 微体系结构
-> RTL / 功能部件
-> 数字逻辑电路
-> 器件

ISA 是软件和硬件之间的桥梁。它规定“机器能执行什么”，例如：

• 有哪些指令。
• 指令如何编码。
• 有哪些寄存器。
• 操作数如何寻址。
• 异常和中断如何表现给软件。

微体系结构关注“如何实现 ISA”。例如，ISA 规定是否有乘法指令；乘法指令到底用移位加法实现，还是用专用乘法器实现，是微体系结构问题。

二进制数、数据类型、整数和补码#

计算机内部处理的所有信息都以 0 和 1 编码，原因包括：

• 二进制只有两个稳定状态，物理实现可靠。
• 二进制计数和运算规则简单。
• 0/1 与逻辑真假自然对应，便于用逻辑门实现计算。

机器级程序中常见基本数据类型：

进制表示与转换#

位置计数法的核心是“每一位的权重不同”。十进制：

二进制同理，只是基数从 10 换成 2：

整数从十进制转二进制：

1. 不断除以 2。
2. 记录每一步余数。
3. 从最后一个余数向前读。

例：

135 / 2 = 67 ... 1
 67 / 2 = 33 ... 1
 33 / 2 = 16 ... 1
 16 / 2 =  8 ... 0
  8 / 2 =  4 ... 0
  4 / 2 =  2 ... 0
  2 / 2 =  1 ... 0
  1 / 2 =  0 ... 1

(135)_10 = (10000111)_2

小数从十进制转二进制：

1. 不断乘以 2。
2. 每次取整数部分作为下一位。
3. 剩余小数继续乘。

例：

0.6875 x 2 = 1.375  -> 1
0.375  x 2 = 0.75   -> 0
0.75   x 2 = 1.5    -> 1
0.5    x 2 = 1.0    -> 1

(0.6875)_10 = (0.1011)_2

二进制基础运算#

单 bit 加法：

单 bit 减法可以看成带 borrow in 的运算：

二进制乘法和十进制竖式类似：

• multiplier 当前位为 1，就加上 shifted multiplicand。
• multiplier 当前位为 0，就跳过该部分积。
• 固定位宽机器会截断超出位数的高位。

二进制除法的直觉是反复比较 remainder 和 divisor：

• 如果 remainder 足够大，商位写 1，并减 divisor。
• 如果 remainder 不够大，商位写 0。
• 硬件实现可发展为 restoring / non-restoring division。

C 中位运算与逻辑运算#

C 的 Bit-Level Operations 把操作数看成 bit vector，逐位运算：

logical operations 把 0 看成 false，把任何非 0 看成 true，结果只会是 0 或 1：

易错对比：

0x69 & 0x55   // 0x41，逐位计算
0x69 && 0x55  // 1，只判断二者是否非 0

p && *p       // 若 p 为 NULL，右侧不会被求值

固定宽度与机器数#

计算机内部的数是固定宽度的 bit pattern。这里要区分：

• machine number：机器内部编码。
• true value：该编码按某种解释方式得到的数学值。

对 $n$ 位无符号整数：

对 $n$ 位二进制补码整数：

常见有符号编码#

补码的定义：

补码负数转换快捷法：

1. 对绝对值的二进制按位取反。
2. 加 1。

补码取负也满足：

补码手算完整流程#

例：用 8 bit 表示 -13。

1. 先写 13 的二进制：

13 = 0000 1101

1. 按位取反：

1111 0010

1. 加 1：

1111 0011

所以：

-13 的 8-bit two's complement = 1111 0011

反过来，看到 1111 0011：

1. 最高位是 1，所以按补码解释为负数。
2. 取反加 1 得绝对值：

1111 0011
0000 1100   // invert
0000 1101   // +1

所以它表示 -13。

补码的一个直观理解是“模环”：

8-bit 下模数是 256
-13 ≡ 256 - 13 = 243
243 = 1111 0011

这也是为什么同一个 bit pattern：

1111 0011

按 unsigned 看是 243，按 signed two's complement 看是 -13。

模运算与溢出#

固定 $w$ 位机器会丢弃超出的高位，因此本质是在模 $2^w$ 下计算。

无符号加法：

无符号乘法：

有符号补码加法和无符号加法在 bit-level 上完全相同，区别只是解释结果的方式。

signed 与 unsigned 的映射#

signed 和 unsigned 互相转换时：

• bit pattern 不变。
• 解释方式改变。

若 $w$ 位补码值 $x < 0$，转为 unsigned 时会变成：

这解释了 C 中很多“看起来奇怪”的比较：

-1 < 0U     // false, 因为 -1 被转换成 unsigned 后是很大的数
(unsigned)-1 > -2  // true

易错点：

• C 表达式中若 signed 和 unsigned 混用，signed 通常会隐式转换为 unsigned。
• 不要因为变量“应该非负”就随便用 unsigned，循环倒着写时很容易下溢。

signed / unsigned 转换例题#

以 4 bit 为例：

规律：

• 最高位为 0 时，signed 和 unsigned 值相同。
• 最高位为 1 时，signed 值 = unsigned 值 $-2^w$。

例如 $w=4$：

1001 unsigned = 9
1001 signed   = 9 - 16 = -7

C 语言比较例：

int x = -1;
unsigned y = 1;
printf("%d\n", x < y);

这里 \(x\) 会被转换成 unsigned：

-1 的 32-bit pattern = 0xffffffff
按 unsigned 解释 = 4294967295

所以：

4294967295 < 1  // false

扩展与截断#

扩展：

截断：

• 直接丢掉高位。
• 对 unsigned 相当于取模。
• 对 signed 会先得到截断后的 bit pattern，再按补码解释。

截断和扩展例题#

例：把 8-bit signed 1111 0011 扩展到 16 bit。

最高位是 1，所以符号扩展：

1111 0011
1111 1111 1111 0011

值仍然是 -13。

如果按 unsigned 扩展，则高位补 0：

1111 0011
0000 0000 1111 0011

值变成 243。

截断例子：

int x = 53191;        // 十六进制 0xCFC7
short y = (short)x;   // 保留低 16 bit

如果 short 是 16-bit signed，则 0xCFC7 最高位为 1，所以 y 是负数：

0xCFC7 unsigned = 53191
0xCFC7 signed   = 53191 - 65536 = -12345

这类题的稳定做法：

1. 先写目标宽度的 bit pattern。
2. 再决定按 signed 还是 unsigned 解释。

移位#

负数想实现 C 整数除法那种“向 0 截断”，右移前要加 bias：

这里适用于 $x<0$ 的情况。

有符号溢出判断#

二进制补码加法中：

• 正数 + 正数 = 负数，则正溢出。
• 负数 + 负数 = 正数，则负溢出。
• 一正一负相加不会溢出。

等价判断：

• 操作数符号相同，结果符号不同，则 overflow。
• 最高有效值位进位和符号位进位不同，则 overflow。

常见 flags：

溢出判断例题#

4-bit signed two's complement 范围：

-8 ~ +7

例 1：\(4 + 5\)

  0100   // 4
+ 0101   // 5
------
  1001

1001 按 signed 是 -7。两个正数相加得到负数，所以正溢出。

例 2：\(-4 + -5\)

  1100   // -4
+ 1011   // -5
------
1 0111

丢弃第 5 位后得到 0111，即 \(+7\)。两个负数相加得到正数，所以负溢出。

例 3：\(-4 + 5\)

  1100   // -4
+ 0101   // 5
------
1 0001

丢弃高位后是 0001，即 1。一正一负相加不会 signed overflow。

硬件中常用判断：

OF = carry into sign bit XOR carry out of sign bit

或者从符号看：

OF = (a_sign == b_sign) && (sum_sign != a_sign)

浮点数和数据存储顺序#

基本形式#

IEEE 浮点数的数值形式：

字段：

单精度：

双精度：

规格化数#

条件：

exp != 000...0 且 exp != 111...1

指数：

其中：

尾数：

这个隐含的前导 1 是规格化数的关键。

非规格化数#

条件：

exp = 000...0

指数：

尾数：

作用：

• 表示非常接近 0 的数。
• 实现 gradual underflow。
• \(\exp=0, frac=0\) 表示 \(+0\) 或 -0。

特殊值#

浮点数编码例题#

例：把 13.25 表示成 IEEE 754 单精度的结构。

先转二进制：

13 = 1101
0.25 = 0.01
13.25 = 1101.01

规格化：

1101.01 = 1.10101 x 2^3

所以：

s = 0
E = 3
Bias = 127
Exp = E + Bias = 130 = 10000010
frac = 10101000000000000000000

最终结构：

0 10000010 10101000000000000000000

这类题不一定要求写完整 32 位十六进制，但必须能判断：

• sign bit。
• exponent 是否要加 bias。
• frac 是去掉规格化前导 1. 后的小数部分。

非规格化数的识别题：

exp = 00000000, frac != 0

此时：

M = 0.frac
E = -126   // single precision

特殊值识别题：

exp = 11111111, frac = 0      -> infinity
exp = 11111111, frac != 0     -> NaN

浮点运算的核心#

浮点加法：

1. 对阶：把较小指数的尾数右移。
2. 尾数相加或相减。
3. 规格化结果。
4. 舍入。
5. 检查 overflow / underflow。

浮点乘法：

1. 符号：$s = s_1 \oplus s_2$。
2. 尾数：$M = M_1 \times M_2$。
3. 指数：$E = E_1 + E_2$。
4. 规格化和舍入。

重要性质：

• 浮点加法通常不满足结合律。
• 浮点乘法也通常不满足结合律和分配律。
• 默认舍入通常是 round-to-nearest-even。

浮点舍入为什么会出问题#

二进制浮点只能保存有限个 frac bit。若精确结果不能放进 frac，就必须舍入。

例：

float a = 1e20;
float b = -1e20;
float c = 3.14;

比较：

(a + b) + c
a + (b + c)

第一种：

a + b = 0
0 + c = 3.14

第二种：

b + c ≈ b   // c 太小，在对阶时被舍掉
a + b = 0

所以浮点加法不满足结合律。考试或调试时看到浮点比较，不要默认它像数学实数那样精确。

数据宽度常用单位：

大端和小端：

大小端只影响多字节数据在内存中的字节排列，不改变数据本身的数值。

本章英文术语#

2. 数字逻辑基础#

逻辑门和数字抽象#

基本逻辑门：

数字信号来自连续物理量，例如电压。数字抽象把电压划分为低电平 0、高电平 1，并在中间留下 threshold region / forbidden zone，避免噪声把 0 和 1 混淆。合法输入必须产生合法输出，这就是 static discipline。

Noise Margin / 噪声容限：

理想 buffer 可近似理解为阈值在中间、噪声容限接近 $V_{DD}/2$；真实 buffer 会有非理想转换区，因此 $NM_H$ 和 $NM_L$ 都小于理想值。

CMOS 晶体管和门电路#

CMOS 中常见两类晶体管：

CMOS 门电路用 pMOS 上拉网络和 nMOS 下拉网络互补实现逻辑函数。NAND、NOR、NOT 是常见基础结构。

电路参数：

Power Dissipation / power consumption 复习时要分清 static power 和 dynamic power：前者来自静态漏电或静态电流，后者主要来自节点电容充放电和信号切换。

布尔代数#

基本逻辑优先级：

1. Parentheses
2. NOT
3. AND
4. OR

常用定理：

Shannon expansion 把一个函数按某个变量拆成两种情况，是理解 mux、递归化简和 BDD 的基础：

对偶形式可写为：

真值表、表达式与标准形式#

描述逻辑函数的常见方式：

术语：

Canonical SOP 使用输出为 1 的 minterms：

Canonical POS 使用输出为 0 的 maxterms：

canonical form 在固定变量顺序下唯一；standard SOP/POS 不要求每个项都包含所有变量，因此不唯一。把 standard SOP 变成 canonical SOP 时，可对缺失变量乘以 $(x+\overline{x})$ 后展开；把 standard POS 变成 canonical POS 时，可对缺失变量加上 $x\overline{x}$ 后用分配律展开。

例：三输入函数 $F(x,y,z)$ 在编号 1, 2, 4, 7 时输出 1。

按变量顺序 x y z：

所以：

如果用 decoder 实现，一个 3-to-8 decoder 的每根输出线天然对应一个 minterm，把 1,2,4,7 输出线接到 OR gate 即可。

K-map 化简#

K-map 的本质是把只差一个变量的 minterms 放在相邻格子。相邻项可以合并，因为：

化简步骤：

1. 把输出为 1 的格子填入 K-map。
2. 按 $1,2,4,8,\ldots$ 个格子分组。
3. 每组必须是矩形，且可跨边界。
4. 每组越大，消去变量越多。
5. 每个 1 至少覆盖一次。
6. 得到每组中保持不变的变量，组成 product term。
7. 所有 product term 相加得到 SOP。

K-map 术语：

don't care 的使用：

• 可以当 1 用来扩大分组。
• 也可以不用。
• 目标是让表达式更简单，而不是机械地包含所有 don't care。

本章英文术语#

3. 组合逻辑电路#

组合逻辑电路概述#

组合逻辑电路满足：

• 输出只由当前输入决定。
• 不含存储状态。
• 不允许形成无意义反馈环。

设计流程：

1. 确定输入、输出和逻辑关系。
2. 写 truth table。
3. 得到逻辑函数并化简。
4. 画电路图或写 HDL。
5. 画 timing diagram。
6. 做 timing analysis。

HDL-based design flow 常见顺序：

logic design with HDL -> simulation -> synthesis -> physical design / FPGA implementation

simulation 验证功能是否符合预期；synthesis 把 HDL 转成门级结构；FPGA flow 的最后一步通常是生成并下载 bitstream。

典型组合逻辑部件#

Decoder：

• $n$ 位输入，最多 $2^n$ 个 one-hot 输出。
• 可用多个小 decoder 和 AND gate 扩展，例如用 1-to-2 结构扩成 2-to-4、3-to-8。
• 常用于地址译码、minterm 生成和控制信号生成。

Encoder：

• 把 one-hot 或 priority input 编成二进制输出。
• 普通 encoder 的两个问题：多个输入同时为 1 时不明确；全 0 和 $I_0=1$ 容易混淆。
• priority encoder 通过优先级解决冲突，并常带 valid bit 表示至少有一个输入有效。

Multiplexer：

• 用选择信号从多个输入中选一个输出。
• $n$ 个 select bit 可以选择 $2^n$ 路输入。
• 逻辑上可看成 decoder 加若干 AND-OR 结构。

Demultiplexer：

• 一个输入分发到多个输出。
• 本质上可看成带 enable/data input 的 decoder。

Half Adder：

Full Adder：

组合逻辑时序分析#

传播延迟：

污染延迟：

critical path：

• 总传播延迟由最长路径决定。
• 如果路径上有多个门，总 $T_{pd}$ 是该路径上各门 $T_{pd}$ 之和。

shortest path：

• 总污染延迟由最短路径决定。
• 常用于分析 hold constraint。

race hazard / glitch：

• 单个输入变化可能沿多条不同延迟路径影响输出。
• 如果输出发生短暂错误跳变，就是 glitch。
• 即使最终逻辑值正确，glitch 也可能被后级时序元件采样到。

本章英文术语#

4. 时序逻辑电路#

时序逻辑与有限状态机#

时序逻辑电路由组合逻辑和存储元件组成，输出不仅依赖当前输入，还依赖过去状态：

有限状态机两种模型：

一般规律：

• Mealy 输出标在边上，常用 input/output。
• Moore 输出标在状态上，通常状态数更多。

组合逻辑与时序逻辑的判断题#

看到题目时可以这样判断：

典型组合逻辑：

• decoder
• encoder
• mux
• adder
• ALU
• barrel shifter

典型时序逻辑：

• register
• counter
• shift register
• FSM
• PC
• register file 的写入部分

Latch 与 Flip-Flop#

双稳态电路能保存 1 bit 状态。Latch 通常由交叉耦合门构成，flip-flop 可由多个 latch 组合而成。

SR latch：

• 有 Set / Reset 输入。
• NOR 型 SR latch 中，\(S=R=1\) 是非法组合。
• NAND 型 SR latch 通常输入低有效，非法组合对应 \(S'=R'=0\)。

D latch：

• \(C=1\) 时，\(D\) 传到 \(Q\)。
• \(C=0\) 时，保持旧值。
• 用一个 data input 避免 SR latch 的非法输入组合。

Pulse-triggered / master-slave flip-flop：

• 用两个 latch 串联，并让两级在不同 clock phase 打开。
• SR / JK pulse-triggered 结构可能出现 1's catching：输入端短暂出现的 1 被 master latch 捕获，即使后来消失，也会传到 slave。

Edge-triggered D flip-flop：

• 只在上升沿或下降沿采样 \(D\)。
• D 输入消除了 SR / JK 中一些输入组合问题。
• 是同步时序电路最常用的存储元件。

常见扩展：

• enabled D flip-flop：\(EN=1\) 时更新，\(EN=0\) 时保持。
• resettable D flip-flop：可以同步或异步 reset。
• JK flip-flop：\(J=K=1\) 时翻转。
• T flip-flop：\(T=1\) 时翻转，\(T=0\) 保持。

触发器描述表#

Characteristic table 描述“当前输入和当前状态会得到什么下一状态”；excitation table 反过来描述“想从当前状态变到目标下一状态，需要什么输入”。

SR flip-flop：

约束下的特征方程：

D flip-flop：

JK flip-flop：

常见写法：

T flip-flop：

常用 excitation table：

Verilog 时序逻辑模板#

同步寄存器：

always @(posedge clk) begin
    q <= d;
end

带同步 reset：

always @(posedge clk) begin
    if (rst)
        q <= 1'b0;
    else
        q <= d;
end

带异步 reset：

always @(posedge clk or posedge rst) begin
    if (rst)
        q <= 1'b0;
    else
        q <= d;
end

时序逻辑经验：

• 时序逻辑用 nonblocking assignment：\(\le \)。
• 组合逻辑常用 blocking assignment：\(=\)。
• 一个寄存器最好只在一个 always block 里赋值。
• reset 是同步还是异步，要和题目或实验框架一致。

FSM 分析与设计流程#

分析一个时序电路：

1. 找状态变量。
2. 写 next-state equation。
3. 写 output equation。
4. 列 state table。
5. 画 state diagram。

设计一个 FSM：

1. Specification：明确功能。
2. Formulation：得到 state diagram 或 state table。
3. State assignment：给状态分配二进制编码。
4. Flip-flop input equation：根据触发器类型推输入方程。
5. Output equation：推输出方程。
6. Optimization：化简。
7. Technology mapping：映射到门和触发器。
8. Verification：验证。

状态化简的依据是状态等价：如果两个状态对所有输入产生相同输出，并转向相同或等价的下一状态，则可以合并。

两个状态等价的条件：

• 对每个可能输入，输出完全相同。
• 对每个可能输入，next state 相同或等价。

序列检测器例子：识别 1101#

Mealy 设计思路：

当在 D 状态读到 1 时，识别到 1101，输出 1。由于最后一个 1 也可能是下一次匹配的起点，所以转回 B。

Moore 版本需要额外状态 E 来输出 1，因此通常“Moore is more”。

对应状态表可以从状态图直接读出：每个 present state 在输入为 0 和 1 时分别写 next state 和 output。状态表也可用于发现等价状态并合并。

FSM 的 Verilog 写法#

推荐三段式写法：

localparam S_IDLE = 2'b00;
localparam S_1    = 2'b01;
localparam S_11   = 2'b10;
localparam S_110  = 2'b11;

reg [1:0] state, next_state;

always @(posedge clk) begin
    if (rst)
        state <= S_IDLE;
    else
        state <= next_state;
end

always @(*) begin
    next_state = state;
    case (state)
        S_IDLE: next_state = x ? S_1 : S_IDLE;
        S_1:    next_state = x ? S_11 : S_IDLE;
        S_11:   next_state = x ? S_11 : S_110;
        S_110:  next_state = x ? S_1 : S_IDLE;
        default: next_state = S_IDLE;
    endcase
end

always @(*) begin
    y = 1'b0;
    if (state == S_110 && x)
        y = 1'b1;   // Mealy: output depends on state and input
end

对应的是 Mealy 版本 1101 序列检测器。输出在读到最后一个 1 的那个周期产生。

若改成 Moore，通常要增加一个 \(S_{1101}\) 状态，并在该状态输出 1：

assign y = (state == S_1101);

Moore 输出更稳定，但可能晚一个周期，并且状态数可能更多。

状态编码#

若有 $m$ 个状态，至少需要 $n$ 位：

状态编码会影响逻辑化简成本。经验规则：

• 对某输入有相同 next state 的状态，尽量编码相邻。
• 同一个状态的多个 next states，尽量编码相邻。
• 输出相同的状态，尽量编码相邻。

Gray code assignment 可减少相邻状态切换时改变的位数，常能降低两级逻辑优化后的 gate input cost。状态编码不同，不改变 FSM 功能，但会改变 next-state equation 和 output equation 的复杂度。

时序约束#

对 D flip-flop：

• $t_{setup}$：时钟沿前输入必须稳定的时间。
• $t_{hold}$：时钟沿后输入必须继续稳定的时间。
• $t_{ffpd}$：clock-to-Q 延迟。

时钟周期约束：

hold 约束：

Setup / Hold 约束例题#

假设：

t_ffpd = 2 ns
t_comb = 7 ns
t_setup = 1 ns

则时钟周期至少：

最大频率：

如果组合逻辑太长，解决方向：

• 优化组合逻辑。
• 插入 pipeline register，把长路径切短。
• 降低 clock frequency。

hold violation 和 setup violation 的直觉不同：

• setup violation：数据来得太晚。
• hold violation：数据变得太早。

setup 可通过降频缓解，hold 通常不能单靠降频解决。

Register、Bus 与 Datapath#

寄存器是多个触发器组成的多 bit 存储单元。

用途：

• 临时保存数据。
• 构建 datapath。
• 支持 register transfer operation。

微操作 microoperation：

数字系统常分成：

寄存器传输结构：

Multiplexer bus 用 mux 保证只选一路；3-state bus 通过 high-Z 状态断开未选 driver，设计时必须确保 enable 互斥。

Shift Register#

移位寄存器可以把数据向 MSB 或 LSB 方向移动。

常见功能：

• shift right
• shift left
• parallel load
• hold

如果每个 D flip-flop 前放一个 4-input MUX，就可以统一支持这几种操作。

基本 serial shift register：

• Data input 是 serial input。
• 每个 clock 把数据向一侧移动一位。
• 所有触发器输出一起看时，就是 parallel output。

并行装入 parallel load 允许一次性写入所有位，之后再进行移位；带可变 shift amount 的移位器可用多级 mux 组成。

Counter#

计数器是按固定状态序列运行的时序电路。

用途：

• 计时。
• 计数事件。
• 记录发送或接收了多少 bit。
• CPU 中的 Program Counter。

Ripple counter：

• 只有最低位直接接全局时钟。
• 高位时钟来自低位输出。
• 变化逐级 ripple。
• 最坏延迟约为 $n \cdot t_{PHL}$。
• 严格说不是完全同步结构，因为各位不是同一 clock edge 同时更新。

Synchronous counter：

• 所有触发器共享同一个 clock。
• 组合逻辑计算 next state。
• 更适合高速设计。
• up-counter 可用 incrementer 产生下一状态。
• count enable 让 counter 在 \(EN=0\) 时保持不变。
• carry out 可接到更高位 counter 的 enable，用于级联。

同步计数器内部常见 carry chain：

• serial gating：carry 逐级通过 AND 链，路径较长。
• parallel gating：并行生成部分 carry，类似 carry lookahead，可减少大计数器延迟。

本章英文术语#

5. FPGA 设计和 Verilog HDL#

可编程逻辑器件和 FPGA#

FPGA 是可编程逻辑器件的一类。使用者通过配置文件改变内部逻辑连接，从而实现不同数字电路。它适合教学和实验，因为可以在硬件上验证 CPU、控制器、数据通路等设计。

相关概念：

HDL 设计流程#

基于 HDL 的数字电路设计通常按下面的链路推进：

1. Logic design with HDL：用 HDL 描述电路结构和行为。
2. Simulation：编写 testbench 验证功能是否正确。
3. Synthesis：把 HDL 综合为门级网表。
4. Physical design：布局布线，确定实际硬件连接。
5. ASIC tape-out 或 FPGA bitstream download：生成版图或下载到 FPGA。

仿真检查的是“逻辑行为是否符合预期”，综合关注的是“这些写法能不能变成实际硬件”。所以 Verilog 不是普通软件语言，写代码时要一直想它对应的电路是什么。

Verilog 基础语法#

模块结构：

module top(
    input a,
    input b,
    output c
);
    assign c = a & b;
endmodule

关键点：

• Verilog 区分大小写。
• 关键字小写。
• // 表示单行注释，\(/* ... */\) 表示多行注释。
• assign 常用于组合逻辑的连续赋值。

数字常量格式：

<位宽>'<进制><数值>

例：

4'b1010
8'hff
16'd255

常见进制：

特殊值：

• \(x\)：unknown。
• \(z\)：high impedance。
• ?：在数字常量中等价于 \(z\)。

负数写法要注意位宽归属：

-6'd3   // 正确
4'd-2   // 错误

常见数据类型：

端口常见规则：

• input 端口定义一般是 wire。
• output 可为 wire 或 reg，取决于赋值方式。
• 实例化时 output 接到外部 wire。

Verilog 建模方式和模板#

assign 适合简单组合逻辑：

assign y = sel ? a : b;
assign sum = a + b;

\(always @(*)\) 适合较复杂的组合逻辑：

always @(*) begin
    y = 1'b0;          // 默认值，避免 latch
    case (op)
        2'b00: y = a & b;
        2'b01: y = a | b;
        2'b10: y = a ^ b;
        2'b11: y = ~a;
        default: y = 1'b0;
    endcase
end

组合逻辑最重要的检查：

• 每条路径都给输出赋值。
• case 最好有 default，或者在前面给默认值。
• 不要在组合逻辑里使用 clock edge。
• 分支不全会让综合工具推导 latch。

错误例子：

always @(*) begin
    if (en)
        y = a;
end

当 \(en=0\) 时，\(y\) 没被赋值，综合工具会认为它必须“记住原值”，于是推导出 latch。

时序逻辑通常由触发器实现，模板是：

always @(posedge clk) begin
    if (rst)
        q <= 1'b0;
    else
        q <= d;
end

注意：

• 时序逻辑通常用非阻塞赋值 \(\le \)。
• 组合逻辑常用阻塞赋值 \(=\)。

本章英文术语#

6. 运算方法和运算部件#

基本运算部件#

串行进位加法器 RCA：

• 由多个全加器串接。
• 低位进位逐级传到高位。
• 硬件简单，但延迟较大。

并行进位加法器 CLA：

定义：

进位：

CLA 通过并行生成进位减少串行等待。

带标志加法器需要生成：

ALU 支持多种算术逻辑操作，是 CPU 运算器核心。

定点数运算#

补码加减法：

所以加法和减法可以共用同一个加法器，只需控制 B 是否取反以及最低位进位输入是否为 1。

有符号溢出判断：

• 两个正数相加得到负数，正溢出。
• 两个负数相加得到正数，负溢出。
• 一正一负相加不会溢出。

原码乘法：

• 符号单独处理。
• 数值部分按无符号乘法。

补码乘法：

• 可用 Booth 编码等方法处理连续 1。
• 核心思想是将连续 1 的部分积转换为少量加/减操作。

除法：

• 恢复余数除法：减过头时加回除数。
• 不恢复余数除法：不立即恢复，而在下一步改为加除数修正。

浮点数运算#

浮点加减：

1. 对阶。
2. 尾数相加或相减。
3. 规格化。
4. 舍入。
5. 检查溢出、下溢和特殊值。

浮点乘除：

• 符号由操作数符号决定。
• 指数相加或相减。
• 尾数相乘或相除。
• 再规格化和舍入。

浮点运算的重点不是“精确实数运算”，而是“有限位宽下的近似运算”。

加法器、ALU 和乘除法硬件#

Carry Propagate Adder#

常见 CPA：

RCA 延迟：

CLA generate 与 propagate#

第 $i$ 位：

carry：

sum：

CLA 的思想是先算每一位或每个 block 的 generate/propagate，减少 carry 串行传播。

Adder 设计细化#

RCA：

FA0 -> FA1 -> FA2 -> ... -> FAN-1

carry 必须一级一级传，所以最坏情况很慢。

CLA 的关键是把：

展开。例如：

这样 carry 可以由多级门并行算出，而不是等前一级 full adder 的 carry out。

Prefix adder 更进一步，把 generate/propagate 做成树形前缀运算：

1-bit group -> 2-bit group -> 4-bit group -> 8-bit group -> ...

所以延迟大致随 $\log N$ 增长，但布线和硬件成本更高。

CLA 可分层做成 block carry lookahead。4-bit block 常写成：

其中：

16-bit 或 32-bit CLA 可以用多个 4-bit block 级联，再对 block-level 的 $G$ 和 $P$ 做 lookahead。常见延迟估算：

这里 $k$ 是每个 CLA block 的位数。

减法器#

减法 $X-Y$ 可以两种实现：

1. 串接 full subtractor，borrow ripple。
2. 用加法器计算：

因此 adder-subtractor 通常通过控制信号决定是否取反 B 并把最低位 carry-in 设为 1。

ALU#

ALU 是 processor datapath 的核心组合逻辑，用来执行：

• arithmetic：add, subtract
• logic：AND, OR, XOR
• shift
• comparison：SLT

典型 datapath：

registers -> ALU -> destination register

ALU 与寄存器配合时，一个 register transfer operation 通常在一个 clock cycle 内完成。

SLT#

SLT 即 set less than。常见做法：

1. 计算 $A-B$。
2. 根据符号位和 overflow 判断 $A<B$。
3. 结果低位置 1，高位补 0。

不能只看减法结果符号位，因为 signed overflow 会影响符号位含义。

ALU 控制信号理解#

一个简单 ALU 可以把多个操作共用硬件：

加法和减法可共用 adder：

SUB: A - B = A + ~B + 1

因此控制信号可以做：

Binvert = 1
Cin = 1

SLT 常基于 subtraction，但 signed SLT 要考虑 overflow：

less = sum_sign XOR overflow

因为 overflow 会让符号位“翻错方向”。

Flag 与简单 ALU 例子#

带 flags 的 adder / ALU 常输出：

一个简化 ALU 的控制可以这样理解：

实际 CPU 的 ALU 通常把加法器、逻辑门、移位器和比较结果接到一个 mux，控制信号选择最终输出。

Barrel Shifter#

barrel shifter 用多级 mux 在一个组合逻辑路径里完成可变位移，不需要一位一位移动。

以 4-bit rotate-left 为例：

• 第一级根据 shift amount 的 bit 0 决定是否左转 1 位。
• 第二级根据 shift amount 的 bit 1 决定是否左转 2 位。
• 两级组合后可实现左转 0、1、2、3 位。

普通 shift register 是时序部件，通常每个 clock 移一位；barrel shifter 是组合部件，可在一个周期内根据 shift amount 直接得到结果，但硬件 mux 更多。

乘法基本思想#

二进制乘法和十进制乘法类似：

• multiplier 的某位为 1，则加入 shifted multiplicand。
• multiplier 的某位为 0，则不加。
• 部分积相加得到结果。

硬件实现会在 area 和 time 间折中：

• 宽 ALU + 多寄存器：简单但硬件多。
• 复用较窄 ALU：硬件少但多周期。
• array multiplier：并行加部分积，快但面积大。

常见迭代乘法实现：

有符号乘法#

简单做法：

1. 记录 operands 的符号。
2. 转成正数做无符号乘法。
3. 根据符号异或决定结果符号。

也可以通过符号扩展和 Booth encoding 直接处理补码。

Booth Encoding#

Booth 算法的核心：

• 把连续的一串 1 变成“开始减一次，结束加一次”。
• 对连续 1 很长的 multiplier，可以减少部分积数量。

1-bit Booth 规则：

直观理解：

Booth 算法更直观的例子#

计算 M x 01111000。

普通乘法看到四个连续的 1，需要：

M<<3 + M<<4 + M<<5 + M<<6

Booth 把它看成：

01111000 = 10000000 - 00001000

所以：

M x 01111000 = (M << 7) - (M << 3)

从 4 次加法变成 1 次加法意义上的高位项和 1 次减法。连续 1 越长，Booth 越有优势。

判断边界：

0 -> 1 : run begins, subtract
1 -> 0 : run ends, add

从右往左扫描乘数时，本质就是检测这些连续 1 的边界。

除法#

无符号除法本质上反复判断：

可以通过：

来判断。

硬件除法常见状态：

做题时可以把每一轮看成：移动、试减、根据余数符号写商位、必要时修正。

Restoring division：

• 先减 divisor。
• 如果 remainder 变负，恢复原值。
• 每 bit 可能需要两次 ALU 操作。

Non-restoring division：

• 如果上一步 remainder 为负，下一步改为加 divisor。
• 避免立即 restore。
• 可以做到约 1 bit per cycle。

有符号除法：

• quotient 的符号由 operands 符号异或决定。
• 非零 remainder 的符号应与 dividend 一致。

Restoring / Non-restoring Division 对比#

Restoring division 每一步：

1. \(R = R - D\)
2. 若 \(R \ge 0\)，商位写 1。
3. 若 \(R < 0\)，商位写 0，并 \(R = R + D\) 恢复。

缺点：

• 失败时要多做一次加法恢复。

Non-restoring division 的想法：

• 如果上一步减过头导致 \(R < 0\)，下一步不要先恢复。
• 下一轮改成加 divisor，把效果补回来。

所以每轮根据 remainder 符号选择：

最后若 remainder 为负，再做一次修正。

本章英文术语#

7. 指令系统和 RISC-V#

指令系统概述#

指令系统是 ISA 的核心。每条指令规定：

• 做什么操作。
• 操作数从哪里来。
• 结果写到哪里。
• 下一条指令如何确定。

指令通常包含：

常见操作类型：

指令系统设计#

设计 ISA 需要权衡：

• 指令数量多少。
• 指令格式固定还是可变。
• 操作数个数。
• 寻址方式多少。
• 是否采用 load-store 风格。
• 是否支持异常、中断和特权机制。

寻址方式：

指令系统风格：

RISC-V 架构#

RISC-V 命名：

RV + 位宽 + 扩展

例：

RISC-V 常见指令格式：

RISC-V 设计特点：

• 寄存器字段位置尽量固定。
• 立即数符号位固定在指令最高位附近，便于符号扩展。
• 无分支延迟槽。
• 基础指令集小，扩展模块化。

ISA 设计、数据通路需求和 RISC-V 细节#

ISA 是什么#

ISA 是软件和硬件之间的契约：

• instruction set
• registers
• memory organization
• addressing modes
• exception / interrupt behavior

ISA 不是具体微架构。同一个 ISA 可以有多个实现。

简化 MIPS 数据通路#

以简化 MIPS 为例，支持：

• addu rd, rs, rt
• subu rd, rs, rt
• ori rt, rs, imm16
• lw rt, imm16(rs)
• sw rt, imm16(rs)
• beq rs, rt, imm16

需要的硬件部件：

PC 更新：

• 顺序执行：\(PC <- PC + 4\)
• branch taken：\(PC <- PC + 4 + (sign_{ext}(imm_{16}) << 2)\)

单周期数据通路信号怎么想#

以简化 MIPS / 类似单周期 CPU 为例，做题时按 instruction 分类。

R-type addu rd, rs, rt：

ori rt, rs, imm16：

lw rt, imm16(rs)：

sw rt, imm16(rs)：

beq rs, rt, imm16：

做数据通路题的顺序：

1. 这条指令要不要写寄存器？
2. 写哪个寄存器？
3. ALU 第二个输入来自寄存器还是立即数？
4. 立即数是 sign extend 还是 zero extend？
5. 结果来自 ALU 还是 memory？
6. 要不要写 memory？
7. PC 是 \(PC+4\) 还是 branch/jump target？

ISA 设计原则#

Hennessy 和 Patterson 总结的原则：

1. Simplicity favors regularity。
2. Make the common case fast。
3. Smaller is faster。
4. Good design demands good compromises。

ISA 设计要考虑：

• 支持哪些数据类型。
• 提供多少操作。
• 每条指令几个 operand。
• operand 放在寄存器还是内存。
• 地址模式如何设计。
• 指令长度固定、可变还是混合。

操作数数量#

以：

Y = (A - B) / (C + (D * E))

为例，2-address instruction 可能写成：

MOV R1, A
MOV R2, D
SUB R1, B
MUL R2, E
ADD R2, C
DIV R1, R2

1-address accumulator instruction 把一个操作数隐含在 accumulator 中：

LDA D
MUL E
ADD C
STO R1
LDA A
SUB B
DIV R1

0-address stack instruction 把操作数隐含在栈顶：

PUSH B
PUSH A
SUB
PUSH E
PUSH D
MUL
PUSH C
ADD
DIV

区别抓手：

• 3-address：表达自然，但 instruction 需要更多字段。
• 2-address：指令较短，但会覆盖一个源操作数，常要先 MOV 保存原值。
• 1-address：CPU 简单，但 accumulator 成为隐含瓶颈。
• 0-address：指令短，表达式求值依赖栈顺序。

典型指令架构风格#

Addressing Modes#

寻址例题可以这样读：

考试时先问“instruction 字段给的是值，还是地址，还是装着地址的地方”。这能快速区分 immediate、direct、indirect。

CISC 与 RISC#

CISC：

• variable length instructions。
• 指令和寻址模式丰富。
• 解码复杂。
• 可能包含 memory-to-memory 操作。
• 常使用 microcode。

RISC：

• fixed length instructions。
• load-store architecture。
• 较少寻址模式。
• 硬连线控制。
• 寄存器数量较多。
• 更容易 pipeline。

现代 x86 常见现象：

• 外部 ISA 是 CISC。
• 内部微架构会把复杂 x86 指令翻译成更类似 RISC 的 micro-ops。

基本特点#

RISC-V 是开放的 RISC ISA 标准。

命名方式：

RV + word width + extensions

例子：

• RV32I：32-bit base integer ISA。
• RV32IM：RV32I 加整数乘除扩展 M。
• RV32G：通常表示 IMAFD。

标准扩展：

RISC-V 处理器状态#

包括：

• PC
• 32 个整数寄存器 \(x_{0}-x_{31}\)
• \(x_{0}\) 恒为 0
• \(x_{1}\) 常作为 return address
• 32 个浮点寄存器 \(f_{0}-f_{31}\)
• floating-point status register

指令格式#

RISC-V base instruction 通常是 32-bit，低两位为 11。

核心格式：

重要规则：

• register fields 的位置固定，便于硬件解码。
• immediate 的 sign bit 总在 instruction bit 31。
• branch/jump offset 按 2-byte 粒度组织，以兼容 compressed instructions。

RISC-V 指令格式字段细节#

R-type：

funct7 | rs2 | rs1 | funct3 | rd | opcode

典型：

add rd, rs1, rs2
sub rd, rs1, rs2

I-type：

imm[11:0] | rs1 | funct3 | rd | opcode

典型：

addi rd, rs1, imm
lw   rd, imm(rs1)
jalr rd, imm(rs1)

S-type：

imm[11:5] | rs2 | rs1 | funct3 | imm[4:0] | opcode

典型：

sw rs2, imm(rs1)

B-type：

imm[12,10:5] | rs2 | rs1 | funct3 | imm[4:1,11] | opcode

典型：

beq rs1, rs2, label

U-type：

imm[31:12] | rd | opcode

典型：

lui   rd, imm20
auipc rd, imm20

J-type：

imm[20,10:1,11,19:12] | rd | opcode

典型：

jal rd, label

设计上看起来 immediate 被“拆散”了，但好处是：

• rd, rs1, rs2 位置尽量固定。
• sign bit 固定在 bit 31。
• 硬件解码和符号扩展更规整。

常见指令类别#

R-type：

• ADD, SUB
• SLT, SLTU
• SLL, SRL, SRA

I-type：

• ADDI
• SLTI, SLTIU
• ANDI, ORI, XORI
• SLLI, SRLI, SRAI
• load instructions

U-type：

• LUI
• AUIPC

Control transfer：

• JAL
• JALR
• conditional branches

Calling Convention#

函数调用阶段：

1. 把参数放到 callee 可访问的位置。
2. 用 jal 跳转到函数。
3. callee 分配局部资源，必要时保存寄存器。
4. 执行函数体。
5. 把返回值放到 caller 可访问的位置，恢复寄存器，释放栈帧。
6. 用 ret 返回。

概念：

RISC-V 函数调用小例子#

C 代码：

int add2(int a, int b) {
    return a + b;
}

RISC-V 中常见约定：

a0 = 第 1 个参数 / 返回值
a1 = 第 2 个参数
ra = return address
sp = stack pointer

可能的汇编：

add2:
    add a0, a0, a1
    ret

如果函数内部还要调用别的函数，就必须保护 ra，因为新的 jal 会覆盖它：

foo:
    addi sp, sp, -16
    sw   ra, 12(sp)

    jal  bar

    lw   ra, 12(sp)
    addi sp, sp, 16
    ret

理解 prologue / epilogue：

• prologue：进入函数时开栈帧、保存该保存的寄存器。
• epilogue：返回前恢复寄存器、释放栈帧。

本章英文术语#

8. 中央处理器#

CPU 概述#

CPU 基本功能：

• 取指令。
• 译码。
• 取操作数。
• 执行运算或访存。
• 写回结果。
• 处理中断和异常。

CPU 基本组成：

单周期 CPU#

单周期 CPU 中，每条指令在一个时钟周期内完成。设计步骤：

1. 分析每条指令的功能。
2. 确定需要哪些部件。
3. 建立数据通路。
4. 增加多路选择器以复用通路。
5. 设计控制器产生控制信号。
6. 根据最长指令路径确定时钟周期。

常见控制信号：

多周期 CPU 和控制器#

多周期 CPU 把一条指令拆成多个阶段执行，每个阶段完成一部分操作。优点是：

• 同一硬件可在不同周期复用。
• 时钟周期可按较短阶段设置。
• 控制器可用有限状态机描述。

控制器设计方式：

流水线 CPU#

典型五级流水：

流水线冒险：

流水线提高吞吐率，但不一定降低单条指令延迟。

和前面章节的关系#

CPU 设计把前面几章的部件放到同一个时间结构中：组合逻辑负责“算出下一步”，触发器和寄存器负责“在时钟边沿保存状态”，控制器负责“根据指令产生选择信号”。单周期 CPU 的关键是连出完整数据通路，多周期 CPU 的关键是把每条指令拆成状态序列，流水线 CPU 的关键是把不同指令的不同阶段重叠执行并处理冒险。

做 CPU 数据通路题时，建议按以下顺序判断：

1. 这条指令是否写寄存器。
2. 写哪个寄存器。
3. ALU 第二操作数来自寄存器还是立即数。
4. 立即数需要 sign extension 还是 zero extension。
5. 写回值来自 ALU、内存还是 PC+4。
6. 是否写数据存储器。
7. PC 下一值是顺序地址、branch target 还是 jump target。

本章英文术语#

9. 存储器层次结构#

存储器概述#

存储器层次结构按速度、容量、成本组织：

寄存器
-> cache
-> 主存 DRAM
-> 外存 SSD/HDD

越靠近 CPU：

• 速度越快。
• 容量越小。
• 单位成本越高。

局部性原理：

主存储器#

SRAM：

• 速度快。
• 成本高。
• 常用于 cache。

DRAM：

• 密度高。
• 成本低。
• 需要刷新。
• 常用于主存。

存储器扩展：

• 位扩展：增加数据宽度。
• 字扩展：增加地址空间容量。
• 字位同时扩展：同时增加宽度和容量。

Cache#

cache 是主存的高速缓存。基本工作方式：

1. CPU 发出地址。
2. cache 判断是否命中。
3. 命中则直接返回数据。
4. 缺失则从主存取块并填入 cache。

映射方式：

替换算法：

• 随机替换。
• FIFO。
• LRU 或近似 LRU。

写策略：

虚拟存储器#

虚拟存储器把主存看作外存的缓存，为每个进程提供独立虚拟地址空间。

分页式虚拟存储：

• 虚拟地址空间划分为虚拟页。
• 物理内存划分为页框。
• 页表记录虚拟页到物理页框的映射。
• 访问未在主存中的页会发生缺页异常。

虚拟存储器的作用：

• 扩大程序可用地址空间。
• 实现进程隔离。
• 支持按需调页。
• 提供存储保护。

和 CPU 执行的关系#

存储层次结构的目标是在“容量、速度、成本”之间折中。寄存器和 cache 让 CPU 尽量少等主存，虚拟存储器让每个进程看到独立的地址空间。理解存储器时要抓住两个缓存关系：cache 是主存的缓存，主存又可以看作外存的缓存。

本章英文术语#

10. 系统互连与输入/输出#

外设与系统总线#

外设分为：

总线是部件之间传递信息的公共路径。系统总线通常包括：

• 地址线。
• 数据线。
• 控制线。

总线性能指标：

带宽常用估算：

其中 $W$ 为一次传输数据量，$F$ 为时钟频率，$N$ 为一次传输所需周期数。

I/O 接口和端口#

I/O 接口也称设备控制器，位于外设和总线之间。功能包括：

• 数据缓冲。
• 状态检测。
• 控制和定时。
• 数据格式转换。

I/O 端口是 I/O 接口中 CPU 可访问的寄存器：

端口编址方式：

输入/输出控制方式#

程序直接控制：

• CPU 主动查询设备状态。
• 简单，但 CPU 可能长时间等待。

中断控制 I/O：

• 设备完成或就绪后向 CPU 发中断。
• CPU 可在等待期间执行其他程序。
• 需要中断响应和中断服务程序。

DMA：

• Direct Memory Access。
• 外设和主存之间由 DMA 控制器直接传输数据。
• CPU 只负责初始化和收尾。
• 适合磁盘等高速块设备。

三种方式对比：

I/O 软件层次#

一次 I/O 请求通常经过多个软件层次：

用户程序 / C 库函数
-> 系统调用
-> 与设备无关的 I/O 软件
-> 设备驱动程序
-> 中断服务程序
-> I/O 控制器和外设

与设备无关软件负责：

• 统一设备驱动接口。
• 缓冲区管理。
• 错误报告。
• 文件打开关闭等通用操作。
• 逻辑块大小处理。

设备驱动程序负责：

• 操作具体设备控制器。
• 读写控制/状态/数据端口。
• 启动设备。
• 处理中断或 DMA 完成事件。

中断服务程序包含：

1. 准备阶段：保存断点和现场，设置屏蔽字。
2. 处理阶段：执行具体中断服务。
3. 恢复阶段：恢复现场并返回。

三种 I/O 方式的直觉#

中断请求的是 CPU 时间，DMA 请求的是总线控制权。这个区别很重要。

本章英文术语#

11. 程序从源代码到运行#

这一部分把“程序如何落到机器上运行”接到前面的 ISA、存储器和操作系统接口上，重点看编译、汇编、链接、加载之间的分工。

编译链路#

C 程序到运行的逻辑步骤：

.c -> .i -> .s -> .o -> executable -> running process

ELF#

ELF 是 Unix-like 系统常见目标文件格式。

三类 object file：

常见 section：

ELF 中符号放在哪里#

看 C 代码：

#define ITEM_NUM 16
static int item_size = 4;
int global_count;

int add(int x, int y) {
    return x + y;
}

int main() {
    char *p = malloc(64);
    return add(item_size, ITEM_NUM);
}

分类：

这类题要分清：

• 宏不是运行时对象。
• initialized data 和 uninitialized data 放不同 section。
• static 限制链接可见性，不代表一定在栈上。
• 外部库函数在当前 .o 里通常是 unresolved external reference。

Assembler 与 Linker#

assembler 要处理：

• pseudo-instructions。
• local labels。
• forward references。
• 生成 object file。

linker 主要做：

1. 合并各 object 的 text/data 等 segment。
2. 符号解析：找到 undefined external symbol 的定义。
3. 重定位：修正地址。
4. 记录 entry point。

注意：C/C++ 程序真正入口通常不是 main，而是 _start 或 crt0 相关启动代码。启动代码初始化运行时环境后再调用 main。

Static Linking 与 Dynamic Linking#

Static linking：

• 链接时把需要的库代码合入 executable。
• 启动时简单。
• 可执行文件可能更大。
• 库更新后程序不自动使用新版库。

Dynamic linking：

• 运行时加载并解析共享库。
• 多个程序可共享同一份库代码。
• 使用 GOT 和 PLT 支持延迟绑定。

PIC：

• position-independent code。
• 代码不依赖固定加载地址。
• 常用于 shared libraries。

链接和加载的直观区别#

链接 linker 解决的是“文件之间怎么拼起来”：

• 多个 .o 合并。
• 找到函数和全局变量的定义。
• 修补地址。
• 生成 executable。

加载 loader 解决的是“executable 怎么变成进程”：

• 创建地址空间。
• 把 text/data 映射进内存。
• 建 stack / heap 初始布局。
• 设置参数、环境变量。
• 跳到 entry point。

一句话：

linking makes a complete program file.
loading makes a running process.

Loader 与进程内存布局#

loader 的工作：

1. 读取 executable header。
2. 分配地址空间。
3. 把 text/data segment 放入内存。
4. 清零 .bss。
5. 建立 stack。
6. 设置参数和环境变量。
7. 跳转到 entry point。

典型内存布局：

high address
stack      grows downward
...
heap       grows upward
static data
text
low address

本章英文术语#

12. 统一复习表#

各章重点#

必须能解释#

• 为什么 signed 和 unsigned 转换时 bit pattern 不变但值会变。
• 为什么补码可以用同一个加法器实现加减法。
• 为什么 signed overflow 不能只看 carry out。
• IEEE 754 中 normalized、denormalized、infinity、NaN 的判定。
• C 的 &/\(|\)/~/\(^\) 与 &&/\(||\)/! 为什么不是一类运算。
• noise margin、propagation delay、transition time、fan-in/fan-out、static/dynamic power 分别看什么。
• canonical SOP/POS 与 standard SOP/POS 的区别。
• prime implicant 和 essential prime implicant 为什么影响 K-map 选圈。
• Verilog 中 wire 和 reg 的使用语境。
• 组合逻辑和时序逻辑的根本区别。
• latch、pulse-triggered flip-flop、edge-triggered flip-flop 的触发差异。
• characteristic table 和 excitation table 分别回答什么问题。
• Mealy 和 Moore FSM 的输出区别。
• setup/hold 约束的意义。
• multiplexer bus 和 three-state bus 的核心差别。
• RCA、CLA、prefix adder 的速度和硬件代价差异。
• barrel shifter 为什么是组合逻辑，而 shift register 是时序逻辑。
• Booth algorithm 为什么能减少部分积。
• ISA 和 microarchitecture 的区别。
• 0/1/2/3-address instruction 对硬件和程序长度的影响。
• stack、accumulator、memory-memory、register-memory、load-store 架构的区别。
• RISC-V R/I/S/B/U/J 格式分别服务什么指令。
• .c 到进程运行的每个阶段在解决什么问题。

易错点清单#

• 位运算的返回值是 bit pattern；逻辑运算返回 0 或 1，且可能短路。
• unsigned 循环变量做 \(i \ge 0\) 这种条件时可能永远为真。
• signed 和 unsigned 混合比较时，signed 会被转换成 unsigned。
• signed 右移负数通常是算术右移，不等价于 C 除法的向 0 截断。
• 浮点数不满足普通实数的结合律。
• K-map 中 don't care 是可选工具，不是必须全部当作 1。
• \(always @(*)\) 中组合逻辑分支不完整会推导出 latch。
• SR latch / SR flip-flop 有非法输入组合，D latch 用一个数据输入规避它。
• 3-state bus 同时使能多个 driver 会造成 bus contention。
• Moore FSM 通常比 Mealy FSM 多状态。
• ripple counter 不是严格同步电路。
• signed SLT 不能只看减法结果符号位，要考虑 overflow。
• load-store ISA 中，算术指令通常不直接访问内存。
• RISC-V 的 \(x_{0}\) 不能被改写。
• object file 不是 executable，必须链接后才可直接运行。

易混概念#

常用公式#

无符号范围：

补码范围：

补码取负：

无符号加法：

无符号乘法：

CLA：

Full adder：

Noise margin：

浮点数：

时钟周期：

Hold 约束：

简化 MIPS branch target：

RISC-V branch target：

其中 B-type immediate 编码已经隐含最低位 0，因此目标地址按 2-byte 粒度对齐。

总线带宽估算：