HILLARY GRIMES III ELEC 7250 TERM PAPER CONCURRENT TEST GENERATION Combinational Circuit Concurrent Test Generation A Brief Overview HILLARY GRIMES III GRADUATE STUDENT AUBURN UNIVERSITY Abstract The complexity of VLSI devices increases rapidly as technology increases resulting in an increase in the difficulty of test generation Traditional test generation algorithms target one fault of a fault set at a time to generate a test This paper presents a brief overview of a few different approaches to concurrent test generation Concurrent test generation is the process of generating tests by concurrently targeting multiple faults 1 Introduction Automatic Test Pattern Generation ATPG is the process of generating a test set a set of input combinations and expected output responses to test for all or most faults in a circuit The complexity of both sequential and combinational ATPG is NP complete growing with circuit size As VLSI technology advances integrated circuits are becoming larger and more complex resulting in the need to develop more efficient methods of generating test sets Many ATPG algorithms generate tests by targeting a single fault and finding an input vector to activate the fault and propagate its effect to a primary output The input vector generated is a test that can detect the targeted fault In concurrent test generation the concurrent ATPG targets multiple faults and tests are generated to detect as many targeted faults as possible Tests are generated by concurrently targeting multiple faults In Section 2 of this paper two similar directed search approaches to concurrent test generation are described one phase of the three phase CONTEST algorithm and a phase in many genetic algorithm approaches to concurrent ATPG Both approaches are simulation based methods in which a fault simulator is used during the ATPG process Before a vector is chosen to be added to the test set it is simulated providing timing analysis during test generation eliminating the generation of hazardous tests This gives simulation based methods a significant advantage over other tests generation methods 6 The two concurrent ATPG approaches described in section 3 target groups of concurrently testable faults and attempt to generate a single test that detects all faults in each targeted group In both methods concurrent D algebra and concurrent ATPG using single fault ATPG and simulation the groups of faults targeted during test generation are grouped by a unique fault collapsing algorithm which is also described in section 3 2 Two Similar Directed Search Methods The two concurrent test generation methods described in this section use a directed search approach In the directed search approach the test generator searches the input vector space in a directed manner for tests The input vector space contains all possible input vectors and tests are usually clustered within the input vector space 1 6 By starting with any initial vector a directed search algorithm directs the search for tests toward the test clusters The first concurrent test generation method described is phase 2 of the CONTEST algorithm CONTEST consists of 3 phases phase 1 generates an initialization vector sequence for sequential circuits phase 2 is the concurrent test generation phase and phase 3 generates tests by targeting single faults 1 3 6 In phase 2 the search for tests is a directed search which is directed by the use of cost functions 1 3 The second concurrent test generation method described is a phase in most genetic algorithm approaches to test generation This approach is similar to phase 2 of the CONTEST algorithm 6 and the search through the input vector space is directed though the use of fitness functions 4 2 1 CONTEST Phase 2 In phase 2 of the CONTEST algorithm tests are generated by concurrently targeting all undetected faults Beginning with an initial vector the circuit is simulated using a concurrent HILLARY GRIMES III ELEC 7250 TERM PAPER CONCURRENT TEST GENERATION fault simulator During simulation cost functions are computed for each target fault The cost function for a fault is the shortest distance that fault s effect is from a primary output If the fault effect is observable on a primary output the cost function is zero and if the fault has no fault effect the fault is not activated the cost function is infinite Trial vectors are generated by modifying the current input vector with a one bit change Each trial vector is simulated and the associated costs are computed By comparing the costs from the current input vector simulation with the costs from the trial vector simulation the algorithm either accepts or rejects the trial vector The trial vector is accepted if the overall costs of undetected faults are found to decrease If accepted the trial vector becomes the current vector and the process starts over When the costs associated with all single bit changes in the current vector do not reduce total cost phase 2 ends and CONTEST begins phase 3 Phase 3 targets single faults to continue the search for tests and is needed because phase 2 only achieves between 65 and 85 percent fault coverage 1 3 6 2 2 Concurrent ATPG using Genetic Algorithms Many ATPGs based on genetic algorithms include a phase of concurrent test generation which is similar to phase 2 of the CONTEST algorithm Both directed search approaches are evolutionary meaning they evolve tests by accepting or rejecting vectors based on how well they detect faults 4 5 6 Test generation using genetic algorithms begins with a set of vectors which initially is usually generated randomly called a population Each vector has an associated fitness which is evaluated through simulation 5 6 The higher the fitness function the more fit a vector is to detect faults The population is improved iteratively with each iteration producing a new population and each population produced is called a generation Each generation is evolved from the previous generations through three evolutionary operators called selection mutation and crossover 4 5 6 In selection two of the higher fit individuals vectors are selected from the population for reproduction in generating the next generation 4 5 The crossover evolutionary operator exchanges bits between two selected vectors of the population to produce two vectors for the next generation Mutation is the process of modifying bits from a selected vector in the population to produce a new vector for the next generation 4 6 The generation of