Digital Design and Computer Architecture 2nd edition.pdf

Digital Design and Computer Architecture takes a unique and modern approach to digital design. Beginning with digital logic gates and progressing to the design of combinational and sequential circuits, Harris and Harris use these fundamental building blocks as the basis for what follows: the design of an actual MIPS processor. SystemVerilog and VHDL are integrated throughout the text in examples illustrating the methods and techniques for CAD-based circuit design. By the end of this book, readers will be able to build their own microprocessor and will have a top-to-bottom understanding of how it works. Harris and Harris have combined an engaging and humorous writing style with an updated and hands-on approach to digital design.

This second edition has been updated with new content on I/O systems in the context of general purpose processors found in a PC as well as microcontrollers found almost everywhere. The new edition provides practical examples of how to interface with peripherals using RS232, SPI, motor control, interrupts, wireless, and analog-to-digital conversion. High-level descriptions of I/O interfaces found in PCs include USB, SDRAM, WiFi, PCI Express, and others. In addition to expanded and updated material throughout, SystemVerilog is now featured in the programming and code examples (replacing Verilog), alongside VHDL. This new edition also provides additional exercises and a new appendix on C programming to strengthen the connection between programming and processor architecture.

【核心代码】

Contents
Preface .................................................... xix
Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xx
Online Supplements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
How to Use the Software Tools in a Course .................. xxii
Labs .................................................... xxiii
Bugs.................................................... xxiii
Acknowledgments ........................................ xxiii
Chapter 1 From Zero to One .................................. 3
1.1 The Game Plan ............................................ 3
1.2 The Art of Managing Complexity ........................... 4
1.2.1 Abstraction ........................................ 4
1.2.2 Discipline .......................................... 5
1.2.3 The Three-Y’s ...................................... 6
1.3 The Digital Abstraction .................................... 7
1.4 Number Systems ........................................... 9
1.4.1 Decimal Numbers .................................. 9
1.4.2 Binary Numbers .................................... 9
1.4.3 Hexadecimal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.4 Bytes, Nibbles, and All That Jazz . . . . . . . . . . . . . . . . . . . 13
1.4.5 Binary Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.6 Signed Binary Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Logic Gates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.1 NOT Gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.2 Buffer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.3 AND Gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.4 OR Gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.5 Other Two-Input Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.6 Multiple-Input Gates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6 Beneath the Digital Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.1 Supply Voltage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.2 Logic Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.3 Noise Margins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.4 DC Transfer Characteristics . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.5 The Static Discipline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
ix
1.7 CMOS Transistors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1 Semiconductors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.7.2 Diodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.7.3 Capacitors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.7.4 nMOS and pMOS Transistors . . . . . . . . . . . . . . . . . . . . . . 28
1.7.5 CMOS NOT Gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7.6 Other CMOS Logic Gates . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7.7 Transmission Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.7.8 Pseudo-nMOS Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.8 Power Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.9 Summary and a Look Ahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Interview Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Chapter 2 Combinational Logic Design ........................ 55
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.2 Boolean Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.2.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.2.2 Sum-of-Products Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.2.3 Product-of-Sums Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.3 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.3.1 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.3.2 Theorems of One Variable . . . . . . . . . . . . . . . . . . . . . . . . 61
2.3.3 Theorems of Several Variables . . . . . . . . . . . . . . . . . . . . . 62
2.3.4 The Truth Behind It All . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.3.5 Simplifying Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.4 From Logic to Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.5 Multilevel Combinational Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.5.1 Hardware Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.5.2 Bubble Pushing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.6 X’s and Z’s, Oh My . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.6.1 Illegal Value: X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.6.2 Floating Value: Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.7 Karnaugh Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.7.1 Circular Thinking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.7.2 Logic Minimization with K-Maps . . . . . . . . . . . . . . . . . . 77
2.7.3 Don’t Cares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
2.7.4 The Big Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
2.8 Combinational Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.8.1 Multiplexers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.8.2 Decoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
2.9 Timing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2.9.1 Propagation and Contamination Delay . . . . . . . . . . . . . 88
2.9.2 Glitches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
x CONTENTS
2.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Interview Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Chapter 3 Sequential Logic Design .......................... 109
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.2 Latches and Flip-Flops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.2.1 SR Latch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.2.2 D Latch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.2.3 D FIip-Flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.2.4 Register. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.2.5 Enabled Flip-Flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.2.6 Resettable Flip-Flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.2.7 Transistor-Level Latch and Flip-Flop Designs . . . . . . 116
3.2.8 Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
3.3 Synchronous Logic Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.3.1 Some Problematic Circuits. . . . . . . . . . . . . . . . . . . . . . . . 119
3.3.2 Synchronous Sequential Circuits . . . . . . . . . . . . . . . . . . 120
3.3.3 Synchronous and Asynchronous Circuits. . . . . . . . . . . 122
3.4 Finite State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.4.1 FSM Design Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.4.2 State Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
3.4.3 Moore and Mealy Machines . . . . . . . . . . . . . . . . . . . . . . 132
3.4.4 Factoring State Machines . . . . . . . . . . . . . . . . . . . . . . . . . 134
3.4.5 Deriving an FSM from a Schematic . . . . . . . . . . . . . . . 137
3.4.6 FSM Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
3.5 Timing of Sequential Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
3.5.1 The Dynamic Discipline . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.5.2 System Timing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.5.3 Clock Skew . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
3.5.4 Metastability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
3.5.5 Synchronizers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
3.5.6 Derivation of Resolution Time . . . . . . . . . . . . . . . . . . . . 154
3.6 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
Interview Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Chapter 4 Hardware Description Languages .................. 173
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
4.1.1 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
4.1.2 Language Origins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
4.1.3 Simulation and Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . 175
CONTENTS xi
4.2 Combinational Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.2.1 Bitwise Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.2.2 Comments and White Space . . . . . . . . . . . . . . . . . . . . . . 180
4.2.3 Reduction Operators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
4.2.4 Conditional Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . 181
4.2.5 Internal Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
4.2.6 Precedence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
4.2.7 Numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
4.2.8 Z’s and X’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
4.2.9 Bit Swizzling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
4.2.10 Delays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
4.3 Structural Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
4.4 Sequential Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
4.4.1 Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
4.4.2 Resettable Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
4.4.3 Enabled Registers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
4.4.4 Multiple Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
4.4.5 Latches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
4.5 More Combinational Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
4.5.1 Case Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
4.5.2 If Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
4.5.3 Truth Tables with Don’t Cares . . . . . . . . . . . . . . . . . . . 205
4.5.4 Blocking and Nonblocking Assignments . . . . . . . . . . . 205
4.6 Finite State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
4.7 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
4.7.1 SystemVerilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
4.7.2 VHDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
4.8 Parameterized Modules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
4.9 Testbenches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
4.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
Interview Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
Chapter 5 Digital Building Blocks ............................ 239
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
5.2 Arithmetic Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
5.2.1 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
5.2.2 Subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
5.2.3 Comparators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
5.2.4 ALU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
5.2.5 Shifters and Rotators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
5.2.6 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
xii CONTENTS
5.2.7 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
5.2.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
5.3 Number Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
5.3.1 Fixed-Point Number Systems . . . . . . . . . . . . . . . . . . . . . 255
5.3.2 Floating-Point Number Systems . . . . . . . . . . . . . . . . . . . 256
5.4 Sequential Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
5.4.1 Counters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
5.4.2 Shift Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
5.5 Memory Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
5.5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
5.5.2 Dynamic Random Access Memory (DRAM) . . . . . . . 266
5.5.3 Static Random Access Memory (SRAM) . . . . . . . . . . . 266
5.5.4 Area and Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
5.5.5 Register Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
5.5.6 Read Only Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
5.5.7 Logic Using Memory Arrays. . . . . . . . . . . . . . . . . . . . . . 270
5.5.8 Memory HDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
5.6 Logic Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
5.6.1 Programmable Logic Array . . . . . . . . . . . . . . . . . . . . . . . 272
5.6.2 Field Programmable Gate Array . . . . . . . . . . . . . . . . . . 274
5.6.3 Array Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Interview Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
Chapter 6 Architecture ..................................... 295
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
6.2 Assembly Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
6.2.1 Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
6.2.2 Operands: Registers, Memory, and Constants . . . . . . 298
6.3 Machine Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
6.3.1 R-Type Instructions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
6.3.2 I-Type Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
6.3.3 J-Type Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
6.3.4 Interpreting Machine Language Code . . . . . . . . . . . . . 308
6.3.5 The Power of the Stored Program . . . . . . . . . . . . . . . . . 309
6.4 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
6.4.1 Arithmetic/Logical Instructions . . . . . . . . . . . . . . . . . . . 310
6.4.2 Branching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
6.4.3 Conditional Statements. . . . . . . . . . . . . . . . . . . . . . . . . . . 316
6.4.4 Getting Loopy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
6.4.5 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
6.4.6 Function Calls. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
CONTENTS xiii
6.5 Addressing Modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
6.6 Lights, Camera, Action: Compiling, Assembling, and Loading. . . 336
6.6.1 The Memory Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
6.6.2 Translating and Starting a Program . . . . . . . . . . . . . . . 337
6.7 Odds and Ends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
6.7.1 Pseudoinstructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
6.7.2 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
6.7.3 Signed and Unsigned Instructions . . . . . . . . . . . . . . . . . 344
6.7.4 Floating-Point Instructions . . . . . . . . . . . . . . . . . . . . . . . 346
6.8 Real-World Perspective: x86 Architecture . . . . . . . . . . . . . . . . . . 347
6.8.1 x86 Registers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
6.8.2 x86 Operands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
6.8.3 Status Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
6.8.4 x86 Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
6.8.5 x86 Instruction Encoding . . . . . . . . . . . . . . . . . . . . . . . . 352
6.8.6 Other x86 Peculiarities. . . . . . . . . . . . . . . . . . . . . . . . . . . 354
6.8.7 The Big Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
Interview Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
Chapter 7 Microarchitecture ................................ 371
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
7.1.1 Architectural State and Instruction Set . . . . . . . . . . . . . 371
7.1.2 Design Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
7.1.3 MIPS Microarchitectures . . . . . . . . . . . . . . . . . . . . . . . . . 374
7.2 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
7.3 Single-Cycle Processor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
7.3.1 Single-Cycle Datapath . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
7.3.2 Single-Cycle Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
7.3.3 More Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
7.3.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
7.4 Multicycle Processor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
7.4.1 Multicycle Datapath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
7.4.2 Multicycle Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
7.4.3 More Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
7.4.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
7.5 Pipelined Processor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
7.5.1 Pipelined Datapath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
7.5.2 Pipelined Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
7.5.3 Hazards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
7.5.4 More Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
7.5.5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
xiv CONTENTS
7.6 HDL Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
7.6.1 Single-Cycle Processor . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
7.6.2 Generic Building Blocks. . . . . . . . . . . . . . . . . . . . . . . . . . 434
7.6.3 Testbench . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
7.7 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
7.8 Advanced Microarchitecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
7.8.1 Deep Pipelines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
7.8.2 Branch Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
7.8.3 Superscalar Processor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
7.8.4 Out-of-Order Processor . . . . . . . . . . . . . . . . . . . . . . . . . . 450
7.8.5 Register Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
7.8.6 Single Instruction Multiple Data . . . . . . . . . . . . . . . . . . 454
7.8.7 Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
7.8.8 Homogeneous Multiprocessors . . . . . . . . . . . . . . . . . . . . 456
7.8.9 Heterogeneous Multiprocessors . . . . . . . . . . . . . . . . . . . 456
7.9 Real-World Perspective: x86 Microarchitecture . . . . . . . . . . . . . 458
7.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
Interview Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
Chapter 8 Memory and I/O Systems ......................... 475
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
8.2 Memory System Performance Analysis . . . . . . . . . . . . . . . . . . . . . 479
8.3 Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
8.3.1 What Data is Held in the Cache? . . . . . . . . . . . . . . . . . 481
8.3.2 How is Data Found? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
8.3.3 What Data is Replaced? . . . . . . . . . . . . . . . . . . . . . . . . . . 490
8.3.4 Advanced Cache Design . . . . . . . . . . . . . . . . . . . . . . . . . . 491
8.3.5 The Evolution of MIPS Caches . . . . . . . . . . . . . . . . . . . 495
8.4 Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
8.4.1 Address Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
8.4.2 The Page Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
8.4.3 The Translation Lookaside Buffer. . . . . . . . . . . . . . . . . 502
8.4.4 Memory Protection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
8.4.5 Replacement Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
8.4.6 Multilevel Page Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
8.5 I/O Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
8.6 Embedded I/O Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508
8.6.1 PIC32MX675F512H Microcontroller . . . . . . . . . . . . . 509
8.6.2 General-Purpose Digital I/O . . . . . . . . . . . . . . . . . . . . . . 513
8.6.3 Serial I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
8.6.4 Timers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
CONTENTS xv
8.6.5 Interrupts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529
8.6.6 Analog I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
8.6.7 Other Microcontroller Peripherals. . . . . . . . . . . . . . . . . 537
8.7 PC I/O Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
8.7.1 USB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
8.7.2 PCI and PCI Express . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
8.7.3 DDR3 Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
8.7.4 Networking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561
8.7.5 SATA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
8.7.6 Interfacing to a PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
8.8 Real-World Perspective: x86 Memory and I/O Systems . . . . . . 564
8.8.1 x86 Cache Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564
8.8.2 x86 Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
8.8.3 x86 Programmed I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
8.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
Epilogue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570
Interview Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
Appendix A Digital System Implementation ................... 583
A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
A.2 74xx Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
A.2.1 Logic Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
A.2.2 Other Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
A.3 Programmable Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
A.3.1 PROMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
A.3.2 PLAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
A.3.3 FPGAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
A.4 Application-Specific Integrated Circuits . . . . . . . . . . . . . . . . . . . . 591
A.5 Data Sheets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
A.6 Logic Families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597
A.7 Packaging and Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
A.8 Transmission Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602
A.8.1 Matched Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
A.8.2 Open Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606
A.8.3 Short Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607
A.8.4 Mismatched Termination . . . . . . . . . . . . . . . . . . . . . . . . . 607
A.8.5 When to Use Transmission Line Models . . . . . . . . . . . 610
A.8.6 Proper Transmission Line Terminations . . . . . . . . . . . 610
A.8.7 Derivation of Z0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
A.8.8 Derivation of the Reflection Coefficient . . . . . . . . . . . . 613
A.8.9 Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . 614
A.9 Economics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615
xvi CONTENTS
Appendix B MIPS Instructions ............................... 619
Appendix C C Programming ................................. 623
C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623
C.2 Welcome to C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625
C.2.1 C Program Dissection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625
C.2.2 Running a C Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 626
C.3 Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
C.3.1 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
C.3.2 #define . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
C.3.3 #include . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628
C.4 Variables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
C.4.1 Primitive Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
C.4.2 Global and Local Variables . . . . . . . . . . . . . . . . . . . . . . 631
C.4.3 Initializing Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
C.5 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
C.6 Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
C.7 Control-Flow Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638
C.7.1 Conditional Statements. . . . . . . . . . . . . . . . . . . . . . . . . . . 639
C.7.2 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641
C.8 More Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
C.8.1 Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
C.8.2 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645
C.8.3 Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649
C.8.4 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650
C.8.5 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
C.8.6 typedef . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
C.8.7 Dynamic Memory Allocation . . . . . . . . . . . . . . . . . . . . . 654
C.8.8 Linked Lists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655
C.9 Standard Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
C.9.1 stdio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
C.9.2 stdlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662
C.9.3 math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
C.9.4 string . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
C.10 Compiler and Command Line Options . . . . . . . . . . . . . . . . . . . . 665
C.10.1 Compiling Multiple C Source Files . . . . . . . . . . . . . . . . 665
C.10.2 Compiler Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
C.10.3 Command Line Arguments . . . . . . . . . . . . . . . . . . . . . . . 666
C.11 Common Mistakes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
Further Reading ............................................ 673
Index ...................................................... 675