最近刚通关图灵完备，作为一个没有学过计算机专业课的人来说，玩的过程中也算是对逻辑电路有了一点点了解。

不知道是不是我的 mac 配置不够的问题，我已经在搭原件的时候遇到两四次死机的情况了。本来还想尝试加一下 risc-v 指令集呢，还是先搁置吧。

基础实现

加法器的输入是两个八位数字 $x$，$y$ 以及进位 $c$，计算 $x+y+c$ 以及输出进位。

一个最基础，同时也是最直观的实现，就是模拟手工计算的过程。这里我们定义 $x_i$，$y_i$ 分别是输入的第 $i$ 位，$s_i$ 以及 $c_i$ 则是第 $i$ 位的输出值和进位。其流程如下：

  • 计算第 0 位的输出以及进位，其中 $s_0 = x_0 \oplus y_0 \oplus c $, $c_0 = (x_0 \land y_0) \lor (x_0 \land c) \lor (y_0 \land c)$。为了方便起见，我们把传入的进位定义为 $c_{-1}$。
  • 把第 0 位得到的进位和第一位计算得到 $s_1$ 和 $c_1$。
  • 以此类推，得到所有八位输出以及最终进位 $c_7$。

其实这里就是把 8 个全加器连接起来。

改写一下

第一个方法很简单，很直白，除了慢了点，没啥缺点。这种实现也有个名字，叫行波进位。容易看出，每一位的计算需要 7 个原件，延迟主要来自 $c_i$ 的计算，抛开能预计算得到的部分，延迟是4。

这里原件是指 xor，nor 之类的，延迟也是游戏里的定义，不玩游戏的话不用关心。

不过这其实并不是最简形式，首先我们给预计算部分进行一下定义（至于为什么叫 $p$ 和 $g$ 后面就会知道了）：

$$ \begin{aligned} g_i &= x_i \land y_i \\ p_i &= x_i \oplus y_i \end{aligned} $$

注意力惊人的人可以发现，$c_i$ 也可以改写为：

$$ c_i = (x_i \land y_i) \lor \left(c_{i-1} \land (x_i \oplus y_i)\right) $$

诶，这时候第 $i$ 位的计算就可以写成如下形式，延迟也降低了1。

$$ \begin{aligned} s_i &= p_i \oplus c_{i-1} \\ c_i &= p_i \lor (g_i \land c_{i-1}) \end{aligned} $$

快一点

虽然但是，目前大部分计算仍然是串行执行的，每一位的计算都依赖于前一位的结果。想要让速度快起来，就必须找到一种方式能够进行并行计算。

先来看 $c_i$ 的计算，我们来展开看看：

$$ \tag{1} \begin{aligned} c_i &= g_i \lor (p_i \cdot c_{i-1}) \\ &= g_i \lor (p_i \cdot (g_{i-1} \lor (p_{i-1} \cdot c_{i-2}))) \\ &= g_i \lor (p_i \cdot (g_{i-1} \lor (p_{i-1} \cdot (g_{i-2} \lor (p_{i-2} \cdot c_{i-3}))))) \\ &= g_i \lor (p_i \cdot g_{i-1}) \lor (p_i \cdot p_{i-1} \cdot (g_{i-2} \lor (p_{i-2} \cdot c_{i-3}))) \\ &= g_i \lor (p_i \cdot g_{i-1}) \lor (p_i \cdot p_{i-1} \cdot g_{i-2}) \lor (p_{i} \cdot p_{i-1} \cdot p_{i-2} \cdot c_{i-3}) \\ &= \cdots \end{aligned} $$

括号太多了，就不继续展开了，总之最后这个式子一定能展开到 $c_{-1}$。这里很多部分都是能够并行计算的（例如四个 and/or 可以在 2 延迟内完成），因此总延迟也就降低了。

好处说完了就有坏处，为了提高并行度势必要引入更多的原件，当然这也是不可避免的 trade-off。

