I was looking at this wallace tree diagram for an 8x8 multiplier:
and I'm confused about why the pairs of two (and the one pair of 3) are not added together in the initial reduction layer. My understanding is that all pairs of three should be sent into a full adder and all pairs of two should be sent into a half adder. Is this diagram incorrect, or is my understanding incorrect?
The pairs of 3 are sent to a carry-save adder, which takes a sum of 3 inputs and reduce it to a sum of 2 inputs (x + y + x => c + s). A carry-save adder's propagation time is constant, while traditional a 2 input adder's propagation time is proportional the the width of the operands. You can also use a half-adder, which performs the reduction (a + b => 2*c + s) in constant time.
For the multiplier to be as fast as possible, you want the layers to use only carry-save and half-adders, as well as have the final 2 input addition to have the lowest width possible. Like this, all your layers performs in constant time, and the final one has the lowest propagation time possible.
You should find that if you reduce the pairs of 2 in the first layers with half-adders, you won't save any layers or reduce the width of the final addition, thus the multiplication won't be faster.
Amr Sabry's CNF generator page at Indiana U cites just a link to Chris Wallace' homepage before describing the Wallace-tree circuit:
In the Wallace-tree circuit, the rows (with appropriate shifts) are added in groups of three to produce sums and carries. The sums and carries (with appropriate shifts) are again added in groups of three, and this is repeated until there is just one sum and one carry. Then a special adder is used to add the final sum and the final carry. The products from any row need go through only a logarithmic number of adders before they get to the special adder. (emphasis added)
There is no mention of half-adders. This is consistent with Wallace' original paper, as Ruben noted.
Half-adders seem to be a discretion of the circuit designer and (contrary to the Wikipedia text) must not be applied greedily.
Jonathan D. explained the motivation for not using a greedy approach.
Indiscriminately adding every group of 2 or 3 wires will unnecessarily increase the width of the final addition, and actually expend more gates prior to that (in the extra 'reductions') just to do so.
But this doesn't explain any rule or heuristic for choosing when to add a group, or when not.
The Wiki illustration shows per-layer discrimination. For example, in the 3rd layer, the two groups of 3 wires on the left are given only a half-adder each, while in the next layer all groups of 3 wires are given full-adders:
It would be useful to have a heuristic to generate a Wallace-tree with half-adders programmatically. I'm not an engineer, so I don't know if the answer is obvious to engineers (?). But the closest I could devise produces a final result similar to the Wikipedia illustration.
Apply the rules greedily whenever doing so does not increase the number of the wires of any weight whose number of wires is 1 or 2, unless:
- Doing so is necessary to reduce a weight whose number of wires is greater than 2 (including carry), or
- it increases the number of consecutive least-weight wires that pass-through directly to the output (i.e. the string of "single dots" on the right-hand side).
This yields different steps compared to the illustration, but the end result is similar:
Example:
•••••••••••••••
•••••••••••••
•••••••••••
•••••••••
•••••••
•••••
•••
•
-----------------
•••••••••••••••
•••••••••••••
•••••••••
•••••••
•••
•
-----------------
••••••••••••••••
••••••••••••
•••••••
•••
-----------------
••••••••••••••••
•••••••••••
•••
-----------------
•••••••••••••••••
••••••••••Will update this if I can find a better rule.
I agree with you that the description of the reduction procedure on the Wikipedia page is inconsistent with the reduction procedure used in the picture. The curious thing is that different sources seem to have a different idea of what a Wallace tree exactly is. There seems to be no rigorous description of the Wallace reduction phase.
During lecture, I learned to reduce Wallace trees the way it is explained on Wikipedia: the 'greedy' way (reduce as much as you can). But I also found this site, where they use a similar reduction scheme as in the image in your question (in fact, it is meant to be the same, but the Wikipedia image contains an error, in the 4th dot diagram, the 7th column from the right contains a dot too many), and refer to it as 'traditional Wallace reduction'. So there are at least two reduction schemes that have Wallace's name attached to it (and the many papers which refer to Wallace trees or Wallace multipliers in some way suggest that there are many more).
In such cases of confusion, it is often useful to look up the original paper, as it usually helps to understand the historical context of the term. It is not very hard to read, and is, at some points, less formal than one might expect (which might be a source of confusion).
When reading the paper, it becomes clear that Wallace trees were not designed with dot diagrams in mind. Once one has adapted this concept, it becomes very easy to improve the reduction proposed by Christopher Wallace. My guess is that people just used the term 'Wallace tree' to refer to these improved schemes as well. The wealth of papers and distinct designs that one find when googling for 'Wallace tree multiplier' seems to indicate that the term is used quite loosely indeed.
Now, let's take a look at the dot diagram of the Wallace tree in your question. Compared to a Dadda tree, two things stand out:
To understand this, it is useful to note that in the original paper, Christopher Wallace does not use dot diagrams. Instead, he loosely describes the strategy as "group three numbers and reduce them to two using adders". The way he builds trees is to take a number of bits with the same weight, and build a tree of those using only full adders. This is illustrated in figure 1 from the paper, in which 20 operands (of odd weight from 1 to 39 from base-4 modified Booth encoding) are added: to add 20 n-bit numbers, you would need n of these trees (plus some structure to handle the carry bits, which could be done with simplified versions of this tree, as it involves adding less than 20 bits: this is where dot diagrams come in handy).
So, Chris Wallace was not thinking about dot diagrams when he came up with his method (which is a reason that it is a pretty inefficient way of reducing numbers in some aspects). He was thinking in terms of numbers (more specifically, multi-bit numbers).
When you think about it, this explains the layout of the dot diagram. The groupings of rows are groups of three numbers which are added together. From this perspective, it doesn't make to much sense to mix bits of the numbers. This 'traditional' Wallace reduction method is really quite trivial when you think of the rows of dots as multi-bit numbers, and you just reduce each group of three numbers to two numbers.
