J.8 加速整数加法

前一节表明，浮点运算需要很多步骤，但最终都归结为整数运算。因此，加速整数运算也能加速浮点运算。

整数加法最简单，也最重要。即使程序不显式计算数值，递增程序计数器和计算地址也需要加法。尽管加法简单，高速实现却没有唯一最佳方法。下面讨论三种实际采用的技术：先行进位、跳跃进位和选择进位。

先行进位

$n$ 位加法器是组合电路，因此可以写成“积之和”的逻辑表达式，用两级逻辑计算。怎样得到这样的电路？由式 J.2.1，第 $i$ 位的和为

s_i=a_i\bar b_i\bar c_i+\bar a_i b_i\bar c_i+\bar a_i\bar b_i c_i+a_i b_i c_i.\tag{J.8.1}

$c_i$ 既是第 $i$ 位的进位输入，也是第 $i-1$ 位的进位输出。问题在于， $a_i,b_i$ 是已知输入， $c_i$ 却未知。目标是把 $c_i$ 写成 a、b 各位的函数。先把式 J.2.2 改写为

c_i=g_{i-1}+p_{i-1}c_{i-1},\qquad g_{i-1}=a_{i-1}b_{i-1},\qquad p_{i-1}=a_{i-1}+b_{i-1}.\tag{J.8.2}

这里 g 代表 generate（生成）：若 $g_{i-1}$ 为真，就一定产生 $c_i$ 。p 代表 propagate（传播）：若 $p_{i-1}$ 为真， $c_{i-1}$ 就传到 $c_i$ 。把式 J.8.1 中的 $c_i$ 用式 J.8.2 替换，再递归替换 $c_{i-1},c_{i-2},\ldots$ ，得到

c_i=g_{i-1}+p_{i-1}g_{i-2}+p_{i-1}p_{i-2}g_{i-3}+\cdots +p_{i-1}p_{i-2}\cdots p_1g_0 +p_{i-1}p_{i-2}\cdots p_1p_0c_0.\tag{J.8.3}

采用该式计算进位的加法器称为先行进位加法器（carry-lookahead adder，CLA）。先用一级逻辑生成 p、g，再用两级生成进位，最后两级生成和，共五级，比行波进位的 $2n$ 级快得多。

直接展开所有进位乘积项的先行进位电路 — 图 J.14 计算 n 位加法器最终进位 cn 的纯先行进位电路。各项的逻辑关系与式 J.8.3 相同。

遗憾的是，从式 J.8.3 或图 J.14 可以看出， $n$ 位 CLA 的 OR 门和最右侧 AND 门都需要 $n+1$ 的扇入， $p_{n-1}$ 还要驱动 $n$ 个 AND 门。再加上不规则结构和很多长连线， $n$ 很大时，这种完全展开的先行进位电路并不实用。

不过，可以逐步生成 p、g，构造约 $\log_2n$ 级逻辑、结构简单规则的加法器。我们已有

c_1=g_0+c_0p_0.

即第 0 位自己生成进位，或把输入进位传播出去，就会产生 $c_1$ 。类似地，

c_2=G_{01}+P_{01}c_0, \qquad G_{01}=g_1+p_1g_0,\qquad P_{01}=p_1p_0.

$G_{01}$ 表示最低两位组成的块会生成进位， $P_{01}$ 表示进位可穿过该块。更一般地，对满足 $i<j,j+1<k$ 的 j，有

c_{k+1}=G_{ik}+P_{ik}c_i.\tag{J.8.4}

G_{ik}=G_{j+1,k}+P_{j+1,k}G_{ij}.\tag{J.8.5}

P_{ik}=P_{ij}P_{j+1,k}.\tag{J.8.6}

式 J.8.5 表示：第 i 到 k 位的整个块生成进位，当且仅当高半块 $(j+1,k)$ 自己生成进位，或低半块 $(i,j)$ 生成进位后穿过高半块。若定义 $G_{ii}=g_i,P_{ii}=p_i$ ，这些式子对 $i\le j<k$ 也成立。

例题　用 p、g 表示 $P_{03},G_{03}$ 。

解答　由式 J.8.6，

P_{03}=P_{01}P_{23}=P_{00}P_{11}P_{22}P_{33}=p_0p_1p_2p_3.

由式 J.8.5，

\begin{aligned} G_{03}&=G_{23}+P_{23}G_{01}\\ &=(G_{33}+P_{33}G_{22})+(P_{22}P_{33})(G_{11}+P_{11}G_{00})\\ &=g_3+p_3g_2+p_3p_2g_1+p_3p_2p_1g_0. \end{aligned}

有了这些准备，就可设计实用 CLA。第一部分用式 J.8.5、J.8.6，从各位的 p、g 生成各种分组 P、G；第二部分用式 J.8.4 生成全部进位。第一部分见图 J.15：输入 $a_7\cdots a_0,b_7\cdots b_0$ 从顶部进入类型 1 单元，变成 p、g。

向下计算各组传播和生成信号的先行进位树 — 图 J.15 先行进位树的第一部分。信号自上而下流动，计算不同范围的 P 和 G。类型 1 单元计算 gi=aibi、pi=ai+bi；类型 2 单元按式 J.8.5、J.8.6 合并相邻分组。

类型 2 单元按二叉树连接，生成各组 P、G。第二部分见图 J.16：从树底输入 $c_0$ ，所有进位从树顶输出。每个单元需要一对 (P,G)，图中把所需值写在单元内。对比图 J.15、J.16，单元一一对应，生成进位的单元所需的 P、G，恰好由对应的另一单元产生。把它们合并，就得到图 J.17。操作数从顶部向下传播，在底部与 $c_0$ 结合，再向上传播生成进位。图 J.17 尚省略了一小块额外逻辑，用来计算整个加法器的进位输出 $c_8$ 。

