第 12 讲 · 算术运算单元（Ⅱ）：进位选择加法器、对数延时加法器与其他运算单元

1. 预计算（Precomputation）思想与双进位链模块结构

在上一讲的第 5.3 节中，进位跳转加法器虽然把中间各组的进位延时压缩成了 1 级 MUX，但存在两大硬伤：① 最坏路径在第 1 组和最后 1 组各要老老实实走完 $M$ 位和 $(M-1)$ 位串行行波（系数为 $2M-1$）；② 存在令静态时序分析（STA）工具报错的跨组伪路径。

老师在 ▶ P44 (5.5) 00:00–05:56 提出了破局之道——预计算（Precomputation）：

• 为什么最后一组要串行行波？ 因为它不知道前一组传过来的进位 $C_{\text{in},k}$ 究竟是 $0$ 还是 $1$，只能干等。
• 双进位链并行预演（▶ P44 (5.5) 02:00–04:15）：既然单比特进位 $C_{\text{in},k} \in \{0, 1\}$ 只有两种可能，我们在每个 $M$ 位小组内部：
  1. 共享第 1 步（Setup 级）：用 1 套电路并行算出本组各比特的 $P_i = A_i \oplus B_i$ 与 $G_i = A_i B_i$；
  2. 双路第 2 步（Dual Carry Chains）：上方放一条假定组输入进位 $C_{\text{in}}=0$ 的 $M$ 位进位链，算出候选进位 $C_1^{(0)}, C_2^{(0)}, \dots, C_M^{(0)}$；下方放一条假定组输入进位 $C_{\text{in}}=1$ 的 $M$ 位进位链，同时算出候选进位 $C_1^{(1)}, C_2^{(1)}, \dots, C_M^{(1)}$；
  3. 多路器瞬时裁决（MUX Array）：当来自低位组的真实进位 $C_{\text{in},k}$ 终于到达本组时，直接作为 $(M+1)$ 个 2-to-1 MUX 的公共选择信号（Select），在 1 个 $t_{\text{mux}}$ 延时内瞬间选出真实的组输出进位 $C_{\text{out},k}$ 以及本组内部每一位的真实进位 $C_1, \dots, C_{M-1}$；
  4. 共享第 3 步（Sum 级）：用 1 套异或门算出最终本位和 $S_i = P_i \oplus C_{i-1}$。

---

2. 等宽线性进位选择加法器（Linear CSLA）的 $2\sqrt{N}$ 延时推导

将 $N$ 位加法器等分为 $K = N/M$ 组（每组 $M$ 位，课件 ▶ P44 (5.5) 05:56–10:07 以 $N=16, M=4, K=4$ 为例，设定 $t_{\text{setup}} = t_{\text{carry}} = t_{\text{mux}} = t_{\text{sum}} = 1$）：

1. 逐时刻追踪 16 位等宽 CSLA（4-4-4-4）时空进程（▶ P44 (5.5) 06:15–08:12）

   • $t = 1$：全部 16 位的 $P_i, G_i$ 同时产生完毕（耗时 $t_{\text{setup}} = 1$）；
   • $t = 1 \to 5$：第 1、2、3、4 组内部的 $C_{\text{in}}=0$ 和 $C_{\text{in}}=1$ 双进位链全部同时并行跑完 4 级进位（耗时 $4 t_{\text{carry}} = 4$，在 $t=5$ 时刻全部就绪）；
   • $t = 5 \to 9$：外部真实进位 $C_{\text{in},0}$ 穿过第 1 组的 MUX 在 $t=6$ 产生 $C_4$ $\to$ 穿过第 2 组 MUX 在 $t=7$ 产生 $C_8$ $\to$ 穿过第 3 组 MUX 在 $t=8$ 产生 $C_{12}$ $\to$ 穿过第 4 组 MUX 在 $t=9$ 选出第 4 组内部全部真实进位；
   • $t = 9 \to 10$：第 4 组经最后 1 级异或门算出最高位和 $S_{13}\sim S_{16}$（总耗时 $10$ 单位）。

