Arithmetic and Logic in Computer Systems

7

Fast Array Dividers

In this chapter, the design and construction of various high-speed iterative cellular arrays for parallel divisions are discussed. In the proposed array dividers, a large amount of replicated units are used for the comparison of the partial remainder and divisor, and the shift is realized by physical wiring. Three types of array dividers are to be introduced: (1) the Restoring Array Dividers, (2) the Non-restoring Array Dividers, and (3) the Carry-Lookahead Array Dividers. In addition, their performance and cost-effectiveness are to be analyzed.

7.1 RESTORING CELLULAR ARRAY DIVIDER

The restoring cellular array divider is based on the “restoring” division algorithm. Recall the circuit schematic of the divider based on the restoring division method shown in Figure 6.5. Partial remainders are stored in a register and subtractions then take place in a two-operand adder. Restorations are realized by the MUX. Hardware for this approach is simple but slow. With the restoring cellular array divider presented below, the execution can be made much faster.

Let dividend A = .a₁a₂ · · · a_2n, divisor D = .d₁d₂ · · · d_n and quotient Q = .q₁q₂ · · · q_n. Figure 7.1 shows a schematic logic diagram of an n-by-n restoring array divider with n = 4.

The basic element shown in the figure is a controlled subtracter (CS) cell, in which a − d is performed if mode P = 0, to find the difference between the previous partial remainder and the divisor. The borrow signal

Fig. 7.1: 4-by-4 ...