超前进位

玻尔百科

核心要点

行波进位加法器 (RCA) 的速度天生较慢，因为其计算时间因顺序的进位传播而随位数线性增长。
超前进位加法器 (CLA) 通过使用“传递”和“生成”信号来并行计算所有进位位，从而彻底改变了这一状况，极大地减少了总延迟。
逻辑门扇入数等实际限制阻碍了大型单级 CLA 的创建，这导致了层次化设计的使用，该设计在多个层级上应用超前原理。
传递与生成的概念是数字设计中的一个通用原则，应用于优化其他组件，如计数器、移位器和乘法器。
从理论上讲，超前方法证明了二进制加法是复杂性类别 AC^0 中的一个问题，意味着它可以在具有无界扇入的并行计算机上以常数时间解决。

引言

每台数字计算机的核心都蕴含着一个基本操作：加法。处理器执行这项简单任务的速度决定了其整体性能。然而，最直观的数字加法方法，即模仿人类在纸上做加法的方式，却造成了严重的速度瓶颈。这种被称为行波进位加法器的简单方法，迫使其计算的每个阶段都等待前一阶段完成，从而产生一连串的延迟反应，对于现代系统中使用的32位或64位数字来说，这种延迟变得极其缓慢。本文将探讨一种卓越而强大的替代方案——超前进位机制，以解决这一关键性能差距。

本文将引导您了解这种高速设计的理论和应用。第一章“原理与机制”解构了行波进位问题，并引入了“传递”和“生成”信号这一优雅的解决方案，展示了它们如何让我们“预见”计算的未来并同时计算所有进位。第二章“应用与跨学科联系”扩展了这一核心思想，揭示了超前原理不仅是加法器的技巧，更是一个彻底改变CPU算术、影响其他数字组件设计，甚至在理论计算机科学领域具有深远意义的基本概念。

原理与机制

想象一下，你在杂货店，收银员正在计算你购买商品的总价。但这位收银员有点奇怪。为了计算总额，他们首先加上分的列。然后写下结果，将元进位，之后才开始加元的列。现在想象一下你的账单上有数百件商品；你得等到天荒地老！这本质上就是计算机内部进行数字加法时面临的挑战。最直接的方法，就像我们那个奇怪的收银员一样，慢得令人沮丧。

行波的“暴政”

构建数字加法器最简单的方法是模仿我们学习在纸上做加法的方式：一次一列，从右到左。我们加上第一列的两个位（以及任何初始输入进位），生成一个和位和一个进位输出。这个进位输出随后“行波式”地成为下一列的输入进位。这个过程一列一列地重复，直到达到最高有效位。这种设计被恰当地命名为行波进位加法器（Ripple-Carry Adder, RCA）。

它简单直观，但有一个致命缺陷：它是时间的奴隶。第二位的加法器必须等到第一位的进位准备好才能工作。第三位必须等待第二位，第三十二位必须等待第三十一位。这形成了一个依赖链，一个延迟的级联，就像一排多米诺骨牌一个接一个地倒下。获得最终正确答案所需的时间与你相加的位数成正比。对于现代计算机中标准的32位或64位数字，这种延迟成为一个严重的瓶颈，限制了整个处理器的运行速度。

如果我们用高速示波器连接到一个4位RCA中每个阶段的进位输出信号，我们就能观察到这种行波效应。第一级的进位 $C_1$ 可能会在比如说 $2$ 纳秒后出现。 $C_2$ 会在 $4$ 纳秒时出现， $C_3$ 在 $6$ 纳秒时出现，而最终的进位 $C_4$ 在 $8$ 纳秒时出现。每个进位都必须依次等待。一定有更好的方法！

天才的火花：传递与生成

突破来自于改变提问的方式。我们不再问“前一级的进位是多少？”，而是问“在什么条件下，本级会产生一个进位输出？” 仔细想想，只有两种可能性。

让我们考虑第 $i$ 个比特位，我们正在对位相加 $A_i$ 和 $B_i$ ，并接收一个输入进位 $C_i$ 。一个进位输出 $C_{i+1}$ 将在以下情况下产生：

