Aymen Also

Signal Integrity-Aware Pattern Generation for Delay Testing

Advancing nanometer technology scaling enables higher integration on a single chip with minimal feature size. As a consequence, the effects of signal and power integrity issues such as crosstalk noise between interconnects, power supply noise and ground bounce in the supply networks significantly increases. Also, reliability issues are eventually introduced by variations in the manufacturing process. These issues will negatively impact the timing characteristics in an integrated circuit (IC), as they give rise to delay defects.

Delay-related parametric failures increase the defect escape rate, yield loss and diminish reliability rate. Hence, design-for-test techniques are employed to have a better controllability and observability on the internal nodes to easily detect and locate the faults. However, they are not always detected by the traditional fault models.

In our work, we target these challenges and propose novel physical design-aware path delay test methods to deal with delay faults coming from manufacturing defects or physical design issues. They include the investigation of path delay variations in the presence of crosstalk noise, power supply noise, ground bounce and process variations. Based on this, we develop technology independent test methods for identifying the test patterns that may cause a worst-case delay on a target path. Then, we develop a dedicated test pattern generation method for path delay testing in the presence of crosstalk noise, power supply noise and ground noise. The proposed methods can be used to characterize the path speed and it helps to address the speed binning problem. Also, they can be employed in improving the classical ATPG approach of pattern generation. The application of these contributions can bring tremendous improvements to the IC test quality by ensuring better defect coverage and for an increased manufacturing yield during speed binning of IC chips.

Introduction xii

List of Figures

List of Tables

Introduction

As predicted by "Moore's law" [START_REF] Moore | Cramming More Components onto Integrated Circuits[END_REF], the integrated circuit (IC) products became denser with increased functionality and aggressive CMOS device scaling. Subsequently, with the arrival of "More Moore" scaling, geometrical shrinking of physical feature size were attained. Currently, "beyond CMOS" technologies are under development to satisfy the competitive consumer market demands. The entire device scaling evolutionary process has driven huge changes in our everyday life. Obvious applications are in medical field, aerospace, consumer products etc., and researches are still ongoing to make it more and more compact. International Technology Roadmap for Semiconductors (ITRS) has predicted that the growth of CMOS device scaling would slowdown and the progress would reach saturation. In the coming years, a functional diversification approach "More-than-Moore" is expected to flourish [START_REF]More-than-Moore, white paper, International Technology Roadmap for Semiconductors (ITRS)[END_REF] with higher efficiency, additional functionality and increased complexity. Well, whatever the technology advancements, the plethora of physical design issues in IC's and manufacturing process imperfectness associated with the current and upcoming technologies is still not resolved. Accordingly, it is important to develop test techniques that can increase the manufacturing yield, along with any progressing technology scaling.

The denser, complex and fast switching circuits impose significant challenges to IC's, even though the remarkable scaling has assisted technology demands very well. They pose challenges to the signal, power and thermal integrity of circuits, as well as, reliability issues. Examples are crosstalk-induced delay, logic errors and substrate coupling. Excessive and varying voltage drop in the power supply and ground networks considerably affect the power integrity of a design. Also, variations in the IC manufacturing process, commonly called as process variations affect the reliability of the circuits. All of their impacts can give rise to distributed delay variations that may affect the functioning and performance of IC's. A new class of "delay" faults caused by the above mentioned delay variations needs to be properly addressed, modelled and used during fault simulation, test xii generation, DFT, DFM and DFY. "What is not testable is not fixable" [START_REF] Moretti | What Is Not Testable Is Not Fixable[END_REF].

An IC must be testable, not only manufacturable. Also, must reach a good yield figure, which makes it cost-effective. Along with the IC designs, DFT techniques were implemented to apply manufacturing tests. Different tests has been widely adopted in industry to detect delay-related defects. Performing at-speed delay test using path delay fault (PDF) model validates that all the delay defects are captured during IC testing phase. But some of the path delay faults escape the test due to the ineffectiveness in the applied test vectors. Path delay estimations must involve the gate models and the interconnect models for an accurate estimation. The PDF models used are based on the basic simplistic models at the gate level and they do not consider circuit physical design data (package, power/ground network parasitics, pad/pin location and cell placements).

Therefore, PDF models generate ineffective vector pairs. They can only be fixed by testing the IC with the PDF models generated at physical design level rather than at gate level.

The problem of testing IC in the presence of various issues at physical design level is also of major concern, as their occurence is not consistent. Path delay fault testing in the presence of crosstalk noise, power supply noise, ground bounce and process variations is examined in this work in accordance with their impact to a circuit path. Other research works in this field were dedicated towards their individual impacts and the ways to mitigate these effects; their combined physical design impacts were not considered. This work focusses on modifying the selection of patterns generated by the testing tools to accommodate the exact patterns that are identified for causing path delay variations in the circuit.

The overall outline of the thesis "Signal Integrity-Aware Pattern Generation for Delay Testing" is shown in Figure 1. This research work includes an introduction, four chapters and finally conclusion and perspective are discussed. The brief description of the thesis chapters are as follows.

Chapter 1 ellaborates the state-of-the-art related to this thesis work. The first part in this chapter discusses, the problems assoiciated with device scaling, i.e., signal integrity issues such as crosstalk noise, power integrity issues such as supply noise and reliability issues such as process variations. In the second part, delay testing principle, types of delay testing, ATPG and DFT are detailed. And, the final part provides an overview of the prior work to the existing solutions for physical design issues and pattern generation. Chapter 2 presents our study on path delay variations in the presence of physical design issues such as crosstalk noise, power supply noise and ground bounce. The aim is to identify a worst-case path delay pattern that can predetermine delay defects. Then, we show that a path delay fault pattern generated by an ATPG tool does not match the pattern identified, hence indicating a discrepancy in the existing PDF model to detect delay defects. A physical design aware pattern generation method based on selective SPICE simulations is proposed to automate the different steps in pattern generation. Our major contributions in this method are the identification of aggressor nets and X-filling by backtrace approach. Our method is verified and results on ITC'99 benchmark circuits are provided.

Chapter 3 focuses on generating a worst-case path delay pattern in the presence of xiv crosstalk noise. Our objective in this chapter is to eliminate the selective SPICE simulation, which is exhaustive for bigger circuits. The basic findings from chapter 2 is utilized in the constrained ATPG method. This method is capable of modifying the selection of patterns generated by testing tools to accommodate the exact patterns that are identified as causing path delay variations in the physical design of a circuit layout. The proposed method is able to generate a worst-case path delay pattern in lesser computational time.

The results are verified on ITC'99 benchmark circuits.

Chapter 4 deals with path delay variations in the combined presence of process variations and supply noise in circuits. By using our proposed metric for probabilistic pattern ranking method, we are able to identify the patterns that can capture the worst-case path delay in their combined presence. This metric aims at detecting the most-effective pattern for path delay testing from the subset of all input patterns. An input pattern ranking method is described based on the mean delay difference and the area of the delay probability distribution for all input patterns. With continually shrinking nanoscale technologies, the increase in manufacturing defects causes difficulties in developing a reliable semiconductor device. Usually, these devices are expected to meet the target specification for a wide range of operating conditions for different on-chip activity levels, voltage distributions in the power supply and ground networks, parametric variations etc. But with critical transistor sizes approaching only tens of atoms and the process engineers can no longer control the manufacturing processes as accurate as needed, the conventional large design margin allocation method to mitigate the impact of faults and variations hit the diminishing rate of returns. Furthermore, the rapid shrinking of the area-performance-power budget along with the increase in process induced variations and time-dependent transistor parameters shift makes this design approach not anymore applicable [START_REF] Alam | Reliability-and Process-variation aware design of integrated circuits -A broader perspective[END_REF].

In sub-45nm technology nodes, there is always a change in the nature of different physical design effects and reliability effects causing abrupt functional problems to a progressive degradation of the performance characteristics of devices and system components.

There is also an increase in the occurrence of both permanent and transient faults, as well as, timing errors due to spatial, temporal and dynamic variations. New failure mechanisms that are not covered by current fault models are observed in designs fabricated in new technologies and new materials. At the same time, the power and signal integrity issues that come with scaled supply voltages and higher operating frequencies increase the number of faults that violate the pre-defined timing margin. Therefore, testing has become more and more important and challenging to verify the correctness of design and manufacturing processes [START_REF] Mohammad Tehranipoor | Introduction to hardware security and trust[END_REF]. The effective way to deal with these problems is by devising better Design-for-test (DFT) methods and capturing defects in the integrated circuits during the testing phase. This approach helps to minimize the defective parts per million (DPPM) of integrated circuit's being manufactured.

Background

Scaling of CMOS structures into the nanometer regime has posed new challenges to the physical design and reliability of circuits. The reasons for this are manifold [START_REF] Frank | Device scaling limits of Si MOSFETs and their application dependencies[END_REF], [START_REF] Hawkins | View from the bottom: nanometer technology AC parametric failures -why, where, and how to detect[END_REF], [START_REF] Wong | Emerging Nanoelectronics: Life with and after CMOS[END_REF]: (1)

Manufacturing structures much smaller than the wavelength of the light used in modern lithography is difficult and can be practically done only in certain coarse limits. (2) As going closer to the dimensions of atoms, the actual location of doping atoms has an effect on the properties of transistors. (3) the structures are closer to each other, resulting in even smaller impurities or metal silvers to create shorts or other defects. Furthermore, the smaller proximity of a circuit structure to another makes the noise environment worse.

(4) As the number of transistors, wires, contacts and vias on a single chip increase, the probability of one or more of being faulty increases.

It is evident that many of these new problems are not visible at the design phase, and thus, cannot be handled by discarding faulty chips after manufacturing and testing them.

Since the faults can become visible only at runtime, so they have to be tested with patterns that can detect the faults at runtime. Signal integrity issues such as crosstalk noise, power supply noise and ground bounce, as well as manufacturing process defects due to process variations cause variations in the path delay estimation. These variations are pattern dependent. Early stage prognosis of input patterns can give a better estimate of path delay in a circuit that may affect the performance. Different delay fault models that are currently employed by Automatic Test Pattern Generation (ATPG) tools for capturing the delay defects are path delay faults and transition delay fault models. Among these, the path delay fault model can be utilized for testing failures due to crosstalk noise. The impact of the physical design issue, such as crosstalk noise can cause a worst-case delay on any victim path. They give rise to delay faults. Therefore, it is essential to predetermine patterns that can capture crosstalk-related delay fault.

ATPG tools are not well versed to capture the faults or defects as they are based on simple logic models and also supply noise or manufacturing variations may take more time to capture a fault. Therefore, testing with patterns generated by the existing and commercially available ATPG tools [START_REF] Tetramax | Automatic Test Pattern Generation[END_REF] may create low-quality products. This motivates us to examine the issues such as crosstalk noise, supply noise and process variations and include their impact during pattern generation in the existing ATPG methods. These methods can be also used for increasing the manufacturing yield and reduce the rate of returns.

Chips that have faults can still be used; at least in some low-reliability applications.

Challenges in Nanoscale Technologies

Crosstalk

Crosstalk is a disturbance in a signal interconnect (i.e., victim net, a signal propagation net of interest) induced by a sudden change in voltage by an aggressor interconnect (i.e., the neighboring nets). It has a direct impact on the signal traveling through the interconnects in the chip. Crosstalk continues to be a major design issue due to interconnects becoming taller, narrower, and more closely spaced with each new technology node. As a result, the interconnect sidewalls become prime locations for coupling while the parasitic load capacitance of the interconnect itself becomes smaller, allowing the coupling capacitance to become more dominant. This has also been a major concern in design verification and timing analysis for many years [START_REF] Chen | Towards true crosstalk noise analysis[END_REF] [12] [START_REF] Agarwal | Modeling and analysis of crosstalk noise in coupled RLC interconnects[END_REF].

During a test, the ATPG tool does not consider which nets are causing it to switch simultaneously. As a result, it is possible to fortuitously exercise some aggressors to increase the amount of crosstalk and push the victim path closer to the timing closure limits calculated during verification. At the same time, it is also possible that the tool will not generate any aggressor switching and the victim path will not be anywhere close to those timing limits. As a result, if a timing related fault were to fall on that path, it is possible the latter case could occur and the fault would go undetected, potentially resulting in higher DPPM.

Several techniques have been proposed to deal with crosstalk issues during verification and test. Crosstalk verification with interconnect process variation is discussed in [START_REF] Nagaraj | Crosstalk noise verification in digital designs with interconnect process variations[END_REF].

The authors in [START_REF] Cuviello | Fault Modeling and Simulation for Crosstalk in System-on-Chip Interconnects[END_REF] present fault modeling called maximum aggressor (MA) and simulation for crosstalk on SOC interconnects. Other techniques have focused on similar approaches to maximize crosstalk [START_REF] Aniket | A novel algorithm for testing crosstalk induced delay faults in vlsi circuits[END_REF] [17] [START_REF] Chun | ATPG-XP: Test Generation for Maximal Crosstalk-Induced Faults[END_REF]. Further investigations have shown that the MA model may not always ensure highest crosstalk effects [START_REF] Tehranipour | Multiple transition model and enhanced boundary scan architecture to test interconnects for signal integrity[END_REF] especially when mutual inductance effects are considered in addition to the timing of transitions. Additionally, many of these approaches require new ATPG algorithms, hindering easy adoption in the industry.

Some researchers have proposed using on-chip sensors or glitch/delay detectors [START_REF] Yang | Improving bus test via iddt and boundary scan[END_REF] to detect noise and delay violations. The drawback of such techniques is that the sensors must be tuned and very accurate and adding one sensor per interconnect is prohibitively expensive. Due to their high sensitivity to voltage and timing, process variation can also negatively impact their operation. The authors in [START_REF] Tehranipour | Testing soc interconnects for signal integrity using boundary scan[END_REF] utilize the boundary scan cells to generate test patterns to detect noise and delay violations on a system chip and observe the responses which are then scanned out using boundary scan shift procedure. Most of the proposed techniques, mentioned above, target only buses or interconnects between cores in a SOC rather than internal paths. Authors in [START_REF] Sinha | Validation and test issues related to noise induced by parasitic inductances of vlsi interconnects[END_REF] propose validation and test generation for crosstalk-induced delay and noise for SOC interconnects. An analytical model for crosstalk was developed in [START_REF] Chen | Test generation in vlsi circuits for crosstalk noise[END_REF] and used as a basis for pattern generation to induce delay due to crosstalk in [START_REF] Chen | Test generation for crosstalk-induced delay in integrated circuits[END_REF]. However, this approach only generates patterns for a single aggressor affecting a target path. The procedure proposed in [START_REF] Krstic | Delay testing considering crosstalk-induced effects[END_REF] considers a genetic algorithm based approach when inducing crosstalk into delay test patterns. There have also been proposed academic ATPGs that considers crosstalk and transition arrival times during pattern generation [START_REF] Chen | Test generation for crosstalk-induced delay in integrated circuits[END_REF] [22] but it lacks the immediate use in practice since they are computationally intensive and would require a significant change to modern ATPG algorithms and models.

We have also summarized below the existing techniques and approaches that were proposed to deal with the different aspects of crosstalk noise in the recent years.

• Accurate crosstalk noise models [START_REF] Chen | Test generation in VLSI circuits for crosstalk noise[END_REF] [11] [START_REF] Cuviello | Fault Modeling and Simulation for Crosstalk in System-on-Chip Interconnects[END_REF] [27] [START_REF] Ding | Accurate crosstalk noise modeling for early signal integrity analysis[END_REF] [13] [START_REF] Kaushik | An Analytical Approach to Dynamic Crosstalk in Coupled Interconnects[END_REF];

• Timing analysis in presence of crosstalk noise [29] [15] ;

• Test generation to maximize crosstalk noise [START_REF] Chen | Analytic models for crosstalk delay and pulse analysis under non-ideal inputs[END_REF] • Timing defect diagnosis in presence of crosstalk [START_REF] Mehta | Timing defect diagnosis in presence of crosstalk for nanometer technology[END_REF].

Power Supply Noise

While Crosstalk directly impacts the signal paths, Power supply noise (PSN) indirectly impacts the data traveling through the signal paths by affecting the transistor drive currents. PSN is a disturbance in the power distribution network that can momentarily change the voltage difference between the power and ground rails of the functional logic.

Power distribution network design has become a significant obstacle as process nodes become smaller and smaller [START_REF] Zhu | Power distribution network design for vlsi[END_REF]. Noise on the power supply can come from four potential sources: IR-drop, L di/dt noise, LC resonance, and electromigration [START_REF] Lin | Challenges in power-ground integrity[END_REF]. Just from a first-order perspective (IR), as each new process node pushes wire widths smaller, the resistance of these wires becomes greater and as functional density increases, current demand increases. Incorrect design of the network can cause supply starvation to a portion of the chip and it will never work on actual silicon.

The power distribution network is usually very customized for the design based on functional power needs [START_REF] Chen | Power supply noise analysis methodology for deep-submicron vlsi chip design[END_REF] [39] and the type of chip packaging [START_REF] Zheng | Electrical modeling of integrated-package power and ground distributions[END_REF]. The functional power is typically estimated early in the design process based on both static and dynamic IR-drop needs. The static power is now dominated by transistor leakage due to the low voltage thresholds used by modern process nodes. The dynamic power is based on the expected average transient current over a period of time (usually the clock period). While this can range from 10%-20% for many designs, the switching activity can be much higher when the design is dominated by buses, but this can often be the exception rather than the rule.

Test power, in the meantime, can cause much greater switching activity than the 10%-20% range [START_REF] Saxena | A case study of ir-drop in structured at-speed testing[END_REF]. As a result, the IR-drop experienced during the test can be much greater since the power distribution network was not designed to handle such current demands. This is due to the ability to scan in any state into the design using the scan chains.

There is an extensive list of literature on the topic power supply noise related to test [START_REF] Girard | Survey of low-power testing of vlsi circuits[END_REF]. In [START_REF] Wen | On low-capture-power test generation for scan testing[END_REF], the authors propose a low-capture-power (LCP) X-filling method for assigning 0's and l's to the X-bits in a test cube so that the number of transitions at the outputs of scan flip-flops in capture mode for the resulting fully-specified test vector is reduced. The authors in [START_REF] Wen | A new atpg method for efficient capture power reduction during scan testing[END_REF] propose another method, called capture-aware (CA) test cube generation, for deterministically generating test cubes not only for fault detection but also for capture power reduction. The preferred fill technique proposed in [START_REF] Remersaro | Preferred fill: A scalable method to reduce capture power for scan based designs[END_REF] attempts to reduce the Hamming distance between the initialized, launched, and captured patterns during TDF testing. In [START_REF] Krstic | Pattern generation for delay testing and dynamic timing analysis considering power-supply noise effects[END_REF], a pattern generation technique was proposed to create maximum supply noise to increase the delay along targeted paths. Neural network and genetic algorithm based solutions were proposed in [START_REF] Liau | Automatic worst case pattern generation using neural networks genetic algorithm for estimation of switching noise on power supply lines in cmos circuits[END_REF]. Also, a method of measuring average power called switching cycle average power (SCAP) was used to produce supply noise tolerant patterns [START_REF] Ahmed | Supply voltage noise aware atpg for transition delay faults[END_REF]. SCAP considers both simultaneous switching and which of the long paths in the design are affected. The method requires pattern delay information which may make it computationally intensive. There have also been more

precise techniques that perform RLC analysis for pattern generation [START_REF] Tirumurti | A modeling approach for addressing power supply switching noise related failures of integrated circuits[END_REF]. However, the extensive analysis required can become time-consuming as these networks become more complicated in modern designs. Vector-based compaction solutions to reduce overkill and power supply noise induced delay have been proposed in [START_REF] Wang | A vector-based approach for power supply noise analysis in test compaction[END_REF]. The authors developed a vector-dependent power supply noise analysis solution that models the voltage drop based on the layout of the chip. However, simulation of each compacted pattern to estimate IR-drop can result in significant run times. Also, their proposed approach does not consider areas of the chip that may be underutilized. There has also been a pattern post-processing technique to verify whether patterns generated will cause an excessive IR-drop [START_REF] Kokrady | Static verification of test vectors for ir drop failure[END_REF]. Again, these approaches attempt to mitigate overkill rather than focus on underkill. Methods to modify conventional ATPG algorithms have also been proposed [START_REF] Polian | Power droop testing[END_REF].

