Arithmetic and Logic in Computer Systems

5

Parallel Multiplication

In the preceding chapter, a multiplication function was completed in n iterations given the input operand of length n. In each iteration, basically an add-and-shift operation was performed. In this chapter, instead of repetitively using the same single-stage hardware, an Array Multiplier is proposed, in which multiple stages of hardware are provided by replicating the single stage circuit. The different iterations of addition can now be performed by different stages of hardware, and each shifting is realized by the proper wiring between hardware stages. In this case, multiple multiplication operations can be overlapped. That is, the second multiplication can start before the first one completes, hence the time required to complete multiple multiplication functions can be reduced. To date, various iterative array multipliers and cellular array processors are available that are capable of high-speed multiplication demanded in scientific computation.

5.1 WALLACE TREES

In the multiplication operation, the addition of the partial products is the most time-consuming process. In the previous chapter, how to reduce the number of partial products is discussed. Here we present a hardware to handle the repetitive addition – Wallace tree.

A Wallace tree is a bit-slice adder which adds all the bits in the same bit position. Figure 5.1 gives the Wallace trees for different number of inputs. In (a), a 3 bit-slice adder, W₃, is presented which is actually a 3-input 2-output ...