3.0 Arithmetic Unit - Part 1

Arithmetic Unit v The Arithmetic and Logic Unit (ALU) is the CPU component that performs actual operations on data. v All operations are performed by logic gates. v The basic arithmetic operations are addition, subtraction, multiplication, and division of integers and floating-point numbers. Integer Representation v Numbers are represented in binary using a positional number system. v A positional number system represents numbers by concatenating symbols. Ø The number of different symbols used is called the radix or base. Ø A symbol in the representation is called a digit. A binary digit is called a bit. Ø The value of a number is the sum of the value of each digit multiplied by the weight of its position. Ø The position number is assigned from a reference mark, the dot (.), with position 0 immediately to the left of the dot and increasing to the left. Ø The weight is equal to the radix raised to the position number of the digit. 101101.012 ⇒ radix = 2 Symbol 1 0 1 1 0 1 0 1 Position 5 4 3 2 1 0 –1 –2 Weight 25 24 23 22 21 20 2–1 2–2 Value = 1×25 + 0×24 + 1×23 + 1×22 + 0×21 + 1×20 + 0×2–1 + 1×2–2 = 45.25 Negative Integer Representation Ø There are 3 common schemes for representing negative integers. Ø All schemes assign the most significant bit (msb) as a sign bit (negative value if sign bit is 1). ⇒ This requires an agreement on the width of the representation. Ø Positive integers have the same representation. Ø Negative integer representation varies according to scheme. Name +4510 Representation Method –4510 Representation Sign-Magnitude 0101101 Set sign bit 1101101 1’s Complement 0101101 Complement all bits 1010010 2’s Complement 0101101 1’s Complement + 1 1010011 Ø Due to ease of use and range, 2’s complement is most commonly used to represent integers.

Integer Addition v In a positional number system, numbers are added according to weight, from smallest to largest (right to left). If the result of an addition exceeds one digit (bit), the higher digit is added to the next position – carry. Simple Adder (Ripple-Carry Adder) v The adder may be implemented by cascading a half-adder (HA) and full-adders (FA). An–1Bn–1 A2 B2 A1 B1 A 0 B0 C n–1 C3 C2 C1 FA

C n Sn–1 HALJ

:

....

:

FA C3

S2

Arithmetic Unit (Part 1)

FA C2

S1

HA C1

S0 1

v For simplicity, circuits will be implemented using only the 3 basic gates: NOT, AND, and OR. Half-Adder Ø A half-adder (HA) takes 2 input bits A and B, and produces the sum S and a carry-out Cout. A B Cout S A 0 0 0 0 B 0 1 0 1 S 1 0 0 1 1 1 1 0 S = A B + AB C out = AB

Cout

Full-Adder Ø A full-adder (FA) takes an extra input, the carry-in Cin from the result of the previous digit. C in A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

Cin 0 1 0 1 0 1 0 1

Cout 0 0 0 1 0 1 1 1

B

A

S 0 1 1 0 1 0 0 1

S

S = A B C in + A BC in + AB Cin + ABC in C out = AB + AC in + BC in

Cout

v Typical ALU design includes a capability to add a carry-in to the least significant bit. Hence, a typical multi-bit adder is implemented as a cascade of full-adders, one for each bit. An–1Bn–1 Ai Bi A1 B1 A0 B0 C0 Carry-in C n–1 C i+1 Ci C2 C1 FA

:

....

:

FA

:

....

:

C i+1 Cn Carry-out

Sn–1

FA C2

Si

FA C1

S1

S0

v The final carry-out Cn may be used for cascading adders or as an overflow indicator. Design Considerations v Size – the number of gates used in implementing the adder. Ø 8 gates (3 NOT, 4 AND, and 1 OR) are needed for the sum. HALJ

Arithmetic Unit (Part 1)

2

Ø 4 gates (3 AND and 1 OR) are needed for the carry-out. Ø An n-bit adder will then need n × 12 gates. v Speed – the amount of time it requires to perform an addition operation. Ø This is dependent on the propagation delay τ of the signal, i.e., the time delay from the time the input arrives up to the time the output becomes valid. Ø This is approximated by assuming that all gates have the same propagation delay δ. Hence, the total propagation delay of a circuit is equal to the longest path from the input to the output. Ø From the diagram, it can be seen that all inputs Ai and Bi arrive with 0 delay while the carry-in Ci “ripples” from the least-significant bit. § The propagation delay of Ci+1 is given by τ C ( i +1) = max( τ Ai + 2δ , τ Bi + 2δ , τ Ci + 2δ ) = max( τ Ai , τ Bi , τ Ci ) + 2δ = τ Ci + 2δ = 2iδ + 2δ = 2(i + 1)δ §