2. 关键路径闭合式与均值不等式求极值（▶ P44 (5.5) 08:12–10:07）
   一般地，对于位宽 $N$、每组 $M$ 位的等宽进位选择加法器，其最坏关键路径为： $$t_p(M) = t_{\text{setup}} + M\,t_{\text{carry}} + \left(\frac{N}{M}\right)t_{\text{mux}} + t_{\text{sum}}$$ 对比第 5.3 节进位跳转加法器的公式 $t_{\text{bypass\_adder}} = t_{\text{setup}} + (2M-1)t_{\text{carry}} + (N/M-1)t_{\text{bypass}} + t_{\text{sum}}$，由于最后一组无需再串行行波 $(M-1)$ 位，含 $M$ 的线性项系数从 $2M$ 直接减半为 $M$！由均值不等式： $$M\,t_{\text{carry}} + \frac{N}{M}\,t_{\text{mux}} \ge 2\sqrt{N\,t_{\text{carry}}\,t_{\text{mux}}}, \qquad \text{当且仅当 } M^* = \sqrt{\frac{N\,t_{\text{mux}}}{t_{\text{carry}}}} \text{ 时取等号}$$ 因此，等宽 CSLA 的主项延时为 $2\sqrt{N}$，比进位跳转加法器的 $2\sqrt{2N}$ 快了 $1 - \frac{1}{\sqrt{2}} \approx 29.3\%$（约 $30\%$）！

---

3. 不等宽平方根进位选择加法器（Square-Root CSLA）：消除空闲等待圈

老师在 ▶ P44 (5.5) 12:02–16:43 指出了等宽 CSLA 时空图中的一个巨大浪费：

• 在 4-4-4-4 等宽分组中，第 2、3、4 组内部的进位链在 $t=5$ 就早早算完了，但前级传来的 MUX 选择信号分别要到 $t=6, 7, 8$ 才到达！这导致第 2 组白白干等了 1 个单位时间，第 3 组干等了 2 个单位时间，第 4 组干等了 3 个单位时间（课件上用蓝色小圆圈标出的空闲等待期）。
• 核心洞察（▶ P44 (5.5) 12:55）：既然第 $k$ 组的 MUX 选择信号比第 $k-1$ 组晚到 1 个单位时间（$t_{\text{mux}} = 1$），为什么不让第 $k$ 组比第 $k-1$ 组多包含 1 个比特（即多算 1 级内部进位 $t_{\text{carry}} = 1$），从而让组内双进位链算完的时刻恰好等于前级 MUX 选择信号到达的时刻？

组号 $k$	组位宽 $M_k$（16位：2-2-3-4-5）	组内双进位链完成时刻 $t_{\text{internal}} = 1 + M_k$	前级进位到达 MUX 选择端时刻 $t_{\text{select}}$	本组 MUX 输出时刻 $t_{\text{out}}$
第 1 组	$M_1 = 2\text{ bit}$	$1 + 2 = 3$	$C_{\text{in},0}$ 在 $t=0$ 已就绪	$t = 3 + 1 = 4$
第 2 组	$M_2 = 2\text{ bit}$	$1 + 2 = 3$（微等 1 拍或恰好对齐）	$C_2$ 在 $t = 4$ 到达	$t = 4 + 1 = 5$
第 3 组	$M_3 = 3\text{ bit}$	$1 + 3 = 4$（与 $t=5$ 完美衔接）	$C_4$ 在 $t = 5$ 到达	$t = 5 + 1 = 6$
第 4 组	$M_4 = 4\text{ bit}$	$1 + 4 = 5$（与 $t=6$ 完美衔接）	$C_7$ 在 $t = 6$ 到达	$t = 6 + 1 = 7$
第 5 组	$M_5 = 5\text{ bit}$	$1 + 5 = 6$（与 $t=7$ 完美衔接）	$C_{11}$ 在 $t = 7$ 到达	$t = 7 + 1(\text{Sum}) = \mathbf{8}$

1. 等差数列求和导出 $\sqrt{2N}$ 标度律（▶ P44 (5.5) 13:55–16:43）
   设共有 $K$ 组，各组位宽按等差数列递增 $1$：$N = M_1 + (M_1+1) + (M_1+2) + \cdots + (M_1+K-1)$。当 $N$ 较大且首组 $M_1 \approx 1\sim 2$ 时： $$N \approx \sum_{k=1}^{K} k = \frac{K(K+1)}{2} \approx \frac{1}{2}K^2 \implies K \approx \sqrt{2N}$$ 由于每一组内部进位均被前级 MUX 链完美掩盖，总关键路径仅取决于首组进位加 $K$ 级 MUX 传播： $$t_{p,\text{sqrt}} = t_{\text{setup}} + M_1 t_{\text{carry}} + K\,t_{\text{mux}} + t_{\text{sum}} \approx \sqrt{2N\,t_{\text{carry}}\,t_{\text{mux}}}$$ 对比等宽 CSLA 的 $2\sqrt{N} = \sqrt{4N}$，递增位宽的平方根进位选择加法器（Square-Root CSLA）将主项延时从 $2\sqrt{N}$ 进一步压缩至 $\sqrt{2N}$，又快了 $1 - \frac{\sqrt{2}}{2} \approx 30\%$！

