CHAPTER 2

LITERATURE SURVEY

2.1 Background of the Project
Websters dictionary defines multiplication as a mathematical operation that at its
simplest is an abbreviated process of adding an integer to itself a specified number of times. A
number (multiplicand) is added to itself a number of times as specified by another number
(multiplier) to form a result (product). In elementary school, students learn to multiply by
placing the multiplicand on top of the multiplier. The multiplicand is then multiplied by each
digit of the multiplier beginning with the rightmost, Least Significant Digit (LSD). Intermediate
results (partial-products) are placed one atop the other, offset by one digit to align digits of the
same weight. The final product is determined by summation of all the partial-products. Although
most people think of multiplication only in base 10, this technique applies equally to any base,
including binary. Figure 2.1 shows the data flow for the basic multiplication technique just
described. Each black dot represents a single digit.

Fig 2.1 Basic Multiplication Data flow

2.2 Different type of Multipliers:
2.2.1 Binary Multiplication
In the binary number system the digits, called bits, are limited to the set. The result of
multiplying any binary number by a single binary bit is either 0, or the original number. This
makes forming the intermediate partial-products simple and efficient. Summing these partial-
products is the time consuming task for binary multipliers. One logical approach is to form the
partial-products one at a time and sum them as they are generated. Often implemented by
software on processors that do not have a hardware multiplier, this technique works fine, but is
slow because at least one machine cycle is required to sum each additional partial-product. For
applications where this approach does not provide enough performance, multipliers can be
implemented directly in hardware.
2.2.2 Hardware Multipliers
Direct hardware implementations of shift and add multipliers can increase performance
over software synthesis, but are still quite slow. The reason is that as each additional partial-
product is summed a carry must be propagated from the least significant bit (LSB) to the most
significant bit (MSB). This carry propagation is time consuming, and must be repeated for each
partial product to be summed.
One method to increase multiplier performance is by using encoding techniques to reduce
the the number of partial products to be summed. Just such a technique was first proposed by
Booth [BOO 511. The original Booths algorithm ships over contiguous strings of ls by using
the property that: 2 + 2(n-1) + 2(n-2) + . . . + 2hm) = 2(n+l) - 2(n-m). Although Booths
algorithm produces at most N/2 encoded partial products from an N bit operand, the number of
partial products produced varies. This has caused designers to use modified versions of Booths
algorithm for hardware multipliers. Modified 2-bit Booth encoding halves the number of partial
products to be summed.
Since the resulting encoded partial-products can then be summed using any suitable
method, modified 2 bit Booth encoding is used on most modern floating-point chips LU 881,
MCA 861. A few designers have even turned to modified 3 bit Booth encoding, which reduces
the number of partial products to be summed by a factor of three IBEN 891. The problem with 3
bit encoding is that the carry-propagate addition required to form the 3X multiples often
overshadows the potential gains of 3 bit Booth encoding.
To achieve even higher performance advanced hardware multiplier architectures search
for faster and more efficient methods for summing the partial-products. Most increase
performance by eliminating the time consuming carry propagate additions. To accomplish this,
they sum the partial-products in a redundant number representation. The advantage of a
redundant representation is that two numbers, or partial-products, can be added together without
propagating a carry across the entire width of the number. Many redundant number
representations are possible. One commonly used representation is known as carry-save form. In
this redundant representation two bits, known as the carry and sum, are used to represent each bit
position. When two numbers in carry-save form are added together any carries that result are
never propagated more than one bit position. This makes adding two numbers in carry-save form
much faster than adding two normal binary numbers where a carry may propagate. One common
method that has been developed for summing rows of partial products using a carry-save
representation is the array multiplier.

2.2.3 Array Multipliers
Conventional linear array multipliers consist of rows of carry-save adders (CSA). A
portion of an array multiplier with the associated routing can be seen in Figure 1.2. In a linear
array multiplier, as the data propagates down through the array, each row of CSAs adds one
additional partial-product to the partial sum. Since the intermediate partial sum is kept in a
redundant, carry-save form there is no carry propagation. This means that the delay of an array
multiplier is only dependent upon the depth of the array, and is independent of the partial-
product width. Linear array multipliers are also regular, consisting of replicated rows of CSAs.
Their high performance and regular structure have perpetuated the use of array multipliers for
VLSI math co-processors and special purpose DSP chips.
The biggest problem with full linear array multipliers is that they are very large. As
operand sizes increase, linear arrays grow in size at a rate equal to the square of the operand size.
This is because the number of rows in the array is equal to the length of the multiplier, with the
width of each row equal to the width of multiplicand. The large size of full arrays typically
prohibits their use, except for small operand sizes, or on special purpose math chips where a
major portion of the silicon area can be assigned to the multiplier array.
Another problem with array multipliers is that the hardware is underutilized. As the sum
is propagated down through the array, each row of CSAs computes a result only once, when the
active computation front passes that row. Thus, the hardware is doing useful work only a very
small percentage of the time. This low hardware utilization in conventional linear array
multipliers makes performance gains possible through increased efficiency. For example, by
overlapping calculations pipelining can achieve a large gain in throughput [NOL 861. Figure 1.3
shows a full array pipelined after each row of CSAs. Once the partial sum has passed the first
row of CSAs, represented by the shaded row of GSAs in cycle 1, a subsequent multiply can be
started on the next cycle. In cycle 2, the first partial sum has passed to the second row of CMs,
and the second multiply, represented by the cross hatched row of CSAs, has begun. Although
pipelining a full array can greatly increase throughput, both the size and latency are increased
due to the additional latches While high throughput is desirable, for general purpose computers
size and latency tend to be more important; thus, fully pipelined linear array multipliers are
seldom found.
2.3 Iterative Techniques
To reduce area, some designers use partial arrays and iterate using a clock. At the limit, a
minimal iterative structure would have one row of CSAs and a latch. Clearly, this structure
requires the least amount of hardware, and has the highest utilization since each CSA is used
every cycle. An important observation is that iterative structures are fast if the latch delays are
small, and the clock is matched to the combinational delay of the CSAs. If both of these
conditions are met, iterative structures approach the same throughput and latency as full arrays.
The only difference in latency is due to the latch and clock overhead. Although they require very
fast clocks, a few companies use iterative structures in their new high-performance floating point
processors.

Figure 2.2 Minimal Iterative Structures
In an attempt to increase performance of the minimal iterative structure additional rows
of CSAs could be added to make a bigger array. For example, the addition of one row of CMs
to the minimal structure would yield a partial array with two rows of CMs. This structure
provides two advantages over the single row of CSA cells:
1) It reduces the required clock frequency, and
2) It requires only half as many latch delays.
It is important to note that although the number of CSAs has been doubled, the latency
was reduced only by halving the number of latch delays. The number of CSA delays remains the
same. Thus, assuming the latch delays are small relative to the CSA delays, increasing the depth
of the partial array by adding additional rows of CSAs in a linear structure yields only a slight
increase in performance.