While most approaches to reduce power during test involve manipulation the test pat-terns, there have also been proposed some approaches that involve integrating additional circuitry or logic to control which scan chains can be enabled or portions of functional logic can capture [53]. While effective since it disables whole sections of the design, the amount of additional logic is not considered trivial. • Supply-noise aware delay test pattern generation [START_REF] Lee | Layout-aware, ir-drop tolerant transition fault pattern generation[END_REF] [58] [57] ;

• Test compaction considering IR drop [START_REF] Lee | Layout-aware, ir-drop tolerant transition fault pattern generation[END_REF] [60] ;

• Worst-case PSN analysis at core and system levels [72] [73] .

Process Variations

Besides crosstalk and supply noise, this thesis is also concerned regarding the impact of process variations on path delay of a circuit. Practically, it is difficult to achieve the fabricated transistor parameters similar to the design specification. In reality, the parameters are different from die-to-die, wafer-to-wafer, and lot-to-lot, and also between transistors on the same die. Parameter variations are caused by differences in impurity concentration densities, oxide thicknesses, diffusion depths, and similar factors. These nonuniform conditions result in deviations in transistor parameters, such as threshold voltage, W/L ratio, as well as variation in the widths of interconnect wires [START_REF] Rabaey | Digital Integrated Circuits, A Design Perspective (Second Edition)[END_REF]. The process variations are expected to impact design performance (increase or decrease gate and interconnect delays) to a large extent in newer technologies. Thus, it is necessary to take these effects into consideration along with the crosstalk noise and PSN issues during pattern generation procedures. Summary of the previous works in this area are discussed in Chapter 4.

In the next section, we will show the importance of testing a circuit design and the various existing test methods that can ensure better quality of IC's being manufactured.

Testing

The goal of manufacturing test is to detect any defect that occurs in the fabricated circuits. Ideally, we can differentiate the faulty circuits and fault-free circuits after the manufacturing test.

Different Types of Manufacturing tests

Chip vendors have a variety of different test methods at their disposal, which are often used in some combination to balance costs. It is usually left to the vendor's discretion which tests to apply and the amount of coverage they need to achieve to satisfy the customers' needs while also containing their own test costs. While there are not a set of standardized tests each vendor must follow there are still common practices amongst most vendors; allowing customers to switch to a different vendor without risking a need to make a dramatic change in the way quality of the shipped parts is measured.

• Parametric Testing

Parametric testing is typically used to check the electrical properties of the device and can be used to characterize any potential systematic issues with the process node. These tests may not check any functionality of the device but can find gross shorts, opens, leakage issues, or current drive problems.

Often specialized circuitry is added for the purpose of parametric testing. Adding ring oscillators to both the wafer scribe lines and to the die itself is a common practice to perform propagation delay tests, setup and hold tests, and speed testing. The most common technique is to employ an on-die chip measurement circuitry to monitor supply droop and adaptively scale it depending on its usage. It is possible to leverage the use of these measurement circuits during parametric testing to get a more granular reading than what can be achieved with the ATE alone.

• Functional Testing

While most often used for design verification, functional testing can also be used for manufacturing test. It is considered very time-consuming and very expensive due to the exhaustive nature of applying test patterns to cover each known reachable functional state.

Expert design knowledge is usually required and little in the way of design automation tools can be used to assist in the effort. Usually, an ad-hoc approach is required for each design, so unless the next design architecture is based very heavily on the previous design, it will not be possible to reuse the assets from the previous design.

• Structural Testing

Structural testing, which will be the backbone of this presented thesis work, allows state observation of circuit behavior from relatively few observation points [START_REF] Frank | Device scaling limits of Si MOSFETs and their application dependencies[END_REF]. Unlike functional testing, it does not require enumeration of all functional states to test the design, so test volumes are not as large. Additionally, structural tests do not require the same expert design-specific knowledge as functional testing and algorithms can be utilized to create automatic test pattern generation (ATPG) tools that can be leveraged to create the patterns. So, even if there is a little design re-use from one design to the next, there can still be a re-use of the same automation tools, which significantly reduces the cost of test. Due to the lower test volumes and tool reuse, structural testing has seen widespread adoption across the semiconductor industry. A closer look at how structural testing is used to find defective chips is detailed in the next section.

Structural Fault models

There are three terms that are usually used to describe the incorrectness of an electronic system.

• Defect

A defect in an electronic system is the unintended difference between the implemented hardware and its intended design. Typical defects in VLSI chips are: process defects, material defects, aging defects and package defects.

• Error

A wrong output signal produced by a defective system is called an error. An error is an effect whose cause is some "defect".

• Fault

A representation of a "defect" at the abstract functional level is called a fault.

A fault model is a mathematical description of how a defect alters the design behavior.

A fault is said to be detected by a test pattern if, when applying the pattern to the design, any logic value observed in one or more of the circuit's primary output's differs between the original design and the design with the fault. There are a lot of fault models developed to describe different kinds of physical defects. The most common fault modes for modern VLSI test includes: stuck-at fault, bridging fault, delay faults (transition delay fault and path delay fault), stuck-open and stuck-short faults, etc.

• Stuck-at faults A signal, which is an input or an output of a logic gate or flip-flop is stuck at a 0 or 1 value, independent of the inputs to the circuit. The single stuck-at fault is widely used, i.e. two faults per line, stuck-at-1 (sa1) and stuck-at-0 (sa0).

• Bridging faults

Two signals are connected together when they should not be. Depending on the logic circuitry employed, this may result in a wired-OR or wired-AND logic function. Since there are O(n2) potential bridging faults, they are normally restricted to signals that are physically adjacent in the design.

• Delay faults

These faults make the signals to propagate slower than normal, and cause the combinational delay of a circuit to exceed clock period. Specific delay faults are: transition delay faults(TDF), path delay faults (PDF), gate delay faults, line delay faults, segment delay faults. Among them, slow-to-rise and slow-to-fall PDF and TDF are the most commonly used ones. Path delay fault model targets the cumulative delay through the entire list of gates in a path while the transition fault model targets each gate output in the design. way as detecting a stuck-at fault at the output fault on the gate's output pin. The effect of stuck-short fault is that the short connects power line and the ground line. So quiescent current (IDDQ) measurement can be used to detect such fault.

Fault Categories

An ATPG tool maintains a list of potential faults in the design and assigns each such fault to a fault class according to its detectability status. Faults classes are organized into categories.

There are 5 higher-level fault categories containing a total of 17 lower-level fault classes:

Detected Faults

The DT (detected) category of faults includes four classes:

• DR (detected robustly)

The faults that are determined during Path Delay ATPG or fault simulation. During ATPG, at least one pattern that caused the fault to be placed in this class is retained.

• DS (detected by simulation)

The faults that are determined by generating patterns and simulating to verify that the patterns result in the faults being detected.

• DI (detected by implication)

The faults that do not have to be detected by specific patterns, because these faults result from shifting scan chains. The faults in the DI class usually occur along the scan chain paths and include clock pins and scan-data inputs and outputs of the scan cells.

• D2

The faults that are clock faults detected when the loadable non-scan cell faulty value is set to both 0 and 1. Note that the loadable non-scan cells feature must be active.

Possibly Detected Faults

The PT (possibly detected) category of faults contains the following four classes:

• AP (ATPG possibly detected)

This class contains faults for which the difference between the good machine and the faulty machine results in a simulated output of X rather than 1 or 0. Analysis proved that the fault cannot be definitely detected under current ATPG conditions, only possibly detected.

• NP (not analyzed-possibly detected)

This class also contains faults for which the difference between the good machine and the faulty machine results in a simulated output of X rather than 1 or 0. However, the analysis to prove that the fault cannot be definitely detected using current ATPG conditions was not conclusive. Like the AP class, the simulation cannot tell the expected output of the faulty machine.

• P0

This class contains clock faults when the loadable non-scan cell faulty value is set to 0.

Note that the loadable non-scan cells feature must be active.

• P1

This class contains clock faults when the loadable non-scan cell faulty value is set to 1.

Note that the loadable non-scan cells feature must be active.

Undetectable Faults

The UD (undetectable)] category of faults contains faults that cannot be tested by any means: ATPG, functional, parametric, or otherwise. Usually, when an ATPG tool calculates test coverage, these faults are subtracted from the total faults of the design.

The UD category includes four classes:

• UU (undetectable unused)

This class contains faults located on unused outputs or, in general, outputs that have no electrical connection to any other logic. A fault located on one of these fault sites has no logic simulation effect on any other logic in the design.

• UO (undetectable unobservable)

This class is similar to the UU (Undetectable Unused) class, except that the UO fault class specifically includes faults on unused gates with fanout (i.e., gates connected to other unused gates). Faults on unused gates without fanout are identified as UU faults.

• UT (undetectable tied)

This class contains faults located on pins that are tied to a logic 0 or 1, which are usually unused inputs that have been tied off. A stuck-at-1 fault on a pin tied to a logic 1 cannot be detected and has no fault effect on the circuit. Similarly, a stuck-at-0 fault on a pin tied to a logic 0 has no effect.

• UB (undetectable blocked)

This class contains faults at locations for which controllability and observability are hindered by redundant faults. UB faults are companion faults to UR faults.

• UR (undetectable redundant)

This class contains faults for which there are redundant logic paths. A fault in one path cannot be detected because the other redundant logic path masks the fault effect. Because of the self-protecting nature of redundant logic design, a single fault cannot be detected and is indistinguishable from the good machine behavior as seen from the design outputs and scan cells.

ATPG Untestable Faults

The AU (ATPG untestable) category of faults contains faults that are not necessarily intrinsically untestable, but are untestable using ATPG methods. These faults cannot be proven to be undetectable and might be testable using other methods (for example, functional tests).

The AU category includes two classes:

• AN (ATPG untestable-not detected)

A fault cannot be controlled or observed because setting up the required patterns would violate a PI or ATPG constraint. Faults associated with non-scan sequential devices (latches and flip-flops) are not testable with simple ATPG methods.

• AX (ATPG untestable-timing exceptions)

This classification occurs under the following circumstances: For each fault affected by timing exceptions, if all the gates in both the backward and forward logic cones are part of the same timing exception simulation path, then the fault is marked AX. This analysis finds the effects of setup exceptions, so it does not impact exceptions that are applied only to hold time.

Not Detected Faults

An ATPG classifies a fault as ND (not detected) when the analysis for that fault was not completed or was aborted. Incomplete or aborted analysis could be caused by the default ATPG iteration limits or by designs that are too complex for the ATPG algorithm to solve.

The ND category has two classes:

• NC (not controlled)
This class contains faults that the ATPG algorithm could not control to achieve both a logic 0 and a logic 1 state. Nodes that are always at an X state are classified as NC because ATPG cannot achieve either a logic 0 or a logic 1.

• NO (not observed)

This class contains faults that could be controlled, but could not be propagated into a scan chain cell or to a design output for observation.

Automatic Test Pattern Generation

ATPG tools have been a great benefit to test engineers. Since they take advantage of structural fault models to generate patterns, the same tool can be used in many different designs with very different architectures. These tools are widely available to industry whether it is commercially [START_REF] Tetramax | Automatic Test Pattern Generation[END_REF] or from academia.

The goal of these tools is to deterministically generate patterns that will stimulate a fault site and propagate the potential fault effect to an observation point to identify as many faults as possible with as few patterns as possible. While not all faults will be testable due to the topology of the circuit, the ATPG will be able to generate patterns for those faults that are testable. The ability to test these fault sites is measured by the fault coverage, which is a fraction of the number of faults detected after pattern generation over the total number of faults in the design, as shown in Equation 1.1, where FC is the fault coverage percentage, DT is the total number of detected faults, and TF is the total number of faults in the design. There is additionally another metric often used by these tools called test coverage. The test coverage, as calculated in Equation 1.2 considers those faults that are not testable either due to circuit redundancies or tied off signals that would make coverage of particular fault types impossible. TC is the test coverage percentage and UT are those faults that have been classified by the ATPG as untestable.

F C = DT T F × 100 (1.1) T C = DT T F -U T × 100 (1.2)
While the fault coverage provides a metric of how much of the design has been covered with the generated pattern set, the test coverage essentially measures the effectiveness of the ATPG tool. These two values can also be used to help guide design issues since a large discrepancy between the two values could imply a potential problem in the design.

While each commercial vendor has their own proprietary algorithm for pattern and coverage optimizations, they all basically follow a similar flow as shown in Figure .1.2.

First, a fault dictionary for the design has to be built. Next, the tools begin to deterministically target these faults one at a time. While the patterns are being generated, compaction of the patterns also occurs dynamically. This is possible since very few bits of the pattern are usually needed to stimulate and observe a specific fault site. After the pattern generation and compaction have filled in some of the pattern's with care-bits, the remaining don't care bits can be filled randomly or with some other fill scheme. The final fully specified pattern is then fault simulated for any fortuitous detection of additional faults.

The ATPG algorithms inject a fault into the CUT, and then use a variety of mechanisms to activate the fault and propagate its effect to the circuit output. The output signal changes from the value expected for the fault-free circuit, and this causes the fault to be detected. There are various ATPG algorithms that can be found in the literature. Some of them are listed below:

• Roth's D-Algorithm (D-ALG) [75];
• Goel's PODEM algorithm [START_REF] Goel | An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits[END_REF];

• Fujiwara and Shimono's FAN algorithm [START_REF] Fujiwara | FAN: A Fanout-Oriented Test Pattern Generation Algorithm[END_REF];

• Kirkland and Mercer's dominator ATPG programs TOPS [START_REF] Kirkland | A Topological Search Algorithm for ATPG[END_REF];

• Schulz's learning ATPG programs SOCRATES [START_REF] Schulz | Advanced automatic test pattern generation and redundancy identification techniques[END_REF] [80][81];

• Giraldi and Bushnell´s EST methodology [START_REF] Giraldi | EST: the new frontier in automatic test-pattern generation[END_REF] [83][84];

• Kunz and Pradhan's Recursive Learning methodology [START_REF] Kunz | Recursive learning: a new implication technique for efficient solutions to CAD problems-test, verification, and optimization[END_REF] [86][87];

• Chakradhar's NNATPG algorithm family [START_REF] Chakradhar | Neural Models and Algorithms for Digital Testing[END_REF];

• BDD-Based ATPG Algorithms [89][90].

The following terms are important test generation definitions and are commonly used in ATPG literature:

• Controllability: A testability metric that measures how difficult it is to drive a node to a specific value.

• Observability: A testability metric that measures how difficult it is to propagate the value on a node to the primary output or scan flip-flop.

• Sensitization: The process of sensitizing the circuit and enable the fault to cause an actual erroneous value at the point of the fault.

• Propagation: The process of propagating error effects to the primary output or scan flip-flop.

• Justification: The process of finding the input combination required to drive an internal circuit node to a specified value.

All the above terms in this section are utilized in the coming chapters during the explanation of our methods to generate patterns.

DFT Techniques

Design-for-Testability (DFT) techniques are widely used in nowadays integrated circuits.

"DFT" is a general term applied to design methods that lead to more thorough and less costly testing. In general, DFT is achieved by employing extra hardware circuits for test purpose. The extra test circuits provide improved access to internal circuit elements.

Through these test circuits, the local internal state can be controlled and/or observed more easily. It adds more controllability and observability to the internal circuits. DFT plays an important role in the development of test programs and as an interface for a test application and diagnostics. With appropriate DFT rules implemented, many benefits ensue from designing a system so that faults are easy to detect and locate. DFT can bring the many benefits. Generally, integrating DFT in the development cycle can help:

• Improve fault coverage

• Reduce test generation time

• Potentially shorten the test length and reduce test memory

• Reduce test application time • Support hierarchical test • Reduce life-cycle costs
These benefits come at the price of extra cost from pin overhead, more area and thus low yield, performance degradation and longer design time. However, since it reduces the overall costs of the chip, DFT is a cost-effective methodology and widely used in the semiconductor industry.

Nowadays DFT techniques have become even more critical in modern designs. Without it, it is only possible to apply test patterns to the primary inputs and observe the results at the primary outputs of the design. When sequential logic is included, covering all of the faults efficiently becomes much more difficult since it will likely take multiple clock pulses to activate the fault site from the primary input and propagate the result from the fault site to the primary output.

Scan Design

Scan design has been widely adopted across the industry due to the ability to achieve The scan chain essentially grants full control and observability of all internal state logic through a single input and output port. This grants the ability to easily place the chip into any state perform a single clock, and scan out the result, turning a potentially complex design into a simple combinatorial circuit.

Different ATPG Modes

These are some of the different operational modes offered by an ATPG tool

• Basic-Scan ATPG
In Basic-Scan mode, ATPG can be operated in a full-scan, combinational only ATPG tool. To get high test coverage, the sequential elements need to be scan elements. Combinational ROM's can be used to gain coverage of circuitry in their shadows in this mode.

• Fast-Sequential ATPG Fast-Sequential ATPG provides limited support for partial-scan designs. In this mode, multiple capture procedures are allowed between scan load and scan unload, allowing data to be propagated through non-scan sequential elements in the design such as functional latches, non-scan flops, and RAM's and ROM's. However, all clock and reset signals to these non-scan elements must still be directly controllable at the primary inputs of the device.

• Full-Sequential ATPG Full-Sequential ATPG, like Fast-Sequential ATPG, supports multiple capture cycles between scan load and unload, thus increasing test coverage in partial-scan designs. Clock and reset signals to the non-scan elements do not need to be controllable at the primary inputs; and there is no specific limit on the number of capture cycles used between scan load and unload.

At-speed Test

In scan-based (as shown in Figure 1.4) at-speed test, input test patterns can be applied in two different manners: launch-off-capture (LOC), also called broadside testing [START_REF] Savir | On broad-side delay test[END_REF] and launch-off-shift (LOS) [START_REF] Savir | Skewed-load transition test: Part i, calculus[END_REF]. While both techniques rely on the scan-based testing to initialize the circuit, the two techniques differ in the manner the data is launched during the first at-speed test cycle. While LOC relies on the functional path to stimulate transitions, LOS stimulates transitions through the shift path. This difference essentially means the scan-enable signal is 0 during the launch cycle for LOC, as shown in Figure 1.5, while it is 1 during the launch cycle for LOS, as shown in Figure 1.6. There have also been other DFT techniques that attempt to combine the two techniques that attempt to use the advantages of each technique while mitigating from the disadvantages [START_REF] Wang | Hybrid delay scan: a low hardware overhead scan-based delay test technique for high fault coverage and compact test sets[END_REF]. Both LOC and LOS have advantages and disadvantages. While LOS provides higher fault coverage since there is a higher degree of control when stimulating the transition through the shift path, the scan-enable signal must be timing closed since it must be asserted during the launch cycle and deserted during the capture cycle. LOC does not have the same design constraints on scan-enable and is the easier of the two methods to implement in physical design, but does not achieve the same fault coverage since transitions must generate through functional logic and become dependent on the functional behavior of the device.

Clk SE Launch Capture Shift input A B C D E F V0 V1 V1'

At-Speed Delay Test Challenges

As circuit complexity and functional frequency increase, power integrity and timing in- This may allow some faults to go undetected. Therefore, PD issues need to be considered during the path delay fault test to reduce delay fault escape and to ensure better path delay defect coverage.

tegrity
Path delay variation usually occurs due to PD issues such as crosstalk (Xtalk) noise, Power Supply Noise (PSN), Ground Bounce (GB). Crosstalk is due to capacitive or inductive coupling between a victim interconnect (i.e., signal propagation net of interest) and an aggressor interconnect (i.e., the neighboring nets). Depending on the circuit's layout, one victim interconnect can have single or multiple aggressor interconnects. Their impact on a victim interconnects (or nets) delay varies depending on the behavior of multi-aggressors, such as their signal switching frequency, signal transitions and their arrival time. Also, their path delay estimation defers as it may expand to the entire victim path (consists of many victim nets) with distributed delay variations. Xtalk impacts may speedup or slowdown the worst-case path delay in a victim net [START_REF] Zhang | Path delay test generation toward activation of worst case coupling effects[END_REF]. Also, an opposite signal transition in the aggressor net maximizes the delay slowdown [START_REF] Peng | Crosstalk-and Process Variations-Aware High-Quality Tests for Small-Delay Defects[END_REF] of the respective victim net, when compared to the same signal transitions and stable inputs (i.e., stable 0 and stable 1). In our work, we determine all the aggressor nets from the physical design of the given circuit layout rather than from their gate level circuit netlist, as it would represent a real circuit structure that will be manufactured and tested.

