Critical path selection is an indispensable step for AC delay test and timing validation. Traditionally, this step relies on the construction of a set of worse-case paths based upon discrete timing models. However, the assumption of discrete timing models can be invalidated by timing defects and process variation in the deep sub-micron domain, which are often continuous in nature. As a result, critical paths defined in a traditional timing analysis approach may not be truly critical in reality. In this paper, we propose using a statistical delay evaluation framework for estimating the quality of a path set. Based upon the new framework, we demonstrate how the traditional definition of a critical path set may deviate from the true critical path set in the deep sub-micron domain. To remedy the problem, we discuss improvements to the existing path selection strategies by including new objectives. We then compare statistical approaches with traditional approaches based upon experimental analysis of both defect-free and defect-injected cases.

In this paper, we propose a new methodology for diagnosis of delay defects in the deep sub micron domain. The key difference between our diagnosis framework and other traditional diagnosis methods lies in our assumptions of the statistical circuit timing and the statistical delay defect size. Due to the statistical nature of the problem, achieving 100% diagnosis resolution cannot be guaranteed. To enhance diagnosis resolution, we propose a 3-phase diagnosis methodology. In the first phase, our goal is to quickly identify a set of candidate suspect faults that are most likely to cause the failing behavior based on logic constraints. In the second phase, we obtain a much smaller suspect fault set by applying a novel diagnosis algorithm that can effectively utilize the statistical timing information based upon a single defect assumption. In the third phase, our goal is to apply additional fine-tuned patterns to successfully narrow down to more exact suspect defect locations. Using a statistical timing analysis framework, we demonstrate the effectiveness of the proposed methodology for delay defect diagnosis, and discuss experimental results based on benchmark circuits.

As technology evolves into the deep sub-micron era, signal integrity problems are growing into a major challenge. An important source of signal integrity problems is the crosstalk noise generated by coupling capacitances between wires. Test vectors that activate and propagate crosstalk noise effects are becoming an essential part of design verification and manufacturing test. However, deriving such vectors is a complex task. In this paper, we propose HyAC, a fast yet accurate hybrid ATPG method targeting multiple-aggressor induced crosstalk errors. Given a victim and a set of aggressors, the proposed ATPG method searches for test vectors to activate and propagate a crosstalk error for the victim. Due to logic constraints, it may not be possible to trigger all aggressors simultaneously. Therefore, firstly we use an implication graph (IG) that consists of logic variables and structural information to check for logic conflicts. If the current set of aggressors is not feasible, our algorithm automatically searches for the next-best subset of aggressors (resulting in the largest noise). After a set of feasible aggressors is identified, we use a modified PODEM [21] algorithm to search for test vectors. This hybrid structural SAT-based ATPG method inherits advantages from both Boolean– satisfiabilitity based methods and structural-based methods to achieve flexibility and efficiency. We demonstrate the accuracy, high quality, and run time efficiency of HyAC through experiments conducted on several benchmark circuits as well as a circuit from a commercial processor. 1.

This paper describes a new post-silicon validation problem for diagnosing systematic timing errors. We illustrate the differences between timing validation and the traditional logic defect diagnosis. The key difference between our validation framework and other traditional diagnosis methods lies in our assumptions of the statistical circuit timing and statistical distribution of the size of timing errors. Different algorithms are proposed and evaluated via statistical timing error injection and simulation. Due to the statistical nature of the problem, 100% diagnosis resolution often cannot be guaranteed. With a statistical timing analysis framework developed in the past, we demonstrate the new concepts in timing validation, and discuss experimental results based upon three types of systematic errors: timing correlation error, crosstalk, and single-site random-size delay perturbation.

In this paper, we study the possibility of using logic defect-level prediction models to predict the detection behavior of statistical timing defects. We compare two known logic models: the Williams-Brown (WB) model and the Mercer-Park-Grimaila-Dworak (MPGD) model. In the WB-model, the defect coverage is replaced by the n-detection transition fault coverage. We first demonstrate that both logic models may fail to predict the detection of statistical timing defects. Then, we propose an improved WB model based upon selection of the hard-to-detect transition faults. We show that, by selecting a proper subset of the hard-to-detect transition faults, the detection behavior of these faults can correlate well to the detection behavior of statistical timing defects. We explain our findings through statistical delay defect injection and simulation, and report results based upon various benchmark circuits.

