In this paper, we present a novel approach to run scan diagnosis in a high volume manufacturing (HVM) environment. Our methodology enables two usage modes during scan diagnosis; we can perform diagnosis on all failing partitions on all units (a) on production testers directly or (b) on a few compute machines. Diagnosis or fault dictionary based methods are employed to pre-generate a suspect database (DB) for each design partition. Computationally efficient capture and chain diagnosis algorithms are developed to query the DB to form a suspect universe that explains the fail signature. Only certain pages of the DB are loaded in memory at any given time, requiring no more than a few megabytes of RAM. The technique has been successfully demonstrated on two Intel products with significant cost savings realized over the traditional approach. Diagnosis results have been validated by comparing against the output of a commercial diagnosis tool on thousands of wafers; more importantly, 97% of actual defects confirmed by physical failure analysis (FA) are successfully identified by the proposed approach.

The test patterns computed for detecting the manufacturing defects in the electronic circuits are generally insufficient for diagnosis. The test set compaction and failure log truncation lead to loss of critical failure observations that diagnosis might depend on. In this context, it is beneficial to know the diagnostic usefulness of failures so that we can log the more useful failures instead of logging the initial failures. In this paper, we evaluate three metrics to gauge such diagnostic usefulness in real-time by observing the circuit responses on the tester. We implement a pattern selection framework for failure logging and compare the results with those achieved by logging the initial failures. Using one of our proposed metrics, we were able to improve the diagnosis quality for a significant number of faulty instances of ISCAS'89 and IWLS'05 benchmarks having 1-7 inserted stuck-at and transition faults.

Diagnosis of each failed part requires the failed data captured on the test equipment. However, due to memory limitations on the tester, one often cannot store all the failed data for every chip tested. Consequently, truncated failure logs are used instead of complete logs for each part. Such truncation of the failure logs can result in very long turn-around times for diagnosis because important failure points may be removed from the log. Subsequently, the accuracy and resolution of final diagnosis may suffer even after multiple iterations of diagnosis. In addition, the existing test response compaction techniques though good for testing, either adversely affect diagnosis or are highly sensitive to deviation from the chosen fault model. In this context, the industry needs dynamic selection of better failure logs that enhances diagnosis. In this paper, we propose a number of metrics based on information theory that may help in selecting failure logs dynamically for improving the accuracy and resolution of final diagnosis. We also report on the efficacy of these metrics through the results of our experiments.

One of the important challenges in testing modern SOCs is the presence of small embedded memories. These memories are too small to employ memory BIST. Also, making these embedded memories scan-able or employing MBIST would increase the area overhead and/or test application time.

A diagnostic test pattern generator using a Satisfiability Modulo Theory (SMT) solver is proposed. Rather than targeting a single fault pair at a time, the proposed SMT approach can distinguish multiple fault pairs in a single instance. Several heuristics are proposed to constrain the SMT formula to further reduce the search space, including fault selection, excitation constraint, reduced primary output vector, and cone-of-influence reduction. Experimental results for the ISCAS85 and full-scan versions of ISCAS89 benchmark circuits show that fewer diagnostic vectors are generated compared with conventional diagnostic test generation methods. Up to 73% reduction in the number of vectors generated can be achieved in large circuits.

We present a new 2-phase symbolic execution driven strategy that achieves high branch coverage in software quickly. Phase 1 follows a greedy approach that quickly covers as many branches as possible by exploring each branch through its corresponding shortest path prefix. Phase 2 covers the remaining branches that are left uncovered if the shortest path to the branch was infeasible. In Phase 1, a basic conflict-driven learning is used to skip all the paths that may have any of the earlier encountered conflicting conditions, while in Phase 2, a more intelligent conflict-driven learning is used to skip regions that do not have a feasible path to any unexplored branch. This results in considerable reduction in unnecessary SMT solver calls. Experimental results show that significant speedup can be achieved, effectively reducing the time to detect a bug and providing higher branch coverage for a fixed time-out period than previous techniques.

Symbolic techniques have been shown to be very effective in path-based test generation, however, they fail to scale to large programs due to the exponential number of paths to be explored. In this paper, we focus on tackling this path explosion problem and propose search strategies to achieve quick branch coverage under symbolic execution, while exploring only a fraction of paths in the program. We present a reach ability-guided strategy that makes use of the reach ability graph of the program to explore unvisited portions of the program and a conflict-driven backtracking strategy that utilizes conflict analysis to perform nonchronological backtracking. We present experimental evidence that these strategies can significantly reduce the search space and improve the speed of test generation for programs.

