这个硬件级的并行乘法算法正确吗？

Question

我是一名本科生，正在学习计算机体系结构教科书中介绍硬件级并行乘法算法的部分。如图所示，该算法在加法阶段涉及到一个顺序剥离过程，即按照 1、1、2、4、8、16 的顺序从正面和背面“剥离”比特，直接进入到来自树的更高级别的输出。

这表明我们只需使用 64 位加法器即可在

log_2(64)

次迭代后完成 64 位乘法。

虽然我了解较低位的“剥离”过程，但我不确定此过程对于较高位是否同样有效。我们是否应该考虑进位产生的影响？这让我怀疑这本书的内容可能有一些不准确的地方。

为了说明我的观点，请考虑

4'b1111

和

4'b1000

的乘法。结果应该是

8'b01111000

，但在这种情况下，第一步似乎不可能剥离“0”。有人可以帮我澄清一下吗？

Answer 1

4'b1111

x

4'b1000

的前两个部分积是

8'b01111000

和

8'b00000000

（

的左移副本乘以 0 或 1）。

或者如果你用其他方式来做，

8'b01000000

和

8'b00100000

当你添加它们时，它们都不会进位到高位，并且所有部分乘积都有一个前导

，所以这不是第一步的反例。

该图的问题在于，他们甚至在第一步加法之前就剥离了结果的高位，所以它总是 0？或者，如果他们正在查看较低位，则不依赖于较低位。但是

0b1111 * 0b1111

是

0b11100001

，它设置了高位。

所以我同意你的观点，这似乎没有意义。

如果第一个“剥离”位来自第一次添加之后，那么它可能会起作用，因为如果在第一步中没有发生，添加相同数字的移位副本可能会使从最顶部的进位变得不可能。（但我不确定这是否属实，并且没有尝试过一些测试用例，例如

0b1011

x

0b1111

，或其他设置位之间只有一个零的情况。）

这表明我们只需使用 64 位加法器即可在
log_2(64)
次迭代后完成 64 位乘法。

不，不仅仅是单个 64 位加法器的 6 次使用！他们并不是说您需要更少的加法器或加法运算，而是使用整数加法的结合性来执行

(a+b) + (c+d)

而不是顺序操作，因此对于相同的工作量，延迟会更低。因此，它们仍然有 63 个 64 位加法器，排列在树中，而不是单个

total += partial_product[i]

依赖链。

这是一个完整的乘法，因此他们仅使用 63x 64 位加法器就能产生 128 位结果。

有趣的事实：您可以做得比他们所展示的更好，只需在每个加法步骤中不完全传播进位，而是使用采用位和进位输入的加法器，或者类似 IIRC 的东西。关键是树的每一层仅具有

O(1)

延迟，而不是 n 位加法器的

O(log n)

（使用进位超前或类似技巧。）