向上生成各位进位的先行进位树 — 图 J.16 先行进位树的第二部分。信号自下而上流动，与 P、G 结合形成进位；每个单元使用 cj+1=Gij+Pijci。

CLA 的信号约经过 $\log_2n$ 级逻辑，行波进位则为 $2n$ ， $n$ 越大，速度优势越明显。行波进位有 n 个单元，CLA 约有 2n 个；但在这里的布局中，占用空间为 $n\log n$ 。少量面积投入，就能获得显著加速。

还可按工艺作调整。例如，把每个树节点的输入从两个增为三个，树高便从 $\log_2n$ 降为 $\log_3n$ ；但单元更复杂、可能更慢，抵消树高收益。若工艺适合快速行波传播，混合设计可能更好，如图 J.19：顶层组内行波传播，B 方框与图 J.17 相同。若穿过四个加法器的行波延迟，小于穿过一层 B 单元的延迟，这种设计就更快。为清楚显示结构，图 J.19 画成 16 位，图 J.17 的 8 位加法器对应它的右半部分。

合并向下和向上传播过程的完整先行进位树加法器 — 图 J.17 完整先行进位树加法器，由图 J.15、J.16 合并而成。加数从顶部进入，在底部与 c0 结合，再向上传播计算各个和位。A 单元除生成 pi、gi 外，还计算 si=ai XOR bi XOR ci；B 单元合并分组信号并分配进位。

跳跃进位加法器

跳跃进位加法器（carry-skip adder）的速度和成本都介于行波进位与先行进位之间。它不简称 CSA，因为 CSA 已用于 carry-save adder。其思路来自 P、G 的方程，例如

P_{03}=p_0p_1p_2p_3,\qquad G_{03}=g_3+p_3g_2+p_3p_2g_1+p_3p_2p_1g_0.

P 比 G 简单得多，因此跳跃进位加法器只计算 P，见图 J.18。

以四位为一组的二十位跳跃进位加法器 — 图 J.18 跳跃进位加法器。总位数 n=20，每块宽度 k=4。

进位在所有块内同时开始逐位传播。某块若自身生成进位，即使该块的输入进位尚未确定，输出进位也会为真。若每次加法开始时把各块输入进位置 0，就不会产生伪进位，因此可以把各块的进位输出当作 G 信号。最低块的进位一旦产生，不仅送往下一块，还与下一块的 P 通过 AND 门结合。如果两者都为真，进位就跳过第二块，直接进入第三块，依此类推。只有各块进位输入能在每次运算开始时方便清零，例如利用 CMOS 预充电，这种设计才实用。

先行进位树与组内行波传播相结合 — 图 J.19 CLA 与行波进位的组合。在顶行每四个方框组成的组内，进位逐位传播。

分析速度时，假设穿过两级逻辑耗时一个单位，则进位穿过 k 位块耗时 k，跳过一个块耗时 1。最长路径从第 0 位生成进位开始：穿过首块用 k，跳过中间块用 $n/k-2$ ，穿过末块再用 k。20 位、每块 4 位时，共需 $4+(20/4-2)+4=11$ 个时间单位。

还有更好的分组。若从低到高采用 2、5、6、5、2 位的五个块，时间降为 9。可见，把内部块做得较大有利于加速；变块宽的思想有时也适用于其他加法器。由于仍有大量行波传播，这种加法器最适合行波传播快的工艺。

选择进位加法器

选择进位加法器（carry-select adder）并行计算两次，一次假设输入进位为 0，一次假设为 1。真正的输入进位确定后，只需选择预先算好的正确结果。图 J.20 将 8 位分成两半，用低半部分进位选择高半部分和位。如果各块内部使用线性时间的行波进位，它以增加 50% 成本换取约两倍速度。但 $c_4$ 要驱动很多多路选择器，在某些工艺中可能很慢。

两个高半部预先分别假设输入进位为零和一 — 图 J.20 简单的选择进位加法器。计算低 4 位之和的同时，高 4 位并行计算两遍：分别假设 c4=0 和 c4=1。

还可从两块增至四块以继续加速，如图 J.21。若 k 位块相加需 k 个时间单位，而由两个进位输出产生多路选择控制需 1 个时间单位，那么最佳分组应沿高位方向逐块增加一位，如图所示。因此，与跳跃进位类似，最佳设计采用可变块宽。

使用逐渐增大分组的选择进位加法器 — 图 J.21 选择进位加法器。最右块的进位输出一旦确定，就用于选择其余和位。

加法器	渐近时间	渐近空间
行波进位	$O(n)$	$O(n)$
先行进位 CLA	$O(\log n)$	$O(n\log n)$
跳跃进位	$O(\sqrt n)$	$O(n)$
选择进位	$O(\sqrt n)$	$O(n)$

图 J.22　四类加法器的渐近时间与空间需求。

图 J.22 总结了本节。跳跃进位、选择进位的时间来自恰当的块宽选择；跳跃进位的推导见习题 J.26。不要把这些方法看成互斥选项，而应把它们看成构造加法器的模块。适用性高度依赖工艺：信号能驱动很多多路选择器时，选择进位很好；每次运算开始时能方便清零时，跳跃进位很有吸引力。

渐近性质有助于理解，却不宜过分依赖，因为它只在 n 极大时才占主导。加法器的 n 是精度位数，而双精度与 20 年前一样，仍约 53 位。计算机越快，计算过程往往越长、舍入误差更多，确实会要求更高精度，但这种增长随时间发生得很慢。