Front Cover 1
Top-Down Digital VLSI Design: From Architectures to Gate-Level Circuits and FPGAs 4
Copyright 5
Contents 6
Preface 16
Why This Book? 16
Highlights 17
Notes to Instructors 17
Acknowledgments 20
Chapter 1: Introduction to Microelectronics 22
1.1 Economic Impact 22
1.2 Microelectronics Viewed From Different Perspectives 25
1.2.1 The Guinness Book of Records Point of View 25
1.2.2 The Marketing Point of View 26
General-purpose ICs 26
Application-specific integrated circuit 26
1.2.3 The Fabrication Point of View 28
Full-custom ICs 28
Semi-custom ICs 28
Field-programmable logic 32
Standard parts 32
1.2.4 The Design Engineer's Point of View 32
Hand layout 32
Cell libraries and schematic entry 33
Automatic circuit synthesis 36
Design with virtual components 38
Electronic system-level (ESL) design automation 39
1.2.5 The Business Point of View 39
1.3 The VLSI Design Flow 41
1.3.1 The Y-chart, a Map of Digital Electronic Systems 41
1.3.2 Major Stages in Digital VLSI Design 43
1.3.3 Cell Libraries 52
1.3.4 Electronic Design Automation Software 53
1.4 Problems 55
1.5 Appendix I: A Brief Glossary of Logic Families 56
1.6 Appendix II: An Illustrated Glossary ofCircuit-Related Terms 58
Chapter 2: Field-Programmable Logic 62
2.1 General Idea 62
2.2 Configuration Technologies 64
2.2.1 Static Memory 64
2.2.2 Flash Memory 65
2.2.3 Antifuses 65
2.3 Organization of Hardware Resources 67
2.3.1 Simple Programmable Logic Devices (SPLD) 67
2.3.2 Complex Programmable Logic Devices (CPLD) 68
2.3.3 Field-Programmable Gate Arrays (FPGA) 68
2.4 Commercial Aspects 74
2.4.1 An Overview on FPL Device Families 74
2.4.2 The Price and the Benefits of Electrical Configurability 74
2.5 Extensions of the Basic Idea 76
2.6 The FPL Design Flow 80
2.7 Conclusions 82
Chapter 3: From Algorithms to Architectures 84
3.1 The Goals of Architecture Design 84
3.1.1 Agenda 84
3.2 The Architectural Solution Space 86
3.2.1 The Antipodes 86
3.2.2 What Makes an Algorithm Suitable for a Dedicated VLSI Architecture? 92
3.2.3 There is Plenty of Land Between the Antipodes 95
3.2.4 Assemblies of General-Purpose and Dedicated Processing Units 96
3.2.5 Host Computer with Helper Engines 97
3.2.6 Application-Specific Instruction set Processors 98
3.2.7 Reconfigurable Computing 100
3.2.8 Extendable Instruction set Processors 102
3.2.9 Platform ICs (DSPP) 103
3.2.10 Digest 104
3.3 Dedicated VLSI Architectures and How to Design Them 108
3.3.1 There is Room for Remodeling in the Algorithmic Domain ... 108
3.3.2 ... and there is Room in the Architectural Domain 110
3.3.3 Systems Engineers and VLSI Designers Must Collaborate 111
3.3.4 A Graph-Based Formalism for Describing Processing Algorithms 113
3.3.5 The Isomorphic Architecture 115
3.3.6 Relative Merits of Architectural Alternatives 116
3.3.7 Computation Cycle Versus Clock Period 118
3.4 Equivalence Transforms for Combinational Computations 119
3.4.1 Common Assumptions 120
3.4.2 Iterative Decomposition 121
Performance and cost analysis 121
3.4.3 Pipelining 124
Performance and cost analysis 124
Pipelining in the presence of multiple feedforward paths 127
3.4.4 Replication 129
Performance and cost analysis 129
3.4.5 Time Sharing 131
Performance and cost analysis 132
3.4.6 Associativity Transform 137
3.4.7 Other Algebraic Transforms 138
3.4.8 Digest 139
3.5 Options for Temporary Storage of Data 141
3.5.1 Data Access Patterns 141
3.5.2 Available Memory Configurations and Area Occupation 141
3.5.3 Storage Capacities 142
3.5.4 Wiring and the Costs of Going Off-Chip 143
3.5.5 Latency and Timing 143
3.5.6 Digest 144
3.6 Equivalence Transforms for Non-Recursive Computations 147
3.6.1 Retiming 147
3.6.2 Pipelining Revisited 148
3.6.3 Systolic Conversion 151
3.6.4 Iterative Decomposition and Time Sharing Revisited 151
3.6.5 Replication Revisited 152
3.6.6 Digest 153
3.7 Equivalence Transforms for Recursive Computations 154
3.7.1 The Feedback Bottleneck 154
3.7.2 Unfolding of First-Order Loops 155
Performance and cost analysis 157
3.7.3 Higher-Order Loops 158
Performance and cost analysis 160
3.7.4 Time-Variant Loops 160
Performance and cost analysis 161
3.7.5 Nonlinear or General Loops 161
3.7.6 Pipeline Interleaving, not Quite an Equivalence Transform 165
3.7.7 Digest 167
3.8 Generalizations of the Transform Approach 169
3.8.1 Generalization to other Levels of Detail 169
Architecture level 169
Bit level 170
3.8.2 Bit-Serial Architectures 171
3.8.3 Distributed Arithmetic 173
3.8.4 Generalization to other Algebraic Structures 176
Finite fields 176
Semirings 176
3.8.5 Digest 181
3.9 Conclusions 181
3.9.1 Summary 181
3.9.2 The Grand Architectural Alternativesfrom an Energy Point of View 184
3.9.3 A Guide to Evaluating Architectural Alternatives 186
3.10 Problems 189
3.11 Appendix I: A Brief Glossary of Algebraic Structures 191
Examples with one operation 192
Examples with two operations 192
3.12 Appendix II: Area and Delay Figures of VLSI Subfunctions 195
Chapter 4: Circuit Modeling with Hardware Description Languages 200
4.1 Motivation and Background 200
4.1.1 Why Hardware Synthesis? 200
4.1.2 Agenda 200
4.1.3 Alternatives for Modeling Digital Hardware 201
4.1.4 The Genesis of VHDL and SystemVerilog 201
4.1.5 Why Bother Learning Hardware Description Languages? 203
4.1.6 A First Look at VHDL and SystemVerilog 205
4.2 Key Concepts and Constructs of VHDL 207
4.2.1 Circuit Hierarchy and Connectivity 207
How to compose a circuit from components 210
4.2.2 Interacting Concurrent Processes 211
How to describe combinational logic behaviorally 212
How to describe a register behaviorally 214
4.2.3 A Discrete Replacement for Electrical Signals 219
The need for multiple logic values to describe a circuit node 219
Some logic values get collapsed during synthesis 221
How to model three-state outputs and busses 222
Selecting adequate data types 223
Data types for modeling multi-bit signals 224
Orientation of binary vectors 225
Data types for modeling fractional and floating point numbers 225
4.2.4 An Event-Driven Scheme of Execution 227
The need for a mechanism that schedules process execution 227
Simulation time versus execution time 228
The benefits of a discretized model of time 228
Transaction versus event 229
Delay modeling 230
The d delay 230
Signal versus variable 231
Event-driven simulation revisited 232
Sensitivity list 232
Wait statement30 233
What exactly is it that makes a process statement exhibit sequential behavior? 234
How to safely code sequential circuits for synthesis 235
Initial values cannot replace a reset mechanism 236
Detecting clock edges and other signal events 236
Signal attributes 237
How to check timing conditions 237
Concurrent assertion statements 237
4.2.5 Facilities for Model Parametrization 239
The need for supporting parametrized circuit models 239
Generics 240
The generate statement used to conditionally spawn concurrent processes 241
The generate statement used to conditionally instantiate components 242
The need to accommodate multiple models for one circuit block 244
Configuration specification and binding 244
Elaboration 245
4.2.6 Concepts Borrowed from Programming Languages 247
Structured flow control statements 247
Object 247
Constant 247
Variable 247
User-defined data types 247
Subtypes 248
Arrays and records 248
Type attributes and array attributes 248
Subprogram, function, and procedure 249
Package 249
Predefined package standard 251
Predefined package textio 251
Design unit and design file 252
Design library 252
Library and use clauses 253
Special libraries work and std 254
4.3 Key Concepts and Constructs of SystemVerilog 255
4.3.1 Circuit Hierarchy and Connectivity 255
The need for supporting modularity and hierarchical composition 255
Module, structural view 255
How to compose a circuit from components 256
Special constructs for modeling busses 257
4.3.2 Interacting Concurrent Processes 258
The need for modeling concurrent activities 258
How to describe combinational logic behaviorally 258
How to describe a register behaviorally 259
Local versus shared variables 260
Module, behavioral view 261
Hardware modeling styles compared 262
4.3.3 A Discrete Replacement for Electrical Signals 264
The need for multiple logic values to describe a circuit node 264
How to model three-state outputs and busses 266
Selecting adequate data types 267
Data types for modeling multi-bit signals 268
Orientation of binary vectors 269
4.3.4 An Event-Driven Scheme of Execution 270
The need for a mechanism that schedules process execution 270
Event-driven simulation 270
Sensitivity list, process suspension and reactivation 271
Delay modeling 271
Blocking versus nonblocking assignments 272
Always blocks 272
No binding order of execution for simultaneous events 273
Initial values cannot replace a reset mechanism 274
How to check timing conditions 274
4.3.5 Facilities for Model Parametrization 275
Parameters 275
The generate statement 276
The need to accommodate multiple models for one circuit block 277
Conditional compilation of source code 277
4.3.6 Concepts Borrowed from Programming Languages 278
User-defined data types 278
Subroutine, function, and task 278
Package 279
Classes, semaphores, mailboxes, etc 280
System tasks 281
4.4 Automatic Circuit Synthesis From HDL Models 283
4.4.1 Synthesis Overview 283
4.4.2 Data Types 284
4.4.3 Finite State Machines and Sequential Subcircuits in General 284
Hardware-compatible wake-up conditions for all processes 284
Explicit versus implicit state models 285
How to capture a finite state machine 286
Packing an entire FSM into a single process statement 286
Distributing an FSM over two (or more) concurrent processes 287
FSM optimization ignored in the language standards 293
4.4.4 RAM and ROM Macrocells 293
4.4.5 Timing Constraints 296
How to partition a circuit in view of synthesis and optimization 300
Synthesis constraints are not part of the HDL standards 297
How to formulate timing constraints 298
How to partition a circuit in view of synthesis and optimization 300
4.4.6 Limitations and Caveats 302
Some circuits essentially need to be defined as gate-level netlists 302
4.4.7 How to Establish a Register Transfer Level Model Step by Step 303
4.5 Conclusions 305
4.6 Problems 307
4.7 Appendix I: VHDL and SystemVerilog Side by Side 310
4.8 Appendix II: VHDL Extensions and Standards 314
4.8.1 Protected Shared Variables IEEE 1076a 314
4.8.2 The Analog and Mixed-Signal Extension IEEE 1076.1 315
4.8.3 Mathematical Packages for Real and Complex Numbers IEEE 1076.2 317
4.8.4 The Arithmetic Packages IEEE 1076.3 317
4.8.5 The Standard Delay Format (SDF) IEEE 1497 318
4.8.6 A Handy Compilation of Type Conversion Functions 319
4.8.7 Coding Guidelines 321
Chapter 5: Functional Verification 322
5.1 Goals of Design Verification 322
5.1.1 Agenda 323
5.2 How to Establish Valid Functional Specifications 324
5.2.1 Formal Specification 325
5.2.2 Rapid Prototyping 325
5.2.3 Hardware-Assisted Verification 327
5.3 Preparing Effective Simulation and Test Vectors 328
5.3.1 A First Glimpse at VLSI Testing 328
5.3.2 Fully Automated Response Checking is a Must 329
5.3.3 Assertion-Based Verification Checks from Within 331
5.3.4 Exhaustive Verification Remains an Elusive Goal 336
5.3.5 Directed Verification is Indispensable but has its Limitations 337
Testing distinct functional mechanisms separately 337
Monitoring toggle counts is of limited use 340
Automatic test pattern generation does not help either 340
Monitoring code coverage helps but does not suffice 340
Routine is the dark side of experience 342
Even real-world data sometimes prove too forgiving 342
5.3.6 Directed Random Verification Guards Against Human Omissions 343
5.3.7 Statistical Coverage Analysis Produces Meaningful Metrics 348
5.3.8 Collecting Test Cases from Multiple Sources Helps 349
5.3.9 Separating Test Development from Circuit Design Helps 350
5.4 Consistency and Efficiency Considerations 352
5.4.1 A Coherent Schedule for Simulation and Test 353
5.4.2 Protocol Adapters Help Reconcile Different Views on Data and Latency 356
5.4.3 Calculating High-Level Figures of Merit 359
5.4.4 Patterning Simulation Set-Ups after the Target System 360
5.4.5 Initialization 361
5.4.6 Trimming Run Times by Skipping Redundant Simulation Sequences 361
5.5 Testbench Coding and HDL Simulation 362
5.5.1 Modularity and Reuse are the Keys to Testbench Design 362
5.5.2 Anatomy of a File-Based Testbench 363
All disk files stored in ASCII format 364
Separate processes for stimulus application and for response acquisition 364
Stimuli and responses collected in records 364
Simulation to proceed even after expected responses have been exhausted 365
Stoppable clock generator 365
Reset treated as an ordinary stimulus bit 365
5.6 Conclusions 367
5.7 Problems 368
5.8 Appendix I: Formal Approaches to Functional Verification 371
Equivalence checking 371
Model checking 371
Deductive verification or model proving 372
5.9 Appendix II: Deriving a Coherent Schedule 373
External timing requirements imposed by a model under test (MUT) 373
Precedence relations captured in a constraint graph 374
Solving the constraint graph 375
Anceau diagrams help visualize periodic events and timing 375
Chapter 6: The Case for Synchronous Design 378
6.1 Introduction 378
6.2 The Grand Alternatives for Regulating State Changes 380
6.2.1 Synchronous Clocking 381
6.2.2 Asynchronous Clocking 381
6.2.3 Self-Timed Clocking 382
6.3 Why a Rigorous Approach to Clocking is Essential in VLSI 385
6.3.1 The Perils of Hazards 385
6.3.2 The Pros and Cons of Synchronous Clocking 386
6.3.3 Clock-as-Clock-Can is not an Option in VLSI 388
6.3.4 Fully Self-Timed Clocking is not Normally an Option Either 389
6.3.5 Hybrid Approaches to System Clocking 389
6.4 The Dos and Donts of Synchronous Circuit Design 391
6.4.1 First Guiding Principle: Dissociate Signal Classes! 391
6.4.2 Second Guiding Principle: Allow for Circuits to Settle Before Clocking! 392
6.4.3 Synchronous Design Rules at a More Detailed Level 393
Unclocked bistables prohibited 393
Zero-latency loops prohibited 394
Monoflops, one-shots, edge detectors and clock chopping prohibited 395
Clock and reset signals to be distributed by fanout trees 396
Beware of unsafe clock gates 396
No gating of reset signals 396
Bistables with both asynchronous reset and preset inputs prohibited 398
Reset signals to be properly conditioned 398
Pay attention to portable design 400
6.5 Conclusions 401
6.6 Problems 402
6.7 Appendix: On Identifying Signals 403
6.7.1 Signal Class 403
Colors in schematic diagrams and HDL source code 403
Clock symbols and clock domains in schematic diagrams 404
6.7.2 Active Level 405
Naming of complementary signals 405
Inversion symbols in schematic diagrams 405
6.7.3 Signaling Waveforms 406
6.7.4 Three-State Capability 407
6.7.5 Inputs, Outputs and Bidirectional Ports 407
6.7.6 Present State vs. Next State 408
6.7.7 Signal Naming Convention Syntax 408
6.7.8 Usage of Upper and Lower Case Letters in HDL Source Code 409
6.7.9 A Note on the Portability of Names Across EDA Platforms 410
Chapter 7: Clocking of Synchronous Circuits 412
7.1 What is the Difficulty With Clock Distribution? 412
7.1.1 Agenda 413
7.1.2 Timing Quantities Related to Clock Distribution 414
7.2 How Much Skew and Jitter Does a Circuit Tolerate? 415
7.2.1 Basics 415
7.2.2 Single-Edge-Triggered One-Phase Clocking 417
Hardware resources and operation principle 417
Detailed analysis 418
Setup condition 418
Hold condition 420
Implications 420
7.2.3 Dual-Edge-Triggered One-Phase Clocking 423
Hardware resources and operation principle 423
Implications 424
Scan-type testing requires the presence of shift registers 421
Watch out when mixing cells from different libraries 422
Hold time fixing 423
7.2.4 Symmetric Level-Sensitive Two-Phase Clocking 425
Hardware resources and operation principle 425
Detailed analysis 426
Setup condition 426
Hold condition 427
Implications 427
7.2.5 Unsymmetric Level-Sensitive Two-Phase Clocking 428
Hardware resources and operation principle 428
Detailed analysis 429
Setup condition 429
Hold condition 429
Implications 430
7.2.6 Single-Wire Level-Sensitive Two-Phase Clocking 432
Hardware resources and operation principle 432
Detailed analysis 432
Setup condition 435
Hold condition 435
Implications 433
7.2.7 Level-Sensitive One-Phase Clocking and Wave Pipelining 433
Hardware resources and operation principle 433
Detailed analysis 435
Implications 435
7.3 How to Keep Clock Skew Within Tight Bounds 437
7.3.1 Clock Waveforms 437
7.3.2 Collective Clock Buffers 438
7.3.3 Distributed Clock Buffer Trees 440
7.3.4 Hybrid Clock Distribution Networks 442
7.3.5 Clock Skew Analysis 442
7.4 How to Achieve Friendly Input/Output Timing 444
7.4.1 Friendly as Opposed to Unfriendly I/O Timing 444
7.4.2 Impact of Clock Distribution Delay on I/O Timing 445
7.4.3 Impact of PTV Variations on I/O Timing 447
7.4.4 Registered Inputs and Outputs 448
7.4.5 Adding Artificial Contamination Delay to Data Inputs 448
7.4.6 Driving Input Registers From an Early Clock 449
7.4.7 Clock Tapped From Slowest Component in Clock Domain 449
7.4.8 "Zero-Delay'' Clock Distribution by Way of a DLL or PLL 450
7.5 How to Implement Clock Gating Properly 453
7.5.1 Traditional Feedback-Type Registers with Enable 453
7.5.2 A Crude and Unsafe Approach to Clock Gating 454
7.5.3 A Simple Clock Gating Scheme that May Work Under Certain Conditions 455
7.5.4 Safe Clock Gating Schemes 455
7.6 Summary 459
7.7 Problems 462
Chapter 8: Acquisition of Asynchronous Data 466
8.1 Motivation 466
8.2 Data Consistency in Vectored Acquisition 468
8.2.1 Plain Bit-Parallel Synchronization 468
8.2.2 Unit-Distance Coding 469
8.2.3 Suppression of Jumbled Data Patterns 470
8.2.4 Handshaking 471
NRZ or two-phase handshake protocol 472
RZ or four-phase handshake protocol 473
8.2.5 Partial Handshaking 474
8.2.6 FIFO Synchronizers 475
8.3 Data Consistency in Scalar Acquisition 478
8.3.1 No Synchronization Whatsoever 478
8.3.2 Synchronization at Multiple Places 478
8.3.3 Synchronization at a Single Place 479
8.3.4 Synchronization From a Slow Clock 479
8.4 Marginal Triggering and Metastability 481
8.4.1 Metastability and How it Becomes Manifest 481
8.4.2 Repercussions on Circuit Functioning 484
8.4.3 A statistical Model for Estimating Synchronizer Reliability 485
8.4.4 Plesiochronous Interfaces 487
8.4.5 Containment of Metastable Behavior 487
Estimate reliability at the system level 488
Select flip-flops with good metastability resolution 488
Remove combinational delays from synchronizers 489
Drive synchronizers with fast-switching clock 489
Free synchronizers from unnecessary loads 489
Lower clock frequency at the consumer end 489
Use multi-stage synchronizers 490
Keep feedback path within synchronizers short 490
8.5 Summary 491
8.6 Problems 492
Appendix A: Elementary Digital Electronics 494
A.1 Introduction 494
A.1.1 Common Number Representation Schemes 494
A.1.2 Floating Point Number Formats 496
A.1.3 Notational Conventions for Two-Valued Logic 498
A.2 Theoretical Background of Combinational Logic 499
A.2.1 Truth Table 499
A.2.2 The n-Cube 500
A.2.3 Karnaugh Map 500
A.2.4 Program Code 500
A.2.5 Logic Equations 501
A.2.6 Two-Level Logic 503
Sum-of-products 503
Product-of-sums 503
Other two-level logic forms 503
A.2.7 Multi-Level Logic 504
A.2.8 Symmetric and Monotone Functions 505
A.2.9 Threshold Functions 506
A.2.10 Complete Gate Sets 506
A.2.11 Multi-Output Functions 507
A.2.12 Logic Minimization 508
Metrics for logic complexity and implementation costs 508
Minimal versus unredundant expressions 509
Multi-level versus two-level logic 510
Multi-output versus single-output minimization 510
Manual versus automated logic optimization 511
A.3 Circuit Alternatives for Implementing Combinational Logic 512
A.3.1 Random Logic 512
A.3.2 Programmable Logic Array (PLA) 512
A.3.3 Read-Only Memory (ROM) 514
A.3.4 Array Multiplier 514
A.3.5 Digest 515
A.4 Bistables and Other Memory Circuits 517
A.4.1 Flip-Flops or Edge-Triggered Bistables 518
The data or D-type flip-flop 518
Initialization facilities 518
Scan facility 519
Enable/disable facility 520
The toggle or T-type flip-flop 520
The nostalgia or JK-type flip-flop 521
A.4.2 Latches or Level-Sensitive Bistables 521
The data or D-type latch 521
A.4.3 Unclocked Bistables 522
The SR-seesaw 522
The edge-triggered SR-seesaw 523
The Muller-C element 524
The mutual exclusion element 525
A.4.4 Random Access Memories (RAM) 527
A.5 Transient Behavior of Logic Circuits 529
A.5.1 Glitches, a Phenomenological Perspective 529
A.5.2 Function Hazards, a Circuit-Independent Mechanism 530
A.5.3 Logic Hazards, a Circuit-Dependent Mechanism 531
A.5.4 Digest 533
A.6 Timing Quantities 534
A.6.1 Delay Parameters Serve for Combinational and Sequential Circuits 534
A.6.2 Timing Conditions Get Imposed by Sequential Circuits Only 536
A.6.3 Secondary Timing Quantities are Derived From Primary Ones 538
A.6.4 Timing Constraints Address Synthesis Needs 539
A.7 Basic Microprocessor Input/Output Transfer Protocols 540
A.8 Summary 542
Appendix B: Finite State Machines 544
B.1 Abstract Automata 544
B.1.1 Mealy Machine 545
B.1.2 Moore Machine 546
B.1.3 Medvedev Machine 547
B.1.4 Relationships Between Finite State Machine Models 548
Equivalence of Mealy and Moore machines in the context of automata theory 548
Equivalence of Mealy and Moore machines in the context of hardware design 550
Equivalence of Moore and Medvedev machines 550
B.1.5 Taxonomy of Finite State Machines 552
B.1.6 State Reduction 553
B.2 Practical Aspects and Implementation Issues 555
B.2.1 Parasitic States and Symbols 555
B.2.2 Mealy-, Moore-, Medvedev-Type, and Combinational Output Bits 557
B.2.3 Through Paths and Logic Instability 558
B.2.4 Switching Hazards 559
B.2.5 Hardware Costs 560
Concurrency, hierarchy and modularity are key to efficiency 560
State reduction 561
State encoding 562
B.3 Summary 563
Appendix C: Symbols and Constants 564
C.1 Abbreviations 564
C.2 Mathematical Symbols 565
C.3 Physical and Material Constants 569
A note on carbon allotropes 569
Bibliography 574
Index 586