add - Differences between Wallace Tree and Dadda Multipliers

Question

Could anyone tell the difference in the partial products reduction method or mechanism between Wallace and Dadda multipliers ?

I have been reading A_comparison_of_Dadda_and_Wallace_multiplier_delays.pdf

Answer 1

两者都非常相似。与传统的基于行的算法不同，它们都旨在实现 A*B 乘以 1/ 将 A 与位 b_i 相乘，2/ 计算每列的位，直到只有两行，并且 3/ 快速执行最终加法加法器。

我研究了一个 Dadda 乘数，但这是很多年前的事了，我不确定是否记得所有细节。据我所知，主要区别在于计数过程。

华莱士引入了“华莱士树”结构（在某些设计中仍然有用）。这允许在给定 n 位的情况下计算该集合中为 1 的位数。一棵 (n,m) 华莱士树（其中 m=ceil(log_2 n)）给出 n 个输入中为 1 的位数，并在 m 位上输出结果。这在某种程度上是一个组合计数器。例如，下面是用全加器（即 (3,2) 华莱士树）制成的 (7,3) 华莱士树的示意图。

如您所见，如果输入位的权重为 2^0，则此树生成逻辑权重为 2^0、2^1 和 2^2 的结果。

这允许快速降低列的高度，但在门数方面可能会效率低下。

Luigi Dadda 没有使用如此激进的减少策略，而是试图保持柱子的高度更加平衡。仅使用全加器（或半加器），每次计数/减少只会生成权重 2^0 和 2^1 的位。减少过程效率较低（从图中的行数较多可以看出），但门数更好。Dadda 策略的时间效率也应该稍低，但根据随附的论文，我不知道，这不是真的。

Wallace/Dadda 乘法器的主要兴趣在于它们可以实现具有 ~log n 时间复杂度的乘法，这比带有进位保存加法器的传统 O(n) 数组乘法器要好得多。但是，尽管有这种理论上的优势，但它们并没有真正被使用。目前的架构更关注吞吐量而不是延迟，并且更喜欢使用更简单的阵列结构而不是有效的流水线。实现 Wallace/Dadda 结构是一场真正的噩梦，除了几位之外，由于它们的不规则结构，向它们添加管道非常复杂。

请注意，其他乘法器设计产生 log n 时间复杂度，具有更常规和可实施的分治策略，例如 Luk-Vuillemin 乘法器。