这个方法也有个名字，叫超前进位加法器 (Carry-Lookahead Adder)。

分而治之

我们在上面展开三位的时候，就已经十分复杂了，实际上总电路规模会随着位数以二次的速率上升，这对于 8 位计算来说是不可接受的，所以就要祭出分治的思想。

分块超前进位就是将输入拆成多个块，分别计算超前进位，最后再拼接起来。例如我们可以将八位的输入拆成两个四位的块，下图展示了其中一块的输入与输出：

       gi,gi+1,gi+2,gi+3      pi,pi+1,pi+2,pi+3
                |                       |
                v                       v
q[i,i+3] <--- +--------------------------------+ <--- ci-1
p[i,i+3] <--- |      4bit 超前进位链块         |
              +--------------------------------+
                           |
                           v
                      ci,ci+1,ci+2

基于上一节里的展开，如果我们分别定义 $g_{[i, j]}$ 和 $p_{[i, j]}$ 为:

$$ \tag{2} \begin{aligned} g_{[i, j]} &= g_j \lor (p_j \cdot g_{j-1}) \lor \cdots \lor (p_j \cdot p_{j-1} \cdots g_{i}) \\ p_{[i, j]} &= p_j \cdot p_{j-1} \cdots p_{i} \end{aligned} $$

进位输出就可以表示为：

$$ c_i = g_{[i, j]} \lor (p_{[i, j]} \cdot c_{j-1}) $$

由于 $p_{[i, j]}$ 和 $g_{[i, j]}$ 的计算同样不依赖前导位，因此可以先并行计算出每个块必要的数据，然后从 $c_{-1}$ 开始，得到每一块的输出，以及需要传递给下一位的进位。

到这里就可以解释 $p$ 和 $g$ 分别是什么了：

  • $p$ (propagate)：进位传播，即当前位是否能将来自上一位的进位传递下去。
    • $p_{[i, j]}$ 的理解也很直接，只有从 $i$ 到 $j$ 的每一位都能传播时，这个块才能传播传入的进位。
  • $g$ (generate)：进位生成，即当前位是否生成了到下一位的进位。
    • $g_{[i, j]}$ 同理，当前位产生了进位只有两种情况，自身有进位或者前一位有进位且自己能传播它，以此类推。

下文里我们将这两个值统称为块信号。

还不够？

分块超前进位的串行度由块数决定，有没有办法再快一点呢？

有的，朋友有的，重新回到公式(1)，注意到这一行：

