# J.8 加速整数加法
<!-- source: p1261 -->

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

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

## 先行进位

\(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\) 级快得多。

<!-- source: p1262 -->

![直接展开所有进位乘积项的先行进位电路](/figures/app-j/fig-j-14.png)
{#fig-J.14 .wide .expand num="J.14" caption="计算 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}
$$

<!-- source: p1263 -->

$$
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。

![向下计算各组传播和生成信号的先行进位树](/figures/app-j/fig-j-15.png)
{#fig-J.15 .wide .expand num="J.15" caption="先行进位树的第一部分。信号自上而下流动，计算不同范围的 P 和 G。类型 1 单元计算 gi=aibi、pi=ai+bi；类型 2 单元按式 J.8.5、J.8.6 合并相邻分组。"}

<!-- source: p1264 -->

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

![向上生成各位进位的先行进位树](/figures/app-j/fig-j-16.png)
{#fig-J.16 .wide .expand num="J.16" caption="先行进位树的第二部分。信号自下而上流动，与 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 位加法器对应它的右半部分。

<!-- source: p1265 -->

![合并向下和向上传播过程的完整先行进位树加法器](/figures/app-j/fig-j-17.png)
{#fig-J.17 .wide .expand num="J.17" caption="完整先行进位树加法器，由图 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。

![以四位为一组的二十位跳跃进位加法器](/figures/app-j/fig-j-18.png)
{#fig-J.18 .wide .expand num="J.18" caption="跳跃进位加法器。总位数 n=20，每块宽度 k=4。"}

<!-- source: p1266 -->

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

![先行进位树与组内行波传播相结合](/figures/app-j/fig-j-19.png)
{#fig-J.19 .wide .expand num="J.19" caption="CLA 与行波进位的组合。在顶行每四个方框组成的组内，进位逐位传播。"}

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

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

<!-- source: p1267 -->

## 选择进位加法器

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

![两个高半部预先分别假设输入进位为零和一](/figures/app-j/fig-j-20.png)
{#fig-J.20 .wide .expand num="J.20" caption="简单的选择进位加法器。计算低 4 位之和的同时，高 4 位并行计算两遍：分别假设 c4=0 和 c4=1。"}

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

![使用逐渐增大分组的选择进位加法器](/figures/app-j/fig-j-21.png)
{#fig-J.21 .wide .expand num="J.21" caption="选择进位加法器。最右块的进位输出一旦确定，就用于选择其余和位。"}

<!-- source: p1268 -->

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

图 J.22　四类加法器的渐近时间与空间需求。
{#fig-J.22 .wide .expand num="J.22"}

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

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