Question

Perhaps the most likely case of adding many numbers at once in a computer would be when trying to multiply more quickly by using any adders to add many numbers in a single clock cycle. Compared to the multiply algorithm in Chapter 3, a carry save scheme with many adders could multiply more than 10 times faster. This exercise estimates the cost and speed of a combinational multiplier to multiply two positive 16-bit numbers. Assume that you have 16 intermediate terms M15, M14, …, M0, called partial products, that contain the multiplicand ANDed with multiplier bits m15, m14, …, m0. The idea is to use carry save adders to reduce the noperands into 2n/3 in parallel groups of three, and do this repeatedly until you get two large numbers to add together with a traditional adder.

First, show the block organization of the 16-bit carry save adders to add these 16 terms, as shown on the right in Figure B.14.1. Then calculate the delays to add these 16 numbers. Compare this time to the iterative multiplication scheme in Chapter 3 but only assume 16 iterations using a 16-bit adder that has full carry lookahead whose speed was calculated in Exercise B.29.

Short answer

Block organization of the 16-bit carry save address to add 16 terms is as follows:

Time consumed=296T

Speed up=8.22

Step-by-step solution

Determine the faster addition

The faster addition can be performed by finding the carry in the higher order bits . The faster method of finding carry will speedup the addition. “Infinite” Hardware can be used to find the fast carry. But this increases the expenses that spent in hardware units. Carry-lookahead adder is capable of finding the fast carry with speed improvements.

Determine the block organization and speed up.

Given:

Combinational multiplier to multiply two 16-bit numbers is introduced.

Assume that there are 16 intermediate terms M15 to M0, called partial products that contain the multiplican ANDed with multiplier bits m15 to m0.

This idea will be used to carry save adders to reduce the n operands to 2n/3 in parallel groups of three.

This will generate two larger numbers that will be added in the traditional adder.

The block diagram , that shows the 16 bit carry save adders to add 16 terms is shown below:

From, the block orgranization, it is depicted that the partial products are grouped in each level. Each group will be processed in parallel with four carry save adders in the level 1.

Likewise , sum of the larger numbers will be found in the level 7.

We know that , there are 7 levels involved in the calculation of the sum of 16 partial products.

From, level 1 to 6 each level will consume 2T time to perform sum.In level 7 carry look ahead adder will consume around 8T time.

The total time consumed will be:

$2\mathrm{T}\times 6+24\mathrm{T}=36\mathrm{T}$

If the multiplication is carried out using traditional look ahead adder, Then the time consumed would be:

For

$$\begin{gathered} M0:16bits=8T \\ M1:17bits=12T \\ M2:18bits=12T \\ M3:19bits=12T \\ M4:20bits=12T \\ M5:21bits=16T \\ M6:22bits=16T \\ M7:23bits=16T \\ M8:24bits=16T \\ M9:25bits=20T \\ M10:26bits=20T \\ M11:27bits=20T \\ M12:28bits=20T \\ M13:29bits=24T \\ M14:30bits=24T \\ M15:31bits=24T \\ M16:32bits=24T \end{gathered}$$

Above is the calculation for time consumed for each partial product on the traditional look ahead adder.

Total time consumed will be:

$\begin{array}{rcl}T& =& 8T+12T\times 4+16T\times 4+20T\times 4+24T\times 4\\ & =& 8T+48T+64T+80T+96T\\ & =& 296T\end{array}$

Speed up is the ratio between the carry save adder orgranization and the traditional look ahead adder.

$\begin{array}{rcl}Speedup& =& \frac{296}{32}\\ & =& 8.22\end{array}$