A cost model for and implementation of a hierarchical test generation technique are presented. The cost model is based on fundamental test generation activities such as implication, justification, and backtracking. The model shows that the cost of hierarchical test generation grows as G log G under some realistic assumptions, while the cost of gate-level test generation may grow as fast as G/sup 2/, where G is the number of gates in a circuit under test. This implies that hierarchical test generators should be much faster than flat test generators on large circuits. The implementation of the hierarchical test generation is fan-out-oriented and uses a minimal hierarchical representation of the circuit and functional level heuristics to perform implication, propagation, and backtracing with high-level functional models. Experiments with three hierarchically described circuits show that hierarchical test generation is 1.5 to 8.9 faster than flat gate-level generation.>

FANHAT, has been designed and implemented to accelerate test generation for digital circuits. FANHAT uses a minimal hierarchical representation of the circuit and functional level heuristics to perform implication, propagation, and backtracking with high-level functional model. Experiments with three circuits show hierarchical test generation using FANHAT is 1.5 to 8.9 times faster than flat gate-level test generation.>

Test generation algorithms use search strategies to control decision making whenever the algorithms encounter a choice of a signal value or action. The authors' study of traditional search strategies used in automatic test pattern generation (ATPG) has led to the observation that no single strategy is superior for all faults in a circuit or all circuits. Further experimentation led to the conclusion that a combination of search strategies provides better fault coverage and/or faster ATPG for a given backtrack limit. Instead of using just one strategy to the backtrack limit, a primary strategy is used for the first half of the backtrack limit, and then a secondary strategy is used for the second half. The authors present an ATPG cost model based on the number of test generation events. They use this model to explain why search strategy switching is faster and show experimental evidence to verify the search strategy switching theory. The experiments were performed with the ISCAS circuits and the authors' implementation of the FAN algorithm.>