2. 四代加法器延时阶梯总览（▶ P44 (5.5) 18:20–19:54）
   $$\underbrace{N}_{\text{行波进位 RCA}} \xrightarrow{\text{旁路跳转}} \underbrace{2\sqrt{2N}}_{\text{进位跳转 Carry-Bypass}} \xrightarrow[-30\%]{\text{双链预计算}} \underbrace{2\sqrt{N}}_{\text{等宽进位选择 Linear CSLA}} \xrightarrow[-30\%]{\text{递增组宽 } 2,2,3,4,5\dots} \underbrace{\sqrt{2N}}_{\text{平方根进位选择 Sqrt-CSLA}}$$

1. 从进位递推展开到黑圆点前缀算子（Dot Operator $\bullet$）

为什么说加法器的全部瓶颈都在于进位？老师在 ▶ P45 (5.6) 04:11–13:21 将三步式全加器的进位递推方程 $C_i = G_i + P_i C_{i-1}$ 进行了彻底的代数重构：

1. 统一边界表示与递归展开（▶ P45 (5.6) 04:11–07:32）
   为了把最低位外部输入进位 $C_{\text{in},0}$ 也纳入统一记号，我们增设第 $0$ 位虚拟信号： $$G_0 = C_{\text{in},0}, \qquad P_0 = 0 \implies C_0 = G_0 + P_0 C_{-1} = G_0$$ 于是 4 位进位可以逐级展开为： $$\begin{aligned} C_1 &= G_1 + P_1 C_0 = G_1 + P_1 G_0 \\ C_2 &= G_2 + P_2 C_1 = G_2 + P_2(G_1 + P_1 G_0) = (G_2 + P_2 G_1) + (P_2 P_1) G_0 \\ C_3 &= G_3 + P_3 C_2 = \big[G_3 + P_3(G_2 + P_2 G_1)\big] + (P_3 P_2 P_1) G_0 \end{aligned}$$ 观察 $C_3 = G_3 + P_3(G_2 + P_2(G_1 + P_1 G_0))$：如果从最内层括号往外一层层串行算，这就是 $O(N)$ 的行波进位；但如果换一种括号结合方式，写成： $$C_3 = (G_3 + P_3 G_2) + (P_3 P_2)(G_1 + P_1 G_0)$$ 你会震惊地发现：高两位的合并项 $(G_{3:2}, P_{3:2}) = (G_3 + P_3 G_2,\; P_3 P_2)$ 与低两位的合并项 $(G_{1:0}, P_{1:0}) = (G_1 + P_1 G_0,\; P_1 P_0)$ 完全可以在第 1 层同时并行算出，然后在第 2 层只需再做一次同样形式的合并即可得到 $C_3$！

2. 黑圆点算子（$\bullet$）的严格定义与电路实现（▶ P45 (5.6) 09:40–13:21）
   将上述两区间合并规律抽象为二元算子 $\bullet$：对于高位区间 $[i:k]$ 与低位区间 $[k-1:j]$（$i \ge k > j \ge 0$）， $$(G_{i:j},\; P_{i:j}) = (G_{i:k},\; P_{i:k}) \bullet (G_{k-1:j},\; P_{k-1:j}) = \big(\underbrace{G_{i:k} + P_{i:k} G_{k-1:j}}_{G_{i:j}},\;\; \underbrace{P_{i:k} P_{k-1:j}}_{P_{i:j}}\big)$$

   • 物理意义：区间 $[i:j]$ 产生进位（$G_{i:j}=1$），当且仅当高半区间 $[i:k]$ 自己产生进位（$G_{i:k}=1$），或者低半区间 $[k-1:j]$ 产生进位（$G_{k-1:j}=1$）且高半区间全体处于传播态（$P_{i:k}=1$）。
   • 前缀终点恒等式：因为 $P_0 = 0$，所以 $G_{i:0} = G_{i:1} + P_{i:1} G_0 = G_{i:1} + P_{i:1} C_0 = C_i$。算出每一位的全前缀 $G_{i:0}$，就等于算出了该位的进位输出 $C_i$！

---

2. 三大经典对数前缀树：Kogge-Stone、Sklansky 与 Brent-Kung

• 既然 $\bullet$ 满足结合律，我们只需用 $\log_2 N$ 层二叉树就能算出最高位进位 $G_{N:0}$。
• 但加法器不是只求最高位，而是要同时求出所有位 $G_{1:0}, G_{2:0}, \dots, G_{N:0}$！老师在 ▶ P45 (5.6) 13:21–22:56 详细拆解了三种不同的建树哲学（以 16 位加法器为例）：

