Datapath design

CHAPTER 4

Datapath Design

An instruction-set processor consists of datapath (data processing) and control units. This chapter addresses the register-level design of the datapath unit, while Chapter 5 covers the control unit. The focus is on the arithmetic algorithms and circuits needed to process numerical data. These circuits are examined first for fixed-point numbers (integers) and then for floating-point numbers. The use of pipelining to speed up data processing is also discussed.

The design of circuits to implement the four basic arithmetic instructions for fixed-point numbers—addition, subtraction, multiplication, and division—is the main topic of this section. It also discusses the implementation of logic instructions and ALU design.

Add and subtract instructions for fixed-point binary numbers are found in the instruction set of every computer. In smaller machines such as microcontrollers they are the only available arithmetic instructions. As we have seen in earlier chapters, addition and subtraction hardware (Example 2.7) or software (Example 3.1) can be used to implement multiplication and, in fact, any arithmetic operation. Beginning with Charles Babbage, computer designers have devoted considerable effort to the design of high-speed adders and subtracters. As we will see, these basic circuits can be designed in many different ways that involve various trade-offs between operating speed and hardware cost.

CHAPTER 4

Datapath Design

An instruction-set processor consists of datapath (data processing) and control units. This chapter addresses the register-level design of the datapath unit, while Chapter 5 covers the control unit. The focus is on the arithmetic algorithms and circuits needed to process numerical data. These circuits are examined first for fixed-point numbers (integers) and then for floating-point numbers. The use of pipelining to speed up data processing is also discussed.

4.1 FIXED-POINT ARITHMETIC

The design of circuits to implement the four basic arithmetic instructions for fixed-point numbers—addition, subtraction, multiplication, and division—is the main topic of this section. It also discusses the implementation of logic instructions and ALU design.

4.1.1 Addition and Subtraction

Add and subtract instructions for fixed-point binary numbers are found in the instruction set of every computer. In smaller machines such as microcontrollers they are the only available arithmetic instructions. As we have seen in earlier chapters, addition and subtraction hardware (Example 2.7) or software (Example 3.1) can be used to implement multiplication and, in fact, any arithmetic operation. Beginning with Charles Babbage, computer designers have devoted considerable effort to the design of high-speed adders and subtracters. As we will see, these basic circuits can be designed in many different ways that involve various trade-offs between operating speed and hardware cost.

230

SECTION 4.1

Fixed-Point

Arithmetic

c_out

P₃

G₃

P₂

G₂

P₁

G₁

P₀

G₀

c₀

Figure 4.6

A 4-bit carry-lookahead adder.

z₁₅:z₁₂

c₁₁

z₁₁:z₈

c₇

z₇:z₄

c₃

z₃:z₀

c_out

x₁₅:x₁₂

y₁₅:y₁₂

x₁₁:x₈

y₁₁:y₈

x₇:x₄

y₇:y₄

x₃:x₀

y₃:y₀

Figure 4.7

A 16-bit adder composed of 4-bit adders linked by ripple-carry propagation.

c₁₅

c₁₀

CHAPTER 4

Datapath Design

Figure 4.8

A 16-bit adder composed of 4-bit adders linked by carry lookahead.

signal pairs p_i instead of c_out. A carry-lookahead generator converts the four sets of p-g signals to the carry inputs required by the four stages. The "group" g and p signals produced by each 4-bit stage are defined by

g = x₃y₃ + x₂y₂(x₃ + y₃) + x₁y₁(x₂ + y₂)(x₃ + y₃) + x₀y₀(x₁ + y₁)(x₂ + y₂)(x₃ + y₃)

 + x₃y₂(x₁ + y₁)(x₂ + y₂)

p = (x₃ + y₃)(x₂ + y₂)(x₁ + y₁)(x₀ + y₀)

which directly extend (4.7). It is not hard to show that the logic to generate the group carry signals c_out, c₁₇, c₇, and c₃ in Figure 4.8 is exactly the same as that of

the carry-lookahead generator of Figure 4.6 and is therefore defined by Equations (4.10).

EXAMPLE 4.1 DESIGN OF A COMPLETE TWOS-COMPLEMENT ADDER-SUBTRACTER.

adder-subtracter that computes the three quantities x + y, x - y, and y - x, as

well as overflow and zero flags. The design goal is to minimize the number of gates used; operating speed is not of concern. The circuit is required in several versions that handle different data word sizes, including 4, 8, and 16 bits. We will assume that we have standard gate-level and 4-bit register-level components available as building blocks.

Those lowest-cost adders employ ripple-carry propagation and can easily provide

access to the internal signals needed by the flags. Recall that overflow detection uses c_n-2, the carry bit to the sign position. Zero detection requires access to all the sum outputs and poses no special problems. Figure 4.9a shows the logic diagram of an appropriate 4-bit ripple-carry adder. The overflow flag v is defined by Equation (4.6) as v = c_s ⨁ c_d and is realized here by an XOR gate. The zero flag is defined by z =

BoothMult

(in: INBUS; out: OUTBUS);

register A[7:0], M[7:0], Q[7:0], Q_-1, COUNT[2:0];

bus INBUS[7:0], OUTBUS[7:0];

BEGIN: A := 0; COUNT := 0;

INPUT: M := INBUS;

Q[7:0] := INBUS; Q[_-1] := 0;

SCAN: if Q[0] = 0 and Q_-1 = 0 then A[7:0] := A[7:0] + M[7:0]; go to TEST;

else if Q[1] Q[0] = 10 then A[7:0] := A[7:0] - M[7:0];

TEST: if COUNT = 7 then go to OUTPUT;

RSHIFT: A[7] / A[7:0] / Q_-1;

INCREMENT: COUNT := COUNT + 1; go to SCAN;

OUTPUT: OUTBUS := A; Q[0];

OUTBUS := Q[7:0];

end BoothMult;

Figure 4.15

HDL description of an 8-bit multiplier implementing the basic Booth algorithm.

Combinational array multipliers.

Advances in VLSI technology have made it possible to build combinational circuits that perform n x n-bit multiplication for fairly large values of n. An example is the Integrated Device Technology 7172CM1 multiplier chip, which can multiply two 16-bit numbers in 16 ns [Integrated Device Technology 1995]. These multipliers resemble the n-step sequential multipliers discussed above but have roughly n times more logic to allow the product to be computed in one step instead of in n steps. They are composed of arrays of simple combinational elements, each of which implements an add/subtract-and-shift operation for small slices of the multiplication operands.

Suppose that two binary numbers X = x_n-1 x_n-2...x₀ x_-1 and Y = y_n-1 y_n-2...y₀ are to be multiplied.

For simplicity, assume that X and Y are unsigned integers. The product P = X x Y can therefore be expressed as

Step

1. Initialize registers
2. Substract M from A
3. Right-shift A,Q

Figure 4.16

Illustration of the Booth multiplication algorithm.

P = _∑^n-1x_iy_i^(4.24)

corresponding to the bit-by-bit multiplication style of Figure 4.10. Now (4.24) can be rewritten as

P = _∑^n-1 ( _∑ⁱ⁼⁰ )x_jy_j ^(4.25)