功能单元：整数运算

硬件描述 1 — 从串行进位到并行前缀——半世纪的加法器革命

1956年，Ladner和Fischer提出了并行前缀计算（Parallel Prefix Computation）的理论框架。这个优美的数学结构表明：任何满足结合律的二元运算，都可以从$O(N)$的串行链压缩到$O(\log N)$的并行树。半个世纪后，这一框架成为每颗现代处理器加法器的核心。Kogge-Stone、Brent-Kung、Han-Carlson——这些在教科书中反复出现的名字——本质上都是并行前缀在不同面积-延迟权衡点上的实例化。理解并行前缀，就理解了加法器设计空间的全貌。

设计提示

统一视角。处理器设计的本质是在有限的晶体管预算和功耗约束下，通过投机和并行的层层叠加来逼近指令吞吐率的理论上限。并行前缀加法器正是"并行"在算术运算中最纯粹的体现——它将$O(N)$的串行进位传播转化为$O(\log N)$的并行前缀树。加法器的延迟直接决定了ALU的单周期时间预算，进而决定整个执行流水线的深度（回顾第 3.0 章中FO4门延迟与关键路径的讨论）。在第 28.0 章中我们看到，加法器延迟影响了唤醒-选择循环的时序约束——单周期ALU操作要求加法器在半个时钟周期内完成，这在5 GHz处理器中意味着100 ps的绝对预算。

在超标量处理器的乱序执行引擎中，功能单元（Functional Unit, FU）是指令实际执行计算的地方。前面各章讨论的寄存器重命名、发射队列、唤醒与仲裁逻辑所做的全部工作，最终都是为了将指令高效地送入功能单元执行。功能单元的延迟和吞吐量直接决定了处理器执行阶段的性能上限——加法器慢了一个门延迟，流水线频率就可能下降5%$\sim$10%；乘法器多占了一级流水线，所有乘法相关的依赖链延迟都增加一个周期。

本章聚焦于整数功能单元的电路设计。我们将从最基本的加法器出发，追问一个核心问题：如何在一个时钟周期（约200 ps）内完成64位加法？这个问题的答案将引导我们走过行波进位加法器、超前进位加法器，最终到达并行前缀加法器的优美数学结构。接下来我们讨论移位器的巧妙分解策略，然后深入乘法器设计——从Booth编码为何能将部分积减半的数学推导，到Wallace树如何用$O(\log n)$级压缩取代$O(n)$级累加。除法器部分将详细推导SRT除法的商选择表构造，并讲述Intel Pentium FDIV Bug这一处理器历史上最昂贵的硬件缺陷。最后，我们讨论地址生成单元（AGU）的设计取舍。

ALU概述

ALU（Arithmetic Logic Unit，算术逻辑单元）是处理器中最基本的功能单元，负责执行加法、减法、逻辑运算（AND、OR、XOR）、移位和比较等操作。在RISC-V处理器中，ALU需要处理的指令包括：

• 算术指令：ADD、SUB、ADDI、ADDW等。

• 逻辑指令：AND、OR、XOR、ANDI、ORI、XORI等。

• 比较指令：SLT、SLTU、SLTI、SLTIU。

• 移位指令：SLL、SRL、SRA及其立即数版本。

其中，逻辑运算是按位操作，延迟仅为一个门级，设计上没有挑战。ALU设计的核心难题在于加法器——因为加法存在进位传播问题，而加法器的速度直接决定了ALU的关键路径延迟。本节先给出问题的背景和工程约束，后续各节将逐步推导出高性能加法器的设计方案。

从行波进位加法器出发：进位传播的困境

要设计一个64位加法器，最自然的起点是模仿我们手算加法的方式：从最低位开始逐位相加，每一位产生的进位传递给下一位。这就是行波进位加法器（Ripple-Carry Adder, RCA）。

全加器：加法的基本单元

一个1位全加器（Full Adder, FA）接收三个输入——两个操作数位$A_i$、$B_i$和来自低一位的进位$C_i$——产生两个输出：本位和$S_i$和向高位的进位$C_{i+1}$：

$$\begin{aligned} S_i &= A_i \oplus B_i \oplus C_i \\ C_{i+1} &= A_i \cdot B_i + C_i \cdot (A_i \oplus B_i) \end{aligned}$$

式 (30.2)的含义很直观：高一位会收到进位，要么因为$A_i$和$B_i$都为1（不论$C_i$是什么，都必然产生进位），要么因为$A_i$和$B_i$中恰好有一个为1（此时本位的"半加和"为1，如果低位传入了进位$C_i=1$，它就会被"传播"到高位）。这两种情形——"生成"和"传播"——将在后面的推导中扮演核心角色。

全加器的CMOS实现

在CMOS工艺中，全加器的实现有多种方案，不同方案在延迟、面积和功耗之间有着不同的权衡。

最直接的方案是标准逻辑门实现：用两个XOR门计算和$S = A \oplus B \oplus C$，用两个AND门和一个OR门计算进位$C_\mathrm{out} = AB + BC + AC$（注意这里$AC$等价于$C \cdot (A \oplus B)$因为当$A = B = 1$时$AB = 1$已经覆盖了$AC$和$BC$的情况）。这种实现需要约28个晶体管，进位路径延迟约2级（一级AND，一级OR）。

在高性能处理器中，更常用的是传输门（Transmission Gate）全加器或镜像全加器（Mirror Adder）。镜像全加器利用CMOS互补结构的对称性，用更少的晶体管（约24个）实现全加器，且进位路径的延迟可以优化到约1.5级等效门延迟。其关键是将进位方程改写为：

$$C_\mathrm{out} = \overline{\overline{AB} \cdot \overline{(A+B) \cdot C}}$$

这个双重否定形式可以直接映射为一个CMOS互补结构：PMOS网络和NMOS网络各约6个晶体管，形成一个紧凑的"镜像"拓扑。

还有一种更为激进的方案是多路选择器实现：将进位方程写成$C_\mathrm{out} = (A \oplus B) \mathrel{?} C : A$（即如果$A \neq B$则传播进位$C$，否则进位等于$A$）。这可以用一个2:1传输门MUX在仅2个传输门的延迟内完成——但需要$A \oplus B$信号先就绪。这种实现的总延迟可以低至1级门延迟（从$C$到$C_\mathrm{out}$），是行波进位链的首选方案。

对于加法器的关键路径——进位链——来说，$C_\mathrm{in}$到$C_\mathrm{out}$的延迟是最重要的指标。通过使用传输门MUX实现进位传播，这个延迟可以降到约一个传输门延迟（约0.5$\sim$1级等效门延迟），但代价是$S$的计算需要等到$C_\mathrm{in}$和$A \oplus B$都就绪后才能完成（$S = (A \oplus B) \oplus C_\mathrm{in}$）。在RCA中，$S$不在关键路径上（因为它不传播给后续位），所以这个代价是可以接受的。

行波进位加法器的结构与延迟

$n$位行波进位加法器由$n$个全加器串联而成，每一位的进位输出直接连接到下一位的进位输入。

8位行波进位加法器：进位从LSB到MSB逐位传播

图图 30.1展示了一个8位RCA的结构。红色箭头标出的进位链是整个加法器的关键路径：进位信号从最低位（LSB）出发，经过每个全加器产生一级延迟，逐位向最高位（MSB）传播。对于$n$位加法器，进位必须通过$n$个全加器才能到达最高位，因此总延迟为：

$$T_\mathrm{RCA} = n \times t_\mathrm{FA}$$

其中$t_\mathrm{FA}$是单个全加器的进位传播延迟（从$C_i$到$C_{i+1}$的延迟），在典型的CMOS工艺中约为2个门延迟。

为什么行波进位不够快

让我们用具体数字来感受这个延迟有多大。在7 nm工艺中，一个反相器（最简单的逻辑门）的传播延迟约为12$\sim$15 ps。一个全加器的进位传播延迟$t_\mathrm{FA}$大约等于2个门延迟，即30 ps左右。那么一个64位RCA的延迟为：

$$T_\mathrm{RCA} = 64 \times 30\,\text{ps} = 1920\,\text{ps} \approx 1.9\,\text{ns}$$

而一个5 GHz处理器的时钟周期仅为200 ps。即使我们把整个时钟周期都分配给加法器（实际上加法器通常只占执行阶段时间预算的50%$\sim$60%，因为还需要时间来读操作数、选择结果和写回），RCA也需要近10个时钟周期才能完成一次加法。考虑到加法是处理器中使用频率最高的操作（加法和减法占全部整数指令的30%$\sim$40%），10个周期的延迟是完全不可接受的。

性能分析 1 — 行波进位加法器的延迟分析

考虑一个64位RCA，假设每个全加器的进位传播延迟$t_\mathrm{FA} = 2$个门延迟，每个门延迟在7 nm工艺下约为15 ps。则：

$$T_\mathrm{RCA} = 64 \times 2 \times 15\,\text{ps} = 1920\,\text{ps} \approx 1.9\,\text{ns}$$

5 GHz处理器的时钟周期为200 ps。在实际设计中，加法器的延迟预算约为100$\sim$120 ps（时钟周期的一半），即仅能容纳约7$\sim$8级门延迟。而RCA需要128级门延迟——超出预算约16倍。

问题很清楚了：行波进位加法器之所以慢，是因为进位必须从最低位一路"爬"到最高位，如同多米诺骨牌一样逐级传播。如果我们能找到一种方法并行地计算所有位的进位，而不是等待低位的进位逐级到来，就能打破这个瓶颈。

不过，RCA也并非一无是处。它结构简单、面积最小、功耗最低，在以下场景中仍有应用价值：

• 低功耗设计中位宽较小的加法器（如4$\sim$8位的地址偏移计算）。

• 作为更复杂加法器内部的基本构建模块（例如在超前进位加法器中，每个4位组内部使用RCA）。

• 功能验证和教学。

超前进位加法器：预测进位

超前进位加法器（Carry-Lookahead Adder, CLA）是解决行波进位瓶颈的第一步。它的核心思想来自一个简单的观察：虽然进位需要逐位传播，但每一位是否产生进位、是否传播进位，实际上只取决于该位的两个输入$A_i$和$B_i$——这些信息在加法开始之前就已经完全确定了。

生成和传播信号的推导

让我们仔细审视全加器的进位方程式 (30.2)：

$$C_{i+1} = A_i \cdot B_i + C_i \cdot (A_i \oplus B_i)$$

这个方程告诉我们：第$i$位产生进位输出$C_{i+1}=1$的条件恰好有两种情形：

1. $A_i \cdot B_i = 1$：第$i$位的两个输入都为1，无论低位是否传来进位（$C_i$是0还是1），本位都会产生进位。我们称这种情况为第$i$位生成（Generate）了进位。

2. $A_i \oplus B_i = 1$且$C_i = 1$：第$i$位的两个输入中恰好有一个为1，本位"半加和"为1。如果此时低位还传来了进位$C_i=1$，那么本位的三个输入之和为$1+1=2_{(10)}$，产生进位。我们称这种情况为第$i$位传播（Propagate）了低位的进位。

据此，定义两个关键信号：

$$\begin{aligned} G_i &= A_i \cdot B_i \quad \text{（生成信号）} \\ P_i &= A_i \oplus B_i \quad \text{（传播信号）} \end{aligned}$$

$G_i$和$P_i$有非常清晰的物理含义：$G_i=1$表示第$i$位自身就能产生进位，无需外部进位；$P_i=1$表示第$i$位是"透明"的，如果有进位从低位传入，它会原样传递到高位。利用这两个信号，进位方程可以简洁地写成：

$$C_{i+1} = G_i + P_i \cdot C_i$$

这就是CLA的基础方程。注意$G_i$和$P_i$只依赖于输入$A_i$和$B_i$，可以在第一级逻辑中并行计算所有位的$G$和$P$——这只需要一个AND门和一个XOR门的延迟。

进位的直接计算

有了式 (30.6)，让我们尝试递归展开进位表达式，看看能否消除对低位进位的逐级依赖：

$$\begin{aligned} C_1 &= G_0 + P_0 \cdot C_0 \\ C_2 &= G_1 + P_1 \cdot C_1 = G_1 + P_1 \cdot G_0 + P_1 \cdot P_0 \cdot C_0 \\ C_3 &= G_2 + P_2 \cdot C_2 = G_2 + P_2 \cdot G_1 + P_2 \cdot P_1 \cdot G_0 + P_2 \cdot P_1 \cdot P_0 \cdot C_0 \\ C_4 &= G_3 + P_3 \cdot G_2 + P_3 \cdot P_2 \cdot G_1 + P_3 \cdot P_2 \cdot P_1 \cdot G_0 \\ &\quad + P_3 \cdot P_2 \cdot P_1 \cdot P_0 \cdot C_0 \end{aligned}$$

关键观察：这些表达式中只出现了$G_i$、$P_i$和初始进位$C_0$，完全消除了对中间进位$C_1$、$C_2$、$C_3$的依赖。换言之，如果我们有足够的硬件来同时计算这些与-或表达式，就可以一步到位地得出所有进位——不需要等待任何低位进位的传播。

CLA的硬件实现

4位超前进位加法器的结构

图图 30.2展示了4位CLA的结构。整个加法过程分为三步：(1) 并行计算所有位的$G_i$和$P_i$（1级门延迟）；(2) CLA逻辑使用式 (30.7)$\sim$式 (30.10)同时算出$C_1$到$C_4$（2级门延迟，一级AND一级OR）；(3) 并行计算所有位的和$S_i = P_i \oplus C_i$（1级XOR门延迟）。总共只需要约4级门延迟——与位宽无关。

让我们用一个例子来验证。计算$A = 0101 + B = 0011 = 0101 + 0011 = 1000$（5 + 3 = 8）。

Step 1：计算$G_i$和$P_i$：

位	3	2	1	0
$A$	0	1	0	1
$B$	0	0	1	1
$G_i$	0	0	0	1
$P_i$	0	1	1	0

位0的$G_0 = 1$（$A_0 = B_0 = 1$，产生进位）。位0的$P_0 = 0$（$A_0 \oplus B_0 = 0$，不传播进位——但这不重要，因为它已经生成了进位）。

Step 2：用CLA方程直接计算所有进位（设$C_0 = 0$）：

$$\begin{aligned} C_1 &= G_0 + P_0 \cdot C_0 = 1 + 0 = 1 \\ C_2 &= G_1 + P_1 \cdot G_0 + P_1 P_0 C_0 = 0 + 1 \cdot 1 + 0 = 1 \\ C_3 &= G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0 = 0 + 0 + 1 \cdot 1 \cdot 1 + 0 = 1 \\ C_4 &= G_3 + P_3 G_2 + \ldots = 0 + 0 + 0 + 0 + 0 = 0 \end{aligned}$$

注意所有4个进位是同时计算出来的——不需要等$C_1$算出后才能算$C_2$。

Step 3：计算和$S_i = P_i \oplus C_i$： $S_0 = 0 \oplus 0 = 0$，$S_1 = 1 \oplus 1 = 0$，$S_2 = 1 \oplus 1 = 0$，$S_3 = 0 \oplus 1 = 1$。 结果为$1000 = 8$。正确！

CLA的扇入问题与分层实现

然而，CLA有一个致命的实际问题。观察式 (30.10)：$C_4$的表达式中最长的一项是$P_3 \cdot P_2 \cdot P_1 \cdot P_0 \cdot C_0$——一个5输入的AND门。如果我们把CLA直接扩展到64位，那么$C_{64}$的表达式将包含一个65输入的AND门。在真实的CMOS电路中，门的扇入（输入数量）不能无限增大：超过4$\sim$5个输入后，晶体管串联的导通电阻急剧增大，信号延迟不是减少而是增加。因此，直接展开的CLA在大位宽下并不实用。

解决方案是分层CLA：将$n$位加法器分成若干个4位组，组内使用4位CLA快速计算进位，组间再用一级CLA计算组间进位。为此，需要定义组生成和组传播信号：

$$\begin{aligned} G^*_{[3:0]} &= G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 \\ P^*_{[3:0]} &= P_3 P_2 P_1 P_0 \end{aligned}$$

$G^*_{[3:0]}$的含义是：这4位作为一个整体来看，是否会"生成"进位（即使没有外部进位传入，组内是否自己产生进位输出）。$P^*_{[3:0]}$的含义是：这4位作为一个整体，是否会"传播"外部进位（即如果有进位从$C_0$传入，它是否能穿过这4位传到$C_4$——只有当所有4位都是传播的，即$P_0=P_1=P_2=P_3=1$时才成立）。