本级自身 生成（generates） 一个进位。当 $A_i$ 和 $B_i$ 都为1时会发生这种情况。在二进制中 $1+1=10$ ，所以无论输入进位是多少，都会生成一个进位。我们可以用一个我们称之为生成（Generate）的信号来捕捉这一点， $G_i = A_i \cdot B_i$ 。
本级传递（propagates）一个输入进位。当本级“准备好”传递一个进位时会发生这种情况。如果 $A_i$ 或 $B_i$ 中有一个为1（但不是两个都为1），它们的和就是1。如果一个输入进位 $C_i=1$ 到达，总和就变成 $1+1=10$ ，这个进位就被传递或传播到下一级。我们可以用一个我们称之为传递（Propagate）的信号来捕捉这个条件， $P_i = A_i \oplus B_i$ 。（ $\oplus$ 符号代表异或（XOR）运算）。

这种重新构建异常强大。“生成”信号告诉我们一个进位在此处诞生。“传递”信号告诉我们，如果一个进位到达此处，它将存活并继续前进。因此，进位输出 $C_{i+1}$ 的规则变得异常简单：如果本级生成一个进位，或者它传递一个输入进位，那么就会有一个进位输出。用布尔代数的语言来说：

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

更妙的是，这种新的思维方式也整理了我们的和计算。当输入（ $A_i, B_i, C_i$ ）中有奇数个1时，和位 $S_i$ 为1。这恰好是级联异或的定义。事实证明 $S_i = (A_i \oplus B_i) \oplus C_i$ ，这正是 $S_i = P_i \oplus C_i$ 。P信号起到了双重作用！

洞见未来

现在是见证奇迹的时刻。我们有规则 $C_{i+1} = G_i + P_i \cdot C_i$ 。它看起来仍然是顺序的，因为 $C_{i+1}$ 依赖于 $C_i$ 。但如果我们把它展开呢？

让我们从头开始，从整个加法器的初始输入进位 $C_0$ 开始。

第一级的进位输出是 $C_1 = G_0 + P_0 \cdot C_0$ 。很简单。

现在，对于第二级： $C_2 = G_1 + P_1 \cdot C_1$ 。我们不用等待 $C_1$ 计算出来，而是将其表达式代入 $C_2$ 的方程中：

$C_2 = G_1 + P_1 \cdot (G_0 + P_0 \cdot C_0) = G_1 + P_1 G_0 + P_1 P_0 C_0$

仔细看那个方程。 $C_2$ 的值现在只依赖于前两个级的P和G信号，以及初始进位 $C_0$ 。它不再依赖于 $C_1$ ！我们已经“超前看”过了第一级的计算。

让我们再为 $C_3$ 做一次，正如中所推导的：

$C_3 = G_2 + P_2 \cdot C_2 = G_2 + P_2(G_1 + P_1 G_0 + P_1 P_0 C_0)$ $C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$

一个模式出现了。每个进位都可以表示为一个（逐渐变大的）方程，它只依赖于P、G和初始的 $C_0$ 。这就是超前进位加法器（Carry-Lookahead Adder, CLA）的核心。

回报：并行的力量

为什么这是一场革命？因为所有独立的 $P_i$ 和 $G_i$ 信号都可以同时计算。它们只依赖于输入位 $A_i$ 和 $B_i$ ，而这些输入位是同时可用的。一旦所有的P和G都准备好了，一个专门的电路——超前进位单元（Carry Lookahead Unit, CLU）——就可以一次性并行地计算 $C_1, C_2, C_3, \dots$ 的方程。

多米诺骨牌链被打破了。我们不再有行波，而是一个单一、协调的计算。

如果我们回到示波器实验，CLA 的图像将截然不同。在计算P/G信号和CLU完成其工作的初始延迟之后，所有的进位—— $C_1, C_2, C_3, C_4$ ——似乎会在完全相同的时间点亮。对于一个具有典型门延迟的4位加法器，这可能意味着所有进位在 $4\tau$ 时稳定，其中 $\tau$ 是一个基本的门延迟单位。

