01 August 2018
Keerthana Samala, for the Master of Science degree in Electrical and Computer, presented on 05/11/2018, at Southern Illinois University Carbondale. TITLE: Test Pattern Generation for Double Transition Faults MAJOR PROFESSOR: Dr. Spyros Tragoudas Under double transition fault model, a fault is associated with a pair of lines and a pair of transitions on these lines. The proposed double transition fault model includes set of cases where the increased delay of a single faulty line may be too small to cause the faulty behavior of the circuit. However, when this delay propagates through another faulty line then the total delay is assumed to be beyond the specified circuit delay which may cause the circuit to fail, thus causing a double transition fault. We propose a test generation procedure for double transition faults, considering different cases of the model. For this purpose a PODEM based Automatic Test Pattern Generation Tool was modified and used. We present experimental results of this procedure for several ISCAS '85 and ISCAS'89 benchmark circuits.
Lenox, Joseph Daniel
01 December 2016
(has links) (PDF)
A method to perform implicit path delay fault grading on GPGPU architectures is presented. Experimentally it is shown that it is over 1200x faster than a single-core implicit path delay fault grading method previously in the literature for higher accuracy and can be shown to scale to multiple GPGPUs. A post-silicon test pattern generation strategy to maximize the efficiency of broadside tests applied to a sequential design for a limited test budget is presented. Arguments are made for this approach for detecting embedded Trojan ICs in the next-state functions of a sequential system; they are based on a model where long sequences of inputs that are applied to the system in the functional mode can detect if Trojan hardware is triggered with high probability. An efficient and scalable input generation algorithm for broadside tests is introduced and its performance on ISCAS'89 and ITC'99 benchmark circuits is evaluated. A design-for-authentication strategy is presented for the insertion of cells to efficiently partition the combinational core of a circuit to detect inserted Trojan ICs. It is shown that the approach, combined with pseudo-exhaustive test pattern generation, guarantees detection in certain circumstances.
Gent, Kelson Andrew
01 December 2016
Integrated circuits, from general purpose microprocessors to application specific designs (ASICs), have become ubiquitous in modern technology. As our applications have become more complex, so too have the circuits used to drive them. Moore's law predicts that the number of transistors on a chip doubles every 18-24 months. This explosion in circuit size has also lead to significant growth in testing effort required to verify the design. In order to cope with the required effort, the testing problem must be approached from several different design levels. In particular, exploiting the Register Transfer Level for test generation allows for the use of relational information unavailable at the structural level. This dissertation demonstrates several novel methods for generating tests applicable for both structural and functional tests. These testing methods allow for significantly faster test generation for functional tests as well as providing high levels of fault coverage during structural test, typically outperforming previous state of the art methods. First, a semi-formal method for functional verification is presented. The approach utilizes a SMT-based bounded model checker in combination with an ant colony optimization based search engine to generate tests with high branch coverage. Additionally, the method is utilized to identify unreachable code paths within the RTL. Compared to previous methods, the experimental results show increased levels of coverage and improved performance. Then, an ant colony optimization algorithm is used to generate high quality tests for fault coverage. By utilizing co-simulation at the RTL and gate level, tests are generated for both levels simultaneously. This method is shown to reach previously unseen levels of fault coverage with significantly lower computational effort. Additionally, the engine was also shown to be effective for behavioral level test generation. Next, an abstraction method for functional test generation is presented utilizing program slicing and data mining. The abstraction allows us to generate high quality test vectors that navigate extremely narrow paths in the state space. The method reaches previously unseen levels of coverage and is able to justify very difficult to reach control states within the circuit. Then, a new method of fault grading test vectors is introduced based on the concept of operator coverage. Operator coverage measures the behavioral coverage in each synthesizable statement in the RTL by creating a set of coverage points for each arithmetic and logical operator. The metric shows a strong relationship with fault coverage for coverage forecasting and vector comparison. Additionally, it provides significant reductions in computation time compared to other vector grading methods. Finally, the prior metric is utilized for creating a framework of automatic test pattern generation for defect coverage at the RTL. This framework provides the unique ability to automatically generate high quality test vectors for functional and defect level testing at the RTL without the need for synthesis. In summary, We present a set of tools for the analysis and test of circuits at the RTL. By leveraging information available at HDL, we can generate tests to exercise particular properties that are extremely difficult to extract at the gate level. / Ph. D.
2010 May 1900
Delay testing is used to detect timing defects and ensure that a circuit meets its timing specifications. The growing need for delay testing is a result of the advances in deep submicron (DSM) semiconductor technology and the increase in clock frequency. Small delay defects that previously were benign now produce delay faults, due to reduced timing margins. This research focuses on the development of new test methods for small delay defects, within the limits of affordable test generation cost and pattern count. First, a new dynamic compaction algorithm has been proposed to generate compacted test sets for K longest paths per gate (KLPG) in combinational circuits or scan-based sequential circuits. This algorithm uses a greedy approach to compact paths with non-conflicting necessary assignments together during test generation. Second, to make this dynamic compaction approach practical for industrial use, a recursive learning algorithm has been implemented to identify more necessary assignments for each path, so that the path-to-test-pattern matching using necessary assignments is more accurate. Third, a realistic low cost fault coverage metric targeting both global and local delay faults has been developed. The metric suggests the test strategy of generating a different number of longest paths for each line in the circuit while maintaining high fault coverage. The number of paths and type of test depends on the timing slack of the paths under this metric. Experimental results for ISCAS89 benchmark circuits and three industry circuits show that the pattern count of KLPG can be significantly reduced using the proposed methods. The pattern count is comparable to that of transition fault test, while achieving higher test quality. Finally, the proposed ATPG methodology has been applied to an industrial quad-core microprocessor. FMAX testing has been done on many devices and silicon data has shown the benefit of KLPG test.
This thesis presents a new approach to improve the efficiency of defect screening during manufacturing test of digital integrated circuits through the use of multiple observations during test generation. To address the limitations of test sets generated based on the single stuck-at fault model, we combine the advantages of multiple-detect and detection at all observable outputs in order to generate test sets that can improve surrogate detection. Imposing additional constraints, such as multiple observations, on the test generation process motivates the development of a new constrained automatic test pattern generation (ATPG) work flow that leverages the recent advancements in the Boolean satisfiability (SAT) problem. Building this ATPG work flow brings its own technical challenges and solutions described in detail in this thesis. To assess the effectiveness of the test sets generated by the proposed ATPG work flow, we evaluate them using coverage metrics for fault models that are not targeted explicitly during test generation. / Thesis / Master of Applied Science (MASc)
16 December 2013
Memory arrays cannot be as easily tested as other storage elements in a chip. Most of the flip-flops (FFs) in a chip can be replaced by scan cells in scan-based design. However, the bits in memory arrays cannot be replaced by scan cells, due to the area cost and the timing-critical nature of many of the paths into and out of memories. Thus, bits in a memory array can be considered non-scan storage elements. Test methods such as memory built-in self-test (MBIST), functional test, and macro test are used to test memory arrays. However, these tests aren’t sufficient to test the paths through the memory arrays. During structural (scan) test generation, memory arrays are treated as “black boxes” or memory arrays are bypassed to a known value. Black boxes decrease coverage loss while bypassing increases chip area and delay. Path delay test through memory arrays is proposed using pseudo functional test (PFT) with K Longest Paths Per Gate (KLPG). In this technique, any longest path that is captured into a non-scan cell (including a memory cell) is propagated to a scan cell. The propagation of the captured value from non-scan cell to scan cell occurs during low-speed clock cycles. In this work, we assume that only one extra coda cycle is sufficient to propagate the captured value to a scan cell. This is true if the output of the memory feeds combinational logic that in turn feeds scan cells. When we want to launch a transition from a memory output, different values are written into different address locations and the address is toggled between the locations. The ATPG writes the different values into the memory cells during the preamble cycles. In the case of launching a transition out of a non-scan cell, the cell must be written with an initial value during the preamble cycles, and the next value set on the non-scan cell input. Thus, it is possible to capture and launch transitions into and from memory and non-scan cells and thus test the path delay of the longest paths into and out of memory and non-scan cells.
01 July 2005
Static learning in the form of logic implications captures Boolean relationships between various gates in a circuit. In the past, logic implications have been applied in several areas of electronic design automation (EDA) including: test-pattern-generation, logic and fault simulation, fault diagnosis, logic optimization, etc. While logic implications have assisted in solving several EDA problems, their usefulness has not been fully explored. We believe that logic implications have not been carefully analyzed in the past, and this lack of thorough investigation has limited their applicability in solving hard EDA problems. In this dissertation, we offer deeper insights into the Boolean relationships exhibited in a circuit, and present techniques to extract their full potential in solving two hard problems in test and verification: (1) Efficient identification of sequentially untestable stuck-at faults, and (2) Equivalence checking of sequential circuits. Additionally, for the dissertation, we define a new concept called multi-cycle path delay faults (M-pdf) for latch based designs with multiple clock domains, and propose an implications-based methodology for the identification of untestable M-pdfs for such designs. One of the main bottlenecks in the efficiency of test-pattern-generation (TPG) is the presence of untestable faults in a design. State-of-the-art automatic test pattern generators (ATPG) spend a lot of effort (in both time and memory) targeting untestable faults before aborting on such faults, or, eventually identifying these faults as untestable (if given enough computational resources). In either case, TPG is considerably slowed down by the presence of untestable faults. Thus, efficient methods to identify untestable faults are desired. In this dissertation, we discuss a number of solutions that we have developed for the purpose of untestable fault identification. The techniques that we propose are fault-independent and explore properties associated with logic implications to derive conclusions about untestable faults. Experimental results for benchmark circuits show that our techniques achieve a significant increase in the number of untestable faults identified, at low memory and computational overhead. The second related problem that we address in this proposal is that of determining the equivalence of sequential circuits. During the design phase, hardware goes through several stages of optimizations (for area, speed, power, etc). Determining the functional correctness of the design after each optimization step by means of exhaustive simulation can be prohibitively expensive. An alternative to prove functional correctness of the optimized design is to determine the design's functional equivalence w.r.t. some golden model which is known to be functionally correct. Efficient techniques to perform this process, known as equivalence checking, have been investigated in the research community. However, equivalence checking of sequential circuits still remains a challenging problem. In an attempt to solve this problem, we propose a Boolean SAT (satisfiability) based framework that utilizes logic implications for the purpose of sequential equivalence checking. Finally, we define a new concept called multi-cycle path-delay faults (M-pdfs). Traditionally, path delay faults have been analyzed for flip-flop based designs over the boundary of a single clock cycle. However, path delay faults may span multiple clock cycles, and a technique is desired to model and analyze such path delay faults. This is especially essential for latch based designs with multiple clock domains, because the problem of identifying untestable faults is more complex in such design environments. In this dissertation, we propose a three-step methodology to identify untestable M-pdfs in latch-based designs with multiple clocks using logic implications. / Ph. D.
03 August 2004
With ever shrinking geometries, growing metal density and increasing clock rate on chips, delay testing is becoming a necessity in industry to maintain test quality for speed-related failures. The purpose of delay testing is to verify that the circuit operates correctly at the rated speed. However, functional tests for delay defects are usually unacceptable for large scale designs due to the prohibitive cost of functional test patterns and the difficulty in achieving very high fault coverage. Scan-based delay testing, which could ensure a high delay fault coverage at reasonable development cost, provides a good alternative to the at-speed functional test. This dissertation addresses several key challenges in scan-based delay testing and develops efficient Automatic Test Pattern Generation (ATPG) and Design-for-testability (DFT) algorithms for delay testing. In the dissertation, two algorithms are first proposed for computing and applying transition test patterns using stuck-at test vectors, thus avoiding the need for a transition fault test generator. The experimental results show that we can improve both test data volume and test application time by 46.5% over a commercial transition ATPG tool. Secondly, we propose a hybrid scan-based delay testing technique for compact and high fault coverage test set, which combines the advantages of both the skewed-load and broadside test application methods. On an average, about 4.5% improvement in fault coverage is obtained by the hybrid approach over the broad-side approach, with very little hardware overhead. Thirdly, we propose and develop a constrained ATPG algorithm for scan-based delay testing, which addresses the overtesting problem due to the possible detection of functionally untestable faults in scan-based testing. The experimental results show that our method efficiently generates a test set for functionally testable transition faults and reduces the yield loss due to overtesting of functionally untestable transition faults. Finally, a new approach on identifying functionally untestable transition faults in non-scan sequential circuits is presented. We formulate a new dominance relationship for transition faults and use it to help identify more untestable transition faults on top of a fault-independent method based on static implications. The experimental results for ISCAS89 sequential benchmark circuits show that our approach can identify many more functionally untestable transition faults than previously reported. / Ph. D.
06 March 2017
Integrated circuits have traveled a long way from being a general purpose microprocessor to an application specific circuit. It has become an integral part of the modern era of technology that we live in. As the applications and their complexities are increasing rapidly every day, so are the sizes of these circuits. With the increase in the design size, the associated testing effort to verify these designs is also increased. The goal of this thesis is to leverage some of the static analysis techniques to reduce the effort of testing and verification at the register transfer level. Studying a design at register transfer level gives exposure to the relational information for the design which is inaccessible at the structural level. In this thesis, we present a way to generate a Data Dependency Graph and a Control Flow Graph out of a register transfer level description of a circuit description. Next, the generated graphs are used to perform relation mining to improve the test generation process in terms of speed, branch coverage and number of test vectors generated. The generated control flow graph gives valuable information about the flow of information through the circuit design. We are using this information to create a framework to improve the branch reachability analysis mainly in terms of the speed. We show the efficiency of our methods by running them through a suite of ITC'99 benchmark circuits. / Master of Science
Exploring Temporal and Spatial Correlations on Circuit Variables for Enhancing Simulation-based Test GenerationChen, Xiaoding 19 September 2006 (has links)
The ever-increasing complexity and size of current circuit designs have made testing and verification major bottlenecks in the design flow of VLSI (Very Large Scale Integrated) circuits. Statistics show that more than 70% of the design effort can be spent on functional verification and manufacturing testing. This percentage is expected to increase in the future if no significant strides in these areas are made. In this dissertation, we target three related problems in simulation-based Design Verification and Testing: Sequential ATPG (Automatic Test Pattern Generation), Unbounded Model Checking (UMC) of safety properties, and low power testing for full-scan sequential circuits. We model these three problems as simulation-based pattern generation problems and exploit novel ATPG algorithms to increase the effectiveness of sequential ATPGs. The main challenge for fault/error detection in sequential circuits is the large number of flip-flops (FFs) in modern designs. Due to the large number and variable length of test sequences required for such circuits, the existing deterministic ATPG algorithms fail to achieve high test coverages. Such algorithms typically work by first unrolling the sequential circuit and then performing frequent backtracking to generate test vectors for fault detection. For the hard-to-detect faults, these schemes either run out of memory or require a huge computational effort. We show that simulation-based ATPGs, on the other hand, scale very well for large circuits as they perform only forward simulation. A fundamental problem associated with simulation-based ATPGs is to avoid exhaustive circuit simulation, which is impractical for large designs in the real world, by choosing high quality test vectors that achieve a high test coverage within a low simulation time. We tackle this primary problem by exploiting different correlation-based heuristics. The intuition behind using correlation-based heuristics is to better guide the pattern generation engine such that the specific objective of either fault detection or property verification in UMC or minimizing power consumption during the testing, is achieved in an efficient manner without resorting to exhaustive simulation. In particular, we model and explore the following correlations: (1) temporal correlations, i.e. correlations on each primary input (PI) in different time frames, and (2) spatial correlations, i.e. correlations among different FFs in the same time frame. We employ temporal correlations in the context of pattern generation of a built-in-self-test (BIST) architecture and we explore spatial correlations to guide a logic-simulation-based sequential ATPG and low power scan test generation. Experimental results on ISCAS and ITC benchmark circuits have shown that those correlations can enhance the simulation to discover more faults or design errors in a significantly shorter time. / Ph. D.
Page generated in 0.0351 seconds