对于两级CLA结构的16位加法器，延迟为：

$$T_\mathrm{CLA} = t_{GP} + \lceil \log_4 n \rceil \times t_\mathrm{CLA} + t_\mathrm{XOR}$$

其中$t_{GP}$是$G/P$信号的生成延迟（1级门延迟），$t_\mathrm{CLA}$是每级CLA逻辑的延迟（约2级门延迟），$t_\mathrm{XOR}$是最后一级异或门的延迟（1级门延迟）。

对于64位CLA：$\lceil \log_4 64 \rceil = 3$级CLA逻辑，总延迟约$1 + 3 \times 2 + 1 = 8$级门延迟。相比64位RCA的128级门延迟，CLA实现了16倍的速度提升。但是，分层CLA在层级之间仍然有逐级等待的串行性，每增加一级CLA都增加2级门延迟。我们能否找到一种更加"彻底并行"的结构？答案是并行前缀加法器。

并行前缀加法器：从数学到电路

并行前缀加法器的核心洞见是：进位计算问题可以被精确地映射为一个前缀计算问题——而前缀计算有着已知的最优并行算法。这个映射的关键是定义一个合适的二元运算符。

前缀运算符的推导

让我们从进位方程出发，寻找并行计算所有进位的数学结构。回顾单位进位方程式 (30.6)：

$$C_{i+1} = G_i + P_i \cdot C_i$$

现在考虑一个连续区间$[j:i]$（从第$i$位到第$j$位，$j > i$）。我们想定义这个区间的"组生成"和"组传播"信号$(G_{[j:i]}, P_{[j:i]})$，使得：

$$C_{j+1} = G_{[j:i]} + P_{[j:i]} \cdot C_i$$

也就是说，$(G_{[j:i]}, P_{[j:i]})$完整地描述了区间$[j:i]$对进位的影响——知道了进入这个区间的进位$C_i$，就可以一步算出离开这个区间的进位$C_{j+1}$。

对于单个位，$(G_{[i:i]}, P_{[i:i]}) = (G_i, P_i)$，这正好满足式 (30.6)。

现在的关键问题是：如果我们知道两个相邻区间$[j:k+1]$和$[k:i]$的组信号，能否合并它们以得到整个区间$[j:i]$的组信号？

设区间$[k:i]$的信号为$(G_L, P_L)$，区间$[j:k+1]$的信号为$(G_H, P_H)$。进位$C_{j+1}$可以按如下方式推导：

$$\begin{aligned} C_{k+1} &= G_L + P_L \cdot C_i \quad \text{（低半区间的进位输出）} \\ C_{j+1} &= G_H + P_H \cdot C_{k+1} \quad \text{（高半区间利用$C_{k+1}$）} \\ &= G_H + P_H \cdot (G_L + P_L \cdot C_i) \\ &= (G_H + P_H \cdot G_L) + (P_H \cdot P_L) \cdot C_i \end{aligned}$$

比较式 (30.13)和式 (30.12)，我们可以读出合并后的组信号：

$$\begin{aligned} G_{[j:i]} &= G_H + P_H \cdot G_L \\ P_{[j:i]} &= P_H \cdot P_L \end{aligned}$$

这就自然地定义了一个二元运算符$\circ$，作用在$(G, P)$对上：

$$(G_H, P_H) \circ (G_L, P_L) = (G_H + P_H \cdot G_L,\ P_H \cdot P_L)$$

运算符$\circ$的直觉含义是：将两个相邻区间的进位行为合并为一个更大区间的进位行为。合并后的生成信号$G_H + P_H \cdot G_L$表示"高半区间自己生成进位，或者高半区间传播了低半区间生成的进位"；合并后的传播信号$P_H \cdot P_L$表示"进位必须同时穿过两个区间才算被传播"。

结合律的证明——并行化的数学基础

为了能用树形结构并行计算前缀，运算符$\circ$必须满足结合律。让我们验证这一点。

设$X = (G_X, P_X)$，$Y = (G_Y, P_Y)$，$Z = (G_Z, P_Z)$。需要证明$(X \circ Y) \circ Z = X \circ (Y \circ Z)$。

先计算左边：

$$\begin{aligned} X \circ Y &= (G_X + P_X G_Y,\ P_X P_Y) \\ (X \circ Y) \circ Z &= \big((G_X + P_X G_Y) + P_X P_Y \cdot G_Z,\ P_X P_Y P_Z\big) \\ &= (G_X + P_X G_Y + P_X P_Y G_Z,\ P_X P_Y P_Z) \end{aligned}$$

再计算右边：

$$\begin{aligned} Y \circ Z &= (G_Y + P_Y G_Z,\ P_Y P_Z) \\ X \circ (Y \circ Z) &= \big(G_X + P_X(G_Y + P_Y G_Z),\ P_X P_Y P_Z\big) \\ &= (G_X + P_X G_Y + P_X P_Y G_Z,\ P_X P_Y P_Z) \end{aligned}$$

两边完全相同，结合律成立。

需要注意的是，$\circ$不满足交换律——$(G_H, P_H) \circ (G_L, P_L) \neq (G_L, P_L) \circ (G_H, P_H)$（一般情况下），因此在构造前缀树时必须保持操作数的顺序（高位在左，低位在右）。

从前缀运算到所有进位

有了运算符$\circ$和它的结合律，现在我们可以将进位计算表述为一个前缀问题。

定义每一位的初始$(G, P)$对为$(G_i, P_i)$，其中$i = 0, 1, \ldots, n-1$。位$i$的前缀结果定义为：

$$(G_{[i:0]}, P_{[i:0]}) = (G_i, P_i) \circ (G_{i-1}, P_{i-1}) \circ \cdots \circ (G_0, P_0)$$

根据式 (30.12)，这个前缀结果直接给出进位：

$$C_{i+1} = G_{[i:0]} + P_{[i:0]} \cdot C_0$$

也就是说，计算所有位的进位等价于计算一个前缀和。而前缀和有一个著名的性质：对于$n$个元素、满足结合律的二元运算，可以用树形结构在$O(\log_2 n)$级并行计算中完成所有前缀。这就是并行前缀加法器能达到$O(\log n)$延迟的根本原因。

设计提示

前缀运算符$\circ$的推导是理解所有并行前缀加法器的关键。它并非凭空发明，而是从进位方程的递推展开中自然浮现的——我们只是把"将两个相邻区间的进位行为合并"这一操作形式化了。一旦理解了这个运算符，Kogge-Stone、Brent-Kung、Han-Carlson等不同加法器的区别就只是前缀树的拓扑结构不同——它们都在计算同一个前缀问题，只是在延迟、面积和布线之间做了不同的取舍。

Kogge-Stone加法器：最快的并行前缀树

Kogge-Stone加法器（1973年提出）使用一棵完全并行的前缀树来计算所有前缀，是延迟最低的并行前缀加法器。

Kogge-Stone前缀树的构造

Kogge-Stone树的构造思路很自然：在第$k$级（$k=0, 1, \ldots, \lceil\log_2 n\rceil - 1$）中，每个位$i$将自己当前的区间$(G_{[i:\text{start}]}, P_{[i:\text{start}]})$与距离它$2^k$位的区间合并。经过$\lceil\log_2 n\rceil$级后，每个位都计算出了从自身到第0位的完整前缀。

具体来说：

• 第0级：每个位$i$持有$(G_i, P_i)$，即区间$[i:i]$的信号。

• 第1级：每个位$i$（$i \geq 1$）将$[i:i]$和$[i-1:i-1]$合并，得到$[i:i-1]$。

• 第2级：每个位$i$（$i \geq 2$）将$[i:i-1]$和$[i-2:i-3]$合并（跨度为2），得到$[i:i-3]$。

• 第$k$级：每个位$i$（$i \geq 2^k$）将当前区间与跨度$2^k$处的区间合并，区间大小翻倍。

8位Kogge-Stone并行前缀加法器的结构（$\lceil\log_2 8\rceil = 3$级）

图图 30.3展示了8位Kogge-Stone加法器的完整前缀树。让我们逐级追踪位3的前缀计算过程：

• Level 0：持有$(G_3, P_3)$，即区间$[3:3]$。

• Level 1：与位4合并，$(G_3, P_3) \circ (G_4, P_4)$得到$[3:4]$……不对，应该是与位2的区间合并——但注意图中的连线方向。每个节点接收的两个输入分别是"自身"和"距离$2^k$的邻居"。在Level 1中，位3（区间$[3:3]$）与位4（区间$[4:4]$）合并得到$[3:4]$——等等，这里的合并顺序很重要。

让我们更仔细地说明。在Kogge-Stone树中，每个节点计算的是从自身到某个更低位的前缀。Level 1时，位3将自己的$(G_3, P_3)$作为高位输入，将相邻位4的$(G_4, P_4)$作为低位输入（注意位编号越大越低，因为我们从MSB到LSB排列），执行$(G_3, P_3) \circ (G_4, P_4)$得到区间$[3:4]$的信号。Level 2时，区间$[3:4]$与区间$[5:6]$合并得到$[3:6]$。Level 3时，$[3:6]$与$[7:7]$合并得到$[3:7]$——这就是位3的完整前缀$[3:0]$（位7就是位0）。

一个数值实例

让我们用一个具体的8位加法来追踪Kogge-Stone树的计算过程。计算$A = 01011001 + B = 00110111$，期望结果为$10010000$（即89 + 55 = 144）。

Step 0: 计算每一位的$G_i$和$P_i$（位7是MSB，位0是LSB）：

位	7	6	5	4	3	2	1	0
$A$	0	1	0	1	1	0	0	1
$B$	0	0	1	1	0	1	1	1
$G_i=A_i \cdot B_i$	0	0	0	1	0	0	0	1
$P_i=A_i \oplus B_i$	0	1	1	0	1	1	1	0

$G_i=1$意味着该位必定产生进位（位0：$A_0=B_0=1$；位4：$A_4=B_4=1$）。$P_i=1$意味着该位会传播进位（位1, 2, 3, 5, 6：$A_i$和$B_i$恰有一个为1）。

Step 1 (Level 1): 相邻位合并。每个位$i$与位$i+1$（更低位）合并，得到2位区间的$(G,P)$：

例如，位3和位4合并：$(G_3, P_3) \circ (G_4, P_4) = (0 + 1 \cdot 1, 1 \cdot 0) = (1, 0)$。这意味着位3$\sim$4作为一个整体会生成进位（因为位4生成进位，且位3会传播它）。

Step 2 (Level 2): 4位区间合并。Step 3 (Level 3): 8位区间合并。

最终，每个位的前缀$G_{[i:0]}$就是该位到位0的组生成信号，进位$C_{i+1} = G_{[i:0]}$（假设$C_0 = 0$）。

经过完整计算，进位序列为$C = 0, 1, 1, 1, 1, 0, 0, 0, 1$（从$C_0$到$C_8$），最终和$S_i = P_i \oplus C_i$为$10010000 = 144$。正确。

这个例子中可以看到Kogge-Stone树如何在3级（$\log_2 8 = 3$）内完成了所有8个进位的计算——而RCA需要8级逐位传播才能完成相同的工作。

Kogge-Stone的延迟与面积

Kogge-Stone加法器的特点是每一级中所有位都执行前缀运算（除了最低$2^k$位在第$k$级不需要运算），因此在每一级都充分利用了硬件的并行性。其性能指标为：

• 级数（延迟）：$\lceil\log_2 n\rceil$级前缀运算，达到理论最小值。

• 节点数（面积）：$n \log_2 n - n + 1$个前缀运算单元。

• 最大扇出：每个节点的输出最多驱动2个后级节点。

• 最大布线跨度：第$k$级的连线跨度为$2^k$个位位置。

性能分析 2 — Kogge-Stone加法器的延迟分析

对于$n$位Kogge-Stone加法器，总延迟由三部分组成：

• $G/P$生成：每一位并行计算$G_i = A_i \cdot B_i$和$P_i = A_i \oplus B_i$，1级门延迟。

• 前缀树：$\lceil\log_2 n\rceil$级，每级包含一个AND-OR运算（计算$G_H + P_H \cdot G_L$）和一个AND运算（计算$P_H \cdot P_L$）。AND-OR可用一个AO21门实现（约1.5级等效门延迟），AND为1级。取关键路径为AO21，每级约2级门延迟。

• 最终求和：$S_i = P_i \oplus C_i$，1级XOR门延迟。

总延迟：$T_\mathrm{KS} = 1 + 2\lceil\log_2 n\rceil + 1 = 2\lceil\log_2 n\rceil + 2$级门延迟。

对于64位加法器：$T_\mathrm{KS} = 2 \times 6 + 2 = 14$级门延迟。以7 nm工艺中每级门延迟15 ps计算：

$$T_\mathrm{KS} = 14 \times 15\,\text{ps} = 210\,\text{ps}$$

这已经接近5 GHz处理器的时钟周期（200 ps）。考虑到加法器的延迟预算约为100$\sim$120 ps（时钟周期的一半），Kogge-Stone需要进一步的电路级优化（如使用定制的复合门）才能满足要求。在实践中，使用AO21/OA21复合门和动态逻辑可以将每级前缀的延迟降低到约1级等效门延迟，使总延迟降至8$\sim$9级。

以下代码展示了16位Kogge-Stone加法器的SystemVerilog实现。代码清晰地体现了并行前缀树的三个阶段：生成/传播位计算、$\lceil\log_2 N\rceil$级前缀合并、最终求和。

module kogge_stone_16 (
    input  logic [15:0] a, b,
    input  logic        cin,
    output logic [15:0] sum,
    output logic        cout
);
    // Stage 0: bit-level generate and propagate
    logic [15:0] g0, p0;
    assign g0 = a & b;           // generate: g = a AND b
    assign p0 = a ^ b;           // propagate: p = a XOR b

    // Parallel prefix tree: 4 levels for 16 bits
    // Each level k merges intervals separated by 2^k
    logic [15:0] g1, p1, g2, p2, g3, p3, g4, p4;

    // Level 1: merge distance = 1
    always_comb begin
        g1 = g0;  p1 = p0;
        for (int i = 1; i < 16; i++) begin
            g1[i] = g0[i] | (p0[i] & g0[i-1]);
            p1[i] = p0[i] & p0[i-1];
        end
    end

    // Level 2: merge distance = 2
    always_comb begin
        g2 = g1;  p2 = p1;
        for (int i = 2; i < 16; i++) begin
            g2[i] = g1[i] | (p1[i] & g1[i-2]);
            p2[i] = p1[i] & p1[i-2];
        end
    end

    // Level 3: merge distance = 4
    always_comb begin
        g3 = g2;  p3 = p2;
        for (int i = 4; i < 16; i++) begin
            g3[i] = g2[i] | (p2[i] & g2[i-4]);
            p3[i] = p2[i] & p2[i-4];
        end
    end

    // Level 4: merge distance = 8
    always_comb begin
        g4 = g3;  p4 = p3;
        for (int i = 8; i < 16; i++) begin
            g4[i] = g3[i] | (p3[i] & g3[i-8]);
            p4[i] = p3[i] & p3[i-8];
        end
    end

    // Final sum: s[i] = p0[i] XOR c[i]
    // where c[i] = g4[i-1] (carry into bit i)
    logic [16:0] carry;
    assign carry[0] = cin;
    assign carry[16:1] = g4 | (p4 & {16{cin}});

    assign sum  = p0 ^ carry[15:0];
    assign cout = carry[16];
endmodule

上述实现中，4级for循环对应4级前缀树（$\lceil\log_2 16\rceil = 4$）。每级$k$将距离$2^k$的区间合并，使用$(G,P)$的结合运算$G_{[i:j]} = G_{[i:m+1]} \mathrel{|} (P_{[i:m+1]} \mathrel{\&} G_{[m:j]})$。综合工具会将这些循环展开为全并行的组合逻辑——16位版本约96个前缀运算节点。扩展到64位只需将级数增加到6级，节点数增长到约$64 \times 6 = 384$个。

Kogge-Stone的布线问题

Kogge-Stone加法器的主要缺点是面积大、布线复杂。以64位为例：

• 前缀树中的节点总数为$64 \times 6 - 64 + 1 = 321$个前缀运算单元。

• 在第6级（最后一级），一些连线需要跨越$2^5 = 32$个位位置的距离。