Xtalk directly impacts the signal through the victim interconnect, while PSN and GB indirectly impact the signal by affecting the drive strength of gates on the signal path. Mainly, PSN and GB are due to the fast switching circuits that introduce voltage fluctuations at their supply nets. We consider the combined behavior of the PD issues, as they would occur similarly in a real circuit design. In this work, our focus is to identify a test pattern that can capture the path delay variations in the combined presence of PD issues such as multi-aggressor crosstalk, PSN and GB on a victim path. ATPG tools utilize static timing analysis (STA) inputs [START_REF]PrimeTime User Guide[END_REF] that are dependent on the lengths of a path. However, they do not consider the physical design data of a circuit (package, power/ground network parasitics, pad/pin location, cell placements, etc.) during pattern generation. So they might not identify actual test patterns that can lead to worst-case path delay in a circuit. Due to these reasons, path delay test using commercial ATPG tools needs to be reexamined for taking into account PD issues.

Prior Work

Several pattern generation techniques were proposed in the literature to consider PD issues during path delay testing. Authors in [START_REF] Krstic | Pattern generation for delay testing and dynamic timing analysis considering power-supply noise effects[END_REF] present a genetic algorithm based approach to find patterns that create maximum supply noise. Layout-aware pattern generation techniques were proposed in [START_REF] Ma | Layout-Aware Pattern Generation for Maximizing Supply Noise Effects on Critical Paths[END_REF], [START_REF] Ma | Layout-Aware Critical Path Delay Test Under Maximum Power Supply Noise Effects[END_REF] for PSN on critical (victim) paths. These approaches are better in terms of adding the PSN effects during pattern generation, but they take longer simulation time. In [START_REF] Lee | A Novel Pattern Generation Framework for Inducing Maximum Crosstalk Effects on Delay-Sensitive Paths[END_REF], a pattern generation framework by inducing maximum crosstalk effects across targeted delay-sensitive paths are proposed. A test generation technique in the presence of worst-case coupling effects for critical delay paths is presented in [START_REF] Zhang | Path delay test generation toward activation of worst case coupling effects[END_REF]. In [START_REF] Todri | Uncorrelated Power Supply Noise and Ground Bounce Consideration for Test Pattern Generation[END_REF], a pattern generation method with PSN and GB impact is shown and [START_REF] Peng | Crosstalk-and Process Variations-Aware High-Quality Tests for Small-Delay Defects[END_REF] proposes pattern evaluation and selection procedure for the impact of crosstalk and process variations. The method proposed in [START_REF] Sanyal | Test Pattern Generation for Multiple Aggressor Crosstalk Effects Considering Gate Leakage Loading in Presence of Gate Delays[END_REF] focuses on an ATPG solution for the multi-aggressor crosstalk noise and [START_REF] Zhang | Path Delay Test Generation Toward Activation of Worst Case Coupling Effects[END_REF] on finding the patterns activating worst-case crosstalk effects. All these works were based on pattern generation in the presence of the individual or partial combinations of PD issues (crosstalk, PSN or GB). The motivation behind this research work is quite different from all the previous work. Our efforts are to investigate on the combined impact of multi-aggressor crosstalk, PSN and GB on path delay variations and identify the test patterns that lead to worst-case path delay on a victim path. To do this, we develop a method for test pattern generation with physical design awareness.

Contributions and Chapter Organization

In this chapter, we propose a physical design aware pattern generation (PDAPG) method for identifying a test pattern that can capture worst-case path delay in the combined presence of PD issues.

Main contributions of this chapter are:

-To the best of our knowledge, this is the first work to investigate on the combined impact of multi-aggressor crosstalk, PSN and GB on pattern generation.

-We demonstrate, that a pattern generated by timing-aware ATPG tool does not capture the worst-case path delay.

-We present our PDAPG method to identify patterns that can capture worst-case path delay in the combined presence of PD issues.

-To identify a high-quality test pattern during path delay testing.

The chapter is organized as follows. In Section 2.4, we describe our motivational experiments which indicate the significance of path delay testing in the combined presence of Xtalk, PSN and GB. Section 2.5 presents the detailed flow of PDAPG method and the simulation results obtained on ITC'99 benchmark circuits. In Section 2.6, we summarize this chapter.

Motivational Experiments

The main motivation behind this chapter is presented in this section. The combined impact of PD issues such as multi-aggressor Xtalk, PSN and GB may cause worst-case delay on a circuit path. We highlight their impact based on the SPICE level simulations performed on a buffer gate circuit, shown in Figure 2.1. Simultaneously, we utilize an ATPG tool that is industrially used for testing path delay faults. ATPG tools function on the klogical level description of the circuit (i.e., VHDL or Verilog description), so they lack the physical design information while generating patterns. The worst-case delay test patterns identified from SPICE simulations are then compared with the patterns generated by the ATPG tool and their discrepancies were reported. Gnd4}, respectively. The nominal power supply voltage, the ground reference voltage and switching frequency of 1V, 0V and 1GHz, respectively are used in this experiment.

Path Delay Analysis

Path delay variations are observed at the target output {Op1} with trigger input at {Ip1} for all the possible input signal transition patterns such as {10 10}, {10 01}, {01 10} and {01 01}} at {Ip1 Ip2}. The stable input patterns {00 00}, {00 01}, etc.

were not considered here as there is no voltage level transition between the input and the output signals of this circuit. Please note that vector pair (01) represents a rising signal transition, (10) represents a falling signal transition, (00) represents a stable 0 condition and (11) represents a stable 1 condition. We not only varied the input patterns, our tests were also performed for varying input signal arrival time at their inputs. The different arrival times given at the primary input {Ip2} were {-200ps 0ps +200ps}. The +/-indicates the advance and the lag in arrival times at {Ip2} with respect to {Ip1}.

We have assumed ±10% tolerance [START_REF] Qi | Simulation and analysis of inductive impact on VLSI interconnects in the presence of process variations[END_REF] in all these experiments as this can practically represent the supply voltage constraints in the distributed power and ground network grids. For analyzing PSN, gate supply voltages are varied by ±10% with respect to the nominal supply voltage of 1V i.e, {0.9V 1V 1.1V}. Similarly for GB, {0V 0.1V} are taken for ground voltage levels. A total crosstalk capacitance of {2fF} is assumed for {Cx1 Cx2

Cx3 Cx4} with a load capacitance of {10fF} at the output of Gate2 and Gate4 (derived from PTM interconnect model). Path delay variations were represented with respect to the nominal path delay with Xtalk noise on the circuit path. Positive and negative values on the z axis denote the speedup and slowdown impact on the victim path. We also note that for some of the input patterns, path delay is larger than others. This clearly indicates the input pattern to be used for obtaining a worst-case path delay. This delay plot becomes much more complex with many corners for bigger circuits.

In Table 2.1, we list the path delay variations for different input patterns with respect to their arrival times. Their impact on the victim path is also mentioned, i.e. slowdown or speedup impact. In this experiment, input pattern {01,10} leads to the worst-case path delay of up to -7.6%. We can make two major observations from this experiment. 1)

Depending on the crosstalk noise conditions and arrival time, path delay on a victim path [START_REF] Todri | A study of path delay variations in the presence of uncorrelated power and ground supply noise[END_REF]. We can conclude two more new observations from this experiment. 1) Path delay variation has increased to -26% compared to nominal delay (i.e., with no PSN and Xtalk) with the addition of a PD issue to the first case.

2) The combined minimal margin between the voltage drop in each gate does not lead to their worst-case path delay. They are due to the varying drive strength of the gates in the preceding stages before the path delay is measured.

In the third case, we perform path delay analysis in the combined presence of Xtalk, PSN and GB. The same circuit is utilized for this experiment also. From the simulation results, the same amount of worst-case delay is observed for 6 different cases. In Table 2.4, worst-case delays for input pattern {01 10}, all arriving at the same time {0ps} and for different conditions of PSN and GB are shown. This is due to non-uniform voltage distribution among gates that impacts their drive strengths in the succeeding stages [START_REF] Todri | Uncorrelated Power Supply Noise and Ground Bounce Consideration for Test Pattern Generation[END_REF]. Additionally, we obtain up to -47% of path delay increase with respect to the nominal delay (i.e., with no Xtalk, PSN and GB) in the combined presence of Xtalk, PSN and GB. The individual and the collective impact of PD issues demonstrated earlier are collec-tively shown in Figure 2.5. In the first case, the stand-alone impact of crosstalk effects is analyzed. In the second case, PSN is injected to the previous case. And in the final case, the GB is added along with the previous two cases. For each input pattern, the minimum to maximum path delay variations when compared with the nominal delay for the three different cases are indicated. The slowdown or speedup impact is also shown here. From the graph, we obtain a worst-case path delay of -47.62% for the input pattern {01 10}, at same input arrival time {0ps}, a Xtalk capacitance of {2fF}, for different values of PSN and GB. This is due to the Xtalk capacitance and the voltage level difference at each gate (i.e., PSN and GB) affecting the drive strength of the gates in their succeeding stages [START_REF] Todri | A study of path delay variations in the presence of uncorrelated power and ground supply noise[END_REF].

Path Delay Fault Testing

For path delay fault testing, we developed a combinational circuit module in Verilog similar to the buffer gate circuit in

Comparison of input patterns

In Table 2.5, we show the ATPG tool generated input pattern (ATPG pattern) and the input pattern identified from our SPICE simulations (SPICE pattern). The ATPG pattern clearly does not match with the SPICE pattern selected from our detailed timing analysis with SPICE simulation. This is due to the addition of the PD issues such as crosstalk, PSN and GB. The worst-case path delay obtained using SPICE pattern is +47.62% larger than the one obtained using an ATPG pattern (with no Xtalk, PSN and GB). This shows that the path delay testing may miss the worst-case delay due to the low quality of the applied test set. The path delay variation in the presence of PD issues is quite high, thus indicating the need for refinement and the requirement of novel techniques to capture the worst-case path delay pattern.

In the next section, we propose a method to generate input test patterns to capture worst-case path delay under the combined impact of multi-aggressor crosstalk, PSN and GB.

Physical Design Aware Pattern Generation Method

PDAPG Flow for Pattern Generation

We propose a Physical Design Aware Pattern Generation (PDAPG) method to generate test patterns (vector pairs) that can capture worst-case path delay under the combined impact of multi-aggressor crosstalk noise, power supply noise and ground bounce. This method describes our complete flow from circuit netlist creation to a physical design aware pattern generation. Accordingly, this pattern can be utilized to test the presence of crosstalk noise, PSN and GB on a victim path. The PDAPG method is applied on ITC'99 benchmark circuits [1], to obtain a physical design aware pattern sequence. This method can be exhaustive for larger circuits in terms of computational time. Improvement and refinement of this method are explained in section 2.6. However, the validity and relevance Faults are assigned to classes indicating their current fault detection or detectability status. Our objective from this algorithm is to select a strong robust, detected fault class, to ensure a signal transition in an at-speed test (as explained in section 1.3.3.1).

Stage III : Placement and Routing of Circuit Netlist

Developing layout of a circuit aids to infer the crosstalk induced noise issues from the perspective of a manufactured IC. We use the industrial CAD tool (Cadence SOC Encounter) for placement and routing of the circuit netlist [108] to integrate a layout-aware path delay test solution. The step by step procedure in this stage is as follows. Initially, design import of our initial verilog circuit netlist is performed, then included design rules, technology details and standard cell abstract information (Library exchange format); followed by floor planning, power planning (power supply network and ground network), standard cell placement (comprising of functional gates and scan flip-flops), power routing and finally signal routing. Parasitic parameters, i.e., resistances in the interconnecting nets and ground coupling capacitances between two standard cells were extracted in this stage.

The codes for the placement and routing of circuit netlist are mentioned in Appendix A.

Stage IV : Pattern Generation

Synopsys ATPG tool, TetraMAX ® [10] is employed to perform path delay fault test on the selected victim path from Stage II. This test ensures that a fault is detected in the path irrespective of other faults that may affect the circuit. As the outcome of this test, the tool generates a random pattern (without any X-bit) and an X-bit pattern that are capable of propagating a signal transition in the victim path. Random patterns are generated by the ATPG tool by randomly filling the X-bits in a pattern based on the built-in algorithms (extended D-Algorithm). X-bits are the don't care bits in the patterns. The care bits generated by the tool are not modified. X-bit patterns are also generated by the tool, left to be filled in any manner based on any heuristic or augmented algorithms. We take forward this X-bit pattern to stage VI, for our selective X-bit filling to identify a physical design aware pattern. The codes for pattern generation of the selected victim path can be referred to Appendix A.

We employ Full-sequential mode ATPG algorithm for executing the PDF tests (as explained in section 1.4.2.3). ATPG tool TetraMAX ® uses only deterministic pattern generation. During deterministic pattern generation, the tool uses a pattern generation process based on path-sensitivity concepts to generate a test vector that detects a specific fault in the design. After generating a vector, the tool fault-simulates the vector to determine the complete set of faults detected by the vector. Test pattern generation continues until all faults either have been detected or have been identified as undetectable by the process [START_REF] Tetramax | Automatic Test Pattern Generation[END_REF]. The different steps in the identification procedure for selecting a victim net is briefly shown in Algorithm2, below. Initially, a single victim net is selected. Then, checked whether the net is horizontally or vertically located in the X-Y plane of the circuit's layout. After knowing its location, it is checked for the placement in the metal layer, i.e., metal1 the permittivity of dielectric material between two nets. These multi-aggressor crosstalk capacitances were added to the SPICE netlist in the last stage of path delay measurement.

Stage VI : X-bit Filling by Backtrace Approach

We utilize the X-bit pattern generated in stage IV for our selective X-bit filling based on backtrace approach. After identifying all the multi-aggressors from the circuit layout, we then employ to trace back to the origin of their X-bit inputs that control each of the aggressor nets, as depicted in Figure 2.12. Some of the backtraced aggressor net gate input can be an aggressor net itself (for example An2 and An3), the subset of all these inputs are considered. There might be a huge number of unfilled X-bits and filled bits in the primary input (PI) and the scan flip-flop input (SI) of the patterns generated by the ATPG. Our approach is to identify and fill the relevant X-bits that is getting

An1

An2 An4

An3

An5

Combinational logic

Primary and Scan FF outputs

FF1 FF2 PI1 FF6 FF9 FF4 FF3 PI3 FF7 PI2 FF5 FF8 X 0 X 1 X 1 X X 0 0 X 1 X 0 X 1 X 1 X X 0 0 X 1 Figure 2
.12: X-filling by backtrace approach affected by crosstalk noise. This approach minimizes the number of X-bit filling from the total X-bits produced, which successively reduces the total number of input pattern combinations (each X-bit can be filled and tested with '0'and '1') applied during the test for physical design defects. The relevant X-bits in the input patterns were filled in the STIL output file, generated by ATPG. STIL (Standard Test Interface Language) file gives the information about the insertion structure of the scan flip-flops and the location of the relevant X-bits that needs to be filled in the input patterns. Further efforts to elucidate the backtrace approach is mentioned below. In this approach, all the identified multi-aggressors were backtraced to the individual scan flip-flop inputs and primary inputs. These input bits are the only relevant X-bits that impact the victim net and needs to be filled. Consider the combinational logic part of the circuit in Figure 2.12, it has 3 primary inputs (PI) with primary input insertion structure 'PI1 PI2 PI3' and 9 scan flip-flop inputs (SI) with scan input insertion structure 'FF1 FF2 FF3 FF4 FF5 FF6 FF7 FF8 FF9'. This is further explained by giving test inputs PI = 0X1 and SI = X0X1X1XX0 to the circuit. From this data, we can see that 6 X-bits needs to be filled in the input pattern. Therefore, 2 6 = 64 X-filled input pattern combinations have to be applied to test the circuit for finding a worst-case path delay pattern. By applying our backtrace approach, we find that inputs to PI2, FF3, FF4, FF8 and FF9 are the most relevant bits in our analysis, refer Figure 2.12. Among them, FF4 and FF9 were already filled by the ATPG; since these bits are controllable but not observable from the primary inputs. Hence, only 3 X-bits are needed to be filled, so The step-by-step details of a typical scan operations for LOC delay test are described as follows:

• The first step is to put the scan flip-flops into scan mode. This is done by using the Scan Enable signal. In this case, forcing Scan Enable to 1 enables the scan mode.

Note that initially all the scan flip-flops at unknown state (X).

• The scan-in process starts. Then the first 3 bits are scanned in. A single test bit is shifted-in at each clock cycle. Usually, the scan shift frequency is much slower than the functional operating frequency of the CUT.

• At this stage, the complete test vector is shifted-in. Scan mode can be disabled by forcing Scan Enable to 0. Note that the shifted-in test vector is currently applied to the combinational logic pieces that are driven by scan flip-flops. It means that 2nd, 3rd, and 4th combinational logic blocks are already forced test inputs.

• The next step is to force primary input (PI) values and measure the primary output (PO) values: force PI and measure PO.

• Now, it is required to create a second test vector to create signal transitions. The second vector will be the output responses of the combinational blocks. Each block will generate the second test vector for the next stage. Since there is no stage before the 1st combinational block, force PI needs to be applied one more time.

• In order to push the output responses of combinational blocks into scan flip-flops, the system clock is toggled. Once this is done and second PI force is applied, the second test vector for the delay test is generated. The second input vector will generate output responses similar to the first one. These output responses needs to be captured, similar to the first one, by toggling the system clock. However, now there is a difference: The system clock has to be toggled at the real operating frequency. This means that the period between the first clock toggle and second clock toggle should be equal to functional clock period. In this way, the delay-test responses are captured at the functional operating frequency. As a result, correct functionality of the circuit is tested at-speed.

• Finally, the captured responses are shifted-out using the slow clock frequency.

Here, we mention our add-on's to the existing LOC scheme for the example we were describing. During the scan mode, the scan inputs 'X0X1X1XX0'were shifted in serially at each clock cycle and applied to the logic blocks. Then forced primary inputs '0X1'. We selectively fill these X-bits obtained from our backtrace approach (as shown in Table 2.7, row 3) for effectively testing patterns under the impact of multi-aggressor crosstalk noise.

Stage VII : Path Delay Measurement

In this stage, we measure the delay variation due to the combined impact of multiaggressor Xtalk, PSN and GB on a victim path. The SPICE circuit netlist is updated with all the calculated multi-aggressor cross-coupling capacitance's from stage V. We also included parasitic parameters extracted from the physical design layout of the circuit netlist along with the global power supply and the ground voltage as inputs. SPICE simulations were performed for capturing the worst-case path delay, with global variation of power and ground voltage level distribution (10% tolerance from the global values) as explained in section 2.4. The combined impacts were evaluated for all the relevantly filled X-bit patterns combinations of the primary and scan inputs. Then, SPICE simulations were performed for capturing the worst-case path delay. Path delay measurement can also be performed using STA tools. However, for establishing the realistic nature (by adding the physical design data such as parasitics in the interconnecting nets) of the multi-aggressor crosstalk noise, we utilize SPICE simulations to obtain a worst-case path delay pattern.

By our presented PDAPG method, we identify partially filled X-bit pattern that can capture worst-case path delay in a victim path. This pattern is compared with the random pattern generated in stage IV and their mismatches are highlighted to show effectiveness in the pattern we identify. In this section, experimental results for eight full-scanned versions of ITC'99 Benchmark [1] circuits are given. Our main goal is to identify a test pattern that can capture the worst-case path delay in the combined presence of multi-aggressor crosstalk, PSN and GB. Although, this method is implemented on a selected victim path, the same can be applied on any victim path. SPICE simulations are finally run to identify the worst-case path delay pattern. The delay is captured for the combined impact of multi-aggressor crosstalk, PSN and GB for different test patterns. The description of the benchmark circuits, the number of gates and the number of scan flip-flops for the circuits are shown in columns 1, 2 and 3 respectively in Table 2.8. Experimental results of ITC'99 benchmark circuits are summarized in Table 2.9. The total number of victim paths generated are given in column 2. In column 3, the %reduction of X-bit input pattern count for a selected victim path in shown. Runtime for testing all the patterns and the path delay variation (%) in comparison with the ATPG pattern are shown in column 4 and 5 respectively. From this list, we selected a strongly robust victim path (as described in section 2.5.1.2) for our path delay fault analysis. ATPG (SI pattern -10011000 and PI pattern -100110) and the X-bit pattern (SI pattern -XX0110XX and PI pattern -100X1X) were generated.

