Query: EfficienSAT-based ATPG techniques for all  multiple stuck-at faults

Candidate papers:

abstract: Due to the continuous shrinking of semiconductor technology, there are more and more subtle errors or faults widely distributed in manufactured chips, and traditional "single" stuck at fault model may become inappropriate. It is definitely better if all combinations of multiple faults can be completely tested. In this paper, we present ATPG (Automatic Test Pattern Generation) techniques targeting all multiple stuck at faults, i.e. all combinations of stuck at faults. That is, given "n" possibly faulty locations in a circuit, the target set of faults consists of 3n 1 fault combinations, as each possibly faulty location is under stuck at 1, stuck at 0, or normal/non faulty. Traditional ATPG flows use fault simulators to eliminate all detectable faults by the current set of test vectors. The problem, however, fault simulators represent fault lists explicitly in the sense that all possible faults are enumerated in the fault lists. This prevents us from dealing with ultra large fault lists, such as 3n 1 faults. We need "implicit" representation of faults in order to deal with such huge numbers of faults or fault combinations. We present SAT based formulations for ATPG of circuits having very large numbers of faults by implicitly eliminating detected faults. We solve a set of SAT problems whose constraints increase pure incrementally (here "pure" means never deleting constraints) and so the entire solving process can be very efficient, as all learnings obtained so far are valid in the following SAT problems. Experiments are performed on combinational parts of ISCAS89 circuits in their AIG (AND Inverter Graph) representations. We have successfully generated the complete set of test vectors assuming that faults happen only at outputs of gates. Our ATPG techniques can also start with a given set of test vectors. If we start the ATPG processes with a set of test vectors for single stuck at faults, we can obtain the set of additional test vectors required for multiple stuck at faults. Results are a little bit surprising in the sense that we need very few additional test vectors for multiple faults, although the numbers of fault combinations are exponentially larger. As far as we know, for the first time, complete test vectors for all stuck at faults for ISCAS89 circuits where faults happen only at outputs of gates in AIG representations of the circuits have been obtained.
author_names: Masahiro Fujita

Alan Mishchenko
title: Efficient SAT based ATPG techniques for all multiple stuck at faults
venue: 2014 International Test Conference
year: 2014

abstract: As fabricated circuitry becomes larger and denser, the modern industrial automatic test pattern generation techniques, which focus on the detection of single faults, become more likely to overlook multiple (simultaneous) faults. Although there are exponentially more multiple faults than single faults in any given circuit design, only a few additional test patterns are needed to cover all of the multiple faults, if the test generation starts from the complete test set for single faults. In this paper, we first show the case where test patterns for single faults are sufficient to cover all multiple faults, and then explain in which conditions some of the multiple faults may be overlooked. Based on this analysis, we propose a method that can efficiently generate the complete test set for double faults without traversing all the faults. Since most of the double faults can be detected by the single faults' test set, the proposed method only selects the uncovered double faults by analyzing the propagation paths of single faults, and then generating new test patterns only for those uncovered faults. The experimental results show that based on the single faults' test set, the proposed method only needs to create a small number of additional test patterns to cover all double faults in most of the given circuits. By repeating the same process, the proposed method can be incrementally applied to deal with all multiple faults.
author_names: Peikun Wang

Conrad Jinyong Moore

Amir Masoud Gharehbaghi

Masahiro Fujita
title: An ATPG Method for Double Stuck At Faults by Analyzing Propagation Paths of Single Faults
venue: IEEE Transactions on Circuits and Systems I: Regular Papers
year: 2018

abstract: Fault Diagnosis is a critical process to identify the locations of physical defects in advanced integrated circuits. Current diagnosis tools often report multiple types of faults as defect candidates. Thus an efficient method to distinguish different types of faults is highly desired. Stuck at and bridging faults are two most commonly used DC fault models during diagnosis. In this paper we present an efficient diagnosis pattern generation procedure to distinguish stuck at faults and bridging faults. Two major techniques are proposed. The first one is a fault inactivation method (FIM) that can quickly distinguish most fault pairs by inactivating one fault while detecting the other in each fault pair. The second one is a fault types transformation method (FTTM) that can transform the problem of distinguishing a stuck at fault and a bridging fault into the problem of detecting a stuck at fault. Both methods involve only one copy of the original circuit and require only an ordinary ATPG tool for stuck at faults. Furthermore, both methods can deal with multiple fault pairs at a time and thus not only is the required CPU time small but also the dynamic test compaction capability of the ATPG tool can be utilized. Experiments on a large number of randomly selected fault pairs in ISCAS'89 and IWLS'05 benchmark circuits have been carried out. The results show that the FIM can distinguish about 91.9% of distinguishable fault pairs quickly and the FTTM can distinguish all other distinguishable fault pairs and identify all equivalent fault pairs. The average ratio of the number of diagnosis patterns over that of the test patterns for stuck at faults is only 0.64. On average, one diagnosis pattern can distinguish 10.89 fault pairs.
author_names: Cheng-Hung Wu