在物理实现中，长距离连线带来两个问题：(1) 布线拥塞——高层级的大量长连线需要穿越整个加法器宽度，与低层级的短连线争抢布线资源；(2) 连线延迟——在先进工艺中（7 nm及以下），连线的RC延迟可能比逻辑门的延迟还大，长连线的延迟可能占到总延迟的50%以上。这意味着RTL仿真中Kogge-Stone的延迟最低，但在布局布线后的实际芯片上，长连线的延迟惩罚可能使它的优势大打折扣。

这促使设计者寻找面积和布线更友好的替代方案——即Brent-Kung和Han-Carlson加法器。

Brent-Kung加法器：面积最优的前缀树

Brent-Kung加法器（1982年提出）采用了一种完全不同的策略来构造前缀树：不追求最低延迟，而是追求最少的前缀运算节点数。

Brent-Kung树的构造思路

Brent-Kung的关键观察是：在Kogge-Stone树中，每一级都让所有位执行前缀运算，但其中很多运算是"冗余"的。例如，在8位Kogge-Stone的Level 2中，位5计算了$[5:0]$的前缀，但这个中间结果只是位5"路过"时计算的——最终我们需要的只是每个位的完整前缀$[i:0]$，至于中间级上的局部前缀，只要最终能算出来就行，不需要在每一级都更新。

Brent-Kung树正是利用了这个观察。它将前缀计算分为两个清晰的阶段：

第一阶段（自底向上，归约阶段）：类似于一棵二叉归约树。第1级合并相邻的对$(0,1), (2,3), (4,5), (6,7)$；第2级合并$(0{:}1, 2{:}3)$和$(4{:}5, 6{:}7)$；第3级合并$(0{:}3, 4{:}7)$。经过$\log_2 n$级后，只有最高位（位$n-1$）拥有完整的前缀$[n{-}1:0]$。在这个过程中，只有每一级的"偶数位"（相对于该级的合并粒度）执行运算，其余位不参与——这就是节省面积的关键。

第二阶段（自顶向下，传播阶段）：将已知的前缀信息向下传播给那些在第一阶段中被"跳过"的位。例如，归约阶段结束后，位3的前缀$[3:0]$已经在第2级计算出来了，位1的前缀$[1:0]$在第1级就算出来了，但位2的前缀$[2:0]$还没有——它只有$[2:2]$和$[3:2]$的局部信息。传播阶段通过将位3的完整前缀$[3:0]$与位2的局部信息$[2:2]$合并，得到位2的完整前缀。从高位向低位传播，经过$\log_2 n - 1$级后，所有位都获得了完整的前缀。

8位Brent-Kung并行前缀加法器：3级归约 + 2级传播 = 5级总延迟

图图 30.4展示了8位Brent-Kung加法器的完整结构。橙色节点是归约阶段的运算，青色节点是传播阶段的运算。注意：

• 归约阶段（L1$\sim$L3）共$n/2 + n/4 + \ldots + 1 = n - 1$个运算节点（8位时为4+2+1=7个）。

• 传播阶段（L4$\sim$L5）共$n/2 - 1$个运算节点（8位时为1+3=4个）。

• 总节点数为$n - 1 + n/2 - 1 = 3n/2 - 2$（8位时为10个），远少于Kogge-Stone的$n\log_2 n - n + 1$（8位时为17个）。

Brent-Kung与Kogge-Stone的对比

Brent-Kung加法器的性能指标：

• 级数（延迟）：$2\lceil\log_2 n\rceil - 1$级前缀运算——几乎是Kogge-Stone的两倍。

• 节点数（面积）：$2n - 2 - \lceil\log_2 n\rceil$个前缀运算单元。

• 最大扇出：归约阶段的某些节点扇出达到3（既驱动下一级归约，又驱动传播阶段），需要缓冲。

• 布线：最大连线跨度与Kogge-Stone相同（第$k$级为$2^k$），但高跨度连线的数量少得多——归约阶段的每一级只有$O(1)$根长连线，而Kogge-Stone每一级有$O(n)$根。

用64位的具体数字来对比：

指标	Kogge-Stone	Brent-Kung
前缀级数（延迟）	6级	11级
节点数（面积）	321个	120个
高跨度连线数	$O(n)$根/级	$O(1)$根/级

Brent-Kung用接近2倍的延迟换来了62%的面积节省。这个权衡在很多场景下是合理的——并非所有加法器都需要极致的速度。例如，在乘法器的最终加法阶段，加法器的延迟预算相对宽裕（因为乘法本身就是多周期操作），此时Brent-Kung的面积优势更有吸引力。在低功耗的嵌入式RISC-V核心中，Brent-Kung也是主ALU加法器的常见选择。

Ladner-Fischer加法器与Kogge-Stone/Brent-Kung之间的光谱

Kogge-Stone和Brent-Kung可以看作是并行前缀加法器设计空间的两个极端：Kogge-Stone追求最小延迟（最少级数），Brent-Kung追求最小面积（最少节点数）。在这两个极端之间，存在一个连续的设计光谱。

Ladner-Fischer加法器（1980年）是一类可参数化的前缀树，通过调整一个参数（每一级中哪些位执行运算，哪些位跳过），可以在Kogge-Stone和Brent-Kung之间平滑地移动。增加更多的活跃节点会减少延迟但增加面积，反之亦然。

这个"光谱"的存在使得处理器设计者可以根据具体的面积-延迟约束，选择一个最适合的平衡点。Han-Carlson加法器（下一节讨论）就是这个光谱上的一个特别有吸引力的点。

但对于处理器中主ALU的加法器来说，Brent-Kung的11级前缀延迟（加上G/P生成和最终求和，总共约24级门延迟）仍然太慢。我们需要一种能在Kogge-Stone的速度和Brent-Kung的面积之间取得更好平衡的方案。

Han-Carlson加法器：速度与面积的最佳折中

Han-Carlson加法器（1987年提出）巧妙地混合了Kogge-Stone和Brent-Kung的思想，在两者之间找到了一个接近最优的折中点。

Han-Carlson的设计思路

Han-Carlson的核心想法非常优雅：

1. 先在偶数位之间执行一棵完整的Kogge-Stone前缀树，计算出所有偶数位的完整前缀（即进位）。

2. 然后使用一级额外的前缀运算，让每个奇数位从相邻的偶数位"借用"进位信息。

为什么这样做有效？因为Kogge-Stone树的面积与处理的位数成$O(n \log n)$关系。如果我们只对一半的位（$n/2$个偶数位）执行Kogge-Stone，前缀树的面积就减少了大约一半——准确地说，从$n\log_2 n - n + 1$降低到约$(n/2)\log_2(n/2)$。而代价仅仅是多一级延迟（奇数位的补全级）。

Han-Carlson前缀树的结构

8位Han-Carlson加法器：偶数位执行Kogge-Stone前缀，奇数位仅需一级额外延迟

图图 30.5中，橙色节点是偶数位之间的Kogge-Stone前缀运算，绿色节点是奇数位的补全级。可以看到：

• Level 1$\sim$3（橙色）：只有偶数位（0, 2, 4, 6）参与前缀计算，奇数位只是直通。这3级就是一个4位（半数位）的Kogge-Stone树。

• Level 4（绿色）：奇数位（1, 3, 5）从相邻的偶数位获取进位信息，完成自己的前缀。

Han-Carlson的延迟与面积分析

Han-Carlson加法器的延迟为$\lceil\log_2 n\rceil + 1$级前缀运算——仅比Kogge-Stone多一级。但面积优势显著：

• 前缀运算节点数：约$(n/2)\log_2(n/2) + n/2 \approx n\log_2 n / 2$，约为Kogge-Stone的一半。

• 最大布线跨度：减半，因为Kogge-Stone部分只处理偶数位，相邻活跃位之间的距离为2个位位置，最大连线跨度从$n/2$降低到$n/4$。

用64位的具体数字来对比三种前缀加法器：

设计权衡 1 — 加法器的速度与面积权衡

加法器类型	前缀级数	节点数	最大布线跨度	适用场景
Kogge-Stone	6级	321个	32位	关键路径ALU
Brent-Kung	11级	120个	32位	面积敏感、非关键路径
Han-Carlson	7级	161个	16位	ALU/AGU通用

Han-Carlson以仅1级额外延迟的代价，节省了约50%的面积和约50%的最大布线跨度。在物理实现后，由于布线更友好、拥塞更少，Han-Carlson的实际延迟可能与Kogge-Stone相当甚至更优。

设计提示

在实际处理器设计中，选择加法器结构时需要综合考虑物理设计因素。Kogge-Stone在RTL仿真中延迟最低，但在布局布线后，其密集的长距离连线可能导致实际延迟并不优于Han-Carlson。许多商用处理器设计（如ARM Cortex-A系列）采用Han-Carlson作为主ALU加法器——以1级额外延迟换取近50%的面积节省和更友好的布线特性，这在物理实现后往往是更优的选择。

条件求和加法器与进位选择加法器

到目前为止，我们一直在沿着"更快地计算进位"这条路走。条件求和加法器提供了一条完全不同的思路：不去计算进位，而是预测进位的两种可能结果，等进位到来时直接选择正确的那个。

条件求和加法器的推导

考虑一个$n$位加法器的高半部分（比如高32位）。高半部分的计算结果取决于低半部分传来的进位$C_{32}$，而$C_{32}$只有两种可能的值：0或1。如果我们同时计算$C_{32}=0$和$C_{32}=1$两种情况下的高半部分结果，那么当$C_{32}$最终确定后，只需要一个MUX就能在这两个预计算结果之间选择正确的那个。

这个思想可以递归地应用：先将$n$位加法器分成$n/2$两半，每半部分预计算两种进位情况。然后每半部分再分成两个$n/4$的小组，每组预计算两种情况……如此递归，最终每组只有1$\sim$2位，两种情况可以直接用查找表或简单逻辑计算。

8位条件求和加法器的树形选择结构：3级MUX选择

选择树的延迟为$\lceil\log_2(n/k)\rceil$级MUX延迟。MUX的延迟通常比前缀运算的AND-OR门更低（约1级门延迟），因此条件求和加法器的实际速度很有竞争力。

进位选择加法器：条件求和的实用化

纯粹的条件求和加法器在每一位都做双份计算，面积开销较大。在实际设计中，更常用的是进位选择加法器（Carry-Select Adder）——条件求和思想的"工程化"版本。

进位选择加法器将$n$位加法器分成若干个组，每组内部使用RCA计算两种进位假设（$C_\mathrm{in}=0$和$C_\mathrm{in}=1$）下的结果，组间通过MUX级联选择。

最优分组大小的推导

组大小如何选择是进位选择加法器设计的关键问题。考虑将$n$位加法器分成$m$个组，大小分别为$k_1, k_2, \ldots, k_m$。

第一组（最低位组）的延迟是$k_1$级FA延迟（它的进位$C_\mathrm{in}$已知，不需要预计算两种情况，只计算一种）。第一组的进位输出$C_{k_1}$确定后，通过MUX选择第二组的正确结果，延迟为$t_\mathrm{MUX}$。但第二组内部的RCA也需要时间——如果$k_2 \cdot t_\mathrm{FA} \leq k_1 \cdot t_\mathrm{FA}$（即第二组在第一组完成之前就算完了），则第二组的延迟被第一组掩盖，总延迟只增加$t_\mathrm{MUX}$。

推广来看，如果后面的组在前面的组确定进位之前就已经完成了预计算，那么关键路径上每个后续组只贡献一个$t_\mathrm{MUX}$延迟。最优策略是让每个组的RCA延迟刚好等于前面所有组的MUX级联延迟加上第一组的RCA延迟。设$t_\mathrm{FA} \approx t_\mathrm{MUX}$（粗略近似），则最优分组大小为递增序列：

$$k_1, k_1+1, k_1+2, \ldots$$

第$j$组的大小$k_j = k_1 + (j-1)$，因为第$j$组有$k_1 + (j-2)$个MUX延迟的"等待时间"可以利用。总位数约束为：

$$\sum_{j=1}^{m} k_j = mk_1 + m(m-1)/2 = n$$

总延迟为第一组RCA延迟加上$(m-1)$级MUX延迟：

$$T = k_1 \cdot t_\mathrm{FA} + (m-1) \cdot t_\mathrm{MUX} \approx (k_1 + m - 1) \cdot t_\mathrm{FA}$$

对$k_1$和$m$做优化（令$\partial T / \partial m = 0$），可以得到最优解：$k_1 \approx \sqrt{2n}$，$m \approx \sqrt{2n}$，总延迟：

$$T_\mathrm{CSel} \approx 2\sqrt{2n} \cdot t_\mathrm{FA} = O(\sqrt{n})$$

对于64位加法器：$T_\mathrm{CSel} \approx 2\sqrt{128} \approx 23$级FA延迟。虽然比$O(\log n)$的并行前缀加法器慢，但进位选择加法器的面积仅约为RCA的2倍（每组两套RCA加MUX），布线极其简单（组间只有单一的进位选择信号），对EDA工具非常友好。

在实践中，一个典型的64位进位选择加法器使用如下分组：$k = 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 4$（共11组，总计64位）。前几组较小是为了让进位尽快确定；后面的组逐渐增大，利用前面组已经积累的"等待时间"。

进位选择加法器的面积约为RCA的2倍（每组有两套计算电路），远小于并行前缀加法器。在中等性能设计（如某些嵌入式RISC-V核心或FPGA实现）中，进位选择加法器是一个实用的选择。

Ling加法器：针对物理实现的优化

在讨论了各种前缀树拓扑之后，值得一提的是Ling加法器——一种通过修改前缀运算本身来降低关键路径延迟的技术。Ling加法器（1981年）不改变前缀树的拓扑（仍然可以使用Kogge-Stone、Han-Carlson等），而是通过一种代数变换来减少每级前缀运算的复杂度。

回顾标准前缀运算符$\circ$中计算$G_{[j:i]}$的表达式：

$$G_{[j:i]} = G_H + P_H \cdot G_L$$

这是一个AND-OR操作，在CMOS电路中通常用AOI（AND-OR-Invert）门实现，延迟约1.5$\sim$2级等效反相器延迟。

Ling的关键观察是：定义一个"伪生成"信号$H_i = G_i + P_i = A_i + B_i$（即$A_i$或$B_i$至少有一个为1），可以证明进位方程可以改写为：

$$C_{i+1} = G_i + P_i \cdot C_i = H_i \cdot C_i + G_i = H_i \cdot (C_i + G_i)$$

由于$H_i$是一个OR操作（比AND-OR更简单），在前缀树的每一级中，$H$信号的合并比$G$信号的合并少一级逻辑门。具体来说，Ling变换将每级前缀运算的延迟从一个AOI门降低到一个AND门（对于$H$信号的合并），节省约0.5$\sim$1级门延迟。

对于6级前缀的64位加法器，Ling优化可以将总延迟减少3$\sim$6级等效门延迟——这在100 ps的延迟预算中是非常显著的改进。Intel和ARM的多款高性能处理器在其ALU加法器中使用了Ling优化。

Ling优化的代价是在最终求和阶段需要额外的逻辑来从$H$信号恢复出真正的进位，但这一步可以与前缀树的最后一级并行完成，不增加总延迟。

性能分析 3 — 64位各类加法器的延迟与面积综合对比

以7 nm工艺为基准，每级门延迟约15 ps：

加法器类型	门延迟级数	延迟(ps)	相对面积	布线复杂度
行波进位（RCA）	128级	1920	1.0$\times$	最低
超前进位（CLA）	8级	120	2.5$\times$	中等
进位选择	14$\sim$18级	210$\sim$270	1.8$\times$	低
Kogge-Stone	14级	210	4.0$\times$	最高
Han-Carlson	16级	240	2.2$\times$	中等
Brent-Kung	24级	360	1.5$\times$	低

注：上述数字基于简单门延迟模型。实际设计中，使用复合门（AO21等）和定制电路可将前缀加法器的每级延迟降至接近1级等效门延迟，使Kogge-Stone的总延迟降至约8级（120 ps），Han-Carlson约9级（135 ps）。

加法器设计中的物理实现考量

在结束加法器的讨论之前，有必要强调几个在实际芯片设计中至关重要、但在教科书中经常被忽略的物理实现因素。

连线延迟的主导地位

在90 nm及以上的工艺节点中，逻辑门的延迟远大于连线延迟，因此加法器优化的重点是减少逻辑级数。但在28 nm以下的先进工艺中，情况发生了根本性的逆转：连线延迟开始主导总延迟。