Experimental Results

We identified all the multi-aggressors from the PD layout of the circuit netlist. Their individual coupling capacitance's (measured 0.0005pF in total) were calculated between each aggressor and victim interconnects. By our backtrace approach, the relevant X-bits (inducing crosstalk) that control the input of the X-bit pattern were detected. They are the first two X-bits of SI pattern (xx0110XX) and both X-bits of PI pattern (100x1x), denoted by small letter 'x'. This method reduces the complexity in testing of test pattern by 75% (i.e, from 2 5 (5 X-bits) = 32 to 2 3 (3 X-bits) = 8). Nominal path delay of 216ps is measured for these X-filled test patterns without considering any PD issues. After considering the combined impact of PD issues, we measured a worst-case path delay of 319ps for multi-aggressor crosstalk capacitance, PSN and GB values of 0.0005pF, 0.9V and 0.1V respectively. The path delay obtained for the test pattern (PI pattern -100111 and SI pattern -110110XX) is 47.46% larger than the nominal path delay (without considering crosstalk, PSN and GB impacts on an ATPG pattern); hence this is a high quality test pattern that should be identified during path delay testing. The high quality test pattern signifies that this pattern gives the worst-case path delay, when applied to the selected victim path. By implementing our PDAPG method on the selected ITC'99 benchmark circuits, we were able to obtain the following: 1) an average reduction of test pattern count by 83.47%, and 2) capture an average path delay variation of 57.23%.

Table 2.10 shows the pattern comparison for the scan inputs (SI) and the primary inputs (PI) obtained from ATPG tool and our PDAPG method. Test pattern generated by the ATPG tool (ATPG pattern) is shown in column 4 with the pattern identified by physical design aware pattern generation method (PDAPG pattern) shown in column 5, along with the X-bit pattern in column 3. The mismatch between the test patterns can be clearly distinguished. The worst-case path delay variation between the ATPG pattern and the PDAPG pattern for the selected victim path is quite high. Ignoring this pattern may cause path delay defect escape during path delay testing. Thus, we show that the PDAPG method is an accurate and efficient delay testing strategy for ensuring better path delay defect coverage in the combined presence of multi-aggressor crosstalk, PSN and GB. We acknowledge that the proposed approach is accurate after performing a detailed timing analysis but is also limited in considering all the multi-aggressors from layout due to the larger circuit size and high volume of X-bit filling, which is also the focus of our ongoing work.

Summary

In this chapter, we presented a novel physical design aware pattern generation (PDAPG) method for path delay testing. PDAPG method focuses on identifying the test patterns that can capture worst-case path delay on victim paths in a circuit. The path delay is captured in the combined presence of physical design issues such as multi-aggressor crosstalk, power supply noise and ground bounce. Our PDAPG method was implemented on ITC'99 benchmark circuits and results were shown by pattern comparison and path delay measurement. By our backtrace approach, we also demonstrated its effectiveness in reducing pattern count during path delay testing. Although, we used a single robust victim path as our initial victim path repository, our method can be applied to any number of victim paths for efficiently identifying the high-quality test patterns. Results suggest the refinement of the existing test methods in timing-aware ATPG tools for incorporating the combined impact of different PD issues. We acknowledge that the proposed approach is accurate after performing a detailed timing analysis, but is exhaustive while performing SPICE simulations for all test patterns due to the larger circuit size and high volume of X-bit filling. This is also the focus of our next work to generate crosstalk-aware patterns.

Introduction

As shown in chapter 2, crosstalk noise causes considerable path delay variations. The physical design aware pattern generation method previously discussed is an exhaustive SPICE-based simulation for bigger circuits. In this work, we aim at generating a dedicated crosstalk-aware pattern that can be utilized for path delay fault testing without using SPICE-based simulations. Due to the complexity in developing and modeling power supply noise and ground bounce effects to ATPG tool, we have only considered crosstalk noise issues in this chapter. The other effects will be dealt as future perspectives.

Several prior works were focused on crosstalk noise and delay-aware ATPG. Still, there is a growing concern in the semiconductor industry for devising better test pattern generation methods to identify an effective pattern at a lesser computational time. ATPG tools utilize the existing path delay fault models to generate test patterns that may or may not capture a crosstalk induced delay defect. These tools utilize static timing analysis (STA) inputs [START_REF]PrimeTime User Guide[END_REF] that are dependent on the lengths of a path (consists of many gates in a path). With the objective of reducing computational time in pattern generation procedure, these delay fault models are based on zero interconnect delay in ATPGs. They target to capture as many faults as possible for an entire circuit with a lesser number of patterns in reduced time. Also, they do not consider the physical design data of a circuit during pattern generation. In other words, interconnect delays which are due to crosstalk noise are neglected during the ATPG path delay test. Therefore, a worst-case path delay pattern may not be identified during the delay test. Due to these reasons, path delay test using timing-aware ATPG tools need to be re-examined for taking into account crosstalk noise delay.

Prior Work

In recent years, path delay based pattern generation has received greater attention for capturing delay defects. Several techniques were proposed in the literature for considering crosstalk noise during path delay fault testing. A circuit redesign can reduce crosstalk noise, but cannot fully wipe out its impact on circuits in advanced technology models with higher density. Therefore, there is always a need for accurate crosstalk analysis and better pattern generation techniques.

Some of the earlier works based on delay testing, consider the gates and interconnect delays. Authors in [START_REF] Krstic | Test Conference, 2001. Proceedings. International[END_REF] present a genetic algorithm based approach to find patterns that produce longer path delays. In [START_REF] Lee | A Novel Pattern Generation Framework for Inducing Maximum Crosstalk Effects on Delay-Sensitive Paths[END_REF], a pattern generation framework by inducing maximum crosstalk effects across targeted delay-sensitive paths are proposed. A test generation technique in the presence of worst-case coupling effects for critical delay paths is presented in [START_REF] Zhang | Path delay test generation toward activation of worst case coupling effects[END_REF]. Furthermore, [START_REF] Peng | Crosstalk-and Process Variations-Aware High-Quality Tests for Small-Delay Defects[END_REF] proposes pattern evaluation and selection procedure for the impact of crosstalk and process variations. The method proposed in [START_REF] Sanyal | Test Pattern Generation for Multiple Aggressor Crosstalk Effects Considering Gate Leakage Loading in Presence of Gate Delays[END_REF] focuses on an ATPG solution for the multi-aggressor crosstalk noise and on finding the patterns activating worst-case crosstalk effects. All these works were based on finding an accurate set of patterns, but may take higher execution time with bigger circuits. Also, path delay estimation on some of these works were based on gate level circuit netlist. The approach proposed in [START_REF] Ganeshpure | Automatic Test Pattern Generation for Maximal Circuit Noise in Multiple Aggressor Crosstalk Faults[END_REF] uses the physical design layout information for multiple aggressor crosstalk faults. However, their estimations were deployed on heuristic techniques.

For reducing the complexity in ATPG, the works in [START_REF] Gope | Maximizing crosstalk-induced slowdown during path delay test[END_REF] and [START_REF] Chun | ATPG-XP: Test Generation for Maximal Crosstalk-Induced Faults[END_REF] propose crosstalkaware pattern generation in comparatively lesser computational time. Our efforts are to investigate the impact of multi-aggressor crosstalk noise on path delay variations and identify the test patterns that lead to worst-case path delay. To do this, we develop a method to generate crosstalk-aware test patterns.

Contributions and Chapter Organization

Our major contributions presented in this chapter are:

-We first show that the path delay in a circuit is significantly high due to crosstalk noise. Thereafter, demonstrated that an ATPG tool is incapable of generating patterns causing worst-case path delay.

-Then, we present our Crosstalk-Aware Test Pattern Generation (Xtalk-ATPG) method to identify high quality test patterns in the presence of multi-aggressor crosstalk noise.

Xtalk-ATPG method can be computationally exhaustive.

-Therefore, we further aim at customizing the existing path delay fault ATPG to include crosstalk noise impact. This can be an effective alternative to SPICE-based simulation in delay testing [START_REF] Chen | Examining Timing Path Robustness Under Wide-Bandwidth Power Supply Noise Through Multi-Functional-Cycle Delay Test[END_REF] in terms of computational time.

-All these efforts lead to generate a high quality test pattern during path delay testing.

The rest of the chapter is organized as follows. In Section 3.4, we describe a motivational experiment to indicate the importance of adding crosstalk noise during the path delay test. Section 3.5 presents the detailed flow of Xtalk-ATPG method and their experimental results. In Section 3.6, we elaborate our proposed constrained ATPG method of pattern generation by using the path delay fault test. In Section 3.7, we provide the summary of our contributions in this chapter.

Motivational Experiments

The main motivation behind our work of crosstalk-aware pattern generation is presented in this section. We highlight the impact of crosstalk noise by identifying a worst-case path

delay

Path Delay Analysis

An ISCAS89 benchmark circuit s27 is developed in SPICE to analyse the impact of crosstalk noise on path delay variations. Here, we have considered a sequential circuit in comparison to the motivational experiment in chapter 2 in order to understand the path delay variation in a sequential circuit. This SPICE level circuit includes parasitics in interconnects which are usually ignored at gate level simulation. Measured path delays for all test patterns obtained from SPICE simulations helps us to understand which patterns and under what conditions will provide the worst-case delay in a circuit path. Victim path we examine is highlighted in Figure 3.1(a). Cross-coupling capacitances

(C X1 , C X2 , C X3 , C X4 , C X5 , C X6
) that causes crosstalk noise in this victim path are not generally extracted by the tools [108]. This capacitance can only be estimated based on the aggressor net proximity from the victim net. We identify all the aggressor nets affecting the entire victim path from the layout. As there are many aggressors [START_REF] Sanyal | Test Pattern Generation for Multiple Aggressor Crosstalk Effects Considering Gate Leakage Loading in Presence of Gate Delays[END_REF] with varying signal transitions and with different arrival times, the path delay alters to a greater extent.

Sketch of s27 circuit layout is shown in

SI

The combinations of all possible permutations of crosstalk noise, vector pair signal transitions and different arrival times result in a large data set. Therefore, the minimum to maximum path delay variations obtained in comparison with nominal delay (i.e., without crosstalk noise) is only shown in column 4 of Table 3.1. For a simple circuit like s27, the maximum path delay variation of +5.07% is obtained. This indicates the importance of considering the impact of multi-aggressor crosstalk noise during the path delay analysis.

The vector pairs (V1, V2) to the flip-flops (FF1, FF2, FF3) identified after the SPICE simulations, their worst-case path delay (δ 1 ) are listed in column 2-5 of Table 3.2. 3.2 lists, the ATPG tool generated vector pairs (V1, V2) for the flip-flop (FF1, FF2, FF3) inputs and the worst-case path delay (δ 2 ) measured in SPICE by the respective vector pair.

Path Delay Fault Testing

Comparison of Vector Pairs

In this subsection, we compare the vector pairs identified from SPICE simulation with the one generated by the ATPG tool and their mismatches are highlighted.

∆ v FF FF FF δ 1 FF FF FF δ 2 1 2 3 (ns) 1 2 3 (ns) (%) V1 1 0 1 0.289 1 0 1 0.286 1.05 V2 1 1 0 0 1 0 ∆ v = (δ 1 -δ 2 ) δ 1 × 100 (3.1)
In Table 3.2, we can see a mismatch in the vector pair at FF1 between the SPICE and ATPG patterns. The path delay variation (∆ v ) in equation 3.1, is the mean delay difference between the worst-case delays obtained from SPICE (δ 1 ) and ATPG (δ 2 ) patterns.

The ∆ v of 1.05% (slowdown impact on the victim path) listed in column 10, implies that a path delay fault test is not performed with a good pattern by ATPG. This path delay is quite high for a small circuit like s27 and it may be even higher and at an unacceptable percentage in bigger circuits. Thus, we provide an evidence that a circuit may escape the test to detect crosstalk delay defect due to lower quality in the applied vector pair. This indicates a serious notice in customizing the existing path delay fault testing method in ATPG. Therefore, our work emphasizes the need for refining ATPG tools and proposing novel methods to include good patterns that can be utilized for capturing crosstalk noise delay defects. For bigger circuits, there may exist many large sets of test patterns. So, it is desirable to implement a method to include crosstalk noise effects during pattern generation.

Crosstalk-Aware Test Pattern Generation Method

Xtalk-ATPG Flow for Pattern Generation

Crosstalk-Aware Test Pattern Generation (Xtalk-ATPG) is similar to the physical design aware pattern generation (PDAPG) method shown in seven stages. Here, we consider only the impact of crosstalk noise. Please refer chapter section 2.5 for its description of pattern generation.

Experimental Results

Xtalk-ATPG method is conducted on ten full-scanned versions of ITC'99 Benchmark [1] circuits with their functionality briefly represented in Table 3.3. The number of gates, scan flip-flops after circuit netlist synthesis and scan chain insertion [53] are respectively shown in column 3 and 4. The total number of victim paths generated [START_REF]PrimeTime User Guide[END_REF] are given in column 4. Our major objectives of this experimental analysis are to show the difference in the patterns and the variations in their path delay measured in the presence of crosstalk noise.

They are the random pattern generated by the ATPG tool and the pattern identified by our Xtalk-ATPG method. We also, demonstrate that the pattern identified gives better results during the path delay fault test. It is capable of capturing worst-case path delay in the presence of multi-aggressor crosstalk noise on a victim path. Although, this method is implemented on a selected victim path, the same can be applied to any victim path.

Selective SPICE simulations are run on a circuit to find a path delay pattern. The details and the experimental results of ITC'99 benchmark circuits are summarized in Table 3.4. In column 2, the number of aggressor nets identified from the layout (mentioned in section 2.5.1.5) is indicated. The total number of X-bits to be filled are given in column 3. Aggressor nets are backtraced to fill the relevant X-bits in the test pattern with their count mentioned in column 4.

We demonstrate Xtalk-ATPG method based on b06 benchmark circuit. Eight victim paths were generated for b06 circuit netlist. There exists many path delay fault class [START_REF] Krstić | Delay fault testing for vlsi circuits[END_REF] based on the sensitization of a victim path. From the summary of the path delay fault class, they are classified as ATPG untestable (3 paths), ATPG undetected (1 path) and a number of aggressor nets, b number of X-bits, c number of X-bits filled, d % reduction in input pattern combinations (with X-bits), e runtime for testing all patterns based on Xtalk-ATPG method (in sec), f path delay variation (crosstalk noise)

ATPG detected (4 paths). The ATPG detected paths were further analyzed for robust (3 paths) and non-robust (1 path) paths. Among them, we select a robust path for our path delay fault analysis. This ensures that at least a single delay fault is detected during the launch-off-capture scheme of pattern generation. Then the robust path (victim path under consideration) is path delay fault tested in ATPG tool. A random pattern and an X-bit pattern were generated as shown in Table 3.5. These patterns are given to the primary inputs (PI) and the scan flip-flops inputs (SI) of the circuit. This random pattern is kept as a reference to compare with the X-bits filled (in Xtalk-ATPG method) pattern in terms of worst-case path delay and the computational time.

All the cross-coupling capacitance's (measured 0.5fF in total) were individually calculated between the identified multi-aggressors and the victim nets. By our backtrace approach, the relevant X-bits (indicated by small letter 'x') in the X-bit patterns that control aggressor nets (by inducing crosstalk noise), thereby affecting the victim nets were

FF1 FF2 FF3 FF4 FF5 FF6 FF7 FF8 PI1 PI2 PI3 PI4 PI5 PI6 random 1 0 0 1 1 0 0 0 1 0 0 1 1 0 X-bit x x 0 1 1 0 X X 1 0 0 x 1 x Xtalk-ATPG 1 1 0 1 1 0 X X 1 0 0 1 1 1
also detected. They are the first two X-bits in the scan flip-flop input and both the X-bits in the primary input (those colored in Table 3.5). In other circuits, some of the relevant X-bits may be already filled by the tool, so they are not modified. Xtalk-ATPG method minimizes the complexity by 75% in delay fault testing by applying reduced X-bit input pattern combinations (i.e., 2 4 (4 X-bits filled) = 16 instead of 2 6 (6 X-bits) = 64). By this way, we selectively provide the pattern combinations for path delay testing. Computation for the percentage reduction in the X-bit filled pattern (∆ X-bit ) combinations given at the circuit input is based on the equation:

∆ X-bit = 2 #X-bits -2 #X-bitsf illed 2 #X-bits × 100 (3.2)
Equation 3.3 gives the computational time for testing all combinations of input patterns (t r ) for crosstalk noise. This time includes the time taken for the generation of the X-bits filled pattern (t atpg ) and for performing their corresponding SPICE simulation (t SP ICE ). The computational time taken by the different benchmark circuits are shown in column 6 of Table 3.4.

t r = (t atpg + t SP ICE ) × 2 #X-bitsf illed (3.3)
Nominal path delay (δ n ) of 216ps is measured for the random pattern without considering crosstalk noise. After considering the impact of multi-aggressors, 268ps crosstalk delay (δ xtalk ) is measured for the X-bit filled (Xtalk-ATPG) pattern. The path delay variation for the Xtalk-ATPG pattern, shown in the last row of Table 3.5 is 24.07% greater than the nominal path delay; hence this is a high quality input pattern that should be identified during path delay fault testing. The high quality test pattern signifies that this pattern gives the worst-case path delay, when applied to the selected victim path. Path delay variation is computed by:

∆ Xtalk = (δ n -δ xtalk ) δ n × 100 (3.4)
These details of the other circuits are respectively shown in column 5, 6 and 7 of Table 3.4. By implementing our Xtalk-ATPG method on the ITC'99 benchmark circuits, we were able to obtain the following: 1) an average reduction of test pattern count by 87.41%

for the 10 ITC'99 benchmark circuits mentioned, and 2) could capture an average path delay variation of 31.73%.

The objective of Table 3.6 is to show the variation between the random pattern obtained from ATPG tool and the pattern identified by our Xtalk-ATPG method. They are separately mentioned for scan inputs (SI) and the primary inputs (PI). X-bit patterns, random patterns and Xtalk-ATPG patterns are respectively shown in the 1 st , 2 nd and 3 rd rows of each circuit. The mismatch between the patterns can be clearly distinguished.

The worst-case path delay variation between the random pattern and the Xtalk-ATPG pattern for the selected victim path is also quite high. Ignoring Xtalk-ATPG pattern may cause path delay defect escape during path delay fault testing. Thus, we show that the Xtalk-ATPG method is an accurate and efficient delay testing strategy for ensuring better delay defect coverage in the presence of multi-aggressor crosstalk. The scripts for aggressor net identification, cross-coupling capacitance calculation, backtrace approach and testing with different combinations of patterns were implemented in PERL. These experiments are performed on Linux ×86 64bit servers with 48 sockets and 1 core per socket and 176GB of available memory.

We acknowledge that the proposed approach is accurate after performing a detailed timing analysis but is also limited in their computational time needed to test all the pattern combinations of the generated X-bit pattern and further their selective SPICE simulation. This is due to the high volume of X-bit filled pattern combinations given during SPICE-level simulation. Minimizing the computational time for generating a crosstalkaware path delay pattern is the focus of our following work.

Constrained ATPG (C atpg ) Method

In this section, we present a novel flow of pattern generation that can be effective in capturing crosstalk-induced delay defects. The assurance with this flow is the reduced based on selective SPICE simulations (i.e., by selective X-filling), it takes higher runtime for bigger circuits.

Stage I : Identification of Aggressor Nets

We utilize industrial tools such as Cadence Encounter RC Compiler [53], Synopsys Prime-Time Static Timing Analysis (STA) tool [START_REF]PrimeTime User Guide[END_REF] and Cadence SOC Encounter tool [108] to generate a circuit netlist, select a victim path and to perform placement and routing of the circuit netlist, in their respective order. From the circuit layout, the aggressor nets were determined for all the victim nets in the victim path. This is based on the separation between two nets (140µm), the degree of the aggressor net impact on a victim net and the width of the aggressor nets (for metal 1, 120µm and for metal2, 140µm were considered).

