Wallace multiplier

A Wallace tree is an efficient hardware implementation of a digital circuit that multiplies two integers, devised by Australian Computer Scientist Chris Wallace in 1964.

The Wallace tree has three steps:

The second phase works as follows. As long as there are three or more wires with the same weight add a following layer:

The benefit of the Wallace tree is that there are only ${\displaystyle O(\log n)}$ reduction layers, and each layer has ${\displaystyle O(1)}$ propagation delay. As making the partial products is ${\displaystyle O(1)}$ and the final addition is ${\displaystyle O(\log n)}$, the multiplication is only ${\displaystyle O(\log n)}$, not much slower than addition (however, much more expensive in the gate count). Naively adding partial products with regular adders would require ${\displaystyle O(\log ^{2}n)}$ time. From a complexity theoretic perspective, the Wallace tree algorithm puts multiplication in the class NC¹.

...
Wikipedia