Kuen-Jong Lee
title: An Efficient Diagnosis Pattern Generation Procedure to Distinguish Stuck at Faults and Bridging Faults
venue: 2014 IEEE 23rd Asian Test Symposium
year: 2014

abstract: Test compaction is an important aspect in the post production test since it is able to reduce the test data and the test costs, respectively. Current automatic test pattern generation (ATPG) methods treat all faults independently from each other which limits the test compaction capability. We propose a new optimization satisfiability (SAT) based ATPG for compact test set generation with high fault coverage as well as a new retargeting stage for test set reduction. The ATPG is based on a novel multiple target test generation formulation using optimization techniques. Robust SAT based solving algorithms are leveraged to determine compatible fault groups which can be detected by the same test. The proposed technique can be used during initial compact test generation as well as a post process to increase the compactness of existing test sets, e.g. generated by commercial tools, in an iterative manner. Experimental results show that the proposed SAT based approach is able to produce highly compacted test sets with high fault coverage for stuck at as well as transition faults. The approach is able to produce lower pattern counts than a commercial ATPG tool. For one industrial circuit, the test set size can even be reduced down to 26% of the size generated by a commercial ATPG tool.
author_names: Stephan Eggersgluss

Kenneth Schmitz

Rene Krenz-Baath

Rolf Drechsler
title: On Optimization Based ATPG and Its Application for Highly Compacted Test Sets
venue: IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems
year: 2016

abstract: Crosstalk faults have emerged as a significant mechanism for circuit failure. Long signal nets are of particular concern because they tend to have a higher coupling capacitance to overall capacitance ratio. A typical long net also has multiple aggressors. In generating patterns to create maximal crosstalk noise on a net, it may not be possible to activate all aggressors logically or simultaneously. Therefore, pattern generation must focus on activating a maximal subset of aggressors switching around the same time the victim net switches. This is a well known problem. In this paper, we present a novel solution assuming a unit delay model for the gates, combining 0 1 integer linear program (ILP) with traditional stuck at fault ATPG. The maximal aggressor activation is formulated as a linear programming problem while the fault effect propagation is treated as an ATPG problem and the gate delays are subsumed by a circuit transformation. The proposed technique was applied to ISCAS 85 benchmark circuits. Results indicate that percentage of total capacitance that can be switched varies from 30 80%
author_names: Kunal P Ganeshpure

Sandip Kundu
title: On ATPG for multiple aggressor crosstalk faults in presence of gate delays
venue: 2007 IEEE International Test Conference
year: 2007

abstract: Crosstalk faults have emerged as a significant mechanism of circuit failure due to decreasing process geometries and increasing operation frequencies. Long signal nets are highly susceptible to crosstalk faults because they tend to have a higher coupling capacitance to overall capacitance ratio. Moreover, a typical long net also has multiple aggressors. In generating patterns to create maximal crosstalk induced delay on a victim net, it may be impossible to activate all aggressors logically or simultaneously to constructively induce maximum noise at the victim. Therefore, pattern generation must focus on activating a maximal subset of aggressors, weighted by actual coupling capacitance value, in close temporal proximity of the victim net transition. This max satisfiability problem is constrained by fault effect propagation condition which involves determining an input signal assignment so as to propagate the fault effect at the victim to the primary output. In this paper, we present Automatic Test Pattern Generation (ATPG) solutions for multiple aggressor crosstalk faults for zero and unit delay models and compare the magnitude of crosstalk induced delay at the victim net. Our solution involves a combination of 0 1 Integer Linear Programming (ILP) for maximal aggressor excitation. Fault effect propagation is solved independently by using traditional stuck at fault ATPG or by generating additional ILP constraints thus forming a integrated ILP formulation with error propagation. The effect of gate delays is summed by circuit transformation. The proposed technique was applied to ISCAS85 benchmark circuits. Results indicate that the percentage of total capacitance that can be switched varies from 75 100% for zero delay and 30 80% for variable delay case while achieving propagation of the fault effect to primary output.
author_names: Kunal P Ganeshpure

Sandip Kundu
title: On ATPG for Multiple Aggressor Crosstalk Faults
venue: IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems
year: 2010