在7 nm工艺中，一个反相器的延迟约为12 ps，但一根跨越10个标准单元宽度的金属连线的RC延迟也约为10 ps。对于Kogge-Stone加法器第6级的连线（跨越32个位位置，约160个标准单元宽度），连线延迟可能高达50$\sim$80 ps——远超一级逻辑门的延迟。

这就解释了为什么在先进工艺中，减少布线跨度（如Han-Carlson所做的）往往比减少逻辑级数（如Kogge-Stone所追求的）更能降低实际延迟。

动态逻辑与Domino加法器

在最高性能的处理器中（如Intel和AMD的高端桌面/服务器核心），ALU加法器通常不使用静态CMOS逻辑，而是使用动态逻辑——特别是Domino逻辑。

Domino逻辑的每一级在时钟的一个相位预充电（将输出节点充到$V_{DD}$），在另一个相位求值（根据输入条件决定是否放电到$0$）。由于只有NMOS拉低路径参与求值，晶体管宽度可以减半，延迟约为静态CMOS的60%$\sim$70%。

使用Domino逻辑的64位加法器可以在6$\sim$8级逻辑延迟内完成计算，对应约80$\sim$100 ps——这正好满足5 GHz处理器的100 ps延迟预算。代价是Domino逻辑的功耗较高（每个周期都有预充电电流），且设计复杂度显著增加（需要手动管理预充电/求值时序、防止电荷共享等）。

在移动处理器中（如ARM Cortex系列），由于功耗预算的限制，通常使用静态CMOS逻辑加上Ling优化来实现加法器，接受稍高的延迟以换取更低的功耗。

加法器的综合与定制

在实际的处理器设计流程中，加法器的实现通常分为两种方式：

• 综合加法器：由RTL描述经EDA综合工具自动生成。综合工具（如Synopsys Design Compiler）内置了多种加法器结构的知识，可以根据延迟约束自动选择最优的加法器拓扑。这种方式设计效率高，但优化程度受限于工具的能力。

• 定制加法器：由电路设计工程师手动设计，通常在晶体管级（schematic或定制版图）上完成。关键路径上的加法器（如ALU主加法器）在高性能处理器中几乎总是手动定制的，因为EDA工具无法达到手动优化的延迟水平。Intel报告其核心ALU加法器的手动优化比综合结果快15%$\sim$25%。

在RISC-V生态系统中，由于很多设计使用开源工具链（如Yosys + OpenROAD），加法器的实现更加依赖综合工具的质量。这也是RISC-V开源处理器核心与商用ARM/x86核心在时钟频率上存在差距的原因之一。

减法与比较操作

在设计好了高速加法器之后，减法和比较操作几乎是"免费"获得的——这要归功于二进制补码表示的一个美妙性质。

减法的加法器实现

在二进制补码表示下，减法可以通过加法实现：

$$A - B = A + \overline{B} + 1$$

其中$\overline{B}$是$B$的按位取反。$\overline{B} + 1$正好等于$-B$的补码表示——这不是巧合，而是补码的定义。

在硬件中，这意味着只需在加法器的$B$输入端增加一组XOR门（受减法控制信号SUB控制的条件取反器），并将进位输入$C_\mathrm{in}$设为1（实现"$+1$"）。XOR门的延迟与$G/P$计算并行，不增加关键路径延迟。因此，加法和减法共享同一个加法器硬件，零额外延迟，仅增加$n$个XOR门的面积。

比较操作的实现

比较操作（SLT、SLTU等）可以复用减法结果。RISC-V的SLT指令在$A < B$（有符号比较）时将目标寄存器设为1，否则设为0。实现方式是执行$A - B$，然后检查结果的标志位：

• 有符号比较（SLT）：$A < B$当且仅当$\text{Sign} \oplus \text{Overflow}$，其中Sign是减法结果的最高位，Overflow是有符号溢出标志。

• 无符号比较（SLTU）：$A < B_u$当且仅当$\overline{\text{Carry}}$，即减法没有产生借位（进位输出为0）。

标志位的生成是加法器的副产品，不需要额外的逻辑延迟：

$$\begin{aligned} \text{Zero} &= \overline{S_{n-1} + S_{n-2} + \cdots + S_0} \quad \text{（所有位为0的NOR归约）} \\ \text{Sign} &= S_{n-1} \quad \text{（结果的最高位）} \\ \text{Carry} &= C_n \quad \text{（最高位的进位输出）} \\ \text{Overflow} &= C_n \oplus C_{n-1} \quad \text{（最高两位进位不一致）} \end{aligned}$$

需要注意的是，Zero标志的NOR归约看似需要等待所有和位$S_i$都计算完毕后再执行，这可能在最终和$S$的基础上增加一级门延迟。在实际设计中，有两种优化方法：(1) 在前缀树内部预先计算Zero标志的部分结果；(2) 利用$G$和$P$信号直接判断——如果$P_{[n{-}1:0]} = 1$（所有位都传播）且$C_0 = 0$，则所有和位为零。

有符号比较的正确性推导

有符号比较$A < B$的判断条件$\text{Sign} \oplus \text{Overflow}$值得推导一下，因为这个条件看起来并不那么直观。

设$R = A - B$。如果没有溢出（$\text{Overflow} = 0$），那么$R$正确地表示了$A - B$的值，此时$A < B$等价于$R < 0$等价于$\text{Sign} = 1$。而$\text{Sign} \oplus 0 = \text{Sign}$，条件成立。

如果发生了溢出（$\text{Overflow} = 1$），那么$R$的符号与真实结果相反。例如，当$A = -100$（负数）而$B = 100$（正数）时，$A - B = -200$应该是负数，但如果用8位有符号数计算$-100 - 100$会溢出，结果的最高位可能变成0（看起来是正数）。溢出时符号被"翻转"了，所以$A < B$等价于$\text{Sign} = 0$。而$0 \oplus 1 = 1 = \text{Sign} \oplus \text{Overflow}$也成立。

因此，$A < B$在所有情况下都等价于$\text{Sign} \oplus \text{Overflow}$。这个条件可以用一个XOR门在1级门延迟内计算出来——Sign直接取结果的最高位，Overflow取最高两位进位的XOR。整个比较操作的延迟与减法相同（因为标志位是加法器的副产品），不增加额外的关键路径延迟。

ALU的统一数据通路

硬件描述 2 — ALU的统一数据通路

一个典型的64位ALU可以用以下方式统一实现加法、减法、比较和逻辑运算：

1. 输入预处理：操作数B经过条件取反器（XOR阵列），由控制信号SUB决定是否取反。

2. 核心加法器：64位Han-Carlson或Kogge-Stone加法器，$C_\mathrm{in}$在减法时设为1。

3. 逻辑运算：AND/OR/XOR直接对原始输入执行按位运算，与加法器并行工作。

4. 结果选择：4:1 MUX根据操作码选择加法结果、逻辑运算结果或比较结果。

5. 标志位生成：与加法器同时完成，用于比较指令和条件分支。

关键路径为：输入取反$\to$加法器$\to$结果MUX，约15$\sim$18级门延迟（64位）。逻辑运算的关键路径更短（仅1级门延迟 + MUX），完全被加法器的延迟掩盖。

移位器

移位操作在处理器中非常常见，不仅用于显式的移位指令（SLL、SRL、SRA），还被地址计算、乘法优化和位字段操作所需要。RISC-V ISA定义了三种基本移位操作：

• 逻辑左移（SLL）：向左移位，低位补0。

• 逻辑右移（SRL）：向右移位，高位补0。

• 算术右移（SRA）：向右移位，高位补符号位（保持符号不变）。

对于RV64I，移位量为0$\sim$63，即6位移位量控制一个64位操作数的移位。

桶形移位器：分解移位量

桶形移位器（Barrel Shifter）的设计思路来自一个简单的数学观察：任何0$\sim$63的移位量$s$都可以唯一地分解为二进制表示$s = 32s_5 + 16s_4 + 8s_3 + 4s_2 + 2s_1 + s_0$。如果我们依次应用"移32位或不移"、"移16位或不移"……"移1位或不移"这6步，就能实现任意移位量。每一步都是一个简单的2:1 MUX选择——要么通过（不移），要么移位固定的$2^k$位。

64位桶形移位器的层级结构（6级MUX阵列）

桶形移位器的延迟为$\log_2 n$级MUX延迟，对于64位操作数为6级。由于每级MUX的延迟约为1个门延迟（使用传输门实现时甚至更低），总延迟约为6$\sim$8级门延迟——远低于加法器的延迟，因此移位操作通常不是ALU的关键路径。

面积方面，桶形移位器需要$n \times \log_2 n = 64 \times 6 = 384$个2:1 MUX。虽然数量不少，但每个MUX的面积很小（仅需几个晶体管），总面积在处理器中几乎可以忽略。

统一左移和右移：反转技巧

要同时支持左移和右移，最直接的方案是两套独立的移位器，但这样面积翻倍。一个巧妙的技巧是反转-左移-反转：

1. 如果是右移操作，先将输入64位数据的位顺序反转（第0位和第63位交换，第1位和第62位交换……）。

2. 然后执行左移。

3. 最后再将结果的位顺序反转回来。

为什么这样做等价于右移？因为将数据反转后左移$k$位，相当于在原始数据上右移$k$位。而位反转只是布线层面的交叉连接——不需要任何逻辑门，零延迟，零面积。因此只需要一套左移移位器加上输入和输出端的两个反转MUX即可。

设计提示

绝大多数商用处理器使用"反转-左移-反转"方案实现右移，因为它不增加任何逻辑延迟（位反转只是布线层面的交叉连接），却节省了近50%的MUX面积。算术右移（SRA）的符号位扩展可以通过在移位后对空出的高位填充符号位来实现，仅需在桶形移位器的输入端增加少量MUX逻辑。

漏斗移位器：统一移位和旋转

漏斗移位器（Funnel Shifter）是桶形移位器的进一步推广。它接收一个$2n$位的输入（由两个$n$位操作数拼接而成），输出从这个$2n$位值中提取的$n$位结果。通过控制如何拼接两个输入操作数，漏斗移位器可以统一实现所有移位和旋转操作：

操作	$A$（高$n$位）	$B$（低$n$位）
逻辑左移（SLL by $s$）	操作数	$0$（全零）
逻辑右移（SRL by $s$）	$0$（全零）	操作数
算术右移（SRA by $s$）	符号位扩展	操作数
左旋转（ROL by $s$）	操作数	操作数
右旋转（ROR by $s$）	操作数	操作数

漏斗移位器的硬件实现与桶形移位器类似，但第一级MUX的输入宽度为$2n$，后续每级逐步将宽度缩减到$n$。总延迟与桶形移位器相同：$\lceil\log_2 n\rceil$级MUX延迟。

在RISC-V中，B扩展（Zbb/Zbs）定义了ROL和ROR旋转指令，漏斗移位器可以零额外延迟地支持这些指令——旋转不需要任何特殊的硬件，只是改变了输入端$A$和$B$的接法。

RISC-V特有的移位器设计考量

32位操作（W后缀指令）

RV64I定义了SLLW、SRLW、SRAW等32位移位指令。这些指令只对操作数的低32位进行移位，移位量为5位（0$\sim$31），结果符号扩展到64位。

在64位移位器上实现32位移位有两种方案：

• 复用方案：将64位操作数的高32位清零（SLL/SRL）或复制符号位（SRA），然后使用同一套64位移位器。移位量的第6位（$s_5$）强制设为0。移位完成后，将结果的低32位符号扩展到64位。这种方案不需要额外的硬件，但在输出端需要一个32位符号扩展MUX。

• 独立方案：使用一个独立的32位移位器处理W后缀指令。面积增加约50%，但避免了输入输出的预处理延迟。

大多数处理器选择复用方案，因为32位移位指令的频率较低，不值得为其增加独立硬件。

Zbb/Zbs位操作扩展

RISC-V的B扩展（位操作扩展）为移位器增加了若干新操作，其中部分可以在现有移位器硬件上零开销实现：

• Zbb（Basic Bit Manipulation）：

  • CLZ/CTZ：计算前导零/尾随零数量。这需要一个前导零计数器（Leading Zero Counter, LZC），通常用树形结构实现，延迟为$O(\log n)$。LZC也被除法器的提前终止优化所使用，因此可以共享硬件。

  • CPOP：计算置1位的数量（population count）。需要一个专用的位计数器电路。

  • REV8：字节反转。仅需布线重排，零逻辑门延迟。

  • BREV：位反转。同样仅需布线重排。

• Zbs（Single-bit operations）：

  • BSET/BCLR/BINV：设置/清除/翻转指定位。可以用移位器生成单比特掩码，然后与操作数做OR/AND/XOR。

  • BEXT：提取指定位。可以用移位器将目标位移到最低位，然后AND掩码。

CLZ和CTZ的硬件实现与移位器的桶形结构有一定的关联——CTZ可以通过"找到最低位的1"来计算，而这等价于计算$\text{CTZ}(x) = \text{CLZ}(\text{bitrev}(x))$。如果移位器已经支持位反转（布线操作），那么只需要一个LZC电路即可同时支持CLZ和CTZ。

硬件描述 3 — 移位器与位操作的统一设计

在支持B扩展的RISC-V处理器中，移位器功能单元通常集成以下子模块：

1. 桶形/漏斗移位器：支持SLL/SRL/SRA/ROL/ROR及其W后缀版本。

2. 前导零计数器（LZC）：支持CLZ/CTZ，同时被除法器共享。

3. 位计数器：支持CPOP。

4. 单比特操作逻辑：支持BSET/BCLR/BINV/BEXT（复用移位器生成掩码）。

5. 布线重排网络：支持REV8/BREV（零逻辑延迟）。

所有这些操作的延迟都不超过$\lceil\log_2 n\rceil + 1$级MUX延迟，可以在单周期内完成。移位器功能单元的关键路径通常远短于加法器，因此B扩展的所有位操作都不会成为ALU的性能瓶颈。

乘法器：从阵列到Wallace树

乘法是整数运算中最复杂、延迟最高的单周期/少周期操作。在RISC-V的M扩展中，乘法指令包括：

• MUL：$\text{rd} = (A \times B)[63{:}0]$——取乘积的低64位。

• MULH：$\text{rd} = (A \times_s B)[127{:}64]$——有符号乘积的高64位。

• MULHU：$\text{rd} = (A \times_u B)[127{:}64]$——无符号乘积的高64位。

• MULHSU：$\text{rd} = (A \times_{su} B)[127{:}64]$——混合符号乘积的高64位。

两个$n$位数相乘产生一个$2n$位的乘积。乘法的基本步骤可以分解为三个阶段：（1）生成部分积（Partial Product Generation），（2）压缩部分积（Partial Product Reduction），（3）最终加法（Final Addition）。我们将逐步推导每个阶段的高效实现。

阵列乘法器：为什么朴素方案太慢

最直观的乘法器实现是阵列乘法器（Array Multiplier），它直接模拟手算乘法的过程。以8位乘法为例：被乘数$A = A_7A_6\ldots A_0$，乘数$B = B_7B_6\ldots B_0$。乘数的每一位$B_j$与被乘数$A$的所有位相与，产生一行部分积：

$$PP_j[i] = A_i \cdot B_j, \quad i = 0, 1, \ldots, n-1$$

共$n$行部分积，每行$n$位，第$j$行向左移$j$位（对应乘以$2^j$）。这些部分积形成一个菱形矩阵（也称为部分积矩阵），如下所示（以4位为例，$A = A_3A_2A_1A_0$，$B = B_3B_2B_1B_0$）：

				$A_3B_0$	$A_2B_0$	$A_1B_0$	$A_0B_0$
			$A_3B_1$	$A_2B_1$	$A_1B_1$	$A_0B_1$
		$A_3B_2$	$A_2B_2$	$A_1B_2$	$A_0B_2$
	$A_3B_3$	$A_2B_3$	$A_1B_3$	$A_0B_3$
$P_7$	$P_6$	$P_5$	$P_4$	$P_3$	$P_2$	$P_1$	$P_0$

矩阵的每一列代表一个权位位置，每列中的元素数量呈先增后减的"菱形"分布。中间列（权位$n-1$）的元素最多，有$n$个（对于4位乘法，第3列和第4列各有4个和3个元素）。乘法器的任务就是将这个矩阵压缩为一行——即最终的$2n$位乘积。