$$ c_{i} = {\color{#9a4638} g_i \lor (p_i \cdot g_{i-1})} \lor ({\color{#9a4638} p_i \cdot p_{i-1}} \cdot ({\color{#4a7c7b} g_{i-2}} \lor ({\color{#4a7c7b} p_{i-2}} \cdot c_{i-3}))) $$

有感觉吗？我们把公式(2)代入：

$$ \begin{aligned} c_{i} &= g_{[i, i-2]} \lor (p_{[i, i-2]} \cdot c_{i-3}) \\ &= g_{[i, i-1]} \lor (p_{[i, i-1]} \cdot (g_{[i-2, i-2]} \lor (p_{[i-2, i-2]} \cdot c_{i-3}))) \\ &= g_{[i, i-1]} \lor (p_{[i, i-1]} \cdot g_{[i-2, i-2]}) \lor (p_{[i, i-1]} \cdot p_{[i-2, i-2]} \cdot c_{i-3}) \\ \end{aligned} $$

不失一般性，对于 $i < j < k$，我们可以从中归纳出如下公式：

$$ \begin{aligned} g_{[i, k]} &= g_{[j, k]} \lor (p_{[j, k]} \cdot g_{[i, j-1]}) \\ p_{[i, k]} &= p_{[i, j-1]} \cdot p_{[j, k]} \\ c_{i} &= g_{[0, i]} \lor (p_{[0, i]} \cdot c_{-1}) \\ s_{i} &= p_{i} \oplus c_{i} \end{aligned} $$

也就是说，相邻的块信号是可以合并的。

为了便于描述，这里定义 $Q_{[i, j]} = (g_{[i, j]}, p_{[i, j]})$，以及对应的计算 $\cup$

$$ Q_{[i, j]} = Q_{[i, j-1]} \cup Q_{[j, k]} $$

这时候，问题就变成了

  • 已知所有长度为 1 的块信号，$Q_{[i, i]} (i = 0\dots 7)$，如何计算 $Q_{[0, i]} (i = 0\dots 7)$

这个问题没有唯一解，所有基于此产生的加法器，可以统称为 并行前缀加法器(Parallel-Prefix Adder)。

一种常见的结构叫做 Kogge-Stone 结构，总共需要三层计算：

  • 第0层是所有 $Q_{[i, i]}$。
  • 第一层将相邻的信号合并，得到 $Q_{[i, i+1]}$。
  • 第二层中，对上一层得到的信号进一步进行跨度为2的合并，得到 $Q_{i, i+3]}$。
  • 最后一层中，再次对上一层的信号进行跨度为4的合并，最终得到所有 $Q_{[0, i]}$。

可以对照下面的表格来品一下上面的合并逻辑。

╔══════════╦═══════╦═══════╦═══════╦═══════╦═══════╦════════╦════════╦════════╗
║ Lvl/Bit  ║  0    ║  1    ║  2    ║  3    ║  4    ║  5     ║  6     ║  7     ║
╠══════════╬═══════╬═══════╬═══════╬═══════╬═══════╬════════╬════════╬════════╣
║   L0     ║ [0]   ║ [1]   ║ [2]   ║ [3]   ║ [4]   ║ [5]    ║ [6]    ║ [7]    ║
╠══════════╬═══════╬═══════╬═══════╬═══════╬═══════╬════════╬════════╬════════╣
║   L1     ║ [0]   ║ [1,0] ║ [2,1] ║ [3,2] ║ [4,3] ║ [5,4]  ║ [6,5]  ║ [7,6]  ║
╠══════════╬═══════╬═══════╬═══════╬═══════╬═══════╬════════╬════════╬════════╣
║   L2     ║ [0]   ║ [1,0] ║ [2,0] ║ [3,0] ║ [4,1] ║ [5,2]  ║ [6,3]  ║ [7,4]  ║
╠══════════╬═══════╬═══════╬═══════╬═══════╬═══════╬════════╬════════╬════════╣
║   L3     ║ [0]   ║ [1,0] ║ [2,0] ║ [3,0] ║ [4,0] ║ [5,0]  ║ [6,0]  ║ [7,0]  ║
╚══════════╩═══════╩═══════╩═══════╩═══════╩═══════╩════════╩════════╩════════╝

感谢 d 老师生成的表格🥹。

除了这种结构外，还有 BK，LF 等结构，就不在此展开了。

结语

到此，我们就成功地设计出了一个高速的加法器。作为一个从没有接触过这方面的小白来说，最终能在游戏里搭建并跑通这个电路还是很有成就感的。

当然，我实际的心路历程是和本文相反的，最初是在 b 站的评论区里发现了超前进位、并行前缀等术语，然而我一点也看不懂，就直接扔给了 d 老师，让 d 老师帮我生成具体的执行步骤，我只管搭建。虽然运行通过了，但是我一点也不理解我在做什么，什么是 $p$，什么是 $g$，为啥要这么合并，为啥要合并三层。

后来在知乎找到了一系列的文章（请看参考），写的非常好，娓娓道来，总算是弄明白了我在做什么。

虽然搞明白这个好像并没有什么卵用，就权当浪费了几天来自娱自乐了（当你看到这里的时候，你也浪费了宝贵的 6 分钟）。

参考