Each aggressor net may reside in different metal layers with varying length, this information is fetched from the DEF (Design Exchange Format) file. Therefore, determining all the aggressor nets from the layout of the circuit gives a better estimate of the impact of crosstalk noise on path delay. We select a strongly robust victim path (as described in section 2.5.1.2) from b08 circuit to test our method. 22 aggressor nets were identified for the 5 victim nets, their notations are given in Table 3.7. Some of the aggressor nets were neglected, if it is (1) a clock net, or (2) a victim net acting itself as an aggressor net to another victim net, or (3) the same aggressor net affecting two different victim nets in the victim path. If it is the last case, then the choice is made based on their degree of impact on the victim net.

Stage II : Sorting and Ranking

Firstly, the identified aggressor nets (as shown in Figure 3.7) are sorted based on their impact on the victim net, i.e., the higher cross-coupling capacitance between them will have a higher impact. Capacitance values were measured between 0.02fF -2fF for a b08 circuit path.

Secondly, we rank the aggressor nets (as shown in Figure 3.8), i.e., nets with lower capacitances are given a lower rank (Rank 22) as they have only a minimal influence on the victim path delay [START_REF] Asokan | A Delay Probability Metric for Input Pattern Ranking Under Process Variation and Supply Noise[END_REF]. Aggressor nets with higher capacitance were given higher rank (Rank 1). Their ranking order is shown in column 3 of Table 3.7.

Stage III : Constraining Aggressor Nets and Pattern Generation

Stage III is our major contribution in the constrained ATPG method. We customize the existing ATPG tool, TetraMAX ® [START_REF] Tetramax | Automatic Test Pattern Generation[END_REF] to generate a crosstalk-aware pattern that can detect a path delay fault. This ATPG tool is unaware of the impact of crosstalk noise on victim path delay. Therefore, we aim at generating a crosstalk-aware pattern by giving constraints to the aggressor nets that in turn impact the victim path delay. In general, crosstalk delay defect can be determined beforehand by adding their impact during exhaustive or selective SPICE simulations, but it is computationally very expensive. We compare the proposed constrained ATPG method with the earlier mentioned Xtalk-ATPG method [START_REF]Path Delay Test in the Presence of Multi-Aggressor Crosstalk, Power Supply Noise and Ground Bounce[END_REF] (section 2.5) in terms of (1) computational time in identifying a crosstalkaware path delay pattern, and (2) validating the effectiveness of this pattern by evaluating their worst-case path delay. Xtalk-ATPG method is based on ATPG and selective SPICE simulation in contrast to the constrained ATPG method (based exclusively on ATPG).

In the latter method, SPICE simulation is merely used to compare the worst-case path delays.

Table 3.8: Aggressor net transition and delay measurement a victim nets, b transition in the victim net, c aggressor nets, d contraining aggressor net with opposite trasition, e fault class, f path delay variation for a constrained ATPG pattern, g contraining aggressor net with stable 0, h contraining aggressor net with stable 1, i indicates a rising transition, j indicates a falling transition, k ATPG fault that is either undetectable or untestable, l ATPG detected fault class that is testable.

Rank Vnet a C b v Anet c C d 1 FC e ∆ f v C g 2 FC ∆v C h 3 FC ∆v 1 Vn3 R i An6 F j UD/AU k 0 DT l 0% 2 Vn3 R An5 F UD/AU 0 DT 0% 3 Vn4 F An19 R UD/AU 0 UD/AU 1 DT 0% 4 Vn4 F An18 R UD/AU 0 UD/AU 1 DT -0.04% 5 Vn3 R An15 F UD/AU 0 DT -0.04% 6 Vn1 R An3 F UD/AU 0 DT -0.04% 7 Vn3 R An13 F UD/AU 0 UD/AU 1 DT -0.04% 8 Vn4 F An21 R DT -0.68% 9 Vn3 R An12 F UD/AU 0 DT -0.70% 10 Vn3 R An7 F UD/AU 0 DT -0.72% 11 Vn4 F An17 R UD/AU 0 UD/AU 1 DT -0.76% 12 Vn1 R An1 F UD/AU 0 DT -0.79% 13 Vn1 R An4 F UD/AU 0 DT -0.79% 14 Vn4 F An20 R UD/AU 0 UD/AU 1 DT -0.80% 15
In this stage 3, we constrain all the aggressor nets one after the other depending on the signal transition in their corresponding victim net, shown in Figure 3.9.

The aggressor net with the higher rank is constrained first based on their impact.

For a victim net with a Rising (R) signal transition, an opposite signal transition in the aggressor net is given initially, i.e., a Falling (F) transition can maximize the crosstalkinduced delay slowdown [START_REF] Gope | Maximizing crosstalk-induced slowdown during path delay test[END_REF]. Then we check whether it generates a testable pattern or not; this ensures that a given signal transition is propagated during the launch clock cycle in an at-speed test [START_REF] Li | Robust test generation for precise crosstalk-induced path delay faults[END_REF]. Sometimes, this gives an unsuccessful pattern generation.

Therefore, we constrain the victim net again with a stable 0 and then again with stable after the other until a final pattern is generated. This can be utilized for path delay fault testing in the presence of multi-aggressor crosstalk noise. Instead of constraining or modifying the victim net, we constrain all the aggressor nets simultaneously for pattern generation. This is the major thrust in this novel method.

Table 3.8 shows the results after applying the C atpg ATPG flow on b08 benchmark circuit. The details are as follows. Aggressor net ranking in column 1, victim net, their signal transition pattern (i.e., R for rising signal and F for falling signal) in column 2-3, their corresponding aggressor net in column 4, their signal transition (i.e., opposite transition F or R, stable 0, or stable 1), their fault class and path delay variation are mentioned in subsequent columns.

There exist several fault class for testing a path delay fault [START_REF] Krstić | Delay fault testing for vlsi circuits[END_REF], such as detected (DT), possibly detected (PT), undetectable (UD), not detected (ND) and ATPG untestable (AU); categorized based on the signal transition propagation, fault detection and pattern generation. Among them, we select the detected faults so that a signal transition in the victim net is propagated during the launch clock cycle. Then, we measure path delay in the victim net (∆ v ) in SPICE. This is to show the effectiveness of a pattern in determining the worst-case delay in a path. By simulating this pattern, we obtain the maximum possible worst-case delay of -1.73% on the victim path. Negative value shows the slowdown impact and a positive value notate a speedup in the victim path delay.

∆ v (C atpg ) = (δ r -δ Catpg ) δ r × 100 (3.5) ∆ v (Xtalk -AT P G) = (δ r -δ Xtalk-AT P G ) δ r × 100 (3.6)
Here δ r is the crosstalk delay due to a random pattern generated by ATPG; δ Catpg and δ Xtalk-AT P G are the worst-case path delays measured by the patterns obtained from the two methods C atpg and Xtalk-ATPG respectively. ATPG generates a random pattern to test path delay fault. This pattern is kept as the reference for path delay fault detection and worst-case path delay comparison. We describe explicitly one of the longest combinatorial victim path by giving trigger input at FF21 and observing its trigger output at FF4. According to the scan based launch-offcapture scheme, the scan inputs are shifted in. Then, the vector pair (i.e., test patterns)

< V 1, V 2 > i.
e., < 01011, 10100 > are given as the circuit's primary input for initiating a signal propagation in the victim path. In Table 3.9, the patterns generated by C atpg flow and the patterns identified from the Xtalk-ATPG method are compared. Also, path delays from both methods are verified. The path delay variation (∆ v ) obtained from each method is shown in the last row of this Table . By this, we show that C atpg method is able to achieve a delay value (-1.73%) closer to the Xtalk-ATPG method (-2.12%) (refer to equation 3.6), without utilizing SPICE simulations. We, thus show that C atpg method is an effective pattern generation method to detect crosstalk related delay faults. Aggressor nets are constrained based on their rank and the patterns are generated. Depending on the signal transition in the aggressor net, some of the X-bits are getting filled (by '1' or '0') and the already filled X-bits are either getting modified or remain the same.

Compared to the initial pattern, 8 scan flip-flop inputs are modified. SPICE simulation with this new pattern from C atpg can sometimes provide a better capture of worst-case delay than the Xtalk-ATPG method. The latter method is based only on the filing of the X-bits in the test pattern and no changes to the already filled X-bits are made. These changes in the C atpg method help to define a new worst-case path delay.