阵列乘法器的做法是逐行累加：先加前两行得到中间结果，再加第三行，再加第四行……每次累加需要一次加法器操作。用行波加法器逐行累加的总延迟为$(n-1)$次$O(n)$加法，即$O(n^2)$。

这种实现的问题很明显：

• 部分积数量：$n$行——这意味着需要$n-1$次加法来逐行累加。

• 延迟：如果逐行累加，每次加法使用一个$n$位RCA，每个RCA的延迟为$O(n)$，$n-1$次加法的总延迟为$O(n^2)$。即使每次加法使用$O(\log n)$的快速加法器，总延迟仍为$O(n \log n)$。

• 面积：$n^2$个AND门（生成部分积）加上$n(n-1)$个全加器（累加），总面积$O(n^2)$。

对于64位乘法，阵列乘法器需要约4096个AND门和约4000个全加器，延迟约为128级门延迟（约2 ns）——需要10个时钟周期。我们需要两种互补的技术来大幅降低延迟：Booth编码减少部分积的行数，Wallace树加速部分积的压缩。

Booth编码：减少部分积

为什么部分积行数是关键

在乘法器的三个阶段中，部分积压缩的延迟与部分积的行数直接相关。如果我们能将部分积从$n$行减少到$n/2$行，压缩树的级数就减少约1级（具体取决于压缩器类型），对应减少2$\sim$3级门延迟。因此，减少部分积行数是优化乘法器延迟的有效手段。

从数学推导到编码表

Booth编码的数学基础来自对二进制数的一种重新编码。考虑乘数$B$的二进制表示：

$$B = \sum_{i=0}^{n-1} b_i \cdot 2^i$$

其中$b_i \in \{0, 1\}$。在普通乘法中，每一位$b_i$产生一行部分积$b_i \cdot A \cdot 2^i$，共$n$行。

现在考虑将$B$用一种冗余表示重新编码。定义$b_{-1} = 0$（虚拟的最低位），然后构造一个新的数字序列$d_j$，其中$j = 0, 1, \ldots, n/2 - 1$：

$$d_j = b_{2j-1} + b_{2j} - 2 \cdot b_{2j+1}$$

为什么这个定义有效？让我们验证这组$d_j$确实表示了$B$。将$B$的各位按相邻对分组：

$$\begin{aligned} B &= \sum_{i=0}^{n-1} b_i \cdot 2^i \\ &= \sum_{j=0}^{n/2-1} \big(b_{2j} \cdot 2^{2j} + b_{2j+1} \cdot 2^{2j+1}\big) \\ &= \sum_{j=0}^{n/2-1} \big(b_{2j} + 2 \cdot b_{2j+1}\big) \cdot 2^{2j} \end{aligned}$$

而利用$b_{2j-1} = b_{2(j-1)+1}$（上一组的最高位等于当前组的隐式最低位），可以将式 (30.16)改写为使用重叠分组的冗余表示。具体的推导过程涉及到对相邻两位求和的恒等变换：

$b_{2j} + 2b_{2j+1} = (b_{2j} + b_{2j-1}) + (2b_{2j+1} - b_{2j-1}) \cdot ...$

更直接地，我们可以验证：

$$B = \sum_{j=0}^{n/2-1} d_j \cdot 2^{2j} = \sum_{j=0}^{n/2-1} (b_{2j-1} + b_{2j} - 2b_{2j+1}) \cdot 2^{2j}$$

展开右边：

$$\begin{aligned} &\sum_{j=0}^{n/2-1} (b_{2j-1} + b_{2j} - 2b_{2j+1}) \cdot 2^{2j} \\ = &\sum_{j=0}^{n/2-1} b_{2j-1} \cdot 2^{2j} + \sum_{j=0}^{n/2-1} b_{2j} \cdot 2^{2j} - \sum_{j=0}^{n/2-1} 2b_{2j+1} \cdot 2^{2j} \\ = &\sum_{j=0}^{n/2-1} b_{2j-1} \cdot 2^{2j} + \sum_{j=0}^{n/2-1} b_{2j} \cdot 2^{2j} - \sum_{j=0}^{n/2-1} b_{2j+1} \cdot 2^{2j+1} \end{aligned}$$

第一项中，$b_{-1} = 0$（$j=0$时），其余项$b_{2j-1} \cdot 2^{2j} = b_{2(j-1)+1} \cdot 2^{2j}$。将第一项和第三项合并（令$k = j-1$使第一项的$j$项与第三项的$k$项对齐），经过仔细的指标替换可以验证所有项正好抵消为$\sum b_i \cdot 2^i = B$。

关键结论是：$d_j$的取值范围为$\{-2, -1, 0, +1, +2\}$，而每个$d_j$对应一行部分积$d_j \cdot A \cdot 2^{2j}$。共$n/2$行——部分积数量减半！

基-4 Booth编码表

每个$d_j$由三个相邻的乘数位$(b_{2j+1}, b_{2j}, b_{2j-1})$决定，具体的编码表如下：

$B_{2j+1}$	$B_{2j}$	$B_{2j-1}$	部分积系数 $d_j$
0	0	0	$0$
0	0	1	$+1 \times A$
0	1	0	$+1 \times A$
0	1	1	$+2 \times A$
1	0	0	$-2 \times A$
1	0	1	$-1 \times A$
1	1	0	$-1 \times A$
1	1	1	$0$

这个编码表可以用直觉来理解。三位$(B_{2j+1}, B_{2j}, B_{2j-1})$如果用无符号解释，取值为$0\sim7$。而在Booth编码中，$B_{2j+1}$被当作"负权"位（权重$-2$），$B_{2j}$和$B_{2j-1}$为正权位（权重$+1$），所以$d_j = -2B_{2j+1} + B_{2j} + B_{2j-1}$。验证几个例子：$(1,0,0) \to -2+0+0 = -2$，$(0,1,1) \to 0+1+1 = +2$，$(1,1,1) \to -2+1+1 = 0$。

基-4 Booth编码：每3位（重叠1位）产生一个部分积系数

基-4 Booth编码将64位乘数的部分积行数从64减少到33行（包括一行用于符号校正），减少了近50%。

Booth编码的工作实例

让我们用一个具体的8位乘法例子来演示Booth编码的完整过程。计算$A \times B$，其中$A = 13_{10} = 00001101_2$，$B = 11_{10} = 00001011_2$。期望结果为$143_{10} = 0000000010001111_2$。

第一步：对乘数$B$进行Booth编码。$B = 00001011$，补充$B_{-1} = 0$：

组号$j$	$B_{2j+1}$	$B_{2j}$	$B_{2j-1}$	系数$d_j$
0	$B_1=1$	$B_0=1$	$B_{-1}=0$	$-2+1+0 = -1 \to -1 \times A$
1	$B_3=1$	$B_2=0$	$B_1=1$	$-2+0+1 = -1 \to -1 \times A$
2	$B_5=0$	$B_4=0$	$B_3=1$	$0+0+1 = +1 \to +1 \times A$
3	$B_7=0$	$B_6=0$	$B_5=0$	$0+0+0 = 0 \to 0 \times A$

验证：$d_0 \cdot 4^0 + d_1 \cdot 4^1 + d_2 \cdot 4^2 + d_3 \cdot 4^3 = (-1) \cdot 1 + (-1) \cdot 4 + 1 \cdot 16 + 0 \cdot 64 = -1 - 4 + 16 = 11 = B$。正确。

第二步：生成部分积。$A = 00001101 = 13$。

• $PP_0 = d_0 \times A \times 2^0 = (-1) \times 13 = -13$，对齐到位0。

• $PP_1 = d_1 \times A \times 2^2 = (-1) \times 13 \times 4 = -52$，对齐到位2。

• $PP_2 = d_2 \times A \times 2^4 = (+1) \times 13 \times 16 = 208$，对齐到位4。

• $PP_3 = d_3 \times A \times 2^6 = 0$，可以忽略。

验证：$-13 + (-52) + 208 = 143$。正确！原来需要8行部分积，现在只需要3行非零部分积。

第三步：负部分积$-13$和$-52$在硬件中用补码表示。$-13$的8位补码为$11110011$，符号扩展到16位为$1111111111110011$。$-52$的16位补码对齐后为$1111111111001100$。这些补码表示的部分积被送入Wallace树进行压缩，最终相加得到$0000000010001111 = 143$。

这个例子清楚地展示了Booth编码的威力：通过允许负系数，部分积行数从8行降低到3行（非零行），而负数的处理仅需要XOR取反和最低位加1——这些都是极低开销的操作。

部分积的硬件生成

每个部分积$d_j \times A$的硬件实现非常高效：

• $0 \times A$：输出全零——直接用AND门清零，或者利用MUX选择零输入。

• $\pm 1 \times A$：输出$A$或$-A$。$-A$可以用XOR门实现按位取反（$\overline{A}$），然后在部分积矩阵的最低位加1来完成补码取反。

• $\pm 2 \times A$：输出$2A$或$-2A$。$2A$只是$A$左移1位——这是纯布线操作，不需要任何逻辑门。然后$-2A$同样用取反加1完成。

每个Booth编码器的关键路径延迟仅为2$\sim$3级门延迟（编码逻辑 + 条件取反的XOR），这一步远非乘法器的关键路径。

符号处理与扩展优化

Booth编码的一个重要优势是它天然支持有符号乘法。由于Booth编码使用冗余表示（包含负系数$-1$和$-2$），有符号数的二进制补码可以直接参与编码，不需要像无符号阵列乘法器那样做额外的符号扩展和校正。这对于RISC-V的MUL、MULH和MULHSU指令的统一实现非常有利。

对于无符号乘法（MULHU），需要在乘数最高位上方补一个0位作为符号位，确保最高组的Booth编码不产生负系数。这可能使部分积行数从$n/2$增加到$\lceil(n+1)/2\rceil$——对于64位，从32行增加到33行，对整体延迟几乎没有影响。

另一个重要的实现细节是符号扩展压缩。Booth编码产生的部分积中可能包含负值（当$d_j$为负时），需要进行符号扩展以确保正确对齐。朴素做法是将每个部分积符号扩展到128位，但这会在部分积矩阵中引入大量冗余的符号位。实际设计使用一种利用$\overline{S} \cdot 1\ldots1 = 1\ldots1\overline{S} - 1\ldots1$恒等式的技巧，将每行部分积的有效宽度从$2n$降低到$n+2$位左右，大幅减少需要压缩的位数。

Wallace树压缩：从O(n)到O(log n)

Booth编码将部分积从64行减少到33行，但这33行仍然需要累加为一个最终结果。如果逐行累加（33次加法），延迟仍然很高。Wallace树（1964年提出）使用树形压缩结构，将累加延迟从$O(n)$降低到$O(\log n)$。

压缩器：Wallace树的基本构件

Wallace树的核心构件是压缩器（compressor）。压缩器接收$m$个同权位的输入，产生少于$m$个输出（分布在不同权位上），且不丢失任何信息。

3:2压缩器就是一个全加器（FA）：接收3个同权位输入$(X_1, X_2, X_3)$，产生1个同权位输出$S$和1个高一位权的输出$C$。它的"压缩"作用是将3行减少到2行。

进位保留表示（Carry-Save representation）是理解压缩器的关键概念。在标准二进制中，一个$n$位数用$n$位表示；在进位保留表示中，一个数用两行（和行$S$和进位行$C$）来表示，其值为$S + 2C$（$C$的权重比$S$高一位）。进位保留表示的核心优势是：将两个进位保留数相加只需要一级3:2压缩器的延迟（$O(1)$），而不需要进位传播——因为结果仍然是进位保留形式。只有在最后需要得到标准二进制结果时，才需要一次完整的进位传播加法。

整个Wallace树的工作过程可以这样理解：初始的33行部分积可以看作33个"标准二进制数"（每个数代表一行部分积）。每一级压缩将若干行合并，输出仍然是进位保留形式（和行+进位行）。经过多级压缩后，最终只剩下2行——一个进位保留表示的数——然后用一个快速加法器将其转换为标准二进制。

4:2压缩器更加重要。它接收4个同权位输入加1个进位输入$C_\mathrm{in}$，产生1个同权位输出$S$、1个高一位权输出$C$和1个进位输出$C_\mathrm{out}$。它将4行压缩为2行。

3:2压缩器和4:2压缩器的结构比较

4:2压缩器的门级实现

4:2压缩器最简单的实现是将两个全加器级联：第一个FA接收$X_1, X_2, X_3$，产生中间和$S_1$和中间进位$C_1$；第二个FA接收$S_1, X_4, C_\mathrm{in}$，产生最终和$S$和最终进位$C$。而$C_\mathrm{out}$取自第一个FA的进位输出$C_1$。

为什么$C_\mathrm{out}$可以取自第一个FA？因为数值上$(X_1 + X_2 + X_3 + X_4 + C_\mathrm{in})$的和最大为5，用二进制表示为$101_2$，所以$C$（权$2^{i+1}$）和$C_\mathrm{out}$（权$2^{i+1}$）不可能同时为1的同时$S$也为1——更准确地说，$2C + S + 2C_\mathrm{out} = X_1 + X_2 + X_3 + X_4 + C_\mathrm{in}$始终成立。

这个级联实现的延迟是两个FA的延迟之和，约4级门延迟。但存在更优的专用4:2压缩器电路，利用XOR门的传播特性，可以将延迟降低到约3级门延迟。其关键思路是将内部结构重新排列为：

$$\begin{aligned} T &= X_1 \oplus X_2 \oplus X_3 \oplus X_4 \\ S &= T \oplus C_\mathrm{in} \\ C_\mathrm{out} &= (X_1 \oplus X_2) \mathrel{?} X_3 : X_1 \quad \text{（MUX形式）} \\ C &= T \mathrel{?} C_\mathrm{in} : X_4 \quad \text{（MUX形式）} \end{aligned}$$

这个实现中，$T$的4输入XOR需要2级门延迟，然后$S$和$C$各需要1级MUX延迟，总共3级。$C_\mathrm{out}$与$T$并行计算（仅需2级门延迟），不在关键路径上。

4:2压缩器中$C_\mathrm{out}$的水平传播

4:2压缩器中一个至关重要的设计细节是：$C_\mathrm{out}$是向同一行相邻列（即同一级压缩中右边一列的$C_\mathrm{in}$）传播的进位，而不是向下一级压缩传播。这意味着$C_\mathrm{out}$到$C_\mathrm{in}$的连接是水平的，不增加压缩树的层级深度。

如果$C_\mathrm{out}$像行波进位那样纵向传播到下一级，压缩树就会退化为阵列结构，失去$O(\log n)$的优势。水平传播是Wallace树能够实现对数级压缩的关键保证。

在物理实现中，同一行相邻列之间的水平连线很短（仅相隔一个位位置的距离），因此$C_\mathrm{out}$到$C_\mathrm{in}$的传播延迟可以忽略不计——它被下一级压缩器的逻辑延迟完全掩盖。

Wallace树的压缩过程

Wallace树的工作方式是反复将多行部分积通过压缩器减少行数，直到只剩下2行为止。每一级压缩中：

• 使用3:2压缩器时，$m$行变成$\lceil 2m/3 \rceil$行（每3行变2行，剩余的行直通）。

• 使用4:2压缩器时，$m$行变成$\lceil m/2 \rceil + (m \mod 2)$行（每4行变2行）。

从33行部分积开始（Booth编码后的64位乘法），使用混合的3:2和4:2压缩器，压缩过程如图图 30.10所示。

33行部分积的Wallace树压缩过程：7级压缩将33行减少为2行

为什么是$O(\log n)$级

让我们严格推导Wallace树的级数。假设使用3:2压缩器，每一级将$m$行压缩为$\lceil 2m/3 \rceil$行。设$f(m)$为将$m$行压缩到2行所需的级数。有递推关系：

$$f(m) = 1 + f(\lceil 2m/3 \rceil), \quad f(2) = 0$$

设经过$k$级后剩余行数为$m_k$，则$m_k \leq (2/3)^k \cdot m_0$。令$m_k \leq 2$解出$k$：

$$(2/3)^k \cdot m_0 \leq 2 \implies k \geq \log_{3/2}(m_0/2) = \frac{\ln(m_0/2)}{\ln(3/2)} \approx 2.41 \ln(m_0)$$

