Wallace and Dadda Multipliers
Wallace and Dadda trees reduce a grid of partial products to two rows in logarithmic depth, making hardware multiplication fast.
Partial-Product Reduction
Multiplying two n-bit numbers produces an n-by-n grid of partial products, one for each pair of input bits. Adding them naively with a chain of adders is slow. Wallace and Dadda multipliers instead build a tree of carry-save adders (3:2 compressors) that shrinks the grid to two rows in a number of stages proportional to log n.
Once two rows remain, a single fast carry-propagating adder produces the final product. The tree does the bulk of the work in parallel; the carry chain is paid only once.
Wallace Trees
A Wallace tree is greedy: at every stage it groups the bits in each column into as many full adders (and half adders) as possible, reducing three bits to two wherever three are available. It minimizes the number of reduction stages, which tends to minimize delay, but it can use more adder cells and produce an irregular, wire-heavy layout.
Dadda Trees
A Dadda multiplier reaches the same logarithmic depth but is lazy: it uses the fewest adders needed to keep each column within the next target height in the reduction sequence (2, 3, 4, 6, 9, 13, ...). It defers reduction, so it typically uses fewer full adders than Wallace and a slightly wider final adder.
- Wallace: reduce aggressively each stage, more cells, same depth
- Dadda: reduce just enough to hit height targets, fewer cells
- Both: log-depth reduction, one final carry-propagate adder
Practical Use
These structures appear in the multiply units of CPUs, GPUs, and DSPs, and in any accelerator that runs many multiply-accumulate operations. Booth encoding is often combined with them to halve the number of partial-product rows before reduction begins, cutting tree height further.
The choice between Wallace and Dadda is usually settled by the synthesis tool and the target library. Dadda's smaller cell count is attractive for area; Wallace's regularity can help routing. In deeply pipelined arithmetic the reduction tree is split across pipeline stages so the multiplier can accept a new pair of operands every clock cycle.