Independence Fault Collapsing and Concurrent Test Generation 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. Alok Shreekant Doshi Certificate of Approval: Victor P. Nelson Professor Electrical and Computer Engineering Vishwani D. Agrawal, Chair James J. Danaher Professor Electrical and Computer Engineering Charles E. Stroud Professor Electrical and Computer Engineering Stephen L. McFarland Acting Dean Graduate School Independence Fault Collapsing and Concurrent Test Generation Alok Shreekant Doshi 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 11, 2006 Independence Fault Collapsing and Concurrent Test Generation Alok Shreekant Doshi 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 Alok S. Doshi, son of Mrs. Rohini Doshi and Mr. Shreekant M. Doshi, was born in Pune, Maharashtra, India. He graduated from Fergusson College, Pune in 1999. He earned the degree Bachelor of Engineering in Electronics and Telecommunication from Maharashtra Institute of Technology affiliated to Pune University, Pune, India in 2003. iv Thesis Abstract Independence Fault Collapsing and Concurrent Test Generation Alok Shreekant Doshi Master of Science, May 11, 2006 (B.E., Pune University, 2003) 99 Typed Pages Directed by Vishwani D. Agrawal The objective of this work is to find suitable targets for Automatic Test Pattern Generation (ATPG) such that a minimal test set is obtained for a combinational circuit. Original concepts of independence fault collapsing and concurrent test gen- eration are developed and a novel test generation strategy based on these is devised. Independence fault collapsing groups faults into independent fault subsets such that each subset includes some faults that cannot be covered by the tests derived for any other subset. Using these fault subsets, optimally compact tests can be found. For an equivalence or dominance collapsed fault set an independence graph is gen- erated using structural and functional independences. Each fault is represented as a node and an undirected edge between two nodes indicates independence of the corre- sponding faults; two independent faults cannot be detected by the same test vector. A ?similarity-based? collapsing procedure reduces the graph to a fully-connected graph, whose nodes specify concurrently-testable fault targets for the ATPG. v Given a set of target faults, a concurrent test is an input vector that detects all (or most) faults in the set. These sets are obtained from the independence fault collapsing procedure. A new algorithm called the concurrent D algebra is presented for concurrent test generation. The independence fault collapsing algorithm and the concurrent D algebra to- gether produced the minimal set of 12 tests for the 4-bit ALU (74181) circuit. But due to the complexity involved in generating the independence graph, this technique was not applied to the ISCAS85 benchmark circuits. A simulation based method was devised for generating the independence graph and for deriving concurrent tests using single-fault ATPG. The simulation based method was applied to the ISCAS85 combinational bench- mark circuits. The results show that minimal test sets were generated for some benchmark circuits in CPU times that were almost half of what were required for an alternative dynamic compaction technique presented in the literature. vi Acknowledgments I would like to gratefully acknowledge the assistance, encouragement, support, patience and direction provided to me by my advisor, Dr. Vishwani D. Agrawal, during my stay at Auburn University. It was a great pleasure for me to undergo this learning experience. I would like to thank Dr. Victor P. Nelson and Dr. Charles E. Stroud for being on my committee and providing me valuable inputs. I would like to express my deepest gratitude to my parents and sister whose love and encouragement is inspiring me to achieve my goals. Finally I would like to thank all my friends here at Auburn University and also those back in India. vii Style manual or journal used LATEX: A Document Preparation System by Leslie Lamport (together with the style known as ?aums?). Computer software used The document preparation package TEX (specifically LATEX) together with the departmental style-file aums.sty. The images and plots were generated using SmartDraw 6 and Microsoft Office Excel 2003. viii Table of Contents List of Tables xi List of Figures xiii 1 Introduction 1 1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Contribution of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Organization of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Background 4 2.1 Fault Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Stuck-at Faults . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Fault Collapsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Fault Simulation and Test Generation . . . . . . . . . . . . . . . . . . 10 2.3.1 Fault Simulation . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.2 Test Generation . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Previous Work on Test Set Minimization 13 3.1 Static Compaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Dynamic Compaction . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Compaction Based on Independent Faults . . . . . . . . . . . . . . . 18 3.4 The Berger and Kohavi Method . . . . . . . . . . . . . . . . . . . . . 20 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Independence Fault Collapsing 26 4.1 Fault Reclassification . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2 Methods of Finding Independence Relations . . . . . . . . . . . . . . 28 4.2.1 Structural Independence . . . . . . . . . . . . . . . . . . . . . 29 4.2.2 Implied Independence . . . . . . . . . . . . . . . . . . . . . . 29 4.2.3 Functional Independence . . . . . . . . . . . . . . . . . . . . . 32 4.3 Independence Graph and Independence Matrix . . . . . . . . . . . . . 33 4.3.1 Independence Graph . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.2 Independence Matrix . . . . . . . . . . . . . . . . . . . . . . . 36 4.4 Algorithm for Independence Fault Collapsing . . . . . . . . . . . . . . 36 4.4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 ix 4.4.2 Independence Fault Collapsing Algorithm . . . . . . . . . . . 43 4.4.3 ALU Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.5 Simulation-Based Independence Fault Collapsing . . . . . . . . . . . . 51 4.5.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.5.2 More Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.6 An Alternative Method for Independence Fault Collapsing . . . . . . 56 5 Concurrent Test Generation 59 5.1 The Concurrent-D Algebra . . . . . . . . . . . . . . . . . . . . . . . . 61 5.1.1 Four-Bit ALU (74181) . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Simulation Based Concurrent Test Generation . . . . . . . . . . . . . 64 5.2.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6 Conclusion 71 6.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Bibliography 74 Appendices 79 A On the Effectiveness of the Independence Fault Collapsing Al- gorithm of Subsection 4.4.2 80 B DIMACS Format 84 x List of Tables 4.1 Independence matrix for c17 benchmark circuit in Figure 4.5. . . . . 37 4.2 Degree of Independence for c17 benchmark circuit of Figure 4.5. . . . 42 4.3 Similarity Metrics for c17 benchmark circuit of Figure 4.5. . . . . . . 43 4.4 Step 1: Computation of degree of independence (DI) for each fault. . 45 4.5 Step 2: Faults ordered according to decreasing degree of independence. 46 4.6 Step 3: Computation of similarity metric for each pair of faults. . . . 47 4.7 Independence fault collapsing of c17 faults. . . . . . . . . . . . . . . . 47 4.8 Independence collapsed fault sets for 4-bit ALU. . . . . . . . . . . . . 51 4.9 Simulation-based independence fault collapsing for 4-bit ALU (74181) circuit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.10 Independence fault collapsing of ripple-carry full-adders. . . . . . . . 55 4.11 Independence fault collapsing on ISCAS85 benchmark circuits. . . . . 56 4.12 Results for the c17 circuit. . . . . . . . . . . . . . . . . . . . . . . . . 58 5.1 Output of a 2-input AND gate with concurrent-D algebra. . . . . . . 62 5.2 Concurrent test vectors for c17. . . . . . . . . . . . . . . . . . . . . . 62 5.3 Concurrent test generation for the 4-bit ALU (74181) circuit. . . . . . 63 5.4 Test sets for ALU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.5 Simulation-based concurrent test generation for the 4-bit ALU (74181) circuit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 xi 5.6 Concurrent ATPG test length. . . . . . . . . . . . . . . . . . . . . . . 67 5.7 Test generation time. . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 A.1 Independence collapsed fault sets for the 4-bit ALU circuit. . . . . . . 82 A.2 Concurrent test generation for the 4-bit ALU circuit. . . . . . . . . . 83 xii List of Figures 2.1 Testing Process. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Fault Collapsing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1 An example fanout-free circuit. . . . . . . . . . . . . . . . . . . . . . 21 3.2 Characteristic graphs for circuit of Figure 3.1. . . . . . . . . . . . . . 22 3.3 Test generation for circuit of Figure 3.1. . . . . . . . . . . . . . . . . 23 3.4 Problem of finding a minimal test. . . . . . . . . . . . . . . . . . . . . 24 4.1 Test relations of faults F1 and F2 with tests T(F1) and T(F2). . . . 27 4.2 Structural independences of faults of Boolean gates and fanout. . . . 29 4.3 Implied independence between faults of two subnetworks. . . . . . . . 31 4.4 An ATPG-based method for finding all faults that are independent of fault Fi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.5 Functional dominance collapsed faults [71] of c17 circuit. . . . . . . . 34 4.6 Independence graph for c17 benchmark circuit in Figure 4.5. . . . . . 36 4.7 Largest clique in the independence graph of Figure 4.6. . . . . . . . . 38 4.8 Examples of independence graphs, cliques and collapsed graphs. . . . 40 4.9 Steps 4 and 5: Collapsing the independence graph of c17. . . . . . . . 48 4.10 ALU dominance collapsed faults [71]. . . . . . . . . . . . . . . . . . . 50 4.11 Random vector fault simulation to obtain independence graph of 4-bit ALU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 xiii 4.12 Independence collapsing of c17 faults starting from a known clique. . 57 5.1 Generation of concurrent test. . . . . . . . . . . . . . . . . . . . . . . 60 5.2 Concurrent test generation for c17. . . . . . . . . . . . . . . . . . . . 62 5.3 Test set size comparison. . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.4 Test generation time comparison. . . . . . . . . . . . . . . . . . . . . 70 A.1 ALU dominance collapsed faults [71]. . . . . . . . . . . . . . . . . . . 81 xiv Chapter 1 Introduction Time is money! This is a phrase that is being put to use by almost everyone today. Lesser the time spent in doing something, more is the money saved. That thought is at the back of every test engineer?s mind. With the advances in science and technology, modern devices are becoming more complex every day. As the device complexity increases, testing becomes even more complex. This results in increased test time and higher test cost. At the same time, the manufacturing cost of a device is going down due to the higher levels of integration. All this has contributed to a test cost that is an increasing fraction of the total manufacturing cost. Hence the necessity of reducing the test cost. To decrease the test cost, the time required to test a device needs to be decreased. This time can be decreased if the number of tests required to test the device is reduced. So, we simply need to devise a test set that is small in size. It would be better to generate a small test set rather than to compact a large test set. This is because the result of compaction depends on the quality of the original test set. This idea has motivated the work presented in this thesis. 1.1 Problem Statement The problem solved in this thesis is: Find a minimal test vector set to detect all single stuck-at faults in a combinational circuit. 1 1.2 Contribution of Thesis We have developed a new test generation technique based on independence fault collapsing and concurrent test generation to produce minimal or near-minimal test sets for combinational circuits. A novel fault collapsing technique based on indepen- dent faults groups faults into nodes of a fully-connected graph. The nodes specify fault targets that are possibly concurrently-testable by an Automatic Test Pattern Generator (ATPG). The term ?concurrently-testable faults,? as defined in this the- sis, refers to faults that can be tested by a common test. We present new algorithms for generating concurrent tests. A simulation based approach for complete test gen- eration, including the independence fault collapsing and concurrent ATPG, is then presented. Results for benchmark circuits show that the method in fact does generate minimal test sets for some of the benchmark circuits, but may require improvements in algorithms and the program implementation for others. Two papers describing this work have been presented at the Ninth VLSI Design and Test Symposium (VDAT-2005) and the Fourteenth IEEE Asian Test Symposium (ATS-2005) and have appeared in the respective proceedings [8, 32]. 1.3 Organization of Thesis The thesis is organized as follows. In Chapter 2, we discuss the basics of testing and the relevant background on faults and test generation. In Chapter 3, the previ- ous work on test set compaction is discussed. In Chapter 4, the new independence fault collapsing algorithm is introduced and results for some benchmark circuits are presented. Chapter 5 discusses the new concurrent test generation technique with 2 results on benchmark circuits. Conclusions and ideas about future work directions are discussed in Chapter 6. 3 Chapter 2 Background The primary task of testing is to detect or diagnose the physical defects produced during the manufacturing process [27]. Testing means to find out whether a device or circuit is functioning properly. The basic process of testing a digital circuit is shown in Figure 2.1 [24]. Binary input patterns are applied to the circuit under test. The response of the circuit is compared with the stored correct response. If the responses match then the circuit under test is said to be good. DIGITAL CIRCUIT COMPARATOR --- 11 --- 01 --- -- --- -- --- 00 00 --- 11 --- -- --- -- --- 10 --- INPUT PATTERNS OUTPUT RESPONSES STORED CORRECT RESPONSE TEST RESULT Figure 2.1: Testing Process. 4 2.1 Fault Modeling Physical defects are those that can really occur in a circuit. During chip fabrica- tion many types of defects can occur, for example, breaks in signal lines, lines shorted to ground, excessive delays, etc. It might seem that if one wishes to ensure that a circuit is free from all defects, this could be done by checking that all the functions of the system are being performed correctly. The problem with this approach is the complexity of the test needed to completely check out even simple functions. A com- plete functional test of a simple module with just 65 inputs may take over 1000 years to complete. On the other hand, if we use information about the structure of the circuit, we could apply a relatively small number of tests to ensure that a given set of faults in the circuit did not exist. A representation of a defect at the abstracted function level is called a modeled fault or simply a fault [24]. In engineering, models bridge the gap between physical reality and mathematical abstraction [24]. The most important models in testing are those of faults. Fault modeling is the translation of physical defects to a mathematical construct that can be operated upon algorithmically and understood by a software simulator for the purposes of providing a metric for quality measurement [30]. A good fault model is one that is simple to analyze and yet closely represents the behavior of physical faults in the circuit. Logical faults represent effects of faults on the behavior of modeled systems. Physical defects are modeled as logical faults because the analysis of logical faults is much simpler than the mathematical analysis of physical defects. Logical fault models can represent many, though not all, physical failures. It is 5 technology-independent and, therefore, technology changes do not affect the methods for detection of such faults. 2.1.1 Stuck-at Faults One of the earliest and still widely used fault models is the stuck-at fault. It is believed that Eldred?s 1959 paper [33] laid the foundation for the stuck-at fault model, though the paper did not explicitly mention the stuck-at fault. The term ?stuck-at fault? first appeared in the 1961 paper by Galey, Norby and Roth [37]. In 1963, Poage presented a theoretical analysis of stuck-at faults [61]. Stuck-at faults are not only the simplest faults to analyze, but they also have proved to be very effective in representing the faulty behavior of actual devices. The simplicity of stuck-at faults is derived from their logical behavior; these faults are often referred to as logical faults [27]. The stuck-at fault is defined as a fault that forces a fixed value (either 0 or 1) on a signal line in the circuit, where the signal line can be an input or an output of a logic gate or flip-flop [24]. So, a stuck-at fault is assumed to affect only the interconnections between gates. The stuck-at faults are of two types, the stuck-at-1 (s-a-1 or sa1) and stuck-at-0 (s-a-0 or sa0). In general, many stuck-at faults can be present in a circuit. A circuit with n lines can have 3n ? 1 possible stuck line combinations [24, 27] as each line can be s-a-1 or s-a-0 or fault-free. All combinations except the one having all lines as fault-free are treated as faults. It is easy to recognize that even with moderately large values of n, the number of multiple stuck-at faults will be very large. Therefore, in practice, we only analyze single stuck-at faults. A circuit with n lines will then have at most 2n single stuck-at faults [24]. The number 6 of faults considered for testing is further reduced by fault collapsing as discussed in the next section. 2.2 Fault Collapsing Fault collapsing can be classified into two types; equivalence collapsing and dom- inance collapsing. Two faults are called equivalent if and only if they transform the circuit such that the two faulty circuits have identical output functions [24]. Equiv- alent faults are also called indistinguishable and have exactly the same set of tests. The set of all faults in a circuit can be partitioned into equivalence sets, such that all faults in a set are equivalent to each other. The process of selecting one fault from each equivalence set is called fault collapsing [24]. The fault set thus obtained is called an equivalence collapsed set. The relative size of the equivalence collapsed set with respect to the set of all faults is called the collapse ratio [24]: Collapse ratio = |Set of collapsed faults||Set of all faults| (2.1) Consider an n-input AND gate. It has a total of 2n+2 faults. Each of the n+1 s-a-0 faults on its input and output lines transforms the AND gate to a constant 0 output function. Thus all s-a-0 faults are equivalent. So, equivalence collapsing reduces the total faults to just n + 2. Similar results are derived for other Boolean gates as well. It must be noted that faults on a fanout stem and those on the branches cannot be collapsed. The example circuit shown in Figure 2.2(a) has 7 lines and a 7 (a) Example circuit with all faults. (b) Equivalence Collapsing. ( c ) Dominance Collapsing. sa0 sa1 sa0 sa1 sa0 sa1 sa0 sa1 sa0 sa1 sa0 sa1 sa0 sa1 sa0 sa1 sa1 sa0 sa1 sa1 sa1 sa0 sa0 sa1 sa1 sa0 sa1 sa1 Figure 2.2: Fault Collapsing. 8 total of 14 faults. Figure 2.2(b) shows the faults after equivalence collapsing. The number of faults is reduced to just 8. So the collapse ratio is 8/14 = 0.57. In equivalence fault collapsing we only collapse the faults that are indistinguish- able. If we are prepared to give up on the diagnostic resolution, i.e., the ability to distinguish between faults, more collapsing is possible. This is accomplished by using the concept of fault dominance. In large circuits, where coverage (detection) of faults rather than their exact location (diagnosis) is a more important, dominance fault collapsing may be desirable. Consider two faults F1 and F2. If all tests of fault F1 detect another fault F2, then F2 is said to dominate F1. The two faults are also called ?conditionally equivalent? with respect to the test set of F1 [24]. When two faults F1 and F2 dominate each other, they are then equivalent. So, dominance is a more basic relation than equivalence. Consider the n-input AND gate again. For the AND gate, the output stuck-at 1 fault dominates all the input s-a-1 faults. So, after dominance collapsing, the fault set reduces to n+1. For the example circuit of Figure 2.2, dominance collapsing reduces the number of faults to just 6 as shown in Figure 2.2(c). So, the collapse ratio now becomes 6/14 = 0.43. Dominance collapsing always results in a smaller test set than the equivalence collapsed set. A ?dominated? fault can become redundant due to the circuit structure. A fault that does not modify the input-output function of the circuit and cannot be detected by any test is called a redundant fault. If a dominated fault is redundant, no test would be obtained for the dominating fault even though that may be detectable. Though dominance collapsing produces a smaller collapsed fault set, the tests for the collapsed 9 faults may not guarantee a 100% fault coverage. Hence equivalence collapsing is more popular. The size of the fault set can be further reduced by performing functional collapsing. The faults in a hierarchical circuit can be collapsed using hierarchical fault collapsing [9, 10, 66, 70, 72]. 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. This leads to expanded definitions for equivalence and dominance [70, 72]. 2.3 Fault Simulation and Test Generation 2.3.1 Fault Simulation A logic simulator or true-value simulator computes the response of a given fault- free circuit for given input stimuli. A fault simulator determines the coverage of a given set of faults by a given set of input vectors through simulation of the circuit. The fault simulator indicates which faults are detected by each input vector. There are several methods of fault simulation, the simplest being the serial fault simulation. In this method, a single fault is introduced into the circuit model and simulation is run like true-value simulation. The circuit response is compared with the stored response of the fault-free circuit. As soon as the 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. 10 Another technique of fault simulation, which simulates more than one fault in one pass is called parallel fault simulation. The idea of parallel fault simulation is to use the bit-parallelism of logical operations in a digital computer [24]. 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. If fault dropping is used, the fault simulator will gain speed. The act of dropping a fault from the fault list as soon as it is detected is called fault dropping. Other fault simulation algorithms include deductive [15], concurrent [75, 76], TEST-DETECT [69], differential [29], etc. 2.3.2 Test Generation Test generation approaches can be classified into three categories: exhaustive, random and deterministic. If the number of inputs for a combinational circuit is small, exhaustive tests consisting of all possible input vectors to ensure 100% fault coverage can be used. Random test generation is a simple and low-cost method in which input vectors are generated randomly. A vector is retained only if new faults are detected by that vector. But, the number of random vectors needed for high fault coverages can be extremely large. So, random vectors are used in conjunction with deterministic vectors [5]. Random vectors are used for achieving an initial 60- 80% fault coverage. Then, tests are generated for the remaining faults by using deterministic methods. We restrict our discussion to combinational circuits. In order for a fault to be detected, the fault must be first activated by a test vector, and then its result must 11 be propagated to a primary output by the same vector. A test vector t activates a fault, when it generates an error by creating different values for faulty and fault free circuits at the site of the fault. The vector t propagates the error to a primary output w, when at least one path between the fault site and the output w has different value for faulty and fault free circuits. A line in the faulty circuit, whose value differs from that in the fault free circuit when subjected to the vector t is said to be sensitized for the fault f. The path composed of sensitized lines is called a sensitized path. Deterministic test pattern generation produces tests by processing a model of the circuit. It uses the notion of activation of the fault, and then the propagation of the faulty result through a sensitized path to a primary output. This is more expensive in terms of computational effort than the random method, but the resulting tests are often shorter and have higher coverage. Therefore, the cost of test application is much reduced relative to that of random testing. In deterministic 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 assignment 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 [36, 44]. 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 automatic deterministic test pattern generation algo- rithms are: D-algorithm [68], PODEM (Path-Oriented Decision Making) [38] and FAN (Fanout-Oriented Test Generator) [35]. 12 Chapter 3 Previous Work on Test Set Minimization Early research on test generation was directed toward efficiently generating a complete test set for a given circuit [35, 38, 68]. Once that objective was met, the next target was to generate smaller test sets. In the past two decades a lot of work has been done in the area of test set minimization. This work continues since the problem of generating a minimum size test set for a combinational circuit is NP- Hard [52]. Every new technique developed performs a little better than the previous one and hence motivates one to go even further as there is still hope of reaching the lower bound or just to close the gap further. By reducing the test sequence length, the memory requirements during test ap- plication and the test application time are reduced. The extent of test compaction possible for deterministic test sequences indicates that test pattern generators spend a significant amount of time generating test vectors that are not necessary. So, al- gorithms for finding compact test sequences remains an open problem in the area of efficient deterministic Automatic Test Pattern Generation (ATPG). Various techniques have been proposed for test set compaction, some of which are discussed in the following sections. These techniques have been grouped into categories depending on the type of compaction used. 13 3.1 Static Compaction Static compaction [1] is performed after the test set has been generated and is independent of the test generation process, so it has been referred to as post- generation compaction [26]. Several static compaction algorithms based on different heuristics exist in the literature and are discussed next. One technique of static compaction eliminates the redundant test vectors from the test set. A redundant test vector is a vector such that each fault detected by that vector is also detectable by some other vector in the test set. Most combina- tional ATPG methods use Random Pattern Generators (RPG) [3, 4] to obtain about 60% fault coverage [24], and then use an ATPG algorithm to generate tests for the remaining faults. This process can be one of the main sources of redundant test vec- tors. Redundant test vectors can be identified using set covering [21] or test vector reordering with fault simulation [64]. Another technique for removing the redendant vectors is reverse order fault simulation [73]. This technique is used in many test generation procedures to drop tests that detect faults that are also detected by tests generated later in the test generation procedure. A more sophisticated static compaction method is described by Goel and Ros- ales [39], 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 generated by an ATPG program, where the unassigned inputs are left as don?t care (X). An example of this technique is given below [24]: Consider the following test set: t1 = 01X t2 = 0X1 t3 = 0X0 t4 = X01 14 By first combining t1 and t3, and then t2 and t4, we obtain the compacted test set: t13 = 010 t24 = 001 When two compatible tests ta and tb are combined into one test tab, the detected faults will be the union of faults detected by ta and tb. Also, the compacted test set will vary depending on the order in which vectors are compacted. The influence of the order in which vectors are merged can be eliminated by using the integer linear programming (ILP) method [34, 43, 56]. ILP guarantees to find the minimal test set contained in the given vector set. Thus, the absolute minimality can be only expected if one starts with an exhaustive vector set. The ILP method has also been used to minimize the N-detection test sets [49], where each fault is detected by at least N different vectors in the set. The derivation of such tests is motivated by the observation that vector sets with N ? 5 have a higher coverage of real defects than the conventional single-detection test sets. One should, however, remember that the complexity of the ILP solution is exponential. Static compaction can be helpful in some situations because it does not require any modifications to the test generation procedure. Though static compaction adds to the test generation time, this time is usually small compared to the total test gen- eration time. But optimal static compaction algorithms are impractical, so heuristic algorithms are used. During static compaction, since the patterns in the given set are not modified or are only passively modified, i.e., only unspecified bits in patterns are modified, it achieves little reduction for a highly incompatible test set. Static compaction could still be useful after dynamic compaction is used, to further reduce 15 the length of the test sequence. The dynamic compaction techniques are discussed in the next section. 3.2 Dynamic Compaction Dynamic compaction [39] is a process that is integrated into the test generation process, generally attempting to generate vectors such that each detects a large num- ber of faults. So the fault coverage of each vector is maximized during test generation to reduce the total number of test vectors. In dynamic compaction, a currently gen- erated vector is used as constraints at primary inputs, and the next target fault is carefully selected such that a test pattern can be generated under the constraints [26]. One of the very first dynamic compaction techniques was presented by Goel and Rosales [39]. Here, every partially-complete vector from ATPG is processed immediately after it is generated, by assigning 0 or 1 to primary inputs with don?t care (X) values to enhance the vector to detect additional faults. Another dynamic compaction method [40] analyzes the internal circuit values produced by a partially- specified vector and selects a secondary target fault for which ATPG is more likely to succeed. An alternative approach to test compaction reduces the test set size by pruning the essential faults of some test vectors to make them redundant. A test vector becomes redundant if it detects no essential faults. A fault is essential if it is detected only by a single test vector [26, 45]. Compaction methods based on essential fault pruning 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 during the process. Algorithms based on essential 16 fault pruning fall into two categories. In the first category, the essential faults of the test vector to be eliminated are pruned by modifying other test vectors in the test set in such a way that they detect their already detected faults in addition to the pruned essential faults. Several algorithms presented in the literature [26, 67] belong to this category. On the other hand, in the second category, a set of N test vectors is replaced by a set of M < N new test vectors. The basic idea is to determine the faults that are detected only by one or more test vectors among the N test vectors to be replaced, and find M < N test vectors that detect all those faults. The algorithms presented by Kajihara et al. [46] belong to the second category. Another dynamic compaction technique is called double detection [45, 47]. This technique maximizes the number of faults that a new test vector detects out of the yet-undetected faults as well as out of the already-detected ones. Thus, it reduces the number of tests and allow tests generated earlier in the test generation process to be dropped. This technique also incorporates a static compaction technique called two by one which simply selects two vectors and replaces them by a single one, without loss of fault coverage. Dynamic compaction has also been done using fault simulation by the criti- cal path tracing algorithm to select a secondary target fault already activated by a partially-specified test vector [2]. A test generation technique, known as the sub- scripted D-algorithm [19], uses multiple path sensitization to derive a test for a given fault target such that a large number of other faults is also detected. A recent dynamic compaction technique [41] makes use of two algorithms called redundant vector elimination and essential fault reduction for generating compact test sets for combinational circuits. These algorithms along with dynamic compaction [39] 17 and a heuristic for estimating the lower bound are incorporated into an advanced ATPG system for combinational circuits called MinTest. The results [41] are better than any others published for the ISCAS85 [23] and ISCAS89 [22] benchmark circuits. But, this technique is computationally expensive. Though dynamic compaction produces smaller test sets (It has been experimen- tally shown that for large combinational circuits, dynamic compaction can reduce the test set by 50% [16]), most dynamic compaction techniques are computationally expensive. Dynamic compaction techniques based on indpendent faults are discussed in the next section. 3.3 Compaction Based on Independent Faults Compaction techniques based on independent faults fall under the dynamic com- paction category. But since our focus is on independent faults, we will discuss these techniques in a separate section. Two faults are said to be independent faults if and only if they cannot be detected by the same test vector [13, 14]. Akers and Krishnamurthy were the first to present test generation and com- paction techniques based on independent faults [13]. They define an independent fault set as one in which no two faults can be detected by the same test. The inde- pendent faults are good target faults for test generation, as the minimum test set size cannot be smaller than the size of the largest set of independent faults. Thus, the tests for independent faults can be considered necessary. Since finding a maximum independent fault set is a difficult problem, heuristics have to be used. Once a maximal set of independent faults is computed, tests are generated for that fault set. This process is repeated for a different maximal set of independent 18 faults. An attempt is then made to merge the two vector sets into a single set, smaller than the union of the two sets. Unspecified values are used for this purpose. This procedure is repeated for other maximal sets of independent faults, until all faults are detected [13]. Results for benchmark circuits are not given. Also 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. However, these fault sets were not used to generate minimal test sets. It has been proved [74] that many of the compatible fault sets published earlier [13] could not be covered by a single test vector. Though this technique did not provide the best results, it became the basis for later work on independent faults. A compaction technique based on independent faults is COMPACTEST [63]. Here, maximal compaction, which is an enhancement to dynamic compaction, is pro- posed to assign as many don?t care bits as possible in a test vector before aiming at the next target fault. To further increase the fault coverage of a generated pattern, a backtrace procedure called rotating backtrace is developed to activate as many sensi- tized paths as possible during test generation for detection of additional undetected faults. In addition to the above considerations, the compaction results are also af- fected by the order of target faults. The concept of compatible fault set [13] is applied to determine the order of target faults. COMPACTEST achieved improvements of up to 10 times over previously known test set sizes using simple and fast heuristics. Another technique based on independent faults, as presented by Tromp [74], is a modification of the original technique [13]. In this, the independent fault set procedure is improved to derive larger independent fault sets and to get a better estimate of the lower bound on the minimum test set size. The implication procedure was also 19 improved. The results presented for the ISCAS85 benchmark circuits showed that the technique was able to generate tests only for the smaller benchmark circuits and those results too were far from being optimal. An algorithm referred to as independent fault clustering is based on the concept of test vector decomposition [59]. Also, one of the compaction techniques discussed in the previous section also makes use of independent fault sets [41]. 3.4 The Berger and Kohavi Method In 1973, Berger and Kohavi presented a method for generating the minimum size test set for a fanout-free combinational circuit [20]. This method is discussed here because in the initial stages of the research presented in this thesis, we attempted to extend this method for any combinational circuit. But, despite our efforts, we were not able to do so. The method is discussed briefly with an example in the following paragraphs. We partition the test set T into two disjoint subsets T1 and T0 where T1 consists of all tests for which the circuit response is 1 and T0 consists of all tests for which the circuit response is 0. Also, R1 consists of all faults covered by T1 and R0 consists of all faults covered by T0. These two subsets are disjoint for a circuit that is free from fanouts. Besides, this circuit has only a single primary output. The union of any minimal subset of T0 covering R0 and any minimal subset of T1 covering R1 constitutes a minimal test set for the given circuit. The network structure is represented by two characteristic graphs denoted by G1 and G0 where G1 represents the network when its output is 1 and G0 represents the network when its output is 0. The gates in the network are represented in the graphs 20 A B C D F Figure 3.1: An example fanout-free circuit. as maxivertices and minivertices. A gate is represented by a maxivertex (M) when for its output to be sensitized all its inputs must be sensitized. A gate is represented by a minivertex (m) when for its output to be sensitized only one of its inputs needs to be sensitized. For example, the AND-gate will be a maxivertex in G1 while it will be a minivertex in G0. A simple fanout-free circuit is shown in Figure 3.1. Figure 3.2 shows the characteristic graphs for the circuit of Figure 3.1. The test generation procedure for the circuit in Figure 3.1 is shown in Figure 3.3. First consider the characteristic graph G1. In this graph, we start tracing back from the output and choose a subgraph such that during the backtracing when we reach a minivertex, we continue through exactly one of its inputs, and when we reach a maxivertex, we continue through all its inputs. We follow this backtracing until we reach primary inputs. Thus, backtracing traverses a subgraph. One such subgraph is shown by dashed lines in Figure 3.3 as G1 ?1. For the subgraph, we assign a 1 to the primary inputs present in the subgraph and a 0 to the remaining inputs that are 21 M M m m m M A B C D A B C D F F G 1 G 0 Figure 3.2: Characteristic graphs for circuit of Figure 3.1. absent from the subgraph. The subgraph G1?1 gives us the first test for the circuit, which for this example circuit is ?1100?. After we get a test, for every boundary maxivertex and for every boundary minivertex with just one input in the selected subgraph, we remove the edges con- nected to the input vertices and delete the corresponding input vertices. The bound- ary vertex is now regarded as an input vertex whose label is composed of the deleted input labels. Also, for a boundary minivertex with two or more input vertices in the selected subgraph, we remove the edge present in the selected subgraph and delete the corresponding input vertex. We repeat this process until the selected subgraph contains no boundary vertices. The graph obtained after this process is shown in Figure 3.3 as G1?2. It is shown by dashed lines as the second backtracing procedure covers the entire remaining graph. We repeat the process of finding a subgraph and the corresponding test, and then removing the vertices until no more vertices are left in the graph. Once we are done with graph G1, we repeat the entire process for graph G0. The steps for graph G0 22 G 1 -1 G 0 -1 G 1 -2 G 0 -2 M M m A B C D F M m C D F m m M A C F m m M A B C D F 1100 0011 1010 0101 Figure 3.3: Test generation for circuit of Figure 3.1. are shown in Figure 3.3 as G0 ?1 and G0 ?2. The tests obtained during this entire process on graphs G1 and G0 give us a minimal test set. For the example circuit of Figure 3.1, the minimal test set consists of 4 test vectors, 1100, 0011, 1010 and 0101. This work was later extended [62] for a small class of combinational circuits with nonreconvergent fanouts, but the work could not be extended for all classes of combinational circuits. Considering the complexity of such procedures, we note that the minimum test set problem for a very small class of combinational circuits may 23 T ( F1 ) T ( F2 ) v 1 v 2 v 3 Test set for fault F1 Test set for fault F2 Figure 3.4: Problem of finding a minimal test. be solvable in polynomial time. The minimum test set problem for other classes of combinational circuits remains NP-Hard. 3.5 Summary Consider two faults F1 and F2 in a combinational circuit and let T(F1) and T(F2) be the sets of all vectors that detect these faults, respectively (see Figure 3.4). Suppose an Automatic Test Pattern Generator (ATPG) targets F1 and finds the test vector v1. Fault simulation will indicate that F2 should be targeted next. If we obtain the test vector v3, static compaction will eliminate the vector v1 and we will get just v3 to cover both faults. However, if vector v2 is obtained as a test for F2 then the compacted set will contain both vectors. Thus, static vector compaction cannot guarantee optimality because its outcome may be affected by an unnecessary vector (v2 in this example) selected for a single-fault target (F2). If v1 has don?t care bits, sometimes a dynamic compaction procedure may convert it into v3, but this is not always guaranteed. Alternatively, dynamic compaction can try to iteratively replace the wrongly selected vectors [41]. This last method has been quite successful in achieving the optimum or near-optimum tests, but has a high time complexity. 24 Figure 3.4 shows a shortcoming of the single-fault ATPG algorithm, which must be overcome by compaction. The required test, v3, would have been found if we targeted both faults F1 and F2 together and sought a common test. These problems of (1) identifying suitable target fault sets and (2) concurrent test vector generation are discussed in the following chapters. Although, test generation for multiple target faults has been addressed in the literature [26, 27, 47], the algorithms and applications presented next are novel. 25 Chapter 4 Independence Fault Collapsing In this chapter, we will present a new algorithm for collapsing (grouping) faults into fault subsets such that all or most faults in each subset will have a single test. Steps required prior to applying the collapsing algorithm are also discussed here. The ideas and analyses given in this chapter have appeared in recent papers [8, 32]. 4.1 Fault Reclassification Consider two faults F1 and F2 with test sets T(F1) and T(F2), respectively. Four possible test relations can exist between the two faults. These are shown in Figure 4.1. The first two relations of equivalence and dominance [24] are commonly used for fault collapsing to reduce the number of faults to be targeted during ATPG. When two faults have the exact same test set, they are said to be equivalent faults. In such a situation, only one fault is targeted, as its detection guarantees the detection of the other fault. So, the size of the target fault list is reduced. Dominance collapsing further reduces the size of the target fault list. In an equivalence collapsed fault list when two faults F1 and F2 satisfy the relation T(F1) ? T(F2), meaning F1 dominates F2, fault F1 is dropped from the target fault set. An equivalence collapsed fault set always, and a dominance collapsed set mostly, generates tests covering all faults. But, the number of test vectors generated is often significantly larger than the minimum number required. The reason for this 26 T(F2) (a) F1 and F2 are equivalent. (b) F1 dominates F2. T(F1) T(F1) T(F2) (c) F1 and F2 are independent. T(F2) (d) F1 and F2 are concurrently testable. T(F1)=T(F2) T(F1) Figure 4.1: Test relations of faults F1 and F2 with tests T(F1) and T(F2). is explained by Figures 4.1 (c) and (d). Two faults, F1 and F2, in the collapsed set can be either independent [13, 14], i.e., they have no common test, or concurrently- testable, i.e., they have common tests. In the absence of any knowledge of these behaviors, we target both faults. If they are independent then we get two tests, which are essential. If they are concurrently testable then we may get one vector (if we were lucky) or two vectors, although only one would have been sufficient. Thus, independence and concurrently-testable properties of faults may be used to improve the efficiency of tests. We make the following observations: ? If two faults are independent, then no concurrent test is possible for them. A trivial case consists of two faults (with opposite polarity) of the same line. ? If two faults are equivalent, then any test for either fault is a concurrent test for both. 27 ? If one fault dominates the other fault, then any test for the dominated fault is a concurrent test for both faults. ? Two faults having neither a concurrent test nor an exclusive test [6], are both redundant. From the above observations we have the definitions for independent faults and concurrently-testable faults: Definition 1: Two faults are independent if and only if they cannot be detected by the same test vector [13, 14]. Definition 2: Two faults that neither have a dominance relationship nor are independent are defined as concurrently-testable faults. A pair of concurrently-testable faults has two types of tests: 1. Each fault has an exclusive test that does not detect the other fault [6]. 2. A common test that detects both faults. We define this as a concurrent test. Concurrently-testable faults have also been referred to as compatible faults in the literature [13]. 4.2 Methods of Finding Independence Relations Independent faults and concurrently-testable faults were defined in Section 4.1. Now, given a pair of faults, we need to find the relation that exists between them, i.e., whether they are independent of each other or they are concurrently-testable. (A dominance collapsed fault list is assumed.) We provide three methods for finding these relations as discussed in the following subsections. 28 sa0 sa1sa0 sa1 sa1 sa0 sa0 sa1 sa1 sa1 sa1 sa0 sa0 sa0 sa0 sa1 sa0 sa1 sa0 sa1 Figure 4.2: Structural independences of faults of Boolean gates and fanout. 4.2.1 Structural Independence Structural independences of faults of Boolean gates can be easily found and are shown in Figure 4.2. Here the faults shown are after equivalence and dominance fault collapsing. This is because the faults with equivalence or dominance relations cannot be independent. As an example, consider a 2-input AND gate. After dominance collapsing, the three faults in the target fault list are stuck-at-1 faults on each of the two inputs and a stuck-at-0 fault on the output. No pair of these faults has a common test and hence all three faults are independent of each other. The mutual independence of a pair of faults is shown by a two-sided arrow in Figure 4.2, which also shows the independence relations for other Boolean gates and a fanout. 4.2.2 Implied Independence Using the results of Section 4.2.1, many other independences can be determined: 29 1. Implication of equivalence: If two faults are equivalent then all faults that are independent of one fault are also independent of the other fault. 2. Implication of dominance: If one fault dominates a second fault then all faults that are independent of the first fault are also independent of the second fault. The proofs for the above statements can be easily given and so are eliminated here. The implied fault independences can be determined in a hierarchically described circuit. This technique would be based on hierarchical fault collapsing [9, 10, 66, 70, 72]. In hierarchical fault collapsing, faults are collapsed within small subcircuits and the collapsed fault sets are saved in libraries. The collapse data is stored in the form of a dominance graph, which contains pair-wise dominance relations among the collapsed fault set and the input and output faults of the subcircuit. The latter are included to determine equivalences between faults of two or more subnetworks when they are connected together. Similar to dominances and equivalences, independence relations remain valid through hierarchy. Theorem 1: If two faults inside a subnetwork are independent then they remain independent when the subnetwork is embedded in a larger combinational circuit. Proof: Consider two faults F1 and F2 of a combinational subnetwork, such that they are independent. First, consider the detection of these faults in the stand alone subnetwork. We apply vectors directly to the inputs of the subnetwork and observe its outputs for fault detection. Let v1 be the test set for fault F1 and v2 be the test set for fault F2 in the stand alone subnetwork. When this subnetwork is embedded in a larger combinational circuit, the inputs of the subnetwork will become internal lines in the larger circuit. A valid test for fault F1 is then a primary input vector that 30 ind. F4F1 F2 F3 F7 F8 ind. equ. implied independence implied independence F6F5 subnetwork Bsubnetwork A dom. Figure 4.3: Implied independence between faults of two subnetworks. applies a test from v1 to the embedded subnetwork and propagates the fault effect from the subnetwork output to a primary output of the larger circuit. Let V1 be the set of all such valid tests for F1 and V2 be the set of all valid tests for F2. Because F1 and F2 are independent in the subnetwork, v1 and v2 are disjoint sets. However, in a combinational circuit two different states on a set of internal signals cannot be produced by the same primary input vector. Therefore, V1 and V2 are also disjoint sets and that makes F1 and F2 independent faults of the larger circuit. Further, fault independences across the boundaries of subnetworks can be estab- lished by implications given above. An example is given in Figure 4.3. Consider two subnetworks A and B such that A feeds into B without fanout to other blocks of the circuit. If faults F1 and F2 are independent in A and faults F3 and F4 are equivalent in B, then F1 and F4 are independent. Similarly, if fault F6 dominates fault F5 in A and faults F7 and F8 are independent in B, then F5 and F8 are independent. 31 4.2.3 Functional Independence In a large circuit, not all independences can be derived by structural analysis. The most general independence relations are functional and we give a procedure to find them. Consider a single-output combinational circuit with output function C0 and two single stuck-at faults, Fi and Fj. We denote the faulty functions as Ci and Cj, respectively. For Fi and Fj to be independent, the following equation must be satisfied for all inputs: (C0 ?Ci).(C0 ?Cj) = 0 (4.1) Each clause in this equation is the test condition for a fault. Only for a test input the clause becomes true. The equation means that no input vector can make both clauses true, simultaneously. Equation 4.1 can be written as, (C0 ?Ci)C0 ?(C0 ?Ci)Cj = 0 (4.2) Equation 4.2 shows that if we construct a circuit (C0?Ci)C0, then a faulty circuit (C0 ? Ci)Cj will be indistinguishable when Fi and Fj are independent, i.e., they satisfy Equation 4.1. Figure 4.4 (a) shows an independence identification procedure using an ATPG that checks for redundant faults. Here, three copies of the circuit under test (CUT) are made. In the third copy a fault Fi is permanently inserted. All three copies have the same primary inputs and their outputs are connected as shown in Figure 4.4 (a) to derive a primary output for the composite circuit. An ATPG is used to detect faults in the top CUT. All faults that are found to be redundant are 32 independent of Fi. If a fault Fj is found to be testable, i.e., a test is generated, then that test is a concurrent test for faults Fi and Fj and can be saved for later use. It is assumed that both faults Fi and Fj are testable in the CUT. By successively inserting each fault in the lower copy of CUT in Figure 4.4 (a) all pair-wise fault independences can be determined. We might point out that this procedure can be expensive and may be useful for small circuits only, which can be handled by an ATPG. For larger circuits one has to rely on the structural independences. Figure 4.4 (b) shows how the procedure of we just described for a single-output circuit can be applied to a multiple-output circuit. Other procedures for independence identification use Boolean satisfiability or binary decision diagram analyses [77]. 4.3 Independence Graph and Independence Matrix The independence and concurrency relations between faults of a circuit are rep- resented using an independence graph and an independence matrix. We define inde- pendence graph and independence matrix in the next two subsections with the help of an example. The c17 ISCAS85 benchmark circuit shown in Figure 4.5 is used as the example circuit. The eleven stuck-at-1 faults marked as 1 through 11 in Figure 4.5 form a functional dominance collapsed fault set [71]. 4.3.1 Independence Graph An independence graph shows the independence relations between the faults of a circuit. Independence graph is also known as fault graph [77] or incompatibility graph [41] in the literature. Each fault is represented by a node and the independence 33 (a) Single output circuit. (b) Multiple output circuit. CUT C 0 CUT C 0 CUT(Fi) C i Primary Inputs Primary Outputs Redundant faults Fj are independent of Fi CUT C 0 CUT C 0 CUT(Fi) C i Primary Inputs Primary Output Redundant faults Fj are independent of Fi Figure 4.4: An ATPG-based method for finding all faults that are independent of fault Fi. Faults 1 through 11 are all s?a?1 type.2 4 1 6 8 7 3 9 10 11 5 Figure 4.5: Functional dominance collapsed faults [71] of c17 circuit. 34 of two faults is represented by an undirected edge between the corresponding nodes. This edge is undirected as independence is a bidirectional property, i.e., if fault 1 is independent of fault 2 then fault 2 is also independent of fault 1. If all pairwise independences are known, then the absence of an edge between two nodes means that the two faults are testable by a common test; they can be equivalent, dominant or concurrently-testable. If the graph contains a dominance collapsed fault set, then the absence of an edge between two nodes means that the two faults are concurrently- testable. For the c17 benchmark circuit of Figure 4.5 we have a set of eleven faults, num- bered 1 through 11 in the figure, obtained after functional dominance collapsing. We construct the independence graph of Figure 4.6 where each fault is represented as a node and an undirected edge between two nodes indicates the independence of the corresponding faults. The edges in the independence graph represent functional in- dependences and were found using the ATPG-based procedure of Figure 4.4(b). The ATPG used was HITEC [58]. Since this graph is small, we can easily identify several largest cliques of size four. Such identification will be impossible for large circuits due to the high complexity of the maximum clique identification problem [12]. The heuristic algorithm of Subsection 4.4 is found to work well in such cases. In general, for large circuits one must rely only on structural independences and, therefore, the independence graph will be only partially complete. This will affect the minimality of the tests. In the following discussion, however, we will assume that all edges of the independence graph are known. 35 1 2 3 4 5 6 7 8 9 10 11 Figure 4.6: Independence graph for c17 benchmark circuit in Figure 4.5. 4.3.2 Independence Matrix An alternative representation of the independence graph is its connectivity ma- trix, which we will call the independence matrix. The independence matrix for the eleven-node graph of Figure 4.6 is shown in Table 4.1. Here an edge between the ith and jth faults is indicated by 1s at the intersections of the ith row (column) and jth column (row). The independence matrix has a diagonal symmetry because independence is a bidirectional property. 4.4 Algorithm for Independence Fault Collapsing Theorem 2: A lower bound on the number of tests required to cover all faults of an irredundant combinational circuit is the size (number of nodes) of the largest clique in the independence graph [13]. 36 Table 4.1: Independence matrix for c17 benchmark circuit in Figure 4.5. Fault 1 2 3 4 5 6 7 8 9 10 11 1 0 1 1 1 1 1 0 0 1 0 1 2 1 0 0 1 1 0 1 0 0 0 1 3 1 0 0 0 1 1 1 1 0 1 1 4 1 1 0 0 1 0 1 0 0 0 1 5 1 1 1 1 0 0 0 1 1 1 0 6 1 0 1 0 0 0 1 1 1 0 0 7 0 1 1 1 0 1 0 1 1 0 0 8 0 0 1 0 1 1 1 0 1 1 1 9 1 0 0 0 1 1 1 1 0 1 1 10 0 0 1 0 1 0 0 1 1 0 1 11 1 1 1 1 0 0 0 1 1 1 0 A clique is defined as a fully-connected subgraph, i.e., a subgraph in which every node is connected to every other node. Thus, the largest clique in the independence graph of Figure 4.6 has a size 4. This is shown in Figure 4.7 by a dashed line enclosure. The above theorem follows from the fact that a test for a fault in the clique will not detect any other fault in that clique. Notice that Theorem 2 is valid even for an independence graph where the in- dependence edges are only partially known. However, the size of the clique will be largest when all independences are known. In that case the lower bound on the number of tests will be smallest. Finding the largest clique in a graph (or even the chromatic number, i.e., the size of the largest clique) is an NP-complete problem [11, 12]. Therefore, we will not try to determine it directly. Besides, our aim is to find the targets for test generation that will lead to the minimal test set. Heuristically, 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 have edges connecting to the two nodes will have 37 1 2 3 4 5 6 7 8 9 10 11 Figure 4.7: Largest clique in the independence graph of Figure 4.6. 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. We have found that for larger circuits it produces non-optimum results. For improved collapsing, we propose a new heuristic method in the next subsection. Once the independence graph is collapsed into a fully-connected graph (a single clique), the faults in each node label may require one or more tests. However, the concurrent tests generated for one node cannot completely detect all faults in any other node. Suppose the ith node contains ki faults, then any pair of those faults can be detected by a concurrent test. Therefore, we have 38 Theorem 3: Given that the independence graph of a circuit is collapsed into a fully-connected (single-clique) graph in which each node contains a group of faults such that: 1. no two faults in a node are pair-wise independent, and 2. for any pair of nodes, one node contains at least one fault that is independent of at least one fault contained in the other node. Following bounds on the number of tests for that circuit exist: Nc ? Number of tests ? N?csummationdisplay i=1 ceilingleftBiggk i 2 ceilingrightBigg (4.3) where, Nc is the size of the largest clique and N?c is the number of nodes in the single- clique collapsed graph (N?c ? Nc). Proof: The lower bound on the number of tests follows from Theorem 2 [13]. The proof for the upper bound is as follows. In the collapsed graph the faults grouped in any node are pair-wise concurrent and hence the maximum number of tests required for any node is the number of faults divided by two. If the number of faults in a node is odd, then we round off to the next higher integer because besides detecting pairs of faults, one additional test may be needed to detect a single remaining fault. Notice that Nc is the chromatic number or the size of the largest clique [11]. It may not always be possible to collapse the independence graph into a clique of Nc nodes. Figure 4.8 shows three example graphs with Nc = 2,2 and 3, respectively. Only the first graph can be collapsed with Nc = N?c. These graphs were not obtained from real circuits, although actual circuit displaying such behavior can be found. 39 3 1 2 34 2, 41, 3 1 6 2 1, 3 6 1 2 3 1, 3 graph Independence Maximal clique cNsize, graph Collapsed 2 2 3 Collapsed graph cN?size, 2 3 4 4 5 2, 5 4 4 5 2, 5 4 Figure 4.8: Examples of independence graphs, cliques and collapsed graphs. When N?c > Nc, the circuit will essentially require more than Nc tests and the lower bound of Theorem 2 will be exceeded. An example is the four-bit ALU circuit for which an independent fault set size (Nc) of 11 has been identified [14] but the circuit needs at least 12 tests for detecting all faults. When the independence graph is collapsed into N?c nodes, Theorem 3 shows that the number of tests a node contributes has an upper bound. A good collapsing algorithm will attempt to group faults such that the number of tests contributed by 40 each node is minimized. In the following we use similarity heuristics to find ?good? groupings. 4.4.1 Definitions Before we discuss the independence fault collapsing algorithm, we will define two metrics that can be directly computed from the independence matrix: Definition 3: Degree of independence (DI): The degree of independence of a fault i is the number of edges attached to its fault node and is computed by adding all the elements of either the ith row or the ith column of the independence matrix: DI(fault?i) = Nsummationdisplay j=1 xij = Nsummationdisplay j=1 xji (4.4) where xij is the element belonging to the ith row and jth column of the N ? N independence matrix (N is the number of faults). Thus, for the fourth fault, the matrix of Table 4.1 gives: DI(4) = 11summationdisplay i=1 x4i = 5 (4.5) The DI for each fault of circuit in Figure 4.5 is shown in Table 4.2. Definition 4: Similarity metric (SIM): This is a measure defined for a pair of faults that determines how similar they are in their independence and concurrent- testability with respect to the entire fault set of the circuit: SIM(fault?i,fault?j) = Nxij + (1?xij) Nsummationdisplay k=1 |xik ?xjk| (4.6) 41 Table 4.2: Degree of Independence for c17 benchmark circuit of Figure 4.5. Fault 1 2 3 4 5 6 7 8 9 10 11 DI 1 0 1 1 1 1 1 0 0 1 0 1 7 2 1 0 0 1 1 0 1 0 0 0 1 5 3 1 0 0 0 1 1 1 1 0 1 1 7 4 1 1 0 0 1 0 1 0 0 0 1 5 5 1 1 1 1 0 0 0 1 1 1 0 7 6 1 0 1 0 0 0 1 1 1 0 0 5 7 0 1 1 1 0 1 0 1 1 0 0 6 8 0 0 1 0 1 1 1 0 1 1 1 7 9 1 0 0 0 1 1 1 1 0 1 1 7 10 0 0 1 0 1 0 0 1 1 0 1 5 11 1 1 1 1 0 0 0 1 1 1 0 7 DI 7 5 7 5 7 5 6 7 7 5 7 The similarity metric ranges between 0 and N. When fault ? i and fault ? j are independent, xij = 1, and the metric assumes the largest value N. When the faults are not independent, the metric is simply the Hamming distance between the corre- sponding row or column vectors of the independence matrix. Although a 0 value may not indicate equivalence of any pair of faults, the similarity metric of two equivalent faults will be exactly 0. The pair-wise similarity metrics for the eleven faults of the c17 benchmark circuit of Figure 4.5 are shown in Table 4.3. Note that a smaller value of the similarity metric for two faults means that they are likely to be detected by the same test. Thus, smaller values point to concurrent- testability and larger values point to independence. The similarity metric and similarity index (defined in Subsection 4.4.2) are used to determine how likely a fault is to be detected by a vector that also detects another fault or a group of faults. Notice that the faults that we are considering are neither equivalent nor have dominance relations because of the prior fault collapsing. These 42 Table 4.3: Similarity Metrics for c17 benchmark circuit of Figure 4.5. Fault 1 2 3 4 5 6 7 8 9 10 11 1 0 11 11 11 11 11 3 4 11 4 11 2 11 0 4 11 11 6 11 6 4 6 11 3 11 4 0 4 11 11 11 11 0 11 11 4 11 11 4 0 11 6 11 6 4 6 11 5 11 11 11 11 0 4 3 11 11 11 0 6 11 6 11 6 4 0 11 11 11 4 4 7 3 11 11 11 3 11 0 11 11 5 3 8 4 6 11 6 11 11 11 0 11 11 11 9 11 4 0 4 11 11 11 11 0 11 11 10 4 6 11 6 11 4 5 11 11 0 11 11 11 11 11 11 0 4 3 11 11 11 0 measures differ from the ?level of similarity? defined in the literature [65], which determines how close a fault is to being equivalent or dominant with respect to another fault. 4.4.2 Independence Fault Collapsing Algorithm Now that we have defined the metrics that we will use for collapsing, let us discuss the independence fault collapsing algorithm in detail. This algorithm collapses the graph or groups the faults into sets of concurrently-testable faults. At this point we already have the independence matrix generated. We will use this matrix for collapsing the faults. Algorithm: Similarity-Based Independence Fault Collapsing 1. Compute the degree of independence for each fault. 2. Arrange the faults in order of decreasing degree of independence. 3. Compute the similarity metric for each pair of faults. 43 4. Starting with an empty graph, place faults in the new order of decreasing degree of independence. Create the first node consisting of the fault with the highest degree of independence. 5. Until all faults have been placed, place a fault F with the same or the next highest degree of independence: ? Compute a similarity index for F for each existing node i as: MaxKk=1SIM(F, kth fault of node i) where K is the number of faults in node i. ? If the similarity index for all nodes is N (maximum value), i.e., all nodes contain at least one fault that is independent of F, then create a new node for F. Otherwise, place F in the node for which it has the smallest similarity index. This algorithm, based on a ?similarity heuristic?, tries to group those faults to- gether that are likely to have a single concurrent test. The algorithm groups faults into nodes such that the similarity metrics among faults within each group are mini- mized. Recall that the similarity metric is a pair-wise measure. Its minimum value, 0, signifies that the two faults, although not equivalent, are close to being equivalent. Larger values of the similarity metric point to the reducing size of the common tests for the two faults. The maximum possible value, which equals the total number of faults (N), indicates a null set for the common tests, i.e., the faults are independent. Thus, by grouping the faults together that are ?nearly? equivalent we increase the 44 Table 4.4: Step 1: Computation of degree of independence (DI) for each fault. Fault 1 2 3 4 5 6 7 8 9 10 11 DI 1 0 1 1 1 1 1 0 0 1 0 1 7 2 1 0 0 1 1 0 1 0 0 0 1 5 3 1 0 0 0 1 1 1 1 0 1 1 7 4 1 1 0 0 1 0 1 0 0 0 1 5 5 1 1 1 1 0 0 0 1 1 1 0 7 6 1 0 1 0 0 0 1 1 1 0 0 5 7 0 1 1 1 0 1 0 1 1 0 0 6 8 0 0 1 0 1 1 1 0 1 1 1 7 9 1 0 0 0 1 1 1 1 0 1 1 7 10 0 0 1 0 1 0 0 1 1 0 1 5 11 1 1 1 1 0 0 0 1 1 1 0 7 DI 7 5 7 5 7 5 6 7 7 5 7 possibility of finding a single concurrent test for the group. Let us see the example of the c17 benchmark circuit of Figure 4.5. The degree of independence is first calculated for each fault as shown in Table 4.4. The faults are then arranged in order of decreasing degree of independence (Table 4.5). The order of the faults is as follows (value shown in parenthesis is the degree of independence): 1(7), 3(7), 5(7), 8(7), 9(7), 11(7), 7(6), 2(5), 4(5), 6(5), 10(5). Then, the similarity metric is calculated for each pair of faults (Table 4.6). The step by step details of the collapsing procedure are shown in Figure 4.9. The number shown inside the node is the fault number while the number shown outside the node is the similarity index for the next fault with that node. We start with fault 1 and create the first node for it. Since SIM(3, 1) = 11 (indicating independence), we create a new node for fault 3. Similarly, a new node is created for fault 5 because it is independent of both faults 1 and 3. Next, fault 8 is placed in the node with fault 1 because it has the lowest similarity index for that node. Proceeding in similar 45 Table 4.5: Step 2: Faults ordered according to decreasing degree of independence. Fault 1 3 5 8 9 11 7 2 4 6 10 DI 1 0 1 1 0 1 1 0 1 1 1 0 7 3 1 0 1 1 0 1 1 0 0 1 1 7 5 1 1 0 1 1 0 0 1 1 0 1 7 8 0 1 1 0 1 1 1 0 0 1 1 7 9 1 0 1 1 0 1 1 0 0 1 1 7 11 1 1 0 1 1 0 0 1 1 0 1 7 7 0 1 0 1 1 0 0 1 1 1 0 6 2 1 0 1 0 0 1 1 0 1 0 0 5 4 1 0 1 0 0 1 1 1 0 0 0 5 6 1 1 0 1 1 0 1 0 0 0 0 5 10 0 1 1 1 1 1 0 0 0 0 0 5 DI 7 7 7 7 7 7 6 5 5 5 5 ways, all other faults are placed as shown in Figure 4.9. The last graph in Figure 4.9 is the final collapsed graph, which contains just four nodes. The groups are also shown in Table 4.7. The edges in the collapsed graph indicate that a minimal set of tests for faults in any node cannot completely cover the faults in any other node. Formula 4.3 gives the lower and upper bounds on the number of test vectors as 4 and 7, respectively. In Chapter 5, we will see that concurrent test generation provides four vectors for this circuit. We make several observations about the independence collapsing algorithm of this section: 1. The algorithm will always terminate with a collapsed graph because the faults are sequentially placed on the collapsed graph and the placement procedure results in a definite placement of a fault before next fault is placed. 46 Table 4.6: Step 3: Computation of similarity metric for each pair of faults. Fault 1 3 5 8 9 11 7 2 4 6 10 1 0 11 11 4 11 11 3 11 11 11 4 3 11 0 11 11 0 11 11 4 4 11 11 5 11 11 0 11 11 0 3 11 11 4 11 8 4 11 11 0 11 11 11 6 6 11 11 9 11 0 11 11 0 11 11 4 4 11 11 11 11 11 0 11 11 0 3 11 11 4 11 7 3 11 3 11 11 3 0 11 11 11 5 2 11 4 11 6 4 11 11 0 11 6 6 4 11 4 11 6 4 11 11 11 0 6 6 6 11 11 4 11 11 4 11 6 6 0 4 10 4 11 11 11 11 11 5 6 6 4 0 Table 4.7: Independence fault collapsing of c17 faults. Fault Faults Group No. (see Figure 4.5) 1 1, 8 2 2, 3, 9 3 4, 6, 10 4 5, 7, 11 47 1,8 3, 9, 2 5, 11, 7 4, 6, 10 1 3 5 1, 8 3 5 1 1 3 1, 8 3, 9 5 1, 8 3, 9 5, 11 1, 8 3, 9 5, 11, 7 1, 8 3, 9, 2 5, 11, 7 1,8 3, 9, 2 5, 11, 7 4 1,8 3, 9, 2 5, 11, 7 4, 6 11 11 11 4 11 11 11 11 0 11 0 11 11 3 11 11 11 4 11 11 11 11 11 11 6 11 11 11 6 Figure 4.9: Steps 4 and 5: Collapsing the independence graph of c17. 48 2. The size of the collapsed graph cannot be smaller than the maximal clique size Nc (chromatic number) of the independence graph. This is because no two faults that are independent can be placed in the same node. 3. Whenever a circuit requires more tests than the lower bound of Theorem 2 or 3, the collapsed graph will definitely have more than Nc nodes, i.e,. N?c > Nc. This happens when the independence graph has more than one maximal clique and those cliques are connected in certain ways. While a complete analysis of such graphs may be complex, the phenomenon is illustrated by the examples of Figure 4.8. 4.4.3 ALU Example The algorithm of Section 4.4.2 was applied to the 74181 4-bit ALU circuit of Figure 4.10. The Exclusive-OR gates in the circuit were expanded as four NAND gates each as the ATPG program [58] and fault simulator [57] used for generating the matrix did not recognize XOR gates. The independence matrix was generated for the 84 dominance collapsed faults shown in Figure 4.10 (92 faults are obtained through functional dominance collapsing [71] of which 8 redundant faults are removed). The independence fault collapsing procedure collapsed the 84 faults into 12 nodes. These groups are shown in Table 4.8. Chapter 5 shows that 12 tests are obtained for the ALU circuit. The principal idea of the collapsing algorithm is to group those faults together that are likely to have a concurrent test. The similarity index and degree of inde- pendence play important roles in this algorithm. Otherwise, the grouping of faults 49 c_n 27 6 26 75 8 20 30 16 1513 14 22 33 4 18 31 2 36 s3 s2 s1 s0 b3 a3 b2 a2 a0 b0 a1 b1 38 23 12 119 10 21 29 46 45 44 42 41 40 24 37 17 51 50 49 35 32 39 19 43 4748 525453 m f3n pn gn f2n a=b f1n f0n 56 58 59 57 25 28 31 34 61 60 55 64 67 65 62 78 79 68 70 69 71 7372 74 77 76 75 81 82 83 80 84 stuck?at?1 stuck?at?0 c_n+4 6366 Figure 4.10: ALU dominance collapsed faults [71]. 50 Table 4.8: Independence collapsed fault sets for 4-bit ALU. Node Maximum No. of No. similarity Faults Fault numbers (see Figure 4.10) index 1 21 5 53, 58, 72, 66, 21 2 29 3 56, 64, 17 3 41 8 54, 48, 59, 73, 70, 67, 23, 6 4 37 3 55, 63, 51 5 43 5 34, 77, 10, 14, 36 6 49 6 61, 74, 42, 46, 50, 38 7 49 7 31, 76, 78, 16, 80, 39, 60 8 38 14 52, 47, 43, 57, 30, 71, 69, 68, 33, 65, 19, 79, 84, 3 9 47 8 28, 75, 29, 22, 18, 83, 8, 44 10 41 8 24, 25, 27, 4, 12, 81, 7, 40 11 43 8 62, 26, 32, 2, 13, 5, 9, 49 12 36 9 20, 82, 35, 41, 45, 15, 11, 1, 37 could have been done almost arbitrarily after we found the largest clique in the in- dependence graph using any available maximum clique program. To illustrate the effectiveness of our independence collapsing algorithm, we reworked the ALU exam- ple. Appendix A shows the collapsed faults sets for the ALU circuit of Figure 4.10 without ordering the faults according to decreasing degree of independence. We were able to collapse the graph to a low of 15 nodes, and we obtained a test set of 17 vectors for those 15 groups of faults. This shows the importance of ordering the faults before we start the collapsing procedure. 4.5 Simulation-Based Independence Fault Collapsing There are practical difficulties in implementing the procedures explained in Sec- tion 4.4 for large circuits. First, functional dominance fault collapsing [71], used prior to independence collapsing, is based on ATPG and is complex (the time taken for 51 functional dominance collapsing for the ALU circuit was approximately 45 minutes). Second, the independence graph generation procedure of Section 4.2.3 is also based on ATPG (the time taken to generate the independence matrix was approximately 50 minutes). In this section, we give an alternative procedure using a conventional fault simulator for generating the independence matrix. The only requirement is that the fault simulator should simulate without fault dropping, as is usually needed in diagnosis applications. The technique has been described in a recent paper [8]. 4.5.1 Algorithm 1. Start with a fully-connected independence graph for an equivalence collapsed fault set (structural collapsing only), i.e., assume initially all faults are indepen- dent of each other. 2. Simulate random vectors without fault dropping to remove edges between faults detected by the same vector. Stop the random vector simulation when a large number of vectors do not remove any new edges. 3. Apply the independence fault collapsing algorithm of Section 4.4.2 to the gen- erated independence matrix. The procedure is illustrated for the 4-bit ALU (74181) circuit. We begin with the structural equivalence collapsed fault set as obtained from any ATPG or fault simula- tion program. For the 4-bit ALU circuit this set contains 301 stuck-at faults including 8 redundant faults. Exclusive-OR gates in the circuit were expanded as four NAND gates each. Assuming no prior information about the concurrent detectability (com- patibility) of faults, initially a fully connected independence graph was constructed 52 Table 4.9: Simulation-based independence fault collapsing for 4-bit ALU (74181) circuit. Group Number Maximum Similarity No. of faults index 1 9 96 2 15 127 3 11 94 4 6 108 5 11 126 6 17 136 7 11 124 8 16 124 9 16 127 10 22 115 11 22 111 12 56 104 13 81 104 for 301 faults. This graph contains 301 ? 301 = 90,601 edges. The fault simulator HOPE [55] was used to simulate random vectors without fault dropping. The upper curve in Figure 4.11 shows the fault coverage reaching 293 (all detectable faults) at vector number 193. All edges among the faults detected by each vector were deleted from the independence graph, reducing the number of edges from 90,601 as shown by the lower curve in Figure 4.11. For example, the first vector detected 73 faults and caused the deletion of 73?73 = 5,329 edges. The simulation was stopped at 2,000 random vectors when it was found that about 200 vectors did not remove any new edge. This left 20,004 or about 22% of the edges. In this graph, there were eight nodes that were still connected to all other nodes giving them a degree of independence 301. An ATPG [54] was used to derive tests or prove redundancy. Since these faults were found to be redundant, the corresponding nodes and all edges attached to them were removed leaving 293 nodes. 53 0 25000 50000 75000 100000 0 500 1000 1500 2000 2500 Random vectors Number of edges 0 80 160 240 320 Faults detected 90601 Faults detected (293) Number of edges in graph (20004) 301 Figure 4.11: Random vector fault simulation to obtain independence graph of 4-bit ALU. The similarity-based independence collapsing algorithm of Section 4.4.2 grouped 293 faults into 13 groups with sizes ranging from 6 to 81 faults. The groups are shown in Table 4.9. Chapter 5 shows that 12 tests were generated for these 13 groups. It has to be noted that the number of groups generated here is more than the optimal result of 12 because when random vectors are used, not all fault-pair relations are found. Some pairwise concurrent faults may still be treated as independent faults just because the set of random vectors did not have a vector that would detect these faults at the same time. Hence, the collapsing procedure may generate more groups. So, Equation 4.3 would now give a different higher bound on the number of tests. 54 Table 4.10: Independence fault collapsing of ripple-carry full-adders. Circuit Independence Collapse Groups 1-b adder 5 2-b adder 5 4-b adder 5 8-b adder 7 16-b adder 7 32-b adder 7 4.5.2 More Results The algorithm of Section 4.4.2 was applied to ripple-carry full-adder circuits ranging from 1-bit to 32-bits. The simulation-based method of graph generation was used. The results are shown in Table 4.10. The adders are known to have a minimal set of 5 tests irrespective of their size [48]. From Table 4.10 it can be seen that the collapsing procedure produced the minimal result until the 4-bit adder and the results slightly deviated for the remaining adder circuits. Table 4.11 shows the independence fault collapsing results for the ISCAS85 com- binational benchmark circuits. The last column shows the total time required for generating the independence matrix as well as collapsing the graph. It can be seen from the table that the time required increases as the size of the circuit increases. This is because the technique is based on fault simulation and as the circuit size in- creases, the number of faults in the circuit increases and so simulation time increases. But, this increase is linear or quadratic and not exponential. The concurrent test generation results for these circuits are presented in the next chapter. 55 Table 4.11: Independence fault collapsing on ISCAS85 benchmark circuits. Circuit Independence Collapse Groups CPU Time (s)* c17 4 0.04 c432 30 2.0 c499 52 3.4 c880 24 4.3 c1355 84 6.9 c1908 106 10.9 c2670 81 16.3 c3540 107 24.7 c5315 92 41.8 c6288 23 64.9 c7552 190 62.9 * Sun Ultra 5 4.6 An Alternative Method for Independence Fault Collapsing In this section we propose another method for independence fault collapsing which is based on cliques. This method uses the same algorithm proposed in Sec- tion 4.4.2, but instead of starting with an empty graph in step 4, we start with a maximum clique. This maximum clique is determined prior to applying the collaps- ing algorithm. There are several algorithms proposed in literature for finding the maximum clique [25, 60, 53]. We use a tool called Reactive Local Search solver [17] which is based on the algorithm of Battiti and Protasi [18] for finding a maximal clique of a graph. The input file for this tool is in the DIMACS (Center for Dis- crete Mathematics and Theoretical Computer Science) [31] format. The details of the DIMACS format are given in Appendix B. This method was applied to the c17 benchmark circuit of Figure 4.5. A maximum clique was found by using the Reactive Local Search solver [17]. One run of the tool gave the maximum clique formed by faults 6, 7, 8 and 9. Then steps 1, 2 and 3 from 56 11 3 4 11 11 11 11 0 6 8 7 9 6 8 7, 1 9 4 11 11 11 4 11 11 11 6 8 7, 1 9, 3 6, 5 8 7, 1 9, 3 11 11 6 4 11 6 11 11 6, 5 ,11 8 7, 1 9, 3 6, 5, 11 8 7, 1 9, 3 2 11 5 11 11 6, 5, 11 8, 4 7, 1, 10 9, 3, 2 6, 5, 11 8, 4 7, 1 9, 3, 2 Figure 4.12: Independence collapsing of c17 faults starting from a known clique. 57 Table 4.12: Results for the c17 circuit. Fault Faults Concurrent Group No. (see Figure 4.5) test vector 1 6, 5, 11 01100 2 7, 1, 10 10011 3 8, 4 10100 4 9, 3, 2 01111 the algorithm in section 4.4.2 were performed. For steps 4 and 5, this clique was used as the starting graph. While performing steps 4 and 5, the faults in the starting clique were omitted as they were already grouped. This collapsing procedure is shown in Figure 4.12. Notice that this collapsing method produced different groups than the previously obtained groups. Also the concurrent test generation for these new groups came up with a different set of four (minimal) tests, which are shown in Table 4.12. For the 74181 circuit, we used the 301-node independence graph obtained by the simulation-based technique in Section 4.5. Reactive Local Search solver [17] found a clique of size 11 which agrees with the lower bound (number of independent faults) for this circuit as given in [14]. But, the minimum number of tests required for this circuit is 12 which is greater than the lower bound [14]. The advantage of this method is that we already have the nodes, and we just have to place the remaining faults into these nodes without forming new nodes unless necessary. So we would always have a chance to come up with the minimum number of nodes. But, the problem of finding the maximal clique is NP-hard and so the tool cannot find the maximal clique in a given small time (the tool was run on the server provided by the website, which allowed a maximum run time of only 600 seconds for a given problem). So, we did not apply this method to the other benchmark circuits. 58 Chapter 5 Concurrent Test Generation Independence fault collapsing discussed in Chapter 4 helped group the faults that are likely to be detected by the same test vector into a single group. Now that the faults are grouped together, we need a technique to find a single test that would detect all or most of the faults in a group. In this chapter we define a new type of test, called ?concurrent test,? for a combinational circuit. Also, we present new techniques to generate these concurrent tests. Some techniques and examples of this chapter have appeared in recent papers [8, 32]. Definition 5: Given a set of target faults, a concurrent test is an input vector that detects all (or most) faults in the set. When concurrent tests are generated for fault sets obtained from independence fault collapsing, minimal or near-minimal tests can be expected. Although the general problem of concurrent test generation relates to a set of faults, for simplicity, we will consider two faults, F1 and F2. Figure 5.1 shows the Boolean satisfiability and multi-valued ATPG formulations of the concurrent test problem. C0 is the fault-free function and Ci is the function with fault Fi permanently injected. Any vector that satisfies the following equation is a concurrent test for F1 and F2. This is the Boolean satisfiability solution shown in Figure 5.1(a). (C0 ?C1).(C0 ?C2) = 1 (5.1) 59 0 1 C C C C2 0 test vector (a) Boolean satisfiability. 1 0 1 Concurrent test vector Concurrent 0/1 0/1 0/1 (b) Five or nine valued ATPG. 1 fault F1 fault F2 CUT C0 CUT C CUT C 0 Figure 5.1: Generation of concurrent test. 60 Figure 5.1(b) shows a multi-valued ATPG solution. Notice that the ATPG re- quires three copies of the circuit (CUT) and the detection of a multiple fault whose components, F1 and F2, are in two separate copies. There are two ways of generating a concurrent test. One way is to use a known method of modeling a multiple fault [51] as a single fault for any available ATPG program. The disadvantage of this method is that the circuit the ATPG program has to deal with is now n+1 times larger when the concurrent fault set has n faults. The second method, which does not duplicate the circuit, is given in the next section. 5.1 The Concurrent-D Algebra Consider two faults, F1 and F2. The state of any line in the circuit is either (1) unaffected by both faults, (2) affected by F1, (3) affected by F2, or (4) affected by both F1 and F2. In the first case the line assumes a value from the set 0, 1, X. In the second case we denote it by D1 or D1, where D1 has the same meaning as in the D-algorithm [69]. Similarly, for the third case the line value is denoted as D2 or D2. In the fourth case, where both faults affect the line, its state is denoted by D12 or D12. Thus, there are nine values that a line can have. For a two-input AND gate, the function is shown in Table 5.1. Figure 5.2 shows the concurrent test generation for the c17 benchmark circuit of Figure 4.5. Faults 2, 3 and 9 shown in Figure 5.2 are all of stuck-at-1 type and were grouped together using the independence fault collapsing algorithm of Section 4.4.2 and are shown in Table 4.7. The concurrent test vector generated for faults 2, 3 and 9 is ?01111?. Table 5.2 shows the concurrent test vectors for all the groups of the c17 circuit. 61 Table 5.1: Output of a 2-input AND gate with concurrent-D algebra. AND I N P U T T W O 0 1 X D1 D2 D1 D2 D12 D12 I 0 0 0 0 0 0 0 0 0 0 N 1 0 1 X D1 D2 D1 D2 D12 D12 P X 0 X X X X X X X X U D1 0 D1 X D1 D12 0 D2 D12 D2 T D2 0 D2 X D12 D2 D1 0 D12 D1 D1 0 D1 X 0 D1 D1 0 0 D1 O D2 0 D2 X D2 0 0 D2 0 D2 N D12 0 D12 X D12 D12 0 0 D12 0 E D12 0 D12 X D2 D1 D1 D2 0 D12 2 - 1 3 - 1 9 - 1 0 1 1 1 1 D 2 D 2 D 3 D 9 D 3 D 9 D 23 D 39 0 Figure 5.2: Concurrent test generation for c17. Table 5.2: Concurrent test vectors for c17. Fault Faults Concurrent Group No. (see Figure 4.5) test vector 1 1, 8 10010 2 2, 3, 9 01111 3 4, 6, 10 10101 4 5, 7, 11 x1010 62 Table 5.3: Concurrent test generation for the 4-bit ALU (74181) circuit. Node Number of faults Test vectors No. Total Targeted Detected from Cumulative (Input order as in this node other nodes coverage Figure 4.10) 1 5 5 5 6 11 01001111010001 2 3 3 3 2 16 01001111110101 3 8 7 7 3 26 01011101000001 4 3 3 3 3 32 101x0101010000 5 5 3 3 4 39 10100101011000 6 6 6 6 2 47 11111000001001 7 7 4 4 3 54 11100000100000 8 14 11 11 1 66 11100110101011 9 8 6 5 1 72 10010100110101 10 8 4 3 2 77 1x101011101100 11 8 3 3 1 81 01010000101100 12 9 2 2 1 84 1x011110001100 5.1.1 Four-Bit ALU (74181) The circuit diagram of the four-bit ALU (74181) used in this work is shown in Figure 4.10. For concurrent test generation, nodes were targeted in the order they are listed in Table 4.8. The result is shown in Table 5.3. For example, the node processed first has 5 faults, all of which are targeted simultaneously. We got a test vector, shown in the last column, that detected all 5 of the targeted faults. Fault simulation of that vector showed that it detected 6 faults from other nodes as well, giving a cumulative coverage of 11. Although there were very few don?t care bits in these vectors they were enumeratively filled during fault simulation and the combination of values that covered most extra faults was retained. The don?t care bits shown in Table 5.3 are those that did not affect the fault coverage. For subsequent nodes, already detected faults were not targeted. Thus, node 3, which has 8 faults, only provided 7 target faults. By the time we reached the twelfth node, 7 of its faults had been detected. 63 Table 5.4: Test sets for ALU. ATPG Number of Tests Concurrent ATPG 12 Atalanta [54] 23 Random [55] 31 Hitec [58] 36 Fastest [50] 37 Gentest [28] 42 However, one fault from a previous node was left over. All three were detected by the twelfth vector. The set of 12 vectors obtained in Table 5.3 is the smallest possible for this circuit [14, 42]. Table 5.4 lists the number of test vectors generated for the ALU circuit by different ATPG programs. The random vector generator within the fault simulator HOPE [55] was used for random ATPG. It can be seen from the results in Table 5.4 that the test set obtained by concurrent ATPG is almost 50% smaller than the best result by any conventional ATPG. Although the results in this section were obtained using the concurrent-D algebra, an ATPG program using this technique has not been completed. The reported results were obtained by a manual application of the algorithm. 5.2 Simulation Based Concurrent Test Generation The use of the concurrent D-algebra of Section 5.1 requires a new ATPG program that may not be readily available to a user. In this section, we give an alternative procedure using a conventional fault simulator and single-fault ATPG programs for concurrent test generation. The only requirement is that the fault simulator should simulate without fault dropping, as is usually needed in diagnosis applications. 64 5.2.1 Algorithm Our objective is to generate a single test vector to cover all or most faults in each group. The independence collapsing algorithm of Section 4.4.2 orders the faults within each group in the order of their degree of independence (DI) given in Equation 4.4. DI is simply the number of edges attached to a fault node in the independence graph. A fault with higher DI is likely to be detectable by a smaller set of vectors. For each group, we select the fault with highest DI, i.e., the first fault in the group, and derive all test vectors for it. We then use a fault simulator to select a vector that detects most faults in the group. If more vectors than one detect the same number of faults within the group, then we select the one that detects most faults outside the group as well. The multiple test vector generation capability of Atalanta [54] and fault simulation without fault dropping in HOPE [55] were used. Since the number of test vectors for a fault can be very large and the vectors may contain don?t care bits, we limited the number of vectors for a target fault to 250 and expanded each vector with don?t cares into no more than 10 vectors. We applied the above procedure to the 4-bit ALU circuit. The simulation based independence fault collapsing had already grouped the faults into 13 sets. The above heuristic produced one vector for each of the first 11 groups as shown in Table 5.5. All 56 faults in group 12 were detected by these 11 vectors and the vector selected for group 13 detected all faults that were not detected by the previous vectors. 5.2.2 Results Table 5.6 shows the results of independence fault collapsing (number of fault groups) and concurrent ATPG (number of vectors) for ripple-carry adders up to 32 65 Table 5.5: Simulation-based concurrent test generation for the 4-bit ALU (74181) circuit. Group Number Test vector No. of faults (for bit order see Figure 4.10) 1 9 01100011111100 2 15 01101100000110 3 11 10100101111010 4 6 11011010100000 5 11 10110101011010 6 17 10100111101010 7 11 10010101001110 8 16 01000111101011 9 16 11100010010011 10 22 11011100110100 11 22 01010001100001 12 56 No test needed. 13 81 10101001110110 bits, the 4-bit ALU and the combinational benchmark circuits. For comparison, single-fault ATPG results are given. The column ?Dyn*? gives one of the best re- ported results obtained by dynamic vector compaction [41]. ?Min-Max? are the num- bers of statically compacted and uncompacted vectors generated by Atalanta [54]. For ripple-carry adders, the minimum number of vectors is 5, irrespective of the adder size [48]. The number of concurrent ATPG vectors grows, though at a slower rate than the compacted Atalanta vectors. The four-bit ALU result is optimum. For several benchmarks, concurrent ATPG produced a minimal vector set. For others it produced more vectors than the best reported [41]. The numbers of collapsed groups indicate approximately how many vectors will be generated. For many circuits, the number of groups would be reduced if we simulated more random vectors causing 66 Table 5.6: Concurrent ATPG test length. Independence Number of vectors Circuit Collapse Concurrent Single-fault ATPG Groups ATPG Dyn* Min-Max 1-b adder 5 5 5-7 2-b adder 5 5 7-9 4-b adder 5 5 8-11 8-b adder 7 7 10-15 16-b adder 7 9 13-22 32-b adder 7 11 17-25 4-b ALU 13 12 22-40 c17 4 4 6-9 c432 30 34 27 49-77 c499 52 52 52 54-68 c880 24 29 16 52-106 c1355 84 84 84 85-109 c1908 106 111 106 118-173 c2670 81 92 44 106-192 c3540 107 130 84 147-263 c5315 92 104 37 114-224 c6288 23 25 12 32-48 c7552 190 198 73 209-358 * Dynamic compaction (Hamzaoglu and Patel [41]) deletion of additional independence links from the graph. Our concurrent ATPG re- quires all vectors for a single fault and had to be restricted when there were too many such vectors. Figure 5.3 shows the graphical comparison of the test set sizes given in Table 5.6. It can be seen from the graph that the concurrent ATPG technique performs better than the single-fault ATPG but needs improvement to match the result of the dynamic compaction technique in [41]. Table 5.7 shows the CPU time in seconds taken by concurrent ATPG, and com- pares it against the CPU times taken by the dynamic compaction technique in [41]. 67 Table 5.7: Test generation time. Circuit Concurrent ATPG Dynamic Compaction [41] (seconds)* (seconds)** 1-b adder 0.085 2-b adder 0.092 4-b adder 0.103 8-b adder 0.182 16-b adder 3.3 32-b adder 9.7 4-b ALU 11.4 c17 0.082 c432 10.4 15 c499 14.6 0.1 c880 23.3 21.9 c1355 34 0.9 c1908 49.6 88.1 c2670 57.6 47.1 c3540 119.6 174.5 c5315 216.3 748.6 c6288 158.1 347.7 c7552 360.7 663.8 * Sun Ultra 5 ** Pentium Pro PC It can be seen from the results that for the smaller circuits, the dynamic compaction technique performs better, but as the circuit size increases, concurrent ATPG tech- nique performs far better than [41]. The time required for test generation for the larger circuits is almost a third of the time taken by dynamic compaction. So we can say that the test generation time for concurrent ATPG has a linear or quadratic relationship with the size of the circuit, and dynamic compaction has an exponential relationship. This is shown in the graph in Figure 5.4. Overall we see that the concurrent ATPG technique performed well in generating minimal test sets for a few of the benchmark circuits and in a time that was less than what the dynamic compaction technique [41] took. 68 0 50 100 150 200 250 300 350 400 Circuits in the order of Table 5.6 Number of test vectors Minimum Concurrent ATPG Single-fault ATPG Single-fault ATPG (no compaction) Concurrent ATPG Minimum Achieved (dynamic compaction) Figure 5.3: Test set size comparison. 69 0 100 200 300 400 500 600 700 800 Circuits in the order of Table 5.7 CPU seconds Minimum Concurrent ATPG Concurrent ATPG Minimum Achieved (dynamic compaction) Figure 5.4: Test generation time comparison. 70 Chapter 6 Conclusion We have developed a new test generation methodology for combinational circuits based on independence fault collapsing and concurrent test generation. The indepen- dence fault collapsing algorithm grouped all the faults in the circuit into a minimum set of independent fault subsets such that each fault subset mostly ended up having just one test. The concurrent test generation algorithm actually generated a single test for each group of faults. The independence fault collapsing procedure collapsed the graph into a minimal clique. But the process of finding the independence matrix was computationally expensive. So, we presented another approach based on fault simulation for finding the independence matrix. This technique was not computationally expensive but, we had to deal with an incompletely specified matrix. This resulted in a larger set of collapsed nodes, thus increasing the lower bound on the number of tests to be generated. The concurrent ATPG using the concurrent D-algebra produced a single test for each subset of faults, thus generating a test set equal to the lower bound. But, this procedure required the implementation of a new ATPG tool. Therefore, we presented another approach to concurrent test generation based on fault simulation and single- fault ATPG. This technique often produced satisfactory results. 71 The simulation based techniques were applied to the ISCAS85 combinational benchmark circuits as well as to several ripple-carry adder circuits and a 4-bit ALU. We saw that for smaller circuits, including the ALU, the techniques produced the optimal result. Also, for some benchmark circuits, the optimal result was achieved. The computational time was found to be far less compared to a dynamic compaction techniques, which have also produced optimal results. We can conclude that concurrent test generation produced compact tests when combined with independence fault collapsing. Also, ATPG and set covering problems have exponential time complexities and so, we cannot expect absolute optimality for large circuits. 6.1 Future Work The simulation-based algorithms for independence fault collapsing and concur- rent test generation can be improved. The fault collapsing algorithm can be made more dynamic in the sense that after collapsing, if a minimal clique is not formed, flexibility needs to be given to go back and remove a fault from a group and place it in some other group. The same flexibility can be provided during the concurrent test generation process. The algorithms need to be made more efficient. A tool that would implement the collapsing and test generation algorithms needs to be developed. One other concern is about the memory required to store the independence ma- trix. As the number of faults in the circuit increases, this requirement also increases. Some alternative method of storing the matrix needs to be devised. It is recommended that an ATPG program be implemented using the concurrent- D algebra. Since the independence fault collapsing does not guarantee that a fault 72 group can be covered by exactly one test vector, the ATPG will need to make a heuristic decision to drop some faults. Another possibility that should be explored is to use the concurrent ATPG phase of a simulation-based directed-search ATPG algorithm [7, 27]. Since the problem of finding the minimal test set is NP-hard, there will always be that extra bit of work that one can do to keep on improving the results. 73 Bibliography [1] M. Abramovici, M. A. Breuer, and A. D. Friedman, Digital Systems Testing and Testable Design. Piscataway, New Jersey: IEEE Press, 1994. [2] M. Abramovici, J. J. Kulikowski, P. R. Menon, and D. T. Miller, ?SMART and FAST: Test Generation for VLSI Scan-Design Circuits,? IEEE Design and Test of Computers, vol. 3, no. 4, pp. 43?54, Aug. 1986. [3] P. Agrawal and V. D. Agrawal, ?Probabilistic Analysis of Random Test Generation Method for Irredundant Combinational Logic Networks,? IEEE Trans. on Computers, vol. C-24, no. 7, pp. 691?695, July 1975. [4] V. D. Agrawal, ?When to use Random Testing,? IEEE Trans. on Computers, vol. C-27, no. 11, pp. 1054?1055, Nov. 1978. [5] V. D. Agrawal and P. Agrawal, ?An Automatic Test Generation System for Illiac IV Logic Boards,? IEEE Trans. Comput., vol. C-21, pp. 1015?1017, Sept. 1972. [6] V. D. Agrawal, D. H. Baik, Y. C. Kim, and K. K. Saluja, ?Exclusive Test and Its Applications in Fault Diagnosis,? in Proc. 16th International Conf. VLSI Design, Jan. 2003, pp. 143?148. [7] V. D. Agrawal, K. T. Cheng, and P. Agrawal, ?A Directed Search Method for Test Generation Using a Concurrent Simulator,? IEEE Trans. on Computer-Aided Design, vol. 8, pp. 131?138, Feb. 1989. [8] V. D. Agrawal and A. S. Doshi, ?Concurrent Test Generation,? in Proc. 14th Asian Test Symp., Dec. 2005. [9] V. D. Agrawal, A. V. S. S. Prasad, and M. V. Atre, ?Fault Collapsing via Functional Dominance,? in Proc. International Test Conf., 2003, pp. 274?280. [10] 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 & Test Workshop, Aug. 2003, pp. 368?374. [11] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, Design and Analysis of Computer Algorithms. Reading, Massachusetts: Addison-Wesley, 1974. [12] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, Data Structures and Algorithms. Reading, Massachusetts: Addison-Wesley, 1987. [13] 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. 74 [14] S. B. Akers and B. Krishnamurthy, ?Test Counting: A Tool for VLSI Testing,? IEEE Design & Test of Computers, vol. 6, no. 5, pp. 58?77, Oct. 1989. [15] D. B. Armstrong, ?A Deductive Method for Simulating Faults in Logic Circuits,? IEEE Trans. on Computers, vol. C-21, no. 5, pp. 464?471, May 1972. [16] B. Ayari and B. Kaminska, ?A new Dynamic Test Vector Compaction for Automatic Test Pattern Generation,? IEEE Trans. on CAD, vol. 13, no. 3, pp. 353?358, Mar. 1994. [17] R. Battiti. Reactive Local Search Solver. Available from - University of Trento: http://rtm.science.unitn.it/intertools/. [18] R. Battiti and M. Protasi, ?Reactive Local Search for the Maximum Clique Problem,? Algorithmica, vol. 29, no. 4, pp. 610?637, Apr. 2001. [19] C. Benmehrez and J. F. McDonald, ?Measured Performance of a Programmed Imple- mentation of the Subscripted D-Algorithm,? in Proc. of the Design Automation Conf., June 1983, pp. 308?315. [20] I. Berger and Z. Kohavi, ?Fault Detection in Fanout-Free Combinational Networks,? IEEE Trans. on Computers, vol. C-22, no. 10, pp. 908?914, Oct. 1973. [21] K. O. Boateng, H. Konishi, and T. Nakata, ?A Method of Static Compaction of Test Stimuli,? in Proc. Asian Test Symp., Nov. 2001, pp. 137?142. [22] F. Brglez, D. Bryan, and K. Kozminski, ?Combinational Profiles of Sequential Bench- mark Circuits,? in Proc. of Int. Symp. on Circuits and Systems, May 1989, pp. 1929? 1934. [23] F. Brglez and H. Fujiwara, ?A Neutral Netlist of 10 Combinational Benchmark Designs and a Special Translator in Fortran,? in Proc. of Int. Symp. on Circuits and Systems, June 1985. [24] M. L. Bushnell and V. D. Agrawal, Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits. Boston: Springer, 2005. [25] R. Carraghan and P. M. Pardalos, ?An Exact Algorithm for the Maximum Clique Problem,? Op. Research Letters, vol. 9, pp. 375?382, 1990. [26] J.-S. Chang and C.-S. Lin, ?Test Set Compaction for Combinational Circuits,? IEEE Trans. on CAD, vol. 14, no. 11, pp. 1370?1378, Nov. 1995. [27] K. T. Cheng and V. D. Agrawal, Unified Methods for VLSI Simulation and Test Gen- eration. Boston: Kluwer Academic Publishers, 1989. [28] W.-T. Cheng and T. J. Chakraborty, ?Gentest: An Automatic Test Generation System for Sequential Circuits,? Computer, vol. 22, no. 4, pp. 43?49, Apr. 1989. [29] 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. [30] A. L. Crouch, Design for Test for Digital IC?s and Embedded Core Systems. New Jersey: Prentice Hall, 1999. 75 [31] DIMACS. Information about DIMACS available from - Rutgers University, http://dimacs.rutgers.edu/. [32] A. S. Doshi and V. D. Agrawal, ?Independence Fault Collapsing,? in Proc. 9th VLSI Design and Test Symp., Aug. 2005, pp. 357?364. [33] R. D. Eldred, ?Test Routines Based on Symbolic Logical Statements,? Journal of the ACM, vol. 6, no. 1, pp. 33?36, Jan. 1959. [34] P. F. Flores, H. C. Neto, and J. P. Marques-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. [35] H. Fujiwara and T. Shimono, ?On the Acceleration of Test Generation Algotithms,? IEEE Trans. on Computers, vol. C-32, no. 12, pp. 1137?1144, Dec. 1983. [36] H. Fujiwara and S. Toida, ?The Complexity of Fault Detection Problems for Combi- national Logic Circuits,? IEEE Trans. Comput., vol. C-31, no. 6, pp. 555?560, June 1982. [37] J. M. Galey, R. E. Norby, and J. P. Roth, ?Techniques for the Diagnosis of Switching Circuit Failures,? in Proc. of the Second Annual Symp. on Switching Circuit Theory and Logical Design, Oct. 1961, pp. 152?160. [38] 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. [39] P. Goel and B. C. Rosales, ?Test Generation and Dynamic Compaction of Tests,? in Proc. International Test Conf., Oct. 1979, pp. 189?192. [40] P. Goel and B. C. Rosales, ?Dynamic Test Compaction with Fault Selection Using Sensitizable Path Tracing,? IBM Technical Disclosure Bulletin, vol. 23, no. 5, pp. 1954?1957, Oct. 1980. [41] 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. [42] J. P. Hayes. 74181 4-bit ALU and Function Generator and Complete Gate-level Tests. Available from: www.eecs.umich.edu/?jhayes/iscas/74181.html. [43] D. S. Hochbaum, ?An Optimal Test Compression Procedure for Combinational Cir- cuits,? IEEE Trans. Computer-Aided Design, vol. 15, no. 10, pp. 1294?1299, oct 1996. [44] 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. [45] S. Kajihara, I. Pomeranz, K. Kinoshita, and S. M. Reddy, ?Cost Effective Generation of Minimal Test Sets for Stuck at Faults in Combinational Logic Circuits,? in Proc. of the Design Automation Conf., June 1993, pp. 102?106. [46] S. Kajihara, I. Pomeranz, K. Kinoshita, and S. M. Reddy, ?On Compacting Test Sets by Addition and Removal of Test Vectors,? in Proc. VLSI Test Symp., Apr. 1994, pp. 25?28. 76 [47] S. Kajihara, I. Pomeranz, K. Kinoshita, and S. M. Reddy, ?Cost Effective Generation of Minimal Test Sets for Stuck at Faults in Combinational Logic Circuits,? IEEE Trans. on CAD, vol. 14, no. 12, pp. 1496?1504, Dec. 1995. [48] S. Kajihara and T. Sasao, ?On the Adders with Minimum Tests,? in Proc. of the Asian Test Symp., Nov. 1997, pp. 10?15. [49] K. R. Kantipudi and V. D. Agrawal, ?On the Size and Generation of Minimal N- Detection Tests,? in Proc. 19th International Conf. VLSI Design, Jan. 2006, pp. 425? 430. [50] T. P. Kelsey, K. K. Saluja, and S. Y. Lee, ?An Efficient Algorithm for Sequential Circuit Test Generation,? IEEE Trans. on Computers, vol. 42, no. 11, pp. 1361?1371, Nov. 1993. [51] Y. C. Kim, V. D. Agrawal, and K. K. Saluja, ?Multiple Faults: Modeling, Simulation and Test,? in Proc. 15th International Conf. VLSI Design, Jan. 2002, pp. 592?597. [52] B. Krishnamurthy and S. 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. [53] D. Kumlander, Some Practical Algorithms to Solve the Maximum Clique Problem. PhD thesis, Tallinn University of Technology, Estonia, Dec 2005. [54] H. K. Lee and D. S. Ha, ?Atalanta: An Efficient ATPG for Combinational Circuits,? Tech. Report 93-12, Dept. of Electrical Eng., Virginia Polytechnic Inst. and State Univ., Blacksburg, Virginia, 1993. [55] H. K. Lee and D. S. Ha, ?HOPE: An Efficient Parallel Fault Simulator for Synchronous Sequential Circuits,? IEEE Trans. on CAD, vol. 15, no. 9, pp. 1048?1058, Sept. 1996. [56] J. P. Marques-Silva, ?Integer Programming Models for Optimization Problems in Test Generation,? in Proc. IEEE Asia-South Pacific Design Automation Conf., 1998, pp. 481?487. [57] T. M. Niermann, W.-T. Cheng, and J. H. Patel, ?PROOFS: A Fast, Memory-Efficient Sequential Circuit Fault Simulator,? IEEE Trans. on CAD, vol. 11, no. 2, pp. 198?207, Feb. 1992. [58] T. M. Niermann and J. H. Patel, ?HITEC: A Test Generation Package for Sequential Circuits,? in Proc. European Design Automation Conf., Feb. 1991, pp. 214?218. [59] Y. E. Osais and A. H. El-Maleh, ?A Static Test Compaction Technique for Combina- tional Circuits based on Independent Fault Clustering,? in Proc. of the International Conf. on Electronics, Circuits and Systems, Dec. 2003, pp. 1316?1319. [60] P. R. J. Ostergard, ?A New Algorithm for the Maximum Clique Problem,? Applied Mathematics, vol. 120, pp. 197?207, 2002. [61] J. F. Poage, ?Derivation of Optimum Tests to Detect Faults in Combinational Cir- cuits,? in Proc. of the Mathematical Theory of Automata Symp., Apr. 1963, pp. 483? 528. 77 [62] I. Pomeranz and Z. Kohavi, ?The Minimum Test Set Problem for Circuits with Non- reconvergent Fanout,? Journal of Electronic Testing: Theory and Application, pp. 339?349, Nov. 1991. [63] I. Pomeranz, L. N. Reddy, and S. M. Reddy, ?COMPACTEST: A Method to Generate Compact Test Sets for Combinational Circuits,? IEEE Trans. on CAD, vol. 12, no. 7, pp. 1040?1049, July 1993. [64] I. Pomeranz and S. M. Reddy, ?Forward-Looking Fault Simulation for Improved Static Compaction,? IEEE Trans. on CAD, vol. 20, no. 10, pp. 1262?1265, Oct. 2001. [65] I. Pomeranz and S. M. Reddy, ?Level of Similarity: A Metric for Fault Collapsing,? in Proc. Design, Automation and Test in Europe (DATE) Conf., volume 1, Mar. 2004, pp. 56?61. [66] 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., Oct. 2002, pp. 391?397. [67] L. N. Reddy, I. Pomeranz, and S. M. Reddy, ?ROTCO: A Reverse Order Test Com- paction Technique,? in Proc. of the EURO-ASIC Conf., June 1992, pp. 189?194. [68] 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. [69] J. P. Roth, W. G. Bouricius, and P. R. Schneider, ?Programmed Algorithms to Com- pute 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. [70] R. K. K. R. Sandireddy, ?Hierarchical Fault Collapsing for Logic Circuits,? Master?s thesis, Auburn University, Auburn, AL, May 2005. [71] R. K. K. R. Sandireddy and V. D. Agrawal, ?Diagnostic and Detection Fault Collaps- ing for Multiple Output Circuits,? in Proc. Design, Automation and Test in Europe (DATE) Conf., Mar. 2005, pp. 1014?1019. [72] R. K. K. R. Sandireddy and V. D. Agrawal, ?Use of Hierarchy in Fault Collapsing,? in Proc. 14th IEEE North Atlantic Test Workshop, May 2005. [73] M. H. Schulz, E. Trischler, and T. M. Sarfert, ?SOCRATES: A Highly Efficient Au- tomatic Test Pattern Generation System,? IEEE Trans. on CAD, vol. 7, no. 1, pp. 126?137, Jan. 1988. [74] G. Tromp, ?Minimal Test Sets for Combinational Circuits,? in Proc. International Test Conf., Oct. 1991, pp. 204?209. [75] E. G. Ulrich, V. D. Agrawal, and J. H. Arabian, Concurrent and Comparative Discrete Event Simulation. Boston: Kluwer Academic Publishers, 1994. [76] E. G. Ulrich and T. Baker, ?Concurrent Simulation of Nearly Identical Digital Net- works,? Computers, vol. 7, pp. 39?44, Apr. 1974. [77] J. C. Wang and E. P. Stabler, ?Collective Test Generation and Test Set Compaction,? in Proc. IEEE International Symp. Circ. and Syst. (ISCAS?95), volume 3, Apr.-May 1995, pp. 2008?2011. 78 Appendices 79 Appendix A On the Effectiveness of the Independence Fault Collapsing Algorithm of Subsection 4.4.2 This appendix gives the Independence Fault Collapsing and Concurrent Test Generation results for the 4-bit ALU (74181) circuit of Figure A.1. The fault col- lapsing algorithm of Subsection 4.4.2 first computes the degree of independence (DI) for each fault and then processes faults in the decreasing order of DI. Because the collapsing procedure is sequential, this ordering is an important step. To demonstrate the significance of DI-ordering, here we use algorithm of Subsection 4.4.2 with an ar- bitrary ordering of faults. In the ALU circuit in Figure A.1, the faults are identified by arbitrarily chosen numbers 1 through 84. The independence matrix for this circuit was generated using the procedure given in Figure 4.4, independence collapsing was done by the algorithm of Subsection 4.4.2 using the increasing order of fault numbers shown in Figure A.1, and concurrent tests were obtained using the Concurrent D Algebra of Section 5.1. The independence collapsed fault sets are shown in Table A.1 and the concurrent test generation results are shown in Table A.2. The total faults were collapsed into 15 nodes. It is seen from Table A.2 that by the time we reached the fifteenth node during the concurrent test generation process, both of its faults were detected. However, four faults from other nodes were left out. Those were concurrently targeted and required three vectors. Hence, a total of 17 tests were generated for 15 fault groups, thus 80 c_n 27 6 26 75 8 20 30 16 1513 14 22 33 4 18 31 2 36 s3 s2 s1 s0 b3 a3 b2 a2 a0 b0 a1 b1 38 23 12 119 10 21 29 46 45 44 42 41 40 24 37 17 51 50 49 35 32 39 19 43 4748 525453 m f3n pn gn f2n a=b f1n f0n 56 58 59 57 25 28 31 34 61 60 55 64 67 65 62 78 79 68 70 69 71 7372 74 77 76 75 81 82 83 80 84 stuck?at?1 stuck?at?0 c_n+4 6366 Figure A.1: ALU dominance collapsed faults [71]. 81 Table A.1: Independence collapsed fault sets for the 4-bit ALU circuit. Node No. of Faults numbers (see Figure A.1) No. Faults 1 10 1, 5, 9, 14, 31, 39, 40, 51, 76, 80 2 8 2, 6, 10, 29, 37, 44, 49, 83 3 12 3, 7, 11, 13, 27, 33, 36, 42, 60, 69, 71, 82 4 9 4, 8, 12, 15, 28, 30, 75, 78, 84 5 5 16, 18, 20, 22, 79 6 4 17, 19, 21, 23 7 5 24, 25, 26, 32, 35 8 5 34, 38, 41, 45, 77 9 5 43, 46, 50, 65, 68 10 5 47, 52, 57, 62, 81 11 6 48, 54, 59, 67, 70, 73 12 4 53, 58, 66, 72 13 2 55, 63 14 2 56, 64 15 2 61, 74 showing the importance of ordering the faults before collapsing them; the DI-ordering in the algorithm produced 12 tests in Subsection 4.4.3. 82 Table A.2: Concurrent test generation for the 4-bit ALU circuit. Node Number of faults Test vectors No. Total Targeted Detected from Cumulative (Input order as in this node other nodes coverage Figure A.1) 1 10 10 7 5 12 01100011000001 2 8 8 6 4 22 01001100111100 3 12 10 10 2 34 10101000101011 4 9 5 5 0 39 101001100101xx 5 5 4 4 0 43 10xx11011111xx 6 4 4 4 0 47 x1xx01010101xx 7 5 5 5 2 54 1x01001100000x 8 5 5 5 0 59 xx011010100000 9 5 3 3 3 65 10011100001010 10 5 4 3 0 68 1x011110x00001 11 6 4 4 0 72 100x0111000001 12 4 4 4 0 76 1x011010110001 13 2 2 2 0 78 xxx11010101000 14 2 2 2 0 80 1xx11010101101 15 2 0 4 2 82 1x011010001100 2 1 83 1xx11111111001 1 1 84 x1x1100101011x 83 Appendix B DIMACS Format This appendix explains the DIMACS [31] format for representing a graph. The first character of each line describes the information: ? ?p? starts the problem line (the two numbers are the number of nodes and number of edges in the graph). ? ?e? describes a single edge (first node is 1). ? ?c? is a comment. ? ?clq? in the problem line states that this is a Max Clique problem. The DIMACS format for the graph in Figure 4.6 is given below: c The following lines are all comments c number of vertices : 11 c nonisolated vertices : 11 c number of edges : 34 c This is the last comment line p clq 11 34 e 1 2 e 1 3 e 1 4 e 1 5 e 1 6 e 1 9 e 1 11 e 2 4 e 2 5 84 e 2 7 e 2 11 e 3 5 e 3 6 e 3 7 e 3 8 e 3 10 e 3 11 e 4 5 e 4 7 e 4 11 e 5 8 e 5 9 e 5 10 e 6 7 e 6 8 e 6 9 e 7 8 e 7 9 e 8 9 e 8 10 e 8 11 e 9 10 e 9 11 e 10 11 The program [17] identified a maximal clique consisting of nodes 6, 7, 8 and 9. This clique was then used as the initial graph in the alternative collapsing procedure illustrated in Figure 4.12. 85