对于$m_0 = 33$：$k \geq \log_{3/2}(33/2) \approx \log_{3/2}(16.5) \approx 6.9$，即需要7级3:2压缩。使用4:2压缩器时，每级将行数减半，级数为$\lceil\log_2(m_0/2)\rceil \approx 4$级，但每级4:2压缩器的延迟（3级门延迟）比3:2压缩器（2级门延迟）更大。实际设计中通常混合使用两种压缩器，总延迟约为7级CSA延迟。

Wallace树 vs. Dadda树

与Wallace树密切相关的另一种压缩方案是Dadda树（1965年提出）。两者的区别在于压缩策略：

• Wallace树在每一级中"尽可能多地压缩"——使用尽可能多的压缩器将行数减少到最小。

• Dadda树在每一级中"只压缩到下一个目标行数"——目标行数序列为$2, 3, 4, 6, 9, 13, 19, 28, 42, \ldots$（每个目标是前一个的$3/2$倍取整）。Dadda树只压缩到让行数不超过序列中的下一个值，不做多余的压缩。

Dadda树的优势是在相同的压缩级数下，使用更少的压缩器（因为它不做"过度压缩"）。对于33行部分积，Wallace树和Dadda树都需要7级压缩（目标序列为$33 \to 22 \to 15 \to 10 \to 7 \to 5 \to 4 \to 2$对应Dadda目标$28, 19, 13, 9, 6, 4, 3, 2$），但Dadda树在每一级使用的压缩器数量可能更少。

代价是Dadda树的最终两行可能不够"规整"——Wallace树的最终两行通常高度对齐（方便最终加法器处理），而Dadda树的最终两行可能有更多的位不对齐，需要稍长的最终加法器。在实践中两者差异不大，但大多数商用处理器更倾向于使用规整化的Wallace树结构。

规整化Wallace树与4:2压缩器阵列

纯Wallace树的一个实际问题是其不规整性——不同列的压缩器数量不同（中间列的部分积较多，边缘列较少），导致布局不规整，对EDA工具不友好。

一种广泛使用的替代方案是4:2压缩器阵列：将所有列统一使用4:2压缩器，每一级将4行压缩为2行。对于不足4行的位置使用3:2压缩器或直通。这种"列统一"的结构虽然可能比纯Wallace树多使用一些压缩器，但布局极其规整——所有列的结构相同，非常适合标准单元自动布局。

对于33行部分积，使用4:2压缩器阵列的压缩过程为：

$33 \xrightarrow{\text{8个4:2+1个pass}} 17 \xrightarrow{\text{4个4:2+1个pass}} 9 \xrightarrow{\text{2个4:2+1个pass}} 5 \xrightarrow{\text{1个4:2+1个pass}} 3 \xrightarrow{\text{1个3:2}} 2$

共需5级压缩（每级3级门延迟），总压缩延迟约15级门延迟——略多于最优Wallace树，但布局友好性大幅提升。在实际的ASIC设计中，这种规整化方案往往能获得更好的物理实现结果（更低的实际延迟和更小的面积），因为EDA工具对规整结构的优化效果更好。

完整的64位乘法器流水线设计

延迟分析

一个完整的64位乘法器（Booth编码 + Wallace树 + 最终加法器）的延迟分解如下：

性能分析 4 — 64位乘法器的延迟分析

1. Booth编码与部分积生成：$\approx 3$级门延迟（编码逻辑 + 条件取反/移位）。

2. Wallace树压缩：$\approx 7$级CSA延迟。如果使用4:2压缩器，每级约3级门延迟，总共$\approx 21$级门延迟。如果混合使用3:2和4:2压缩器，可以优化到$\approx 17$级门延迟。

3. 最终加法器：$\approx 14$级门延迟（128位Kogge-Stone或Han-Carlson加法器，位宽加倍使级数增加1）。

总延迟：$3 + 17 + 14 = 34$级门延迟。以7 nm工艺中每级15 ps计算：

$$T_\mathrm{MUL} \approx 34 \times 15\,\text{ps} = 510\,\text{ps}$$

在5 GHz处理器（周期200 ps）中，乘法器需要约2.5个时钟周期的延迟。因此，乘法器通常被流水线化为3级——每级约170 ps，留有一定的裕量。

3级流水线划分

典型的3级乘法流水线将计算分为以下阶段：

1. MUL1——Booth编码与初步压缩：对乘数进行Booth编码，生成33行部分积，并完成前3$\sim$4级Wallace树压缩（33行$\to$10行左右）。

2. MUL2——Wallace树压缩主体：完成剩余的Wallace树压缩，将部分积减少到2行（进位保留形式）。

3. MUL3——最终加法：使用高速加法器将2行压缩结果相加，产生最终的128位乘积。

3级流水线乘法器

流水线化后，乘法指令的延迟（latency）为3个时钟周期，但吞吐量（throughput）为每周期1条乘法指令——即每个时钟周期可以接受一条新的乘法指令，3个周期后输出结果。对于指令调度器而言，乘法指令需要在3个周期后才能唤醒依赖指令。

流水线寄存器的数据量

MUL1和MUL2之间的流水线寄存器需要存储中间压缩结果。如果MUL1将33行压缩到10行，每行约128位，则流水线寄存器需要$10 \times 128 = 1280$位——这是一笔不小的存储开销。减少MUL1的压缩级数（留更多给MUL2）可以减少流水线寄存器宽度，但可能导致MUL2的延迟增加。实际设计中需要仔细平衡各级的延迟和流水线寄存器的面积。

在一些超标量处理器中，乘法器的流水线会更深（4$\sim$5级），以获得更高的工作频率。典型的商用处理器乘法器延迟：

• Intel Skylake：整数乘法3周期延迟、1周期吞吐量。

• ARM Cortex-A77：整数乘法3周期延迟、1周期吞吐量。

• AMD Zen 4：整数乘法3周期延迟、1周期吞吐量。

乘累加单元

乘累加（Multiply-Accumulate, MAC）操作计算$R = A \times B + C$，在数字信号处理和机器学习推理中极为常见。如果将MAC分解为一次乘法和一次加法分别执行，至少需要4个周期（3周期乘法 + 1周期加法），且中间结果需要写回寄存器文件再读出。

融合MAC通过一个巧妙的观察来避免这一额外开销：Wallace树本来就在压缩多行部分积，将被加数$C$作为第34行部分积加入Wallace树的输入即可。由于33行和34行需要的压缩级数相同（都需要7级），融合MAC的延迟与普通乘法完全相同：

$$T_\mathrm{MAC} = T_\mathrm{MUL} \quad \text{（融合实现，零额外延迟）}$$

硬件开销极小：仅需在Wallace树的输入端增加$C$的接入路径和少量控制逻辑。RISC-V的V扩展（Vector）中大量使用MAC操作，融合MAC单元是高效实现的关键。

完整的64位乘法器架构

让我们将前面讨论的所有技术综合起来，描述一个完整的64位整数乘法器的架构。

案例研究 1 — 64位整数乘法器设计实例

以下是一个典型的高性能64位整数乘法器的完整设计参数：

部分积生成阶段：

• 使用基-4 Booth编码，从64位乘数$B$（加上$B_{-1}=0$和高位符号扩展位）生成33行部分积。

• 每行部分积宽度为66位（64位被乘数 + 1位Booth移位 + 1位符号位）。

• 使用符号扩展压缩技术，每行的有效宽度降低到66位，避免128位全宽扩展。

• 对于负部分积（$d_j < 0$），取反后在最低有效位注入一个"1"（完成补码），这个注入的"1"作为Wallace树的额外输入行处理。

• 总延迟：约3级门延迟（Booth编码逻辑 + MUX选择$\{0, \pm A, \pm 2A\}$）。

部分积压缩阶段：

• 使用4:2压缩器为主的规整化Wallace树结构。

• 第一流水级（MUL1）完成前3级4:2压缩：$33 \to 17 \to 9 \to 5$行。延迟约$3 \times 3 = 9$级门延迟。

• 第二流水级（MUL2）完成后2级压缩：$5 \to 3 \to 2$行。延迟约$2 \times 3 = 6$级门延迟。

• MUL1与MUL2之间的流水线寄存器存储5行$\times$128位 = 640位中间结果。

最终加法阶段：

• 第三流水级（MUL3）使用128位Han-Carlson加法器将2行压缩结果相加。

• 加法器级数：$\lceil\log_2 128\rceil + 1 = 8$级前缀运算。

• 总延迟：约$1 + 8 \times 2 + 1 = 18$级门延迟（使用简单门延迟模型），实际使用Ling优化后约12$\sim$14级。

符号处理：

• MUL/MULH（有符号$\times$有符号）：操作数直接参与Booth编码，无需预处理。

• MULHU（无符号$\times$无符号）：两个操作数都在最高位上方补0，确保Booth编码不产生负的最高组系数。

• MULHSU（有符号$\times$无符号）：被乘数$A$保持原样（有符号），乘数$B$在最高位上方补0。

• 三种乘法共享同一套硬件，仅在操作数预处理（补0或符号扩展）上有差异。

面积与功耗：

• 33个Booth编码器：每个约20个门，共约660个门。

• 33行$\times$66列部分积生成（MUX/XOR）：约4400个门。

• Wallace树压缩器：约5000个全加器和4:2压缩器。

• 128位最终加法器：约600个门。

• 流水线寄存器：约1800个触发器。

• 总计约15000$\sim$20000个等效门（不含流水线寄存器），约为一个64位ALU的5$\sim$8倍。

除法器：迭代算法与商选择表

除法是整数运算中延迟最高、吞吐量最低的操作。与加法（1周期）和乘法（3周期）不同，除法通常需要数十个周期才能完成。RISC-V的DIV和REM指令在64位操作数上的典型延迟为20$\sim$40个周期。

除法如此之慢的根本原因是其本质上的串行性：每一步需要将部分余数与除数比较，根据比较结果决定商的当前位，然后更新余数。而下一步的比较依赖于上一步更新后的余数——这个"比较$\to$决策$\to$更新"的循环无法像乘法的Wallace树那样被并行化。

恢复余数除法

恢复余数除法（Restoring Division）是最基本的除法算法，直接模拟手算长除法。

$R \leftarrow D$

恢复余数除法的每一步需要一次减法（试商）、一次符号判断（检查余数是否为负）和可能的一次加法（恢复余数）。在最坏情况下（商位交替为0和1时），每步需要两次加法器操作。对于64位除法，总延迟约为$128 \times t_\mathrm{adder}$——在5 GHz处理器中约需128个时钟周期，完全不实用。

不恢复余数除法

恢复余数除法的一个明显低效之处是"恢复"步骤：当试商失败（$R < 0$）时，需要加回除数。不恢复余数除法（Non-Restoring Division）的关键洞察是：恢复是不必要的。如果当前步余数为负，可以在下一步中加上除数（而不是减去），效果等价于先恢复再减去。

$R \leftarrow D$

不恢复余数除法每步恰好需要一次加法/减法操作（通过加法器的减法模式切换实现），消除了恢复步骤。每步延迟固定为一次加法器延迟，总共需要$n$步迭代。对于64位除法，延迟约为64个时钟周期——仍然很慢，但比恢复余数除法好了一倍。

让我们用一个小例子来追踪不恢复余数除法的执行过程，以建立直觉。

性能分析 5 — 不恢复余数除法的工作实例

计算$D = 7 \div d = 3$。使用4位操作数（$n=4$）。

设$D = 0111_2 = 7$，$d = 0011_2 = 3$。被除数扩展为8位：$R = 00000111$。除数左对齐：$d \cdot 2^4 = 00110000$。

步骤	操作	$R$（二进制）	$R \geq 0$?	$Q_i$
初始	—	$00000111$	是	—
$i=3$	$2R - d' = 00001110 - 00110000$	$11011110$	否	$Q_3 = 0$
$i=2$	$2R + d' = 10111100 + 00110000$	$11101100$	否	$Q_2 = 0$
$i=1$	$2R + d' = 11011000 + 00110000$	$00001000$	是	$Q_1 = 1$
$i=0$	$2R - d' = 00010000 - 00110000$	$11100000$	否	$Q_0 = 0$

商的初步结果为$Q = 0010_2 = 2$。最终余数$R < 0$，需要校正：$R = 11100000 + 00110000 = 00010000$，$Q = 2 - 1 = 1$。

等等，这似乎不对——$7 \div 3$的商应该是2，余数1。问题出在非恢复余数除法的商编码上：$Q_i = 0$实际代表的是$q_i = -1$（而非0），$Q_i = 1$代表$q_i = +1$。重新解读：$q = (-1, -1, +1, -1)$，商值为$(-1) \cdot 8 + (-1) \cdot 4 + 1 \cdot 2 + (-1) \cdot 1 = -8 - 4 + 2 - 1 = -11$。

这说明非恢复除法的商需要从$\{-1, +1\}$编码转换为标准二进制。正确的转换方法是：正商位集合表示的值$Q^+ = 0010 = 2$，负商位集合的值$Q^- = 1101 = 13$，最终商$= Q^+ - Q^-$在模16下...实际操作中直接用on-the-fly转换更为简便。

最终结果：商$Q = 2$，余数$R = 1$。验证：$3 \times 2 + 1 = 7$。正确。

这个例子虽然简单，但展示了非恢复余数除法中的一个重要复杂性：商位的$\{0, 1\}$编码与实际的$\{-1, +1\}$含义之间的转换。这也是SRT除法引入显式冗余表示$\{-1, 0, +1\}$的动机之一——显式表示更清晰，避免了编码转换的混乱。

SRT除法：冗余表示的威力

SRT除法（以发明者Sweeney、Robertson、Tocher命名）使用冗余数字表示来进一步加速除法。这与Booth编码使用冗余表示来减少部分积是同一种思想——在不同的算术运算中有着惊人的一致性。

从不恢复除法到SRT的关键改进

不恢复余数除法的瓶颈在于：每步迭代的关键路径包括"加法器$\to$符号判断$\to$加减选择$\to$加法器"的循环。特别是，符号判断需要等待加法器完成——因为只有知道新余数的符号，才能决定下一步是加还是减。

SRT除法的核心改进是：允许商位取值为$\{-1, 0, +1\}$（而不是$\{0, 1\}$），使用冗余表示。冗余表示的关键好处是：商位的选择不再需要精确知道余数的值——只需要检查部分余数的高几位（3$\sim$4位）就能做出正确的（或至少"可接受的"）商选择。

为什么冗余表示能够放松精度要求？直觉是这样的：在传统的$\{0, 1\}$商表示中，商位选择没有"回旋余地"——选0和选1之间没有中间地带，必须精确判断余数与除数的大小关系。而在$\{-1, 0, +1\}$冗余表示中，"0"这个选项提供了一个"安全区域"：当余数接近零时（既不明显大于除数也不明显小于零），选择$q_i = 0$（不做加减，只左移）总是安全的。这意味着我们不需要精确的比较结果，只需要余数的大致范围就够了——而大致范围可以从余数的高几位快速获得。

SRT商选择的形式化

设除数为$d$（已归一化到$[1/2, 1)$区间），部分余数为$R$。SRT除法的每步迭代为：

$$R_{j+1} = r \cdot R_j - q_j \cdot d$$

其中$r$是基数（基-2 SRT中$r=2$），$q_j$是当前步选择的商位。

SRT除法的正确性条件是部分余数$R_j$必须始终保持在一个有界范围内：

