Parallelized Boolean Satisfiability Approach for VLSI Test Generation

Abstract

VLSI Test Generation involves generating input patterns that give different response for a given fault in a faulty and fault-free circuit. The problem for test generation for combinational circuits is NP- Complete. Conventional methods for test generation involve exhaustive, random and deterministic techniques. These methods are not very effective and become very costly and time-consuming as the size of the circuit increases. The complexity of VLSI circuits is rapidly increasing. The need for effective and economical testing has given birth to unconventional methods for VLSI test generation. These include methods such as Boolean Satisfiability approach, Neural computing and Quantum approach etc. The Boolean Satistiability approach for test generation was proposed by Larrabee in 1992. It is neither purely structural nor an algebraic one. The approach generates test patterns in two steps: First, it extracts the .formula that defines the test patterns that detect the fault. Second, it satisfies the formula using Boolean satisfiability algorithm. In this thesis, we have explored the Boolean Satisfiability approach and proposed a parallel approach for VLSI test generation based on this approach. The Parallelized Boolean Satisfiability Approach tor VLSI Test Generation is highly efficient, scalable and economical algorithm tor the generation of test patterns tor single-stuck-at faults in combinational circuits. If both the steps of Boolean Satisfiability approach are effectively parallelized, YLSI test generation will be much faster, effective and economic process. The parallel algorithm for both the steps has been proposed. The first step has been parallelized by concurrent computation of the CNF formulas for the components of the circuit to generate the Boolean truth function. It is proposed that the second step can be parallelized by generating the 2SA T solutions of the Boolean truth function using different orders of variables concurrently at the first level and checking the consistency with 3CNF clauses at the second level. The effectiveness of the approach has been demonstrated by implementing it in a distributed environment. The implementation of first step i.e. extraction of the Boolean truth function has been done using PYM message-passing architecture with master-slave approach. The experimental results show the efficiency and good performance of the algorithm.