abstract: A testable realization of Generalized Reed Muller (GRM) or EXOR Sum of Products (ESOP) expression has been proposed that admits a combined universal test set of size (2n+6) for detection of stuck at and bridging faults. For GRM implementation, the test set detects all single stuck at and bridging faults (both OR and AND type) and a large number of multiple bridging faults. For ESOP, a few single bridging faults may remain untested, occurrence of which can be avoided by employing a design and layout technique. The test set is independent of the function and the circuit under test and can be stored in a ROM on chip for built in self test. For several benchmark circuits, the size of the test set is found to be much smaller than an ATPG generated test set or those of the previous methods.
author_names: Hafizur Rahaman

Debesh Kumar Das

Bhargab B Bhattacharya
title: Easily testable realization of GRM and ESOP networks for detecting stuck at and bridging faults
venue: 17th International Conference on VLSI Design. Proceedings.
year: 2004

abstract: Failures caused by phenomena such as crosstalk or power supply noise are gaining in importance in advanced nanoscale technologies. The detection of such complex defects benefits from the satisfaction of certain constraints, for instance justifying specific transitions on neighbouring lines of the defect location. We present a SAT based ATPG tool that supports the enhanced conditional multiple stuck at fault model (ECMS@ This model can specify multiple fault locations along with a set of hard conditions imposed on arbitrary lines; hard conditions must hold in order for the fault effect to become active. Additionally, optimisation constraints that may be required for best coverage can be specified via a set of soft conditions. The introduced tool justifies as many of these conditions as possible, using a mechanism known as SAT with preferences. Several applications are discussed and evaluated by extensive experimental data. Furthermore, a novel fault clustering technique is introduced, thanks to which the time required to classify all stuck at faults in a suite of industrial benchmarks was reduced by up to 65%
author_names: Alexander Czutro

Matthias Sauer

Tobias Schubert

Ilia Polian

Bernd Becker
title: SAT ATPG using preferences for improved detection of complex defect mechanisms
venue: 2012 IEEE 30th VLSI Test Symposium (VTS)
year: 2012

abstract: Decreasing process geometries and increasing operating frequencies have made VLSI circuits more susceptible to signal integrity related failures. Capacitive crosstalk is one of the causes of such kind of failures. Crosstalk fault results from switching of neighboring lines that are capacitively coupled. Long nets are more susceptible to crosstalk faults because they tend to have a higher coupling capacitance to overall capacitance ratio. A typical long net has multiple aggressors. In generating patterns to create maximal crosstalk noise, it may not be possible to activate all aggressors at the same time. Therefore, pattern generation must focus on activating a maximal subset of aggressors weighted by actual coupling capacitance values. This is a variant of max satisfiability problem. Unlike a traditional max satisfiability problem, here we must deal with signal propagation to an observable output. In this paper, the authors present a novel solution that combines 0 1 integer linear program (ILP) with traditional stuck at fault ATPG. The maximal aggressor activation is formulated as a linear programming problem while the fault effect propagation is treated as an ATPG problem. The problems are separated by min cut circuit partitioning technique based on Kernighan Lin Fiduccia Mattheyses (KLFM) method. This proposed technique was applied to ISCAS 85 benchmark circuits. Results indicated that 75 100% of the aggressors could be switched for generating crosstalk noise while satisfying requirement of sensitizing a path to the output
author_names: Kunal P Ganeshpure

Sandip Kundu
title: Automatic Test Pattern Generation for Maximal Circuit Noise in Multiple Aggressor Crosstalk Faults
venue: 2007 Design, Automation Test in Europe Conference Exhibition
year: 2007

abstract: Contest (cone oriented test pattern generator) an ATPG (automatic test pattern generation) tool for very large combinational digital circuits, is presented. Contest is based on four major ideas. Cone oriented circuit partitioning reduces the circuit complexity and increases the number of dominators. The propagation graph is a dynamic data structure that keeps track of all paths from the fault location to a primary output. The multiple backtrace procedure reduces contradictory node assignments by examination of fanout nodes and dynamic implications. The pattern parallel fault dropping technique is based on Hamming distance variations of generated test patterns. Experimental results for benchmark circuits containing up to 40000 nodes illustrate the superiority of the ATPG system. For these circuits a 100% fault coverage for all detectable stuck at faults and a 100% redundancy identification are achieved.<ETX>
author_names: Udo Mahlstedt

Torsten Gruning

Cengiz Ozcan

Wilfried Daehn
title: Contest: a fast ATPG tool for very large combinational circuits
venue: 1990 IEEE International Conference on Computer Aided Design. Digest of Technical Papers
year: 1990