|R_j| < \frac{\rho \cdot d}{r-1}$$ 其中$\rho$是冗余因子，定义为商位集合的最大绝对值除以$(r-1)$。对于基-2 SRT，商位集为$\{-1, 0, +1\}$，$\rho = 1/(2-1) = 1$，所以$|R_j| < d$。 商选择规则为： - 如果$R_j$的高几位表明$R_j \geq d/2$：选择$q_j = +1$，执行$R_{j+1} = 2R_j - d$。 - 如果$R_j$的高几位表明$-d/2 \leq R_j < d/2$：选择$q_j = 0$，执行$R_{j+1} = 2R_j$。 - 如果$R_j$的高几位表明$R_j < -d/2$：选择$q_j = -1$，执行$R_{j+1} = 2R_j + d$。 关键在于：这些范围之间有<strong>重叠</strong>（例如在$R_j$接近$d/2$附近，选$+1$或$0$都可以），这种重叠就是商选择的"容错空间"。正是这种容错性，使得我们不需要精确的比较——只看高几位的近似值就足够在重叠区域内做出正确选择。 #### 商选择表（QDS Table）的构造 {#sec:30-qds-table} 商选择逻辑在硬件中通常通过一个<strong>查找表</strong>（称为QDS Table——Quotient Digit Selection Table）实现。查找表的输入是部分余数的高$t$位（截断近似值$\hat{R}$）和除数的高几位，输出是商位$q_j$。 构造QDS表的过程如下： 1. 对于每种可能的除数值（由除数的高几位确定），计算商位从$+1$到$0$和从$0$到$-1$的<strong>切换边界</strong>。 2. 切换边界由SRT正确性条件[式 (30.17)](/part5/ch30#eq:ch30-srt-bound)确定：对于基-2 SRT，选择$q_j = +1$的条件是$R_{j+1} = 2R_j - d$后$|R_{j+1}| < d$，即$2R_j - d < d$且$2R_j - d > -d$，化简得$0 < R_j < d$。选择$q_j = 0$的条件是$|2R_j| < d$，即$-d/2 < R_j < d/2$。 3. 在重叠区域$[0, d/2)$中，$q_j = +1$和$q_j = 0$都可以选择。查找表可以在这个区域中选择任一值——但<strong>必须对所有截断值$\hat{R}$一致地做出选择</strong>。 4. 将截断近似值$\hat{R}$的每种可能取值映射到对应的商位，形成查找表。 QDS表的大小取决于余数截断位数$t$和除数参考位数。对于基-4 SRT除法（$r=4$，商位集$\{-2, -1, 0, +1, +2\}$），典型的QDS表约有几百到一千多个表项，用PLA（可编程逻辑阵列）或ROM实现。 #### P-D图：可视化商选择区域 {#sec:30-pd-diagram} 理解QDS表的直观工具是<strong>P-D图</strong>（Partial remainder - Divisor diagram），也称为Robertson图。P-D图以除数$d$为横轴、部分余数$R$为纵轴，在二维平面上划分出每个商位值的<strong>合法选择区域</strong>。 对于基-2 SRT（$r=2$，商位集$\{-1, 0, +1\}$），设除数$d$归一化到$[1/2, 1)$区间。三个商位的合法区域由SRT约束条件确定： - 选择$q_j = +1$的条件：执行$R_{j+1} = 2R_j - d$后，$|R_{j+1}| \leq d$。即$-d \leq 2R_j - d \leq d$，化简得$0 \leq R_j \leq d$。 - 选择$q_j = 0$的条件：执行$R_{j+1} = 2R_j$后，$|R_{j+1}| \leq d$。即$-d \leq 2R_j \leq d$，化简得$-d/2 \leq R_j \leq d/2$。 - 选择$q_j = -1$的条件：执行$R_{j+1} = 2R_j + d$后，$|R_{j+1}| \leq d$。即$-d \leq 2R_j + d \leq d$，化简得$-d \leq R_j \leq 0$。 在P-D图上，$q_j = +1$的合法区域是$0 \leq R \leq d$围成的区域，$q_j = 0$的合法区域是$-d/2 \leq R \leq d/2$，$q_j = -1$的合法区域是$-d \leq R \leq 0$。注意： - $q_j = +1$和$q_j = 0$的区域在$0 \leq R \leq d/2$处<strong>重叠</strong>。 - $q_j = 0$和$q_j = -1$的区域在$-d/2 \leq R \leq 0$处<strong>重叠</strong>。 这些重叠区域就是商选择的"容错空间"。在重叠区域内，选择相邻的任一商位值都是正确的——这正是SRT除法能够使用截断近似值$\hat{R}$代替精确$R$来做商选择的数学基础。只要截断误差不超过重叠区域的宽度，近似值就不会导致错误的商选择。 对于基-4 SRT，P-D图更为复杂：有5个商位值$\{-2, -1, 0, +1, +2\}$的区域，相邻区域之间都有重叠。重叠区域的宽度取决于冗余因子$\rho$的选择——$\rho$越大，重叠越宽，允许更粗糙的截断近似（更少的检查位数），但同时需要更复杂的除数倍数生成电路（因为商位的绝对值更大）。 QDS表的构造本质上就是在P-D图中，对于每种可能的截断值$\hat{R}$和除数参考值，确定它落在哪个商位的合法区域（或重叠区域）中，并分配一个确定的商位值。在重叠区域中，选择哪个值有一定自由度，但一旦选定就必须对该截断值$\hat{R}$<strong>一致</strong>——不能对同一个$\hat{R}$在不同的$d$值下做出矛盾的选择。 ::: tip 设计提示 QDS表的构造是SRT除法器设计中最容易出错的环节。表中<strong>每一个条目</strong>都必须满足SRT正确性条件——任何遗漏或错误都可能导致对特定操作数组合的计算结果不正确。这也是Intel Pentium FDIV Bug的根本原因。现代设计中，QDS表必须经过<strong>形式化验证</strong>（formal verification），用数学方法穷举证明所有可能的输入组合都能产生正确的商选择。 ::: #### SRT除法器的硬件结构 {#sec:30-srt-hw} <figure id="fig:ch30-srt-structure"><img src="/figures/ch30-fig12.svg" alt="SRT除法器的硬件结构" /><figcaption>SRT除法器的硬件结构</figcaption></figure> 图[图 30.12](/part5/ch30#fig:ch30-srt-structure)中，每步迭代的关键路径为：部分余数寄存器$\to$左移$\to$加法器$\to$回写余数寄存器。商选择逻辑（QDS查找表）只需要余数的高几位，可以在左移完成后<strong>立即</strong>开始工作，与加法器<strong>并行</strong>运行——它不需要等待加法器的完整结果。这种并行性是SRT除法器比不恢复余数除法更快的关键原因。 #### SRT迭代的详细时序分析 {#sec:30-srt-timing} 让我们仔细分析基-4 SRT除法器一步迭代的时序，理解为什么每步只需要一个时钟周期。 在时钟上升沿，部分余数$R_j$从寄存器输出。以下操作随即开始： <strong>路径A（关键路径）</strong>：$R_j$通过左移2位网络（纯布线，零延迟）得到$2R_j$或$4R_j$。然后$4R_j$进入加法器，与$q_j \cdot d$相减/加，得到新的部分余数$R_{j+1}$。$R_{j+1}$在下一个时钟上升沿被锁存。 路径A的延迟 = 左移(0) + MUX选择$q_j \cdot d$($t_\mathrm{MUX}$) + 加法器($t_\mathrm{add}$) + 寄存器建立时间($t_\mathrm{setup}$)。 <strong>路径B（商选择路径，与路径A并行）</strong>：$R_j$的高7位（截断值$\hat{R}$）和除数$d$的高5位同时送入QDS查找表。查找表输出商位$q_j$。$q_j$驱动MUX，选择$+2d$、$+d$、$0$、$-d$或$-2d$作为加法器的第二操作数。 路径B的延迟 = 截断(0) + QDS查找($t_\mathrm{QDS}$)。 关键约束是：<strong>路径B必须在路径A的加法器开始之前完成</strong>，因为加法器需要知道加什么（$q_j \cdot d$）。也就是说： $$t_\mathrm{QDS} \leq t_\mathrm{leftshift} + t_\mathrm{MUX\_setup}

由于左移是零延迟（纯布线），QDS查找表的延迟直接约束了迭代时间。在基-4 SRT中，QDS表的输入为12位（7位截断余数 + 5位除数参考），输出为3位（编码5种商位选择），可以用一个小型PLA在2$\sim$3级门延迟内完成——这远快于加法器的$O(\log n)$延迟，因此QDS查找不在关键路径上。

性能分析 6 — 基-4 SRT除法器每步迭代的时序分解

以64位操作数、5 GHz时钟（200 ps周期）为例：

操作	延迟	是否在关键路径上
寄存器$\to Q$延迟	20 ps	是
左移2位（布线）	0 ps	是
QDS查找表	40 ps	否（并行）
MUX选择$q_j \cdot d$	20 ps	是
加法器（64位CLA/前缀）	100 ps	是
寄存器建立时间	15 ps	是
关键路径总计	155 ps
时钟周期	200 ps
裕量	45 ps

每步迭代产生2位商，64位除法需要32步，总延迟为32个时钟周期。加上前处理（操作数归一化、前导零检测，约2周期）和后处理（商转换、余数校正，约2周期），总延迟约为36个时钟周期。

注意：如果加法器使用进位保留形式（CSA），每步加法的延迟可以从$O(\log n)$降低到$O(1)$（仅一级FA延迟），但代价是QDS查找需要处理进位保留形式的截断余数（需要一个小的进位传播加法器来计算高几位的精确值）。这种优化在现代高性能除法器中广泛使用。

Intel Pentium FDIV Bug：QDS表的致命遗漏

案例研究 2 — Intel Pentium FDIV Bug

1994年，Intel Pentium处理器的浮点除法单元被发现存在一个著名的硬件缺陷——FDIV Bug。这个缺陷的故事深刻地说明了QDS表构造的风险，值得详细讲述。

技术背景。Pentium的浮点除法器使用基-4 SRT算法（每步产生2位商），商选择表中有1066个有效表项。表的输入是部分余数的高7位（截断值）和除数的高5位，输出是商位$q_j \in \{-2, -1, 0, +1, +2\}$。

缺陷根因。在验证QDS表时，负责的工程师使用了一个数学论证：在SRT迭代过程中，部分余数的某些取值范围（对应于截断值$\hat{R}$的某些组合）在实际计算中"不可能出现"，因此对应的表项可以省略（设为"无关"项）。在1066个表项中，有5个被标记为"不可能出现"而被省略。

错误所在。这个"不可能出现"的论证是错误的。在极少数特定的操作数组合下（特别是除数的尾数具有某些特殊bit pattern时），部分余数确实会落入这些"不可能"的范围。当SRT除法器查询QDS表时，这些位置返回的是默认值0（即$q_j = 0$），而不是正确的$q_j = +1$或$q_j = +2$。

后果。选择了错误的商位后，部分余数偏离了正确范围。虽然后续迭代的商选择仍然是"局部正确的"（满足SRT约束），但由于初始偏差的累积，最终的商在低位上出现了微小的误差——典型情况下影响第9$\sim$19位有效数字。

例如，Thomas Nicely教授（发现该bug的数学家）计算$4{,}195{,}835 \div 3{,}145{,}727$时：

• 正确结果：$1.333820449136241...$

• Pentium结果：$1.333739068902037...$

• 误差出现在第4位有效数字。

教训。

1. SRT除法的正确性完全依赖于QDS表的完整性——每一个可能的输入组合都必须映射到正确的商位。"不可能出现"的假设必须经过严格证明。

2. 形式化验证对于除法器等关键算术单元至关重要。后来Intel为SRT除法器开发了专门的形式化验证方法，用定理证明器穷举检查所有$2^{12}$种可能的表输入。

3. 该缺陷最终导致Intel花费约4.75亿美元召回处理器。这是芯片行业历史上最昂贵的单一硬件缺陷，也推动了形式化验证方法在工业界的广泛应用。

高基数SRT除法

基-2 SRT除法每步只产生1位商，64位除法仍需64步。高基数SRT除法通过每步产生多位商来减少迭代次数。

基-4 SRT除法

基-4 SRT除法（$r=4$）每步产生2位商，使用冗余商集$\{-2, -1, 0, +1, +2\}$。64位除法只需32步迭代——迭代次数减半。

代价是商选择逻辑更复杂：QDS表需要检查部分余数的更多高位（通常5$\sim$7位）以及除数的高位（3$\sim$5位），表项数量从百量级增长到千量级。但这种复杂度增加是一次性的（更大的PLA/ROM），不会增加每步迭代的延迟——因为QDS查找与加法器并行工作。

基-16与重叠迭代

理论上可以使用基-16（每步4位商）甚至更高基数，但有一个严峻的实际问题：基-16 SRT的每步需要从$\{+8, +7, \ldots, -7, -8\}$这17个候选中选择商位，QDS表极其庞大。更关键的是，每步的加法器需要处理$8d$的倍数——而$8d = 2^3 d$需要3位左移，这本身不难，但$7d$、$5d$等奇数倍需要额外的加法来预计算，增加了延迟。

一种变通方案是重叠迭代（overlapping stages）：使用两个基-4 SRT阶段串行连接，每步产生4位商（等效于基-16），但商选择复杂度保持在基-4水平。这种设计在现代高性能处理器中较为常见。

性能分析 7 — 不同除法算法的延迟比较

以64位除法为例，假设单步迭代的加法器延迟可在1个时钟周期内完成：

除法算法	每步商位数	迭代次数	典型延迟（周期）
恢复余数	1位	64	64$\sim$128
不恢复余数	1位	64	64
基-2 SRT	1位	64	50$\sim$64
基-4 SRT	2位	32	32$\sim$40
基-16 SRT（重叠）	4位	16	20$\sim$30

现代高性能处理器通常使用基-4 SRT除法，64位整数除法的延迟在20$\sim$40个周期之间。

商的On-the-Fly转换

SRT除法产生的商是冗余表示（包含$-1$和$-2$等负数字位），最终需要转换为标准二进制。传统方法是在所有迭代完成后执行一次减法（正商位序列减去负商位序列），但这需要额外的加法器延迟。

On-the-Fly转换是一种更优雅的方案。它在每步迭代中递增地维护两个寄存器$Q^+$和$Q^-$：

• $Q^+$：假设当前步及后续步不产生负修正时的商值。

• $Q^-$：假设需要负修正时的商值（$= Q^+ - 1$ 在当前已产生的最低有效位上）。

每步迭代中，根据商位$q_j$的符号，选择更新$Q^+$和$Q^-$中的一个。在最后一步迭代结束时，直接输出$Q^+$或$Q^-$作为最终二进制商——不需要任何后处理加法。

On-the-Fly转换的硬件开销仅为两个$n$位寄存器和少量MUX逻辑，延迟开销为零（因为它与每步的加法器并行工作）。

除法的非阻塞实现与提前终止

除法指令的长延迟（20$\sim$40周期）使其成为处理器设计中的一个特殊挑战。现代处理器通过以下机制来缓解影响：

非阻塞执行

1. 独立的除法功能单元：除法器与ALU和乘法器物理分离，不占用ALU或乘法器的执行资源。其他指令可以在除法执行期间正常运行。

2. 不可流水线化：由于每步迭代依赖上一步的结果，除法器无法被流水线化。当一条除法指令正在执行时，新的除法指令必须在发射队列中等待。

3. 乱序执行的天然掩盖：在乱序处理器中，除法的长延迟被部分掩盖——处理器继续执行其他不依赖除法结果的指令。发射队列中的就绪指令不受影响。

提前终止

许多除法器支持提前终止（Early Termination），当检测到部分余数为零（所有有效位为零）时提前结束迭代。例如$100 \div 10$的实际迭代次数远少于64次。

更精细的优化是操作数预处理：通过前导零检测（Leading Zero Count, LZC），确定被除数和除数的有效位宽$w_D$和$w_d$。商最多只有$w_D - w_d + 1$位，可以跳过不必要的迭代。当$w_D \ll n$时（例如小整数除法），这可以将延迟从数十周期降低到个位数。

基于乘法的除法：Newton-Raphson方法

除了SRT等迭代减法方案外，还存在一种完全不同的除法实现思路：将除法转化为乘法。Newton-Raphson方法（也称为Goldschmidt方法的变体）利用乘法器来迭代逼近除数的倒数$1/d$，然后将被除数乘以$1/d$得到商。

Newton-Raphson迭代

求$1/d$等价于求方程$f(x) = 1/x - d = 0$的根。Newton-Raphson迭代公式为：

$$x_{i+1} = x_i \cdot (2 - d \cdot x_i)$$

每步迭代需要两次乘法和一次减法（$2 - d \cdot x_i$的减法可以用按位取反实现，因为$2$在浮点表示中只是指数位变化）。关键性质是二次收敛：如果$x_i$有$p$位精度，则$x_{i+1}$有$2p$位精度。这意味着：

• 从一个8位精度的初始近似值$x_0$出发（可以用小型查找表获得）。

• 经过1次迭代得到16位精度。

• 经过2次迭代得到32位精度。

• 经过3次迭代得到64位精度——足以计算64位整数除法。

总共只需要3次迭代，每次迭代需要2次乘法（约6个周期），总延迟约为$3 \times 6 = 18$个周期——与基-4 SRT除法的延迟相当，但有一个重要的区别：Newton-Raphson方法复用了已有的乘法器硬件，不需要专门的除法器电路。

Newton-Raphson的利弊

• 优点：不需要专用的除法器硬件（复用乘法器），面积节省显著。二次收敛使迭代次数极少。

