Abd-El-Barr M., El-Rewini H. Fundamentals of Computer Organization and Architecture

Подождите немного. Документ загружается.

Example Consider the division of a dividend X ¼ 8 ¼ (1000) and a divisor

D ¼ 3 ¼ (0011) using the non-restoring algorithm. The process is illustrated in

the following table.

Initially 0 0 0 0 0 1 0 0 0

;

First cycle

00011

Shift 0 0 0 0 1 0 0 0

Subtract 1 1 1 0 1

Set x

1110 0000

Shift 1 1 1 0 0 0 0 0

Add 00011

)

Second cycle

Set x

11111 0000

Shift 1 1 1 1 0 0 0 0

Add 00011

)

Third cycle

Set x

00001 0001

Shift 0 0 0 1 0 0 0 1

Subtract 1 1 1 0 1

)

Fourth cycle

Set x

11111 0010

|ﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄ{zﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄ}

Quotient

Add 11111

)

Restore remainder00011

00010

Remainder

|ﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄ{zﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄﬄ}

4.3. FLOATING-POINT ARITHM ETIC

Having considered integer representation and arithmetic, we consider in this section

ﬂoating-point representation and arithmetic.

4.3.1. Floating-Point Representation (Scientiﬁc Notation)

A ﬂoating-point (FP) number can be represented in the following form: +m



where m, called the mantissa, represents the fraction part of the number and is

Divisor (D)

Shift Left

(n+ 1)-bit Adder

Add

Control Logic

Figure 4.10 Binary division structure

COMPUTER ARITHMETIC

normally represented as a signed binary fraction, e represents the exponent, and b

represents the base (radix) of the exponent.

Example Figure 4.11 is a representation of a ﬂoating-point number having

m ¼ 23 bits, e ¼ 8 bits, and S (sign bit) ¼ 1 bit. If the value stored in S is 0, the

number is positive and if the value stored in S is 1, the number is negative.

The exponent in the above example, can only represent positive numbers 0

through 255. To represent both positive and negative exponents, a ﬁxed value,

called a bias, is subtracted from the exponent ﬁeld to obtain the true exponent.

Assume that in the above example a bias ¼ 128 is used, then true exponents in

the range 2128 (stored as 0 in the exponent ﬁeld) to þ127 (stored as 255 in the

exponent ﬁeld) can be represe nted. Based on this representation, the exponent þ4

can be represented by storing 132 in the exponent ﬁeld, while the exponent 212

can be represented by storing 116 in the exponent ﬁeld.

Assuming that b ¼ 2, then an FP number such as 1.75 can be represented in any

of the forms shown in Figure 4.12.

To simplify performing operations on FP numbers and to increase their precision,

they are always represented in what is called normalized forms. An FP number is

said to be normalized if the leftmost bit of the mantissa is 1. Therefore, among

the three above possibl e representations for 1.75, the ﬁrst representation is normal-

ized and should be used.

Since the most signiﬁcant bit (MSB) in a normalized FP number is always 1, then

this bit is often not stored and is assumed to be a hidden bit to the left of the radix

point, that is, the stored mantissa is 1.m. Therefore, a nonzero normalized number

represents the value (  1)

(1:m)

e128

Floating-Point Arithmetic Addition/Subtraction The difﬁculty in adding

two FP numbers stems from the fact that they may have different exponents.

Therefore, before adding two FP numbers, their exponents must be equalized, that

is, the mantissa of the number that has smaller magnitude of exponent must be

aligned.

Figure 4.11 Representation of a ﬂoating-point number

+0.111*2

+0.0111*2

+0.00000000000000000000111*2

10000001

11100000000000000000000

0 10000010 01110000000000000000000

0 10010101 00000000000000000000111

Figure 4.12 Different representation of an FP number

4.3. FLOATING-POINT ARITHMETIC 75

Steps Required to Add/Subtract Two Floating-Point Numbers

1. Compare the magnitude of the two exponents and make suitable alignment to

the number with the smaller magnitude of exponent.

2. Perform the addition/subtraction.

3. Perform normalization by shifting the resulting mantissa and adjusting the

resulting exponent.

Example Consider adding the two FP numbers 1.1100

and 1.1000

1. Alignment: 1.1000

has to be aligned to 0.0110

2. Addition: Add the two numbers to get 10.0010

3. Normalization: The ﬁnal normalized result is 0.1000

(assuming 4 bits

are allowed after the radix point).

Addition/subtraction of two FP numbers can be illustrated using the schematic

shown in Figure 4.13.

Multiplication Multiplication of a pair of FP numbers X ¼ m

and Y ¼

is represented as X

Y ¼ (m

 m

)

aþb

A general algorithm for multiplication of FP numbers consists of three basic

steps. These are:

1. Compute the exponent of the product by adding the exponents together.

2. Multiply the two mantissas.

3. Normalize and round the ﬁnal product.

Example Consider multipl ying the two FP numbers X ¼ 1.000

and