A digital circuit usually comprises a controller and datapath. The time spent for determining a valid controller behavior to detect a fault usually dominates test generation time. A validation test set is used to verify controller behavior and, hence, it activates various controller behaviors. In this paper, we present a novel methodology wherein the controller behaviors exercised by test sequences in a validation test set are reused for detecting faults in the datapath. A heuristic is used to identify controller behaviors that can justify/propagate pre-computed test vectors/responses of datapath register-transfer level (RTL) modules. Such controller behaviors are said to becompatiblewith the corresponding precomputed test vectors/responses. The heuristic is fairly accurate, resulting in the detection of a majority of stuck-at faults in the datapath RTL modules. Also, since test generation is performed at the RTL and the controller behavior is predetermined, test generation time is reduced. For microprocessors, if the validation test set consists of instruction sequences then the proposed methodology also generates instruction-level test sequences.

In this paper, we present a novel and accurate method for identifying design for testability (DFT) solutions for register-transfer level (RTL) circuits. Test generation proceeds by abstracting the circuit components using input/output propagation rules so that any justification/propagation event can be captured as a Boolean implication. Consequently, the RTL test generation problem is reduced to a satisfiability (SAT) instance. If a given SAT instance is not satisfiable, then we identify Boolean implications (also known as the unsatisfiable segment) that are responsible for unsatisfiability. We show that adding DFT elements is equivalent to modifying these clauses such that the unsatisfiable segment becomes satisfiable. The proposed DFT technique is both fast and accurate as it is applicable to RTL and mixed gate-level/RTL circuits and uses exact unsatisfiability conditions to identify the DFT solutions.

In this paper, we present a test generation framework for quantum cellular automata (QCA) circuits. QCA is a nanotechnology that has attracted recent significant attention and shows promise as a viable future technology. This work is motivated by the fact that the stuck-at fault test set of a circuit is not guaranteed to detect all defects that can occur in its QCA implementation. We show how to generate additional test vectors to supplement the stuck-at fault test set to guarantee that all simulated defects in the QCA gates get detected. Since nanotechnologies will be dominated by interconnects, we also target bridging faults on QCA interconnects. The efficacy of our framework is established through its application to QCA implementations of MCNC and ISCAS'85 benchmarks that use majority gates as primitives

In this paper, we present a satisfiability (SAT)-based framework for automatically generating test programs that target gate-level stuck-at faults in microprocessors. The microarchitectural description of a processor is first translated into a unified register-transfer level (RTL) circuit description, called assignment decision diagram (ADD), for test analysis. Test generation involves extraction of justification/propagation paths in the unified circuit representation from an embedded module's input-output (I/O) ports to primary I/O ports, abstraction of RTL modules in the justification/propagation paths, and translation of these paths into Boolean clauses in conjunctive normal form (CNF). Additional clauses are added that capture precomputed test vectors/responses at the embedded module's I/O ports. An SAT solver is then invoked to find valid paths that justify the precomputed vectors to primary input ports and propagate the good/faulty responses to primary output ports. Since the ADD is derived directly from a microarchitectural description, the generated test sequences correspond to a test program. If a given SAT instance is not satisfiable, then Boolean implications (also known as the unsatisfiable segment) that are responsible for unsatisfiability are efficiently and accurately identified. We show that adding design for testability (DFT) elements is equivalent to modifying these clauses such that the unsatisfiable segment becomes satisfiable. Test generation at the RTL also imposes a large number of initial conditions that need to be satisfied for successful detection of targeted stuck-at faults. We demonstrate that application of the Boolean constraint propagation (BCP) engine in SAT solvers propagates these conditions leading to significant pruning of the sequential search space which in turn leads to a reduction in test generation time. Experimental results demonstrate an 11.1X speedup in test generation time for test generation at the RTL over a state-of-the-art gate-level sequential generator called MIX, at comparable fault coverages. An unsatisifiability-based DFT approach at the RTL improves this fault coverage to near 100% and incurs very low area overhead (3.1%). Unlike previous approaches that either generate a test program consisting of random instruction sequences or assume the existence of test program templates, the proposed approach constructs test programs in a deterministic fashion from the microarchitectural description of a processor

In this paper, we present a test generation framework for testing of quantum cellular automata (QCA) circuits. QCA is a nanotechnology that has attracted significant recent attention and shows immense promise as a viable future technology. This work is motivated by the fact that the stuck-at fault test set of a circuit is not guaranteed to detect all defects that can occur in its QCA implementation. We show how to generate additional test vectors to supplement the stuck-at fault test set to guarantee that all simulated defects in the QCA gates get detected. Since nanotechnologies will be dominated by interconnects, we also target bridging faults on QCA interconnects. The efficacy of our framework is established through its application to QCA implementations of MCNC benchmarks that use majority gates as primitives

