4. 运算部件与 ALU

章节导引

本页从《计算机系统基础讲义》拆分而来，保留原章节锚点，方便从旧总览页和旧链接跳转。

学习目标

理解算术运算如何由组合逻辑构成，并能解释 ALU 中常见操作和溢出判断。

前置知识

第 1 章整数/浮点表示，第 2–3 章逻辑函数与组合模块。

建议用时

建议 6–8 小时：加减法 2 小时，乘除/Booth 2–3 小时，浮点与 ALU 2–3 小时。

练习建议

画 1 位全加器真值表；解释有符号溢出；手算一个 Booth 编码示例。

参考资料与引用边界

• 整理者：Lumner。
• 课程来源：根据 SYS/ 目录下的课件整理；本章对应课件：SYS/Lec04_Arithmetic Unit.pptx。
• 原始讲义文件：note/SYS_计算机系统基础讲义.md。
• 引用边界：这是公开学习笔记，不替代课程正式教材、教师课件或考试要求；外部引用时请注明来自本网站整理版。

4.1 迭代组合电路

很多算术运算作用于二进制向量，并在每一位重复类似结构。例如加法器、乘法器、除法器都可以看成由多个 cell 组成的迭代阵列。

概念	含义
Cell	单个位或局部子功能模块
Iterative array	多个 cell 按位连接形成整体功能
1D array	如串行进位加法器
2D array	如阵列乘法器

4.2 半加器与全加器

半加器输入 A, B，输出和位 S 与进位 Cout：

S = A ⊕ B
Cout = A B

全加器输入 A, B, Cin，输出：

S = A ⊕ B ⊕ Cin
Cout = AB + ACin + BCin

也可用 generate/propagate 表示：

Gi = Ai Bi
Pi = Ai ⊕ Bi
Ci+1 = Gi + Pi Ci
Si = Pi ⊕ Ci

4.3 多位加法器

常见 CPA（carry propagate adder）：

类型	思想	优点	缺点
RCA	进位逐位传播	硬件简单	慢，延迟随位数线性增长
Carry Skip	某些块整体传播时跳过	比 RCA 快	控制和分块复杂
Carry Select	同时计算 Cin=0/1，最后选择	快	硬件重复
CLA	直接推导多位进位	快	扇入和布线复杂
Prefix Adder	用前缀树计算进位	log N 级	面积和布线开销较大

Ripple-carry adder 延迟近似：

t_RCA = N × t_FA

Carry lookahead 展开：

C1 = G0 + P0 C0
C2 = G1 + P1 G0 + P1 P0 C0
C3 = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0
C4 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 C0

当位数很大时，直接展开会导致门扇入过大，因此使用分组 generate/propagate 或 prefix tree。

Prefix adder 的核心递推：

G_{i:j} = G_{i:k} + P_{i:k} G_{k-1:j}
P_{i:j} = P_{i:k} P_{k-1:j}

延迟近似：

t_PA = t_pg + log2(N) × t_prefix + t_XOR

4.4 减法与溢出

无符号减法可通过补码加法实现：

M - N = M + (2^n - N)

硬件上：

A - B = A + (~B) + 1

4 位加减器可用控制信号 S：

• S=0：执行 A + B。
• S=1：执行 A + ~B + 1。

Carry 和 overflow 区别：

标志	用于	含义
Carry / Borrow	无符号运算	结果超出无符号范围
Overflow	有符号补码运算	结果超出补码范围

有符号溢出发生于：

• 两个正数相加得到负数。
• 两个负数相加得到正数。

检测方式：

OF = Cn ⊕ Cn-1

其中 Cn 是最高位的进位输出，Cn-1 是进入符号位的进位。

常见标志：

标志	含义
ZF	结果为 0
SF / NF	结果符号位
CF	无符号进位或借位
OF	有符号溢出

4.5 ALU

ALU 是处理器数据通路的核心，执行算术和逻辑操作。

图像说明：ALU 符号

原课件包含 ./sys_notes_assets/alu_symbol.png。公开仓库当前不附带这张图片；本节保留文字化说明，阅读时可把它理解为“ALU 符号”的结构示意。

典型 ALU 操作：

控制	功能
AND	按位与
OR	按位或
ADD	加法
SUB	减法
SLT	set less than
NOT	取反
SRL/SRA/SLL	移位
XOR	按位异或

SLT 的基本思路：