Y ¼ 21.010

1. Add exponents: 22 þ (21) ¼ 2 3.

2. Multiply mantissas: 1.000

2 1.010 ¼ 21.010000.

The product is 2 1.0100

Figure 4.13 Addition/subtraction of FP numbers

COMPUTER ARITHMETIC

Multiplication of two FP numbers can be illustrated using the schematic shown in

Figure 4.14.

Division Division of a pair of FP numbers X ¼ m

and Y ¼ m

represented as X=Y ¼ (m

)

ab

A general algorithm for division of FP numbers consists of three basic steps:

1. Compute the exponent of the result by subtracting the exponents.

2. Divide the mantissa and determine the sign of the result.

3. Normalize and round the resulting value, if necessary.

Example Consider the division of the two FP numbers X ¼ 1.0000

and

Y ¼ 2 1.0100

1. Subtract exponents: 22 2 (21) ¼ 21.

2. Divide the mantissas: 1.0000 421.0100 ¼ 20.1101.

3. The result is 20.1101

Division of two FP numbers can be illustrated using the schematic shown in

Figure 4.15.

4.3.3. The IEEE Floating-Point Standard

There are essentially two IEEE standard ﬂoating-point formats. These are the basic

and the extended formats. In each of these, IEEE deﬁnes two formats, that is, the

single-precision and the double-precision formats. The single-precision format is

32-bit and the double-precision is 64-bit. The single extended format should have

at least 44 bits and the double exte nded format should have at least 80 bits.

Exponent E2 Exponent E1

Add

Mantissa M2

Mantissa M1

Multiply

Result normalization and round logic

Result Exponent Result Mantissa

Figure 4.14 FP multiplication

4.3. FLOATING-POINT ARITHMETIC 77

In the single-precision format, base 2 is used, thus allowing the use of a hidden

bit. The exponent ﬁeld is 8 bits. The IEEE single-precision representation is shown

in Figure 4.16.

The 8-bit exponent allows for any of 256 combinations. Among these, two com-

binations are reserved for special values:

1. e ¼ 0 is reserved for zero (with fraction m ¼ 0) and denormalized numbers

(with fraction m = 0).

2. e ¼ 255 is reserved for +1 (with fraction m ¼ 0) and not a number (NaN)

(with fraction m = 0).

m ¼ 0 m = 0

e ¼ 0 0 Denormalized

e ¼ 255 +1 NaN

The single extended IEEE format extends the exponent ﬁeld from 8 to 11 bits and

the mantissa ﬁeld from 23þ1 to 32 or more bits (without a hidden bit). This results in

a total length of at least 44 bits. The single extended format is used in calculating

intermediate results.

4.3.4. Double-Precision IEEE Format

Here the exponent ﬁeld is 11 bits and the signiﬁcant ﬁeld is 52 bits. The format is

shown in Figure 4.17.

Similar to the single-precision format, the extreme values of e (0 and 2047) are

reserved for the same purpose.

Exponent E2 Exponent E1

Subtract

Mantissa M2

Mantissa M1

Divide

Result normalization and round logic

Result Exponent Result Mantissa

Figure 4.15 FP division

Figure 4.16 IEEE single-precision representation

COMPUTER ARITHMETIC

A number of attributes characterizing the IEEE single- and double-precisi on

formats are summarized in Table 4.2.

4.4. SUMMARY

In this chapter, we have discussed a number of issues related to computer arithmetic.

Our discussion started with an introduction to number representation and radix con-

version techniques. We then discussed integer arithmetic and, in particular, we dis-

cussed the four main operations, that is, addition, subtraction, multiplication, and

division. In each case, we have shown basic architectures and organization. The

last topic discussed in the chapt er has been ﬂoating-point representation and arith-

metic. We have also shown the basic architectures needed to perform basic ﬂoat-

ing-point operations such as addition, subtraction, multiplication, and divisi on.

We ended our discussion in the chapter with the IEEE ﬂoating-point number

representation.

EXERCISES

1. Represent the decima l values 26, 2123 as signed, 10-bit numbers using each

of the following binary formats:

(a) Sign-and-magnitude;

(b) 2’s complement.

2. Compute the decimal value of the binary number 1011 1101 0101 0110 if the

given number represents unsigned integer. Repeat if the number represents

2’s complement. Repeat if the number represents sign-magnitude integer.

Figure 4.17 Double-precision representation

TABLE 4.2 Characteristics of the IEEE Single and Double

Floating-Point Formats

Characteristic Single-precision Double-precision

Length in bits 32 64

Fraction part in bits 23 52

Hidden bits 1 1

Exponent length in bits 8 11

Bias 127 1023

Approximate range 2

128

 3:8  10

1024

 9:0  10

307

Smallest normalized number 2

126

 10

38

1022

 10

308

EXERCISES 79

3. Consider the binary numbers in the following addition and subtraction pro-

blems to be signed 6-bit values in the 2’s complement representation. Per-