In this paper, we present a satisfiability (SAT)-based algorithm for automatically generating test sequences that target gate-level stuck-at faults in a circuit by using its register-transfer level (RTL) description. Our methodology uses a unified RTL circuit representation, called assignment-decision diagrams (ADDs), for test analysis. Test generation proceeds by abstracting the components in this unified representation using input/output propagation rules, so that any justification/propagation event can be captured as a Boolean implication. Consequently, we reduce RTL test generation to an SAT instance that has a significantly lower complexity than the equivalent problem at the gate level. Our algorithm is tailored to overcome the disadvantages of several existing RTL precomputed test-set-based approaches, such as the need for an explicit controller/datapath separation, the use of all test vectors or none from the precomputed test set for any given module, a dependence on symbolic justification (observability) paths from (to) circuit inputs (outputs) for a module, and a lack of applicability to mixed gate-level/RTL designs. Using the state-of-the-art SAT solver Zchaff, we show that our RTL test generator can outperform gate-level sequential automatic test-pattern generation (ATPG), in terms of both fault coverage and test-generation time (two-to-three orders of magnitude speedup), in comparable test-application times. Furthermore, we show that in a bilevel testing scenario, in which RTL ATPG is followed by gate-level sequential ATPG on the remaining faults, we improve the fault coverage even further, while maintaining a high speedup in test-generation time (nearly 32/spl times/) over pure gate-level sequential ATPG, at comparable test-application times.

In this paper, the authors present compression techniques for effectively reducing the test-data-volume requirements of modern systems-on-a-chip (SOC). Their techniques are based on the following observations: 1) Conventional test compression schemes, which are designed to satisfy various constraints including low hardware overheads and decompression times, cannot fully exploit compression opportunities present in test data and 2) due to the diversity of components used in SOCs (and consequently in their test strategies and test-data characteristics), a single compression strategy may not be best suited to handle them. The authors propose the use of multilevel and heterogeneous test compression schemes to address the above issues and demonstrate that they can provide significant reductions in the test volume above currently known state-of-the-art test compression techniques. An architecture that reuses infrastructure components already present in SOCs (programmable processors, on-chip communication architecture, memory, etc.) for an efficient implementation of their techniques is proposed. Finally, the authors suggest various architectural-customization techniques, such as partitioning of the decompression functionality between the hardware and software and the addition of custom instructions, to improve decompression times and reduce hardware overheads. Experiments with several designs, including an industrial media-processing SOC, demonstrate the efficacy of the proposed techniques in achieving test-data-volume reductions with low overheads

In this paper, we present a novel and accurate method for identifying design for testability (DFT) solutions for register-transfer level (RTL) circuits. In this technique, clauses are generated using a satisfiability (SAT) based automatic test pattern generation (ATPG) tool to represent the control and data flow for a module under test in the given RTL circuit. RTL test generation makes use of the concept of pre-computed test sets for different RTL modules. The generated clauses corresponding to different pre-computed test vectors are then resolved by a SAT solver to obtain the test sequences for that module. In case of an unsatisfiable (UNSAT) solution, recent advances in the field of satisfiability enable us to accurately and efficiently identify clauses that are responsible for unsatisfiability (also known as the unsatisfiable segment). We show that adding DFT elements is equivalent to modifying clauses such that the unsatisfiable segment becomes satisfiable. In order to minimize the number of DFT elements added to a circuit, a greedy algorithm is used to select circuit variables for DFT such that all the unsatisfiable segments become satisfiable. Unlike existing DFT techniques that are either inefficient in terms of the amount of test hardware added or take significant time to identify an efficient solution, the proposed DFT technique is both fast and accurate as it is applicable to RTL and mixed gate-level/RTL circuits and uses UNSAT to identify the DFT solutions. Experimental results on benchmarks show that for RTL circuits, the CPU time required to identify pre-computed test vectors for which the SAT ATPG fails to generate test sequences and to select DFT solutions for such cases is two orders of magnitude smaller than the time required for a single run of a gate-level sequential test generator. The DFT solution has very low area overhead (an average of 1.7%) and results in near-100% fault coverage.

We present a satisfiability-based algorithm for automatically generating test sequences that target gate-level stuck-at faults in a circuit by using its register-transfer level (RTL) description. Our methodology exploits a popular, unified RTL circuit representation, called assignment decision diagrams, for its analysis and justifies module-level precomputed test vectors on this representation. Test generation proceeds by abstracting the components in this unified representation using input/output propagation rules, so that any justification/propagation event can be captured as a Boolean implication. Consequently, we reduce RTL test generation to a satisfiability (SAT) instance that has a significantly lower complexity than the equivalent problem at the gate-level. Using the state-of-the-art SAT solver ZCHAFF, we show that our RTL test generator can outperform gate-level sequential automatic test pattern generation (ATPG) in terms of both fault coverage and test generation time (two-to-three orders of magnitude speed-up), in comparable test application times. Furthermore, we show that in a bi-level testing scenario, in which RTL ATPG is followed by gate-level sequential ATPG on the remaining faults, we improve the fault coverage even further, while maintaining a high speed-up in test generation time (nearly 29X) over pure gate-level sequential ATPG, at comparable test application times.