Fault Detection and Diagnostic Test Set Minimization
Except where reference is made to the work of others, the work described in this thesis is
my own or was done in collaboration with my advisory committee. This thesis does not
include proprietary or classified information.
Mohammed Ashfaq Shukoor
Certificate of Approval:
Victor P. Nelson
Professor
Electrical and Computer Engineering
Vishwani D. Agrawal, Chair
James J. Danaher Professor
Electrical and Computer Engineering
Adit D. Singh
James B. Davis Professor
Electrical and Computer Engineering
George T. Flowers
Dean
Graduate School
Fault Detection and Diagnostic Test Set Minimization
Mohammed Ashfaq Shukoor
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulfillment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
May 9, 2009
Fault Detection and Diagnostic Test Set Minimization
Mohammed Ashfaq Shukoor
Permission is granted to Auburn University to make copies of this thesis at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Mohammed Ashfaq Shukoor, son of Mrs. Rasheeda Begum and Mr. S. Mohammad
Iqbal, was born on October 2, 1983, in Bangalore, Karnataka, India. He graduated from
St. Joseph?s College, Bangalore in 2001. He earned the degree Bachelor of Engineering
in Electronics and Communication from Bangalore Institute of Technology affiliated to
Visvesvaraya Technological University, Belgaum, India in 2005. He then worked at Cog-
nizant Technology Solutions for about a year as a Programmer Analyst in the domain
of Customer Relationship Management. He joined the graduate program in Electrical &
Computer Engineering at Auburn University in January 2007. At Auburn University, as
a graduate research assistant he received support in parts from an Intel Corporation grant
and from the Wireless Engineering Research and Education Center (WEREC). During the
summer of 2008, he held an internship at Texas Instruments, Bangalore, India, working on
low power testing of VLSI circuits.
iv
Thesis Abstract
Fault Detection and Diagnostic Test Set Minimization
Mohammed Ashfaq Shukoor
Master of Science, May 9, 2009
(B.E., Bangalore Institute of Technology, 2005)
101 Typed Pages
Directed by Vishwani D. Agrawal
The objective of the research reported in this thesis is to develop new test generation
algorithms using mathematical optimization techniques. These algorithms minimize test
vector sets of a combinational logic circuit for fault detection and diagnosis, respectively.
The first algorithm generates a minimized fault detection test set. The test mini-
mization Integer Linear Program (ILP) described in the literature guarantees an absolute
minimal test set only when we start with the exhaustive set of test vectors. As it is im-
practical to work with exhaustive test sets for large circuits, the quality of the result will
depend upon the starting test set. We use the concept of independent fault set (IFS) defined
in the literature to find a non-exhaustive vector set from which the test minimization ILP
will give an improved (often minimal) test set. An IFS is a set of faults such that no two
faults in the set can be detected by the same vector. The largest IFS gives a lower bound
on the size of the test set since at least one vector is needed to detect each fault in the IFS.
This lower bound can be closely achieved by selecting tests from the test vectors derived for
the faults in the IFS. Using the theory of primal-dual linear programs, we model the IFS
identification as the dual of the test minimization problem. A solution of the dual problem,
v
whose existence is guaranteed by the duality theorem, gives us a conditionally independent
fault set (CIFS). A CIFS is an IFS relative to a non-exhaustive vector set. Our CIFS is,
therefore, not absolute but is specific to the starting vector set. Successively adding more
vectors to test the faults in the identified CIFS and solving the dual problem, we bring
the CIFS closer to its minimal size. In the process of reaching the absolute IFS we have
accumulated a non-exhaustive set of vectors that can now be minimized by the test mini-
mization ILP (now referred to as the primal problem) to get a minimal test set. Thus the
newly proposed primal-dual solution to the minimal test generation problem is based on (1)
identifying independent faults, (2) generating tests for them, and (3) minimizing the tests.
The primal-dual method, when applied to the ISCAS85 benchmark circuits, produces bet-
ter results compared to an earlier primal ILP-alone test minimization method [47]. For the
largest benchmark circuit c7552, the earlier minimization method (primal ILP) produced a
test set of 145 vectors in 151 CPU seconds, while our method (primal-dual ILP) produced
a test set of 139 vectors in just 71 CPU seconds.
In the second part of this research, we address the minimization of a diagnostic test
set without reduction in diagnostic resolution. A full-response dictionary is considered for
diagnosis. The full-response dictionary distinguishes between faults detected by exactly the
same test vectors but at different outputs of the circuit. A new diagnostic ILP is formulated
from a diagnostic table obtained by fault simulation without fault dropping. This ILP can
become intractable for large circuits due to very large number of constraints that typically
grows quadratically with the number of faults. We make the complexity manageable by
two innovations. First, we define diagnostic independence relation for fault-pairs with no
common test vector and also for faults-pairs detected by a common vector but at different
vi
outputs of the circuit. These fault-pairs require no constraint in the ILP, thus reducing
the number of constraints. Second, we propose a two-phase ILP approach. An initial ILP
phase, using an existing ILP procedure that requires a smaller set of constraints (linear in
the number of faults), preselects a minimal detection test set from the given unoptimized
vector set. Fault-pairs that are already distinguished by the preselected detection vectors
then do not require distinguishing constraints in the diagnostic ILP of the final phase,
which selects a minimal set of additional vectors for distinguishing between the remaining
fault-pairs. The overall minimized diagnostic test set obtained by the two phase method
may be only slightly longer than a one-step diagnostic ILP optimization, but it has the
advantages of significantly reduced computation complexity and reduced test application
time. The two-phase method, when applied to the ISCAS85 benchmark circuits, produces
very compact diagnostic test sets. For the largest benchmark circuit c7552, an earlier
compaction method [41] has reported a test set of 198 vectors obtained in 33.8 seconds.
Our method produced a test set of 128 vectors in 18.57 seconds.
vii
Acknowledgments
A lot of people have either directly or indirectly contributed towards this thesis, and I
owe a debt of gratitude to each and every one.
This work may not have been possible without the strong support, constant guidance
and remarkable patience of my advisor Dr. Vishwani Agrawal. His approach to research and
an in-depth knowledge of the subject will continue to inspire me. I thank Dr. Adit Singh
and Dr. Victor Nelson for being on my committee. I would like to express my gratitude to
Auburn University for giving me the opportunity to pursue my ambitions. I appreciate the
support from the Wireless Engineering Research and Education Center (WEREC) and the
encouragement I received from its director, Dr. Prathima Agrawal. The patient advice and
helpful attitude of Dr. Srivaths Ravi, Dr. Rubin Parekhji, and other coworkers at Texas
Instruments, Bangalore, added significantly to my understanding of VLSI testing.
Throughout the course of my Master?s degree, I have received a lot of support from my
colleagues especially Nitin, Wei, Khushboo, Jins, Fan, Kim, and Manish. I am thankful for
all their help and suggestions.
No words are enough to express my gratitude to my family for their unconditional love
and support. My parents Mohammad Iqbal and Rasheeda Begum, my brother Musheer,
and sister Zeba have provided me the best possible love and support.
Finally my special thanks to all my friends back home and at Auburn who have stood
by me during my good and bad times.
viii
Style manual or journal used Journal of Approximation Theory (together with the style
known as ?aums?). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (specifically LATEX)
together with the departmental style-file aums.sty.
ix
Table of Contents
List of Figures xii
List of Tables xiii
1 Introduction 1
1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Original Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Background 5
2.1 Types of Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Testing/Diagnosis Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Fault Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.1 Single Stuck-at Fault Model . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.2 Other Fault Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 Relations among Faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5.1 Fault Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5.2 Fault Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5.3 Fault Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5.4 Fault Concurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6 Fault Collapsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.7 Fault Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.8 Test Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.9 Failure Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.10 Fault Diagnosis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.11 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.11.1 Standard LP Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.12 Primal and Dual Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.13 Integer Linear Programming (ILP) . . . . . . . . . . . . . . . . . . . . . . . 22
2.14 Applications of Linear Programming in Testing . . . . . . . . . . . . . . . . 23
3 Previous Work on Detection Test Set Minimization 24
3.1 Independent Fault Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Independence Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Need for Test Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Test Set Compaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
x
3.4.1 Static Compaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.2 Dynamic Compaction . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Methods of Finding Maximal IFS . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Minimal Test Generation using Primal-dual ILP Algorithm 38
4.1 Test Minimization ILP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2 Dual ILP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3 A Primal-Dual ILP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4.1 Example 1: c1355 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4.2 Example 2: c2670 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5 Benchmark Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.6 Primal LP with Recursive Rounding . . . . . . . . . . . . . . . . . . . . . . 50
4.7 Analysis of Duality for Integer Linear Programs . . . . . . . . . . . . . . . . 52
5 Background on Fault Diagnosis 56
5.1 Fault Diagnosis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.1.1 Cause-Effect Diagnosis . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.1.2 Effect-Cause Diagnosis . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2 Diagnosis Using Fault Dictionaries . . . . . . . . . . . . . . . . . . . . . . . 57
5.2.1 Full-Response (FR) Dictionary . . . . . . . . . . . . . . . . . . . . . 58
5.2.2 Pass-Fail (PF) Dictionary . . . . . . . . . . . . . . . . . . . . . . . . 58
5.3 Dictionary Compaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6 Daignostic Test Set Minimization 63
6.1 ILP for Diagnostic Test Set Minimization . . . . . . . . . . . . . . . . . . . 63
6.1.1 Fault Diagnostic Table for Diagnostic ILP . . . . . . . . . . . . . . . 63
6.1.2 Diagnostic ILP Formulation . . . . . . . . . . . . . . . . . . . . . . . 65
6.2 Generalized Fault Independence . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 Two-Phase Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.5 Analysis of Undistinguished Fault Pairs of c432 . . . . . . . . . . . . . . . . 76
7 Conclusion 79
7.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.1.1 Primal-Dual Algorithm with Partially Specified Vectors . . . . . . . 80
Bibliography 83
Appendix 88
xi
List of Figures
2.1 Testing/Diagnosis Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Relations Between Faults f1 and f2 . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1 c17 Circuit with 11 Functional Dominance Collapsed Faults [69] . . . . . . . 25
3.2 Independence Graph for c17 Benchmark Circuit . . . . . . . . . . . . . . . . 26
3.3 Largest Clique in the Independence Graph of Figure 3.2 . . . . . . . . . . . 27
3.4 Multiple Maximum Cliques in the Independence Graph of Figure 3.2 . . . . 28
4.1 Detection Matrix akj. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 CPU Time Comparison Between Primal LP-Dual ILP Solution with Pri-
mal ILP-Dual ILP Solution. . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Test Set Size Comparison Between Primal LP-Dual ILP Solution with Pri-
mal ILP-Dual ILP Solution. . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1 Tests and Their Fault Free Responses. . . . . . . . . . . . . . . . . . . . . . 59
5.2 Full-Response Fault Dictionary. . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.3 Pass-Fail Fault Dictionary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.1 Full-Response Fault Dictionary. . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2 Fault Diagnostic Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.3 Fault Detection Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.4 Fault Diagnostic Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.5 Comparison Between 1-Step Diagnostic ILP Minimization and 2-Phase Ap-
proach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.6 An ATPG-based Method for Examining a Fault Pair (fi, fj). . . . . . . . . 78
7.1 Non-optimal Solution Obtained Using ILP Minimization. . . . . . . . . . . 81
7.2 Minimizing Partially Specified Vectors and then Vector Merging. . . . . . . 82
xii
List of Tables
2.1 Primal and Dual Problem Definition . . . . . . . . . . . . . . . . . . . . . . 22
4.1 Four-bit ALU and Benchmark Circuits - Initial ATPG Vectors and Target
Fault Set. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2 Example 1: Dual ILP Iterations and Primal ILP Solution for c1355. . . . . 47
4.3 Example 2: Dual ILP Iterations and Primal ILP Solution for c2670. . . . . 48
4.4 Test Sets Obtained by Primal-Dual ILP for 4bit ALU and Benchmark Circuits. 49
4.5 Comparing Primal-Dual ILP Solution With ILP-Alone Solution [47]. . . . . 50
4.6 Test Sets Obtained by Primal LP-Dual ILP Solution for 4bit ALU and
Benchmark Circuits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.7 Comparing Primal LP-Dual ILP Solution with LP-Alone Solution [48]. . . . 54
4.8 Comparison of Optimized Values of Relaxed LP and ILP. . . . . . . . . . . 55
6.1 Independence Relation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.2 Generalized Independence Relation. . . . . . . . . . . . . . . . . . . . . . . 68
6.3 Constraint Set Sizes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.4 Phase-1: Diagnosis With Minimal Detection Test Sets. . . . . . . . . . . . . 74
6.5 Phase-2: Diagnostic ILP Minimization. . . . . . . . . . . . . . . . . . . . . . 75
6.6 Diagnosis with Complete Daignostic Test Set. . . . . . . . . . . . . . . . . . 76
6.7 Two-phase Minimization vs. Previous Work [41]. . . . . . . . . . . . . . . . 77
xiii
Chapter 1
Introduction
With increasing integration levels in today?s VLSI chips, the complexity of testing them
is also increasing. This is because the internal chip modules have become increasingly diffi-
cult to access. Testing costs have become a significant fraction of the total manufacturing
cost. Hence there is a necessity to reduce the testing cost. The factor that has the biggest
impact on testing cost of a chip is the time required to test it. This time can be decreased
if the number of tests required to test the chip is reduced. So, we simply need to devise a
test set that is small in size. One way to generate a small test set is to compact a large
test set. But, the result of compaction depends on the quality of the original test set. This
aspect of compaction has motivated the work presented in the initial part of this thesis.
Another important aspect of the VLSI process is Failure Analysis, the process of de-
termining the cause of failure of a chip. Once a chip has failed a test, it is important to
determine the cause of its failure as this can lead to improvement in the design of the chip
and/or the manufacturing process. This in turn can increase the yield of the chips. Fault
diagnosis is the first step in failure analysis, which by logical analysis gives a list of likely
defect sites or regions. Basically, fault diagnosis narrows down the area of the chip on which
physical examination needs to be done to locate defects. Fault dictionary based diagnosis
has been the most popular method, as it facilitates faster diagnosis by comparing the ob-
served behaviors with pre-computed signatures in the dictionary. Here again the size of the
fault dictionary becomes prohibitive for large circuits. We explore the idea of managing the
diagnostic data in a full-response dictionary by optimizing the diagnostic test set.
1
1.1 Problem Statement
The problems solved in this thesis are:
? Finding a minimal set of vectors to cover all stuck-at faults in a combinational circuit
? Formulating an exact method for minimizing a given diagnostic test set.
? Devising a polynomial time approach to overcome the computational limitations of
the exact method of item 2.
1.2 Original Contributions
We have developed a new test generation algorithm to produce minimal test sets for
combinational circuits. This method is based on (1) identifying independent faults, (2)
generating tests for them, and (3) minimizing the tests. The parts 1 and 2, give us a non-
exhaustive vector set, which on compaction will give a minimal test set. Using the theory of
primal-dual linear programs, we have modeled the independent fault set identification as the
dual of the already known test minimization integer linear program (ILP) [29]. A solution of
the dual ILP, whose existence is guaranteed by the duality theorem, gives us a conditionally
independent fault set (CIFS). The third part, test minimization, is accomplished by the
already known test minimization ILP, now called the primal ILP. Benchmark results show
potential for both smaller test sets and lower CPU times.
To address the problem of the fault dictionary size, we have given a Diagnostic ILP
formulation to minimize test sets for a full-response dictionary based diagnosis. The ILP
solution is a smaller test set with diagnostic characteristics identical to the unoptimized
test set. An ideal test set for diagnosis is one which distinguishes all faults. Thus during
2
diagnostic test set minimization it should be ensured that the resulting test set consists of
at least one vector to distinguish every pair of faults. This is done by having a constraint
for every fault pair to be distinguished. Note that the number of fault pairs is proportional
to the square of the number of faults. This results in a very large number of constraints
in the diagnostic ILP, making its computational complexity exponential. To overcome the
constraint problem we have defined a diagnostic fault independence relation which reduces
the number of fault pairs to be distinguished and thus the number of constraints. Finally we
have developed a two-phase method for generating a minimal diagnostic test set from any
given test set. In the first phase we used existing ILP minimization techniques to obtain a
minimal detection test set and found the faults not diagnosed by this test set. In the second
phase we used the diagnostic ILP to select a minimal set of vectors capable of diagnosing
the undiagnosed faults of phase-1. The resulting minimized test set combined with the
minimal detection test set of phase-1 serves as our complete diagnostic test set.
A paper [73] describing the primal-dual ILP algorithm was presented at the 12th VLSI
Design and Test Symposium (VDAT-2008) in July 2008. Another paper [74] on the two-
phase method of diagnostic test set minimization has been accepted for presentation at the
Fourteenth IEEE European Test Symposium (ETS-2009) to be held in May 2009.
1.3 Organization of the Thesis
The thesis is organized as follows. In Chapter 2, we discuss the basics of testing and
fault diagnosis. In Chapter 3, the previous work on test set compaction is discussed. In
Chapter 4, the new primal-dual ILP algorithm is introduced and results for some benchmark
circuits are presented. To prepare the reader for the second part of research in the thesis,
3
Chapter 5 provides the background material on fault diagnosis. Chapter 6 then discusses the
original two-phase approach for diagnostic test set minimization with results on benchmark
circuits. Conclusions and ideas about future work directions are discussed in Chapter 7.
4
Chapter 2
Background
This chapter gives the basic background material on VLSI testing and fault diagnosis,
which includes fault models, fault collapsing, test generation, fault simulation, etc. We also
touch upon some basics of Linear Programming, the optimization technique used in this
research for minimizing test sets for both testing and diagnosis. Our discussion begins with
a description of the types of circuits that will and will not be addressed by the testing and
diagnosis methods discussed in this thesis.
2.1 Types of Circuits
This thesis will address the problem of minimal test set generation for testing and
diagnosis in combinational logic circuits only. However, it should be noted that nearly all
sequential logic, i.e., circuits containing state-holding elements (flip-flops) are tested in a
way that transforms their operation under test from sequential to combinational. This is
usually accomplished by implementing scan-based design [13] in which all flip-flops in the
circuit are modified and are stitched together to from one or more scan chains, so that they
can be controlled and observed by shifting data through these scan chains. During scan
based testing, input data is scanned into the flip-flops via the scan chains and other input
data is applied to the input pins (or primary inputs) of the circuit. Once these inputs are
applied and the circuit (now fully combinational) has stabilized its response, the circuit is
clocked to capture the results back into the flip-flops, and the data values at the output pins
(or primary outputs) of the circuit are recorded. The combination of values at the primary
5
outputs and the values scanned out of the scan chains make up the response of the circuit
to the test. Like for testing, the scan based environment is also used for fault diagnosis.
2.2 Testing/Diagnosis Process
The basic process of testing or diagnosing a digital circuit is shown in Figure 2.1 [13].
During testing the digital circuit is referred to as Circuit under Test (CUT), and during
diagnosis it is referred as Circuit under Diagnosis (CUD). Binary test vectors are applied
to the CUT/CUD. The response of the CUT/CUD to a test vector is compared with the
stored correct response. A mismatch between the stored and observed responses indicates
a bad circuit.
The input data to the CUT/CUD is referred to as the test pattern or test vector. A
collection of test vectors designed to exercise whole or part of the circuit is called a test
set. There are two kinds of tests: fault detection tests and fault diagnostic tests [16]. Fault
detection tests are used for the purpose of testing and they tell us whether the CUT is
faulty or fault-free. They do not give any information on the identity (type, location) of
the fault. A diagnostic test is applied after a circuit has failed the testing process. Its aim
is to identify the fault that caused the circuit to fail.
2.3 Testing
Testing is the process of verifying if the manufactured chip has the intended functional-
ity and timing. The test inputs to a digital IC (Integrated Circuit) are developed to exercise
the implemented function or to detect modeled faults [6].
6
STORED
CORRECT
RESPONSE
COMPARATOR
DIGITAL
CIRCUIT
--- 11
--- 01
-----
-----
--- 00
01 ---
10 ---
-----
-----
10 ---
TEST / DIAGNOSIS
RESULT
INPUT PATTERNS OUTPUT RESPONSES
Figure 2.1: Testing/Diagnosis Process
Testing can be of two types - functional and structural testing. Functional tests are
used to completely exercise the circuit function. A complete functional test for a circuit will
check all entries of the truth table for the circuit function. The problem with this approach is
the number of the tests needed to completely exercise even simple functions. For example,
a 64-bit ripple carry adder has 129 inputs and 65 outputs. To completely exercise its
function, we need 2129 input patterns. An Automatic Test Equipment (ATE) operating at
1GHz would take about 1022 years to apply all of these patterns to the CUT [13]. Thus an
exhaustive functional test is impractical even for moderate sized circuits. Structural tests
on the other hand are used to verify the topology of the CUT. A structural test can be
used to verify if all connections are intact and all gate-level truth tables are correct [35].
Structural testing is entirely based on fault models.
7
2.4 Fault Modeling
A defect is the unintended difference between implemented hardware and its intended
design [13]. Defects are those that could occur in a fabricated IC. A fabricated chip could
have many types of defects, for example, breaks in signal lines, lines shorted to ground,
lines shorted to VDD, etc. Fault modeling is the translation of real world defects to a
mathematical construct that can be operated upon algorithmically and understood by a
software simulator for the purpose of providing a metric for quality measurement [21].
Thus physical defects are modeled as faults because the analysis of faults is much simpler.
Also, fault models greatly simplify the test generation process. Physical defects can be
modeled as either logical faults or delay faults, depending on whether the defect affects the
logical behavior or the time of operation. Fault models can represent many, though not all
physical defects.
2.4.1 Single Stuck-at Fault Model
This is the earliest and most widely used fault model to date. Eldred?s 1959 paper [27]
laid the foundation for the stuck-at fault model, though that paper did not make any
mention of the stuck-at fault. The term ?stuck-at fault? first appeared in the 1961 paper
by Galey, Norby and Roth [33].
Stuck-at faults are gate-level faults modeled by assigning a fixed ?0? or ?1? value to an
input or an output of a logic gate or a flipflop [13]. Each interconnection in a circuit can have
two faults, stuck-at-1 (sa1, s-a-1) and stuck-at-0 (sa0, s-a-0). If we assume that there can be
several simultaneous stuck-at faults, then in a circuit with n interconnections between gates
there are 3n ?1 possible multiple stuck-at faults. All combinations except the one having
8
all lines as fault-free are treated as faults. It is evident that even for moderate values of n,
the number of multiple stuck-at faults could be very large. Thus it is a common practice to
model only single stuck-at faults. Therefore the assumption is that only one stuck-at fault
is present in a circuit at a time. In a circuit with n interconnections there can be no more
than 2n single stuck-at faults. This number can be further reduced using fault collapsing
techniques [13, 69] discussed in Section 2.6. Numerous algorithms have been developed and
programmed to efficiently generate tests for single stuck-at faults [66, 36, 31, 65, 43, 71, 72].
2.4.2 Other Fault Models
Other than stuck-at faults there are bridging faults that model electrical shorts between
signal lines occurring at the wafer level. Then there are transition delay faults that model
gross delay defects (such as pinched metal lines, resistive contacts, etc.) at gate terminals.
Path delay faults model small distributed delay defects which cause timing failures in the
chip. The detection of transition and path delay fault requires a pair of vectors. The IDDQ
faults are those that elevate the steady state current in the circuit. For example, transistor
shorts can be effectively modeled as IDDQ faults. As can be seen each fault model, models
unique types of defects. Details of these fault models can be found in [13].
2.5 Relations among Faults
Consider two faults f1 and f2. Let T(f1) and T(f2) be the sets of all the test vectors
that detect f1 and f2 respectively. The following relations can be defined for a pair of
faults.
9
T( f1 )=T (f2) T( f2 ) T (f 1 )
T( f1 ) T( f1 ) T (f2) T (f2)
(a) f1 and f2 are equivalent (b ) f 2 dominates f 1
( c ) f1 and f2 are i ndependent ( d ) f1 and f2 are c oncurrent
Figure 2.2: Relations Between Faults f1 and f2
2.5.1 Fault Equivalence
Two faults are said to be equivalent, if and only if the corresponding faulty circuits
have identical output functions [13]. Equivalent faults cannot be distinguished by any test
vector, i.e., a test for one fault will also detect the other fault. Thus the two faults have
the exact same test sets as shown in Figure 2.2(a).
2.5.2 Fault Dominance
If all tests of fault f1 detect another fault f2, then f2 is said to dominate f1. This
relation is shown in Figure 2.2(b), where T(f1) ? T(f2). Thus any test for the dominated
fault (f1) will also be a test for the dominating fault (f2). Notice that fault equivalence
10
is a special condition of fault dominance in which two faults dominate each other. So,
dominance is a more basic relation than equivalence.
2.5.3 Fault Independence
Two faults are said to be independent if and only if they cannot be detected by the
same test vector [7, 8], i.e., they have no common test. Thus, if f1 and f2 are independent
then T(f1) and T(f2) are disjoint sets as shown in Figure 2.2(c).
2.5.4 Fault Concurrence
Two faults that neither have a dominance relationship nor are independent are defined
as concurrently-testable faults [24]. The concurrently-testable faults can have two types of
tests as depicted in Figure 2.2(d):
1. Each fault has an exclusive test that does not detect the other fault [3].
2. A common test called the concurrent test in [24], that detects both faults.
Concurrently-testable faults have also been referred to as compatible faults in the litera-
ture [7].
2.6 Fault Collapsing
We had seen that for a circuit with n interconnections we would have 2n stuck-at faults.
Clearly this number would become very large for big circuits, and would result in longer
test set generation times. Fault Collapsing is the process of reducing the number of faults
that need to be targeted for test generation, without any penalty on the fault coverage. It
11
is done by utilizing the relations defined in the previous section. The relative size of the
collapsed set with respect to the set of all faults is called the collapse ratio [13]:
Collapse ratio = |Set of collapsed faults||Set of all faults|
Fault collapsing can be classified into two types, Equivalence collapsing and Dominance
Collapsing. Equivalent fault collapsing involves partitioning all faults into disjoint equiv-
alent fault sets such that all faults in a set are equivalent to each other, and selecting
one representative fault from each set. The resulting set of faults is called an equivalence
collapsed fault set. A test vector which detects the representative fault of an equivalent
fault set will also detect all other faults belonging to that set. So we need to generate a
test only for the representative fault. This reduces the test generation time. It should be
noted that equivalence collapsing does not affect the diagnostic resolution, i.e., the ability
to distinguish between faults.
In the case of large circuits, where coverage (detection) of faults is more important
than their exact location (diagnosis), dominance fault collapsing may be desirable [23]. For
a pair of faults having a dominance relation, a test for the dominated fault will also detect
the dominating fault. Thus the dominating fault can be dropped from the target fault
list. However there is a drawback to dominance fault collapsing. In case the dominated
fault is redundant, i.e., it does not modify the input-output function of the circuit and
cannot be detected by any test, there would be no test for the dominating fault even if it
is detectable. Dominance collapsing always results in a smaller set than the equivalence
collapsed set. Though dominance collapsing produces a smaller collapsed fault set, the
12
tests for the collapsed faults may not guarantee 100% fault coverage. Hence equivalence
collapsing is more popular.
For example, consider an n-input AND gate. The total number of stuck-at faults is
2n + 2. All single s-a-0 faults on the inputs and output of the AND gate are equivalent.
Thus, using equivalence collapsing, the number of stuck-at faults is reduced to n+2. Also,
the output s-a-1 fault dominates a single s-a-1 fault on any input and hence the output s-
a-1 can be left out of the target fault set. Thus, dominance fault collapsing further reduces
the number of faults for an n-input AND gate to n+ 1. Similar results for dominance and
equivalence fault collapsing can be derived for other Boolean gates as well. It must be noted
that faults on a fanout stem and branches cannot be collapsed.
Equivalence and dominance fault collapsing can either be performed at a functional or
structural level. Functional collapsing is based on the effect of faults on the Boolean function
of the circuit [4]. For an n-line circuit there are 2n single stuck-at faults, and the Boolean
equation has to be applied to 2n2?1 pairs of faults to determine all equivalence/dominance
relations [13]. Also, it will be cumbersome to manipulate large Boolean functions. For these
reasons structural collapsing is used in practice. In structural collapsing relations between
faults are determined for simple Boolean gates and are then applied to larger circuits.
The size of the fault set can be further reduced by performing hierarchical fault collaps-
ing as described in [4, 5, 63, 68, 70]. Most definitions for fault equivalence and dominance,
appearing in the literature, correspond to single output circuits. For such circuits, fault
equivalence defined on the basis of indistinguishability (identical faulty functions) implies
that the equivalent faults have identical tests. However, for multiple output circuits, two
faults that have identical tests can be distinguishable if their output responses are not the
13
same. This leads to diagnostic equivalence and diagnostic dominance which are extended
definitions for equivalence and dominance respectively [68, 70].
2.7 Fault Simulation
Fault simulation is the process of computing the response of a faulty circuit to given
input stimuli. The program that performs fault simulation is called a fault simulator. The
basic operation of a fault simulator is as follows: Given a circuit, a test input and a fault,
the fault simulator inserts the fault into the circuit and computes its output response for
the test input. It also computes the good circuit response to the same test input. Finally it
declares the fault as detected if there is mismatch between the good and faulty responses.
Thus for a test set and a fault list the fault simulator can give the fault coverage of the test
set. Fault coverage is defined as [13],
Fault Coverage = Number of faults detectedNumber of faults in initial fault list
Notice that the fault simulator can determine which faults are detected by which test
vectors. We have used this feature of the fault simulator extensively in our work. Also, a
fault simulator is used along with an Automatic Test Pattern Generator (ATPG) for test
generation.
There are several algorithms for fault simulation, the simplest being the serial fault
simulation. Here fault simulation is performed for one fault at a time. As soon as one fault
is detected, the simulation is stopped and a new simulation is started for another fault.
This fault simulation method, though simple, is very time consuming.
14
Another technique of fault simulation, which simulates more than one fault in one pass
is called parallel fault simulation. It makes use of the bit-parallelism of logical operations
in a digital computer [13]. The parallel fault simulator can simulate a maximum of w ?1
faults in one pass, where w is the machine word size. So, a parallel fault simulator may run
w ?1 times faster than a serial fault simulator. Other fault simulation algorithms include
Test-Detect [67], Deductive [9], Concurrent [77, 78], Differential [18], etc.
2.8 Test Generation
Automatic test pattern generation is the process of generating input patterns to test a
circuit, which is described strictly with a logic-level netlist [13]. These programs usually op-
erate with a fault generator program, which creates the collapsed fault list. Test generation
approaches can be classified into three categories: exhaustive, random and deterministic.
In the exhaustive approach, for an n-input circuit, 2n input patterns are generated.
The exhaustive test set guarantees 100% fault coverage (ignoring the redundant faults if
any). It is evident that this approach is feasible only for circuits with very small number of
primary inputs.
Random test generation is a simple approach in which the input patterns are generated
randomly. Fault simulation is performed for every randomly generated pattern. A pattern
is selected only if it detects new faults. In a typical test generation process, random patterns
are used for achieving an initial 60-80% fault coverage, after which deterministic test pattern
generation can be employed to achieve the remaining coverage [2].
Deterministic Automatic Test Pattern Generator (D-ATPG) algorithms are based on
injecting a fault into a circuit, and determining values for the primary inputs of the circuit
15
that would activate that fault and propagate its effect to the circuit output. In deter-
ministic test generation, the search for a solution involves a decision process for selecting
an input vector from the set of partial solutions using an algorithmic procedure known as
backtracking. In backtracking, all previously assigned signal values are recorded, so that
the search process is able to avoid those signal assignments that are inconsistent with the
test requirement. The exhaustive nature of the search causes the worst-case complexity to
be exponential in the number of signals in the circuit [32, 42]. To minimize the total time,
a typical test generation program is allowed to do only a limited search in the number of
trials or backtracks, or the CPU time.
The most widely used deterministic automatic test pattern generation algorithms are:
D-algorithm[66], PODEM(Path-Oriented DecisionMaking)[36]and FAN(Fanout-Oriented
Test Generator) [31]. The faults left undetected after the D-ATPG phase are either redun-
dant faults for which no test exists, or aborted faults that could not be detected due to
CPU time limit.
2.9 Failure Analysis
Testing of fabricated chips prevents the shipment of defective parts, but improving
the production quality of the chips depends on effective failure analysis. A better quality
production process means higher yield, i.e., more usable die. Typically, an IC product
goes through two manufacturing stages [52]: (1) prototype stage, and (2) high-volume
manufacturing stage.
During the prototype stage, a small number of sample chips are produced to verify
the functionality and timing of the design. The chips may fail badly due to design bugs or
16
manufacturing imperfections. All issues that cause the chip to fail must be addressed so
that these do not recur when the design goes into mass production. It is here that failure
analysis comes into play.
After the prototype stage, the product is ready for high-volume production. In this
stage there could be fluctuations in the yield mainly due to manufacturing errors. Contin-
uous yield monitoring is necessary from time to time to respond to unexpected low-yield
situations [50]. Here again failure analysis is the means for yield improvement.
Some of the methods of failure analysis consist of etching away certain layers, imag-
ing the silicon surface by scanning electron microscopy (SEM) or focused ion beam (FIB)
systems, particle beams, etc. [52]. Any analysis performed directly on the defective chip is
called physical analysis. With millions of transistors and several layers of metals, physical
analysis process is often laborious and time consuming. Thus physical inspection of the chip
is not feasible without an initial suspect list of defect sites. It is the job of fault diagnosis
to guide the physical analysis process by providing the suspected defect locations.
2.10 Fault Diagnosis
Fault diagnosis is the first step in failure analysis which by logical analysis gives a list
of likely defect sites or regions. Basically, fault diagnosis narrows down the area of the chip
on which physical examination needs to be done to locate defects. Fault diagnosis involves
applying tests to failed chips and analyzing the test results to determine the nature of the
fault. A test set used for the purpose of diagnosis is referred to as a diagnostic test set [16].
The test sets are constructed so as to ideally pin-point to a single fault candidate. Such a
characteristic of a diagnostic test set is called its diagnostic resolution. The highest number
17
of fault candidates reported for a test in the diagnostic test set is referred to as its diagnostic
resolution. Precision of fault diagnosis is very critical as it leads to physical analysis. If a
wrong site or location is predicted then the actual defect site could be damaged during the
physical inspection process of the predicted site.
2.11 Linear Programming
In the work described in this thesis, the optimization of detection and diagnostic test
sets is done using linear programming techniques. Thus, the current and the subsequent
sections of this chapter give a brief review of linear programming.
Linear Programming (LP) is the method of selecting the best solutions from the avail-
able solutions to a problem. It is the most widely used method of constrained optimization
in economics and engineering fields.
The main elements of any linear program are,
1. Variables: The goal is to find the values for the variables that provide the best value
of the objective function. These values are unknown at the start of the problem.
LP assumes that all variables are real valued, meaning that they can take fractional
values.
2. Objective function: This is a linear mathematical expression that uses the variables
to express the goal of optimization. The goal of the LP problem is to either maximize
or minimize the value of the objective function.
3. Functional Constraints: These are linear mathematical expressions that use the
variables to express certain conditions that need to be met while looking for the
possible optimum solution
18
4. Variable Constraints: Usually variables have bounds. Very rarely are the variables
unconstrained.
With the advancements in computing power and algorithms for solving LPs, the largest
optimization problems today could have millions of variables and hundreds of thousands of
constraints. These large problems can be solved in practical amounts of time.
2.11.1 Standard LP Problems
LP problems can have objective functions to be maximized or minimized, constraints
may be inequalities (?, ?) or equalities (=), and variables can have upper or lower bounds.
There are two standard classes of problems - the standard maximum problem and the stan-
dard minimum problem [28]. In these problems all variables are constrained to be non-
negative, and all functional constraints are inequalities. These two play an important role
because any LP problem can be converted to one of these two standard forms.
We are given an m-vector, b = (b1, . . .,bm)T, an n-vector, c = (c1, . . .,cn)T, and an
m ? n matrix of real numbers,
A =
?
??
??
??
??
??
??
??
?
a11 a12 . . . a1n
a21 a22 . . . a2n
. . . .
. . . .
am1 am2 . . . amn
?
??
??
??
??
??
??
??
?
The Standard Maximum Problem [28] is to find an n-vector, x = (x1, . . .,xn)T,
to Maximize
P = c1x1 + c2x2 +...+ cnxn (or P = cTx)
19
subject to the constraints,
a11x1 + a12x2 + . . . + a1nxn ? b1
a21x1 + a22x2 + . . . + a2nxn ? b2
. (or Ax ? b)
.
am1x1 + am2x2 + . . . + amnxn ? bm
and
x1 ? 0, x2 ? 0, . . . , xn ? 0 (or x ? 0)
Here, xj and cj (where j = 1,2,...,n) are the variables and coefficients respectively in
the objective function. P is the objective function value that needs to be maximized. bi are
the limits, and aij (where i = 1,2,...,m) are the coefficients of the functional constraint
equations.
SimilarlytheStandard Minimum Problem[28]istofind anm-vector, y = (y1, ...,yn)T,
to Minimize
Q = b1y1 + b2y2 +...+ bmym (or Q = yTb)
subject to the constraints,
a11y1 + a12y2 + . . . + am1yn ? c1
a12y1 + a22y2 + . . . + am2yn ? c2
. (or yTA ? cT)
.
a1ny1 + a2ny2 + . . . + amnyn ? cn
20
and
y1 ? 0, y2 ? 0, . . . , ym ? 0 (or y ? 0)
Here, yi and bi (where i = 1,2,...,m) are the variables and coefficients respectively in
the objective function. Q is the objective function value that needs to be minimized. cj are
the limits, and aij (where j = 1,2,...,n) are the coefficients of the functional constraint
equations.
Many algorithms have been proposed to solve linear programs. One of the oldest and
most popular methods is the simplex method [10, 22] invented by George Dantzig in 1947.
It is a robust method as it can solve any linear program. Interior-point method found by
Karmarkar [49] is a polynomial time method and is preferred over the simplex method for
extremely large problems.
2.12 Primal and Dual Problems
If we have an optimization problem defined for an application, we could define another
optimization problem called the dual problem. The original problem now will be called the
primal problem. These two problems share a common set of coefficients and constants. If
the primal minimizes one objective function of one set of variables then its dual maximizes
another objective function of the other set of variables
Let us look at the duality for the standard problems defined previously. As in Sec-
tion 2.11.1, c and x are n-vectors, b and y are m-vectors, and A is an m ? n matrix. We
assume m ? 1 and n ? 1.
The dual of the standard maximum problem is the standard minimum problem. The
definitions of the primal maximum problem and the dual minimum problem are given in
21
Table 2.1: Primal and Dual Problem Definition
Standard Maximum Standard Minimum
Problem (Primal) Problem (Dual)
Maximize P = cTx Minimize Q = yTb
subject to, subject to,
Ax ? b yTA ? cT
and x ? 0 and y ? 0
Table 2.1. Another way to look at this is the dual of the standard minimum problem is the
standard maximum problem. Hence the two problems are called duals.
The primal and dual LP problems are related by an important property called dual-
ity. This property indicates that we may in fact solve the dual problem in place of or in
conjunction with the primal problem.
Duality theorem states that if the primal problem has an optimal solution, then the
dual also has an optimal solution, and the optimized values of the two objective functions
are equal [75].
There is a twofold advantage in studying the dual problem. First, its implementation
enhances the understanding of the original (primal) model. Second, it is sometimes com-
putationally easier to solve the dual model than the original model, and likewise provides
the optimal solution to the latter at no extra cost.
2.13 Integer Linear Programming (ILP)
ILP is a variant of LP where the variables can take on only integer values. In ILP
the number of solutions grows extremely rapidly as the number of variables in the problem
increases. This is because of the numerous possible ways of combining these variables. Thus
the worst case computational complexity of ILP problems is exponential.
22
Special algorithms such as branch and bound method [10] have been developed to find
optimal integer solutions. However, the size of problem that can be solved successfully by
these algorithms is an order of magnitude smaller than the size of linear programs that can
easily be solved. The LP problem has polynomial complexity due to its continuous decision
space, as the variables can take fractional values. Thus in some cases the ILP problem is
converted to a relaxed-LP problem by allowing the variables to take on real values, after
which rounding algorithms are used to obtain an integer solution.
The primal-dual problems of LP described in the previous section can be transformed
into two ILP problems by treating the variables as integers. The ILP problems share several
of the duality properties.
2.14 Applications of Linear Programming in Testing
The ILP techniques have been used to optimize various aspects of testing. They have
been used to obtain optimization of test sets for both combinational [29] and sequential
circuits [26] as well as for globally minimizing N-detect tests [47, 46] and multiple fault model
tests [81]. Other applications for the ILP techniques include test resource optimization [14,
58] and test data compression [15] for the testing of SoCs.
As stated earlier the computational complexity of the ILP would be too high to obtain
an optimum solution for even medium size circuits. For this reason reduced-complexity LP
variations such as the recursive rounding technique [48] can be used. The recursive rounding
technique has been described in detail in the appendix.
23
Chapter 3
Previous Work on Detection Test Set Minimization
This chapter gives a background of the various compaction techniques that have been
proposedfordetectiontestsetminimization. Inthischapter testsetminimization/compaction
is in the context of detection test sets only.
Before discussing the various test minimization techniques described in the literature let
us look at the concept of independent fault set (IFS), which plays an important role in test
minimization.
3.1 Independent Fault Set
In Section 2.5 we had seen the definition of the independence relation between a pair of
faults. Two faults are called independent if no vector can detect both [7]. An independent
fault set (IFS) contains faults that are pair-wise independent. Thus we need one vector for
every fault in the IFS. Hence the cardinality of the largest IFS for a circuit provides a lower
bound on the size of a complete fault detection test set [7].
3.2 Independence Graph
The independence relations among faults can be represented graphically as an inde-
pendence graph (also known as incompatibility graph). In an independence graph the nodes
represent faults, and the edges between nodes represent the pair-wise independence rela-
tions between faults. As independence is a symmetric relation the edge does not require a
24
direction. Thus an edge between two nodes means that the two corresponding faults cannot
be detected by a common vector. And the absence of an edge between two nodes indicates
that the corresponding two faults can be detected by a common test vector, i.e., the two
faults could have equivalence, dominance or concurrence relation.
Figure 3.2 shows the independence graph for ISCAS85 [40] benchmark circuit c17 [23].
The circuit has 17 nets, so there will be 34 single stuck-at faults. Using functional dominance
collapsing of [69] the number of faults is reduced to eleven. Figure 3.1 shows the eleven faults
in the c17 circuit, numbered 1 through 11. The edges in the independence graph represent
functional independences and were found using the ATPG-based procedure described in [23].
Here it should noted that if the independence graph is for a dominance collapsed fault set,
then the absence of an edge between two nodes means that the two faults are concurrently-
testable.
x
x x
x
x
x
4
x x
x
2
x
x
1
6
8
7 3
5
9
1 0
11
Faults numbered 1 through 11 are all s - a - 1 t yp es
Figure 3.1: c17 Circuit with 11 Functional Dominance Collapsed Faults [69]
In an independence graph the nodes belonging to a clique form an IFS. A clique is a
subgraph in which every node is connected to every other node [20]. A maximum clique is
25
2 3 4 5
6 7 8 9 10
11
1
Figure 3.2: Independence Graph for c17 Benchmark Circuit
a clique of largest size i.e., with the highest number of nodes. Thus the maximum clique of
an independence graph will give the largest IFS.
From the independence graph of c17, redrawn in Figure 3.3, it is clear that nodes
(faults) 1, 2, 4 and 5 form an independent fault set (IFS). So, in order to detect all faults
in c17, we need at least 4 vectors. Actually, the minimum possible test set for c17 has
four vectors. In general, however, the size of largest IFS is only a theoretical minimum and
such a test set whose size equals the lower bound may not be achieved in practice for many
circuits. This was shown in [46] where, for a 5-bit and 6-bit multiplier a minimum test set
of 7 test vectors was obtained, whereas the theoretical lower bound for these multipliers is
6.
One important point to make note of is that a circuit can have multiple maximal
independent fault sets. For example, Figure 3.4 shows the same independence graph for c17
26
2 3 4 5
6 7 8 9 10
11
1
Figure 3.3: Largest Clique in the Independence Graph of Figure 3.2
with another maximum clique formed by nodes numbered 6, 7, 8 and 9. The four faults
corresponding to these nodes also form a maximal IFS.
3.3 Need for Test Minimization
Compact test sets are very important for reducing the cost of testing VLSI circuits by
reducing test application time and test storage requirements of the tester. This is especially
important for scan-based circuits as the test application time for such circuits is directly
proportional to the test set size and number of flip-flops used in the scan chain.
3.4 Test Set Compaction
The test minimization problem for combinational circuits has been proven to be NP-
complete [51, 34]. Most ATPGs are not concerned with generating minimal test sets, as test
27
2 3 4 5
6 7 8 9 10
11
1
Figure 3.4: Multiple Maximum Cliques in the Independence Graph of Figure 3.2
generation is in itself computationally difficult. Thus ATPGs adopt a localized approach
by targeting a single fault and generating a test vector for that fault. So heuristic methods
based on compaction algorithms are used to obtain a minimal test set.
There are two types of compaction techniques - static compaction and dynamic com-
paction.
3.4.1 Static Compaction
Static compaction, also known as post-generation compaction [17], techniques are used
to compact a given test set. Static compaction techniques work only with already generated
test vectors. Hence these techniques are usually independent of the test generation process.
Several static compaction algorithms based on different heuristics exist in the literature and
are discussed next.
28
One of the most popular static compaction techniques is reverse order fault simula-
tion [72], where the generated test vectors are simulated in the reverse order, hoping to
eliminate some of the initially generated vectors. This method is very effective because the
normal test generation often starts with a random phase, where random vectors are simu-
lated until no new faults are being detected and then a deterministic ATPG phase begins,
where fault-specific vectors are generated. This is done so that the test pattern generation
effort is not wasted on the easy to detect faults that can be detected by random vectors. The
random vector generation phase is one of the main sources of redundant test vectors. Fault
simulation of the test vectors in the reverse order removes most of the initially generated
random vectors, which are made redundant by the deterministic vectors.
Another static compaction technique is described by Goel and Rosales [37], where
pairs of compatible test vectors, that do not conflict in their specified (0, 1) values, are
repeatedly merged into single vectors. This method is suitable only for patterns in which
the unassigned inputs are left as don?t care (X) by the ATPG program. Also, the compacted
test set will vary depending on the order in which vectors are compacted. One drawback of
this technique is that little reduction in test set size can be achieved for a highly incompatible
test set.
The paper [45] describes a test ordering technique called double detection which com-
bines static and dynamic compaction. In this technique, during test generation a fault is
not dropped from the fault list until it is detected twice. Each vector is assigned a variable
to keep a count of the number of faults it uniquely detects. At the end of the test generation
if a vector has a count 0 it means that all the faults detected by it are also detected by
29
other vectors. But this does not mean that the vector is redundant, because it may be-
come an essential vector for a fault on eliminating some other vector after fault simulation.
Fault simulation is performed during which all vectors with non-zero counts are simulated
first, followed by the vectors with zero counts in the reverse order. This time many vectors
with 0 counts become redundant, i.e., those that do not detect any new fault, and can be
eliminated.
In all of the techniques described above, the size of the compacted test set depends on
the order in which the vectors are compacted. One static compaction technique in which
the order of vectors does not influence the final compacted test set size is the integer linear
programming (ILP) method called the Test Minimization ILP [29]. The test minimization
ILP gives the most compact test set possible for the given test set. However, it should be
noted that the complexity of the ILP is exponential. Other linear programming (LP) based
techniques like recursive rounding [48] that have polynomial time complexity can be used
to obtain a close to optimum test set. The work presented in this thesis makes extensive
use of the test minimization ILP along with recursive rounding. The test minimization ILP
is described in the next chapter and the details of the recursive rounding technique can be
found in Appendix A.
One of the main advantages of static compaction is that no modification of the ATPG is
needed, as it is independent of the test generation process. Though static compaction adds
to the test generation time, this time is usually small compared to the total test generation
time. However optimal static compaction algorithms are impractical, so heuristic algorithms
are used. Static compaction can also be used after dynamic compaction to further compact
the test sets.
30
3.4.2 Dynamic Compaction
In the literature techniques that attempt to reduce the number of test vectors during
test generation have been classified as dynamic compaction techniques. There are some
other techniques in literature classified as static which work after test generation and signif-
icantly modify or replace previously generated vectors based on the fault simulation infor-
mation. We have classified such techniques as dynamic. Thus there are two sub categories
of dynamic compaction.
Dynamic Compaction during Test Generation
Dynamic compaction techniques under this category attempt to reduce the number of
test vectors while they are being generated. These techniques require modifications in the
test generation process and algorithms. The key idea of compaction during test generation
is that if the fault coverage of each test pattern is maximized during test generation, then
the total number of patterns can be reduced.
The first dynamic compaction procedure was proposed by Goel and Rosales [37] in
which every partially specified test vector is processed immediately after its generation
by trying to use only the unspecified inputs in the test vector to derive a test to detect
additional faults by the same vector.
Akers and Krishnamurthy were the first to present test generation and compaction
techniques based on independent faults [7]. As the minimum test set size cannot be smaller
than the size of the largest independent fault set (IFS), the tests for independent faults
can be considered necessary. For every fault in a maximal IFS, partially specified tests are
found using the test value propagation technique. Each partially specified test also gives
31
information on which other faults can be potentially detected by it. This process is repeated
for a different maximal IFS. While each pair of faults within an IFS requires separate tests,
there is a definite possibility that a pair of faults from different IFSs can be detected by a
single test. Thus a fault matching procedure was used to find sets of compatible faults, i.e.,
faults that can be detected by a single test vector, from the independent fault sets. The
authors suggested that the information on compatible fault sets and independent fault sets
could be used to decide the order of faults to be targeted during test generation. Thus these
techniques could be used as a pre-processing step to the test generation step. However they
did not provide any specific technique for fault ordering. Results for benchmark circuits are
also not given. Though this paper did not provide any results, it became the basis for later
work on independent faults.
COMPACTEST [59] was the first technique to make use of independent faults for fault
ordering. The target faults are ordered such that the faults present in largest maximum
independent fault sets (MIFS) appear at the beginning of the fault list. Later Kajihara
et al. [45] proposed dynamic fault ordering which is an enhancement of the fault ordering
technique of COMPACTEST. Here the fault list is reordered whenever a test is generated.
The independent fault set with largest number of undetected faults at that point is put at
the beginning of the fault list.
The ?double detection algorithm? [45] described earlier in the section on static com-
paction is also a dynamic compaction technique. Here the processing done during test
generation falls under the dynamic compaction category.
A redundant vector elimination (RVE) algorithm, which identifies redundant vectors
during test generation and dynamically drops them from the test set, was developed by
32
Hamzaoglu and Patel [38]. The RVE algorithm fault simulates all the faults in the fault list
except the ones that are proven to be untestable, and it keeps track of the faults detected
by each vector, the number of essential faults of each vector and the number of times a fault
is detected. The essential faults of a vector are those that cannot be detected by any other
vector in the vector set [17, 45]. During test generation if the number of essential faults of
a vector reduces to zero, i.e. the vector becomes redundant, and it is dropped from the test
set. The compaction results of RVE algorithm were similar to those of the double detection
algorithm of [45].
Another recent work on dynamic compaction involves independence fault collapsing [25,
23] and concurrent test generation [24, 23], which collapses faults into groups based on
independence relation, and then for each group tries to generate either a single vector, or
as few vectors as possible, which can detect all faults in that group. In the independence
fault collapsing algorithm an independence graph is constructed for a dominance collapsed
fault set. In such a graph the absence of an edge between two nodes indicates that the
corresponding two faults are concurrently testable. Thus two nodes that are not connected
by an independence edge can form a single node whose label combines the fault labels of both
nodes. Then, all nodes that had edges connecting to the two nodes will have edges to the
combined node. This collapsing procedure ends when the graph becomes fully-connected.
However, depending on the order in which the nodes are collapsed the size of the collapsed
graph can vary. Thus the collapsing of faults in the independence graph is done using
metrics - degree of independence defined for every fault and similarity metric defined for
every pair of faults. This algorithm groups faults into nodes such that the similarity metrics
among faults within each group are minimized. This increases the possibility of finding a
33
single concurrent test for the group. Concurrent test generation technique is used to find
a single or as few test vectors as possible to detect all faults in each group. However these
two techniques were very computationally intensive and could not provide optimum results.
Dynamic Compaction after Test Generation
Compaction methods under this category are mainly based on essential fault pruning,
and have been classified in the literature as static techniques as they are applied after the
test generation process. But, we will consider them as dynamic techniques as the test
vectors are modified or even replaced by new vectors during the compaction process. The
main advantage of the dynamic compaction techniques in this category is that the level of
compaction achievable is not dependent on the quality of the original test set, as opposed
to static compaction.
Chang and Lin [17] proposed the forced pair-merging algorithm which involves mod-
ification of one vector to cover the essential faults of another vector. The essential faults
of a vector are those that cannot be detected by any other vector in the vector set. For
a vector say t1, as many specified (0s and 1s) bits as possible are replaced with Xs such
that the vector still detects its essential faults. Then, for each of the remaining vectors,
say t2, the algorithm tries to change the bits that are incompatible with the new t1 to Xs.
If the process succeeds, the pair is merged into a single vector. The authors also propose
essential fault pruning (EFP) method to achieve further compaction by removing a vector
by modifying other vectors of the test set to detect all the essential faults of the target
vector. A limitation of this method is its narrow view of the problem; it is not possible to
remove all the essential faults of a vector.
34
Kajihara, et al. give the essential fault extraction (EFE) algorithm in [44]. The EFE
is similar to EFP, wherein instead of modifying existing vectors, new vectors are generated
by targeting essential faults. The authors also propose the Two-by-one algorithm in which
addition of a new test vector removes two other vectors in a given test set. After determin-
imng two tests to be removed the essential faults of these vectors are used as target faults
for the vector to be added.
In [39] the essential fault reduction (EFR) algorithm [39] is proposed which is an im-
proved version of the EFP method of [17]. EFR uses a multiple target test generation
(MTTG) procedure [17, 45] to generate a test vector that will detect a given set of faults.
The EFR algorithm makes use of the independence (incompatibility) graph to decide which
faults in a vector can be pruned through detection by another vector. The EFR algorithm,
redundant vector elimination (RVE) algorithm described in the previous sub-section, along
with dynamic compaction [37] and a heuristic for estimating the lower bound are incor-
porated into an advanced ATPG system for combinational circuits, and is called MinTest.
MinTest produced some of the smallest reported single-detect test sets for the ISCAS85 [12]
and ISCAS89 [11] (scan versions) benchmark circuits. However this technique was compu-
tationally expensive.
3.5 Methods of Finding Maximal IFS
The importance of independent fault sets (IFS) in the reduction of test set size has
been established in the previous sections. We also saw that the largest IFS provides a lower
bound on the test set size. This lower bound can be closely achieved by selecting tests from
the test vectors derived for the faults in the IFS [7, 8]. However, the problem of finding the
35
largest IFS is complex, and heuristics have to be used to find a maximal independent fault
set.
Akers and Krishnamurthy [7] were the first to describe the derivation of maximal IFS
from a set of faults within a given circuit by combining the notions of fault dominance and
fault independence. For a given circuit their procedure involved finding dominance and
independence relations among faults for primitive gates forming the circuit. Then use the
transitive property of fault dominance to find additional dominance relations among faults
in the entire circuit. The transitive property of fault dominance is, if a fault f1 dominates
f2 and f2 in turn dominates f3, then f1 dominates f3. They then create a graph with
undirected edges between nodes representing the independence relations between faults of
the primitive gates of the circuit. The authors give a theorem stating that if fault f1
dominates f2, f3 dominates f4, and f1 and f3 are independent then f2 and f4 are also
independent. Using this theorem, additional edges are added to the graph. In the final graph
a maximal clique gives the maximal IFS. It was here that the notion of an independent fault
graph was first introduced, though the term ?independence fault graph? was not used.
In the paper by Tromp [76] a maximal independent fault set was found using a graph,
constructed based on necessary assignments [64] of all faults. Necessary assignments are
line values that must be set for a fault to be detected. There is an edge between two nodes
in the graph, if the necessary assignments of the faults corresponding to the nodes have
conflicting values, implying the faults are independent. A maximal IFS was found as a
maximal clique in the graph. The main problem with this technique is that it has high
computational complexity, as all pairs of faults have to be considered, and then a maximal
clique problem has to be solved over all pairs of faults. The paper [60] gives an improved
36
technique to compute independent fault sets based on necessary assignments. It allows
construction of an IFS incrementally, thus resulting in reduced computational complexity.
In the paper on COMPACTEST [59], due to the complexity of computing independent
faults sets for the entire circuit, independent faults sets are computed only within maximal
fanout free regions using a labeling procedure. It also shows that the IFS for a fanout free
region is also the IFS for the complete circuit.
Kajihara, et al. [45] give an improved method to find the necessary assignments uti-
lizing static learning [31] and unique sensitization [31, 72]. The use of these techniques
increases the number of necessary assignments, thereby increasing the potential to compute
larger maximal IFS. Heuristics are used to store the necessary assignments efficiently and
to simplify the identification process for independence of two faults.
In [39] a minimum test set size (MTSS) estimation technique is given to find lower
bounds on test set sizes. As the size of maximal IFS gives the lower bound on the test set
size, it computes the maximal IFS by finding the maximal clique in the independence graph
initially only for essential faults and then enlarging this clique by considering other faults.
37
Chapter 4
Minimal Test Generation using Primal-dual ILP Algorithm
In the previous chapters we saw that the size of the largest IFS gives a lower bound
on the test set size. This lower bound can be closely achieved by selecting tests from the
test vectors derived for the faults in the IFS. This chapter describes the formulation of a
dual ILP whose solution gives the largest IFS. The dual ILP is obtained by treating the
test minimization ILP as the primal problem. The latter part of this chapter gives the
primal-dual ILP based algorithm for generating a minimal detection test set, followed by
the results of the algorithm.
4.1 Test Minimization ILP
The Test Minimization ILP [29] falls under the category of static compaction as ex-
plained in Section 3.4.1. It is an exact solution to the problem of creating a minimum
detection test set. The level of compaction achievable by this method is conditional to the
original unoptimized test set. Thus, an absolute minimum test set for a circuit would be
given by the test minimization ILP solution if we start with the exhaustive vector set for
that circuit.
Suppose a combinational circuit has K faults. We are given a vector set V of J vectors
and we assign a [0, 1] integer variable vj , j = 1, 2, . . . , J to each vector. Without loss
of generality, we assume that all K faults are detected by these vectors. Our problem then
is to find the smallest subset of these vectors that detects all faults. The variables vj have
the following meaning:
38
? If vj = 1, then vector j is included in the selected vector set.
? If vj = 0, then vector j is discarded.
Fault Vector number (j)
number (k) 1 2 3 4 . . . . . J
1 0 1 1 0 . . . . . 1
2 0 0 1 0 . . . . . 1
3 1 0 0 1 . . . . . 0
4 0 1 0 0 . . . . . 0
. . . . . . . . . . .
. . . . . . . . . . .
K 1 1 0 0 . . . . . 1
Figure 4.1: Detection Matrix akj.
We simulate the fault set and the vector set without dropping faults. The result is
represented as a detection table (matrix) of 0s and 1s, shown in Figure 4.1. In this matrix,
an element akj = 1 only if fault k is detected by vector j.
The test minimization ILP problem is stated as,
Minimize
Jsummationdisplay
j=1
vj (4.1)
subject to,
Jsummationdisplay
j=1
vj akj ? 1; for k = 1,2,...,K (4.2)
39
vj ? integer[0,1], j = 1,...,J (4.3)
The constraint set given by equation (4.2) ensures that the kth fault is detected by
at least one vector in the selected vector set. The fact that we start with a vector set V
that detects all faults in the set F and the direction of inequality in constraints that allow
us to set any or all vj?s to 1, guarantee the existence of a solution [26, 47]. Additionally,
the provable ability of the ILP to find the optimum, provided its execution is allowed to
complete, and the minimum requirement of 1 for every constraint guarantees the smallest
size test set.
4.2 Dual ILP
Treating the test minimization ILP problem described in the previous section as the
primal, we formulate another ILP called the dual ILP to obtain the largest IFS.
Suppose a combinational circuit has K faults. We are given a vector set V of J vectors.
Without loss of generality, we assume that all K faults are detected by these vectors. Recall
that in the test minimization ILP we had assigned a [0, 1] integer variable vj to vector j.
For the dual problem we assign a [0, 1] integer variable fk , k = 1, 2, . . . , K to each fault.
The dual ILP is stated as,
Maximize
Ksummationdisplay
k=1
fk (4.4)
40
subject to,
Ksummationdisplay
k=1
fk akj ? 1; for j = 1,2,...,J (4.5)
fk ? integer[0,1], k = 1,...,K (4.6)
akj is the element of the detection matrix obtained by fault simualtion without fault
dropping as described in the previous section. Because a solution to the primal test min-
imization problem specified by equations (4.1), (4.2) and (4.3) exists, according to the
duality theorem [75], a solution of the dual fault set maximization problem given by equa-
tions (4.4), (4.5) and (4.6) must also exist. We interpret this solution as a fault set, which
contains fault k only if fk = 1. We show that the dual solution provides an independent
fault set.
Definition 1: We define a pair of faults that is detectable by a vector set V to be
conditionally independent with respect to a vector set V if no vector in the set detects both
faults.
In comparison, therefore, the conventional fault independence as defined in the litera-
ture [7, 8] would mean ?absolute? independence that is conditional to the exhaustive vector
set with an additional implication that the faults are irredundant. In a similar way, con-
ditional equivalence, conditional dominance, conditional compatibility or concurrence can
be defined with respect to a vector set. Each definition will then become ?absolute?, as
41
defined in the literature [24, 25], when the vector set becomes exhaustive and the faults are
irredundant.
Definition 2: For a given vector set, a subset of all detectable faults in which no pair
of faults can be detected by the same vector, is called a conditionally independent fault set
(CIFS).
Theorem 1 A solution of the dual ILP of equations (4.4), (4.5) and (4.6) provides a largest
conditionally independent fault set (CIFS) with respect to the vector set V.
Proof: The jth constraint of the constraint set 4.5 consists of fault variables corre-
sponding to non-zero akj , i.e., faults detectable by jth vector. It allows only one of those
faults to be selected since no more than a single fk can be set to 1 in any inequality. Sup-
pose, we set fk = 1. Then, constraint inequalities of all other vectors that also detect the
kth fault will be violated if any other fault detectable by them was selected. Hence, setting
of fk = 1 ensures that no fault that is conditionally compatible with kth fault with respect
to vector set V can be selected. This guarantees that the selected set of faults will only
contain faults that are conditionally independent with respect to V.
The other part of theorem, i.e., the selected conditionally independent fault set is
largest, follows from the provable ability of ILP in finding the optimum solution if one exists.
Existence of a solution is guaranteed from the duality theorem [75], combined with the fact
that a solution of the primal test minimization problem exists. Note that the optimality
of the solution will lead to the largest fault set because the objective function 4.4 requires
maximization.
Theorem 2 For a combinational circuit, suppose V1 and V2 are two vector sets such
that V1 ? V2 and V1 detects all detectable faults of the circuit. If CIFS(V1) and
42
CIFS(V2) are the largest CIFS with respect to V1 and V2, respectively, then |CIFS(V1)| ?
|CIFS(V2)|.
Proof: Let G1(U,E1) be the independence graph of the circuit under consideration,
where U is the vertex set and E1 the edge set. Each vertex in an independence graph
represents a fault, and the presence of an edge between any two vertices indicates that the
corresponding faults are independent. The independence relations among vertices in graph
G1 have been determined by the vector set V1. Thus, CIFS(V1) is a maximum clique in
the graph G1 and |CIFS(V1)| is the clique number of G1. A maximum clique is a clique
of largest size and the clique number of a graph is defined as the number of vertices in a
maximum clique.
Consider a vector set V2 such that V1 ? V2. Let G2(U,E2) be the independence
graph relative to the vector set V2. Thus, CIFS(V2) is a maximum clique in G2, and
|CIFS(V2)| is the clique number of G2. U is the vertex set and E2 is the edge set of G2.
The vectors in the set V2?V1 can only invalidate the independence relations which
were determined by the vector set V1, but cannot determine new independence relations
among the faults. Thus the edges in graph G1 either remain unchanged or some may be
deleted because of the vector set V2, but no new edge can be added to graph G1.
Note that a graph may have several maximum cliques. As no new edge is added to
G1, the clique number cannot increase. If an edge is removed such that it was contained
in every maximum clique, its removal modifies all these cliques, decreasing their clique
numbers. Removing an edge from a clique of m vertices still leaves two cliques of m ? 1
vertices each. If there is at least one maximum clique from which no edge is removed, then
that clique will remain unchanged and clique number will not decrease. Thus, removal
43
of an edge cannot increase the clique number and can only decrease it by 1. This is a
well-understood result in graph theory.
Theorem 2 implies that the largest CIFS should monotonically converge to the absolute
IFS as more vectors are added to an initial vector set. In addition, the augmented vector
set will contain multiple tests for each fault of the IFS. This would enhance the capability
of the primal ILP to select the ?right? vector for each IFS fault such that all faults are
covered. Note that one vector per IFS fault is the best we can do.
4.3 A Primal-Dual ILP Algorithm
An absolute minimal test set would be given by the primal solution of Section 4.1 if
we start with the exhaustive vector set. For large number of primary inputs (PIs), that is
impractical. Even for a moderate number of PIs, the solution becomes costly because of the
exponential complexity of ILP [75]. In an alternative approach, we start with any vector
set and then find a conditionally independent fault set (CIFS) by solving the dual problem
stated in Section 4.2. In this process, we solve the dual ILP iteratively by generating
multiple-detect tests generated only for the CIFS. Once, the CIFS is sufficiently converged,
we solve the primal ILP to get a minimal vector set. This method belongs to the dynamic
test minimization category, where test generation and minimization are done interactively.
The primal-dual ILP algorithm for minimal detection test set generation consists of
the following steps:
1. Generate an initial vector set: We used the ATPG program ATALANTA [56] but
any other program can be used. In general, for combinational circuits close to 100%
coverage is obtained. In terms of the number of vectors, this set is non-optimal and
44
may contain many more vectors than the final minimized set. Some redundant faults
are identified and a few others are left undetected due to time or backtrack limits.
Both categories are removed from the fault set to obtain a target fault set.
2. Obtain detection matrix: A fault simulator simulates the initial vector set for the
target fault set without fault dropping. We used the HOPE [57] program. Thus, the
akj, matrix of [0, 1] elements shown in Figure 4.1 is obtained.
3. Solve dual ILP to determine CIFS: Set up the dual ILP of (4.4), (4.5) and (4.6).
Obtain a solution using an ILP solver. We used the AMPL package [30]. In order to
make this step time efficient, we set a time limit on the dual ILP.
4. Generate tests for CIFS: We generate N-detect tests only for the faults in the CIFS
and augment the existing vector set with these vectors. We used ATALANTA to
generate 5-detect vectors for the CIFS.
5. Compact CIFS: Repeat steps 2 through 4 until the size of CIFS converges.
6. Solve primal ILP for final vector set: Set up the primal ILP of (4.1), (4.2) and (4.3)
for all accumulated vectors. Solve to obtain the final set of vectors.
4.4 Results
Results of step 1 are given in Table 4.1. The total faults are equivalence collapsed
single stuck-at faults. All CPU times are for a SUN Fire 280R 900MHz Dual Core machine.
These times are for ATPG by ATALANTA [56]. Some faults were identified as redundant
and some others were not detected due to per fault limits used in the program. Both
were removed from the fault list to obtain a target fault list. The ATPG vector set and
45
target fault list whose sized are shown in Table 4.1 were used in the subsequent steps of the
primal-dual algorithm. Next, we examine the iterations of the dual-ILP for two examples.
Table 4.1: Four-bit ALU and Benchmark Circuits - Initial ATPG Vectors and Target Fault
Set.
Circuit Circuit Primary No. of Total ATPG Fault Redund. Target
name function [40] inputs gates faults vectors coverage faults fault set
4-b ALU 4-bit ALU 14 78 237 35 100% 0 237
c17 - 5 6 22 10 100% 0 22
27-channel
c432 interrupt 36 120 524 79 99.24% 1+31 520
controller
c499 32-bit SEC2 41 162 758 67 99.24% 8 750
circuit
c880 8-bit ALU 60 320 942 109 100% 0 942
c1355 32-bit SEC2 41 506 1574 114 99.49% 8 1566
circuit
c1908 16-bit SEC2/ 33 603 1879 183 99.52% 2+71 1870
DED2 circuit
c2670 12-bit ALU & 233 872 2747 194 95.74% 86+311 2630
controller
c3540 8-bit ALU 50 1179 3428 245 96.01% 137 3291
c5315 9-bit ALU 215 1726 5350 215 98.90% 56 5291
c6288 16 x 16 32 2384 7744 54 99.56% 34 7710
multiplier
c7552 32-bit adder/ 207 2636 7550 361 98.25% 77+541 7419
comparator
1ATPG runs terminated due to per fault backtrack or CPU time limit
2SEC and DED stand for ?Single-Error-Correcting? and ?Double-Error Detecting?
4.4.1 Example 1: c1355
The benchmark circuit c1355 has 41 primary inputs and 506 gates. Of the total of 1574
faults, eight are found to be redundant, giving us a target set of 1566 faults. These faults
are covered by an initial ATPG generated set of 114 vectors. The size of CIFS converges
to 84 in three iterations as shown in Table 4.2. This is a case where the iterations converge
quickly. At the end of the third iteration a total of 903 vectors were accumulated. The
46
primal ILP selected exactly one vector per fault, giving a final set of 84 vectors. Considering
the published data on IFS [39, 45], this is the smallest possible test set. The results are
shown in Table 4.2.
Table 4.2: Example 1: Dual ILP Iterations and Primal ILP Solution for c1355.
Primal Iteration No. of ATPG Fault Sim. CIFS No. of min. ILP
or dual number vectors CPU s CPU s Size vectors CPU s
1 114 0.033 0.333 85 0.24
Dual 2 507 0.085 1.517 84 0.97
3 903 0.085 2.683 84 1.91
Primal 903 84 3.38
4.4.2 Example 2: c2670
The benchmark circuit c2670 has 233 primary inputs and 872 gates. Of the total of
2747 faults, 86 are found to be redundant and 31 undetectable, giving us a target set of
2630 faults. These faults are covered by an initial ATPG generated set of 194 vectors. The
size of CIFS converges to a stable value of 70 in 12 iterations as shown in Table 4.3. This
is a case where the iterations do not converge quickly. At the end of the twelfth iteration a
total of 4200 vectors were accumulated. Even though this CIFS is larger than the published
results on IFS [39, 45], further iterations were suspended because the last three iterations
did not provide any reduction. The primal ILP selected exactly one vector per fault, giving
a final set of 70 vectors. Considering the published data on IFS [39, 45], this is not the
smallest possible test set, which might be more expensive to find. The results are shown
in Table 4.3. In this example, the size of CIFS is strongly dependent on the vector subset.
It indicates that we should explore different strategies for generating vectors for the dual
problem.
47
Table 4.3: Example 2: Dual ILP Iterations and Primal ILP Solution for c2670.
Primal Iteration No. of ATPG Fault Sim. CIFS No. of min. ILP
or dual number vectors CPU s CPU s Size vectors CPU s
1 194 2.167 3.670 102 1.99
2 684 1.258 5.690 82 3.22
3 1039 1.176 6.895 79 7.90
4 1424 1.168 8.683 78 3.69
5 1738 1.136 10.467 76 5.89
Dual 6 2111 1.128 12.333 76 7.43
7 2479 1.112 14.183 74 7.16
8 2836 1.086 15.933 73 8.45
9 3192 1.073 17.717 72 9.81
10 3537 1.033 19.267 70 10.90
11 3870 1.048 20.983 70 12.02
12 4200 1.033 22.600 70 13.44
Primal 4200 70 316.52
4.5 Benchmark Results
Benchmark circuit results obtained for the primal-dual ILP algorithm are summarized
in Table 4.4. The column Initial vectors gives number of vectors in the initial ATPG
generated test set. The column Final vectors gives the number of vectors accumulated after
dual ILP iterations. The next column gives the total CPU time taken for all the ATPG runs
and fault simulations performed during the dual ILP iterations. Recall that fault simulation
is required in every iteration of the dual ILP to generate the detection matrix needed for
ILP runs. The next three columns under the Dual-ILP Solution tab give the number of
dual ILP iterations, the final CIFS size obtained after the last dual ILP iteration, and the
CPU time for these iterations. The two columns under the Primal-ILP Solution tab give
the number of vectors in the minimized test set obtained as a solution to the primal ILP
and the CPU time for the primal ILP run. Here it can be seen that for larger benchmark
circuits the primal ILP runs are incomplete, and also the time taken by a single primal-ILP
48
Table 4.4: Test Sets Obtained by Primal-Dual ILP for 4bit ALU and Benchmark Circuits.
ATPG and Dual-ILP Primal-ILP solution
Circuit fault simulation solution with time-limit
Name Initial Final CPU No. of CIFS CPU Minimized CPU
vectors vectors s iterations size s vectors s
4b ALU 35 270 0.36 5 12 1.23 12 0.78
c17 5 6 0.03 2 4 0.07 4 0.03
c432 79 2036 1.9 13 27 25.04 30 2.2
c499 67 705 2.41 4 52 2.33 52 1.08
c880 109 1384 4.11 15 13 635.39 24 1001.06*
c1355 114 903 2.89 3 84 1.21 84 3.38
c1908 183 1479 7 4 106 10.79 106 19.47
c2670 194 4200 34.85 12 70 91.9 70 316.52
c3540 245 3969 24.76 9 84 622.09 104 1007.74*
c5315 215 1295 13.83 5 39 510.82 71 1004.51*
c6288 54 361 10.03 6 6 311.03 16 1004.3*
c7552 361 4929 114 8 116 287.65 127 1015.06*
*Execution terminated due to a time limit of 1000 s
run is greater than the total time for the multiple dual ILP runs. Thus the computational
complexity of the dual ILP is much lesser than that of the primal ILP.
To examine the benefit of the primal-dual ILP over the plain (primal) ILP, we compare
the results of Table 4.4 with those in the literature [47]. In that work, ILP was used to
minimize large vector sets that were generated for N-detection. In some cases values of N
were greater than 100 resulting in large vector sets and therefore large numbers of variables
in ILP. That comparison is shown in Table 4.5. The principal benefit of the dual problem
appears to be in reducing the vector set size, which saves ATPG and fault simulation time,
as well as the ILP CPU time. It is also evident that the dual ILP takes much less CPU time
than the primal ILP. Hence, the use of the dual ILP in the iterative loop is appropriate,
while the primal ILP is used only once. Also, note that after the initial ATPG run that
includes all faults, all subsequent runs only work on CIFS that is much smaller.
49
Table 4.5: Comparing Primal-Dual ILP Solution With ILP-Alone Solution [47].
Circuit Lower bound ILP-alone minimization [47] Primal-dual minimization [this work]
Name on vectors Unopt. LP Minimized Unopt. Total Minimized
[39, 45] vectors CPU s vectors vectors CPU s vectors
4b ALU 12 2370 5.19 12 270 2.01 12
c432 27 14822 82.3 27 2036 27.24 30
c499 52 397 5.3 52 705 3.41 52
c880 13 3042 306.8 25 1812 1636.45* 24
c1355 84 755 16.7 84 903 4.59 84
c1908 106 2088 97 106 1479 30.26 106
c2670 44 8767 1568.6* 71 4200 408.42 70
c3540 78 - - - 3969 1629.83* 104
c5315 37 - - - 1295 1515.53* 71
c6288 6 243 519.7 18 361 1315.33* 16
c7552 65 2156 1530.0* 148 4929 1302.71* 127
*ILP execution was terminated due to a CPU time limit
Note: Both experiments were performed on SUN Fire 280R, 900 MHz Dual Core machine
4.6 Primal LP with Recursive Rounding
Due to the high computational complexity of the primal ILP, we transform it into a
linear program by treating the variables as real numbers in the range [0.0, 1.0]. We then
use the recursive rounding technique [48] to round off the real variables to integers. In the
recursive rounding method, the LP is recursively used, each time rounding off the largest
variable to 1 and reducing the size of the LP. This is done until an integer solution is
obtained. This is a polynomial time solution, but an absolute optimality is not guaranteed.
Table 4.6 gives test set sizes and CPU times for the primal-dual test minimization
method. Observe that the test sets obtained from the primal LP with recursive rounding
are smaller than those obtained by primal ILP (Table 4.4) for cases in which the primal ILP
gave suboptimal solution due to CPU time limited termination. Thus using primal LP with
recursive rounding is a good trade-off between optimality and computational complexity.
50
Table 4.6: Test Sets Obtained by Primal LP-Dual ILP Solution for 4bit ALU and Bench-
mark Circuits.
Number of Dual-ILP solution Primal-LP solution Total
Circuit unoptimized with recursive rounding CPU
Name vectors No. of CIFS CPU Minimized CPU s
iterations size s vectors s
4b ALU 270 5 12 1.23 12 0.63 1.86
c17 6 2 4 0.07 4 0.03 0.1
c432 2036 13 27 25.04 30 1.14 27.28
c499 705 4 52 2.33 52 0.43 3.41
c880 1384 15 13 635.39 24 19.42 654.81
c1355 903 3 84 1.21 84 0.82 4.59
c1908 1479 4 106 10.79 107 0.38 30.26
c2670 4200 12 70 91.9 70 10.73 102.3
c3540 3969 9 84 622.09 95 99.75 721.84
c5315 1295 5 39 510.82 63 298.5 809.32
c6288 361 6 6 311.03 16 44.77 355.8
c7552 4929 8 116 287.65 119 160.57 448.22
The graphs in Figures 4.2 and 4.3 give the comparison between primal LP-dual ILP
solution with Primal ILP-dual ILP solution. They illustrate the benefit of using the primal
LP over the primal ILP. The total CPU time for primal LP-dual ILP solution is significantly
lesser than the Primal ILP-dual ILP solution, whereas the test set sizes obtained are almost
similar for the two techniques.
Table 4.7 compares primal LP-dual ILP solution with the ILP-alone solution (recursive
LP version) [48] for almost similar unoptimized vector set sizes. For this reason, some
minimized vector sets in the last column are larger than those shown in Tables 4.4, 4.5
and 4.6. For example, in Table 4.7 the circuit c2670 has 79 vectors obtained after minimizing
a set of 1039 vectors. All other tables show 70 vectors for this circuit obtained from a set
4200 vectors that was generated by the dual ILP solution (Table 4.3). This observation
is significant because the level of compaction obtainable from the primal LP is dependent
on the type of vectors in the original vector set on which it is run. It is evident that
51
0
200
400
600
800
1000
1200
1400
1600
1800
c432 c880 C1355 C1908 C2670 C3540 C5315 C6288 C7552
ISCAS85 Benchmark Circuits
CPU s
Primal-Dual ILP
Primal_LP-Dual_ILP
Figure 4.2: CPU Time Comparison Between Primal LP-Dual ILP Solution with Pri-
mal ILP-Dual ILP Solution.
the primal-dual minimization technique performs better than the ILP-alone minimization
technique. This confirms the role of the dual ILP in obtaining proper vectors, which then
can be optimized by the primal LP. Note that the basic idea here is to target faults that
belong to an independent fault set.
4.7 Analysis of Duality for Integer Linear Programs
The duality theorem defined in Section 2.12 is applicable to linear programs [75]. How-
ever the concept of duality in the case of integer linear programs is not well understood
as no specific results are found in the literature. In this section we attempt to establish a
relation between the optimized values of the primal ILP and dual ILP.
In the previous section, we had seen that the primal ILP due to its high computational
complexity was transformed into a relaxed primal LP and solved using the recursive round-
ing technique. This transformation was done by allowing the variables to take on real values
52
0
20
40
60
80
100
120
140
c17 c432 c499 c880 C1355 C1908 C2670 C3540 C5315 C6288 C7552
ISCAS85 Benchmark Circuits
Number of Vectors
Primal-Dual ILP
Primal LP - Dual ILP
Figure 4.3: Test Set Size Comparison Between Primal LP-Dual ILP Solution with Pri-
mal ILP-Dual ILP Solution.
in the range [0.0, 1.0]. Similarly, the dual ILP can also be transformed into a relaxed dual
LP problem. The Table 4.8 lists the optimized values for the objective functions obtained
from relaxed LP?s corresponding to both primal and dual ILP problems for the benchmark
circuits. Here the unoptimized vectors used were those shown in Tables 4.4 through 4.6,
and not those used for Table 4.7. The optimized values of the relaxed primal LP and the
relaxed dual LP are equal, which is in accordance with the duality theorem [75]. These
values are listed in the second column of Table 4.8.
It is also known that the optimized value of the objective function obtained from the
relaxed LP provides a bound for the parent ILP problem [46, 48]. Thus, the single value
obtained from primal and dual LP?s is an upper bound on the size of the conditional
independent fault set (CIFS) and is also a lower bound on the size of the minimized vector
53
Table 4.7: Comparing Primal LP-Dual ILP Solution with LP-Alone Solution [48].
Circuit Lower bound LP-alone minimization [48] Primal-dual minimization [this work]
Name on vectors Unopt. LP Minimized Unopt. Total Minimized
[39, 45] vectors CPU s vectors vectors CPU s vectors
c432 27 608 2 36 983 5.52 31
c499 52 379 1 52 221 1.35 52
c880 13 1023 31 28 1008 227.21 25
c1355 84 755 5 84 507 1.95 84
c1908 106 1055 8 107 728 2.5 107
c2670 44 959 9 84 1039 17.41 79
c3540 78 1971 197 105 2042 276.91 95
c5315 37 1079 464 72 1117 524.53 67
c6288 6 243 78 18 258 218.9 17
c7552 65 2165 151 145 2016 71.21 139
set. These bounds are expressed as follows:
Primal ILP objective ? Relaxed LP objective ? Dual ILP objective
Or
Minimized vector set size ? Relaxed LP objective ? Largest CIFS size
The data in Table 4.8 conforms to these inequalities. Because of the CPU time con-
straints, several primal ILP solutions (column 3) had to be obtained by the recursive round-
ing method [48]. These vector sets may be larger than the real optimum size that would be
possible if we could solve the ILP. Interestingly, in all such cases, the CIFS size (column 4)
is strictly lower than its upper bound. In most cases where the primal ILP was directly
solved, the CIFS size was equal to its upper bound.
54
Table 4.8: Comparison of Optimized Values of Relaxed LP and ILP.
Circuit Relaxed primal and Primal ILP Dual ILP
Name dual LP?s optimized objective finction objective function
objective functions (minimized vectors) (CIFS size)
4b-alu 12.00 12 12
c17 4.00 4 4
c432 29.06 30 27
c499 52.00 52 52
c880 19.53 24* 14
c1355 84.00 84 84
c1908 106.00 106 106
c2670 70.00 70 70
c3540 86.07 95* 84
c5315 52.63 63* 39
c6288 8.40 16* 6
c7552 116.00 119* 116
*LP based recursive rounding [48]
Observe that in column 2 of Table 4.8, several entries (4b-alu, c17, c499, c1355, c1908,
c2670, and c7552) have integer values. Notably, these are the only cases where the CIFS
sizes (column 4) exactly match the upper bounds. With the exception of c7552, for all
circuits in this category, the minimized vector set size matched the respective lower bound.
In fact, we found that in the relaxed LP solutions for these circuits (excepting c7552) all
variables assumed only integer (0 or 1) values. Thus, the relaxed LP solutions were also the
ILP solutions. In some of these cases, theoretical lower bounds on vectors (see Table 4.7)
is actually achieved. Circuit c2670 is an exception that perhaps requires more, or better,
vectors to select from.
55
Chapter 5
Background on Fault Diagnosis
In this chapter we will review the different types of fault diagnosis techniques with
an emphasis on fault dictionary based diagnosis. We will also review the common fault
dictionary organizations, and a few compaction techniques employed to manage the size of
the fault dictionary.
5.1 Fault Diagnosis
The concept of fault diagnosis was introduced in Chapter 2. Fault diagnosis involves
applying tests to failed chips and analyzing the test results to determine the nature of the
fault. The results of fault diagnosis are suspected defect locations which are used to guide
the physical analysis process for defect identification. Diagnosis algorithms are broadly
classified into two types - cause-effect fault diagnosis and effect-cause fault diagnosis.
5.1.1 Cause-Effect Diagnosis
The cause-effect diagnosis starts with a particular fault model and compares the sig-
nature of the observed faulty behavior with the simulated signatures for each fault in the
circuit. A fault signature is the data representation of the response of a defective circuit to
a diagnostic test set [55]. Basically it is a list of failing vectors and the outputs at which
errors are detected. A cause-effect algorithm can further be classified as static, in which all
fault simulation is done in advance and all fault signatures are stored as a fault dictionary
or, as dynamic, where no pre-computed information is used and simulations are performed
56
only as needed during the diagnosis process. The single stuck-at fault model has been the
most widely used fault model in the area of fault diagnosis too.
As the cause-effect algorithms are based on a fault model and actual defects on the chip
may not behave according to the fault model used, the observed signature may not match
with any of the simulated signatures. In such cases sophisticated matching algorithms are
used to select a set of signatures that best match the observed signature [53].
5.1.2 Effect-Cause Diagnosis
As the name suggests the effect-cause algorithm directly examines the syndrome of the
failing chip and then derives the fault candidates [1] using path-tracing methods. The fault
candidate here usually is a logical location or area of the chip. Some of the effect-cause
diagnosis algorithms are structural pruning [80], backtrace (functional pruning) [52], inject
and evaluate [62], etc. One important feature of effect-cause diagnosis algorithms is that
they can be constructed to handle cases of multiple faults in the failing chip. This is an
advantage over most other diagnosis strategies that rely heavily on a single-fault assumption.
The diagnosis results of effect-cause algorithms are usually pessimistic and imprecise.
5.2 Diagnosis Using Fault Dictionaries
Fault dictionary based diagnosis has been very popular as it facilitates faster diagnosis
by comparing the observed behaviors with pre-computed signatures in the dictionary. This
is especially significant where a large number of parts must be diagnosed. Also, since fault
simulation is performed as a part of test generation, most test generation programs can
57
create a fault dictionary. When a fault dictionary is used for diagnosis, each entry (signa-
ture) in the dictionary must be compared with the observed behavior during the diagnosis
process. The comparison can be accomplished by changing the format of dictionary entries
to match the observed behavior or vice-versa. The choice depends on the dictionary format.
Most of the previously published approaches have implied that the observed behavior will
be converted into the dictionary entry format [19].
The two most popular forms of dictionaries are the full-response dictionary and the
pass-fail dictionary.
5.2.1 Full-Response (FR) Dictionary
The full-response dictionary is the most detailed form of fault dictionary which can
provide all the diagnosis information for a given test set. It consists of all output responses
of each fault for each test. Thus this dictionary for a modeled fault can not only tell what
test fails but also at which outputs discrepancies are observed. The size of such a dictionary
would be (F ? V ? O), where F is the number of faults, V number of vectors, and O is
the number of outputs. Thus the size of such a dictionary can get prohibitively large for
modern circuits.
Example: Let us consider a circuit with 2 outputs having 8 faults that are detected
by 5 test vectors. The fault free responses of the 5 tests are given in Figure 5.1. The
full-response dictionary obtained by complete fault simulation is shown in Figure 5.2.
5.2.2 Pass-Fail (PF) Dictionary
The pass-fail dictionary is the most compact form of fault dictionary. It stores a single
pass or fail bit for a fault-vector pair. The size of such a dictionary would be (F?V), where
58
Fault free
Tests response
o1 o2
t1 1 1
t2 1 0
t3 0 1
t4 1 0
t5 0 0
Figure 5.1: Tests and Their Fault Free Responses.
Output Responses
Faults t1 t2 t3 t4 t5
f1 1 0 1 0 1 0 1 0 0 0
f2 1 1 1 1 1 0 1 1 1 0
f3 1 1 1 1 1 0 1 0 1 1
f4 0 1 0 1 0 0 0 1 0 0
f5 0 0 1 0 0 1 0 0 0 0
f6 0 0 1 0 0 1 1 0 0 0
f7 0 0 0 0 0 1 1 0 0 0
f8 0 0 1 0 1 0 1 0 1 0
Figure 5.2: Full-Response Fault Dictionary.
F is the number of faults, and V the number of vectors. Thus the size of a PF dictionary
is independent of the number of outputs of a circuit and is a lot smaller than the FR
dictionary. However, the disadvantage with pass-fail dictionaries is that since the failing
output information is ignored, faults that fail same set of tests but at different outputs
cannot be distinguished [54]. Thus pass-fail dictionaries are not commonly used for fault
diagnosis.
The pass-fail dictionary for the circuit in the example of the previous section is shown
in Figure 5.3. Here ?0? stands for pass and ?1? stands for fail.
59
t1 t2 t3 t4 t5
f1 1 0 1 0 0
f2 0 1 1 1 1
f3 0 1 1 0 1
f4 1 1 1 1 0
f5 1 0 0 1 0
f6 1 0 0 0 0
f7 1 1 0 0 0
f8 1 0 1 0 1
Figure 5.3: Pass-Fail Fault Dictionary.
5.3 Dictionary Compaction
There has been a lot of work done to reduce the size of the full-response dictio-
nary [19, 54, 61]. Most of these techniques concentrate on reducing the size by managing
the organization and encoding of the dictionary. Dictionary organization is the order and
content of the information. Basically it tells us what data is stored in the dictionary. Dic-
tionary encoding is the data representation format in the dictionary, i.e., how the data is
stored in the dictionary. An appropriate organization and encoding is essential in making
dictionary-based diagnosis practical for very large circuits.
On one extreme is the detailed FR dictionary that contains all the information to
diagnose every diagnosable fault and on the other extreme is the compact PF dictionary
that may not distinguish all the distinguishable faults. The compaction techniques search
for a dictionary in between these two dictionaries. They look for the smallest dictionary
that can give a diagnostic resolution of a FR dictionary.
Pomeranz and Reddy in [61] have given an algorithm by which sufficient amount of
information can be added to a pass-fail dictionary to obtain a resolution equal to the
resolution of the full-response dictionary. Their method uses a greedy algorithm to choose
columns from a full-response dictionary to augment a pass-fail dictionary.
60
Another popular method of compacting is to only record the failing output vectors.
Since it is unlikely that all faults will be detected by all tests, many output vectors will
be fault free. Therefore we can drop a lot of unnecessary information without sacrificing
the diagnostic resolution. Such a dictionary is called a detection dictionary. In its full
form, the detection dictionary contains all the information present in a FR dictionary. One
drawback of such a dictionary is that the structure becomes irregular, which inhibits the
encoding of the dictionary entries. This dictionary can be further compacted by sacrificing
the diagnostic resolution using a drop-on-K heuristic. A drop-on-K detection dictionary
is one where the number of detections for each fault is limited to K. Another variation of
drop-on-K is a drop-when-distinguished dictionary.
The paper by Higami et al. [41] describes an algorithm to compact the diagnostic vector
set used in a pass-fail dictionary, thereby reducing the dictionary size. The algorithm for
compaction is based on a set covering method. They use a fault distinguishing table (FDIST)
which contains information about fault pairs distinguished by each vector. However, since
the number of fault pairs is usually very large, a complete FDIST cannot be constructed
and stored. Thus they work with a partial FDIST which includes information only for a
subset of all possible fault pairs. Using the partial FDIST, a small number of vectors is
selected. Then fault simulation is performed for the selected vectors to see if the original
diagnostic resolution is achieved. If not another subset of fault pairs is selected and a
new partial FDIST is constructed for the newly selected fault pairs and additional test
vectors are selected. This process is repeated until all the distinguishable fault pairs are
distinguished. The paper does not describe the set covering method used in the algorithm.
And the algorithm is for a PF dictionary which is not commonly used due its low diagnostic
61
resolution. This was the only work on diagnostic vector set compaction that we could find
in the literature.
62
Chapter 6
Daignostic Test Set Minimization
In this chapter we give an Integer Linear Program (ILP) formulation to minimize
test sets for a full-response dictionary based diagnosis. The ILP formulation is an exact
solution and has high complexity in terms of number of constraints. Next, we introduce a
generalized fault independence relation to reduce the number of constraints in the diagnostic
ILP. Finally a two-phase method is proposed for generating a minimal diagnostic test set
from any given test set.
6.1 ILP for Diagnostic Test Set Minimization
In the previous chapter we had seen two ILP formulations - Primal ILP for minimizing
a detection test set and Dual ILP to find the largest IFS. Both of these use a fault detection
table which contains information about faults detected by each vector. The fault detection
table was obtained by fault simulation without fault dropping. Note that the information
in a fault detection table is similar to that in the pass-fail dictionary.
6.1.1 Fault Diagnostic Table for Diagnostic ILP
The ILP formulation for minimizing test sets used for full-response dictionary based
diagnosis will have to use a matrix which not only tells what tests detect which faults,
but also at which outputs the discrepancies were observed for each fault-test pair. For this
reason we use a fault diagnostic table. We illustrate the construction of a fault diagnostic
table with the following example.
63
Output Responses
Faults t1 t2 t3 t4 t5
f1 1 0 1 0 1 0 1 0 0 0
f2 1 1 1 1 1 0 1 1 0 0
f3 1 1 1 1 1 0 0 0 0 0
f4 0 1 0 1 0 0 0 1 0 0
f5 0 0 0 0 0 1 0 0 1 1
f6 0 0 0 0 0 1 0 0 0 0
f7 0 0 0 0 0 1 0 0 0 1
f8 0 0 1 0 1 0 1 0 0 0
Figure 6.1: Full-Response Fault Dictionary.
t1 t2 t3 t4 t5
f1 1 1 1 1 0
f2 2 2 1 2 0
f3 2 2 1 0 0
f4 3 3 0 3 0
f5 0 0 2 0 1
f6 0 0 2 0 0
f7 0 0 2 0 2
f8 0 1 1 1 0
Figure 6.2: Fault Diagnostic Table.
Let us consider a circuit with 2 outputs having 8 faults that are detected by 5 test
vectors. A sample full response dictionary for such a circuit is shown in the Figure 6.1.
Here ?0? stands for pass and ?1? stands for fail.
We use integers to represent the output response for each test vector. As faults de-
tected by different test vectors are already distinguished, there is no need to compare the
corresponding output responses. Hence we assign indices for the failing output responses for
each test vector. In the example, for test t1 the 3 different failing output responses (?10?,
?11?, and ?01?) are indexed by integers 1, 2, and 3, respectively, in the fault diagnostic
table as shown in Figure 6.2. The largest integer needed to index an output response in
the worst case is equal to minimum(2No. of output pins?1, highest number of faults detected
64
by any test vector). However it should be noted that output responses to a particular vector
are likely to repeat across a fault set as faults in the same output cone can have identical
output responses for a particular test. For this reason the largest integer needed to index
an output response observed in our experiments was much smaller than the highest number
of faults detected by any test vector.
6.1.2 Diagnostic ILP Formulation
Suppose a combinational circuit has K faults. We are given a vector set V of J vectors
and we assign a [0, 1] integer variable vj , j = 1, 2, . . . , J to each vector. The variables
vj have the following meaning:
? If vj = 1, then vector j is included in the selected vector set.
? If vj = 0, then vector j is discarded.
Without loss of generality, we assume that all K faults are detected by vector set V and
are also distinguishable from each other. Our problem then is to find the smallest subset of
these vectors that distinguish all the fault pairs. We simulate the fault set and the vector
set without dropping faults and the fault diagnostic table is constructed as explained in the
previous section. In this table, an element akj ? 1 only if fault k is detected by vector j.
The diagnostic ILP problem is stated as,
Minimize
Jsummationdisplay
j=1
vj (6.1)
subject to,
65
Jsummationdisplay
j=1
vj aij ? 1; for i = 1,2,...,K (6.2)
Jsummationdisplay
j=1
vj |akj ?apj| ? 1 (6.3)
for, k = 1,2,..,K ?1 and p = k + 1,..,K
vj ? integer[0,1], j = 1,...,J (6.4)
The constraint set given by equation (6.2) consists of K constraints - called detection
constraints, which ensure that every fault is detected by at least one vector. The constraint
set given by (6.3) consists of K(K ?1)/2 constraints - one constraint for every fault pair.
These are called the diagnostic constraints. A diagnostic constraint consists of vector vari-
ables corresponding to non-zero |akj ?apj|, i.e., the vectors that produce different output
responses for the kth and pth faults. It allows at least one of those vectors to be selected
since the inequality is greater than or equal to 1. Thus the diagnostic constraint set ensures
that kth fault is distinguished from the pth fault by at least one vector in the selected vector
set. Additionally, the provable ability of the ILP to find the optimum provided its execution
is allowed to complete guarantees the smallest size test set. Note that the total number of
constraints here is K(K+1)/2, which is proportional to the square of the number of faults.
66
t1 t2 t3 t4
f1 1 0 1 0
f2 1 1 0 0
f3 0 0 1 1
Figure 6.3: Fault Detection Table.
6.2 Generalized Fault Independence
One clear disadvantage of the diagnostic ILP is that the number of constraints is a
quadratic function of the number of faults. Thus for large circuits the number of con-
straints would be unmanageable. To overcome this, we define a relation between a pair of
faults which allows us to drop the diagnostic constraints in the ILP corresponding to such
fault pairs. We have generalized the conventional fault independence given in literature by
considering the detection of the faults at different outputs and relative to a vector set. In [7],
a pair of faults is called independent if the faults are not detected by a common vector. This
definition does not take into account the detection of the faults at specific outputs. Also
it implies ?absolute? independence, which is conditional to the exhaustive vector set. We
generalize the definition of fault independence by saying that two faults detected by the
same vector can still be called independent, provided the output responses of the two faults
to that vector are different
Definition 3: Generalized Fault Independence - A pair of faults detectable by a vector
set V are said to be independent with respect to vector set V, if there is no single vector that
detects both the faults and produces an identical output response.
Note that the generalized independence relation is conditional to a vector set.
Example: Consider a fault detection table with 3 faults and 4 test vectors as shown in
Figure 6.2. The independence relation between every fault pair is given in Table 6.2.
67
Table 6.1: Independence Relation.
Fault Independence Reason
pair relation
f1, f2 NO Both faults
detected by t1
f1, f3 NO Both faults
detected by t3
f2, f3 YES No vector detects
both faults
t1 t2 t3 t4
f1 1 0 1 0
f2 2 1 0 0
f3 0 0 1 1
Figure 6.4: Fault Diagnostic Table.
Table 6.2: Generalized Independence Relation.
Fault Generalized Reason
pair Indep. relation
Different output
f1, f2 YES responses for t1
detecting both faults
Identical output
f1, f3 NO responses for t3
detecting both faults
f2, f3 YES No vector detects
both faults
68
Table 6.3: Constraint Set Sizes.
No. of Initial No. of Final
Circuit Faults Constraint Diagnostic Constraint
Set Indep. Flt. Set
Pairs
4 alu 227 25,651 22,577 3,074
c17 22 231 170 61
c432 520 125,751 111,589 14,162
c499 750 271,953 138,255 133,698
c880 942 392,941 344,180 48,761
c1908 1870 1,308,153 1,201,705 106,448
Now consider a fault diagnostic table for the same set of faults and vectors as shown in
Figure 6.2. Recall that the fault diagnostic table takes into account the output responses
for each fault-vector pair. It is constructed as explained in Section 6.1.1. The generalized
independence relations for all pairs of faults are given in Table 6.2.
In the context of the diagnostic ILP, the generalized independence relation plays an
important role in reducing the number of constraints to be used in the formulation. When
two faults are independent, any vector that detects either of the faults will be a distinguish-
ing vector for the two faults. Thus, in the constraint set of equation (6.3), a constraint for
an independent fault pair will have vector variables corresponding to all the vectors that
detect any one or both the faults. In the presence of detection constraints of equation (6.2)
which guarantee a test for every fault, a diagnostic constraint for an independent fault
pair is redundant. Also, such a constraint will be covered by other diagnostic constraints
corresponding to non-independent fault pairs containing a fault from the independent fault
pair.
Table 6.3 shows the reduction in the constraint set sizes by considering generalized
independent faults for a 4 bit ALU and few ISCAS85 benchmark circuits.
69
It can be seen that there is an order of magnitude reduction in the constraint set sizes
on eliminating constraints corresponding to diagnostic independent faults. However the
constraint set sizes still are large and need to be reduced to manageable proportions. We
further address this problem in the next section.
6.3 Two-Phase Minimization
Given an unoptimized test set, we propose the following procedures:
Phase 1: Use existing ILP minimization techniques [73, 29] to obtain a minimal detection
test set from the given unoptimized test set. Find the faults not diagnosed by the minimized
detection test set.
Phase 2: Run the diagnostic ILP on the remaining unoptimized test set to obtain a minimal
set of vectors to diagnose the undistinguished faults from phase-1. The resulting minimized
test set combined with the minimal detection test set of phase-1 serves as a complete diag-
nostic test set.
In the context of diagnostic ILP of phase-2, the phase-1 along with the generalized
independence relation helps in reducing the number of constraints to manageable levels.
This is because diagnostic constraints are now needed only for the undiagnosed fault pairs
of phase-1. Also, there will be a further reduction in the number of diagnostic constraints
due to diagnostically independent fault pairs that could be present. We can also drop
the detection constraints as we have started with a detection test set that detects all the
targeted faults.
70
There is another benefit of the test set obtained by the two-phase approach. For all
good chips, testing can be stopped at the detection test set, which is of minimal size.
Only for bad chips whose number depending on yield may be small, we need to apply the
remaining tests for diagnosis.
The graph in Figure 6.5 gives the comparison between diagnostic test sets got by
single-step diagnostic ILP minimization and the 2-phase approach. The experiment could
be performed only on 4-b ALU and the smaller benchmark circuits c17 and c432. For other
larger benchmark circuits like c880 we could not run the diagnostic ILP as the number of
constraints was too many for the problem to be loaded onto the computer. Hence the empty
slot in the graph for the 1-step process of c880. As can be seen, the final diagnostic test
sets obtained by 2-phase approach are slightly larger than the ones obtained by single-step
minimization. In the case of 2-phase minimization, we had suggested that the testing of
good chips can be stopped at the minimal detection test set and the remaining diagnostic
tests (which are few) can be used to complete the diagnosis of bad chips. This idea can
applied to the diagnostic test set got by single-step diagnostic ILP. A detection test set
can be obtained from the vectors comprising the diagnostic test set by using the existing
ILP minimization techniques [29] (Test minimization ILP). The diagnostic vector set can
be reordered such that the detection vectors are present at the start of the vector set.
Thus here too the testing of good circuits can be stopped at the detection vector sets. It
can be seen from the graph that, for c17, 4-b ALU and c432 the detection test set in the
case of single-step diagnostic ILP minimization is larger than that obtained during 2-phase
minimization. Thus the testing of good circuits will take a longer time, which depending
71
0
10
20
30
40
50
60
Number of Vectors
1-step 2-phase 1-step 2-phase 1-step 2-phase 1-step 2-phase
ALU and Benchmark Circuits
Additional Diagnostic Vectors
Detection Vectors
Complete
Diagnostic
Test Set
4 - b ALU c17 c432 c880
Figure 6.5: Comparison Between 1-Step Diagnostic ILP Minimization and 2-Phase Ap-
proach
on the yield may be high in number. The complete diagnostic test set will be applied to
only to bad circuits, which in case of high yield are few.
6.4 Results
In our experiments we have used the ATPG ATALANTA [56] and fault simulator
HOPE [57]. We have used AMPL package [30] for ILP formulation.
Results of phase-1 are given in Table 6.4. First column lists the names of the ISCAS85
circuits. The next column gives the number of faults in the target fault list. These faults
are equivalence collapsed single stuck-at faults, excluding the ones that were identified as
redundant or were aborted by the ATPG program. We have used the minimal detection
test sets obtained using the primal-dual test minimization algorithm of Section 4.6. The
primal-dual algorithm creates unoptimized test sets which essentially consist of N-detect
tests, and then minimizes them to give the minimal detection test sets. The sizes of the
72
unoptimized and minimized vector sets are given in columns 3 and 4 of the table. The
subsequent columns give the diagnosis statistics of the minimal detection test sets. We
say a fault is uniquely diagnosed if it has a unique syndrome. On the other hand a fault
whose syndrome is shared by other faults is said to be undiagnosed. Column 5 gives the
number of undiagnosed faults. Faults with identical syndromes are grouped into a single
set called an equivalent fault set. Note that such an equivalent fault set is dependent
on the vector set used for diagnosis, thus it is called a Conditional Equivalent Fault Set
(CEFS). The column, No. of CEFS gives the number of such sets. There is one CEFS
for every non-unique syndrome consisting of the undiagnosed faults associated with that
syndrome. Maximum faults per syndrome give the maximum number of faults associated
with a syndrome. Diagnostic resolution (DR) defined in [3] gives an average number of
faults per syndrome. It is obtained by dividing the total number of faults by the total
number of syndromes. These two parameters quantify the effectiveness of diagnosis since
DR indicates how well faults are distributed among all syndromes and the Maximum faults
per syndrome indicate the worst distribution among all syndromes. The undiagnosed faults
obtained in this step are the target faults in phase-2 of our algorithm.
Table 6.5 gives the results for phase-2 in which diagnostic ILP is used to minimize
the tests for the undistinguished fault pairs of phase-1. In this step we have used the
unoptimized test sets (excluding the minimal detection tests) of phase-1. The No. of Faults
here are the undiagnosed faults from Table 6.4. The next column gives the number of
constraints generated during the ILP formulation. It can be seen that the constraint set
size is very small even for the larger benchmark circuits like c7552 and c6288. The column
Minimized Vectors gives the result of the diagnostic ILP. These vectors combined with the
73
Table 6.4: Phase-1: Diagnosis With Minimal Detection Test Sets.
No. of Primal-Dual Minimal Detection Test Diagnostic Statistics
Circuit Faults Algorithm [73]
No. of No. of No. of No. of Maximum Diagnostic
Unoptim. Minimized Undiagnosed CEFS Faults per Resolution
Vectors Vectors Faults Syndrome
4b ALU 227 270 12 43 19 4 1.118
c17 22 32 4 6 3 2 1.158
c432 520 2036 30 153 68 9 1.195
c499 750 705 52 28 12 3 1.023
c880 942 1384 24 172 83 4 1.1
c1355 1566 903 84 1172 531 5 1.693
c1908 1870 1479 107 543 248 17 1.187
c2670 2630 4200 70 833 316 11 1.245
c3540 3291 3969 95 761 313 8 1.158
c5315 5291 1295 63 1185 527 8 1.142
c6288 7710 361 16 2416 1122 6 1.202
c7552 7419 4924 122 1966 891 7 1.17
minimal detection vectors of phase-1 constitute the complete diagnostic test set. The last
column gives the CPU time for the diagnostic ILP runs. It is evident that the complexity
of the diagnostic ILP is greatly reduced. All CPU times are for a SUN Fire 280R 900MHz
Dual Core machine. For cases in which the ILP complexity is high, reduced-complexity LP
variations described in [48] can be used.
Table 6.6 gives the results and statistics of the fault dictionary obtained by using the
complete diagnostic test set. The total diagnostic vectors are the combined vector sets from
phase-1 and 2. Notice that these test sets are just a little bigger than the minimal detection
test sets of Table 6.4. Thus failed chips can be diagnosed very quickly as the detection
tests would have already been applied during testing. Column 3 gives the number of faults
in the target fault list. Column 4 gives the number of uniquely diagnosed faults. The
remaining columns have similar meaning to that of Table 6.5. It can be seen that there
74
Table 6.5: Phase-2: Diagnostic ILP Minimization.
Circuit Number of No. of No. of Minimized CPU s
Unoptimized Vectors Faults Constraints Vectors
4b ALU 258 43 30 6 1.36
c17 28 6 3 2 1.07
c432 2006 153 101 21 3.03
c499 652 28 10 2 1.09
c880 1358 172 41 7 2.74
c1355 1131 1172 12 2 2.13
c1908 819 543 186 21 3.16
c2670 4058 833 383 51 5.29
c3540 3874 761 146 27 8.45
c5315 1232 1185 405 42 15.35
c6288 345 2416 534 12 50.13
c7552 4802 1966 196 31 9.35
is an improvement in the diagnostic resolution from that of phase-1 due to the diagnosis
vectors from phase-2.
The unoptimized test sets used in our experiments are essentially N-detect tests. It
should be noted here that using an unoptimized test set consisting of diagnostic ATPG
vectors [79] will be more effective in achieving a good diagnostic resolution, as these vectors
are generated for the sole purpose of distinguishing pairs of faults.
Table 6.7 gives the comparison between our work on two-phase minimization and a prior
work [41] on the compaction of test sets for a pass-fail dictionary. For both the algorithms
an initial unoptimized set of 1024 random vectors is used. The authors in [41] measure
the diagnostic effectiveness of the compacted test set in terms of number of undiagnosed
fault pairs. The pass-fail dictionaries have inherently lower resolution than the full-response
dictionaries. Thus there may not be a one-to-one comparison between these results as the
prior work is for a pass-fail dictionary test set and ours is for a full-response dictionary.
75
Table 6.6: Diagnosis with Complete Daignostic Test Set.
1 2 3 4 5 6 7 8 9
Total No. of Uniquely No. of Undiag. No. of Maximum Diagnostic
Circuit Diag. Faults Diag. CEFS faults Synd. Faults per Resolution
Vectors Faults (3 - 4) (4 + 5) Syndrome (3 / 7)
4b ALU 18 227 227 0 0 227 1 1
c17 6 22 22 0 0 22 1 1
c432 51 520 488 16 32 504 2 1.032
c499 54 750 726 12 24 738 2 1.016
c880 33 942 832 55 110 887 2 1.062
c1355 86 1566 397 532 1169 929 3 1.686
c1908 127 1870 1380 238 490 1618 8 1.156
c2670 121 2630 2027 263 603 2290 11 1.149
c3540 122 3291 2720 234 571 3033 8 1.085
c5315 105 5291 4496 381 795 4877 4 1.085
c6288 28 7710 5690 1009 2020 6699 3 1.151
c7552 153 7419 5598 848 1821 6446 7 1.151
However we can notice the compactness of the diagnostic test sets got by the two-phase
method and its computing efficiency.
6.5 Analysis of Undistinguished Fault Pairs of c432
We examine the fault pairs that remained undistinguished by the minimized diagnostic
vector set. From Table 6.6 we see that for c432 the minimized diagnostic test set has 51
vectors and the number of undiagnosed faults is 32, which are distributed in 16 conditional
equivalent fault sets (CEFS). Now, since the maximum faults per syndrome is 2, each CEFS
can contain at most 2 faults. Thus there are 16 undistinguished fault pairs.
We used the circuit structure shown in Figure 6.6 to examine the undistinguishable
fault pairs. Here, two copies of the circuit under test (CUT) are used. Each copy has one
fault from the fault pair permanently inserted. Both copies have the same primary inputs
and their outputs are connected as shown in Figure 6.6 to derive a primary output for
76
Table 6.7: Two-phase Minimization vs. Previous Work [41].
Pass-Fail dictionary compaction [41] Two-Phase Approach [This work]
Circuit Fault Minim. Undist. CPU Fault Minim. Undist. CPU
Coverage Vectors Fault s Coverage Vectors Fault s
% Pairs % Pairs
c432 97.52 68 93 0.1* 98.66 54 15 0.94**
c499 - - - - 98.95 54 12 0.39**
c880 97.52 63 104 0.2* 97.56 42 64 2.56**
c1355 98.57 88 878 0.8* 98.6 80 766 0.34**
c1908 94.12 139 1208 2.1* 95.69 101 399 0.49**
c2670 84.4 79 1838 2.8* 84.24 69 449 8.45**
c3540 94.49 205 1585 10.6* 94.52 135 590 17.26**
c5315 98.83 188 1579 15.4* 98.62 123 472 25.03**
c6288 99.56 37 4491 1659* 99.56 17 1013 337.89**
c7552 91.97 198 4438 33.8* 92.32 128 1289 18.57**
*Pentium IV 2.6 GHz machine **SUN Fire 280R, 900 MHz Dual Core machine
the composite circuit. An ATPG is used to detect sa0 fault at the primary output of the
composite circuit. There are three possible outcomes of the ATPG run.
1. An exclusive test is found indicating that the faults are distinguishable. An Exclusive
test is an input vector that detects only one fault from a pair of targeted faults [3].
2. Identifies the output sa0 fault as redundant, in which case the two faults fi and fj are
equivalent. Although not often recognized, all redundant faults of a combinational
circuit form an equivalent fault set.
3. Aborts - no conclusion can be reached on the distinguishablity of faults in the fault
pair.
For c432, after running the ATPG for the 16 fault pairs, an exclusive test was found
for 3 pairs, and for the remaining 13 pairs the ATPG aborted. This illustrates the need for
programs to generate exclusive tests for fault pairs. Also, efficient programs are needed to
find functional equivalences.
77
CUT
f i
CUT
f j
x
s a0
1
1
n
n
Primary
Inputs
Figure 6.6: An ATPG-based Method for Examining a Fault Pair (fi, fj).
For c432, we added the 3 vectors obtained as exclusive tests to the original test set
of 2036 vectors and repeated the 2-phase minimization. Phase-1 gave a minimal detection
test set of 30 vectors which is the same as that obtained in the earlier 2-phase minimization
run of Table 6.4. Phase-2 gave a minimal diagnostic set of 23 additional vectors, 2 more
than the earlier case (Table 6.5). Thus, the new complete diagnostic test set consisted of
53 vectors and the 26 faults (i.e., 13 fault pairs) remained undiagnosed.
78
Chapter 7
Conclusion
The initial part of this thesis gives a dual ILP formulation, which is an exact solution to
finding the maximal IFS. The dual ILP is modeled as the dual of the test minimization ILP
(now called the primal ILP) described in literature. It was observed that the computational
complexity of the dual ILP was much lesser than that of the primal ILP. Using the primal
ILP and dual ILP we have presented a novel primal-dual algorithm for test optimization
for combinational circuits. The dual ILP helps in obtaining proper vectors, which then
can be optimized by the primal ILP. We should point out that the ILP formulation for
both the primal and dual is exact and has exponential complexity. As the primal ILP was
more complex than the dual, for larger benchmark circuits we see large CPU times. Thus
in place of primal ILP, we use primal LP based recursive rounding technique which is of
lower complexity and provides an approximate solution. The primal-dual method, when
applied to the ISCAS85 benchmark circuits, produced better results compared to an earlier
LP-alone test minimization method [47].
In the second part of the thesis we have presented an Integer Linear Program (ILP)
formulation for compaction of the diagnostic test set used in full-response dictionary based
fault diagnosis. The compaction can be carried out without any loss in the diagnostic
resolution of the initial test set. The newly defined diagnostic independence relation between
pairs of faults is very effective in reducing the number of faults that need to be distinguished,
thereby reducing the number of constraints in the diagnostic ILP. Finally we have proposed
a 2-phase approach for generating a minimal diagnostic test set. The diagnostic test sets
79
obtained are very small because of which there can be a significant reduction in the fault
dictionary size and also the diagnosis time.
7.1 Future Work
? In the context of primal-dual algorithm of Chapter 4, Theorem 2 [73] suggests that as
the vector set approaches the exhaustive set, the CIFS must converge to IFS. In our
experiments it was observed that for dual ILP iterations using N-detect vectors for
the faults in the CIFS made the convergence of the CIFS to the IFS a slow process.
Thus, new strategies for generating vectors for the dual problem must be explored in
order to have the CIFS quickly converge to IFS before vector set becomes exhaustive.
? Yogi and Agrawal?s work on N-model test set minimization [81], showed how a single
detection table can be constructed for tests of multiple fault models. This idea could
be used for creating a fault dictionary for multiple fault models and then using the 2-
phase approach to minimize the diagnostic vector set. The diagnosis results of such a
fault dictionary could be more accurate in predicting the defect locations and nature.
? Toward improving the resolution of diagnostic tests, the analysis of the undiagnosed
fault pairs of c432 in Section 6.5 showed the need for programs to generate exclusive
tests for fault pairs. Also, efficient programs are needed to find functional equivalences.
7.1.1 Primal-Dual Algorithm with Partially Specified Vectors
Consider the circuit consisting of two AND gates as shown in Figure 7.1. The faults in
the figure are equivalence collapsed single stuck-at faults. Suppose that vectors t1, t2 and
t3 are generated by targeting faults of the first AND gate, and vectors t4, t5, and t6 are
80
sa1
sa1
sa0
x x x x
sa1
sa1
sa0 x
x x x
sa1
sa1
1
2
1 1 0 0
1 0 1 0
0 1 1 0
0 0 1 1
Minimized
Vector Set
0 1 1
1 0 1
0 1 0
0 0 0
0 0 1
0 0 0
0 1 1
1 0 1
ATPG
Vectors
t6 t5 t4 t3 t2 t1
Figure 7.1: Non-optimal Solution Obtained Using ILP Minimization.
generated by targeting faults of the second AND gate. Now the ILP minimization of the 6
vectors gives us a test set of 4 vectors. But this circuit has a minimal detection test set of
3 vectors.
We used the primal-dual algorithm on similar circuits consisting of 4, 8 and 16 AND
gates. It was observed the algorithm could find a minimal test set of 4 vectors for all the
three circuits by minimizing vectors accumulated in two dual ILP iterations. But it did not
get to the absolute minimal set of 3 vectors even after seven dual ILP iterations.
Figure 7.2 shows a possible solution to the problem illustrated above. Here ILP min-
imization is carried out for partially specified test vectors, followed by further compaction
of the minimized test set by vector merging. A partially specified vector is one in which
the bits corresponding to unspecified inputs are left as X?s (don?t cares). Vector merging
is a static compaction technique where pairs of partially specified test vectors, that do not
conflict in their specified (0, 1) values, are repeatedly merged into single vectors [13]. We
81
sa1
sa1
sa0
x x x x
sa1
sa1
sa0 x
x
0 1 1
1 0 1
x x x
x x x
x x x
x x x
0 1 1
1 0 1 x x
sa1
sa1
1
2
Compacted
Vector Set
0 1 1
1 0 1
0 1 1
1 0 1
x x x 0 1 1
x x x 1 0 1
0 1 1 x x x
1 0 1 x x x
Minimized
Vector Set t3 t2 t1 t6 t5 t4
Figure 7.2: Minimizing Partially Specified Vectors and then Vector Merging.
start with the six partially specified vectors and then minimize them using the ILP min-
imization. We have found that an ILP formulation for partially specified vectors can be
easily worked out. In this example the ILP minimization does not provide any reduction in
initial test set size. This is because the circuit used here is an extreme example. Normally,
there will be reduction in the test set size. However, the level of compaction achievable by
ILP minimization may not be as high as in the case of fully specified vectors. On further
compacting the vectors resulting from ILP minimization we get a set of 3 vectors, which is
the minimal possible set for this circuit.
A similar approach can be used for the primal-dual algorithm. We can use primal-dual
algorithm with partially specified vectors. Then the resulting minimized test set is further
compacted by vector merging. Such an approach may produce more compact test sets.
The use of partially specified vectors and ILP minimization followed by don?t care merging
may be especially beneficial for circuits with small logic depth and large number of primary
inputs.
82
Bibliography
[1] M. Abramovici and M. A. Breuer, ?Multiple Fault Diagnosis in Combinational Circuits Based
on an Effect-Cause Analysis,? IEEE Transactions on Computing, vol. C-29, no. 6, pp. 451?460,
June 1980.
[2] V. D. Agrawal and P. Agrawal, ?An Automatic Test Generation System for Illiac IV Logic
Boards,? IEEE Trans. on Computers, vol. C-21, no. 9, pp. 1015?1017, Sept. 1972.
[3] V. D. Agrawal, D. H. Baik, Y. C. Kim, and K. K. Saluja, ?Exclusive Test and its Applications
to Fault Diagnosis,? in Proc. International Conf. on VLSI Design, 2003, pp. 143?148.
[4] V. D. Agrawal, A. V. S. S. Prasad, and M. V. Atre, ?Fault Collapsing via Functional Domi-
nance,? in Proc. International Test Conf., 2003, pp. 274?280.
[5] V. D. Agrawal, A. V. S. S. Prasad, and M. V. Atre, ?It is Sufficient to Test 25-Percent of
Faults,? in Proc. Seventh IEEE VLSI Design and Test Workshop, 2003, pp. 368?374.
[6] V. D. Agrawal and S. C. Seth, Test Generation for VLSI Chips. Los Alamitos, CA: IEEE
Computer Society Press, 1988.
[7] S. B. Akers, C. Joseph, and B. Krishnamurthy, ?On the Role of Independent Fault Sets in the
Generation of Minimal Test Sets,? in Proc. International Test Conf., 1987, pp. 1100?1107.
[8] S. B. Akers and B. Krishnamurthy, ?Test Counting: A Tool for VLSI Testing,? IEEE Design
and Test of Computers, vol. 6, no. 5, pp. 58?77, Oct. 1989.
[9] D. B. Armstrong, ?A Deductive Method for Simulating Faults in Logic Circuits,? IEEE Trans-
actions on Computers, vol. C-21, no. 5, pp. 464?471, May 1972.
[10] S. P. Bradley, A. C. Hax, and T. L. Magnanti, Applied Mathematical Programming. Addison-
Wesley, 1977.
[11] F. Brglez, D. Bryan, and K. Kozminski, ?Combinational Profiles of Sequential Benchmark
Circuits,? in Proc. Int. Symp. on Circuits and Systems, 1989, pp. 1929?1934.
[12] F. Brglez and H. Fujiwara, ?A Neutral Netlist of 10 Combinational Benchmark Designs and a
Special Translator in Fortran,? in Proc. Int. Symp. on Circuits and Systems, 1985.
[13] M. L. Bushnell and V. D. Agrawal, Essentials of Electronic Testing for Digital, Memory, and
Mixed-Signal VLSI Circuits. Springer, 2000.
[14] K. Chakrabarty, V. Iyengar, and A. Chandra, Test Resource Partitioning for System-On-Chip.
Kluwer Academic Publishers, 2002.
[15] A. Chandra and K. Chakrabarty, ?Test data compression and test resource partitioning for
system-on-a-chip using frequency-directed run-length (FDR) codes,? IEEE Transactions on
Computers, vol. 52, no. 8, pp. 1076?1088, 2003.
[16] H. Y. Chang, E. Manning, and G. Metze, Fault Diagnosis of Digital Systems. Wiley-
Interscience,, 1970.
83
[17] J. S. Chang and C. S. Lin, ?Test Set Compaction for Combinational Circuits,? IEEE Trans.
on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, no. 11, pp. 1370?1378,
Nov. 1995.
[18] W. T. Cheng and M. L. Yu, ?Differential Fault Simulation for Sequential Circuits,? Journal of
Electronic Testing: Theory and Applications, vol. 1, no. 1, pp. 7?13, Feb. 1990.
[19] B. Chess and T. Larrabee, ?Creating Small Fault Dictionaries,? IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems, pp. 346?356, Mar. 1980.
[20] T. H. Cormen, C. E. Leiserson, and R. L. Riverst, Introduction to Algorithms. MIT Press,
2001.
[21] A. L. Crouch, Design for Test for Digital ICs and Embedded Core Systems. New Jersey:
Prentice Hall, 1999.
[22] G. B. Dantzig, Linear Programming and Extension. Princeton, New Jersey: Princeton Univer-
sity Press, 1963.
[23] A. S. Doshi, ?Independence Fault Collapsing and Concurrent Test Generation,? Master?s thesis,
Auburn University, Auburn, Alabama, May 2006.
[24] A. S. Doshi and V. D. Agrawal, ?Concurrent Test Generation,? in Proc. 14th IEEE Asian Test
Symp., 2005, pp. 294?299.
[25] A. S. Doshi and V. D. Agrawal, ?Independence Fault Collapsing,? in Proc. 9th VLSI Design
and Test Symp., 2005, pp. 357?364.
[26] P. Drineas and Y. Makris, ?Independent Test Sequence Compaction through Integer Program-
ming,? in Proc. International Conf. Computer Design, 2003, pp. 380?386.
[27] R. D. Eldred, ?Test Routines Based on Symbolic Logical Statements,? Journal of the ACM,
vol. 6, no. 1, pp. 33?36, Jan. 1959.
[28] T. S. Ferguson, ?Linear Programming: A Concise Introduction.? Website. Available at http:
//www.math.ucla.edu/~tom/LP.pdf/.
[29] P. Flores, H. Neto, and J. M. Silva, ?An Exact Solution to the Minimum Size Test Pattern
Problem,? ACM Trans. Design Automation of Electronic Systems, vol. 6, no. 4, pp. 629?644,
Oct. 2001.
[30] R. Fourer, D. M. Gay, and B. W. Kernighan, AMPL: A Mathematical Programming Language.
Brooks/Cole-Thomson Learning, 2003.
[31] H. Fujiwara and T. Shimono, ?On the Acceleration of Test Generation Algorithms,? IEEE
Trans. on Computers, vol. C-32, no. 12, pp. 1137?1144, Dec. 1983.
[32] H. Fujiwara and S. Toida, ?The Complexity of Fault Detection Problems for Combinational
Logic Circuits,? IEEE Trans. on Computers, vol. C-31, no. 6, pp. 555?560, June 1982.
[33] J. M. Galey, R. E. Norby, and J. P. Roth, ?Techniques for the Diagnosis of Switching Circuit
Failures,? in Proc. Second Annual Symp. on Switching Circuit Theory and Logical Design, 1961,
pp. 152?160.
[34] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of
NP-Completeness. W. H. Freeman, 1979.
[35] D. Gizopoulos, Advances in Electronic Testing: Challenges and Methodologies. Springer, 2006.
84
[36] P. Goel, ?An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic
Circuits,? IEEE Trans. on Computers, vol. C-30, no. 3, pp. 215?222, Mar. 1981.
[37] P. Goel and B. C. Rosales, ?Test Generation and Dynamic Compaction of Tests,? in Digest of
Papers 1979 Test Conference, 1979, pp. 189?192.
[38] I. Hamzaoglu and J. H. Patel, ?Test Set Compaction Algorithms for Combinational Circuits,?
in Proc. International Conf. on Computer-Aided Design, 1998, pp. 283? 289.
[39] I. Hamzaoglu and J. H. Patel, ?Test Set Compaction Algorithms for Combinational Circuits,?
IEEE Trans. on CAD, vol. 19, no. 8, pp. 957?963, Aug. 2000.
[40] M. C. Hansen, H. Yalcin, and J. P. Hayes, ?Unveiling the ISCAS-85 Benchmarks: A Case
Study in Reverse Engineering,? IEEE Design and Test of Computers, vol. 16, no. 3, pp. 72?80,
1999.
[41] Y. Higami, K. K. Saluja, H. Takahashi, S. Kobayashi, and Y. Takamatsu, ?Compaction of
Pass/Fail-based Diagnostic Test Vectors for Combinational and Sequential Circuits,? in Proc.
Asia and South Pacific Design Automation Conf., 2006, pp. 75?80.
[42] O. H. Ibarra and S. K. Sahni, ?Polynomially Complete Fault Detection Problems,? IEEE Trans.
on Computers, vol. C-24, no. 3, pp. 242?249, Mar. 1975.
[43] H. Ichihara, K. Kinoshita, and S. Kajihara, ?On Test Generation with A Limited Number of
Tests,? in Proc. 9th Great Lakes Symposium on VLSI, 1999, pp. 12?15.
[44] S. Kajihara, I. Pomeranz, K. Kinoshita, and S. M. Reddy, ?On Compacting Test Sets by
Addition and Removal of Test Vectors,? in Proc. IEEE VLSI Test Symposium, 1994, pp. 25?
28.
[45] S. Kajihara, I. Pomeranz, K. Kinoshita, and S. M. Reddy, ?Cost Effective Generation of Min-
imal Test Sets for Stuck at Faults in Combinational Logic Circuits,? IEEE Trans. on CAD,
vol. 14, no. 12, pp. 1496?1504, Dec. 1995.
[46] K. R. Kantipudi, ?Minimizing N-Detect Tests for Combinational Circuits,? Master?s thesis,
Auburn University, Auburn, Alabama, May 2007.
[47] K. R. Kantipudi and V. D. Agrawal, ?On the Size and Generation of Minimal N-Detection
Tests,? in Proc. 19th International Conf. VLSI Design, 2006, pp. 425?430.
[48] K. R. Kantipudi and V. D. Agrawal, ?A Reduced Complexity Algorithm for Minimizing N-
Detect Tests,? in Proc. 20th International Conf. VLSI Design, Jan. 2007, pp. 492?497.
[49] N. K. Karmarkar, ?New Polynomial-Time Algorithm for Linear Programming,? Combinatorica,
vol. 4, pp. 373?395, 1984.
[50] J. B. Khare, W. Maly, S. Griep, and D. Schmitt-Landsiedel, ?Yield-oriented Computer-aided
Defect Diagnosis,? IEEE Trans. on Semiconductor Manufacturing, vol. 8, no. 2, pp. 195?206,
May 1995.
[51] B. Krishnamurthy and B. Akers, ?On the Complexity of Estimating the Size of a Test Set,?
IEEE Trans. on Computers, vol. C-33, no. 8, pp. 750?753, Aug. 1984.
[52] X. W. L.-T. Wang, C.-W. Wu, VLSI Test Principles and Architectures: Design for Testability.
San Francisco, CA: Morgan Kaufmann Publishers, 2006.
85
[53] D. Lavo, B. Chess, T. Larrabee, and F. J. Ferguson, ?Diagnosing Realistic Bridging Faults
with Single Stuck-at Information,? IEEE Trans. Computer-Aided Design, vol. 17, no. 3, pp.
255?268, Mar. 1998.
[54] D. Lavo and T. Larrabee, ?Making Cause-Effect Cost Effective: Low-Resolution Fault Dictio-
naries,? in Proc. International Test Conference, 2001, pp. 278?286.
[55] D. B. Lavo, Comprehensive Fault Diagnosis of Combinational Circuits. PhD thesis, University
of California, Santa Cruz, CA, Sept. 2002.
[56] H. K. Lee and D. S. Ha, ?Atalanta: an Efficient ATPG for Combinational Circuits,? Technical
report, Dept. of Elec. Eng., Virginia Polytechnic Institute and State University, Blacksburg,
VA, USA, 1993.
[57] H. K. Lee and D. S. Ha, ?HOPE: An Effcient Parallel Fault Simulator for Synchronous Se-
quential Circuits,? IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems,
vol. 15, no. 9, pp. 1048?1058, Sept. 1996.
[58] M. Nourani and C. Papachristou, ?An ILP Formulation to Optimize Test Access Mechanism
in System-On-Chip Testing,? in Proc. of International Test Conf, 2000, pp. 902?910.
[59] I. Pomeranz, L. N. Reddy, and S. M. Reddy, ?COMPACTEST A Method to Generate Compact
Test Sets for Combinational Circuits,? in Proc. International Test Conf., 1991, pp. 194?203.
[60] I. Pomeranz and S. M. Reddy, ?Generalization of Independent Fault Sets for Transition Faults,?
in Proc. IEEE VLSI Test Symposium, 1992, pp. 7?12.
[61] I. Pomeranz and S. M. Reddy, ?On the Generation of Small Dictionaries for Fault Location,?
in Proc. International Conf. on Computer-Aided Design, 1992, pp. 272?278.
[62] I. Pomeranz and S. M. Reddy, ?On Correction of Multiple Design Errors,? IEEE Trans. on
Computer-Aided Design of Integrated Circuits and Systems, vol. 14, no. 2, pp. 255?264, Feb.
1995.
[63] A. V. S. S. Prasad, V. D. Agrawal, and M. V. Atre, ?A New Algorithm for Global Fault
Collapsing into Equivalence and Dominance Sets,? in Proc. International Test Conf., 2002, pp.
391?397.
[64] J. Rajski and H. Cox, ?A Method to Calcufate Necessary Assignments in Algorithmic Test
Pattern Generation,? in Proc. International Test Conf., 1990, pp. 25?34.
[65] S. M. Reddy, ?Complete Test Sets for Logic Functions,? IEEE Trans. on Computers, vol. C-22,
no. 11, pp. 1016?1020, Nov. 1973.
[66] J. P. Roth, ?Diagnosis of Automata Failures: A Calculus and a Method,? IBM Journal of
Research and Development, vol. 10, no. 4, pp. 278?291, July 1966.
[67] J. P. Roth, W. G. Bouricius, and P. R. Schneider, ?Programmed Algorithms to Compute Tests
to Detect and Distinguish Between Failures in Logic Circuits,? IEEE Trans. on Electronic
Computers, vol. EC-16, no. 5, pp. 567?580, Oct. 1967.
[68] R. K. K. R. Sandireddy, ?Hierarchical Fault Collapsing for Logic Circuits,? Master?s thesis,
Auburn University, Auburn, Alabama, May 2005.
[69] R. K. K. R. Sandireddy and V. D. Agrawal, ?Diagnostic and Detection Fault Collapsing for
Multiple Output Circuits,? in Proc. Design, Automation and Test in Europe, 2005, pp. 1014?
1019.
86
[70] R. K. K. R. Sandireddy and V. D. Agrawal, ?Use of Hierarchy in Fault Collapsing,? in Proc.
14th IEEE North Atlantic Test Workshop, 2005.
[71] M. H. Schulz and E. Auth, ?Improved Deterministic Test Pattern Generation with Applications
to Redundancy Identification,? IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, vol. 8, no. 7, pp. 811?816, July 1989.
[72] M. H. Schulz, E. Trischler, and T. M. Sarfert, ?SOCRATES: A Highly Efficient Automatic
Test Pattern Generation System,? IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, vol. 7, no. 1, pp. 126?137, Jan. 1988.
[73] M. A. Shukoor and V. D. Agrawal, ?A Primal-Dual Solution to the Minimal Test Generation
Problem,? in Proc. VLSI Design and Test Symp., 2008, pp. 269?279.
[74] M. A. Shukoor and V. D. Agrawal, ?A Two Phase Approach for Minimal Diagnostic Test Set
Generation,? in Proc. 14th IEEE European Test Symposium, May 2009.
[75] G. Strang, Linear Algebra and Its Applications. Fort Worth: Harcourt Brace Javanovich College
Publishers, third edition, 1966.
[76] G. Tromp, ?Minimal Test Sets for Combinational Circuits,? in Proc. International Test Conf.,
1991, pp. 204?209.
[77] E. G. Ulrich, V. D. Agrawal, and J. H. Arabian, Concurrent and Comparative Discrete Event
Simulation. Boston: Kluwer Academic Publishers, 1994.
[78] E. G. Ulrich and T. Baker, ?Concurrent Simulation of Nearly Identical Digital Networks,?
Computers, vol. 7, pp. 39?44, Apr. 1974.
[79] A. Veneris, R. Chang, M. S. Abadir, and M. Amiri, ?Fault equivalence and diagnostic test
generation using ATPG,? in Proc. International Symposium on Circuits and Systems, 2004,
pp. 221?224.
[80] J. A. Waicukauski and E. Lindbloom, ?Failure Diagnosis of Structured VLSI,? IEEE Design
and Test of Computers, vol. 6, no. 4, pp. 49?60, Aug. 1989.
[81] N. Yogi and V. D. Agrawal, ?N-Model Tests for VLSI Circuits,? in Proc. of 40th Southwestern
Symp. on System Theory, 2008.
87
Appendix
Recursive Rounding Technique
The complexity of an integer linear programming (ILP) problem is exponential in terms
of the number of variables present in the problem. For large circuits the ILP execution takes
a very long time to complete. A useful method to solve an integer linear programming (ILP)
problem in polynomial time is to first solve a relaxed linear programming (LP) problem
having the same objective function and constraints, but regarding the variables as real
continuous variables. Then round off the real solution to an integer solution. Since the LP
complexity is polynomial, a solution is easily obtained from available programs [30].
Kalyan and Agrawal in [48] have given a recursive rounding technique for the test
minimization problem. The test minimization ILP problem described in Section 4.1 is
converted to a relaxed LP problem, which has the same objective function and constraints
as given in Equations (4.1) and (4.2), but the variables ti are regarded as real continuous
variables in the range [0.0,1.0].
The recursive rounding procedure is as follows,
1. Obtain an LP solution. Stop if each ti is either 0.0 or 1.0.
2. Round the largest ti to 1 and fix its value to 1.0. If several ti have the largest value,
then arbitrarily set only one to 1.0. Go to Step 1.
Step 1 guarantees that any solution thus obtained satisfies all constraints.
The recursive rounding technique can be applied to the dual ILP of Section 4.2 and
diagnostic ILP of Section 6.1.2.
88