Preface
CHAPTER ONE
Digital Logic Circuits 1
1-1 Digital Computers 1
1-2 Logic Gates 4
1-3 Boolean Algebra 7
Complement of a Function 10
1-4 Map Simplification 11
Product'of'Sums Simplification 14
Don't'Care Conditions 16
1-5 Combinational Circuits 18
Half-Adder 19
Full-Adder 20
1-6 Flip-Flops 22
SR Flip-Flop 22
D Flip-Flop 23
JK Flip-Flop 24
T Flip-Fbp 24
Edge-Triggered Flip-Flops 25
Excitation Tables 27
1-7 Sequential Circuits 28
Fiip-Fiop Input Equations 28
State Table 30
State Diagram 3 J
Design Example 32
Design Procedure 36
Problems 37
References 39
CHAPTER TWO
Digital Components
2-1 Integrated Circuits 41
2-2 Decoders 41
NAND Gate Decoder 45
Decoder Expansion 46
Encoders 47
2-3 Multiplexers 48
2-4 Registers 50
Register with Parallel Load 51
2-5 Shift Registers 53
Bidirectional Shift Register with Parallel Load 53
2-6 Binary Counters 56
Binary Counter with Parallel Load 58
2-7 Memory Unit 58
Random-Access Memory 60
Read'Only Memory 61
Types of ROMs 62
Problems 63
References 65
CHAPTER THREE
Data Representation
3-1 Data Types 67
Number Systems 68
Octal and Hexadecimal Numbers 69
Decimal Representation 72
Alphanumeric Representation 73
3-2 Complements 74
(r-l)'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
3-5 Other Binary Codes 84
Gray Code 84
Other pecimal Codes 85
Other Alphanumeric Codes 86
3-6 Error Detection Codes 87
Problems 89
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 lncrementer .105
Arithmetic Circuit J 06
4-5 Logic Microoperations 108
List of Logic Microoperations 109
Hardware Implementation .111
Some Applications 111
4-6 Shift Microoperations 114
Hardware Implementation J15
4-7 Arithmetic Logic Shift Unit 116
Problems 119
References 122
CHAPTER FIVE
Basic Computer Organization and Design 123
5-1 Instruction Codes 123
Stored Program Organization 125
Indirect Address 126
5-2 Computer Registers 127
Common Bus System 129
5-3 Computer Instructions 132
Instruction Set Completeness 134
5-4 Timing and Control 135
5-5 Instruction Cycle 139
Fetch and Decode 139
Determine the Type of Instruction 141
Register-Reference Instructions 143
5-6 Memory-Reference Instructions 145
AND to AC 145
ADD to AC 146
LDA: Load to AC 146
STA: Store AC 147
BUN: Branch UncorvhtionaUy 147
BSA: Branch and Save Return Address 147
ISZ: Increment and Slap If Zero 149
Control Flowchart 149
5-7 Input-Output and Interrupt 150
Input-Output Configuration 151
Input-Output Instructions 152
Program Interrupt 153
Interrupt Cycle 156
5-8 Complete Computer Description 157
5-9 Design of Basic Computer 157
Control Logic Gates 160
Control of Registers and Memory 160
Control of Single Flip-Flops 162
Control of Common Bus 162
5-10 Design of Accumulator Logic 164
Control of AC Register 165
Adder and Logic Circuit 166
Problems 167 References 171
CHAPTER SIX
Programming the Basic Computer 173
6-1 Introduction 173
6-2 Machine Language 174
6-3 Assembly Language 179
Rules of the Language 179
An Example 181
Translation to Binary 182
6-4 The Assembler 183
Representation of Symbolic Program
in Memory 184
First Pass 185
Second Pass 187
6-5 Program Loops 190
6-6 Programming Arithmetic and Logic
Operations 192
Multiplication Program 193
Double-Precision Addition 196
Logic Operations 197
Shift Operations 197
6-7 Subroutines 198
Subroutines Parameters and Data Linkage 200
6-8 Input-Output Programming 203
Character Manipulation 204
Program Interrupt 205
Problems 208
References 211
CHAPTER SEVEN
Microprogrammed Control 213
7-1 Control Memory 213
7-2 Address Sequencing 216
Conditional Branching 217
Mapping of Instruction 219
Subroutines 220
7-3 Microprogram Example 220
Computer Configuration 220
Microinstruction Format 222
Symbolic Microinstructions 225
The Fetch Routine 226
Symbolic Microprogram 227
Binary Microprogram 229
7-4 Design of Control Unit 231
Microprogram Sequencer 232
Problems 235
References 238
CHAPTER EIGHT
Central Processing Unit 241
8-1 Introduction 241
8-2 General Register Organization 242
Control Word 244
Examples of Microoperations 246
8-3 Stack Organization 247
Register Stack 247
Memory Stack 249
Reverse Polish Notation 251
Evaluation of Arithmetic Expressions 253
8-4 Instruction formats 255
Three-Address Instructions 258
Two-Address Instructions 258
One-Address Instructions 259
Zero-Address Instructions 259
RISC Instructions 259
8-5 Addressing Modes 260
Numerical Example 264
8-6 Data Transfer and Manipulation 266
Data Transfer Instructions 267
Data Manipulation Instructions- 268
Arithmetic Instructions 269
Logical and Bit Manipulation Instructions 270
SAifc Mstructions 271
8-7 Program Control 273
Status Bit Conditions 274
Conditional Branch Instructions 275
Subroutine Call and Return 278
Program Interrupt 279
Types of Interrupts 281
8-8 Reductd Instruction Set Computer (RISC) 282
CISC Characteristics 283
RISC Characteristics 284
Overlapped Register Windows 285
Berkeley RISC I 288
Problems
References
CHAPTER NINE
Pipeline and Vector Processing
9-1 Parallel Processing 299
9-2 Pipelining 299
General Considerations 304
9-3 Arithmetic Pipeline
9-4 Instruction Pipeline
Example: Four-Segment Instruction Pipeline 311
Data Dependency 313
Handling of Branch Instructions 314
9-5 RISC Pipeline
Example: Three-Segment Instruction Pipeline 316
Delayed Load 317
Delayed Branch 318
9-6 Vector Processing
Vector Operations 321
Matrix Multiplication 322
Memory Interleaving 324
Supercomputers 325
9-7 Array Processors
Attached Array Processor 326
SIMD Array Processor 327 Problems References
CHAPTER TEN
Computer Arithmetic
10-1 Introduction 333
10-2 Addition and Subtraction 334
Addition and Subtraction with Signed-Magnitude
Data 335
Hardware Implementation 336
Hardware Algorithm 337
Addition and Subtraction with Signed-2's
Complement Data 338
10-3 Multiplication Algorithms 340
Hardware Implementation for Signed-Magnitude
Data 341
Hardware Algorithm 342
Booth Multiplication Algorithm 343
Array Multiplier 346
10-4 Division Algorithms 348
Hardware Implementation for Signed-Magnitude
Data 349
Divide Overflow 351
Hardware Algorithm 352 Other Algorithms 353
10-5 Floating-Point Arithmetic Operations 354
Basic Considerations 354 Register Configuration 357
Addition and Subtraction 358
Multiplication 360 --'Division 362
10-6 Decimal Arithmetic Unit 363
BCD Adder 365
BCD Subtraction 368
10-7 Decimal Arithmetic Operations 369
Addition and Subtraction 371
Multiplication 371
Division 374
Floating-Point Operations 376
Problems 376
References 380
CHAPTER ELEVEN
Input-Output Organization 381
11-1 Peripheral Devices 381
ASCII Alphanumeric Characters 383
11-2 Input-Output Interface 385
I/O Bus and Interface Modules 386
I/O versus Memory Bus 387
Isolated versus Memory-Mapped I/O 388
Example of I/O Interface 389
11-3 Asynchronous Data Transfer 391
Strobe Control 391
Handshaking 393
Asynchronous Serial Transfer 396
Asynchronous Communication Interface 398
First-In, First-Out Buffer 4 00
11-4 Ixodes of Transfer 402
Example of Programmed I/O 403
Interrupt-Initiated I/O 406
Software Considerations 406
11-5 Priority Interrupt 407
Daisy-Chaining Priority 408
Parallel Priority Interrupt 409
Priority Encoder 411
Interrupt Cycle 412
Software Routines 413
Initial and Final Operations 414
11-6 Direct Memory Access (DMA) 415
DMAController 416
DMA Transfer 418
11-7 Input-Output Processor (IOP) 420
CPU-IOP Communication 422
IBM 370 I/O Channel 423
Intel 8089 IOP 427
11-8 Serial Communication 429
Character-Oriented Protocol 432
Transmission Example 433
Data Transparency 436
Bit-Oriented Protocol 437
Problems 439
References 442
CHAPTER TWELVE
Memory Organization 445
12-1 Memory Hierarchy 445
12-2 Main Memory 448
RAM and ROM Chips 449
Memory Address Map 450
Memory Connection to CPU 452
12-3 Auxiliary Memory 452
Magnetic Disks 454
Magnetic Tape 455
12-4 Associative Memory 456
Hardware Organization 457
Match Logic 459
Read Operation 460
Write Operation 461
12-5 Cache Memory 462
Associative Mapping 464
Direct Mapping 465
Set-Associative Mapping 467
Writing into Cache 468
Cache Initialization 469
12-6 Virtual Memory
Address Space and Memory Space 470
Address Mapping Using Pages 472
Associative Memory Page Table 474
Page Replacement 475
12-7 Memory Management Hardware
Segmented-Page Mapping 477
Numerical Example 479
Memory Protection 482
Problems 483
References 486
CHAPTER THIRTEEN
Multiprocessor
13-1Characteristics of Multiprocessors 489
13-2 Interconnection Structures
Time'Shared Common Bus 491
Multipart Memory 493
crossbar Switch 494
Multistage Switching Network 496
Hypercube Interconnection 498
13-3 Interprocessor Arbitration 500
System Bus 500
Serial Arbitration Procedure 502
Parallel Arbitration Logic 503
Dynamic Arbitration Algorithms 505
13-4 Interprocessor Communication and
Synchronization 506
Interprocessor Synchronisation 507
Mutual Exclusion with a Semaphore 508
13-5^Cache Coherence 509
Conditions for Incoherence 509
Solutions to the Cache Coherence Problem 510
Problems 512
References 514
Index 515