In this paper, we study the problem of delay defect diagnosis based on statistical timing models. We propose a diagnosis algorithm that can effectively utilize statistical timing information based upon single defect assumption. We evaluate its performance and its applicability to single as well as multiple defect scenarios via statistical defect injection and simulation. With a statistical timing analysis framework developed in the past, we demonstrate the new concept in statistical delay defect diagnosis, and discuss experimental results using benchmark circuits.

The performance of deep submicron designs can be affected by various parametric variations, manufacturing defects, noise or modeling errors that are all statistical in nature. In this paper, we propose a methodology to capture the effects of these statistical variations on circuit performance. It incorporates statistical information into timing analysis to compute the performance sensitivity of internal signals subject to a given type of defect, noise or variation sources. Next, we propose a novel path and segment selection methodology for delay testing based on the results of statistical performance sensitivity analysis. The objective of path/segment selection is to identify a small set of paths and segments such that the delay tests for the selected paths/segments guarantee the detection of performance failure. We apply the proposed path selection technique for selection of a set of paths for dynamic timing analysis considering power supply noise effects. Our experimental results demonstrate the difference in estimated circuit performance for the case when power supply noise effects are considered versus when these effects are ignored. Thus, they indicate the need for considering power supply noise effects on delays during path selection and dynamic timing analysis.

At-speed testing of high-speed circuits is becoming increasingly difficult with external testers due to the growing gap between design and tester performance, growing cost of high-performance testers and increasing yield loss caused by inherent tester inaccuracy. Therefore, empowering the chip to test itself seems like a natural solution. Hardware-based self-testing techniques have limitations due to performance and area overhead and problems caused by the application of non-functional patterns.Embedded software-based self-testing has recently become focus of intense research. In this methodology, the programmable cores are used for on-chip test generation, measurement, response analysis and even diagnosis. After the programmable core on a System-on-Chip (SoC) has been self-tested, it can be reused for testing on-chip buses, interfaces and other non-programmable cores. The advantages of this methodology include at-speed testing, low design-for-testability overhead and application of functional patterns in the functional environment. In this paper, we give a survey and outline the roadmap and challenges of this emerging embedded software-based self-testing paradigm.

We propose a false-path-aware statistical timing analysis framework. In our framework, cell as well as interconnect delays are assumed to be correlated random variables. Our tool can characterize statistical circuit delay distribution for the entire circuit and produce a set of true critical paths.

We propose a new statistical timing analysis algorithm, which produces arrival-time random variables for all internal signals and primary outputs for cell-based designs with all cell delays modeled as random variables. Our algorithm propagates probabilistic timing events through the circuit and obtains final probabilistic events (distributions) at all nodes. The new algorithm is deterministic and flexible in controlling run time and accuracy. However, the algorithm has exponential time complexity for circuits with reconvergent fanouts. In order to solve this problem, we further propose a fast approximate algorithm. Experiments show that this approximate algorithm speeds up the statistical timing analysis by at least an order of magnitude and produces results with small errors when compared with Monte Carlo methods.

Increased noise/interference effects, such as crosstalk, power supply noise, substrate noise and distributed delay variations lead to increased signal integrity problems in deep submicron designs. These problems can cause logic errors and/or performance degradation and must be addressed both in the design for deep submicron and testing for deep submicron phases. Existing delay testing techniques cannot capture the effects of noise on the cell/interconnect delays. In this paper, we address the problem of delay testing considering crosstalk-induced delay effects. We propose solutions for target fault selection and pattern generation. The key elements of our strategy are performance sensitivity analysis with respect to crosstalk noise and a genetic algorithm (GA) based vector generation technique. The role of performance sensitivity analysis is to consider the effects of crosstalk noise during the target fault selection process. Next, for each selected fault consisting of a path and a set of crosstalk noise sources interacting with the path, we apply our iterative GA-based pattern generation process. Our goal is to derive a test that produces a large crosstalk-induced delay effect on the given path. Our technique allows consideration of any number of coupling sources along the target path. Due to its flexibility, efficiency and scalability, the technique can be applied to large circuits.

