极客工场

Appearance

共 1,622 字预计阅读约 5 分钟

Wallace/Dadda 压缩树：让乘法器快起来的关键 ​

更新时间：2026-09-12。本文是「集成电路大类 · 芯片设计」进阶层（intermediate）数字逻辑第四十八篇。乘法器基础讲了部分积和阵列乘法，这一篇讲高性能乘法器为什么快——在最终相加之前，先用全加器把一大堆部分积压缩成两行。

本文要回答的问题 ​

  • 阵列乘法器慢在哪？「进位保留」和「进位传播」差在哪？
  • 全加器怎么当 3:2 压缩器用？carry 为什么进的是高一列而不是本列？
  • Wallace 和 Dadda 两种压缩策略各自动机是什么，谁面积小、谁层数少？
  • 4:2 压缩器为什么在布局布线上特别好用？
  • Booth 编码、符号扩展和最后的快速加法器在整个层次里处于什么位置？

一、先压缩，最后才传播进位 ​

n×n 无符号乘法先用与门产生 n 行部分积，每行按权重左移。朴素阵列乘法把它们逐行进进位传播加法器，进位要一路向高位串，关键路径长。

快速乘法器换思路：在压缩阶段绝不沿整行传播进位，而是把每一列「同权重」的 bit 用全加器归并。一个全加器在这里不叫「加法器」而叫 3:2 压缩器（3:2 compressor / carry-save adder）：吃进同列 3 个 bit，吐出本列的 sum（权重同列）和 carry（权重是左边高一列）。每用一层，部分积行数大致按 3→2 收缩，进位只在列与列之间落位、不形成横向长链——这叫进位保留（carry-save）。

压缩到只剩 2 行后，才用一个普通的快速进位传播加法器（CPA，如 CLA/前缀加法器）把这两行一次合并成最终积。于是乘法延迟 = 「产生部分积」+「O(log n) 层压缩」+「一次快速加法」，远优于阵列的线性进位。

二、Wallace：尽快压到两行 ​

Wallace 树的策略是激进压缩：每一层对每一列尽可能多地放 3:2 压缩器，让行数尽快下降。n 行 → 约 ⌈2n/3⌉ → 约 ⌈2/3·…⌉，层数约 log₁.₅ n。逻辑层数（延迟）最少，但用的全加器多、布线呈不规则树状、布通难度大。

三、Dadda：尽量晚压缩，省全加器 ​

Dadda 树相反，追求用最少的全加器：先算出「为了在目标层数内压到两行，每层每列最多允许多高」，只有当某列高度超过该层允许值时才放压缩器，能不动就不动。因为 3:2 压缩器每用一个都会把 1 个 bit「变成」进位送到高列，总数并非无脑减少，Dadda 的规则保证总全加器/半加器数最少，代价是压缩层数可能略多（通常比 Wallace 多至多一层）、关键路径稍长。两者最终都压到两行、再用同样宽度的 CPA，乘积完全相同，差别只在中间的面积-延迟权衡；实践中还有介于二者之间的策略。

四、4:2 压缩器、Booth 与完整乘法器层次 ​

  • 4:2 压缩器：表面吃 4 进 2，内部是两个全加器串接并把进位专门引到高列，关键是它有规整的「块」边界、内部进位不横向乱串，在标准单元布局里能排成整齐阵列、布线和时序都友好，是高性能乘法器的主力积木。
  • Booth 编码：基-4 Booth 一次检查乘数 3 位，把部分积行数直接减半（允许 ±1、±2 倍被乘数），有符号数还能自然处理负权，显著降低压缩树规模；代价是产生部分积时要做取反和 +1 修正。
  • 符号扩展修正：有符号部分积每行都要正确符号扩展，朴素补一堆 1 面积大，经典做法用 Baugh-Wooley 或取反加常量，把符号位折叠成少量常量项。

完整高速乘法器层次：部分积产生（AND/Booth）→ 压缩树（3:2、4:2，Wallace/Dadda）压成 S、C 两行 → 一次快速 CPA（CLA/并行前缀）合并。浮点尾数乘法、DSP48 MAC、通用处理器乘法指令内部都是这个骨架；再叠加压缩树的流水线切分，可做到高主频高吞吐。

与现有篇目的衔接 ​

总结 ​

一句话总结：快速乘法器不在压缩阶段沿整行传播进位，而把全加器当 3:2 压缩器，对每一列同权 bit 归并——sum 留本列、carry 落左列，使部分积行数按约 3→2 逐层收缩（进位保留），直到只剩两行才用一次快速进位传播加法器合并，延迟由阵列乘法的线性进位降为「部分积产生 + O(log n) 压缩层 + 一次 CPA」；Wallace 树每层尽量多压、层数最少但全加器多且布线不规则，Dadda 树只在列高超限时才压、总加法器数最少、面积小但可能多至多一层，二者乘积相同只是面积-延迟折中；4:2 压缩器因边界规整利于布局而成为主力，基-4 Booth 编码把部分积行数减半并自然处理有符号数，符号扩展用 Baugh-Wooley 折叠成常量项，最终构成「部分积产生→压缩树→CPA」的标准高速乘法器骨架，也是浮点尾数乘法和 DSP MAC 的内核。