Digital Design and Computer Architecture,

Front Cover......Page 1
In Praise of Digital Designand Computer Architecture......Page 2
About the Authors......Page 5
Digital Design and Computer Architecture......Page 6
Copyright......Page 7
Dedication......Page 8
Table of Contents......Page 10
Preface......Page 20
  Accessible Overview of Advanced Microarchitecture......Page 21
 Online Supplements......Page 22
  Optional Tools: Synplify Premier and QtSpim......Page 23
 Acknowledgments......Page 24
 1.1 The Game Plan......Page 28
  1.2.1 Abstraction......Page 29
  1.2.2 Discipline......Page 30
  1.2.3 The Three-Y\'s......Page 31
 1.3 The Digital Abstraction......Page 32
  1.4.2 Binary Numbers......Page 34
  1.4.3 Hexadecimal Numbers......Page 36
  1.4.4 Bytes, Nibbles, and All That Jazz......Page 38
  1.4.5 Binary Addition......Page 39
   Sign/Magnitude Numbers......Page 40
   Two\'s Complement Numbers......Page 41
   Comparison of Number Systems......Page 43
 1.5 Logic Gates......Page 44
  1.5.3 AND Gate......Page 45
  1.5.6 Multiple-Input Gates......Page 46
  1.6.2 Logic Levels......Page 47
  1.6.3 Noise Margins......Page 48
  1.6.5 The Static Discipline......Page 49
 1.7 CMOS Transistors*......Page 51
  1.7.2 Diodes......Page 52
  1.7.4 nMOS and pMOS Transistors......Page 53
  1.7.6 Other CMOS Logic Gates......Page 56
  1.7.8 Pseudo-nMOS Logic......Page 58
 1.8 Power Consumption*......Page 59
 1.9 Summary and a Look Ahead......Page 60
 Exercises......Page 62
 Interview Questions......Page 77
 2.1 Introduction......Page 80
  2.2.2 Sum-of-Products Form......Page 83
 2.3 Boolean Algebra......Page 85
  2.3.2 Theorems of One Variable......Page 86
  2.3.3 Theorems of Several Variables......Page 87
  2.3.4 The Truth Behind It All......Page 89
  2.3.5 Simplifying Equations......Page 90
 2.4 From Logic to Gates......Page 91
 2.5 Multilevel Combinational Logic......Page 94
  2.5.1 Hardware Reduction......Page 95
  2.5.2 Bubble Pushing......Page 96
  2.6.1 Illegal Value: X......Page 98
  2.6.2 Floating Value: Z......Page 99
 2.7 Karnaugh Maps......Page 100
  2.7.1 Circular Thinking......Page 101
  2.7.2 Logic Minimization with K-Maps......Page 102
  2.7.3 Don\'t Cares......Page 106
  2.7.4 The Big Picture......Page 107
   2:1 Multiplexer......Page 108
   Multiplexer Logic......Page 109
  2.8.2 Decoders......Page 111
   Decoder Logic......Page 112
  2.9.1 Propagation and Contamination Delay......Page 113
  2.9.2 Glitches......Page 117
 2.10 Summary......Page 120
 Exercises......Page 122
 Interview Questions......Page 131
 3.2 Latches and Flip-Flops......Page 134
  3.2.1 SR Latch......Page 136
  3.2.2 D Latch......Page 138
  3.2.4 Register......Page 139
  3.2.5 Enabled Flip-Flop......Page 140
  3.2.7 Transistor-Level Latch and Flip-Flop Designs*......Page 141
  3.2.8 Putting It All Together......Page 143
  3.3.1 Some Problematic Circuits......Page 144
  3.3.2 Synchronous Sequential Circuits......Page 145
  3.3.3 Synchronous and Asynchronous Circuits......Page 147
  3.4.1 FSM Design Example......Page 148
  3.4.2 State Encodings......Page 154
  3.4.3 Moore and Mealy Machines......Page 157
  3.4.4 Factoring State Machines......Page 159
  3.4.5 Deriving an FSM from a Schematic......Page 162
  3.4.6 FSM Review......Page 165
 3.5 Timing of Sequential Logic......Page 166
  3.5.2 System Timing......Page 167
   Setup Time Constraint......Page 168
   Hold Time Constraint......Page 169
   Putting It All Together......Page 170
  3.5.3 Clock Skew*......Page 173
   Resolution Time......Page 176
  3.5.5 Synchronizers......Page 177
  3.5.6 Derivation of Resolution Time*......Page 179
 3.6 Parallelism......Page 182
 3.7 Summary......Page 186
 Exercises......Page 187
 Interview Questions......Page 196
  4.1.1 Modules......Page 198
  4.1.2 Language Origins......Page 199
   Simulation......Page 200
   Synthesis......Page 201
  4.2.1 Bitwise Operators......Page 202
  4.2.3 Reduction Operators......Page 205
  4.2.4 Conditional Assignment......Page 206
  4.2.5 Internal Variables......Page 207
  4.2.6 Precedence......Page 209
  4.2.7 Numbers......Page 210
  4.2.8 Z’s and X’s......Page 211
  4.2.10 Delays......Page 213
 4.3 Structural Modeling......Page 215
  4.4.1 Registers......Page 218
  4.4.2 Resettable Registers......Page 219
  4.4.3 Enabled Registers......Page 221
  4.4.4 Multiple Registers......Page 222
 4.5 More Combinational Logic......Page 223
  4.5.1 Case Statements......Page 226
  4.5.2 If Statements......Page 227
  4.5.4 Blocking and Nonblocking Assignments......Page 230
   Combinational Logic*......Page 232
   Sequential Logic*......Page 233
 4.6 Finite State Machines......Page 234
 4.7 Data Types*......Page 238
  4.7.1 SystemVerilog......Page 239
  4.7.2 VHDL......Page 240
 4.8 Parameterized Modules*......Page 242
 4.9 Testbenches......Page 245
 4.10 Summary......Page 249
 Exercises......Page 251
 Interview Questions......Page 262
  5.2.1 Addition......Page 264
   Ripple-Carry Adder......Page 265
   Carry-Lookahead Adder......Page 266
   Prefix Adder*......Page 268
   Putting It All Together......Page 270
  5.2.3 Comparators......Page 271
  5.2.4 ALU......Page 273
  5.2.5 Shifters and Rotators......Page 275
  5.2.6 Multiplication*......Page 277
  5.2.7 Division*......Page 278
  5.2.8 Further Reading......Page 279
  5.3.1 Fixed-Point Number Systems......Page 280
  5.3.2 Floating-Point Number Systems*......Page 281
   Single- and Double-Precision Formats......Page 282
   Floating-Point Addition......Page 283
  5.4.1 Counters......Page 285
   Scan Chains*......Page 286
  5.5.1 Overview......Page 288
   Organization......Page 289
   Memory Types......Page 290
  5.5.4 Area and Delay......Page 291
  5.5.5 Register Files......Page 292
  5.5.6 Read Only Memory......Page 293
  5.5.8 Memory HDL......Page 295
  5.6.1 Programmable Logic Array......Page 297
  5.6.2 Field Programmable Gate Array......Page 299
  5.6.3 Array Implementations*......Page 304
 5.7 Summary......Page 305
 Exercises......Page 307
 Interview Questions......Page 318
 6.1 Introduction......Page 320
  6.2.1 Instructions......Page 321
   Registers......Page 323
   The Register Set......Page 325
   Memory......Page 326
   Constants/Immediates......Page 329
  6.3.1 R-Type Instructions......Page 330
  6.3.2 l-Type Instructions......Page 332
  6.3.4 Interpreting Machine Language Code......Page 333
  6.3.5 The Power of the Stored Program......Page 334
  6.4.1 Arithmetic/Logical Instructions......Page 335
   Logical Instructions......Page 336
   Shift Instructions......Page 337
   Generating Constants......Page 338
   Conditional Branches......Page 339
   Jump......Page 340
   If Statements......Page 341
  6.4.4 Getting Loopy......Page 342
   While Loops......Page 343
   Magnitude Comparison......Page 344
   Array Indexing......Page 345
   Bytes and Characters......Page 347
   Function Calls and Returns......Page 350
   Input Arguments and Return Values......Page 351
   The Stack......Page 352
   Preserved Registers......Page 354
   Recursive Function Calls......Page 355
   Additional Arguments and Local Variables*......Page 357
 6.5 Addressing Modes......Page 358
   The Global Data Segment......Page 361
  6.6.2 Translating and Starting a Program......Page 362
   Step 1: Compilation......Page 363
   Step 2: Assembling......Page 364
   Step 3: Linking......Page 365
   Step 4: Loading......Page 366
  6.7.1 Pseudoinstructions......Page 367
  6.7.2 Exceptions......Page 368
   Addition and Subtraction......Page 369
   Loads......Page 370
  6.7.4 Floating-Point Instructions......Page 371
 6.8 Real-World Perspective: x86 Architecture*......Page 372
  6.8.2 x86 Operands......Page 373
  6.8.4 x86 Instructions......Page 375
  6.8.5 x86 Instruction Encoding......Page 377
  6.8.7 The Big Picture......Page 379
 6.9 Summary......Page 380
 Exercises......Page 382
 Interview Questions......Page 394
  7.1.1 Architectural State and Instruction Set......Page 396
  7.1.2 Design Process......Page 397
 7.2 Performance Analysis......Page 399
  7.3.1 Single-Cycle Datapath......Page 401
  7.3.2 Single-Cycle Control......Page 407
  7.3.3 More Instructions......Page 410
  7.3.4 Performance Analysis......Page 413
 7.4 Multicycle Processor......Page 414
  7.4.1 Multicycle Datapath......Page 415
  7.4.2 Multicycle Control......Page 421
  7.4.3 More Instructions......Page 428
  7.4.4 Performance Analysis......Page 430
 7.5 Pipelined Processor......Page 434
  7.5.1 Pipelined Datapath......Page 437
  7.5.2 Pipelined Control......Page 438
  7.5.3 Hazards......Page 439
   Solving Data Hazards with Forwarding......Page 441
   Solving Data Hazards with Stalls......Page 443
   Solving Control Hazards......Page 446
   Hazard Summary......Page 449
  7.5.5 Performance Analysis......Page 451
 7.6 HDL Representation*......Page 454
  7.6.1 Single-Cycle Processor......Page 455
  7.6.2 Generic Building Blocks......Page 459
  7.6.3 Testbench......Page 462
 7.7 Exceptions*......Page 465
  7.8.1 Deep Pipelines......Page 469
  7.8.2 Branch Prediction......Page 471
  7.8.3 Superscalar Processor......Page 472
  7.8.4 Out-of-Order Processor......Page 475
  7.8.5 Register Renaming......Page 477
  7.8.6 Single Instruction Multiple Data......Page 479
  7.8.7 Multithreading......Page 480
  7.8.9 Heterogeneous Multiprocessors......Page 481
 7.9 Real-World Perspective: x86 Microarchitecture*......Page 483
 7.10 Summary......Page 490
 Exercises......Page 492
 Interview Questions......Page 498
 8.1 Introduction......Page 500
 8.2 Memory System Performance Analysis......Page 504
 8.3 Caches......Page 505
  8.3.1 What Data is Held in the Cache?......Page 506
   Direct Mapped Cache......Page 507
   Multi-way Set Associative Cache......Page 511
   Fully Associative Cache......Page 512
   Block Size......Page 513
   Putting it All Together......Page 514
  8.3.3 What Data is Replaced?......Page 515
  8.3.4 Advanced Cache Design*......Page 516
   Multiple-Level Caches......Page 517
   Reducing Miss Rate......Page 518
   Write Policy......Page 519
  8.3.5 The Evolution of MIPS Caches*......Page 520
 8.4 Virtual Memory......Page 521
  8.4.1 Address Translation......Page 523
  8.4.2 The Page Table......Page 525
  8.4.3 The Translation Lookaside Buffer......Page 527
  8.4.4 Memory Protection......Page 528
  8.4.6 Multilevel Page Tables*......Page 529
 8.5 I/O Introduction......Page 531
 8.6 Embedded I/O Systems......Page 533
  8.6.1 PIC32MX675F512H Microcontroller......Page 534
  8.6.2 General-Purpose Digital I/O......Page 538
  8.6.3 Serial I/O......Page 540
   Serial Peripheral Interface (SPI)......Page 541
   Universal Asynchronous Receiver Transmitter (UART)......Page 546
  8.6.4 Timers......Page 552
  8.6.5 Interrupts......Page 554
  8.6.6 Analog I/O......Page 556
   A/D Conversion......Page 557
   D/A Conversion......Page 558
   Pulse-Width Modulation......Page 561
  8.6.7 Other Microcontroller Peripherals......Page 562
   Character LCDs......Page 563
   VGA Monitor......Page 566
   Bluetooth Wireless Communication......Page 572
   Motor Control......Page 573
   DC Motors......Page 574
   Servo Motor......Page 577
   Stepper Motor......Page 579
 8.7 PC I/O Systems......Page 583
  8.7.1 USB......Page 584
  8.7.2 PCI and PCI Express......Page 585
  8.7.4 Networking......Page 586
   Data Acquisition Systems......Page 587
   USB Links......Page 588
  8.8.1 x86 Cache Systems......Page 589
  8.8.3 x86 Programmed I/O......Page 592
 Epilogue......Page 593
 Exercises......Page 595
 Interview Questions......Page 605
 A.2 74xx Logic......Page 608
  A.3.1 PROMs......Page 609
  A.3.2 PLAs......Page 613
  A.3.3 FPGAs......Page 614
 A.5 Data Sheets......Page 616
 A.6 Logic Families......Page 622
  Packages......Page 624
  Breadboards......Page 625
  Printed Circuit Boards......Page 626
 A.8 Transmission Lines......Page 627
  A.8.1 Matched Termination......Page 629
  A.8.2 Open Termination......Page 631
  A.8.4 Mismatched Termination......Page 632
  A.8.6 Proper Transmission Line Terminations......Page 635
  A.8.7 Derivation of Z0*......Page 637
  A.8.8 Derivation of the Reflection Coefficient*......Page 638
  A.8.9 Putting It All Together......Page 639
 A.9 Economics......Page 640