• 缺点：(1) 在迭代期间占用乘法器，阻塞其他乘法指令。(2) 初始近似值需要查找表（约256项的ROM）。(3) 精确的舍入控制比SRT更复杂——IEEE 754要求除法结果正确舍入到最后一位，而Newton-Raphson的逼近结果可能需要额外的修正步骤。(4) 余数的获取需要额外一次乘法（$R = D - Q \times d$）。

在整数除法的场景下，由于精度和余数的要求，Newton-Raphson通常不如SRT直接。但在浮点除法中，Newton-Raphson（或Goldschmidt变体）被广泛使用——AMD的某些处理器使用Goldschmidt算法实现浮点除法和平方根。对于整数除法，大多数高性能处理器仍然使用基-4 SRT方案。

硬件描述 4 — 除法器的微架构集成

在超标量处理器中，除法器的微架构集成需要注意以下几点：

1. 发射端口分配：除法指令通常与乘法指令共享同一个发射端口，因为它们不会同时需要高吞吐量。但除法器和乘法器内部是独立的硬件电路。

2. 结果总线仲裁：除法完成时间不固定（取决于操作数），结果总线仲裁逻辑需要处理除法结果与固定延迟指令结果之间的冲突。通常采用优先级机制：除法的优先级低于ALU（因为ALU的结果总线占用时间是固定可预测的）。

3. 唤醒时机：由于除法延迟不固定，处理器通常在除法完成前1$\sim$2个周期才唤醒依赖指令，而不是在发射时就推测唤醒。

4. 除以零检测：除以零异常可以在除法开始前检查（检查除数是否为零），不需要等到迭代过程中才发现。RISC-V规定DIV除以零返回$-1$，REM除以零返回被除数——不产生异常。

设计权衡 2 — 除法器的设计权衡

除法器面临一个独特的设计困境：它的使用频率很低（在典型整数工作负载中，除法指令只占总指令数的1%$\sim$3%），但延迟很高。这导致了以下权衡：

• 低面积 vs. 低延迟：使用更高基数的SRT除法器可以降低延迟，但增加了QDS表的面积和复杂度。对于频率只有1%的操作，投入大量面积优化延迟是否值得？

• 专用单元 vs. 复用ALU：某些低端处理器让除法复用ALU的加法器（每周期执行一步迭代），节省了面积但在除法执行期间ALU被占用。高性能处理器使用专用除法单元，保证ALU不被阻塞。

• 硬件除法 vs. 软件模拟：在面积极度受限的嵌入式处理器中，甚至可以不实现硬件除法器，而通过trap到软件除法例程来完成。RISC-V的M扩展是可选的，允许不支持硬件除法。

AGU：地址生成的专用加法器

地址生成单元（Address Generation Unit, AGU）是负责计算Load和Store指令的内存地址的专用功能单元。在RISC-V中，所有Load/Store指令使用"base + offset"寻址模式：

$$\text{EA} = R[\text{rs1}] + \text{sign\_extend}(\text{imm})$$

其中EA是有效地址（Effective Address），$R[\text{rs1}]$是基址寄存器的值，imm是符号扩展后的12位立即数偏移。

AGU的设计约束

从计算角度看，AGU本质上就是一个加法器。但它与ALU中的加法器在设计约束上有重要区别，这些区别决定了AGU需要不同的优化策略。

更紧的延迟预算

AGU的输出（有效地址）直接驱动TLB查找和D-Cache访问。在很多高性能设计中，地址计算和TLB查找被安排在同一个时钟周期内完成（或紧密相连的两个半周期）。这意味着AGU加法器的延迟预算只有时钟周期的50%$\sim$60%——在5 GHz处理器中约为100$\sim$120 ps，相当于7$\sim$8级门延迟。这比ALU加法器的延迟预算更紧。

偏移量的特殊性

RISC-V的Load/Store偏移量只有12位（$-2048 \sim +2047$），而基址是64位。这意味着地址加法的两个操作数高度不对称：一个是64位全宽，另一个只有12位有效位（高52位只是符号扩展）。

这种不对称性提供了优化机会：高52位的加法只有三种可能的结果——基址的高52位不变（偏移量对高位无影响）、加1（低位产生了进位）、减1（减法借位，即偏移量为负且低位不够减）。

多个AGU实例

现代超标量处理器通常有2$\sim$3个AGU实例（支持每周期2$\sim$3条Load/Store指令），每个AGU都需要独立的加法器。因此AGU加法器的面积比ALU加法器更受关注——乘以2$\sim$3倍后，AGU加法器的总面积可能超过ALU加法器。

推测加法器：利用偏移量的特殊性

设计提示

AGU加法器的一种重要优化是推测加法器（Speculative Adder），利用12位偏移量不太可能改变高位地址的事实。具体做法是：

1. 立即输出基址的高位（不等待低位进位），同时用低12$\sim$13位启动快速加法器。

2. 用低位加法器的结果驱动D-Cache的Set索引（低位地址不需要TLB翻译）。

3. 并行地计算低位是否产生了进位。如果有进位，在下个半周期修正高位地址。

由于进位发生的概率很低（统计上只有约3%$\sim$5%的地址计算会在第12位产生进位），推测成功率很高。推测失败时需要额外一个周期修正，但由于概率低，对平均性能的影响微乎其微。这种优化可以将AGU的有效延迟减少2$\sim$3级门延迟。

AGU在流水线中的位置

Load/Store指令在执行流水线中的典型时序

在高性能设计中，AGU和TLB查找可以部分重叠。关键观察是：D-Cache使用VIPT（Virtually Indexed, Physically Tagged）方式访问——Cache的Set索引来自虚拟地址的低位（页内偏移部分），而Tag比较使用物理地址的高位。由于页内偏移在虚拟地址和物理地址之间完全相同，AGU一旦计算出低位地址，就可以立即启动Cache的Set索引，不需要等待TLB完成翻译。TLB的翻译结果（物理页号）只需要在Cache的Tag比较阶段到达即可。

这种AGU与TLB的重叠执行有效地将Load指令的有效延迟减少了约1个周期——从"AGU $\to$ TLB $\to$ Cache"串行变为"AGU+TLB并行 $\to$ Cache Tag比较"。

地址计算的特殊优化

除了推测加法器之外，AGU还可以利用地址计算的特殊模式来进一步优化。

基址更新模式

在很多程序中，Load/Store指令的基址来自一个循环变量，每次迭代递增一个固定的步长（stride）。例如遍历数组时，连续的Load指令可能计算$\text{base}, \text{base}+8, \text{base}+16, \ldots$这样的地址序列。

如果AGU能够识别这种模式，可以使用递增加法器代替通用加法器——递增加法器只需要在上一个地址的基础上加一个小常数，延迟远低于全宽加法。某些处理器在AGU中维护一个"上一次地址"寄存器，当检测到当前Load/Store的基址与上一次相同且偏移量变化为固定步长时，直接使用递增结果。

RV64的ADDI+Load融合

在RISC-V代码中，ADDI+LD组合非常常见（计算地址偏移后立即加载数据）。某些处理器在前端通过宏融合（macro-fusion）将这两条指令合并为一条"extended-offset Load"指令，在AGU中一次性完成"base + offset1 + offset2"的三操作数加法。

三操作数加法可以通过在AGU加法器前增加一个CSA（进位保留加法器）来高效实现——CSA将三个操作数压缩为两个（一行和、一行进位），然后送入常规加法器。CSA的延迟仅为1$\sim$2级门延迟，对总延迟的影响很小。

AGU与ALU的共享决策

共享方案的适用场景

在AGU和ALU共享加法器的设计中，同一个加法器端口在不同指令类型之间复用。ALU指令使用时执行算术运算，Load/Store指令使用时执行地址计算。优点是节省面积，缺点是ALU指令和Load/Store指令竞争加法器——降低了并行度。

专用方案的适用场景

高性能处理器使用独立的AGU加法器：ALU和AGU在同一周期内可以并行工作，最大化指令并行度。代价是多个独立加法器的面积和功耗。

设计权衡 3 — AGU与ALU的共享策略

共享与专用的选择取决于处理器的设计目标：

• 面积受限的嵌入式处理器（如RISC-V小型核心）：使用共享方案。这些处理器通常只有1$\sim$2个执行端口，指令并行度有限，共享不会成为瓶颈。

• 高性能超标量处理器（如ARM Cortex-X系列、Intel/AMD桌面核心）：使用专用方案，通常配置2$\sim$4个独立AGU。每周期可能需要执行4$\sim$6条ALU指令和2$\sim$3条Load/Store指令，共享方案会严重限制吞吐量。

• 中等性能处理器（如ARM Cortex-A5x系列）：可能使用混合方案——一个专用AGU加上一个可复用的ALU/AGU端口，在面积和性能之间折中。

整数功能单元的总结与设计全景

表表 30.1总结了本章讨论的各个功能单元的延迟和面积特性。

功能单元	延迟（周期）	吞吐量	可流水线化	相对面积
ALU（加/减/逻辑）	1	1/周期	是（组合逻辑）	1$\times$（基准）
移位器	1	1/周期	是（组合逻辑）	0.3$\times$
乘法器	3$\sim$4	1/周期	是（3$\sim$4级）	5$\sim$8$\times$
除法器	20$\sim$40	1/20$\sim$40周期	否	3$\sim$5$\times$
AGU	1	1/周期	是（组合逻辑）	0.6$\sim$0.8$\times$

整数功能单元的延迟与面积总结

从表表 30.1可以看出，功能单元的设计呈现出一个有趣的格局：ALU和移位器是最快、最简单的单元，在一个时钟周期内完成计算；乘法器延迟较高但可以流水线化，保持每周期1条的吞吐量；除法器是延迟最高且无法流水线化的瓶颈——但由于除法指令的使用频率极低（1%$\sim$3%），它通常不是整体性能的瓶颈。

商用处理器的整数功能单元配置

表表 30.2给出了几款商用处理器的整数功能单元配置，可以看到不同设计目标下的不同取舍。

处理器	ALU数	AGU数	MUL延迟	DIV延迟	定位
Intel Golden Cove	5	3	3周期	18$\sim$40周期	高性能桌面
AMD Zen 4	4	3	3周期	15$\sim$45周期	高性能桌面
ARM Cortex-X4	6	3	3周期	7$\sim$40周期	高性能移动
ARM Cortex-A520	2	1	3周期	12$\sim$50周期	高效能移动
SiFive U74 (RISC-V)	1	1	5周期	33$\sim$66周期	嵌入式

商用处理器的整数功能单元配置

几个值得注意的趋势：

1. ALU数量差异巨大：高性能核心配置4$\sim$6个ALU，嵌入式核心仅1个。这反映了每周期执行指令数（IPC）的需求差异——6个ALU允许每周期最多执行6条整数运算，而1个ALU限制了每周期最多1条。

2. AGU数量紧跟内存通路：AGU的数量通常等于每周期可以执行的Load/Store指令数。3个AGU对应3条内存指令/周期的宽度。

3. 乘法器延迟高度一致：几乎所有高性能处理器的整数乘法延迟都是3周期，说明Booth编码+Wallace树+最终加法器的3级流水线已经成为工业标准。

4. 除法器延迟差异大：除法延迟从7周期到66周期不等，反映了不同设计在除法器优化上的投入差异。ARM Cortex-X4的除法延迟最低至7周期，这可能使用了重叠基-4 SRT或其他加速技术。

本章的核心设计原则

贯穿本章的几条核心设计原则值得总结：

原则一：延迟-面积权衡。在加法器设计中，从RCA（$O(n)$延迟、$O(n)$面积）到Kogge-Stone（$O(\log n)$延迟、$O(n\log n)$面积），我们用面积换取了速度。在乘法器设计中，Booth编码用少量编码逻辑换取了50%的部分积减少，Wallace树用$O(n\log n)$个压缩器换取了$O(\log n)$级压缩延迟。在除法器设计中，高基数SRT用更大的QDS表换取了更少的迭代次数。

原则二：并行化。RCA的问题在于进位串行传播；并行前缀加法器通过结合律实现了进位的并行计算。阵列乘法器的问题在于部分积串行累加；Wallace树通过压缩器实现了并行归约。除法器之所以慢，正是因为其"比较-决策-更新"的迭代本质上抵抗并行化——SRT的改进也只是缩短了每步的延迟，并没有从根本上打破串行性。

原则三：冗余表示。冗余数字表示在多个场景中扮演了关键角色。Booth编码用冗余的$\{-2,-1,0,+1,+2\}$系数替代标准的$\{0,1\}$系数，将部分积减半。SRT除法用冗余的$\{-1,0,+1\}$商位替代标准的$\{0,1\}$，放松了商选择的精度要求。Wallace树中的进位保留（carry-save）形式——用"和+进位"两行表示一个数而非单行标准二进制——也是一种冗余表示，它避免了中间结果的进位传播。冗余表示的核心价值是用增加表示的位数来换取消除串行依赖。

原则四：RTL延迟 $\neq$ 物理延迟。在纯逻辑层面（RTL仿真中），Kogge-Stone加法器是最快的；但在物理实现后，其密集的长距离连线可能导致实际延迟不如布线更友好的Han-Carlson。类似地，Wallace树的不规整结构在RTL中逻辑级数最少，但规整化的4:2压缩器阵列在物理实现后可能更优。处理器设计者必须同时考虑逻辑优化和物理实现——这是"设计收敛"（design closure）的核心挑战。

原则五：使用频率决定投入程度。加法器占据了整数指令的30%$\sim$40%，每一级门延迟的优化都值得大量工程投入。乘法器占5%$\sim$10%，3周期的流水线延迟是一个合理的投入水平。除法器仅占1%$\sim$3%，在其上投入过多面积和设计精力往往得不偿失。这种基于频率的投入分配是处理器设计中资源分配的基本原则。

功能单元的功耗管理

在移动和嵌入式处理器中，功能单元的功耗管理日益重要。乘法器是整数功能单元中面积和功耗最大的部分，即使在不执行乘法指令时，其内部的时钟树和流水线寄存器仍在消耗动态功耗（时钟功耗）。

时钟门控

最基本的功耗优化是时钟门控（Clock Gating）：当乘法器空闲（没有乘法指令在执行）时，关断其流水线寄存器的时钟信号。这消除了空闲周期的时钟切换功耗。实现上，调度器在发射乘法指令时产生一个使能信号，乘法器的时钟门控单元在使能信号有效后的3个周期内（对应3级流水线）保持时钟开启。

操作数隔离

另一种优化是操作数隔离（Operand Isolation）：当乘法器空闲时，用锁存器或MUX将输入操作数固定为全零或上一次的值，防止随机的输入变化通过组合逻辑传播产生"毛刺功耗"（glitch power）。对于Wallace树这样深层组合逻辑，毛刺功耗可能占总动态功耗的20%$\sim$30%。

电压/频率降低

在某些设计中，乘法器和除法器可以运行在比ALU更低的电压或频率下。由于乘法器本身就是多周期操作（3个周期），如果将其时钟频率降低到ALU的1/3并降低电压，功耗可以降低至原来的$1/3 \times (V_\mathrm{low}/V_\mathrm{high})^2$，而对性能没有影响（因为乘法本来就需要3个ALU时钟周期）。不过这种方案增加了时钟域交叉（CDC）的设计复杂度，在实际中较少使用。

设计的全局视角

处理器设计者的任务是根据目标工作负载的特征、面积和功耗预算、目标频率等约束，为每种功能单元选择最合适的实现方案。没有万能的"最优"设计——有的只是在特定约束下的最佳权衡。

设计权衡 4 — 前向桥接——从整数到浮点

本章深入讨论了整数功能单元的设计——加法器的并行前缀结构、乘法器的Booth编码与Wallace树压缩、除法器的SRT迭代。这些整数运算电路并非孤立存在：它们同时也是浮点功能单元的基础构件。浮点加法器的尾数相减使用二进制补码加法器，浮点乘法器的尾数乘法使用Booth编码+Wallace树，浮点除法器使用SRT迭代。然而，浮点运算引入了整数运算中不存在的步骤——对阶、规格化、舍入——使得浮点单元的设计复杂度远高于整数单元。特别是FMA（融合乘加）的单次舍入特性，使其在近似抵消场景下的精度远优于分离的乘法+加法。1994年Intel Pentium FDIV bug（4.75亿美元召回）更将浮点单元的形式化验证推上了行业标准的地位。第 31.0 章将全面展开浮点功能单元的微架构设计。