华莱士树和达达乘数之间的差异

Question

谁能说出华莱士乘法器和达达乘法器之间的部分乘积减少方法或机制的区别？

我一直在阅读A_comparison_of_Dadda_and_Wallace_multiplier_delays.pdf

Answer 1

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

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

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

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

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

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

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

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