In Table 3.9, we also show the modified patterns in the aggressor nets after constraining them. As aggressor nets are either primary input nets, scan input nets or other interconnecting nets between the standard cells, a constrained signal transition in them can force to change the generated pattern. Therefore, constraining these nets with opposite or stable 0, stable 1 signal transition, modifies the pattern generated by the tool. From the vector pair colored in Table 3.9, we can see that 13 aggressor nets are undergoing changes in their signal transition after applying C atpg method. Comparison between the sketched waveforms is shown in Figure 3.11. After the clock, scan enable (SE), scan input (SI) signal, victim net transition is shown, followed by their respective aggressor net transitions. These nets are constrained and the pattern generated based on the victim net transition. Some of the nets that have an X-bit (don't care bit) input are getting filled either by '1'or '0'. The forced filling of these bits aggravates the victim nets to generate good patterns that can be utilized for testing crosstalk noise. Not only the X-bits are getting filled, the already filled bits in the input pattern are also undergoing changes (or getting modified) in order to activate the signal propagation. The newly generated test pattern shows the effectiveness in capturing the worst-case path delay. Launch and capture cycles are highlighted in this figure 3.11. X-bits are indicated in red color. We show the delay variation in the victim path due to the impact of the aggressor net in Figure 3.12. Aggressors are constrained one after the other based on their rank, as mentioned in C atpg flow. From the plot, we can see that there are two successful opposite pattern transitions (first at An21 and then at An9) that are highly maximizing the slowdown of victim path delay. Path delay variation is comparatively low after constraining other aggressor nets, as they are stable conditions.

Experimental Results

In this section, we describe the experimental results after applying C atpg flow on 21 fullscan versions of ITC'99 benchmark circuits [1]. Our aim is to generate a pattern that can be effective in path delay fault testing. This pattern is capable of capturing worst-case delay in the victim path in the presence of multiple aggressors with their varying degree of impact. Our method of pattern generation is fully based on ATPG tool. We could save a lot of computational time as this method has not used SPICE or selective SPICE simulations for pattern identification. This flow is scalable and can be applied to any sized circuits. a number of X-bits, b number of X-bits filled by backtrace approach, c number of aggressor nets, d by Xtalk-ATPG method, e by constrained ATPG method, f path delay variation difference between Xtalk-ATPG and Catpg method, g computational time difference between Xtalk-ATPG and Catpg method, h path delay variation (crosstalk noise) by Xtalk-ATPG method, i computational time for Xtalk-ATPG method, j path delay variation (crosstalk noise) by Catpg method, k computational time for Catpg method, l computational time in seconds.

Details of experimental results are summarized in Table 3.10. Number of X-bits in the scan input and primary input pattern are given in column 2. These inputs are generated by the ATPG tool by performing path delay fault test on a victim path. In column 3, the minimum number of relevant X-bits that need to filled in Xtalk-ATPG method is shown.

The number of all possible aggressor nets to the selected victim path are given in column noise. We acknowledge that the proposed flow is simple to implement, and it is better in terms of computational time and worst-case path delay patterns.

Summary

In this chapter, we presented a crosstalk-aware pattern generation method for emphasizing the impact of crosstalk noise on path delay of a circuit. This method focuses on identifying a test pattern that can capture worst-case path delay on a victim path. Although, we used a single victim path as our initial path repository, this method can be applied to any paths for identifying a high quality test pattern. Results from this method suggest the refinement of the existing ATPG path delay test methods for incorporating the impacts of crosstalk noise. Further, we proposed a novel flow of constrained ATPG method targeting path delay fault. This method could eliminate the selective SPICE simulation and it produces patterns to test the worst-case path delay in lesser computational time. All the step by step procedures related to C atpg method are completely automated. Our flow is implemented on ITC'99 benchmark circuits and the results were shown by comparison with SPICE simulation. By this flow, we also show the effectiveness in computational time and the generation of a high quality pattern. The explanation of this method is based on a specific ATPG tool, TetraMAX ® , but the same can be adopted in any ATPG tool or method to identify the right set of PDF patterns.

manufacturing process variations combinedly with the noise disturbances in the power supply and ground networks on delay. ATPG tools are commercially utilized to detect delay-related defects. As these tools ignore the physical design parameters affecting the gates, interconnects, power supply and ground networks, they are incapable of accurately generating the right pattern that can capture worst-case path delay in a circuit. Statistical static timing analysis (SSTA) [START_REF] Li | On hierarchical statistical static timing analysis[END_REF] based techniques models gate or path delays, considers the variations in all interconnecting nets between the gates in a path. Also, SSTA and process corner based STA techniques [START_REF] Chang | Statistical timing analysis considering spatial correlations using a single PERT-like traversal[END_REF] work with delay probability distributions.

However, they are too complex and time consuming to work with realistic path delay distributions and identify an accurate delay pattern. This has motivated us to propose a simple and novel delay probability metric to identify a worst-case path delay pattern for capturing delay defects in the presence of process variations and supply noise.

Unpredictable process parameter fluctuations and changing operating voltage conditions cause random variations in the circuit parameters, thereby affecting the expected nominal path delay values. Fluctuations in the manufacturing process affect the gate parameters such as threshold voltage (V th ), oxide thickness (t ox ), transistor length (L g ) and width (W g ), as well as the width of interconnects by varying the interconnect resistances (R), inductances (L) and capacitances (C). Operating voltage of a circuit varies depending on the noise disturbances in their power supply (i.e., power supply noise) or ground networks (i.e., ground bounce), thereby varying the drive strength of the gates in a path. Also, path delay of a circuit varies randomly depending on the test vectors (input patterns) applied at their inputs and their arrival time difference between the applied vectors. The combined impact of all these effects makes path delay estimation very difficult. Therefore, a simple yet effective method for identifying the worst-case or the most effective path delay patterns that can capture a delay defect during testing is essential.

In this work, we propose a delay probability metric to identify a worst-case path delay pattern in the presence of reliability issues (PV) and power integrity issues (SN). This metric utilize 90nm Cadence Generic Standard Cell Library to run the process corner [START_REF] Onaissi | A Linear-Time Approach for Static Timing Analysis Covering All Process Corners[END_REF] based SPICE simulations to obtain the delay distributions for all the gates and interconnects in a path. Other approaches such as monte carlo simulations [START_REF] Agaram | Insights into process reliability through simulation[END_REF] will be too expensive, because of the increased number of corners and more conditions to evaluate for identifying a pattern in the presence of different combinations of PV and SN parameters. Also, it will complicate more with bigger circuits.

Prior Work

There are a number of contributions that investigate on the impact of PV's and SN. Based on the source of physical defects, they can be classified as delay defect: (1) due to a single source (i.e., either due to PV, SN or crosstalk noise), (2) from multiple sources, and

(3) irrespective of the source. The first classification focuses only on process variations [START_REF] Galarza-Medina | Smalldelay defects detection under process variation using Inter-Path Correlation[END_REF][START_REF] Wang | Path-RO: A novel on-chip critical path delay measurement under process variations[END_REF][START_REF] Tayade | Small-Delay Defect Detection in the Presence of Process Variations[END_REF][START_REF] Yu | A Framework for Accounting for Process Model Uncertainty in Statistical Static Timing Analysis[END_REF]. Francisco et al. [START_REF] Galarza-Medina | Smalldelay defects detection under process variation using Inter-Path Correlation[END_REF] proposed a statistical timing analysis framework based on delay correlation information between two paths. Critical path delay measurement using a ring oscillator is presented in [START_REF] Wang | Path-RO: A novel on-chip critical path delay measurement under process variations[END_REF]. Authors in [START_REF] Tayade | Small-Delay Defect Detection in the Presence of Process Variations[END_REF] have proposed an algorithm to detect a resistive interconnect defect for a path with minimum delay variance. An optimization framework is suggested by Yu [START_REF] Yu | A Framework for Accounting for Process Model Uncertainty in Statistical Static Timing Analysis[END_REF] based on SSTA for worst-case circuit analysis. In the second classification, different approaches for pattern generation from multiple sources were proposed [START_REF] Todri | Uncorrelated Power Supply Noise and Ground Bounce Consideration for Test Pattern Generation[END_REF][START_REF] Xu | The combined effect of process variations and power supply noise on clock skew and jitter[END_REF][START_REF] Peng | High-quality pattern selection for screening small-delay defects considering process variations and crosstalk[END_REF]. Todri et al. [START_REF] Todri | Uncorrelated Power Supply Noise and Ground Bounce Consideration for Test Pattern Generation[END_REF] has analyzed power supply noise and ground bounce for capturing worst-case path delay patterns based on simulated annealing. Xu [START_REF] Xu | The combined effect of process variations and power supply noise on clock skew and jitter[END_REF] described a statistical model for skitter with PV and power supply noise effects. Peng [START_REF] Peng | High-quality pattern selection for screening small-delay defects considering process variations and crosstalk[END_REF] explains their work of pattern evaluation and selection considering crosstalk and PV. In the third classification, worst-case delay of a circuit path is analyzed, with no detailed reference to the source of defects. A theoretical framework for statistical timing analysis is proposed by Orshansky and Keutzer [START_REF] Orshansky | A general probabilistic framework for worst case timing analysis[END_REF] for detecting the worst-case path delay in a circuit.

In contrast to all these works, our goal is to re-examine the problem of path delay pattern generation by introducing a delay probability metric for ranking patterns under the impact of PV and SN. Using the probabilistic metrics, we can estimate and identify an efficient worst-case path delay pattern or set of patterns that can capture the worst path delay. Our method is practical and easily adaptable to be implemented on any existing pattern generation flow. Complementary to the previous works, we have additionally incorporated the impact of ground bounce in supply noise.

Contributions and Chapter Organization

Our major contributions in this chapter are summarized as follows:

-A probability metric is presented to identify worst-case path delay pattern while considering the combined impact of PV and SN. This metric aims at detecting the mosteffective pattern for path delay testing from the subset of all input patterns.

-Ranking method is described based on the mean delay difference and the area of the delay probability distribution of all input patterns.

-Case study and simulation results are shown to validate our method.

The rest of the chapter is organized as follows. Section 4.4 demonstrates the motivational experiment for showing the difference in pattern generated by an ATPG tool and the worst-case path delay pattern identified from SPICE simulations. In Section 4.5, we formulate the problem of path delay distribution for detecting a worst-case pattern in the presence of PV and SN. An input pattern based ranking method is explained in section 4.6 to identify the right pattern in the presence of PV's and SN. Section 4.7 presents the simulation results on ITC'99 benchmark circuits. Finally, in Section 4.8, we summarize the findings in this chapter.

Motivational experiment

In this section, we show the main motivation behind our work of process variation-aware pattern generation. Essentially, our goal is to show that a standard ATPG tool may not be able to generate good patterns that can capture worst-case path delay in the presence of PV's. We utilize SPICE simulations to highlight the impact of PV on path delay of a circuit. The path delays for all the input patterns are measured and a single pattern is identified among them, which helps us to understand which patterns and under which conditions would provide the worst-case path delay. Such an input pattern is then compared with the ATPG tool pattern and their discrepancies are reported, hence showing that the circuit may escape the test due to the low quality of the applied test set.

Path Delay Analysis

Path Delay Fault Testing

For path delay fault testing, we reconstructed a sequential circuit module similar to the one in Figure. and interconnect length and width that impact interconnect parasitics, R, L, C. From supply noise perspective, we consider noise on power, V dd and ground, G nd .

The entire process flow of path delay estimation is shown in Fig. The delay of a pMOS transistor due to a rising input can be expressed as [START_REF] Weste | Principles of cmos vlsi design: A systems perspective[END_REF]:

δ r = 2C L β p [(V dd -G nd ) -|V thp |] [ |V thp | -0.1(V dd -G nd ) [(V dd -G nd ) -|V thp |] + 1 2 log | 19(V dd -G nd ) -20|V thp | (V dd -G nd ) |] (4.2)
where C L is the load capacitance including the next stage load and interconnect capacitance and V thp is the threshold voltage of pMOS transistor. Similarly, the transistor delay for a falling input can be expressed as [START_REF] Weste | Principles of cmos vlsi design: A systems perspective[END_REF]:

δ f = 2C L β n [(V dd -G nd ) -V thn ] [ V thn -0.1(V dd -G nd ) [(V dd -G nd ) -V thn ] + 1 2 log | 19(V dd -G nd ) -20V thn (V dd -G nd ) |] (4.3)
where V thn is the threshold voltage of nMOS transistor and β is the transistor gain factor (in pMOS and nMOS), can be expressed as:

β = µǫ t ox W g L g (4.4)
where µ is the effective surface mobility of the carriers in the channel, and ǫ is the permittivity of the gate insulator. Based on the transistor delay, the gate delay can be computed, such as for an inverter the average gate delay can be computed as:

δ g = (δ f + δ r )/2 (4.5)
Interconnects are usually modeled as π-networks with RLC parasitics, their delay, δ int can be computed by applying Elmore delay formulation as a function of ζ i at node i, as in [START_REF] Ismail | Equivalent Elmore delay for RLC trees[END_REF]:

δ int = 1.047e -ζ i 0.85 + 1.39ζ i (4.6)
where ζ i is expressed as:

ζ i = 1 2 k C k R ik √ k C k L ik (4.7)
where R k is the interconnect resistance, C k is the interconnect capacitance, L k is the interconnect inductance and k represents the number of elements on the π-network interconnect model. Hence, the delay on a path can be computed as the sum of gate delays and interconnects delays (i.e. for n gates and n -1 interconnects on a given path) that are triggered by a given input pattern as:

δ path = n i=1 δ g i + n-1 i=1 δ int i (4.8)

Delay Probability Distribution

For a given path, the delay would be a function of many variables due to PV and SN.

Path delay variations due to these variables can be expressed as a function of parameters as:

δ path = f (V dd , G nd , V th , t ox , L g , W g , R, L, C, C L ) = f (SN, P V ) (4.9)
Definition: In general terms, the path delay variation, δ path for a given input pattern, P I can be represented as a normal distribution function. As path delay (due to δ g i or δ int i ) can be real-valued random values whose distribution are unknown, the highest probability of worst-case path delay can be observed better using a normal delay distribution function.

The path delay due to the input patterns for all parameters (PV and SN) can be expressed as normal distribution N (µ P I , σ P I ).

The mean and standard deviation of a path delay for a given input pattern, P I and all parameters can be expressed as:

µ P I = 1 N N i=1
δ path i (4.10)

σ P I = 1 N N i=1 (δ path i -µ P I ) 2 (4.11)
where N represents the total number of path delay measurements for a given path under PV and SN parameters.

Probabilistic Pattern Ranking Method

Here, we describe the concept of deriving pattern ranking method utilizing the path delay distribution function. The standard flow of input pattern ranking method explained in this section is shown in Steps 2-4 are our major contributions.

Step 1 is similar to the ones shown in Chapters 2 and 3. In step 2, we add process variation and supply noise variation parameters to estimate the path delay of a selected path. Then, we distribute all the delay values for obtaining a normalized curve. Finally, we apply our input pattern ranking method based on their maximum mean delay difference and the probability of likeness of pattern that causes worst-case path delay on a circuit path.

Impact of Process Variations

Case I: In the first case, we study only the impact of PV, by varying the interconnect and transistor parameters while applying a nominal global supply voltage at their gates. Fig.

Impact of Supply Noise

Case II: In this case, we study only the impact of SN, by locally varying power supply and ground voltage, while considering no process variation on transistors and interconnects. For each input pattern, their respective µ P Id , P identif ication and rank are listed in column IV, V and VI of Table . 4.4. Using our probabilistic pattern ranking method, we obtain P I 8 as the worst-case path delay pattern under the impact of SN. After comparing Fig.

Impact of Process Variations and Supply Noise

Case III: In the third case, we investigate the combined impact of PV and SN. For each input pattern, their respective µ P Id , P identif ication and rank are listed in column IV, V and VI of Table . 4.5. Based on our probabilistic pattern ranking method, we obtain P I 8 as the worst-case path delay pattern under the combined impact of PV and SN. Please note that, while P I 8 pattern was also identified in case I and II, the value of the probability density function for path delay varies. The results of three different case studies indicate that by applying the proposed ranking method, we can identify the pattern(s) that lead to the worst-case path delay when PV and SN conditions are present.

Experimental Results

In this section, we present the results based on eight full-scanned versions of ITC'99 benchmark circuits [1], their functionalities are briefly described in Table 3.3. We apply our probabilistic based ranking method on a single victim path to identify the pattern that cause worst-case path delay, even though this method can be applied to any path. 8 and 11) for each input pattern, respectively. Then, we selected the input pattern with rank 1 i.e.,(000110XX, 100111), as by our method this pattern has the highest probability to give the worst-case path delay under the impact of PV and SN. Also, we selected the input pattern generated by the ATPG tool i.e., (10011000, 100110), whose rank is 13 as per our method. In column 8, the mean delay difference (i.e., 34.6%) between the two patterns (our method pattern and ATPG pattern) is mentioned. Such discrepancies further indicate the need to investigate the worst-case path delay problem and reveal the effectiveness of our method in ranking and selecting input patterns that take into account process variation and supply noise issues. The pattern generated by random X-filling using the ATPG tool differs from the pattern generated by our probabilistic method. This indicates that, while a test pattern

Thesis Summary

With semiconductor technology scaling, the defect spectrum now includes more problems such as crosstalk noise, resistive shorts, resistive opens in interconnects, power supply noise and ground bounce in the supply networks, as well as, process variations in interconnects or at gate level. These are not always detected by the traditional fault models.

Delay-related parametric failures in semiconductor devices increase the defect escape rate, yield loss and diminish the reliability rate. Therefore, different test techniques have been widely adopted in the industry to detect defects using patterns generated by ATPG tools (Automatic Test Pattern Generation). For instance, at-speed delay test uses the path delay fault model that targets delay defects during IC testing phase. They are commercially employed due to their minimal implementation cost and higher test coverage.

Signal and power integrity issues are mostly impacted by crosstalk noise, power supply noise and ground bounce, respectively. Also, due to the variations in the manufacturing process may cause reliability issues. All these issues negatively impact the timing characteristics in a circuit as they give rise to delay defects. In addition, the impact of these issues depends on the input test vectors provided during the scan-based test. In this thesis work, we propose methods to deal with the delay-related failures using at-speed scan test techniques for path delay test.

In Chapter 2, we present a novel physical design aware pattern generation (PDAPG) method for path delay fault testing. PDAPG method focuses on identifying the input patterns that can capture worst-case path delay on critical paths. The path delay is measured in the combined presence of physical design issues such as multi-aggressor crosstalk, power supply noise and ground bounce. As technology shrinks, the spacing between adjacent interconnect keeps decreasing, which increases the overall contribution of the coupling capacitances to the total interconnect capacitance. Also, gate noise sensitivity increases due to supply voltage scaling and limited scaling of the voltage threshold. As a result, crosstalk noise and supply noise play a greater role in sub-100nm technologies and creates signal integrity issues. Therefore, it is vital to consider both effects during design validation and the path delay test to ensure the performance and reliability of the chip.

PDAPG method is implemented on ITC'99 benchmark circuits and the results were shown by pattern comparison and path delay measurement. The basic principle behind this method is: all the aggressor nets closer to the critical path are backtraced till the relevant control input bits are found and then they are filled accordingly with different transition (rise, fall, stable 0, stable 1) signals. Experimental results demonstrate that our method is better in choosing the effective patterns, that can increase the impact of crosstalk noise, from the subset of all possible patterns to identify a worst-case path delay pattern. Although, we used a single robust critical path as our initial critical path repository, our method can be applied to any number of critical paths for efficiently identifying the high-quality input test patterns. The results suggest that the existing ATPG test methods have to be refined to incorporate the impact of physical design issues.

In Chapter 3, we propose an ATPG method that targets path delay fault by considering the impact of crosstalk noise. This work is the continuation of chapter 2, which is limited due to higher computational time, as the pattern identification method is based on SPICE simulations. Sometimes, SPICE-based simulation can be exhaustive for bigger circuits. Hence, the new method eliminates the exhaustive SPICE simulation and it is equally good for any sized circuits. The basic principle behind this method is: all the aggressor nets closer to the critical path are constrained depending on the victim net signal transition. Our method is implemented on ITC'99 benchmark circuits and the results were compared with SPICE simulation. With this method, we also show the effectiveness in computational time and pattern quality.

Experimental results demonstrate that the proposed method is fast even after considering all the aggressor nets neighboring the functionally testable critical paths. This method reduces the very time-consuming validation phase. The generated patterns can potentially be used for speed binning to replace the functional patterns if applied to a proper set of critical paths. As future work, we plan to extend this flow to add the impacts of other signal integrity issues such as supply noise during pattern generation.

In Chapter 4, we propose a delay probability metric for identifying a worst-case path delay pattern in the combined presence of process variation and supply noise. This metric can detect the most effective pattern from the set of all input patterns and can be employed with the existing ATPG path delay fault test.

The basic principle behind this method is: All the input patterns are ranked based on their mean delay difference and the area of the delay probability distribution. Among them, the pattern giving worst-case path delay is identified. This pattern can be utilized to capture the delay defects during IC test phase. Our experimental results on ITC'99 benchmark circuits suggests that the existing pattern generation methods need to be improved by incorporating the impacts of process variations and supply noise.

Future works

This thesis work gives a number of exciting research directions. The application of our work can bring tremendous improvements to the IC test quality by ensuring better defect coverage and for an increased manufacturing yield during speed binning of IC chips. Here, we summarize some extensions to this work that are relevant for DFT and defect diagnosis.

Our work has covered the analysis of path delay variations induced by crosstalk noise, power supply noise, ground bounce and process variations, which are the major industrial concerns. We have developed constrained ATPG method by improving the existing classical ATPG method. Crosstalk noise issues are only considered in this method, due to the complexity in developing and modeling power supply noise, ground bounce and process variations effects to ATPG tool. Our method can be further developed to add the impacts of power supply noise, ground bounce and process variations.

4

 4 Path delay variations due to the combined impact of Xtalk noise, PSN and GB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Path delay variation of buffer gate circuit . . . . . . . . . . . . . . . . . . . 2.6 Verilog circuit for Path delay test in TetraMAX . . . . . . . . . . . . . . . 2.7 Physical design aware pattern generation method . . . . . . . . . . . . . . 2.8 Identification of Multi-aggressors . . . . . . . . . . . . . . . . . . . . . . . 2.9 Victim-Aggressor net sketch from the layout . . . . . . . . . . . . . . . . . 2.10 Aggressor net (An) and victim net (Vn) is horizontally located (a) both with equal length (H1) (b) Vn > An (H2) (c) Vn < An (H3) (d) Vn, An in parallel, but with fringe capacitance (H4) (e) distant apart between the nets, but with fringe capacitance (H5) (f) in the same X plane (H6) . . . . 2.11 Aggressor net (An) and victim net (Vn) is vertically located (a) both with equal length (V1) (b) Vn > An (V2) (c) Vn < An (V3) (d) Vn, An in parallel, but with fringe capacitance (V4) (e) distant apart between the nets, but with fringe capacitance (V5) (f) in the same Y plane (V6) . . . . 2.12 X-filling by backtrace approach . . . . . . . . . . . . . . . . . . . . . . . . 2.13 Path delay fault testing with LOC . . . . . . . . . . . . . . . . . . . . . . . 3.1 (a) s27 benchmark circuit-under-test (b) 3-pi network model for interconnects 3.2 Layout sketch of s27 circuit . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Layout of s27 circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Path delay fault testing in TetraMAX . . . . . . . . . . . . . . . . . . . . . 3.5 Crosstalk-aware pattern generation method . . . . . . . . . . . . . . . . . . 3.6 Constrained ATPG flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Aggressor nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Aggressor net ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii 3.9 Constrained ATPG method . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 State diagram of constrained ATPG . . . . . . . . . . . . . . . . . . . . . . 3.11 (a) Waveform of Xtalk-ATPG pattern (b) Waveform of constrained ATPG pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Path delay variation plot of a victim path . . . . . . . . . . . . . . . . . . 3.13 Comparison of 2 methods in terms of path delay variation . . . . . . . . . 3.14 Comparison of 2 methods in terms of computational time . . . . . . . . . . 4.1 Different corner cases for process variations . . . . . . . . . . . . . . . . . . 4.2 (a) s27 benchmark circuit-under-test (b) 3-pi network model for interconnects (c) CMOS model for NOT gate . . . . . . . . . . . . . . . . . . . . . 4.3 Path delay estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Delay Probability distribution of an input pattern . . . . . . . . . . . . . . 4.5 SPICE circuit under the impact of process variations and supply noise . . . 4.6 Tolerance range of circuit parameters . . . . . . . . . . . . . . . . . . . . . 4.7 Flow of input pattern ranking method . . . . . . . . . . . . . . . . . . . . 4.8 Identification of worst-case path delay pattern under PV . . . . . . . . . . 4.9 Identification of worst-case path delay pattern under SN . . . . . . . . . . 4.10 Identification of worst-case delay pattern under PV and SN . . . . . . . . .

3. 1

 1 Path delay variation due to the impact of crosstalk . . . . . . . . . . . . . 3.2 Pattern comparison and delay variation . . . . . . . . . . . . . . . . . . . . 3.3 Functionality of ITC'99 Benchmark circuits [1] . . . . . . . . . . . . . . . . 3.4 Circuit description and experimental results for ITC'99 Benchmark circuits 3.5 b06 input patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Input pattern comparison results of ITC'99 Benchmark circuits . . . . . . 3.7 Aggressor net ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Aggressor net transition and delay measurement . . . . . . . . . . . . . . . 3.9 Pattern comparison and Path delay variation . . . . . . . . . . . . . . . . . 3.10 Circuit description and experimental results on ITC'99 Benchmark circuits 4.1 Path delay variation due to the impact of process variations . . . . . . . . 4.2 Pattern comparison and delay variation . . . . . . . . . . . . . . . . . . . . 4.3 Ranking method patterns under the impact of PV . . . . . . . . . . . . . . 4.4 Ranking method patterns under the impact of SN . . . . . . . . . . . . . . 4.5 Ranking method patterns under the impact of PV and SN . . . . . . . . . 4.6 Input pattern comparison results of ITC'99 Benchmark circuits . . . . . . 4.7 Results of ITC'99 Benchmark circuits . . . . . . . . . . . . . . . . . . . . . x

Figure 1 :

 1 Figure 1: Thesis outline

Chapter 5

 5 includes concluding remarks of this thesis work and future research direc-. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Challenges in Nanoscale Technologies . . . . . . . . . . . . . . 1.2.1 Crosstalk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Power Supply Noise . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Process Variations . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Different Types of Manufacturing tests . . . . . . . . . . . . . . 1.3.2 Structural Fault models . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Fault Categories . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.4 Automatic Test Pattern Generation . . . . . . . . . . . . . . . 1.4 DFT Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Scan Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Different ATPG Modes . . . . . . . . . . . . . . . . . . . . . . 1.4.3 At-speed Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.4 At-Speed Delay Test Challenges . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Principle behind testing chips

•

  Stuck-open and Stuck-short faults A CMOS transistor is considered as an ideal switch. Stuck-open and stuck-short faults model the switch being permanently in either the open or the shorted state. And they assume just one transistor to be stuck-open or stuck short.The effect of a stuck-open fault is a floating state at the output of the faulty logic gate. It can be detected in a similar

  Figure 1.3, a basic scan flip-flop is a combination of a D flip-flop with a multiplexer placed at the D input; the multiplexer is controlled by a new signal called scan-enable (SE).

Figure 1 . 3 :Figure 1 . 4 :

 1314 Figure 1.3: A scan flip-flop

Figure 1 . 5 :Figure 1 . 6 :

 1516 Figure 1.5: At-speed pattern generation using launch-off capture

Figure 2 .

 2 Figure 2.1 shows the buffer gate circuit developed in SPICE for analyzing the individual and combined impact of crosstalk, PSN and GB on path delay variations. This circuit con-

Figure 2 . 2 :

 22 Figure 2.2: Path delay variations due to Xtalk noise

Figure 2 .

 2 Figure 2.2 refers to the variation in path delay due to the capacitive coupling between the aggressor and victim interconnects for an early and lag in arrival times at {Ip2}. The delay is plotted as a function of measured maximum Xtalk noise for the all the input patterns and varying arrival times.

2 )

 2 Opposite direction input signal transition leads to worst-case path delay in a circuit. 3) Also, same direction signal transition may or may not lead to either slowdown or speedup depending on the value of the crosscoupling capacitances between the two interconnecting nets.

Figure 2 . 3 :

 23 Figure 2.3: Path delay variations due to the combined impact of Xtalk noise and PSN

  Figure 2.4 refers to path delay variations with respect to 1) input pattern transitions, 2) arrival time, 3) capacitive coupling between the interconnects 4) supply voltage variation (maximum PSN) at the gate supply inputs and 5) variation in the ground network voltage (maximum GB) at each of the gates. The plot in the figure has become much more random with many corners due to the addition of GB.

Figure 2 . 4 :

 24 Figure 2.4: Path delay variations due to the combined impact of Xtalk noise, PSN and GB

Figure 2 . 5 :

 25 Figure 2.5: Path delay variation of buffer gate circuit

Figure 2 . 6 :

 26 Figure 2.6: Verilog circuit for Path delay test in TetraMAX

Figure 2 . 7 :

 27 Figure 2.7: Physical design aware pattern generation method

Figure 2 . 8 :Figure 2 . 9 :

 2829 Figure 2.8: Identification of Multi-aggressors

Algorithm 2 :Figure 2 . 10 :

 2210 Figure 2.11. Subsequently, cross-coupling capacitance is measured, the steps are repeated

Figure 2 . 11 :

 211 Figure 2.11: Aggressor net (An) and victim net (Vn) is vertically located (a) both with equal length (V1) (b) Vn > An (V2) (c) Vn < An (V3) (d) Vn, An in parallel, but with fringe capacitance (V4) (e) distant apart between the nets, but with fringe capacitance (V5) (f) in the same Y plane (V6)

2 3 = 8 X

 38 -filled pattern combinations to test for worst-case path delay under the impact of crosstalk noise since they control the inputs through multi-aggressor nets. By our approach, we show a reduction of 87.50% in pattern count which consequently lowers the testing time of a path delay fault. We adopted the launch-off-capture (LOC) scheme for the scan-based path delay fault test in the presence of multi-aggressor crosstalk noise. The structural representation of a design under test is shown in Figure2.13. The scan chain with the scan input and scan output ports are shown in dotted lines with scan flip-flops between the combinational the combinational logic blocks between the sequential elements

Figure 2 . 13 :

 213 Figure 2.13: Path delay fault testing with LOC

( 3

 3 paths), ATPG undetected (1 path) and ATPG detected (4 paths) based on their path delay fault class. Refer chapter 1, fault category subsection for more details. The ATPG detected paths were further analyzed for robust (3 paths) and non-robust (1 path) paths.

3 . 3 3 . 4 3 . 5

 333435 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Prior Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Contributions and Chapter Organization . . . . . . . . . . . . Motivational Experiments . . . . . . . . . . . . . . . . . . . . . 3.4.1 Path Delay Analysis . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Path Delay Fault Testing . . . . . . . . . . . . . . . . . . . . . 3.4.3 Comparison of Vector Pairs . . . . . . . . . . . . . . . . . . . . Crosstalk-Aware Test Pattern Generation Method . . . . . . 3.5.1 Xtalk-ATPG Flow for Pattern Generation . . . . . . . . . . . . 3.5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 3.6 Constrained ATPG (C atpg ) Method . . . . . . . . . . . . . . . . 3.6.1 C atpg Flow for Pattern Generation . . . . . . . . . . . . . . . . 3.6.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 3 .Figure 3 . 1 :

 331 Figure 3.1(a) depicts s27 circuit with 10 gates, 3 D-type flip-flops, 4 inputs and a single output. The circuit is synthesized, DFT scan-chains [53] inserted and circuit netlist with 7 functional standard cells and 3 scan-out D Flip-Flops are generated. This facilitates one-to-one comparison of the simulation results from path delay analysis and path delay fault testing (explained in section 2.4.2). Placement and routing of the circuit netlist are then performed to extract the parasitic parameters (in gates and interconnects) from the layout [108]. Interconnect parasitic parameters consists of resistances (R1, R2, R3) and ground coupling capacitances (C g1 , C g2 , C g3 , C g4 ) as shown in Figure 3.1(b). Parasitic

Figure 3 .Figure 3 . 2 :

 332 Figure 3.2: Layout sketch of s27 circuit

Figure 3 .

 3 Figure 3.3 is derived from the actual circuit layout of s27 circuit.

