a Wallace-tree multiplier

Shift-and-add multiplies in a loop, one partial product per cycle, which is slow. A Wallace-tree multiplier instead lays out every partial product at once and then races to add them all together as fast as a tree of small adders allows. Picture being handed forty receipts to total: adding them one by one is slow, but if you split into groups, total each group in parallel, then combine the group totals, you finish in far fewer rounds. The Wallace tree is that parallel grouping applied to the columns of partial products.

First, all the partial products are generated simultaneously — for an n-bit by n-bit multiply that is up to n shifted rows (often halved first by Booth encoding). The key device is a carry-save adder: it takes three numbers and reduces them to two (a sum vector and a carry vector) without ever propagating a carry across the word, so it is fast and its delay does not depend on width. The tree applies carry-save adders in layers, each layer turning three partial-sum rows into two, shrinking the pile of rows by a factor of about 3-to-2 per level. After roughly logarithmically many levels only two rows remain, and a single ordinary fast adder (a lookahead or prefix adder) adds those last two to produce the final product. The slow carry propagation happens just once, at the very end.

The result is a multiplier whose delay grows like the logarithm of the operand width rather than linearly — the standard choice when multiply throughput matters, as in signal processing and machine-learning hardware. The honest cost is area and power: you are building a thicket of adders to do in space what shift-and-add did in time. A regular array multiplier is the simpler, more layout-friendly cousin (slightly slower, easier to wire); Wallace and the related Dadda tree minimize the number of adder levels at the expense of a more irregular structure.