B MIPS Instructions......Page 644
 C.1 Introduction......Page 648
 Summary......Page 649
   Main function: int main(void)......Page 650
 Summary......Page 651
  C.3.2 #define......Page 652
  C.3.3 #include......Page 653
 C.4 Variables......Page 654
  C.4.1 Primitive Data Types......Page 655
  C.4.2 Global and Local Variables......Page 656
 C.5 Operators......Page 658
 C.6 Function Calls......Page 662
 C.7 Control-Flow Statements......Page 663
   if/else Statements......Page 664
   switch/case Statements......Page 665
   do/while Loops......Page 666
   for Loops......Page 667
  C.8.1 Pointers......Page 668
  C.8.2 Arrays......Page 670
  C.8.3 Characters......Page 674
  C.8.4 Strings......Page 675
  C.8.5 Structures......Page 676
  C.8.6 * typedef......Page 678
  C.8.7 * Dynamic Memory Allocation......Page 679
  C.8.8 * Linked Lists......Page 680
   printf......Page 682
   File Manipulation......Page 685
   rand and srand......Page 687
   Format Conversion: atoi, atol, atof......Page 688
  C.9.3 math......Page 689
  C.10.2 Compiler Options......Page 690
  C.10.3 Command Line Arguments......Page 691
 C.11 Common Mistakes......Page 692
Further Reading......Page 698
 A......Page 700
 B......Page 701
 C......Page 702
 D......Page 703
 E......Page 704
 G......Page 705
 I......Page 706
 L......Page 707
 M......Page 708
 N......Page 709
 P......Page 710
 S......Page 711
 T......Page 713
 V......Page 714
 Z......Page 715