树形加法器拓扑	核心建树思想	逻辑层数（$N=16$）	节点最大扇出（Fan-out）	水平跨距连线与面积	适用场景
Kogge-Stone (KS) (▶ P45 (5.6) 14:10)	每比特拥有独立平移二叉树（利用区间重叠性质）	最少：$\log_2 N = 4$ 层	最小：$\le 2$	最复杂：第 $k$ 层跨距 $2^{k-1}$ 交叉线极密，面积最大	追求极致主频的 64 位高端 CPU ALU
Sklansky (▶ P45 (5.6) 17:03)	极致复用低半区已算完的公共前缀根节点	最少：$\log_2 N = 4$ 层	恶劣：高达 $N/2 = 8$（64位达 32！）	简单：无交叉长线，黑圆点单元数比 KS 少近一半	需插大缓冲器，较少直接裸用
Brent-Kung (BK) (▶ P45 (5.6) 20:28)	$\log_2 N$ 层正向归约树 + $(\log_2 N-1)$ 层反向分发树	翻倍：$2\log_2 N - 1 = 7$ 层	最小：$\le 2$	最简单、面积最小：完全消除大扇出与交叉连线	面积、功耗与布线受限的中高速设计

• 树形加法器的“不可能三角”（▶ P45 (5.6) 24:50–26:44）：老师总结道，在并行前缀树设计中，① 逻辑层数最少（$\log_2 N$）、② 节点扇出最小（$\le 2$）、③ 连线简单且单元面积最小 这三个理想目标不可能同时达到！Kogge-Stone 选了 ①+②（牺牲 ③ 连线复杂度），Sklansky 选了 ①+③（牺牲 ② 产生大扇出），Brent-Kung 选了 ②+③（牺牲 ① 逻辑层数翻倍）。现代综合器还支持介于三者之间的混合树（如 Han-Carlson 树、Knowles 树），在该三角空间内按需微调。

1. 加减法器统一架构与最高位预计算低功耗比较器

算术逻辑单元（ALU）中的减法与大小比较本质上都是加法器的衍生运算。老师在 ▶ P46 (5.7) 00:00–10:22 从电路复用一路剖析到低功耗架构创新：

1. 补码加减法合一（▶ P46 (5.7) 00:00–02:07）
   利用二进制补码恒等式 $-B = \overline{B} + 1$，只需用控制信号 $\text{Sub} \in \{0, 1\}$ 与操作数 $B$ 的每一比特做异或（$B_i' = B_i \oplus \text{Sub}$），并令最低位进位输入 $C_{\text{in},0} = \text{Sub}$，即可在零额外加法器面积下实现加减同构。

2. 最高位预计算门控比较器（Precomputation Gated Comparator，▶ P46 (5.7) 04:36–09:54）
   在常规 $N$ 位数字比较器中，为了判断 $A > B$、$A < B$ 还是 $A = B$，往往直接让 $N$ 位减法器算出 $S = A - B$。然而老师指出一个惊人的统计事实：

   • 假设输入 $A, B$ 为均匀分布的随机二进制数，那么它们的最高有效位（MSB）$A_{N-1}$ 与 $B_{N-1}$ 不相等的概率高达 $50\%$！
   • 当 $A_{N-1} \ne B_{N-1}$ 时（例如无符号数 $A_{N-1}=1, B_{N-1}=0$），无论低 $(N-1)$ 位是什么数值，必然有 $A > B$！此时让低 $(N-1)$ 位减法器跟着翻转计算完全是白白浪费动态功耗！
   • 门控架构实现：先用 1 个同或门算出使能信号 $\text{EN} = A_{N-1} \odot B_{N-1}$（仅当 $A_{N-1} = B_{N-1}$ 时 $\text{EN}=1$），再用 $\text{EN}$ 通过与门对低 $(N-1)$ 位输入进行门控锁死（$A_i' = A_i \cdot \text{EN},\; B_i' = B_i \cdot \text{EN}$）。
   • 功耗与延时权衡：在 $50\%$ 的时钟周期内，$\text{EN}=0$ 使后级 $(N-1)$ 位电路保持静默，立省约 $50\%$ 动态功耗；若预看最高 2 位，则有 $1 - (1/2)^2 = 75\%$ 的概率锁死后级，省电 $75\%$！一般地，预看高 $k$ 位可省电 $(1 - 2^{-k})$，但代价是当高 $k$ 位恰好相等（那个 $2^{-k}$ 的小概率最坏情况）时，信号必须先穿过 $k$ 位预计算门控逻辑才能启动后级减法器，导致最坏关键路径变长。

