Redundancy identification and parallel test generation using boolean satisfiability

An Automatic Test Pattern Generator is an indispensable tool in the production of reliable computer systems. It distinguishes defective components from defect-free components by generating input vector sets that cause the outputs under test to be different in the two cases. Test generators spend most of their time on a small subset of redundant and hard-to-detect faults. In this dissertation we present two schemes to achieve high quality tests for combinational Very Large Scale Integrated circuits. We identify redundant faults directly by deciding the satisfiability problem for a boolean difference formula in the conjunctive normal form. The algorithm is based on a system of five reduction rules which form a complete rule system. Experimental results on the benchmark circuits show that the number of rule applications in all cases is comparable to the size of the original boolean difference formula. Other satisfiability problems can also be solved using our method. We present a method of parallelizing test generation using boolean satisfiability. Based upon our study of the alternatives for parallelization, we propose a dynamic search-space allocation strategy to split work between the available processors. This strategy is easy to implement with a greedy heuristic and is economical in its demand for inter-processor communication. We propose an analytical model to predict the performance of the parallel versus sequential implementations. The results of test generation for the hard-to-detect faults on the benchmark circuits show that the parallel test generation scheme significantly improves fault coverage and CPU time. The experimental data conclusively validates our analytical model and allows predictions of performance for a range of timeout limits