Computer System Architecture Textbook PDF

www.pearson.co.in This edition is manufactured in India and is authorized for sale only in India, Bangladesh, Bhutan, Pakistan, Nepal, Sri Lanka and the Maldives. FM.qxd 5/21/2007 5:18 PM Page i EON...

www.pearson.co.in This edition is manufactured in India and is authorized for sale only in India, Bangladesh, Bhutan, Pakistan, Nepal, Sri Lanka and the Maldives. FM.qxd 5/21/2007 5:18 PM Page i EON PreMedia CONFIRMING PGS THIRD EDITION COMPUTER SYSTEM ARCHITECTURE M. Morris Mano California State University Los Angeles FM.qxd 5/21/2007 5:18 PM Page ii EON PreMedia CONFIRMING PGS The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories to determine their effectiveness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the docu- mentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of the furnishing, performance, or use of these theories and programs. Authorized adaptation from the United States edition, entitled Computer System Architecture, Third Edition, ISBN: 0131755633 by Mano, Morris M., published by Pearson Education, Inc., © 1993 Indian Subcontinent Adaptation Copyright © 2007 Dorling Kindersley (India) Pvt. Ltd. This book is sold subject to the condition that it shall not, by way of trade or otherwise, be lent, resold, hired out, or otherwise circulated without the publisher’s prior written consent in any form of binding or cover other than that in which it is published and without a similar condition including this condition being imposed on the subsequent purchaser and without limiting the rights under copyright reserved above, no part of this publication may be reproduced, stored in or introduced into a retrieval system, or transmitted in any form or by any means (electronic, mechanical, photocopying, recording or otherwise), without the prior written permission of both the copyright owner and the above-mentioned publisher of this book. No part of this eBook may be used or reproduced in any manner whatsoever without the publisher’s prior written consent. This eBook may or may not include all assets that were part of the print version. The publisher reserves the right to remove any material in this eBook at any time. ISBN 81-317-0070-4 eISBN 978-93-325-7613-1 First Impression, 2007 This edition is manufactured in India and is authorized for sale only in India, Bangladesh, Bhutan, Pakistan, Nepal, Sri Lanka and the Maldives. Published by Dorling Kindersley (India) Pvt. Ltd., licensees of Pearson Education in South Asia. Head Office: 15th Floor, Tower-B, World Trade Tower, Plot No. 1, Block-C, Sector-16, Noida 201 301, Uttar Pradesh, India. Registered Office: 4th Floor, Software Block, Elnet Software City, TS-140, Block 2 & 9, Rajiv Gandhi Salai, Taramani, Chennai 600 113, Tamil Nadu, India. Fax: 080-30461003, Phone: 080-30461060 www.pearson.co.in, Email: [email protected] FM.qxd 5/21/2007 5:18 PM Page iii EON PreMedia CONFIRMING PGS Contents Preface xv CHAPTER ONE Digital Logic Circuits 1 1-1 Digital Computers 1 1-2 Logic Gates 5 1-3 Boolean Algebra 7 Complement of a Function 12 1-4 Map Simplification 12 Product-of-Sums Simplification 16 Don’t-Care Conditions 18 1-5 Combinational Circuits 20 Half-Adder 21 Full-Adder 22 1-6 Flip-Flops 24 SR Flip-Flop 24 D Flip-Flop 25 JK Flip-Flop 26 T Flip-Flop 26 Edge-Triggered Flip-Flops 27 Excitation Tables 28 1-7 Sequential Circuits 29 Flip-Flop Input Equations 30 State Table 31 State Diagram 33 Design Example 33 Design Procedure 36 Problems 38 References 40 iii FM.qxd 5/21/2007 5:18 PM Page iv EON PreMedia CONFIRMING PGS iv Contents CHAPTER TWO Digital Components 41 2-1 Integrated Circuits 41 2-2 Decoders 43 NAND Gate Decoder 45 Decoder Expansion 46 Encoders 47 2-3 Multiplexers 47 2-4 Registers 50 Register with Parallel Load 50 2-5 Shift Registers 52 Bidirectional Shift Register with Parallel Load 53 2-6 Binary Counters 55 Binary Counter with Parallel Load 56 2-7 Memory Unit 59 Random-Access Memory 60 Read-Only Memory 61 Types of ROMs 62 Problems 63 References 65 CHAPTER THREE Data Representation 67 3-1 Data Types 67 Number Systems 68 Octal and Hexadecimal Numbers 69 Decimal Representation 72 Alphanumeric Representation 73 3-2 Complements 74 (r ⫺ 1)’s Complement 75 (r’s) Complement 75 Subtraction of Unsigned Numbers 76 3-3 Fixed-Point Representation 77 Integer Representation 78 Arithmetic Addition 79 Arithmetic Subtraction 80 Overflow 80 Decimal Fixed-Point Representation 81 3-4 Floating-Point Representation 83 FM.qxd 5/21/2007 5:18 PM Page v EON PreMedia CONFIRMING PGS Contents v 3-5 Other Binary Codes 84 Gray Code 85 Other Decimal Codes 85 Other Alphanumeric Codes 87 3-6 Error Detection Codes 87 Problems 90 References 91 CHAPTER FOUR Register Transfer and Microoperations 93 4-1 Register Transfer Language 93 4-2 Register Transfer 95 4-3 Bus and Memory Transfers 97 Three-State Bus Buffers 100 Memory Transfer 101 4-4 Arithmetic Microoperations 102 Binary Adder 103 Binary Adder-Subtractor 104 Binary Incrementer 105 Arithmetic Circuit 106 4-5 Logic Microoperations 108 List of Logic Microoperations 109 Hardware Implementation 111 Some Applications 111 4-6 Shift Microoperations 114 Hardware Implementation 115 4-7 Arithmetic Logic Shift Unit 116 4-8 Hardware Description Languages 118 Introduction to VHDL 119 Basic Framework and Syntax 119 Problems 121 References 124 CHAPTER FIVE Basic Computer Organization and Design 125 5-1 Instruction Codes 125 Stored Program Organization 127 Indirect Address 128 FM.qxd 5/21/2007 5:18 PM Page vi EON PreMedia CONFIRMING PGS vi Contents 5-2 Computer Registers 129 Common Bus System 131 5-3 Computer Instructions 134 Instruction Set Completeness 136 5-4 Timing and Control 137 5-5 Instruction Cycle 141 Fetch and Decode 141 Determine the Type of Instruction 143 Register-Reference Instructions 145 5-6 Memory-Reference Instructions 147 AND to AC 147 ADD to AC 148 LDA: Load to AC 148 STA: Store AC 149 BUN: Branch Unconditionally 149 BSA: Branch and Save Return Address 149 ISZ: Increment and Skip if Zero 151 Control Flowchart 151 5-7 Input–Output and Interrupt 152 Input–Output Configuration 153 Input–Output Instructions 154 Program Interrupt 155 Interrupt Cycle 158 5-8 Complete Computer Description 159 5-9 Design of Basic Computer 159 Control Logic Gates 160 Control of Registers and Memory 160 Control of Single Flip-flops 164 Control of Common Bus 164 5-10 Design of Accumulator Logic 166 Control of AC Register 167 Adder and Logic Circuit 168 Problems 169 References 173 CHAPTER SIX Programming the Basic Computer 175 6-1 Introduction 175 6-2 Machine Language 176 FM.qxd 5/21/2007 5:18 PM Page vii EON PreMedia CONFIRMING PGS Contents vii 6-3 Assembly Language 181 Rules of the Language 181 An Example 183 Translation to Binary 184 6-4 The Assembler 185 Representation of Symbolic Program in Memory 186 First Pass 187 Second Pass 189 6-5 Program Loops 192 6-6 Programming Arithmetic and Logic Operations 194 Multiplication Program 195 Double-Precision Addition 198 Logic Operations 199 Shift Operations 199 6-7 Subroutines 200 Subroutine Parameters and Data Linkage 202 6-8 Input–Output Programming 205 Character Manipulation 206 Program Interrupt 207 Problems 210 References 213 CHAPTER SEVEN Microprogrammed Control 215 7-1 Control Memory 215 7-2 Address Sequencing 218 Conditional Branching 219 Mapping of Instruction 221 Subroutines 222 7-3 Microprogram Example 222 Computer Configuration 222 Microinstruction Format 224 Symbolic Microinstructions 227 The Fetch Routine 228 Symbolic Microprogram 229 Binary Microprogram 231 FM.qxd 5/21/2007 5:18 PM Page viii EON PreMedia CONFIRMING PGS viii Contents 7-4 Design of Control Unit 233 Microprogram Sequencer 234 Problems 237 References 240 CHAPTER EIGHT Central Processing Unit 243 8-1 Introduction 243 8-2 General Register Organization 244 Control Word 245 Examples of Microoperations 248 8-3 Stack Organization 249 Register Stack 249 Memory Stack 251 Reverse Polish Notation 253 Evaluation of Arithmetic Expressions 255 8-4 Instruction Formats 257 Three-Address Instructions 260 Two-Address Instructions 260 One-Address Instructions 261 Zero-Address Instructions 261 RISC Instructions 261 8-5 Addressing Modes 262 Numerical Example 266 8-6 Data Transfer and Manipulation 268 Data Transfer Instructions 269 Data Manipulation Instructions 270 Arithmetic Instructions 271 Logical and Bit Manipulation Instructions 272 Shift Instructions 273 8-7 Program Control 275 Status Bit Conditions 276 Conditional Branch Instructions 277 Subroutine Call and Return 280 Program Interrupt 281 Types of Interrupts 283 8-8 Reduced Instruction Set Computer (RISC) 284 CISC Characteristics 285 RISC Characteristics 286 FM.qxd 5/21/2007 5:18 PM Page ix EON PreMedia CONFIRMING PGS Contents ix Overlapped Register Windows 287 Berkeley RISC I 290 Problems 293 References 299 CHAPTER NINE Pipeline and Vector Processing 301 9-1 Parallel Processing 301 9-2 Pipelining 304 General Considerations 306 9-3 Arithmetic Pipeline 309 9-4 Instruction Pipeline 312 Example: Four-Segment Instruction Pipeline 313 Data Dependency 315 Handling of Branch Instructions 316 9-5 RISC Pipeline 317 Example: Three-Segment Instruction Pipeline 318 Delayed Load 319 Delayed Branch 320 9-6 Vector Processing 321 Vector Operations 323 Matrix Multiplication 324 Memory Interleaving 326 Superscalar Processors 327 Supercomputers 328 9-7 Array Processors 329 Attached Array Processor 329 SIMD Array Processor 330 Problems 331 References 333 CHAPTER TEN Computer Arithmetic 335 10-1 Introduction 335 10-2 Addition and Subtraction 336 Addition and Subtraction with Signed-Magnitude Data 337 FM.qxd 5/21/2007 5:18 PM Page x EON PreMedia CONFIRMING PGS x Contents Hardware Implementation 338 Hardware Algorithm 339 Addition and Subtraction with Signed-2’s Complement Data 340 10-3 Multiplication Algorithms 342 Hardware Implementation for Signed-Magnitude Data 343 Hardware Algorithm 344 Booth Multiplication Algorithm 345 Array Multiplier 348 10-4 Division Algorithms 350 Hardware Implementation for Signed-Magnitude Data 351 Divide Overflow 353 Hardware Algorithm 354 Other Algorithms 355 10-5 Floating-Point Arithmetic Operations 356 Basic Considerations 356 Register Configuration 359 Addition and Subtraction 360 Multiplication 362 Division 364 10-6 Decimal Arithmetic Unit 365 BCD Adder 367 BCD Subtraction 370 10-7 Decimal Arithmetic Operations 371 Addition and Subtraction 373 Multiplication 373 Division 376 Floating-Point Operations 378 Problems 378 References 382 CHAPTER ELEVEN Input–Output Organization 383 11-1 Peripheral Devices 383 ASCII Alphanumeric Characters 385 11-2 Input–Output Interface 387 I/O Bus and Interface Modules 388 I/O versus Memory Bus 389 FM.qxd 5/21/2007 5:18 PM Page xi EON PreMedia CONFIRMING PGS Contents xi Isolated versus Memory-Mapped I/O 390 Example of I/O Interface 391 11-3 Asynchronous Data Transfer 393 Strobe Control 394 Handshaking 395 Asynchronous Serial Transfer 398 Asynchronous Communication Interface 400 First-In, First-Out Buffer 402 11-4 Modes of Transfer 404 Example of Programmed I/O 405 Interrupt-Initiated I/O 408 Software Considerations 408 11-5 Priority Interrupt 409 Daisy-Chaining Priority 410 Parallel Priority Interrupt 411 Priority Encoder 413 Interrupt Cycle 414 Software Routines 415 Initial and Final Operations 416 11-6 Direct Memory Access (DMA) 417 DMA Controller 418 DMA Transfer 420 11-7 Input–Output Processor (IOP) 422 CPU—IOP Communication 424 IBM 370 I/O Channel 425 Intel 8089 IOP 429 11-8 Serial Communication 431 Character-Oriented Protocol 434 Transmission Example 435 Data Transparency 438 Bit-Oriented Protocol 439 Problems 441 References 444 C H A P T E R T W E LV E Memory Organization 447 12-1 Memory Hierarchy 447 12-2 Main Memory 450 RAM and ROM Chips 451 FM.qxd 5/21/2007 5:18 PM Page xii EON PreMedia CONFIRMING PGS xii Contents Memory Address Map 452 Memory Connection to CPU 454 12-3 Auxiliary Memory 454 Magnetic Disks 456 Magnetic Tape 457 12-4 Associative Memory 458 Hardware Organization 459 Match Logic 461 Read Operation 462 Write Operation 463 12-5 Cache Memory 464 Associative Mapping 466 Direct Mapping 467 Set-Associative Mapping 469 Writing into Cache 470 Cache Initialization 471 12-6 Virtual Memory 471 Address Space and Memory Space 472 Address Mapping Using Pages 474 Associative Memory Page Table 476 Page Replacement 477 12-7 Memory Management Hardware 478 Segmented-Page Mapping 479 Numerical Example 481 Memory Protection 484 Problems 485 References 488 CHAPTER THIRTEEN Multiprocessors 491 13-1 Characteristics of Multiprocessors 491 13-2 Interconnection Structures 493 Time-Shared Common Bus 493 Multiport Memory 495 Crossbar Switch 496 Multistage Switching Network 498 Hypercube Interconnection 500 13-3 Interprocessor Arbitration 502 System Bus 502 FM.qxd 5/21/2007 5:18 PM Page xiii EON PreMedia CONFIRMING PGS Contents xiii Serial Arbitration Procedure 504 Parallel Arbitration Logic 505 Dynamic Arbitration Algorithms 507 13-4 Interprocessor Communication and Synchronization 507 Interprocessor Synchronization 509 Mutual Exclusion with a Semaphore 509 Problems 511 References 512 Index 513 FM.qxd 5/21/2007 5:18 PM Page xiv EON PreMedia CONFIRMING PGS This page is intentionally left blank. FM.qxd 5/21/2007 5:18 PM Page xv EON PreMedia CONFIRMING PGS Preface This book deals with computer architecture as well as computer organization and design. Computer architecture is concerned with the structure and behavior of the various functional modules of the computer and how they interact to provide the processing needs of the user. Computer organization is concerned with the way the hardware components are connected together to form a computer system. Computer design is concerned with the development of the hardware for the computer taking into consideration a given set of specifications. The book provides the basic knowledge necessary to understand the hardware operation of digital computers and covers the three subjects associ- ated with computer hardware. Chapters 1 through 4 present the various digital components used in the organization and design of digital computers. Chapters 5 through 7 show the detailed steps that a designer must go through in order to design an elementary basic computer. Chapters 8 through 10 deal with the organization and architecture of the central processing unit. Chapters 11 and 12 present the organization and architecture of input–output and memory. Chapter 13 introduces the concept of multiprocessing. The plan of the book is to present the simpler material first and introduce the more advanced subjects later. Thus, the first seven chapters cover material needed for the basic understanding of computer organization, design, and programming of a simple digital computer. The last six chapters present the organization and architecture of the separate functional units of the digital computer with an emphasis on more advanced topics. The material in the third edition is organized in the same manner as in the second edition and many of the features remain the same. The third edition, however, offers several improvements over the second edition. All chapters except two (6 and 10) have been completely revised to bring the material up to date and to clarify the presentation. Two new chapters were added: chapter 9 on pipeline and vector processing, and chapter 13 on multiprocessors. Two sections deal with the reduced instruction set computer (RISC). Chapter 5 has been revised completely to simplify and clarify the design of the basic computer. New problems have been formulated for eleven of the thirteen chapters. xv FM.qxd 5/21/2007 5:18 PM Page xvi EON PreMedia CONFIRMING PGS xvi Preface The physical organization of a particular computer including its registers, the data flow, the microoperations, and control functions can be described symbolically by means of a hardware description language. In this book we develop a simple register transfer language and use it to specify various computer operations in a concise and precise manner. The relation of the register transfer language to the hardware organization and design of digital computers is fully explained. The book does not assume prior knowledge of computer hardware and the material can be understood without the need of prerequisites. However, some experience in assembly language programming with a microcomputer will make the material easier to understand. Chapters 1 through 3 can be skipped if the reader is familiar with digital logic design. The following is a brief description of the subjects that are covered in each chapter with an emphasis on the revisions that were made in the third edition. Chapter 1 introduces the fundamental knowledge needed for the design of digital systems constructed with individual gates and flip-flops. It covers Boolean algebra, combinational circuits, and sequential circuits. This provides the necessary background for understanding the digital circuits to be presented. Chapter 2 explains in detail the logical operation of the most common standard digital components. It includes decoders, multiplexers, registers, counters, and memories. These digital components are used as building blocks for the design of larger units in the chapters that follow. Chapter 3 shows how the various data types found in digital computers are represented in binary form in computer registers. Emphasis is on the rep- resentation of numbers employed in arithmetic operations, and on the binary coding of symbols used in data processing. Chapter 4 introduces a register transfer language and shows how it is used to express microoperations in symbolic form. Symbols are defined for arithmetic, logic, and shift microoperations. A composite arithmetic logic shift unit is developed to show the hardware design of the most common micro- operations. Chapter 5 presents the organization and design of a basic digital com- puter. Although the computer is simple compared to commercial computers, it nevertheless encompasses enough functional capabilities to demonstrate the power of a stored program general purpose device. Register transfer language is used to describe the internal operation of the computer and to specify the requirements for its design. The basic computer uses the same set of instruc- tions as in the second edition but its hardware organization and design has been completely revised. By going through the detailed steps of the design presented in this chapter, the student will be able to understand the inner workings of digital computers. Chapter 6 utilizes the twenty five instructions of the basic computer to illustrate techniques used in assembly language programming. Programming examples are presented for a number of data processing tasks. The relationship FM.qxd 5/21/2007 5:18 PM Page xvii EON PreMedia CONFIRMING PGS Preface xvii between binary programs and symbolic code is explained by examples. The basic operations of an assembler are presented to show the translation from symbolic code to an equivalent binary program. Chapter 7 introduces the concept of microprogramming. A specific microprogrammed control unit is developed to show by example how to write microcode for a typical set of instructions. The design of the control unit is carried-out in detail including the hardware for the microprogram sequencer. Chapter 8 deals with the central processing unit (CPU). An execution unit with common buses and an arithmetic logic unit is developed to show the gen- eral register organization of a typical CPU. The operation of a memory stack is explained and some of its applications are demonstrated. Various instruction formats are illustrated together with a variety of addressing modes. The most common instructions found in computers are enumerated with an explanation of their function. The last section introduces the reduced instruction set computer (RISC) concept and discusses its characteristics and advantages. Chapter 9 on pipeline and vector processing is a new chapter in the third edition. (The material on arithmetic operations from the second edition has been moved to Chapter 10.) The concept of pipelining is explained and the way it can speed-up processing is illustrated with several examples. Both arith- metic and instruction pipeline is considered. It is shown how RISC processors can achieve single-cycle instruction execution by using an efficient instruction pipeline together with the delayed load and delayed branch techniques. Vector processing is introduced and examples are shown of floating-point operations using pipeline procedures. Chapter 10 presents arithmetic algorithms for addition, subtraction, mul- tiplication, and division and shows the procedures for implementing them with digital hardware. Procedures are developed for signed-magnitude and signed-2’s complement fixed-point numbers, for floating-point binary num- bers, and for binary coded decimal (BCD) numbers. The algorithms are presented by means of flowcharts that use the register transfer language to specify the sequence of microoperations and control decisions required for their implementation. Chapter 11 discusses the techniques that computers use to communicate with input and output devices. Interface units are presented to show the way that the processor interacts with external peripherals. The procedure for asyn- chronous transfer of either parallel or serial data is explained. Four modes of transfer are discussed: programmed I/O, interrupt initiated transfer, direct memory access, and the use of input–output processors. Specific examples illustrate procedures for serial data transmission. Chapter 12 introduces the concept of memory hierarchy, composed of cache memory, main memory, and auxiliary memory such as magnetic disks. The organization and operation of associative memories is explained in detail. The concept of memory management is introduced through the presentation of the hardware requirements tor a cache memory and a virtual memory system. FM.qxd 5/21/2007 5:18 PM Page xviii EON PreMedia CONFIRMING PGS xviii Preface Chapter 13 presents the basic characteristics of mutiprocessors. Various interconnection structures are presented. The need for interprocessor arbitration, communication, and synchronization is discussed. Every chapter includes a set of problems and a list of references. Some of the problems serve as exercises for the material covered in the chapter. Others are of a more advanced nature and are intended to provide practice in solving problems associated with computer hardware architecture and design. A solutions manual is available for the instructor from the publisher. The book is suitable for a course in computer hardware systems in an electrical engineering, computer engineering, or computer science department. Parts of the book can be used in a variety of ways: as a first course in computer hardware by covering Chapters 1 through 7; as a course in computer organiza- tion and design with previous knowledge of digital logic design by reviewing Chapter 4 and then covering chapters 5 through 13; as a course in computer organization and architecture that covers the five functional units of digital computers including control (Chapter 7), processing unit (Chapters 8 and 9), arithmetic operations (Chapter 10), input–output (Chapter 11), and memory (Chapter 12). The book is also suitable for self-study by engineers and scientists who need to acquire the basic knowledge of computer hardware architecture. Acknowledgments My thanks goes to those who reviewed the text: particularly Professor Thomas L. Casavant of the University of Iowa; Professor Murray R. Berkowitz of George Mason University; Professor Cem Ersoy of Brooklyn Polytechnic University; Professor Upkar Varshney of the University of Missouri, Kansas City; Professor Karan Watson of Texas A&M University, and Professor Scott F. Midkiff of the Virginia Polytechnic Institute. M. Morris Mano I am grateful to K. Raja Kumar, Assistant Professor, Department of Computer Science and Systems Engineering, Andhra University, Visakhapatnam, for typing and incorporating the changes made in the text. I am also thankful to my wife, P. Rama Lakshmi, and children, Ravi Kumar and Rajani, for their support. P. Seetha Ramiah The publishers would like to thank P. Seetha Ramaiah, Professor, Department of Computer Science and Systems Engineering, Andhra University, Visakhapatnam, for his valuable suggestions and inputs in enhancing the content of this book to suit the requirements of Indian universities. Chapter01.qxd 2/2/2007 6:04 PM Page 1 EON PreMedia CONFIRMING PGS CHAPTER ONE Digital Logic Circuits IN THIS CHAPTER 1-1 Digital Computers 1-2 Logic Gates 1-3 Boolean Algebra 1-4 Map Simplification 1-5 Combinational Circuits 1-6 Flip-Flops 1-7 Sequential Circuits 1-1 Digital Computers The digital computer is a digital system that performs various computational tasks. The word digital implies that the information in the computer is represented by variables that take a limited number of discrete values. These values are processed internally by components that can maintain a limited number of discrete states. The decimal digits 0, 1, 2,... , 9, for example, provide 10 discrete values. The first electronic digital computers, developed in the late 1940s, were used primarily for numerical computations. In this case the discrete elements are the digits. From this application the term digital computer has emerged. In practice, digital computers function more reliably if only two states are used. Because of the physical restric- tion of components, and because human logic tends to be binary (i.e., true-or-false, yes-or-no statements), digital components that are constrained to take discrete val- ues are further constrained to take only two values and are said to be binary. Digital computers use the binary number system, which has two digits: 0 and 1. A binary digit is called a bit. Information is represented in digital computers in groups of bits. By using various coding techniques, groups of bits can be made to represent not only binary numbers but also other discrete symbols, such as deci- mal digits or letters of the alphabet. By judicious use of binary arrangements and by using various coding techniques, the groups of bits are used to develop com- plete sets of instructions for performing various types of computations. 1 Chapter01.qxd 2/2/2007 6:04 PM Page 2 EON PreMedia CONFIRMING PGS 2 CHAPTER ONE Digital Logic Circuits In contrast to the common decimal numbers that employ the base 10 sys- tem, binary numbers use a base 2 system with two digits: 0 and 1. The decimal equivalent of a binary number can be found by expanding it into a power series with a base of 2. For example, the binary number 1001011 represents a quantity that can be converted to a decimal number by multiplying each bit by the base 2 raised to an integer power as follows: 1
26  0
25  0
24  1
23  0
22  1
21  1
20  75 The seven bits 1001011 represent a binary number whose decimal equivalent is 75. However, this same group of seven bits represents the letter K when used in conjunction with a binary code for the letters of the alphabet. It may also represent a control code for specifying some decision logic in a particular digi- tal computer. In other words, groups of bits in a digital computer are used to rep- resent many different things. This is similar to the concept that the same letters of an alphabet are used to construct different languages, such as English and French. A computer system is sometimes subdivided into two functional entities: hardware and software. The hardware of the computer consists of all the elec- tronic components and electromechanical devices that comprise the physical entity of the device. Computer software consists of the instructions and data that the computer manipulates to perform various data-processing tasks. A sequence of program instructions for the computer is called a program. The data that are manipulated by the program constitute the data base. A computer system is composed of its hardware and the system software available for its use. The system software of a computer consists of a collection of programs whose purpose is to make more effective use of the computer. The programs included in a systems software package are referred to as the operating system. They are distinguished from application programs written by the user for the purpose of solving particular problems. For example, a high- level language program written by a user to solve particular data-processing needs is an application program, but the compiler that translates the high-level language program to machine language is a system program. The customer who buys a computer system would need, in addition to the hardware, any available software needed for effective operation of the computer. The system software is an indispensable part of a total computer system. Its function is to compensate for the differences that exist between user needs and the capability of the hardware. computer hardware The hardware of the computer is usually divided into three major parts, as shown in Fig. 1-1. The central processing unit (CPU) contains an arithmetic and logic unit for manipulating data, a number of registers for storing data, and control circuits for fetching and executing instructions. The memory of a computer contains storage for instructions and data. It is called a random-access memory (RAM) because the CPU can access any location in memory at random and retrieve the binary information within a fixed interval of time. The input and Chapter01.qxd 2/2/2007 6:04 PM Page 3 EON PreMedia CONFIRMING PGS SECTION 1-1 Digital Computers 3 Random-access memory (RAM) Central processing unit CPU Input Input-output processor Output devices (IOP) devices Figure 1-1 Block diagram of a digital computer. output processor (IOP) contains electronic circuits for communicating and controlling the transfer of information between the computer and the outside world. The input and output devices connected to the computer include keyboards, printers, terminals, magnetic disk drives, and other communication devices. This book provides the basic knowledge necessary to understand the hard- ware operations of a computer system. The subject is sometimes considered from three different points of view, depending on the interest of the investigator. When dealing with computer hardware it is customary to distinguish between what is referred to as computer organization, computer design, and computer architecture. computer Computer organization is concerned with the way the hardware components organization operate and the way they are connected together to form the computer system. The various components are assumed to be in place and the task is to investigate the organizational structure to verify that the computer parts operate as intended. computer Computer design is concerned with the hardware design of the computer. design Once the computer specifications are formulated, it is the task of the designer to develop hardware for the system. Computer design is concerned with the deter- mination of what hardware should be used and how the parts should be con- nected. This aspect of computer hardware is sometimes referred to as computer implementation. computer Computer architecture is concerned with the structure and behavior of the com- architecture puter as seen by the user. It includes the information, formats, the instruction set, and techniques for addressing memory. The architectural design of a computer sys- tem is concerned with the specifications of the various functional modules, such as processors and memories, and structuring them together into a computer system. Two basic types of computer architectures are von Neumann architecture and Harvard architecture. von Neumann architecture describes a general frame- work, or structure, that a computer’s hardware, programming, and data should follow. Although other structures for computing have been devised and imple- mented, the vast majority of computers in use today operate according to the von Chapter01.qxd 2/2/2007 6:04 PM Page 4 EON PreMedia CONFIRMING PGS 4 CHAPTER ONE Digital Logic Circuits Neumann architecture. Von Neumann envisioned the structure of a computer sys- tem as being composed of the following components: 1. the central arithmetic unit, which today is called the arithmetic-logic unit (ALU). This unit performs the computer’s computational and logical functions; 2. memory; more specifically, the computer’s main, or fast, memory, such as random access memory (RAM); 3. a control unit that directs other components of the computer to perform certain actions, such as directing the fetching of data or instructions from memory to be processed by the ALU; and 4. man-machine interfaces; i.e., input and output devices, such as a keyboard for input and display monitor for output, as shown in Fig. 1.1. Of course, computer technology has developed extensively since von Neumann’s time. For instance, due to integrated circuitry and miniaturization, the ALU and control unit have been integrated onto the same microprocessor “chip”, becoming an integrated part of the computer’s central processing unit (CPU). The most note- worthy concept contained in von Neumann’s first report was most likely that of the stored-program principle. This principle holds that data, as well as the instructions used to manipulate that data, should be stored together in the same memory area of the computer and instructions are carried out sequentially, one instruction at a time. The sequential execution of programming imposes a sort of ‘speed limit’ on program execution, since only one instruction at a time can be handled by the computer’s processor. It means that the CPU can be either reading an instruction or reading/writing data from/to the memory. Both cannot occur at the same time since the instructions and data use the same signal pathways and memory. The Harvard architecture uses physically separate storage and signal path- ways for their instructions and data. The term originated from the Harvard Mark I relay-based computer, which stored instructions on punched tape (24-bits wide) and data in relay latches (23-digits wide). In a computer with Harvard architec- ture, the CPU can read both an instruction and data from memory at the same time, leading to double the memory bandwidth. An example of computer architecture based on the von Neumann architec- ture is the desktop personal computer. Microcontroller (single-chip microcom- puter)-based computer systems and DSP (Digital Signal Processor)-based computer systems are examples for Harvard architecture. The book deals with all three subjects associated with computer hardware. In Chapters 1 through 4 we present the various digital components used in the organization and design of computer systems. Chapters 5 through 7 cover the steps that a designer must go through to design and program an elementary digi- tal computer. Chapters 8 and 9 deal with the architecture of the central process- ing unit. In Chapters 11 and 12 we present the organization and architecture of the input—output processor and the memory unit. Chapter01.qxd 2/2/2007 6:04 PM Page 5 EON PreMedia CONFIRMING PGS SECTION 1-2 Logic Gates 5 1-2 Logic Gates Binary information is represented in digital computers by physical quantities called signals. Electrical signals such as voltages exist throughout the computer in either one of two recognizable states. The two states represent a binary variable that can be equal to 1 or 0. For example, a particular digital computer may employ a signal of 3 volts to represent binary 1 and 0.5 volt to represent binary 0. The input terminals of digital circuits accept binary signals of 3 and 0.5 volts and the circuits respond at the output terminals with signals of 3 and 0.5 volts to represent binary input and output corresponding to 1 and 0, respectively. Binary logic deals with binary variables and with operations that assume a log- ical meaning. It is used to describe, in algebraic or tabular form, the manipulation and processing of binary information. The manipulation of binary information is gates done by logic circuits called gates. Gates are blocks of hardware that produce signals of binary 1 or 0 when input logic requirements are satisfied. A variety of logic gates are commonly used in digital computer systems. Each gate has a distinct graphic symbol and its operation can be described by means of an algebraic expression. The input—output relationship of the binary variables for each gate can be represented in tabular form by a truth table. The basic logic gates are AND and inclusive OR with multiple inputs and NOT with a single input. Each gate with more than one input is sensitive to either logic 0 or logic 1 input at any one of its inputs, generating the output according to its function. For example, a multi-input AND gate is sensi- tive to logic 0 on any one of its inputs, irrespective of any values at other inputs. The names, graphic symbols, algebraic functions, and truth tables of eight logic gates are listed in Fig. 1-2, with applicable sensitivity input values. Each gate has one or two binary input variables designated by A and B and one binary output variable designated by x. The AND gate produces the AND logic function: that is, the out- put is 1 if input A and input B are both equal to 1; otherwise, the output is 0. These conditions are also specified in the truth table for the AND gate. The table shows that output x is 1 only when both input A and input B are 1. The algebraic operation symbol of the AND function is the same as the multiplication symbol of ordinary arithmetic. We can either use a dot between the variables or concatenate the vari- ables without an operation symbol between them. AND gates may have more than two inputs, and by definition, the output is 1 if and only if all inputs are 1. OR The OR gate produces the inclusive-OR function; that is, the output is 1 if input A or input B or both inputs are 1; otherwise, the output is 0. The algebraic symbol of the OR function is , similar to arithmetic addition. OR gates may have more than two inputs, and by definition, the output is 1 if any input is 1. inverter The inverter circuit inverts the logic sense of a binary signal. It produces the NOT, or complement, function. The algebraic symbol used for the logic comple- ment is either a prime or a bar over the variable symbol. In this book we use a prime for the logic complement of a binary variable, while a bar over the letter is reserved for designating a complement microoperation as defined in Chap. 4. The small circle in the output of the graphic symbol of an inverter designates a logic complement. A triangle symbol by itself designates a buffer circuit. A Chapter01.qxd 2/2/2007 6:04 PM Page 6 EON PreMedia CONFIRMING PGS 6 CHAPTER ONE Digital Logic Circuits Graphic Algebraic Truth Input Name symbol function table sensitivity A B x A x = A B 0 0 0 AND B x or 0 1 0 0 x = AB 1 0 0 1 1 1 A B x A 0 0 0 OR x x=A+B 0 1 1 1 B 1 0 1 1 1 1 A x Inverter A x x = A' 0 1 1 0 Not Applicable A x Buffer A x x=A 0 0 Not Applicable 1 1 A B x A 0 0 1 NAND x x = (AB )' 0 1 1 0 B 1 0 1 1 1 0 A B x A 0 0 1 NOR x x = (A + B )' 0 1 0 1 B 1 0 0 1 1 0 A B x Exclusive-OR A x=A+B 0 0 0 x or 0 1 1 Not Applicable (XOR) B x = A'B + AB' 1 0 1 1 1 0 A B x Exclusive-NOR A x = (A + B)' 0 0 1 x or 0 1 0 Not Applicable or equivalence B x = A'B + AB' 1 0 0 1 1 1 Figure 1-2 Digital logic gates with applicable input sensitivity values. Chapter01.qxd 2/2/2007 6:04 PM Page 7 EON PreMedia CONFIRMING PGS SECTION 1-3 Boolean Algebra 7 buffer does not produce any particular logic function since the binary value of the output is the same as the binary value of the input. This circuit is used merely for power amplification. For example, a buffer that uses 3 volts for binary 1 will pro- duce an output of 3 volts when its input is 3 volts. However, the amount of elec- trical power needed at the input of the buffer is much less than the power produced at the output of the buffer. The main purpose of the buffer is to drive other gates that require a large amount of power. NAND The NAND function is the complement of the AND function, as indicated by the graphic symbol, which consists of an AND graphic symbol followed by a small circle. The designation NAND is derived from the abbreviation of NOR NOT-AND. The NOR gate is the complement of the OR gate and uses an OR graphic symbol followed by a small circle. Both NAND and NOR gates may have more than two inputs, and the output is always the complement of the AND or OR function, respectively. exclusive-OR The exclusive-OR gate has a graphic symbol similar to the OR gate except for the additional curved line on the input side. The output of this gate is 1 if any input is 1 but excludes the combination when both inputs are 1. The exclusive-OR func- tion has its own algebraic symbol or can be expressed in terms of AND, OR, and complement operations as shown in Fig. 1-2. The exclusive-NOR is the complement of the exclusive-OR, as indicated by the small circle in the graphic symbol. The out- put of this gate is 1 only if both inputs are equal to 1 or both inputs are equal to 0. A more fitting name for the exclusive-OR operation would be an odd function; that is, its output is 1 if an odd number of inputs are 1. Thus in a three-input exclusive-OR (odd) function, the output is 1 if only one input is 1 or if all three inputs are 1. The exclusive-OR and exclusive-NOR gates are commonly available with two inputs, and only seldom are they found with three or more inputs. 1-3 Boolean Algebra A Boolean algebra is an algebra (set, operations, elements) consisting of a set B with 2 elements, together with three operations—the AND operation  (Boolean product), the OR operation + (Boolean sum), and the NOT operation (comple- ment)—defined on the set, such that for any element a, b, c,... of set B, a  b, a  b, and a are in B. Consider the four-element Boolean algebra B4  ({0, x, y, 1}; , , ; 0, 1). The AND, OR, and NOT operations are described by the following tables:  0 x y 1  0 x y 1  0 0 0 0 0 0 0 x y 0 0 1 x 0 x 0 x x x x 1 1 x y y 0 0 y y y y 1 y 1 y x 1 0 x y 1 1 1 1 1 1 1 0 Chapter01.qxd 2/2/2007 6:05 PM Page 8 EON PreMedia CONFIRMING PGS 8 CHAPTER ONE Digital Logic Circuits Consider the two-element Boolean algebra B2  ({0, 1}; , , ; 0, 1). The three operations. (AND), + (OR), '(NOT) are defined as follows:  0 1  0 1  0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 The two-element Boolean algebra B2 among all other Bi , where i > 2, defined as switching algebra, is the most useful. Switching algebra consists of two elements represented by 1 and 0 as the largest number and the smallest number respectively. *Boolean algebra is a switching algebra that deals with binary variables and logic operations. The variables are designated by letters such as A, B, x, and y. The Boolean function three basic logic operations are AND, OR, and complement. A Boolean function can be expressed algebraically with binary variables, the logic operation symbols, parentheses, and equal sign. For a given value of the variables, the Boolean func- tion can be either 1 or 0. Consider, for example, the Boolean function F  x  yz The function F is equal to 1 if x is 1 or if both y and z are equal to 1; F is equal to 0 otherwise. But saying that y  1 is equivalent to saying that y  0 since y is the complement of y. Therefore, we may say that F is equal to 1 if x  1 or if yz  01. The relationship between a function and its binary variables can be represented in a truth table. To represent a function in a truth table we need a list of the 2n com- truth table binations of the n binary variables. As shown in Fig. l-3(a), there are eight possi- ble distinct combinations for assigning bits to the three variables x, y, and z. The function F is equal to 1 for those combinations where x  1 or yz  01; it is equal to 0 for all other combinations. A Boolean function can be transformed from an algebraic expression into a logic diagram composed of AND, OR, and inverter gates. The logic diagram logic diagram for F is shown in Fig. l-3(b). There is an inverter for input y to generate its x y z F 0 0 0 0 0 0 1 1 x 0 1 0 0 0 1 1 0 y F 1 0 0 1 1 0 1 1 z 1 1 0 1 1 1 1 1 (a) Truth table (b) Logic diagram Figure 1-3 Truth table and logic diagram for F  x  yz. *Two Element Chapter01.qxd 2/2/2007 6:05 PM Page 9 EON PreMedia CONFIRMING PGS SECTION 1-3 Boolean Algebra 9 complement y. There is an AND gate for the term yz , and an OR gate is used to combine the two terms. In a logic diagram, the variables of the function are taken to be the inputs of the circuit, and the variable symbol of the function is taken as the output of the circuit. The purpose of Boolean algebra is to facilitate the analysis and design of dig- ital circuits. It provides a convenient tool to: 1. Express in algebraic form a truth table relationship between binary vari- ables. 2. Express in algebraic form the input—output relationship of logic diagrams. 3. Find simpler circuits for the same function. A Boolean function specified by a truth table can be expressed algebraically in many different ways. Two ways of forming Boolean expressions are canonical and non-canonical forms. Canonical forms express all binary variables in every prod- uct (AND) or sum (OR) term of the Boolean function. To determine the canoni- cal sum-of-products form for a Boolean function F (A, B, C )  AB  C  ABC, which is in non-canonical form, the following steps are used: F  AB  C  ABC  AB(C  C)  (A  A)(B  B)C  ABC, where x  x  1 is a basic identity of Boolean algebra  ABC  ABC  ABC  ABC  ABC  ABC  ABC  ABC  ABC  ABC  ABC   ABC  ABC By manipulating a Boolean expression according to Boolean algebra rules, one may obtain a simpler expression that will require fewer gates. To see how this is done, we must first study the manipulative capabilities of Boolean algebra. Table 1-1 lists the most basic identities of Boolean algebra. All the identi- ties in the table can be proven by means of truth tables. The first eight identi- ties show the basic relationship between a single variable and itself, or in TABLE 1-1 Basic Identities of Boolean Algebra (1) x  0  x (2) x  0  0 (3) x  1  1 (4) x  1  x (5) x  x  x (6) x  x  x (7) x  x  1 (8) x  x  0 (9) x  y  y  x (10) xy  yx (11) x  (y  z )  (x  y)  z (12) x(yz)  (xy)z (13) x (y  z