Verification by error modeling : using testing techniques in hardware verification

1. DESIGN FLOW Integrated circuit (IC) complexity is steadily increasing. ICs incorporating hundreds of millions of transistors, mega-bit memories, complicated pipelined structures, etc., are now in high demand. For example, Intel Itanium II processor contains more than 200 million transistors, including a 3 MB third level cache. A billion transistor IC was said to be "imminently doable" by Intel fellow J. Crawford at Microprocessor Forum in October 2002 [40]. Obviously, designing such complex circuits poses real challenges to engineers. Certainly, no relief comes from the competitive marketplace, with increasing demands for a very narrow window of time (time-to-market) in engineering a ready product. Therefore, a systematic and well-structured approach to designing ICs is a must. Although there are no widely adhered standards for a design flow, most companies have their own established practices, which they follow closely for in-house design processes. In general, however, a typical product cycle includes few milestones. An idea for a new product starts usually from an - depth market analysis of customer needs. Once a window of opportunity is found, product requirements are carefully specified. Ideally, these parameters would not change during the design process. In practice, initial phases of preparing a design specification are susceptible to potential errors, as it is very difficult to grasp all the details in a complex design.

List of Figures	p. xi
Acknowledgments	p. xv
Chapter 1 Introduction	p. 1
1. Design Flow	p. 1
2. Verification--Approaches and Problems	p. 4
2.1 Verification Approaches	p. 5
2.2 Verification by Simulations	p. 5
2.3 Test Vector Generation	p. 5
2.4 Design Error Models	p. 7
2.5 Other Simulation Methods	p. 9
2.5.1 Coverage Verification	p. 9
2.5.2 Other Metrics	p. 10
2.6 Formal Verification	p. 11
2.7 Model-based Formal Verification Methods	p. 12
2.8 Proof-theoretical Formal Verification Methods	p. 14
2.9 Spectral Methods in Verification	p. 14
3. Book Objectives	p. 15
Chapter 2 Boolean Function Representations	p. 19
1. Background--Function Representations	p. 19
1.1 Truth Tables	p. 20
1.2 Boolean Equations--Sum of Products	p. 21
1.3 Satisfiability of Boolean Functions	p. 23
1.3.1 Algorithms for Solving Satisfiability	p. 24
1.4 Shannon Expansion	p. 28
1.5 Polynomial Representation	p. 28
2. Decision Diagrams	p. 30
2.1 Reduced Ordered Binary Decision Diagrams	p. 31
2.2 Word-Level Decision Diagrams	p. 33
2.2.1 Binary Moment Diagrams	p. 33
2.2.2 Limitations of WLDDs	p. 35
3. Spectral Representations	p. 38
3.1 Walsh-Hadamard Transform	p. 39
3.2 Walsh Transform Variations	p. 40
3.3 Walsh-Hadamard Transform as Fourier Transform	p. 41
4. Arithmetic Transform	p. 44
4.1 Calculation of Arithmetic Transform	p. 47
4.1.1 Fast Arithmetic Transform	p. 47
4.1.2 Boolean Lattice and AT Calculation	p. 48
4.2 AT and Word-Level Decision Diagrams	p. 49
Chapter 3 Don't Cares and Their Calculation	p. 51
1. Incompletely Specified Boolean Functions	p. 51
1.1 Don't Cares in Logic Synthesis	p. 51
1.2 Don't Cares in Testing for Manufacturing Faults	p. 52
1.3 Don't Cares in Circuit Verification	p. 54
2. Using Don't Cares for Redundancy Identification	p. 55
2.1 Basic Definitions	p. 56
2.2 Calculation of All Don't Care Conditions	p. 57
2.2.1 Computation of Controllability Don't Cares	p. 57
2.2.2 Algorithms for Determining CDCs	p. 59
2.3 Algorithms for Computing ODCs	p. 65
2.4 Approximations to Observability Don't Cares--CODCs	p. 67
Chapter 4 Testing	p. 71
1. Introduction	p. 71
2. Fault List Reduction	p. 73
3. Overview of Simulators	p. 73
3.1 True-Value Simulator Types	p. 74
3.2 Logic Simulators	p. 75
4. Fault Simulators	p. 79
4.1 Random Simulations	p. 81
4.1.1 Linear Feedback Shift Registers	p. 82
4.1.2 Other Pseudo-Random Test Pattern Generators	p. 88
4.1.3 Final remarks	p. 93
5. Deterministic Vector Generation--ATPG	p. 94
5.1 Deterministic Phase	p. 94
5.2 Search for Vectors	p. 98
5.3 Fault Diagnosis	p. 100
6. Conclusions	p. 101
Chapter 5 Design Error Models	p. 103
1. Introduction	p. 103
2. Design Errors	p. 105
3. Explicit Design Error Models	p. 107
3.1 Detecting Explicit Errors	p. 110
3.1.1 Application of Stuck-at-value Vector Set	p. 110
3.1.2 Detection of Gate Replacements	p. 110
3.1.3 Universal Test Set Approach	p. 111
4. Implicit Error Model Precursors	p. 112
4.1 Rationale for Implicit Models	p. 113
4.2 Related Work--Error Models	p. 114
4.2.1 Port Fault Models	p. 114
5. Additive Implicit Error Model	p. 115
5.1 Arithmetic Transform of Basic Design Errors	p. 117
6. Design Error Detection and Correction	p. 123
6.1 Path Trace Procedure	p. 125
6.2 Back-propagation	p. 126
6.3 Boolean Difference Approximation by Simulations	p. 127
7. Conclusions	p. 128
Chapter 6 Design Verification by AT	p. 129
1. Introduction	p. 129
2. Detecting Small AT Errors	p. 132
2.1 Universal Test Set	p. 132
2.2 AT-based Universal Diagnosis Set	p. 133
3. Bounding Error by Walsh Transform	p. 135
3.1 Spectrum Comparison	p. 137
3.2 Spectrum Distribution and Partial Spectra Comparison	p. 138
3.3 Absolute Value Comparison	p. 140
4. Experimental Results	p. 142
4.1.1 Improvements--Neighborhood Subspace Points	p. 145
5. Conclusions	p. 146
Chapter 7 Identifying redundant gate and wire replacements	p. 147
1. Introduction	p. 147
2. Gate Replacement Faults	p. 149
2.1 Redundant Replacement Faults	p. 150
2.1.1 Overview of the Proposed Approach	p. 151
3. Redundancy Detection by Don't Cares	p. 151
3.1 Using Local Don't Cares	p. 152
3.2 Using Testing--Single Minterm Approximation	p. 154
3.3 Redundant Single Cube Replacements	p. 159
3.3.1 Use of SAT in Redundancy Identification	p. 160
3.3.2 Passing Proximity Information to SAT	p. 161
4. Exact Redundant Fault Identification	p. 163
4.1.1 Preprocessing	p. 164
5. Identifying Redundant Wire Replacements	p. 164
5.1 Wire Replacement Faults and Rewiring	p. 166
5.2 Detection by Don't Cares	p. 167
5.3 Don't Care Approximations	p. 169
5.4 SAT for Redundant Wire Identification	p. 170
5.4.1 Approximate Redundancy Identification	p. 171
6. Exact Wire Redundancy IDentification	p. 172
7. I/O Port Replacement Detection	p. 175
7.1 Detection of I/O Port Wire Switching Errors	p. 175
8. Experimental Results	p. 177
8.1 Gate Replacement Experiments	p. 177
8.1.1 Minimum Distance Replacements	p. 177
8.2 Wire Replacement Experiments	p. 182
8.2.1 True Fan-in Acyclic Replacements	p. 184
8.3 SAT vs. ATPG	p. 185
9. Conclusions	p. 185
Chapter 8 Conclusions and future work	p. 187
1. Conclusions	p. 187
2. Future Work	p. 189
Appendices	p. 191
References	p. 197
Index	p. 211

Available:*

On Order

Summary

Summary

Table of Contents