这种并行性带来了巨大的速度提升。详细分析表明，对于一个4位加法器，获得最终和位的关键路径延迟可能从RCA的 $18$ 纳秒减少到CLA的仅 $10$ 纳秒——速度几乎快了一倍。RCA的延迟随位数线性扩展，即 $O(N)$ ，而CLA的延迟扩展得慢得多，像位数的对数，即 $O(\log N)$ 。

现实的挑战：扇入数问题

那么，为什么我们不直接建造巨大的、64位的单级CLA，然后一劳永逸呢？和许多绝妙的想法一样，这里有一个实际的难题。再看看 $C_3$ 的方程。它已经变得复杂了。 $C_4$ 的方程甚至更大：

$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$

为了实现这个逻辑，最终的或门需要5个输入。最后一个与门（ $P_3 P_2 P_1 P_0 C_0$ ）也需要5个输入。随着我们处理更高位数，这些方程的规模会爆炸性增长。对于一个 $n$ 位加法器，计算最终进位 $C_n$ 的逻辑需要具有 $n+1$ 个输入的门。这被称为门的扇入数（fan-in）。

物理晶体管不能被连接成具有任意大数量的输入。存在电气限制（电容、电阻），限制了实际的扇入数。一个常见的限制可能在8或9左右。这意味着单级CLA设计在物理上不可能超过大约 $n=8$ 位。我们宏伟的计划似乎碰壁了。

层次结构的优雅

工程师们有一个经典的解决方案来处理变得过于庞大的问题：分而治之。如果我们不能建造一个巨大的64位CLA，也许我们可以用更小的、可管理的部件来构建它。

让我们将64位分成16个4位的块。每个4位块可以是一个快速、高效的CLA。现在，问题是如何将进位从一个块传递到下一个块。我们可以让它在块之间行波式传播，这是一个不错的折衷方案。这种混合设计肯定比一个完整的RCA快，因为缓慢的行波每4位才发生一次，而不是每单个位。

但我们可以通过再次应用超前原理做得更好，只是在更高的层级上。对于整个4位块，我们可以定义一个组生成（group generate）（ $G^*$ ）和一个组传递（group propagate）（ $P^*$ ）信号。

如果4位块自身产生一个进位输出，而不管其输入进位如何， $G^*$ 就为真。
如果该块会将其输入进位一直传递到其进位输出， $P^*$ 就为真。

这些组信号可以从块内的单个P和G中导出。对于一个4位块，组传递就是 $P^* = P_3 P_2 P_1 P_0$ 。逻辑很清晰：要让一个进位跨越整个块传播，内部的每一位都必须准备好传递。 $G^*$ 的表达式更复杂，但遵循相同的超前逻辑。

一旦我们为所有16个块都得到了这些 $P^*$ 和 $G^*$ 信号，我们就可以将它们送入一个第二级超前进位单元。这个第二级LCU的工作不是计算位进位，而是计算块间的进位（ $C_4, C_8, C_{12}, \dots$ ）。逻辑与之前完全相同，只是用 $P^*$ 和 $G^*$ 代替了 $P$ 和 $G$ 。

这种层次化超前进位结构是工程学的杰作。延迟路径变为：

计算所有64位的所有P/G信号（1步）。
计算所有16个块的所有P*/G*信号（1步）。
第二级LCU计算所有16个块的进位（1步）。
这些块进位反馈到第一级CLA中，计算最终的和位（1步）。

结果是惊人的。一个以这种方式构建的32位加法器可以比其行波进位表亲快8倍之多。当然，扇入数问题并没有完全消失；它只是转移到了下一个层级。一个由16个块组成的64位加法器，其二级LCU将需要 $16+1=17$ 的扇入数。虽然具有挑战性，但这比单级设计所要求的65的扇入数要现实得多。