Figure 3 . 3 :

 33 Figure 3.3: Layout of s27 circuit

Figure 3 . 4 :

 34 Figure 3.4: Path delay fault testing in TetraMAX

Figure 3 . 5 :

 35 Figure 3.5: Crosstalk-aware pattern generation method

Figure 3 . 7 :Figure 3 . 8 :

 3738 Figure 3.7: Aggressor nets

Figure 3 . 9 :

 39 Figure 3.9: Constrained ATPG method

Figure 3 . 10 :

 310 Figure 3.10: State diagram of constrained ATPG

Figure 3 . 11 :

 311 Figure 3.11: (a) Waveform of Xtalk-ATPG pattern (b) Waveform of constrained ATPG pattern

Figure 3 . 12 :

 312 Figure 3.12: Path delay variation plot of a victim path

4 .

 4 Column 5-6 depict the path delay variation and computational time for producing the patterns by Xtalk-ATPG method (selective SPICE simulation). We haven't shown some results on the Xtalk-ATPG method in column 5, as the simulation of a large sized circuit takes days to complete. Similarly, in column 7-8, we show the results obtained after applying C atpg ATPG flow on pattern generation. The path delay difference (δ d ) and the computational time difference (δ t ) obtained after comparing the two methods are shown in subsequent columns and also represented graphically in Figure3.13 and Figure3.14. The positive and negative notations in column 9 and 10, express the benefit and the relaxation margins, respectively between both methods. The smaller circuit consumes more time for pattern generation as it is proportional to the total number of aggressors constrained and patterns generated each time. C atpg method indicates that, with a small relaxation in the path delay, we gain a very high margin in computational time.

Figure 3 . 13 :

 313 Figure 3.13: Comparison of 2 methods in terms of path delay variation

Figure 3 . 14 :

 314 Figure 3.14: Comparison of 2 methods in terms of computational time

Figure 4 . 1 :

 41 Figure 4.1: Different corner cases for process variations

An

  ISCAS89 benchmark circuit s27, is developed in SPICE to analyse the individual impact of PV on a circuit path. The schematic is shown in Figure. 4.2(a) with its magnified view in Figure. 4.2(b) and 4.2(c). This circuit is similar to the one shown in section 3.4, the only difference is that crosstalk noise is ignored and PV parameters are only considered. The SPICE level circuit includes the gate variation parameters such as Vthn (threshold voltage in nMOS), Vthp (threshold voltage in pMOS), oxide thickness (tox) and variations in the CMOS gate length (Lg) and gate width (Wg), as well as, interconnect variation parameters such as resistances (R1, R2, R3) and ground coupling capacitances (Cg1, Cg2, Cg3, Cg4). Victim path we examine is highlighted in Fig.4.2(a). As there are many variation parameters, along with varying signal transitions and with difference in signal arrival times, the path delay alters to a greater extend. The nominal power supply voltage, ground reference voltage and switching frequency of 1V, 0V and 1GHz, respectively are used in this experiment. Path delay variations are observed at the target output FF3/D with the trigger input at the start of combinatorial victim path FF2/Q, refer Fig.4.2(a). All the possible vector pair signal transitions are

4 . 3 .Figure 4 . 3 :

 4343 Figure 4.3: Path delay estimation

Fig. 4 .

 4 [START_REF] Moretti | What Is Not Testable Is Not Fixable[END_REF] illustrates the probability density distribution of an input pattern under process variation and supply noise. Assuming that for a known design, a worst-case path delay. Their corresponding metrics will indicate the input pattern to be the most effective for capturing path delay defects under PV and SN conditions. Three different cases are explained below to show the individual and combined impact of PV and SN.

Figure 4 . 7 :

 47 Figure 4.7: Flow of input pattern ranking method

Figure 4 . 7 .

 47 Figure 4.7. The entire flow are described in four different steps: (1) Pattern generation, (2) Path delay estimation, (3) Delay probability distribution, and (4) Input pattern ranking.

4. 8

 8 depicts the probability density distribution function of all the input patterns under PV.

Figure 4 . 8 :

 48 Figure 4.8: Identification of worst-case path delay pattern under PV

Fig. 4 .

 4 Fig. 4.9 depicts the probability density distribution function of all the input patterns under SN.

Figure 4 . 9 :

 49 Figure 4.9: Identification of worst-case path delay pattern under SN

Fig. 4 .

 4 10 depicts the probability density distribution function of all the input patterns under PV and SN.

Figure 4 . 10 :

 410 Figure 4.10: Identification of worst-case delay pattern under PV and SN

106 5. 2

 1062 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

6 -

 6 clock 0.5 [remove_from_collection [all_inputs] {clock}] set_output_delay -clock clock 0.5 [all_outputs] set_false_path -from [all_inputs] -to [all_outputs] write_sdc b01.sdc write_delay_paths -max_paths 1000 -slack 20 -clock clock b01_delaypaths.txt exit Placement and Routing using Cadence Encounter P&R tool 0.9 -width_left 1.8 -width_bottom 1.8 -width_top 1.8 -spacing_top 0.9 -layer_bottom M1 -stacked_via_top_layer M7 -width_right 1.8 -around core -jog_distance 0.42 -offset_bottom 0.6 -layer_top M1 -threshold 0.42 -offset_left 0.spacing_right 0.9 -spacing_left 0.9 -offset_right 0.6 -offset_top 0.6 -layer_right M2 -nets gnd vdd -stacked_via_bottom_layer M1 -layer_left M2 addStripe -block_ring_top_layer_limit M3 -max_same_layer_jog_length 0.84 -padcore _ring_bottom_layer_limit M1 -set_to_set_distance 100 -stacked_via_top_layer M7 -padcore_ring_top_layer_limit M3 -spacing 0.42 -merge_stripes_value 0.42 -layer M2 -block_ring_bottom_layer_limit M1 -width 0.42 -nets gnd vddgds -mapFile streamOut.map -libName DesignLib -units 1000 -mode ALL summaryReport -outdir summaryReport extractRC rcOut -setload b01.setload rcOut -setres b01.setres rcOut -spf b01.spf rcOut -spef b01.spef saveFPlan ./b01.fp savePlace ./b01.place.gz saveNetlist b01.v global dbgLefDefOutVersion set dbgLefDefOutVersion 5.5 defOut -floorplan -netlist -routing b01.def set dbgLefDefOutVersion 5.5 streamOut b01.gds -mapFile streamOut.map -libName DesignLib -stripes 1 -units 1000 -mode ALL summaryReport -outdir Snapshot saveDesign ./b01.enc createSnapshot -dir Snapshot -name b01 -overwrite exit Pattern generation using Synopsys TetraMAX ATPG tool set_messages -log tmax.log -DT write_patterns b01_pat_new.stil -internal -format STIL -unified_stil_flow -replace write_testbench -input b01_pat_new.stil -output path_pat_serial_tb -parameterserial -replace -log path_pat_serial_tb.log exit

1

  Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv 1.1 Principle behind testing chips . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 General ATPG Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 A scan flip-flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4 An example of scan-chains inserted design . . . . . . . . . . . . . . . . . . 1.5 At-speed pattern generation using launch-off capture . . . . . . . . . . . . 1.6 At-speed pattern generation using launch-off shift . . . . . . . . . . . . . . 1.7 At nanometer process nodes, parasitic effects increase . . . . . . . . . . . . 2.1 Buffer gate circuit for path delay analysis . . . . . . . . . . . . . . . . . . . 2.2 Path delay variations due to Xtalk noise . . . . . . . . . . . . . . . . . . . 2.3 Path delay variations due to the combined impact of Xtalk noise and PSN 2.

  2.1 Path delay variations for different input patterns (Xtalk) . . . . . . . . . . 2.2 Path delay variations for different input patterns (Xtalk+PSN) . . . . . . . 2.3 Path delay variations for different input patterns (Xtalk+PSN+GB) . . . . 2.4 Worst-case path delays for the combined impact of Xtalk, PSN and GB . . 2.5 Input Pattern Comparison and Path Delay Variation . . . . . . . . . . . . 2.6 Victim nets and aggressor nets . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Victim nets and aggressor nets . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Functionality of ITC'99 Benchmark circuits [1] . . . . . . . . . . . . . . . . 2.9 Circuit description and Path delay variation results for ITC'99 Benchmark circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Input pattern comparison results of ITC'99 Benchmark circuits . . . . . .

drop Coupling capacitance RC delay Gate delay Figure

  are becoming more and more important to circuit design and test. The test power consumption, supply voltage noise, crosstalk noise caused by signal coupling effect, and hot spots caused by nonuniform on-chip temperature will significantly impact yield and reliability. As shown in Figure1.7 from[START_REF] Bell | Growing Challenges in Nanometer Timing Analysis[END_REF], with shrinking technology node, the percent-which reduce the noise immunity of the design and expose it to signal integrity issues. For example, a poor power planning or missing power via's can incur on-chip power droop for some test vectors. The power droop can impact a gate(s) on a critical path and it may cause timing failure. This failure may only be excited with certain test vectors as inputs. If the corresponding test vector is not included in the test pattern set, the failure becomes an escape and cannot be reproduced during diagnosis with the current test pattern set. Current automatic test pattern generation (ATPG) tools are not aware of the switching distribution on the layout and the pattern induced noises. There are escapes and "No Problem Found" (NPF) parts returned by customers, which have passed the tests using the layout-unaware test patterns generated by ATPG

	100% IR Chapter 2
	80%
	60%
	40%
	20%
	0%

age of delay caused by coupling effect between signal lines (crosstalk noise) and IR-drop on power and ground lines (power supply noise) is taking a larger portion. Power supply noise and crosstalk noise are becoming two important noises that impact circuits' timing integrity. The lower supply rails in today's IC's mean much less immunity from signal integrity problems that tie directly into power integrity. Supply voltages on many high-end IC's are now down to 1V and below, leading to decreasing margins for voltage fluctuation. Simultaneously, switching noise can cause fluctuations in the ground voltage level, leading to difficult-to-isolate signal-integrity problems and timing issues. Power, timing, and signal integrity effects are all interdependent at 90-nanometers (nm) and below. 1.7: At nanometer process nodes, parasitic effects increase Timing failures are often the result of a combination of weak points in a design and silicon abnormalities, tools. Thus, high-quality test patterns are imperative which can be used to capture noiseinduced delay problems during production test and identify noise-related failures during diagnosis. Test vector (pattern) generation considering the noise effect, mainly supply noise, crosstalk noise and process variations will be the focus of this thesis work.

Path Delay Test in the Presence of Multi-Aggressor Crosstalk, Power Supply Noise and Ground Bounce Contents 2

.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Prior Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Contributions and Chapter Organization . . . . . . . . . . . . 27 2.4 Motivational Experiments . . . . . . . . . . . . . . . . . . . . . 28 2.4.1 Path Delay Analysis . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.2 Path Delay Fault Testing . . . . . . . . . . . . . . . . . . . . . 35 2.4.3 Comparison of input patterns . . . . . . . . . . . . . . . . . . . 36 2.5 Physical Design Aware Pattern Generation Method . . . . . 36 2.5.1 PDAPG Flow for Pattern Generation . . . . . . . . . . . . . . 36 2.5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 49 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.1 Introduction

With technology scaling, the varying impacts of physical design (PD) issues have become a major challenge in IC's. These PD may issues create undesired effects such as multi-aggressor crosstalk noise, power supply noise and ground bounce. PD issues are the processes that induce additional delays in any circuit path. Their effects cause considerable path delay variations, thereby degrading the circuit performance. Path delay test patterns generated by timing-aware Automatic Test Pattern Generation (ATPG) tools are commercially utilized to determine faults or errors caused by path delay variations. As these tools are not built to account for PD issues, identifying proper test patterns to capture the worst-case path delay becomes difficult. Thus, by applying the existing path delay test techniques, might not necessarily identify the right set of test patterns.

Table 2 .

 2

	1: Path delay variations for different input patterns (Xtalk)
	{Ip1 Ip2} Arrival time Delay variation Delay impact
		-200ps	-2.84%	slowdown
	{10 10}	0ps	+2.07%	speedup
		+200ps	-2.17%	slowdown
		-200ps	-1.72%	slowdown
	{10 01}	0ps	-5.07%	slowdown
		+200ps	-1.69%	slowdown
		-200ps	-3.64%	slowdown
	{01 10}	0ps	-7.60%	slowdown
		+200ps	-3.28%	slowdown
		-200ps	-3.64%	slowdown
	{01 01}	0ps	+3.59%	speedup
		+200ps	-3.72%	slowdown
	may increase or decrease.

Table 2 .

 2

	2: Path delay variations for different input patterns (Xtalk+PSN)
	{Ip1 Ip2}	Arrival time	{Xtalk}{PSN}	Delay variation
	{10 10}			upto -17%
	{10 01} {01 10}	{-200ps 0ps 200ps} {0-2fF}{0.9V 1V 1.1V}	upto -20% upto -26%
	{01 01}			upto -15%

Path delay variations are listed in Table

2

.2. Xtalk and PSN values were varied as shown in column 3 along with the varying input patterns in column 1 and input arrival times in column 2. As the combinations of all possible permutations of Xtalk noise, PSN distribution, input patterns, arrival times results in a quite large data set, so only the maximum values are shown in the table. From the simulation results, the worst-case delay is observed with the input pattern {01 10} for the same input arrival time {0ps} and for PSN of {0.9V 0.9V 1.1V 0.9V} at {Vdd1 Vdd2 Vdd3 Vdd4}. This is due to the voltage level difference at each gates affecting the drive strength of the gates in the succeeding stages

Table 2 .

 2

3 lists the path delay variations for different input patterns. Similarly, as in

Table 2 . 3 :

 23 Path delay variations for different input patterns (Xtalk+PSN+GB) , the combinations of Xtalk, PSN, GB, input patterns and arrival time values results in a large data set and we have chosen only to show worst-case delays in the table.

	{Ip1 Ip2}	Arrival time	{Xtalk}{PSN}{GB}	Delay variation
	{10 10}			upto -32%
	{10 01} {01 10}	{-200ps 0ps 200ps}	{0-2fF}{0.9V 1V 1.1V} {0V 0.1V}	upto -34% upto -47%
	{01 01}			upto -38%

Table 2 . 4 :

 24 Worst-case path delays for the combined impact of Xtalk, PSN and GB

	{Input pattern}{Xtalk}	{PSN}	{GB}
		{0.9V 0.9V 1.1V 0.9V} {0.1V 0.1V 0V 0V}
		{0.9V 0.9V 1.1V 0.9V} {0.1V 0.1V 0V 0.1V}
	{01 10}{2fF}	{0.9V 0.9V 1.1V 1V} {0.9V 0.9V 1.1V 1V} {0.1V 0.1V 0V 0.1V} {0.1V 0.1V 0V 0V}
		{0.9V 0.9V 1.1V 1.1V} {0.1V 0.1V 0V 0V}
		{0.9V 0.9V 1.1V 1.1V} {0.1V 0.1V 0V 0.1V}

Table 2 . 5 :

 25 Input Pattern Comparison and Path Delay Variation

	ATPG pattern SPICE pattern Delay variation	Result
	{01 01}	{01 10}	-47.62%	Pattern mismatch

Table 2 . 6 :

 26 Victim nets and aggressor nets

	Victim nets	Aggressor nets
	Vn1, Vn2, Vn3, Vn4, Vn5 An1, An2, An3, An4, An5

Table 2 . 7 :

 27 Victim nets and aggressor nets

	Approach	Scan inputs Primary inputs #patterns
	Classical ATPG X0X1X1XX0	0X1	2 6 =64
	Backtrace filling X0x1X1Xx0	0x1	2 3 =8

Table 2 . 8 :

 28 Functionality of ITC'99 Benchmark circuits[1]

	Name Functionality	# of Gates # of FFs a
	b01	FSM that compares serial flows	49	5
	b02	FSM that recognizes BCD numbers	28	4
	b05	Elaborate the contents of a memory	998	33
	b06	Interrupt handler	56	8
	b09	Serial to serial converter	170	27
	b11	Scramble string with variable cipher	770	30
	b14	Viper processor (subset)	10098	215
	b22	A copy of b14 and two modified versions of b14 21772	611

a number of scan flip-flops.

Table 2 . 9 :

 29 Circuit description and Path delay variation results for ITC'99 Benchmark circuits

	Ckt #VP's	#X a	Time b	Delay variation c
	b01	5	50%	194s	35.45%
	b02	4	50%	155s	52.92%
	b05	34	99.21%	42214s	60.81%
	b06	8	75%	620s	47.46%
	b09	28	93.7%	8691s	43.20%
	b11	30	99.97%	74496s	67.66%
	b14	215	99.9% 1229874s	71.03%
	b22	613	99.99% 9936728s	79.34%
	Average	83.47%		57.23%

a % Reduction of X-bit input pattern count b Runtime for testing all patterns based on PDAPG method (in sec) c Path delay variation (%)

We demonstrate our PDAPG method based on b06 benchmark circuit. Eight victim paths were generated for b06 circuit netlist. These paths are classified as ATPG untestable

Table 2 . 10 :

 210 Input pattern comparison results of ITC'99 Benchmark circuits

	Ckt	Input	SI	PI
		X-bit pattern	x100 X	1100 1x
	b01	Random pattern	1100 0	1100 10
		PDAPG pattern	1100 X	1100 11
		X-bit pattern	xX00	0000 x
	b02	Random pattern	1000	0000 0
		PDAPG pattern	1X00	0000 1
		X-bit pattern	1111 0111 0100 Xxxx	00x0 x
	b05		11xx xxXX XXX0 1111 1X
		Random pattern	1111 0111 0100 1000	0010 0
			1110 0101 1010 1111 10
		PDAPG pattern	1111 0111 0101 X101	0010 01
			1111 00XX XXX0 1111 1X
		X-bit pattern	xx01 10XX	100x 1x
	b06	Random pattern	1001 1000	1001 10
		PDAPG pattern	1101 10XX	1001 11
		X-bit pattern	x100 1100 111X XxxX	0000 x
	b09		xX01 1001 1111
		Random pattern	1100 1100 1110 0010	0000 0
			0101 1001 1111
		PDAPG pattern	1100 1100 111X X01X	0000 1
			1X01 1001 1111
		X-bit pattern	xxXX XX10 11Xx xxX0	xxXX XXX0 00x
	b11		1100 1000 X111 xx
		Random pattern	1000 1010 1101 0110	0110 001
			1100 1000 0111 10
		PDAPG pattern	10XX XX10 11X1 11X0	10XX XXX0 001
			1100 1000 X111 11
		X-bit pattern	Xx11 X01x xX10 X001	1100 010x xxxx
	b14		x010 XX1x 1001 0X10	xxx0 1xxx
			XX00 1101 xxxx X01x	x001 10x
		Random pattern	1011 1011 0010 0001	1100 1010
			1010 1011 1001 0110	1000 1100
			1000 1101 1010 0010	0001 100
		PDAPG pattern	X111 X010 1X10 X001	1100 1110
			0010 XX11 1001 0X10	0010 1110
			XX00 1101 1110 X010	0001 100

  pattern from SPICE simulations. Simultaneously, we execute path delay fault test to generate a pattern that can capture path delay defect. This test utilizes the existing path delay fault model in the ATPG tool, TetraMAX ®[START_REF] Tetramax | Automatic Test Pattern Generation[END_REF]. Basically, our goal is to show that a standard ATPG tool may not be able to generate good patterns that can capture worst-case path delay in the presence of crosstalk. And our experimental results will show, such situation occurs simply because any commercial ATPG tool does not take

into account any physical design properties (i.e., parasitics for crosstalk, noise on power and ground lines, etc.) as they work on the logical level description (gate level netlist) of the circuit (i.e., VHDL or Verilog description) during pattern generation. The worst-case delay test patterns identified from SPICE simulations are compared with the patterns generated by the ATPG tool and their discrepancies are reported.

Table 3 .1:

 3 Path delay variation due to the impact of crosstalk

	Inputs Signal transitions Arrival time Delay variation Delay impact
	A
	B	Rise,	{-200ps,	-3.59%	speedup(-ve)
	C	Fall,	0ps,	to	/
	D	S0, S1	200ps}	+5.07%	slowdown(+ve)

Table 3 . 2 :

 32 Pattern comparison and delay variation SPICE ATPG

