In recent years, considerable research efforts have been devoted to utilizing circuit structural information to improve the efficiency of Boolean satisfiability (SAT) solving, resulting in several efficient circuit-based SAT solvers. In this paper, we present a sequential equivalence checking framework based on a number of circuit-based SAT solving techniques as well as a novel invariant checker. We first introduce the notion of kth invariants. In contrast to the traditional invariants that hold for all cycles, k th invariants are guaranteed to hold only after the kth cycle from the initial state. We then present a bounded model checker (BMChecker) and an invariant checker (IChecker), both of which are based on circuit SAT techniques. Jointly, BMChecker and IChecker are used to compute the kth invariants, and are further integrated in a sequential circuit SAT solver for checking sequential equivalence. Experimental results demonstrate that the new sequential equivalence checking framework can efficiently verify large industrial designs that cannot be verified by existing solutions.

In this paper, we propose two fault-diagnosis methods for improving multiple-fault diagnosis resolution. The first method, based on the principle of single-fault activation and single-output observation, employs a new circuit transformation technique in conjunction with the use of a special type of diagnostic test pattern, named single-observation single-location-at-a-time (SO-SLAT) pattern. Given a list of candidate suspects (which could be stuck-at, transition, bridging, or other faults obtained by any existing diagnosis method), we generate a set of SO-SLAT patterns, each of which attempts to activate only one fault in the list and propagate its effects only to a specific observation point. Observing the responses of the circuit under diagnosis to the SO-SLAT patterns helps more precisely determine whether each fault suspect is a true or false candidate. The method can tolerate most of the timing hazards for a more accurate diagnosis of failures caused by timing faults. The second method generates and applies limited-cycle sequential tests, based on a Boolean satisfiability solver, to identify multiple defective signals which can jointly explain the circuit’s faulty behavior. These two methods can be applied independently and/or jointly after any existing state-of-the-art diagnosis process to further improve the diagnosis resolution. The experimental results demonstrate the effectiveness of the proposed methods for diagnosing multiple faults, including timing faults.

Recent research results have shown that the traditional structural testing for delay and signal integrity faults may result in overtesting due to the nontrivial number of such faults that are untestable in the functional mode although testable in the test mode. This paper presents a pseudofunctional-test methodology that attempts to minimize the overtesting problem of the scan-based circuits in automatic test pattern generation (ATPG) and built-in self-test (BIST) test generation approaches. The first pattern of a two-pattern test is still delivered by scan in the test mode but the pattern is generated in such a way that it does not violate the functional constraints extracted from the functional logic. The second pattern is then generated in a functional mode using the functional justification (also called broadside) test application scheme. The authors use a sequential boolean satisfiability solver to extract a set of functional constraints that consists of illegal states and internal signal correlation. The functional constraints are imposed upon an ATPG tool to generate pseudofunctional tests and/or implemented as a monitor in the BIST environment to allow only functional-like patterns generated from the random test pattern generator as tests. The experimental results for delay faults indicate that the percentage of functionally untestable delay faults is nontrivial for many circuits. This finding supports the hypothesis of the overtesting problem in delay testing. In addition, the results indicate the effectiveness of the proposed constraint extraction method and the proposed BIST scheme.

Recent research results have shown that the traditional structural testing for delay and crosstalk faults may result in over-testing due to the non-trivial number of such faults that are untestable in the functional mode while testable in the test mode. This paper presents a pseudo-functional test methodology that attempts to minimize the over-testing problem of the scan-based circuits for the delay faults. The first pattern of a two-pattern test is still delivered by scan in the test mode but the pattern is generated in such a way that it does not violate the functional constraints extracted from the functional logic. In this paper, we use a SAT solver to extract a set of functional constraints which consists of illegal states and internal signal correlation. Along with the functional justification (also called broad-side) test application scheme, the functional constraints are imposed to a commercial delay-fault ATPG tool to generate pseudo-functional delay tests. The experimental results indicate that the percentage of untestable delay faults is non-trivial for many circuits which support the hypothesis of the over-testing problem in delay testing. The results also indicate the effectiveness of the proposed constraint extraction method.

A sequential SAT solver, Satori, was recently proposed (Iyer, M.K. et al., Proc. IEEE/ACM Int. Conf. on Computer-Aided Design, 2003) as an alternative to combinational SAT in verification applications. This paper describes the design of Seq-SAT, an efficient sequential SAT solver with improved search strategies over Satori. The major improvements include: (1) a new and better heuristic for minimizing the set of assignments to state variables; (2) a new priority-based search strategy and a flexible sequential search framework which integrates different search strategies; (3) a decision variable selection heuristic more suitable for solving the sequential problems. We present experimental results to demonstrate that our sequential SAT solver can achieve orders-of-magnitude speedup over Satori. We plan to release the source code of Seq-SAT.

In this paper, we propose a diagnostic test generation method in conjunction with an efficient sequential SAT-based diagnosis procedure to precisely identify multiple defective signals which can jointly explain the circuit's faulty behavior. This method can be applied after any existing state-of-the-art diagnosis process to further improve the diagnosis resolution. The proposed diagnosis method generates limited-cycle sequential tests for SAT-based diagnosis which results in significantly higher diagnosis accuracy for multiple faults. The experimental results demonstrate the effectiveness of the proposed method.

This paper presents a pseudo-functional BIST scheme that attempts to minimize the over-testing problem of logic BIST for delay and crosstalk-induced failures. The over-testing problem is evident from the non-trivial number of structurally testable while functionally untestable (ST-FU) faults. Such faults can be detected by some scan/BIST patterns but not by any functional pattern. The goal of this BIST scheme is to allow only functional-like patterns generated from the BIST random test pattern generator (RTPG) as tests. This is done by inserting a Monitor at the output of the RTPG, which indicates whether the current pattern violates some pre-extracted functional constraints. In case of violation, the pattern is skipped. In our implementation, a SAT solver is used to analyze and extract a set of functional constraints from the functional logic. These functional constraints are then implemented in hardware as the Monitor. Even though the extracted functional constraints can not be exhausted, the proposed BIST scheme can detect and filter out, in real-time, a substantial subset of the nonfunctional patterns, and thus minimizing the over-testing problem. We present some experimental results to demonstrate the effectiveness of the proposed BIST scheme.

The developments of efficient SAT solvers have attracted tremendous research interest in recent years. The merits of these solvers are often compared in terms of their performance based upon a wide spread of benchmarks. In this paper, we extend an earlier-proposed solver design concept called (SCGL) Signal Correlation Guided Learning that is ATPG-based into a family of heuristics. Along with this SCGL family of heuristics, we classify benchmark examples according to their performance using the SCGL heuristics. With this study, we identify the class of problems that are uniquely suitable to be solved by using the SCGL approach. In particular, for solving difficult circuit-based problems at INTEL, our SCGL-based ATPG solver is able to achieve at least an order of magnitude speedup over the state-of-the-art SAT solvers. Our conclusion is that SCGL is an unique solver design concept that can complement heuristics proposed by others for solving circuit-oriented difficult problems.