Noise effects such as power supply and crosstalk noise can significantly impact the performance of deep submicrometer designs. Existing delay testing and timing analysis techniques cannot capture the effects of noise on the signal/cell delays. Therefore, these techniques cannot capture the worst case timing scenarios and the predicted circuit performance might not reflect the worst case circuit delay. More accurate and efficient timing analysis and delay testing strategies need to be developed to predict and guarantee the performance of deep submicrometer designs. In this paper, we propose a new pattern generation technique for delay testing and dynamic timing analysis that can take into account the impact of the power supply noise on the signal propagation delays. In addition to sensitizing the selected paths, the new patterns also cause high power supply noise on the nodes in these paths. Thus, they also cause longer propagation delays for the nodes along the paths. Our experimental results on benchmark circuits show that the new patterns produce significantly longer delays on the selected paths compared to the patterns derived using existing pattern generation methods.

The performance of deep submicron designs can be affected by various parametric variations, manufacturing defects, noise or modeling errors that are all statistical in nature. We propose a statistical framework for analyzing the performance sensitivity of designs to various timing related defects/noise/variations. The core engine of our approach is a highly efficient statistical timing analysis tool. We describe the application of our framework for delay fault modeling and analysis of resistive opens and shorts and as well as interconnect crosstalk. We present experimental results demonstrating the accuracy of our statistical framework as compared to SPICE (for a given set of input patterns) and nominal worst-case analysis. Experimental results for analysis of resistive opens and shorts are also included.

Noise effects such as power supply and crosstalk can significantly affect the performance of deep submicron designs. These delay effects are highly input pattern dependent. Existing path selection and timing analysis techniques cannot capture the effects of noise on cell/interconnect delays. Therefore, the selected critical paths may not be the longest paths and predicted circuit performance might not reflect the worst-case circuit delay. In this paper, we propose a path selection technique that can consider power supply noise effects on the propagation delays. Next, for the selected critical paths, we propose a pattern generation technique for dynamic timing analysis such that the patterns produce the worst-case power supply noise effects on the delays of these paths. Our experimental results demonstrate the difference in estimated circuit performance for the case when power supply noise effects are considered vs. when these effects are ignored. Thus, they validate the need for considering power supply noise effects on delays during path selection and dynamic timing analysis.

This paper addresses the problem of testing path delay faults in a microprocessor core using its instruction set. We propose to self-test a processor core by running an automatically synthesized test program which can achieve a high path delay fault coverage. This paper discusses the method and the prototype software framework for synthesizing such a test program. Based on the processor's instruction set architecture, micro-architecture, RTL netlist as well as gate-level netlist on which the path delay faults are modeled, the method generates deterministic tests (in the form of instruction sequences) by cleverly combining structural and instruction-level test generation techniques. The experimental results for two microprocessors indicate that the test instruction sequences can be successfully generated for a high percentage of testable path delay faults.

This paper addresses the problem of testing path delay faults in a microprocessor using instructions. It is observed that a structurally testable path (i.e., a path testable through at-speed scan) in a microprocessor might not be testable by its instructions simply because no instruction sequence can produce the desired test sequence which can sensitize the paths and capture the fault effect into the destination output/flip-flop at-speed. These paths are called functionally untestable paths. We discuss the impact of delay defects on the functionally untestable paths on the overall circuit performance and illustrate that they do not need to be tested if the delay defect does not cause the path delay to exceed twice the clock period. Identification of such paths helps determine the achievable path delay fault coverage and reduce the subsequent test generation effort. The experimental results for two microprocessors (Parwan and DLX) indicate that a significant percentage of structurally testable paths are functionally untestable and thus need not be tested.

We present new techniques for estimating the maximum instantaneous current through the power supply lines for CMOS circuits. We investigate four different approaches: (1) timed-ATPG-based approach; (2) probability-based approach; (3) genetic algorithm-based approach; and (4) integer linear programming (ILP) approach. The first three approaches produce a tight lower bound on the maximum current. The ILP-based approach produces the exact solutions for small circuits, and tight upper bounds of the solutions for large circuits. Our experimental results show that the upper bounds produced by the ILP approach combined with the lower bounds produced by the other three approaches confine the exact solution for the maximum instantaneous current to a small range.