Table 3 . 3 :

 33 Functionality of ITC'99 Benchmark circuits [1] number of scan flip-flops, b number of victim paths.

	Name	Functionality	# of Gates	# of FFs a	# of VPs b
	b01	FSM that compares	49	5	5
		serial flows
	b02	FSM that recognizes	28	4	4
		BCD numbers
	b03	Resource arbiter	160	31	30
	b04	Compute min and max	737	66	66
	b05	Elaborate the	998	33	34
		contents of a memory
	b06	Interrupt handler	56	8	8
	b07	Count points on	441	41	41
		a straight line
	b08	Find inclusions in	183	21	21
		sequences of numbers
	b09	Serial to serial converter	170	27	28
	b10	Voting system	206	17	17
	b11	Scramble string	770	30	30
		with variable cipher
	b12	1-player game	1076	119	119
		(guess a sequence)
	b13	Interface to meteo sensors	362	45	45
	b14	Viper processor (subset)	10098	215	215
	b15	80386 processor (subset)	8922	415	415
	b17	Three copies of b15	32326	1311	1311
	b18	Two copies of b14	114621	2754	2754
		and two of b17
	b19	Two copies of b14	231320	5510	5510
		and two of b17
	b20	A copy of b14 and a	20226	429	429
		modified version of b14
	b21	Two copies of b14	20571	429	429
	b22	A copy of b14 and two	21772	611	611
		modified versions of b14

a

Table 3 . 4 :

 34 Circuit description and experimental results for ITC'99 Benchmark circuitsCkt #Anet a #X-bits b #X-bits filled c ∆ d

	X-bit	t e r	∆ f Xtalk

Table 3 . 5

 35

		: b06 input patterns
	Pattern	Scan FF input	Primary input
	type

Table 3 . 7 :

 37 Aggressor net ranking

	Victim net Aggressor net Rank
		An1	12
	Vn1	An2	20
		An3	6
		An4	13
	Vn2	NA*
		An5	2
		An6	1
		An7	10
		An8	16
		An9	18
	Vn3	An10	15
		An11	21
		An12	9
		An13	7
		An14	17
		An15	5
		An16	19
		An17	11
	Vn4	An18	4
		An19	3
		An20	14
		An21	8
	Vn5	An22	22
	NA* -No aggressor net for this victim net.

Table 3 . 10 :

 310 Circuit description and experimental results on ITC'99 Benchmark circuits

	Ckt	#X bits a	#X-bits filled bits b	#Anet c	Xtalk-ATPG d ∆ h v t i r	∆ j v	C e atpg	t k r	δ	f d	δ	g t
	b01	2	1	8	-0.01%	40s l	-0.01%	58s	0%	18s(-)
	b02	2	1	10	-0.11%	25s	-0.24%	46s	0.13%(+)	21s(-)
	b03	31	10	11	-2.06%	170342s	-2.87%	53s	0.81%(+)	170289s(+)
	b04	73	22	21	-28.75%	4218924564s	-21.50%	124s	7.25%(-)	4218924440s(+)
	b05	29	16	36	-3.34%	9133840s	-1.88%	278s	1.46%(-)	9133562s(+)
	b06	6	1	6	-0.17%	353s	-0.17%	30s	0%	323s(+)
	b07	35	20	41	-4.92%	818469s	-3.81%	201s	1.11%(-)	818268s(+)
	b08	26	14	22	-2.12%	2910945s	-1.73%	104s	0.39%(-)	2910841s(+)
	b09	10	3	13	-1.63%	1298s	-1.86%	68s	0.23%(+)	1230s(+)
	b10	22	10	27	-2.59%	185661s	-2.23%	188s	0.36%(-)	185473s(+)
	b11	21	13	22	-19.68%	5152358s	-14.14%	184s	5.54%(-)	5152174s(+)
	b12	106	8	16	-22.30%	2353725s	-20.07%	102s	2.23%(-)	2353623s(+)
	b13	47	7	9	-14.62%	54508s	-17.54%	52s	2.92%(+)	54456s(+)
	b14	183	71	65	-	1E+26s	-27.93%	493s	-	(+)
	b15	443	22	29	-	3E+11s	-17.66%	153s	-	(+)
	b17	1334	101	199	-	3E+35s	-35.27%	1880s	-	(+)
	b18	2776	133	224	-	4E+45s	-37.02%	4328s	-	(+)
	b19	5535	67	72	-	8E+25s	-42.15%	1512s	-	(+)
	b20	380	54	108	-	9E+21s	-38.32%	1272s	-	(+)
	b21	439	21	42	-	1E+12s	-36.97%	494s	-	(+)
	b22	572	126	200	-	4E+43s	-34.84%	1834s	-	(+)

Table 4 . 1 :

 41 Path delay variation due to the impact of process variations and different arrival times result in a large data set. Therefore, the minimum to maximum path delay variations obtained in comparison with nominal delay (i.e., without process variation) are only shown in column 4 of Table4.1. For a simple circuit like s27, the maximum path delay variation of +16.84% is obtained. This indicates the importance of considering the impact of process variations during the path delay fault testing. The vector pairs (V1,V2) to the flip-flops (FF1, FF2, FF3) identified after the SPICE simulations, their worst-case path delay (δ 1 ) are listed in column 2-5 of Table4.2.

	Inputs Signal transitions Arrival time Delay variation Delay impact
	A
	B	Rise,	{-200ps,	-12.30%	speedup(-ve)
	C	Fall,	0ps,	to	/
	D	S0, S1	200ps}	+16.84%	slowdown(+ve)
	SI
	pair signal transitions

Table 4 .

 4 3.4. Then, we tested with the existing path delay fault model in the ATPG tool, TetraMAX ® at 1GHz clock frequency. This model is widely used in industry for avoiding IC's with delay defects, caused by manufacturing process variations. the gates. Additionally, different gates on a path can suffer from different amounts of supply noise. Random process variations induce deviation on the transistor's and interconnect's dimensions and carrier mobility. In this work, we consider process variation on threshold voltage, V th , oxide thickness, t ox , transistor gate length, L g and width, W g

	The ATPG tool doesn't allow to include interconnect models and gate models during
	pattern generation, so it is not possible to analyze PV-induced delay faults. And our ex-
	periments will show that such situation occurs simply because any commercial ATPG tool
	does not take into account any physical design properties (such as parameter variations
	in the gates and in the interconnecting nets between them), as they work on logical level
	description of the circuit (i.e. VHDL or verilog description). Vector pairs were generated
	for path delay fault test for the victim path from FF2/Q to FF3/D. Column 6-9 of

2 lists, the ATPG tool generated vector pairs (V1, V2) for the flip-flop (FF1, FF2, FF3) inputs and the worst-case path delay (δ 2 ) measured in SPICE by their respective vector pairs. of

Table 4 . 3 :

 43 Ranking method patterns under the impact of PV

	Pattern Input vectors (V 1 V 2 )	Input	Under PV
	(P I j )	at {Ip1 Ip2 Ip3}	transition	µ a P Id	P b idn	Rank
	PI1	{10 10 10}	{Fall Fall Fall} 0.27ps 0.51	5
	PI2	{10 10 01}	{Fall Fall Rise} 4.67ps 0.60	4
	PI3	{10 01 10}	{Fall Rise Fall} 0.07ps 0.50	6
	PI4	{10 01 01}	{Fall Rise Rise} 9.47ps 0.70	3
	PI5	{01 10 10}	{Rise Fall Fall} 0.13ps 0.49	7
	PI6	{01 10 01}	{Rise Fall Rise} 9.47ps 0.70	2
	PI7	{01 01 10}	{Rise Rise Fall}	NA c	NA	NA
	PI8	{01 01 01}	{Rise Rise Rise} 35.9ps 0.94	1

a Difference between nominal delay (µ nom ) and delay mean of an input pattern µ(P i), b P identif ication i.e., exposed area of the probability density function, c No output transition at launch cycle, no no delay measured.

Table 4 . 4 :

 44 Ranking method patterns under the impact of SN

	Pattern Input vectors (V 1 V 2 )	Input		Under SN
	(P I j )	at {Ip1 Ip2 Ip3}	transition	µ a P Id	P b idn	Rank
	PI1	{10 10 10}	{Fall Fall Fall} 7.73ps 0.67	5
	PI2	{10 10 01}	{Fall Fall Rise} 7.97ps 0.58	7
	PI3	{10 01 10}	{Fall Rise Fall} 7.33ps 0.66	4
	PI4	{10 01 01}	{Fall Rise Rise} 17.6ps 0.81	2
	PI5	{01 10 10}	{Rise Fall Fall} 7.36ps 0.67	6
	PI6	{01 10 01}	{Rise Fall Rise} 17.3ps 0.80	3
	PI7	{01 01 10}	{Rise Rise Fall}	NA c	NA	NA
	PI8	{01 01 01}	{Rise Rise Rise} 48.2ps 0.98	1

a Difference between nominal delay (µ nom ) and delay mean of an input pattern µ(P i), b P identif ication i.e., exposed area of the probability density function, c No output transition at launch cycle, no no delay measured.

Table 4 . 5 :

 45 Ranking method patterns under the impact of PV and SN Difference between nominal delay (µ nom ) and delay mean of an input pattern µ(P i), b P identif ication i.e., exposed area of the probability density function, c No output transition at launch cycle, no no delay measured.

	Pattern Input vectors (V 1 V 2 )	Input	Under PV and SN
	(P I j )	at {Ip1 Ip2 Ip3}	transition	µ a P Id	P b idn	Rank
	PI1	{10 10 10}	{Fall Fall Fall} 1.12ps 0.68	4
	PI2	{10 10 01}	{Fall Fall Rise} 1.56ps 0.63	7
	PI3	{10 01 10}	{Fall Rise Fall} 1.22ps 0.67	5
	PI4	{10 01 01}	{Fall Rise Rise} 11.8ps 0.89	2
	PI5	{01 10 10}	{Rise Fall Fall}	1.5ps 0.69	6
	PI6	{01 10 01}	{Rise Fall Rise} 11.7ps 0.89	3
	PI7	{01 01 10}	{Rise Rise Fall}	NA c	NA	NA
	PI8	{01 01 01}	{Rise Rise Rise} 25.9ps 0.99	1

a

Table . 4

 . .6 and Table. 4.7 shows the summary of our experimental results. We utilized an ATPG tool for generating X-bit input patterns, as mentioned in the 1st row of each delay difference µ P Id (i.e., 121.4ps, 123ps, 136.2ps, 188.2ps, 147.5ps, 171.9ps, 182.67ps, 127.4ps, 152.3ps, 139.2ps, 166.2ps, 122.5ps, 111.4ps, 157.8ps, 143.6ps, 132.5ps) and also the P identif ication (i.e., 0.82, 0.94, 0.81, 0.90, 0.88, 0.85, 0.80, 0.89, 0.88, 0.91, 0.84, 0.96, 0.84, 0.81, 0.94, 0.93), and then ranked (i.e.,15, 13, 10, 1, 7, 3, 2, 12, 6, 9, 4, 14, 16, 5,

Table 4 . 7 :

 47 Results of ITC'99 Benchmark circuits Mean delay difference (between nominal delay and identified input pattern delay), b Exposed area under the curve, c Delay difference between two methods, d Runtime for testing all the patterns and finding a worst-case path delay pattern (PV + SN).

	Ckt	ATPG		Our method
	µ a P Id	P b idn	Rank	µ a P Id	P b idn	Rank % µ c P Id	tr(s) d
	b01 136.00ps 0.91	2	140.77ps 0.95	1	3.3%	2K
	b02 159.34ps 0.96	2	167.00ps 0.93	1	4.5%	3K
	b03 148.60ps 0.83 187 179.34ps 0.86	1	17.1%	31K
	b06 123.00ps 0.94	13	188.20ps 0.90	1	34.6%	7K
	b08 310.90ps 0.86 289 342.60ps 0.94	1	9.2%	41K
	b09 269.55ps 0.92	5	285.51ps 0.90	1	5.5%	33K
	b10 373.21ps 0.94 462 499.86ps 0.98	1	25.3%	19K
	b13 398.74ps 0.85	39	487.33ps 0.93	1	18.1%	72K

a

Acknowledgements

This PhD thesis is a part of the three-year research work that has been carried out in SYSMIC (TRAFIC) research group of the Laboratory of Informatics, Thank you very much for the trust and confidence that you have given to me. I would like to acknowledge the University of Montpellier and French National Centre for Scientific Research (CNRS) for providing the financial support of this PhD research.

List of Abbreviations

computational time in identifying a path delay pattern for testing.

Circuit netlist

Identification of aggressor nets

Sorting and ranking aggressor nets

Constraining aggressor nets

Pattern generation

Is pattern testable?

Yes

No

Yes

No

Vary transitions

Constrained all aggressors?

Crosstalk-aware pattern

Step 3

Step 1

Step 2

Selection of a victim path Placement and routing

C atpg Flow for Pattern Generation

The C atpg flow shown in Figure 3.6 is described in three stages: (1) identification of aggressor nets (to a victim path), (2) sorting and ranking aggressor nets (based on their impact), and (3) constraining aggressor nets and pattern generation (for a victim path).

C atpg method is a generic method and this method is presented on a sample circuit b08, an ITC'99 benchmark circuit. The relevance of the proposed flow shows a great promise to generate an effective worst-case path delay pattern similar to the patterns identified by the Xtalk-ATPG method mentioned in section 2.5. Even though, the latter method was

a scan flip-flops from 1 to 21 from the synthesized DFT scan chain structure, b by constrained ATPG method, c by Xtalk-ATPG method, d all the 22 aggressor nets to the victim path, e path delay variation.

The path delay variation (∆ v ) for the constrained ATPG and Xtalk-ATPG methods were computed using the equations below:

Introduction

Ongoing technology scaling significantly increases the delay defects in IC's. In previous chapters, we have examined the impacts of crosstalk noise, power supply noise and ground bounce that causes delay defects. In this chapter, we discuss about the impacts of the The combinations of all possible permutations of process variation parameters, vector

Comparison of Vector Pairs

In this subsection, we compare the vector pairs identified from SPICE simulation with the one generated by the ATPG tool and their mismatches are highlighted. This comparison is to show that input patterns generated by the testing tools have to be effective enough to accommodate the path delay variations due to PV's.

In Table 4.2, we can see a mismatch in the vector pairs at FF1 and FF2 between the SPICE and ATPG patterns. The path delay variation (∆ v ) in equation 4.1, is the mean delay difference between the worst-case delays obtained from SPICE (δ 1 ) and ATPG (δ 2 )

patterns. The ∆ v of 6.64% (slowdown impact on the victim path) listed in column 10, implies that a path delay fault test is not performed with a good pattern. This path delay is quite high for a small circuit like s27 and it may be even higher and at an unacceptable percentage in bigger circuits. Thus, we provide an evidence that a circuit may escape the test to detect PV-induced delay defect due to lower quality in the applied vector pair.

This indicates a serious notice in customizing the existing path delay fault testing method in ATPG. Therefore, our work emphasizes the need for refining ATPG tools and proposing novel methods to include good patterns that can be utilized for capturing PV-induced delay defects. For bigger circuits, there may exist many large set of test patterns. So, it is desirable to implement a method to include PV effects during pattern generation.

In the next section we formulate the problem of path delay estimation in the presence of PV's.

Problem formulation

In this section, we describe the problem that we address and propose our mathematical approach in identifying an input pattern that can capture the worst-case path delay under the impact of PV and SN. Initially, we estimate the dependent circuit parameters that affect the delay of a circuit path. Then, describe the proposed probabilistic metrics for ranking patterns based on their effectiveness. Finally, we describe our method of ranking patterns based on a delay probability metric.

Path Delay Estimation

In this subsection, we elaborate the proposed analytical method for computing the ranking order of input patterns. The problem of path delay test is a well-understood and widely investigated problem by the scientific community, in effectively identifying the test patterns for performance evaluation that would eventually lead to high-quality test patterns and that can lower delay defect escape rate. With technology scaling, increased circuit densities and faster switching circuits, identifying the highest quality patterns are getting even more challenging. Even more so when the impact of physical design issues and PV are taken into account. Due to the nature of the problem with many parameters that can cause a wide delay distribution, we exploit a probability based-approach to rank patterns based on their effectiveness in capturing the worst case delay under the impact of PV and SN.

Each input pattern triggers a given switching activity on the circuit and the victim (or paths that are critical) path under observation. As already shown in [START_REF] Todri | Uncorrelated Power Supply Noise and Ground Bounce Consideration for Test Pattern Generation[END_REF], critical paths can undergo drastic delay variation that can lead to slowdown and/or speedup impacts in a path. We expect that such delay variations will be even more pronounced when PV of transistors and interconnects are also included with SN.

Problem definition: We aim to identify the set of patterns that are the most effective in capturing the worst case path delay under the impact of PV and SN; based on the delay probability density function of each pattern.

Path delay on a circuit is computed by considering the delays of both interconnects and gates. Supply noise which exhibits itself as power (PSN) and ground (GB) voltage fluctuations can impact the operating regions of transistors, hence the delay behavior there is a predefined delay threshold with µ nom that represents the tolerable delay of the circuit.

Definition: We define the probability of identification, P identif ication that can analytically estimate the likeliness of a pattern j under PV and SN conditions to cause a path delay at each node i, δ path i larger than the allowed delay threshold, µ nom , and can be expressed as:

where µ max j of a pattern j is defined as:

Hence, for each pattern, the P identif ication j allows us to compute the exposed area of the probability density function beyond a delay threshold also as shown in Fig. Utilizing this metric, we further define the pattern ranking method that considers both the mean, µ P I j and probability of identification, P identif ication j of each pattern for classifying the patterns for inducing the worst path delay under PV and SN conditions.

The ranking metric, Rank P I j is defined as:

where α 1 and α 2 are weight coefficients between 0 to 1 that can be given for taking into account both the changes in mean, µ P I d and the identification metric P identif ication j , where µ P I d is expressed as:

The values for α 1 and α 2 can be chosen based on their priority during path delay testing i.e., either µ P I d or P identif ication j . We further utilize these probability metrics for ranking the patterns on a sample circuit to illustrate the effectiveness of the proposed ranking method. (i) estimate path delay (δ path i ), (ii) compute mean (µ P I j ) and standard deviation (σ P I j ) from the delay probability distribution of each input pattern (P I j ), and (iii) identify the worst-case path delay pattern (P identif ication j ) based on the ranking method. We utilize MATLAB to execute the mathematical computations of equations described in Section II. 4.6. Then, we filled only the relevant X-bits (indicated by small letter 'x') based on X-filling method [START_REF]Path Delay Test in the Presence of Multi-Aggressor Crosstalk, Power Supply Noise and Ground Bounce[END_REF]. based on the likeliness to obtain the worst path delay when process variation and supply noise variations are taken into account. The proposed method is practical to be embedded on the standard ATPG generation flow i.e., post-ATPG X-filling, which is also the focus of our future work.

Input Pattern Ranking Method

Summary

In this chapter, we proposed a delay probability metric for identifying a worst-case path delay pattern under the impact of process variation and supply noise. The presented probabilistic pattern ranking method aims at capturing delay defects during path delay test. Our experimental results on ITC'99 benchmark circuits suggests to improve the existing pattern generation methods by incorporating the impacts of PV and SN. As future research, we aim to implement the probabilistic method in X-filling pattern generation flow.

Experimental results on the benchmark circuits have demonstrated the efficiency of the proposed techniques. Furthermore, after integrating to the ATPG tool, our constrained ATPG method could save significant CPU runtime. It is capable of identifying worstcase path delay pattern for the biggest ITC'99 benchmark circuit, b22 with 21772 gates.

Anyways, we think this method should be further improved to be able to deal with circuits composed of billions of gates. This method still needs to be refined in terms of computational time (for generating patterns) and efficiency to deal with the real industrial circuits. In other words, the methods in this thesis still opens up a door to new and refined ATPG techniques.

Our procedures are still open to add more effects if necessary such as on-chip temperature variations, substrate coupling, etc. It is easy to add more effects to our proposed flow of ATPG:

(1) Model the new effect and map it to the parameter variant (i.e., gate or interconnect), where it impacts. For example, for crosstalk noise, we have mapped their variation to the interconnects.

(2) Combine all the new effects and sensitize the critical path for generating a worstcase path delay pattern.

Appendix A Circuit netlist creation using Cadence Encounter RC compiler

This RTL code converts a circuit behaviour description (in vhdl) to a circuit design implementation (to verilog). The code mentioned is for b01 circuit of ITC'99 benchmark