---

2. 进位保留加法器（CSA）与乘法器演进：从行波阵列（$3N$）到 Wallace 树

二进制乘法 $P = A \times B$ 的第一步是用 $N \times N$ 个二输入与门生成全部部分积（Partial Products）$p_{i,j} = A_i B_j$，真正的速度瓶颈在于如何将这 $N$ 行部分积高效相加：

乘法器拓扑架构	进位与求和传递方式	最坏关键路径延时（$N \times N$）	硬件规整度与特点
常规行波阵列乘法器 (▶ P46 (5.7) 12:55)	进位在每行内水平传递，求和沿列垂直传递	$(N-1)t_{\text{sum}} + (2N-3)t_{\text{carry}} \approx \mathbf{3N}$	结构规整，但每行都要等水平进位，$t_{\text{sum}}$ 占 $1/3$、$t_{\text{carry}}$ 占 $2/3$
进位保留阵列乘法器 (▶ P46 (5.7) 16:29)	前 $N-1$ 行用 CSA 将进位沿 $45^\circ$ 斜向送入下一行 + 末行 VMA	$(N-1)t_{\text{carry}} + (N-1)t_{\text{VMA}} \approx \mathbf{2N}$	面积几乎不变、版图极度规整，关键路径直接缩短 $1/3$（快 $33\%$）！
Booth + Wallace 树乘法器 (▶ P46 (5.7) 21:10)	Radix-4 Booth 减半行数 + 3:2 CSA 树对数层压缩 + 末级对数加法器	$O(\log_{1.5}(N/2)) + O(\log_2 N) = \mathbf{O(\log N)}$	速度达组合乘法极限，但跨层连线高度不规则，适合 32/64 位高速 DSP/CPU

• 为什么进位保留加法器（CSA）能消灭水平进位链？（▶ P46 (5.7) 10:22–12:55）
  普通加法器是“2 输入 $\to$ 1 输出”，进位必须在同一行内从低位传到高位；而进位保留加法器（Carry-Save Adder）把 $N$ 个全加器当作独立的 3:2 压缩器（3:2 Compressor），接收 3 个加数向量 $(X, Y, Z)$，在 1 级全加器延时内直接输出本位和向量 $S$ 与进位向量 $C$（满足 $X + Y + Z = S + 2C$）。进位 $C_i$ 根本不在本行内部横向传播，而是直接斜向跨入下一行与新的部分积一起做下一轮 3:2 压缩，直到最后只剩 2 个向量时，才用 1 个高速矢量合并加法器（Vector-Merge Adder, VMA）一举算出最终乘积！

---

3. 多位移位器（Shifter）：阵列移位器 vs 对数级联桶形移位器

在浮点运算对阶、算术移位与位域提取中，需要在单周期内完成任意位数（$0 \sim N-1$ 位）的移位。老师在 ▶ P46 (5.7) 23:45–26:20 对比了两类移位器拓扑：

1. 阵列移位器（Array / Crossbar Shifter）

   • 采用 $K$-to-$2^K$ 译码器（$N = 2^K$）将二进制移位控制码译为 $N$ 条独热（One-hot）字线，每条字线控制一排 $N$ 个传输管，将输入信号斜向跨接平移相应位数。
   • 优缺点：数据信号只需穿过 1 级传输管，但需要庞大的译码器，且传输管数量与连线复杂度高达 $O(N^2)$（64 位需 $64 \times 64 = 4096$ 个单元），节点寄生电容极大。

2. 对数级联桶形移位器（Logarithmic Barrel Shifter）

   • 二进制权重分解：任意移位量 $\text{Sh} \in [0, N-1]$ 均可唯一表示为二进制形式 $\text{Sh} = \sum_{m=0}^{K-1} s_m 2^m$（其中 $K = \log_2 N$）。
   • 级联多路器架构：共串联 $K = \log_2 N$ 级 2-to-1 MUX 阵列，直接用移位码的第 $m$ 位 $s_m$ 作为第 $m$ 级 MUX 的选择信号——当 $s_0=1$ 时第 0 级移位 $2^0=1$ 位（否则直通）；当 $s_1=1$ 时第 1 级移位 $2^1=2$ 位；当 $s_2=1$ 时第 2 级移位 $2^2=4$ 位……
   • 显著优势：完全省去了译码器！对于 $N=64$ 位移位器，仅需 $\log_2 64 = 6$ 级 2-to-1 MUX 级联，硬件复杂度从 $O(N^2)$ 骤降至 $O(N \log_2 N)$。