We propose a new delay test generation technique that can take into account the impact of the power supply noise on the signal propagation delays. This is different from existing delay fault models and test generation techniques that ignore the dependence of path delays on the applied test patterns and cannot capture the worst-case timing scenarios in deep submicron designs. In addition to sensitizing the fault and propagating the fault effects to the primary outputs, our new tests also produce the worst-case power supply noise on the nodes in the target path. Thus, the tests also cause the worst-case propagation delay for the nodes along the target path. Our experimental results on benchmark circuits show that the new delay tests produce significantly longer delays on the tested paths compared to the tests derived using existing delay testing methods.

The speed of new VLSI designs is rapidly increasing. Assuring the performance of the circuit requires that the circuit be tested at its intended operating speed. The high cost of high speed testers makes it impossible for the testers to follow the designs in terms of speed increase. This gap between the speed of the new circuits and the speed of the testers is not likely to disappear. In this paper, we focus on at-speed strategies for testing high speed designs on slower testers. Conventional at-speed testing strategies assume that the primary inputs/outputs can be applied/observed at the circuit rated speed. This requires a high speed tester. Our assumption is that a fast clock matching the speed of the designs is available. We describe two classes of at-speed strategies that can be used on a low speed tester. The first class consists of testing schemes for which the test generation procedure is independent of the speed of the tester. These methods apply multiple input patterns in one tester cycle and the test application time for them can be long. The strategies in the second class of at-speed testing schemes integrate the tester's speed limitations with the test generation process. Due to constraints placed at the test generation process, these schemes might result in a reduced fault coverage. To increase the fault coverage and reduce the test application time, the slow-fast-slow and at-speed strategies can be combined for testing high speed designs on slower testers. We present preliminary experimental results for at-speed schemes for slow testers for transition faults.

We investigate two strategies to guarantee temporal correctness of a combinational circuit. We first propose a new technique to identify and test primitive faults. A primitive fault is a path delay fault that has to be tested to guarantee the performance of the circuit. Primitive faults can consist of single- (SPDF's) or multiple path delay faults (MPDF's). Testing strategies for single primitive faults exist. In this paper, we focus on identifying and testing multiple primitive faults. Identification and testing of these faults is important for at least two reasons: (1) a large percentage of paths in production circuits remain untestable under the SPDF model, and (2) distributed manufacturing defects usually adversely affect more than one path and these defects can be detected only by analyzing multiple affected paths. The SPDF's contained in a multiple primitive fault have to merge at some gate(s). Our methodology can quickly (1) rule out a large number of gates as possible merging gates for primitive faults, and (2) prune the combinations of paths that can never belong to any primitive fault. Our identification procedure also finds a test for the fault. We present a complete algorithm for identifying and testing double path delay faults, Identifying and testing all primitive faults is impractical for large designs. This is because no efficient methods are known for testing primitive faults that include a large number of paths. However, to guarantee that the performance of a digital circuit is not affected by timing defects, it is necessary to test all primitive faults. Our second contribution is a new design for testability method. Our method guarantees that only primitive faults with at most two paths can exist in the circuit in the test mode. The main idea is to efficiently identify a small set of signals for inserting test points to eliminate primitive faults with more than two paths. Our test points only provide controllability. Addition of a single test point can lower the cardinality of several primitive faults. Our approach efficiently re-evaluates primitive delay fault testability of the circuit after insertion of a test point. After a few iterations only primitive faults with at most two paths can exist in the circuit in the test mode. Experimental results on several multilevel combinational benchmark circuits are included to demonstrate the usefulness of our techniques.

We propose a new methodology based on incremental logic restructuring for post-layout performance improvement. The new post-layout logic restructuring technique allows to use accurate interconnection delays for performance optimization, while the incremental nature of the technique guarantees convergence between logic synthesis and layout. The technique can be further integrated with other post-layout optimization techniques such as gate sizing and buffer insertion. Experimental results show that this technique combined with post-layout buffer insertion can achieve an additional 15% improvement in performance compared to designs produced by timing-driven logic optimization followed by pre-layout buffer insertion followed by timing-driven physical design. 1. Introduction Performance-driven logic synthesis followed by performance -driven layout [1] has become a necessity for designing high performance circuits. However, this loosely coupled two-phase timing optimization methodology has...

