Register your product to gain access to bonus material or receive a coupon.
Hardware Design Verification: Simulation and Formal Method-Based Approaches
- By William K. Lam
- Published Mar 3, 2005 by Pearson.
Book
- Sorry, this book is no longer in print.
About
Features
Broad coverage of digital design verification delivered in an organized and systematic fashion.
° Covers the technology the industry uses for design verification, namely simulation based verification.
° Introduces formal verification, an emerging technology that is beginning to get into practice.
° Written by a senior engineering manager at Sun Microsystems Laboratories and winner of 2002 Sun Microsystem's Chairman's Award for Innovation (highest award for technical achievement).
Description
- Copyright 2005
- Edition: 1st
- Book
- ISBN-10: 0-13-143347-4
- ISBN-13: 978-0-13-143347-2
The Practical, Start-to-Finish Guide to Modern Digital Design Verification
As digital logic designs grow larger and more complex, functional verification has become the number one bottleneck in the design process. Reducing verification time is crucial to project success, yet many practicing engineers have had little formal training in verification, and little exposure to the newest solutions. Hardware Design Verification systematically presents today's most valuable simulation-based and formal verification techniques, helping test and design engineers choose the best approach for each project, quickly gain confidence in their designs, and move into fabrication far more rapidly. College students will find that coverage of verification principles and common industry practices will help them prepare for jobs as future verification engineers.
Author William K. Lam, one of the world's leading experts in design verification, is a recent winner of the Chairman's Award for Innovation, Sun Microsystems' most prestigious technical achievement award. Drawing on his wide-ranging experience, he introduces the foundational principles of verification, presents traditional techniques that have survived the test of time, and introduces emerging techniques for today's most challenging designs. Throughout, Lam emphasizes practical examples rather than mathematical proofs; wherever advanced math is essential, he explains it clearly and accessibly.
Coverage includes
- Simulation-based versus formal verification: advantages, disadvantages, and tradeoffs
- Coding for verification: functional and timing correctness, syntactical and structure checks, simulation performance, and more
- Simulator architectures and operations, including event-driven, cycle-based, hybrid, and hardware-based simulators
- Testbench organization, design, and tools: creating a fast, efficient test environment
- Test scenarios and assertion: planning, test cases, test generators, commercial and Verilog assertions, and more
- Ensuring complete coverage, including code, parameters, functions, items, and cross-coverage
- The verification cycle: failure capture, scope reduction, bug tracking, simulation data dumping, isolation of underlying causes, revision control, regression, release mechanisms, and tape-out criteria
- An accessible introduction to the mathematics and algorithms of formal verification, from Boolean functions to state-machine equivalence and graph algorithms
- Decision diagrams, equivalence checking, and symbolic simulation
- Model checking and symbolic computation
Simply put, Hardware Design Verification will help you improve and accelerate your entire verification process--from planning through tape-out--so you can get to market faster with higher quality designs.
Sample Content
Online Sample Chapter
Does Your Design Meet Its Specs? Introduction to Hardware Design Verification
Downloadable Sample Chapter
Table of Contents
Preface xvii
Acknowledgments xxiii
About the Author xxv
Chapter 1 An Invitation to Design Verification 1
1.1 What Is Design Verification? 2
1.2 The Basic Verification Principle 4
1.3 Verification Methodology 8
1.4 Simulation-Based Verification versus Formal Verification 15
1.5 Limitations of Formal Verification 17
1.6 A Quick Overview of Verilog Scheduling and Execution Semantics 17
1.7 Summary 23
Chapter 2 Coding for Verification 25
2.1 Functional Correctness 27
2.2 Timing Correctness 39
2.3 Simulation Performance 44
2.4 Portability and Maintainability 52
2.5 "Synthesizability," "Debugability," and General Tool Compatibility 56
2.6 Cycle-Based Simulation 59
2.7 Hardware Simulation/Emulation 62
2.8 Two-State and Four-State Simulation 64
2.9 Design and Use of a Linter 66
2.10 Summary 67
2.11 Problems 67
Chapter 3 Simulator Architectures and Operations 73
3.1 The Compilers 74
3.2 The Simulators 79
3.3 Simulator Taxonomy and Comparison 108
3.4 Simulator Operations and Applications 112
3.5 Incremental Compilation 126
3.6 Summary 129
3.7 Problems 130
Chapter 4 Test Bench Organization and Design 137
4.1 Anatomy of a Test Bench and a Test Environment 137
4.2 Initialization Mechanism 142
4.3 Clock Generation and Synchronization 148
4.4 Stimulus Generation 155
4.5 Response Assessment 162
4.6 Verification Utility 183
4.7 Test Bench-to-Design Interface 195
4.8 Common Practical Techniques and Methodologies 196
4.9 Summary 204
4.10 Problems 204
Chapter 5 Test Scenarios, Assertions, and Coverage 211
5.1 Hierarchical Verification 214
5.2 Test Plan 217
5.3 Pseudorandom Test Generator 227
5.4 Assertions 232
5.5 SystemVerilog Assertions 248
5.6 Verification Coverage 259
5.7 Summary 279
5.8 Problems 280
Chapter 6 Debugging Process and Verification Cycle 287
6.1 Failure Capture, Scope Reduction, and Bug Tracking 288
6.2 Simulation Data Dumping 297
6.3 Isolation of Underlying Causes 300
6.4 Design Update and Maintenance: Revision Control 315
6.5 Regression, Release Mechanism, and Tape-out Criteria 318
6.6 Summary 321
6.7 Problems 322
Chapter 7 Formal Verification Preliminaries 331
7.1 Sets and Operations 332
7.2 Relation, Partition, Partially Ordered Set, and Lattice 334
7.3 Boolean Functions and Representations 342
7.4 Boolean Functional Operators 353
7.5 Finite-State Automata and Languages 359
7.6 Summary 380
7.7 Problems 381
Chapter 8 Decision Diagrams, Equivalence Checking, and Symbolic Simulation 387
8.1 Binary Decision Diagrams 388
8.2 Decision Diagram Variants 412
8.3 Decision Diagram-Based Equivalence Checking 424
8.4 Boolean Satisfiability 430
8.5 Symbolic Simulation 442
8.6 Summary 457
8.7 Problems 458
Chapter 9 Model Checking and Symbolic Computation 465
9.1 Properties, Specifications, and Logic 466
9.2 Property Checking 484
9.3 Symbolic Computation and Model Checking 494
9.4 Symbolic CTL Model Checking 513
9.5 Computational Improvements 524
9.6 Using Model-Checking Tools 529
9.7 Summary 531
9.8 Problems 531
Bibliography 539
Index 561
Preface
Two groups of people are essential to a successful design project: a design team and a verification team. Designers usually have formal training from schools. Many colleges have comprehensive curricula on logic design, ranging from introduction to digital design to advanced computer architecture. On the contrary, most verification engineers learn their trade on the job; few were educated as verification engineers in academia, although many schools are beginning to teach verification curriculum. In fact, a majority of verification engineers started out as designers and gradually transitioned to design verification. Unlike design techniques and methodologies, a broad range of verification knowledge is loosely organized and informally acquired through hands-on experience. Furthermore, the horizon of verification has been expanding at a rapid pace: The verification landscape is evolving every six months with new techniques, standards, and tools. Nevertheless, there are principles and techniques that have survived the test of time and prove to be cornerstones of verification.
This book collects and organizes a wide range of digital design verification techniques and methodologies commonly used in industry and presents them in a systematic fashion. The focus of the book is on digital logic design and verification. It does not cover verification of circuits with mixed-signal or radio frequency components. A goal of the book is to pass the vast amount of verification knowledge to college students and engineers so that they are better prepared for the workforce, and to speed up their learning pace. It is tempting to write a ten-minute verification engineering book that lists detailed practical tips that can be used immediately on the job. These quick-fix tips often become obsolete over a short period of time. On the other hand, presenting the principles only will not be immensely useful for practicing engineers. Thus, I decided to strike a balance between the two and present verification principles as well as common practices. It is my belief that only by understanding the principles can one truly grasp the essence of the practices and be creative about using them.
To the Audience
One targeted audience for this book includes undergraduate students at the junior or senior level or first-level graduate students. I will assume that these readers have a sound understanding of a hardware descriptive language, preferably Verilog, because Verilog is used for illustration purposes in most parts of the book. In addition, a rudimentary knowledge of logic design is beneficial. This book is an introduction to design verification. Through its study, students will learn the main ideas, tools, and methodologies used in simulation-based verification, and the principles behind formal verification. The materials presented are industry tested and widely used. At the end of each chapter, problems are presented as a means of refreshing the knowledge covered in the chapter. For those who want to explore certain topics in more depth, please refer to the citations listed in the bibliography.
The other targeted audience includes verification professionals who may have some verification experience but would like to get a systematic overview of the different areas in verification and an understanding of the basic principles behind formal verification. The prerequisites for this audience are similar to those for the first group: basic design knowledge and a hardware descriptive language. The first part of the book provides a comprehensive treatment of simulation-based verification methodology and serves as a refresher or an introduction to verification professionals. For many practicing engineers, formal verification tools appear to be a form of black magic that requires a doctorate in mathematics to comprehend. This book explains these tools and the working principles of formal verification. Before formal verification is discussed in depth, Chapter 7 reviews the basics of mathematics and computer algorithms required to understand verification algorithms fully.
As with every technology, there is no substitution for hands-on experience. I encourage you to get acquainted with verification tools by running some of the examples and problems in the book or designing a project that makes use of the tools described. Free CAD tools such as Verilog simulator, test bench development aid, and waveform viewer are available at www.verilog.net/free.html.
To the Instructor
This book is comprised of two parts. The first part addresses the conventional verification strategy-simulation-based verification-whereas the second part addresses the aspects of formal verification that are well established in academia and tested in industry. The two parts are self-contained and thus can be taught independently as deemed fit.
The first part describes many verification tools. Because the specifics of these tools differ from vendor to vendor and change from time to time, only pseudo common commands are used in this book. To reinforce learning these tools, I recommend that industrial tools be part of a verification laboratory (for instance, a simulator, a waveform viewer, a coverage tool, a bug tracking system, and a revision control system). Similarly, to solidify the knowledge of formal verification, commercial formal verification tools such as an HDL linter, a model checker, and an equivalence checker should be used during lab sessions.
This book has a companion instructor's manual that contains the solutions to all the problems at the end of each chapter. The instructor's manual is available on request to the publisher.
Organization of the Book
Again, this book is intended as an introduction to design verification. I will assume that you have an understanding of basic Verilog constructs. Even though the book is written using Verilog as the hardware description language, I made an effort to present ideas independent of Verilog. When the use of Verilog is unavoidable, the simplest Verilog constructs are used to allow readers unfamiliar with the language to grasp the main ideas.
As previously stated, this book consists of two parts. The first part is devoted to simulation-based verification and the second part discusses formal verification. Simulation-based verification is by far the most widely used methodology and is a necessary requirement for all verification engineers. Formal verification is a relatively new technology and it complements simulation-based verification. I believe that to utilize a technology best, one must first be equipped with an in-depth understanding of the internal working principles of that technology. As a result, instead of just studying a verification tool's operations at the user level-a topic better suited for user manuals-this book spends much time studying the fundamental principles of simulation and formal technology.
The first part--simulation technology--consists of Chapters 2 through 6, and these chapters are ordered similar to the usual sequence of operations encountered during a simulation verification process. We start with Chapter 2, checking for static errors. These are errors that can be detected without input vectors and must be eliminated before extensive simulation begins. In Chapter 3, we study the basic architectures of simulators. Event-driven and cycle-based simulation algorithms are presented first, followed by simulator operations and applications for which we discuss cosimulation, design profiling, common simulator options, and the user interface.
Before one can begin a simulation, one must construct a test bench to host the design. Chapter 4 discusses test bench design, initialization, stimuli generation, clock network, error injection, result assessment, and test configuration. After a design is free of static errors and is embedded in a test bench, it is ready to be simulated. But how should the design be simulated? Chapter 5 addresses the issues of what to simulate and how to measure the quality of the simulation. We will look at test plan design, generation of tests for the items in the test plan, output response assessment, assertion (particularly, SystemVerilog assertions), and verification coverage.
After a circuit is simulated and the bugs are discovered, the next step is to debug problems found during simulation. Chapter 6 presents widely used debugging techniques, including case reduction, check pointing, error tracing, trace dumping, and forward and backward debugging. In addition, Chapter 6 examines the four basic views of design: source code, schematic, waveform, and finite-state machine. We then examine the scenario after the bugs are fixed. The tools and methodology discussed include the revision control system, regression mechanism, and tape-out criteria.
The second part of the book--formal verification--consists of Chapters 7 through 9. Several chapters in the first part of the book can be studied in conjunction with the second. For example, Chapters 2, 4, 5, and 6 are also applicable to formal verification.
The key to understanding formal verification lies in an understanding of the theory behind it. Chapter 7 provides the basic mathematical background for the later chapters. The materials cover Boolean functions and representations, symmetric Boolean functions, finite-state machines and the equivalence algorithm, and graphic algorithms such as depth-first search and breadth-first search, and strongly connected components.
Chapter 8 presents a survey of decision diagrams, with an emphasis on binary decision diagrams. We then review SAT (satisfiability) as an alternative to decision diagrams. The chapter concludes with a look at applications of decision diagrams and SAT in equivalence checking and symbolic simulation.
Chapter 9 presents an in-depth study of symbolic model checking. First it presents automata and computational tree logic as a means of modeling temporal behavior with fairness constraints. It then discusses algorithms for checking a model against a temporal specification. Based on the model-checking algorithms, efficient symbolic model-checking algorithms are presented in which graphical operations are accomplished through Boolean function computations. Next, equivalence checking is revisited for general circuits for which one-to-one state correspondence does not exist. To conclude, algorithms for better managing symbolic computation are studied.
Index