关于先行进位加法器延迟的思考

最近在复习 COA 加法器的部分，发现对于加法器延迟的运算隐含了一些假设：

1. 逻辑门输入的数量是无限制的
2. 逻辑门输入的数量与逻辑门的延迟是无关的

这里逻辑门输入的数量即为扇入

也就是说，在给定的延迟下，无论加法器的位数是多少，全先行进位加法器的延迟是固定的。

这显然与实际是不一致的，逻辑门如果在物理上具有太多的扇入，由于输入级电路会增加器件等效的电容，整个逻辑门将产生一定的传输延迟。

课件中指出，引入部分先行进位加法器是为了在计算时间和硬件复杂度之间取得权衡。在这里，降低硬件复杂度本身就是减少逻辑门的扇入，而这在某种程度上，也减少了逻辑门的传输延迟。尽管这种效应可能不及硬件结构改变后计算时间的增加。

另一方面，在给定的扇入下，可以设计硬件结构，进一步优化部分先行进位加法器的延迟。

考虑如下的逻辑门属性：

• 与门延迟 → 1 ty
• 或门延迟 → 1 ty
• 异或门延迟 → 3 ty
• 逻辑门最大扇入为 8

这里的想法是让模块间的进位信号也能快速传递，基本思路是基于辅助函数 $p_i$ 和 $g_i$，设计第二层超前进位电路。

这里是课件中的部分先行进位加法器的结构图：

我们需要让模块间的进位信号 $C_8,C_{16},C_{24},C_{32}$ 能够快速传递，为此写出这些信号的原始表达式。

记 $p_i = x_iy_i,g_i = x_i+y_i$，则 $C_8 = G_0 + P_0C_0$，其中：

• $G_0=g_7+p_7g_6+p_7p_6g_5+\cdots+p_7p_6p_5p_4p_3p_2p_1g_0$
• $P_0=p_7p_6p_5p_4p_3p_2p_1p_0$

类似的有 $C_{8i+8} = G_{i} + P_iC_{8i}$，其中：

• $G_i=g_{8i+7}+p_{8i+7}g_{8i+6}+p_{8i+7}p_{8i+6}g_{8i+5}+\cdots+p_{8i+7}p_{8i+6}p_{8i+5}p_{8i+4}p_{8i+3}p_{8i+2}p_{8i+1}g_{8i}$
• $P_i=p_{8i+7}p_{8i+6}p_{8i+5}p_{8i+4}p_{8i+3}p_{8i+2}p_{8i+1}p_{8i}$

在这种方案下，电路结构图如下：

我们可以使用 $G_i$ 和 $P_i$，在电路复杂性和延迟之间进行进一步优化：

• $p_i$ 和 $g_i$ 的延迟为 $1$
• $P_i$ 和 $G_i$ 的延迟为 $3=1+2$
• $C_i$ 的延迟为 $5$ 或 $7$
  • $C_8, C_{16}, C_{24}, C_{32}$ 为 $5=3+2$
  • 其余为 $7=5+2$
• $S_i$ 的延迟为 $10=7+3$

即最大延迟为 10ty，优于课件中的 12ty，并且，在加法器运算位数增加的情况下，这里的延迟不会发生变化（见最后的勘误），而课件中的延迟会相应的增大。

这里的关键是，充分利用逻辑门的最大扇入。实际上，这里的假定的最大扇入仍然有点多，我们可以进一步减少扇入为 4，于是相应的将 CLA 和第二层超前进位电路设计为 4 位即可。

参考资料：

• 扇入 - 维基百科
• Fundamentals of Digital Logic with Verilog Design

勘误：

• 在加法器运算位数增加的情况下，优化后的结构要想延迟不发生变化，需要满足 模块数 ≤ 最大扇入 - 1 的条件，否则会超出最大扇入的限制。
• 可以将条件弱化为 模块数 ≤ 最大扇入，此时最高位的进位通过模块中的第一层超前进位电路得到，而非通过第二层超前进位电路得到。