The propagation delay of Si is given by τ Si = max( τ Ai + 3δ , τ Bi + 3δ , τ Ci + 3δ ) = max( τ Ai , τ Bi , τ Ci ) + 3δ = τ Ci + 3δ = 2iδ + 3δ = (2i + 3)δ

Ø An n-bit adder will then have a total propagation delay given by τ = max(τ S 0 , τ S1 , ..., τ S ( n −1) , τ Cn ) = max( 3δ , 5δ , ..., (2 n + 1)δ , 2nδ ) = (2n + 1)δ Fast Adder (Using Carry LookAhead) v The fast-adder attempts to reduce the total propagation time by implementing a separate circuit to generate the carries – the carry lookahead circuit. v Consider the carry-out of the ith bit, C i +1 = Ai Bi + Ai Ci + Bi C i = Ai Bi + ( Ai + Bi )C i v Define generate function Gi and propagate function Pi, Gi = Ai Bi Pi = Ai + Bi v Ci+1 can be rewritten as C i +1 = Gi + Pi C i Similarly, C i = Gi −1 + Pi −1Ci −1 Hence, C i +1 = Gi + Pi (Gi −1 + Pi −1C i −1 ) = Gi + Pi Gi −1 + Pi Pi −1Ci −1 HALJ

Arithmetic Unit (Part 1)

3

This process may then be recursed to obtain C i +1 = Gi + Pi Gi −1 + Pi Pi −1C i −1 = Gi + Pi Gi −1 + Pi Pi −1 (Gi −2 + Pi −2C i −2 ) = Gi + Pi Gi −1 + Pi Pi −1Gi −2 + Pi Pi −1 Pi −2C i − 2 = Gi + Pi Gi −1 + Pi Pi −1Gi −2 + Pi Pi −1 Pi −2Gi −3 + Pi Pi −1 Pi −2 Pi −3C i −3 : = Gi + Pi Gi −1 + Pi Pi −1Gi −2 + ... + Pi Pi −1 ...P1G0 + Pi Pi −1 ... P1 P0C 0 v From an arbitrary carry-in Ck , the carry-out Ci can be obtained using C i = Gi −1 + Pi −1Gi −2 + Pi −1 Pi −2Gi −3 + ... + Pi −1Pi −2 ...Pk +1Gk + Pi −1 Pi −2 ...Pk +1 Pk C k Ø (i – k) each of generate and propagate functions are required. § 1 AND gate per generate function and 1 OR gate per propagate function gives a total of 2(i – k) gates. § Each requires a propagation time of 1δ. Ø Given the generate and propagate functions, the carry-out requires: § 1 OR gate and (i – k) AND gates, with § propagation delay of +2δ from the longest of τGx, τPx, and τCk . Example A3 B 3

A 2 B2

A1 B1

A0 B0

G and P circuit G3 P3 C4

G2 P 2

G1 P 1

G 0 P0

Carry Lookahead A3 B 3 FA S3

A 2 B2 C3

FA S2

A1 B1 C2

FA

C0 A0 B0

C1

S1

FA S0

Ø Propagation delays § All inputs Ax and Bx, as well as the carry-in C0, have delays of 0δ. § All generate and propagate functions Gx and Px have delays of 1δ. § All generated carries C1 to C4 have delays of max(τGx, τPx, τC0) + 2δ = 3δ.. § τS0 = max(τA0, τB0, τC0) + 3δ = 3δ. § τS1 = τS2 = τS3 = max(τAx, τBx, τCx) + 3δ = 6δ. § The total delay of the 4-bit adder is max(τS0, τS1, τS2, τS3, τC4) = 6δ. Ø Gate counts § 32 gates (4 adders × 8 gates) are needed for the sums S0 to S3. § 4 AND gates are needed for the generate functions G0 to G3. § 4 OR gates are needed for the propagate functions P0 to P3. § 2 gates (1 OR and 1 AND) are needed for C1. § 3 gates (1 OR and 2 AND) are needed for C2. § 4 gates (1 OR and 3 AND) are needed for C3. § 5 gates (1 OR and 4 AND) are needed for C4. § The adder requires a total of 54 gates. HALJ

Arithmetic Unit (Part 1)

4

Integer Subtraction v Integer subtraction is performed by adding the 2’s complement of the subtrahend. Ø The 2’s complement is taken by complementing all bits of the subtrahend (Y) and setting the carry-in. Ø Complementing can be performed by taking the exclusive OR (XOR) with 1. Y3

Y2

Y1

Y0 Add/Sub

A3

A2

A1

A0 B3

B2

4-bit Adder

Carry-out

HALJ

S3

S2

S1

B1

B0 Carry-in

S0

Arithmetic Unit (Part 1)

5