|
"8x12=96" and "12x8=96"...so what is Ken Chapman on about this
week?
Well I haven’t quite gone mad just yet, it’s just that I’m
thinking about those Xilinx Virtex and Spartan-II devices again and
how multipliers are constructed in the CLBs. I will prove to you
that "8x12" is not equal to "12x8", and hopefully in the process,
provide you with some details of how to get the most out of your
designs that contain multiplication.
To prove this, I need to bend the rules a little, and change my
definition of the maths! In my case I’m not going to consider the
numerical values of "8" and "12," but consider the multiplication of
an 8-bit value and 12-bit value.
Here we see full binary (unsigned) multiplication of the values
3021 (BCD hexadecimal) and 228 (E4 hexadecimal).
The act of multiplication comes down to some very simple
procedures. I have labeled the two inputs "A" and "B". The
multiplication is performed by taking each bit of "B" in turn, and using it to multiply the whole
of input "A". Now in binary this is very simple. Since one bit can
only represent the value "0" or "1," then the result of this one-bit
multiplication can only be the value zero or "A".
It then requires that all these partial products are added
together to form the final product of multiplication. Of course, we
have to restore the original bit weighting associated with each bit
of "B", and this is achieved by the ever-increasing partial product
shifting to the left that is provided by the "0" padding on each line.
Regardless of which value is the multiplicand, and which is the
multiplier, the result is always 688788 (A8294 hexadecimal) and I’m
still losing the game!
The one-it multiplication is logically very simple requiring only
sets of AND gates. These either allow the "A" value to be passed, or force the partial
product completely to zero.
Then, we need to add all the partial products together with
appropriate bit weighting. If we have time (enough clock cycles), we
can adopt the classical "shift and add" technique based on an
accumulator, but in this case I am looking for a maximum performance
parallel multiplier. For this, I will need an "addition tree".
It can be seen that the bit weighting is restored throughout the
addition process. It is always easy to determine the number of bits
required at any stage, as each adder output is in itself a partial
product of the final result. As shown, the first adders provide the
products of the 12-bit input "A"
multiplied by 2 bits of "B", and hence
generate a 14-bit (12+2) product. The second stage adders require
16-bits to represent a 12-bit by 4-bit product. The final result is
then the full 20-bit product.
Obviously, the addition of zero bits does not require a real
addition process. However, if the adder is pipelined, then the least
significant bits to which zero is added will also require flip-flops
to balance the pipeline delay. These flip-flops occupy the same
space as a full adder (unless that wonderful SRL16E can combine
several stages together).
Since addition is such a key part of this multiplication process,
let’s review how a full adder is so cleverly achieved in Virtex and
Spartan-II. Each function generator (of which there are 4 in each
CLB arranged into 2 "slices") is complemented by a simple 2-input
XOR gate called XORCY and a 2:1 multiplexer called MUXCY. From the
left-hand truth table for a full adder, it is clear that the sum in
the result of A xor B xor Cin.
In Virtex and Spartan-II, this function is broken into two parts
such that the Half_sum = A xor
B is generated first using the function generator, and then the
dedicated XORCY is used to form the full sum of Half_sum xor Cin. The clever bit can be
seen in the right-hand table. This shows how the Half-sum is used to control the MUXCY
multiplexer which generates the carry output. Notice how the Half_sum selects either the original carry
input or the "A" input.
Whilst the latter stages of the addition tree are pure
add functions, look at the way in which the first two partial
products are formed and then applied to the first stage adder. This
means that in the majority of cases, the two adder inputs are each
driven by a 2-input AND gate. As these AND gates would each occupy a
function generator, a multiplier suddenly becomes very large in an
FPGA. In my case of a 12-bit by 8-bit multiplier it would require
12x8 = 96 function generators (48 slices) just to implement the AND
gates.
However, we can quickly see an optimisation. The AND
gate associated with one of the adder inputs can be absorbed into
the function generator forming the Half_sum for addition. This in itself reduces
the size of the 12-bit by 8-bit multiplier by 48 function generators
(24 slices).
It would be nice to absorb the other AND gate into the
function generator, but the signal it produces is also required by
the MUXCY part of the addition function. So this would appear to be
the most we can achieve.
However, Virtex and Spartan-II does allow this second
AND gate to be absorbed. Next to each function generator is yet
another component called the MULT_AND. It has the effect of
re-creating the same input to the MUXCY, even though the desired
signal is now buried within the function generator.
So, back to the issue of "8x12" not being equal to
"12x8".
Since all the AND gates associated with multiplication
are essentially free in Virtex and Spartan-II, the structure of a
parallel multiplier is the same as that for an addition tree with
the first stage adders also performing the multiplication by two
bits of "B". As we break the "B" word into 2-bit sections, so the resulting
addition tree must reflect the number of bits in the "B" word.
------
--------------------------------------------------------------------
The fact that 8 is a power of 2 means that the "12x8"
breaks down nicely into 4 multiplier adders in the first stage;
hence, it leads to a symmetrical addition tree of 3 levels. In
contrast, the "8x12" is less elegant: the 6 multiplier adders of the
first stage do not sum easily, leading to more adders and 4 levels
of logic. For a fully pipelined multiplier, there is even the
requirement for delay compensation.
Admittedly, the multiplier adders and pure adders of
the "8x12" are generally a smaller number of bits than in the
"12x8"; but with Virtex and Spartan-II, this has a very minimal
impact on performance. In any case, both multipliers have the same
largest-size adder at the final stage. Combinatorial multiplier
performance will be set by the number of logic levels, and in this
case, the "12x8" will definitely win.
So, I have eventually proven that 8x12 is not
equal to 12x8 when it comes to the size and performance of
multipliers in Virtex and Spartan-II devices. Consider this as you
use full parallel multipliers in your designs.
The Variable Parallel Multiplier IP contained in the
Core Generator allows you to define the width of the "A" and "B" ports,
so do consider the impact this will have. The data sheet indicates
that latency is a function of the "B"
port; if you play with the GUI, you will see instant feedback that
for an 8x12 the latency is 4 cycles. For the 12x8, it is just 3
cycles. I suggest that this information is also used to determine
the number of levels of logic in combinatorial multipliers before
actually selecting the combinatorial option.
If you are an HDL user, try to understand how your
tool maps what you write to the structure. All synthesis tools
stating that they specifically target Virtex or Spartan-II devices
should be making full use of the MULT_AND gate, and hence producing
optimum area solutions. However, you may need to experiment to
discover the "A" and "B" port-mapping.
A more significant issue with HDL coding is
performance. Although the above VHDL example will generate a
multiplier, it will result in a combinatorial multiplier with a
single register at the output. To increase performance, the addition
stages really do need to be pipelined. This is where you may insert
a Xilinx IP Core.
Alternatively, your code could describe the internal
structure of the multiplier in more detail. Synthesis vendors have
also been looking at coding styles combined with "re-timing," which
can distribute lumped register delays following a multiplier back
into the addition stages. In this case, it is vital that you
understand the particular synthesis tools you use and that you fully
appreciate that...
“8x12 is not equal to 12x8”
Share your comments, questions and ideas with Ken Chapman and
other interested designers at the "8x12 Does NOT Equal 12x8" FORUM. | 