form each of the following operations, specifying whether ov erﬂow occurs.

010110 011001 110111 100001 111111 011010

þ001001 þ010000 þ101011 2011101 2000111 2100010

4. Multiply each of the following pairs of signed 2’s complement numbers

using the 2-bit Booth algorithm.

M ¼ 010111 M ¼ 110011 M ¼ 110101 M ¼ 1111

Q ¼ 110110 Q ¼ 101100 Q ¼ 011011 Q ¼ 1111

5. Divide each of the following pairs of signed 2

s complement numbers using

both the restoring and the nonrestoring algorithms.

X ¼ 010111 X ¼ 110011 X ¼ 110101 X ¼ 1111

D ¼ 110110 D ¼ 101100 D ¼ 011011 D ¼ 1111

6. Show how to perform addition, subtraction, multiplication, and division of

the following ﬂoating numbers.

A ¼ 0 10001 011011

B ¼ 1 01111 101010

The numbers are represented in a 12-bit format using a base b ¼ 2, a 5-bit

exponent e with a bias ¼ 16, and 6-bit normalized mantissa m.

7. Show a complete design (in terms of the logic equations) for a 4-bit adder/

subtractor using carry-look-ahead technique for all carries c

, c

Assume that the two 4-bit input numbers are A ¼ a

and

B ¼ b

8. Design a BCD adder using a 4-bit binary adder and the least number of logic

gates. The adder should receive two 4-bit numbers A and B and should pro-

duce 4-bit sum and a carry output.

9. Show a design of a 16-bit CLA that uses the 4-bit CLA block shown in

Figure 4.5. Compute the delay and the area (in terms of the number of

logic gates required).

10. Compare the longest path delay from input to output of a 32-bit adder using

4-bit CLA adder blocks in a multilevel architecture with that of a 32-bit CRT

adder. Assume that a gate delay is given by T

11. Convert each of the following decimal numbers to their IEEE single-

precision ﬂoating-point counterparts.

(a) 276

(b) 0.92

80 COMPUTER ARITHMETIC

(d) 20.000072

(e) 8.04 10

12. Convert the following IEEE single-precision ﬂoating-point numbers to their

decimal counterparts.

(a) 6589 00000

(b) 807B 00000H

13. Complete the logic design of the array multiplier shown in Figure 4.6.

14. Design the control logic shown in Figure 4.7.

15. Provide a complete logic design for the Control Logic indicated in

Figure 4.10.

REFERENCES AND FURTHER READING

C. Hamacher, Z. Vranesic and S. Zaky, Computer Organization, 5th ed., McGraw-Hill,

New York, 2002.

V. Heuring and H. Jordan, Computer Systems Design and Archiecture, Addison Wesley

Longman, NJ, USA, 1997.

K. Israel, Computer Arithmetic Algorithms, 2nd ed., A. K. Peters, Ltd., Massachusetts, 2002.

W. Stallings, Computer Organization and Architectures: Designing for Performance, 4th ed.,

Prentice-Hall, NJ, USA, 1996.

B. Wilkinson, Computer Architecture: Design and Performance, 2nd ed., Prentice-Hall,

Hertfordshire, UK, 1996.

REFERENCES AND FURTHER READING 81

CHAPTER 5

Processing Unit Design

In previous chapters, we studied the history of computer systems and the fundamen-

tal issues related to memory locations, addressing modes, assembly language, and

computer arithmetic. In this chapter, we focus our attention on the main component

of any computer system, the central processing unit (CPU). The primary function of

the CPU is to execu te a set of instructions stored in the computer’s memory. A

simple CPU consists of a set of registers, an arithmetic logic unit (ALU), and a con-

trol unit (CU). In what follows, the reader will be introduced to the organization and

main operations of the CPU.

5.1. CPU BASICS

A typical CPU has three major components: (1) register set, (2) arithmetic logic

unit (ALU), and (3) control unit (CU). The regist er set differs from one computer

architecture to another. It is usually a combina tion of general-purpose and special-

purpose registers. General-purpose registers are used for any purpose, hence the

name general purpose. Special-purpose registers have speciﬁc functions within

the CPU. For example, the program counter (PC) is a special-purpose register

that is used to hold the address of the instruction to be executed next. Another

example of special-purpose registers is the instruction register (IR), which is

used to hold the instruction that is currently executed. The ALU provides the cir-

cuitry needed to perform the arithmet ic, logical and shift operations demanded of

the instruction set. In Chapter 4, we have covered a number of arithmetic oper-

ations and circuits used to support computation in an ALU. The control unit is

the entity responsible for fetching the instruction to be executed from the main

memory and decoding and then executing it. Figure 5.1 shows the main com-

ponents of the CPU and its interactions with the memor y system and the input/

output devices.

The CPU fetches instructions from memory, reads and writes data from and to

memory, and transfers data from and to input/output devices. A typical and

Fundamentals of Computer Organization and Architecture, by M. Abd-El-Barr and H. El-Rewini