We present two new algorithms for generating a smallset of patterns for estimating the maximum instantaneouscurrent through the power supply lines for CMOScircuits.The first algorithm is based on timed ATPG,while the second is a probability-based approach.Bothalgorithms can handle circuits with arbitrary but knowndelays and they produce a set of 2-vector tests.Experimentalresults demonstrating that the outcome of applyingour algorithms is a small set of patterns producinga current that is a tight lower bound on the maximuminstantaneous current are included.

To guarantee the temporal correctness of a digital circuit a set of multiple path delay faults called primitive faults need to be tested. Primitive faults can contain one or more faulty paths. Existing techniques can identify and test primitive faults containing up to two or three paths. Identifying and testing primitive faults that consist of a larger number of paths is impractical for large designs. We propose a design for testability method that assures the temporal correctness of the circuit without the need to test all primitive faults in the circuit. In the test mode, only primitive faults that contain up to two paths can affect the circuit performance. Our methodology efficiently identifies a small set of potential locations for inserting control points to eliminate primitive faults with more than two paths. Addition of a single control point can lower the cardinality of several primitive faults. Our approach re-evaluates primitive delay fault testability of the circuit after insertion of every control point. After a few iterations only primitive faults with at most two paths can exist in the circuit in the test mode. Experimental results on several circuits are included to demonstrate our method.

We propose a new method to identify and test primitive faults in combinational circuits described as multi-level or two-level netlists. A primitive fault is a multiple path delay fault for which none of the single paths contained in the fault is robustly or non-robustly testable while the presence of the fault can degrade the circuit performance. Identification and testing of primitive faults is important for at least two reasons: (1) a large percentage of paths in production circuits remain untestable under the single-path delay fault model, (2) distributed manufacturing defects usually adversely affect more than one path and these defects can be detected only by analyzing multiple affected paths. The single-path delay faults contained in a primitive fault have to merge at some gate(s). Our methodology for identifying primitive faults can quickly (1) rule out a large number of gates as possible merging points for primitive faults, and (2) prune the combination of paths that can never belong long any primitive fault. Our identification procedure also finds a test for the fault. We present a complete algorithm for identifying and testing double path delay faults. This procedure can be extended to identify primitive faults consisting of three or more paths. Experimental results on several multi-level combinational benchmark circuits are included to demonstrate the usefulness of our technique.

In many designs a large portion of path delay faults is not robustly testable. In this paper, we investigate testing strategies for robustly untestable faults. We show that the quality of nonrobust tests may be very poor in detecting small defects caused by manufacturing process variation. We demonstrate that better quality nonrobust tests can be obtained by including timing information into the process of test generation. A good nonrobust test can tolerate larger timing variations on the off-inputs. We also show that not all nonrobustly untestable path delay faults may be ignored in high quality delay testing. Functional sensitizable paths are nonrobustly untestable but, under some faulty conditions, may degrade the performance of the circuit. However, up till now, there was no strategy for generating tests for such faults. In this paper, we present algorithms for generating high quality nonrobust and functional sensitizable tests. We also devise an algorithm for generating tests for validatable nonrobust faults which have a high quality in detecting defects but are hard to be generated automatically. Our experimental results show that the quality of delay testing increases if validatable and high quality nonrobust tests, as well as tests for functional sensitizable path delay faults are included.

Some previously published results show that in a number of combinational circuits a significant portion of long paths is neither robustly nor non-robustly testable. However, not all of those untestable paths may be ignored in delay testing. Functional sensitizable paths are robust and non-robust untestable but, under some faulty conditions, may degrade the performance of the circuit. Even though the need for testing functional sensitizable paths was recognized in previous research, up till now, there was no strategy for generating tests for them. In this paper we present an algorithm for generating high quality tests for functional sensitizable paths based on including the timing information into the process of test derivation. Our experimental results prove that the quality of delay testing increases if additional test vectors for functional sensitizable path delay faults are included.