if rs < rt then rd = 1 else rd = 0

硬件常通过计算 rs - rt，再根据符号与溢出判断大小。对于有符号比较，不能只看减法结果符号位，还要结合 overflow。

4.6 移位器

移位类型：

类型	右移填充	用途
逻辑左移/右移	0	无符号位操作
算术右移	原符号位	有符号除以 2 的幂
循环移位	移出的位绕回	加密、校验、位操作

关系：

A << N  = A × 2^N
A >>> N ≈ A / 2^N   // 算术右移，适用于补码有符号数的某些场景

Barrel shifter 可以在组合逻辑中一次完成多位移位，避免多周期逐位移动。

图像说明：4 位 barrel shifter 功能表

原课件包含 ./sys_notes_assets/barrel_shifter_table.png。公开仓库当前不附带这张图片；本节保留文字化说明，阅读时可把它理解为“4 位 barrel shifter 功能表”的结构示意。

4.7 乘法

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

1. 根据乘数每一位生成部分积。
2. 部分积按位移位。
3. 将部分积相加。

最直接的 shift-add 算法：

product = 0
for each bit i of multiplier:
    if multiplier[i] == 1:
        product += multiplicand << i

硬件实现可以逐步优化：

实现	特点
实现 1	ALU 和寄存器较宽，直接但浪费
实现 2	被乘数固定，乘数右移，部分积右移
实现 3	乘数放在部分积寄存器右半部，减少寄存器
阵列乘法器	并行加部分积，速度快但面积大

有符号乘法的简单方法：

1. 记录两个操作数符号。
2. 转成非负数做无符号乘法。
3. 根据符号决定结果正负。

更高效方法：Booth 算法。

4.8 Booth 算法

Booth 算法利用乘数中连续的 1：

01111000 = 10000000 - 00001000

一长串连续 1 可以用一次加和一次减代替多次加。

规则可用当前位和右侧前一位判断：

当前位	右侧位	含义	操作
0	0	0 串中间	无操作
0	1	1 串结束	加
1	0	1 串开始	减
1	1	1 串中间	无操作

Booth 编码也可扩展到每周期处理 2 位：

编码效果	操作
-2	左移被乘数 1 位后减
-1	减
0	无操作
+1	加
+2	左移被乘数 1 位后加

优点是减少部分积数量，缺点是控制逻辑更复杂。

4.9 除法

无符号除法的硬件思想来自长除法：

1. 比较当前余数与除数。
2. 若余数大于等于除数，则减去除数，商位为 1。
3. 否则商位为 0，并恢复余数。

Restoring division：

R = R - D
if R < 0:
    R = R + D
    Q_i = 0
else:
    Q_i = 1

Non-restoring division 避免失败后立即恢复：

• 如果上一步余数为负，下一步用加除数代替减除数。
• 可以达到每位约 1 个周期的吞吐。

有符号除法：

• 商的符号由被除数和除数符号是否相同决定。
• 非零余数的符号应与被除数一致。

4.10 浮点加法与乘法

浮点加法步骤：

1. 对阶：把较小指数的尾数右移，使指数相同。
2. 尾数相加或相减。
3. 规格化结果。
4. 检查溢出或下溢。
5. 舍入。

例：

0.5 + (-0.4375)
0.5     =  1.000_2 × 2^-1
-0.4375 = -1.110_2 × 2^-2
对阶: -1.110_2 × 2^-2 = -0.111_2 × 2^-1
相加: 1.000_2 - 0.111_2 = 0.001_2
规格化: 0.001_2 × 2^-1 = 1.000_2 × 2^-4
结果: 0.0625

浮点乘法步骤：

1. 符号位异或。
2. 指数相加，若使用偏置指数则要减去 bias。
3. 尾数相乘。
4. 规格化。
5. 检查溢出/下溢。
6. 舍入。

浮点硬件通常比整数加法器复杂得多，常采用多周期或流水线实现。

4.11 数据通路中的 ALU

数据通路由寄存器、ALU、移位器、总线/多路选择器组成。控制器产生选择信号和写使能，决定：

• 哪些寄存器作为源操作数。
• ALU 执行哪种操作。
• 结果写回哪个目的寄存器。

寄存器传输级描述常写成：

R3 <- R1 + R2

如果有控制条件：

K1: R1 <- R1 + R2
K2: R1 <- R1 - R2

---