从一个简单、缓慢、循序渐进的过程，通过视角的转变——从计算到预测——我们找到了一种“洞见”加法未来的方法，打破了顺序时间的枷锁，为驱动我们世界的高速计算打开了大门。

应用与跨学科联系

既然我们已经掌握了超前进位那巧妙的内部机制，现在就可以开始真正的乐趣了。一个伟大科学原理的真正美妙之处不仅在于其自身的优雅，还在于它的影响能有多深远，能打开多少意想不到的大门。超前进位不仅仅是加速算术运算的技巧；它是一种关于远见和并行性的更深层次思想的体现。让我们踏上一段旅程，看看这一个绝妙的概念如何在广阔的数字工程领域中回响，甚至触及理论计算机科学的抽象王国。

机器的心脏：革新计算机算术

从本质上讲，超前进位生成器是高速计算的引擎。你用过的几乎每一块微处理器，其速度都归功于这个思想。在上一章中，我们看到了如何通过同时“窥视”所有前面的输入位来推导出进位位的逻辑。通过展开递归进位方程 $C_{i+1} = G_i + P_i C_i$ ，我们可以直接用初始输入来写出任何进位的表达式，比如 $C_3$ 。这种从顺序依赖链到并行、两级逻辑结构的转变是关键。这就像一群人一个接一个地传递秘密，与一个观察者一次看到所有人的状态来推断最终结果之间的区别。

但是当我们需要像现代CPU那样进行64位或128位数字的加法时，会发生什么呢？为 $C_{63}$ 写一个单一的超前方程将是极其复杂的。在这里，工程师们借鉴了一个永恒的策略：分而治之。我们不建造一个巨大的加法器，而是构建更小的、可管理的4位或8位CLA块，然后创建一个第二级、更高层次的超前单元，该单元处理来自这些块的“块传递”和“块生成”信号。这创造了一个优美的层次化结构。这是一种“超前的超前”，一个将复杂性和延迟都降至最低的组织杰作。

这个强大的算术核心也是一个伪装大师。稍加巧思，计算 $A+B$ 的同一硬件也可以计算 $A-B$ 。通过使用二进制补码法——即将B的各位取反再加1——我们可以将减法转化为加法。“加1”的部分通过将加法器的初始输入进位 $C_0$ 设置为1来优雅地处理。因此，一个单一的控制信号就可以使该单元在加法和减法之间切换，为我们提供了一个通用且高效的算术逻辑单元（ALU）。

为了追求极致的速度，我们可以引入一种直接来自工厂流水线的技术：在处理器设计中称为*流水线技术（pipelining）。我们不是等待一个完整的64位加法完成后才开始下一个，而是可以将计算分解为多个阶段。一个流水线寄存器，充当缓冲器，被插入到关键路径的某个位置。第一阶段完成部分工作并将其结果传递给寄存器。在下一个时钟周期，第二阶段处理该结果，而第一阶段则开始下一次加法。通过仔细放置这个寄存器，例如，在超前逻辑的与门和或门平面之间，我们可以完美地平衡每个阶段的延迟。得到第一个结果的时间（延迟）保持不变，但我们得到后续*结果的速率（吞吐量）却大大增加。

一个普适原则：“超前”思想的释放

传递和生成的概念是如此强大，以至于将其局限于加法实在是太可惜了。事实上，它出现在最令人意想不到的地方。

考虑一个算术右移位器，这个操作将一个数除以2的幂。通常，我们需要根据被移出的位来对结果进行舍入。例如，如果被丢弃的最高有效位是'1'，我们可能需要对结果加1。这个“加1”操作似乎需要另一个缓慢的加法器。但并非必须如此！我们可以将这个舍入操作重新构想为一个“进位”问题。向上舍入的信号充当初始进位 $C_0$ 。数字本身的位则充当传递信号——如果一个位是‘1’，它将传递输入的“向上舍入”信号；如果它是‘0’，它将吸收该信号。这里不需要生成信号，因为我们只加0或1。通过这种巧妙的重构，我们的超前机制可以在移位器上执行高速舍入，展示了抽象的优美力量。

