Structured Computer Organization

by Tanenbaum, Andrew S.

• ISBN13: 9780130959904
• ISBN10: 0130959901
• Edition: 5th
• Format: Hardcover
• Copyright: 2006-01-01
• Publisher: PRENTICE HALL

Summary

Preserving the same popular structure found in the previous four editions of this best-selling book, Andrew Tanenbaum teaches that a computer can be structured as a hierarchy of levels. In this book he covers them all, including the digital logic level, the microarchitecture level, the instruction set architecture level, the operating system machine level and the assembly language level.

Author Biography

Andrew S. Tanenbaum is a professor of computer science at the Vrije Universiteit in Amsterdam where he has taught courses in computer organization, operating systems and networks for over 30 years to thousands of students

Table of Contents

PREFACE	xvi
1 INTRODUCTION	1	(38)
1.1 STRUCTURED COMPUTER ORGANIZATION	2	(11)
1.1.1 Languages, Levels, and Virtual Machines	2	(2)
1.1.2 Contemporary Multilevel Machines	4	(4)
1.1.3 Evolution of Multilevel Machines	8	(5)
1.2 MILESTONES IN COMPUTER ARCHITECTURE	13	(11)
1.2.1 The Zeroth Generation--Mechanical Computers (1642-1945)	13	(3)
1.2.2 The First Generation--Vacuum Tubes (1945-1955)	16	(3)
1.2.3 The Second Generation--Transistors (1955-1965)	19	(2)
1.2.4 The Third Generation--Integrated Circuits (1965-1980)	21	(2)
1.2.5 The Fourth Generation--Very Large Scale Integration (1980-?)	23	(1)
1.3 THE COMPUTER ZOO	24	(5)
1.3.1 Technological and Economic Forces	25	(1)
1.3.2 The Computer Spectrum	26	(3)
1.4 EXAMPLE COMPUTER FAMILIES	29	(7)
1.4.1 Introduction to the Pentium II	29	(2)
1.4.2 Introduction to the UltraSPARC II	31	(3)
1.4.3 Introduction to the picoJava II	34	(2)
1.5 OUTLINE OF THIS BOOK	36	(3)
2 COMPUTER SYSTEMS ORGANIZATION	39	(78)
2.1 PROCESSORS	39	(17)
2.1.1 CPU Organization	40	(2)
2.1.2 Instruction Execution	42	(4)
2.1.3 RISC versus CISC	46	(1)
2.1.4 Design Principles for Modern Computers	47	(2)
2.1.5 Instruction-Level Parallelism	49	(4)
2.1.6 Processor-Level Parallelism	53	(3)
2.2 PRIMARY MEMORY	56	(12)
2.2.1 Bits	56	(1)
2.2.2 Memory Addresses	57	(1)
2.2.3 Byte Ordering	58	(3)
2.2.4 Error-Correcting Codes	61	(4)
2.2.5 Cache Memory	65	(2)
2.2.6 Memory Packaging and Types	67	(1)
2.3 SECONDARY MEMORY	68	(21)
2.3.1 Memory Hierarchies	69	(1)
2.3.2 Magnetic Disks	70	(3)
2.3.3 Floppy Disks	73	(1)
2.3.4 IDE Disks	73	(2)
2.3.5 SCSI Disks	75	(1)
2.3.6 RAID	76	(4)
2.3.7 CD-ROMs	80	(4)
2.3.8 CD-Recordables	84	(2)
2.3.9 CD-Rewritables	86	(1)
2.3.10 DVD	86	(3)
2.4 INPUT/OUTPUT	89	(24)
2.4.1 Buses	89	(2)
2.4.2 Terminals	91	(8)
2.4.3 Mice	99	(2)
2.4.4 Printers	101	(5)
2.4.5 Modems	106	(3)
2.4.6 Character Codes	109	(4)
2.5 SUMMARY	113	(4)
3 THE DIGITAL LOGIC LEVEL	117	(86)
3.1 GATES AND BOOLEAN ALGEBRA	117	(11)
3.1.1 Gates	118	(2)
3.1.2 Boolean Algebra	120	(2)
3.1.3 Implementation of Boolean Functions	122	(1)
3.1.4 Circuit Equivalence	123	(5)
3.2 BASIC DIGITAL LOGIC CIRCUITS	128	(13)
3.2.1 Integrated Circuits	128	(1)
3.2.2 Combinational Circuits	129	(5)
3.2.3 Arithmetic Circuits	134	(5)
3.2.4 Clocks	139	(2)
3.3 MEMORY	141	(13)
3.3.1 Latches	141	(2)
3.3.2 Flip-Flops	143	(2)
3.3.3 Registers	145	(1)
3.3.4 Memory Organization	146	(4)
3.3.5 Memory Chips	150	(2)
3.3.6 RAMs and ROMs	152	(2)
3.4 CPU CHIPS AND BUSES	154	(16)
3.4.1 CPU Chips	154	(2)
3.4.2 Computer Buses	156	(3)
3.4.3 Bus Width	159	(1)
3.4.4 Bus Clocking	160	(5)
3.4.5 Bus Arbitration	165	(2)
3.4.6 Bus Operations	167	(3)
3.5 EXAMPLE CPU CHIPS	170	(11)
3.5.1 The Pentium II	170	(6)
3.5.2 The UltraSPARC II	176	(3)
3.5.3 The picoJava II	179	(2)
3.6 EXAMPLE BUSES	181	(12)
3.6.1 The ISA Bus	181	(2)
3.6.2 The PCI Bus	183	(6)
3.6.3 The Universal Serial Bus	189	(4)
3.7 INTERFACING	193	(5)
3.7.1 I/O Chips	193	(2)
3.7.2 Address Decoding	195	(3)
3.8 SUMMARY	198	(5)
4 THE MICROARCHITECTURE LEVEL	203	(100)
4.1 AN EXAMPLE MICROARCHITECTURE	203	(15)
4.1.1 The Data Path	204	(7)
4.1.2 Microinstructions	211	(2)
4.1.3 Microinstruction Control: The Mic-1	213	(5)
4.2 AN EXAMPLE ISA: IJVM	218	(9)
4.2.1 Stacks	218	(2)
4.2.2 The IJVM Memory Model	220	(2)
4.2.3 The IJVM Instruction Set	222	(4)
4.2.4 Compiling Java to IJVM	226	(1)
4.3 AN EXAMPLE IMPLEMENTATION	227	(16)
4.3.1 Microinstructions and Notation	227	(5)
4.3.2 Implementation of IJVM Using the Mic-1	232	(11)
4.4 DESIGN OF THE MICROARCHITECTURE LEVEL	243	(21)
4.4.1 Speed versus Cost	243	(2)
4.4.2 Reducing the Execution Path Length	245	(8)
4.4.3 A Design with Prefetching: The Mic-2	253	(1)
4.4.4 A Pipelined Design: The Mic-3	253	(7)
4.4.5 A Seven-Stage Pipeline: The Mic-4	260	(4)
4.5 IMPROVING PERFORMANCE	264	(19)
4.5.1 Cache Memory	265	(5)
4.5.2 Branch Prediction	270	(6)
4.5.3 Out-of-Order Execution and Register Renaming	276	(5)
4.5.4 Speculative Execution	281	(2)
4.6 EXAMPLES OF THE MICROARCHITECTURE LEVEL	283	(15)
4.6.1 The Microarchitecture of the Pentium II CPU	283	(5)
4.6.2 The Microarchitecture of the UltraSPARC-II CPU	288	(3)
4.6.3 The Microarchitecture of the picoJava II CPU	291	(5)
4.6.4 A Comparison of the Pentium, UltraSPARC, and picoJava	296	(2)
4.7 SUMMARY	298	(5)
5 THE INSTRUCTION SET ARCHITECTURE LEVEL	303	(100)
5.1 OVERVIEW OF THE ISA LEVEL	305	(13)
5.1.1 Properties of the ISA Level	305	(2)
5.1.2 Memory Models	307	(2)
5.1.3 Registers	309	(2)
5.1.4 Instructions	311	(1)
5.1.5 Overview of the The Pentium II ISA Level	311	(2)
5.1.6 Overview of the The UltraSPARC II ISA Level	313	(4)
5.1.7 Overview of the Java Virtual Machine	317	(1)
5.2 DATA TYPES	318	(4)
5.2.1 Numeric Data Types	319	(1)
5.2.2 Nonnumeric Data Types	319	(1)
5.2.3 Data Types on the Pentium II	320	(1)
5.2.4 Data Types on the UltraSPARC II	321	(1)
5.2.5 Data Types on the Java Virtual Machine	321	(1)
5.3 INSTRUCTION FORMATS	322	(10)
5.3.1 Design Criteria for Instruction Formats	322	(3)
5.3.2 Expanding Opcodes	325	(2)
5.3.3 The Pentium II Instruction Formats	327	(1)
5.3.4 The UltraSPARC II Instruction Formats	328	(2)
5.3.5 The JVM Instruction Formats	330	(2)
5.4 ADDRESSING	332	(16)
5.4.1 Addressing Modes	333	(1)
5.4.2 Immediate Addressing	334	(1)
5.4.3 Direct Addressing	334	(1)
5.4.4 Register Addressing	334	(1)
5.4.5 Register Indirect Addressing	335	(1)
5.4.6 Indexed Addressing	336	(2)
5.4.7 Based-Indexed Addressing	338	(1)
5.4.8 Stack Addressing	338	(3)
5.4.9 Addressing Modes for Branch Instructions	341	(1)
5.4.10 Orthogonality of Opcodes and Addressing Modes	342	(2)
5.4.11 The Pentium II Addressing Modes	344	(2)
5.4.12 The UltraSPARC II Addressing Modes	346	(1)
5.4.13 The JVM Addressing Modes	346	(1)
5.4.14 Discussion of Addressing Modes	347	(1)
5.5 INSTRUCTION TYPES	348	(22)
5.5.1 Data Movement Instructions	348	(1)
5.5.2 Dyadic Operations	349	(1)
5.5.3 Monadic Operations	350	(2)
5.5.4 Comparisons and Conditional Branches	352	(1)
5.5.5 Procedure Call Instructions	353	(1)
5.5.6 Loop Control	354	(2)
5.5.7 Input/Output	356	(3)
5.5.8 The Pentium II Instructions	359	(3)
5.5.9 The UltraSPARC II Instructions	362	(2)
5.5.10 The picoJava II Instructions	364	(5)
5.5.11 Comparison of Instruction Sets	369	(1)
5.6 FLOW OF CONTROL	370	(13)
5.6.1 Sequential Flow of Control and Branches	371	(1)
5.6.2 Procedures	372	(4)
5.6.3 Coroutines	376	(3)
5.6.4 Traps	379	(1)
5.6.5 Interrupts	379	(4)
5.7 A DETAILED EXAMPLE: THE TOWERS OF HANOI	383	(5)
5.7.1 The Towers of Hanoi in Pentium II Assembly Language	384	(1)
5.7.2 The Towers of Hanoi in UltraSPARC II Assembly Language	384	(2)
5.7.3 The Towers of Hanoi in JVM Assembly Language	386	(2)
5.8 THE INTEL IA-64	388	(9)
5.8.1 The Problem with the Pentium II	390	(1)
5.8.2 The IA-64 Model: Explicitly Parallel Instruction Computing	391	(2)
5.8.3 Predication	393	(2)
5.8.4 Speculative Loads	395	(1)
5.8.5 Reality Check	396	(1)
5.9 SUMMARY	397	(6)
6 THE OPERATING SYSTEM MACHINE LEVEL	403	(80)
6.1 VIRTUAL MEMORY	404	(25)
6.1.1 Paging	405	(2)
6.1.2 Implementation of Paging	407	(2)
6.1.3 Demand Paging and the Working Set Model	409	(3)
6.1.4 Page Replacement Policy	412	(2)
6.1.5 Page Size and Fragmentation	414	(1)
6.1.6 Segmentation	415	(3)
6.1.7 Implementation of Segmentation	418	(3)
6.1.8 Virtual Memory on the Pentium II	421	(5)
6.1.9 Virtual Memory on the UltraSPARC	426	(2)
6.1.10 Virtual Memory and Caching	428	(1)
6.2 VIRTUAL I/O INSTRUCTIONS	429	(7)
6.2.1 Files	430	(1)
6.2.2 Implementation of Virtual I/O Instructions	431	(4)
6.2.3 Directory Management Instructions	435	(1)
6.3 VIRTUAL INSTRUCTIONS FOR PARALLEL PROCESSING	436	(10)
6.3.1 Process Creation	437	(1)
6.3.2 Race Conditions	438	(4)
6.3.3 Process Synchronization Using Semaphores	442	(4)
6.4 EXAMPLE OPERATING SYSTEMS	446	(30)
6.4.1 Introduction	446	(9)
6.4.2 Examples of Virtual Memory	455	(4)
6.4.3 Examples of Virtual I/O	459	(11)
6.4.4 Examples of Process Management	470	(6)
6.5 SUMMARY	476	(7)
7 THE ASSEMBLY LANGUAGE LEVEL	483	(40)
7.1 INTRODUCTION TO ASSEMBLY LANGUAGE	484	(10)
7.1.1 What Is an Assembly Language?	484	(1)
7.1.2 Why Use Assembly Language?	485	(3)
7.1.3 Format of an Assembly Language Statement	488	(3)
7.1.4 Pseudoinstructions	491	(3)
7.2 MACROS	494	(4)
7.2.1 Macro Definition, Call, and Expansion	494	(2)
7.2.2 Macros with Parameters	496	(1)
7.2.3 Advanced Features	497	(1)
7.2.4 Implementation of a Macro Facility in an Assembler	498	(1)
7.3 THE ASSEMBLY PROCESS	498	(8)
7.3.1 Two-Pass Assemblers	498	(1)
7.3.2 Pass One	499	(3)
7.3.3 Pass Two	502	(3)
7.3.4 The Symbol Table	505	(1)
7.4 LINKING AND LOADING	506	(13)
7.4.1 Tasks Performed by the Linker	508	(3)
7.4.2 Structure of an Object Module	511	(1)
7.4.3 Binding Time and Dynamic Relocation	512	(3)
7.4.4 Dynamic Linking	515	(4)
7.5 SUMMARY	519	(4)
8 PARALLEL COMPUTER ARCHITECTURES	523	(90)
8.1 DESIGN ISSUES FOR PARALLEL COMPUTERS	524	(30)
8.1.1 Communication Models	526	(4)
8.1.2 Interconnection Networks	530	(9)
8.1.3 Performance	539	(6)
8.1.4 Software	545	(6)
8.1.5 Taxonomy of Parallel Computers	551	(3)
8.2 SIMD COMPUTERS	554	(5)
8.2.1 Array Processors	554	(1)
8.2.2 Vector Processors	555	(4)
8.3 SHARED-MEMORY MULTIPROCESSORS	559	(27)
8.3.1 Memory Semantics	559	(5)
8.3.2 UMA Bus-Based SMP Architectures	564	(5)
8.3.3 UMA Multiprocessors Using Crossbar Switches	569	(2)
8.3.4 UMA Multiprocessors Using Multistage Switching Networks	571	(2)
8.3.5 NUMA Multiprocessors	573	(2)
8.3.6 Cache Coherent NUMA Multiprocessors	575	(10)
8.3.7 COMA Multiprocessors	585	(1)
8.4 MESSAGE-PASSING MULTICOMPUTERS	586	(23)
8.4.1 MPPs--Massively Parallel Processors	587	(5)
8.4.2 COWs--Clusters of Workstations	592	(1)
8.4.3 Scheduling	593	(5)
8.4.4 Communication Software for Multicomputers	598	(3)
8.4.5 Application-Level Shared Memory	601	(8)
8.5 SUMMARY	609	(4)
9 READING LIST AND BIBLIOGRAPHY	613	(18)
9.1 SUGGESTIONS FOR FURTHER READING	613	(7)
9.1.1 Introduction and General Works	613	(1)
9.1.2 Computer Systems Organization	614	(1)
9.1.3 The Digital Logic Level	615	(1)
9.1.4 The Microarchitecture Level	616	(1)
9.1.5 The Instruction Set Architecture Level	617	(1)
9.1.6 The Operating System Machine Level	617	(1)
9.1.7 The Assembly Language Level	618	(1)
9.1.8 Parallel Computer Architectures	618	(2)
9.1.9 Binary and Floating-Point Numbers	620	(1)
9.2 ALPHABETICAL BIBLIOGRAPHY	620	(11)
A BINARY NUMBERS	631	(12)
A.1 FINITE-PRECISION NUMBERS	631	(2)
A.2 RADIX NUMBER SYSTEMS	633	(2)
A.3 CONVERSION FROM ONE RADIX TO ANOTHER	635	(2)
A.4 NEGATIVE BINARY NUMBERS	637	(3)
A.5 BINARY ARITHMETIC	640	(3)
B FLOATING-POINT NUMBERS	643	(10)
B.1 PRINCIPLES OF FLOATING POINT	644	(2)
B.2 IEEE FLOATING-POINT STANDARD 754	646	(7)
INDEX	653