同样的模式再次出现在同步计数器中，这些电路在每个时钟脉冲时向前计数。对于一个二进制计数器的位 $Q_k$ 要发生翻转，所有比它低位的位（ $Q_{k-1}, \ldots, Q_0$ ）必须都为‘1’。这听起来熟悉吗？这是一个传播链！翻转第 $k$ 位的条件， $T_k = Q_{k-1} \land Q_{k-2} \land \ldots \land Q_0$ ，恰好类似于一个进位通过一系列都处于“传递”状态的位进行传播。通过使用超前逻辑并行计算这些翻转条件，我们可以构建能够在极高速度下递增的计数器，而没有简单设计的行波效应。

进一步扩展我们的视野，超前进位加法器不仅仅是独立的单元；它们是更复杂计算结构内部的关键组成部分。以硬件乘法器为例。一种常见的将两个大数（比如64位乘以64位）相乘的方法是使用Wallace树。这种架构首先生成一个部分积数组，然后使用一个由简单加法器组成的树将这许多行减少到只有两行。接下来会发生什么？这两行最终必须相加以产生最终的乘积。这个最终的加法通常是整个乘法过程中最慢的一步。为了使其快速，工程师们采用了一个宽的、高度优化的超前进位加法器。整个乘法器的性能取决于其最终CLA阶段的速度。

从硅片到理论：更深层次的联系

超前原理的抽象之美在硅芯片的物理世界中找到了一个非常具体的归宿。当在复杂可编程逻辑器件（CPLD）上实现一个设计时，器件自身的架构起着巨大的作用。CPLD非常擅长以固定的、可预测的延迟实现宽泛的积之和（SOP）逻辑函数。展开的超前进位方程天然地就是这种SOP形式。相比之下，一个简单的行波进位加法器，由于其长串的顺序依赖关系，无法利用这一架构特性。因此，对于给定的位宽，CLA在CPLD上可以显著更快，这不仅因为其逻辑更并行，还因为它与底层硬件平台完美匹配。

这引导我们对整个过程有了一个更通用、也更深刻优雅的看法。所有超前式加法器都围绕一个基本的结合律算子构建，我们称之为 $\circ$ ，它组合了两个（生成，传递）对：

(g_2, p_2) \circ (g_1, p_1) = (g_2 \lor (p_2 \land g_1), p_2 \land p_1)

这个算子本质上是说：“给定每个子块的状态，组合块（1和2）的生成/传递状态是什么？” 像Kogge-Stone加法器这样的高级设计，不过是这些 $\circ$ 算子节点的高效、对数深度的网络，被安排用来并行计算所有比特位的前缀。这揭示了支撑所有这些看似临时的工程技巧的优美、形式化的数学结构。

最后，我们来到了最抽象，或许也是最深刻的联系：与计算复杂性理论的联系。理论家根据解决问题所需的资源来对问题进行分类。类别 $AC^0$ 包含了可以用具有常数深度（无论输入 $n$ 有多大）和多项式数量门的电路解决的问题，前提是这些门可以有无限数量的输入（无界扇入）。一个简单的行波进位加法器，其深度随位数线性增长（ $O(n)$ ），显然不在 $AC^0$ 中。

但超前进位加法器则不同。每个进位位的展开公式是许多与项的大或运算。使用无界扇入门，这个公式可以用常数深度的电路实现——一个与门层和一个或门层。因为这对每个进位位都成立，所以整个 $n$ 位加法问题都可以在常数时间内解决！因此，超前进位方法证明了二进制加法从根本上属于复杂性类别 $AC^0$ 。从理论角度看，这对于并行计算机来说是一个“简单”的问题。

从一个简单的提速技巧到一个CPU设计的基石，一个数字逻辑中的普适原则，以及复杂性理论中的一个深刻例子，超前的思想展示了科学与工程的卓越统一。它教导我们，有时，最快的前进方式是首先退后一步，纵览全局。