This paper presents a linear system formulation for evaluating full-chip electromigration (EM) risk in general (straight line, tree, and mesh) wiring topologies, considering stress-induced backflow of metal ions. The system of equations is based on stress gradients and mass displacements in wire segments as variables, and is formulated for efficient implementation in computer-aided design (CAD) tools for designing high-performance microprocessor chips involving large databases. Derived from a well-known hydrostatic stress model in tree interconnects (J. Appl. Phys., vol. 47, no. 4, p. 1203, 1976; IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 18, no. 5, p. 576, 1999; Microelectron. Reliab., vol. 39, no. 11, p. 1667, 1999), the system is readily modified for evaluating EM risk in mesh topologies. The authors demonstrated a significant increase in the predicted lifetime of a high-performance microprocessor with the application of the proposed method to filter out risk-free structures from subsequent statistical EM risk calculations.

High performance circuits are facing increasingly severe signal integrity problems due to crosstalk noise and crosstalk noise awareness has become an integral part of static timing analysis (STA). Existing crosstalk noise aware STA methods compute noise induced delay uncertainty on a net by net basis and in a pessimistic way, without considering the overlap bounds of the victim and aggressor timing windows and realistic delay impact on early and late signal arrival times. Since crosstalk induced delay on individual nets contribute cumulatively on data and clock paths, even small amounts of pessimism in computation can add up to produce several unrealistic timing violations. Unlike glitch noise analysis where noise often attenuates during propagation, quality of delay noise analysis is severely affected by any pessimism in noise estimation and can unnecessarily cost valuable silicon and design resources for fixing unreal violations. In this paper, we propose two temporal techniques to reduce pessimism in crosstalk noise aware STA. The first method, "effective delay noise", is a net based method where the exact overlap points of victim and aggressor timing windows are considered to obtain the part of delay noise that actually impacts early and late signal arrival times. The second method, "path based delay noise", is a path based method where the reduced arrival uncertainty of the nets of a given path are utilized for pessimism reduction. We also propose a novel "uncertainty propagation" technique as part of the second method, which results in an iteration free crosstalk noise aware STA of the path with significantly reduced pessimism. The two techniques are combined in a proposed methodology that is compatible with existing industrial static timing analyzers with very little computational overhead compared to the traditional noise aware STA and a significant improvement in eliminating unreal violations. The proposed techniques resulted in 77% reduction of worst case negative slack and 57% reduction in the number of failing paths in the setup analysis of a 90nm industrial design.

High-performance digital circuits are facing increasingly severe noise problems due to cross-coupled noise injection. Traditionally, noise analysis tools use the conservative assumption that all neighbors of a net can switch simultaneously, producing the worst-case noise. However, due to logic correlations in the circuit, this worst-case noise may not be realizable, resulting in a so-called false noise failure. Some techniques for computing logic correlations have been designed targeting static CMOS circuits. However high performance microprocessors commonly use domino logic for their ALU. The domino circuits have lower noise margins than static CMOS circuits and are more sensitive to coupled noise. Any unnecessary pessimism of the noise analysis tool results in large number of false noise violations and either requires additional extensive SPICE simulations or circuit over-design. Unfortunately false noise analysis developed for static CMOS circuits fails to compute many logic correlations in domino circuits. In this paper we propose a novel technique of computing logic correlations in domino circuits. It takes into account the fact that both pull up and pull down networks of a domino gate can be in non conducting state. The proposed technique generates additional logic correlations for such states of domino gates. In order to improve the capability of logic correlation derivation technique we combine the resolution method with recursive learning algorithm. The proposed technique is implemented in an industrial noise analysis tool and tested on high performance ALU blocks.

High-performance digital circuits are facing increasingly severe signal integrity problems due to crosstalk noise and therefore the state-of-the-art static timing analysis (STA) methods consider crosstalk-induced delay variation. Current noise-aware STA methods compute noise-induced delay uncertainty for each net independently and annotate appropriate delay changes of nets onto data paths and associated clock paths to determine timing violations. Since delay changes in individual nets contribute cumulatively to delay changes of paths, even small amounts of pessimism in noise computation of nets can add up to produce large timing violations for paths, which may be unrealistic. Unlike glitch noise analysis where noise often attenuates during propagation, quality of delay noise analysis is severely affected by any pessimism in noise estimation and can unnecessarily cost valuable silicon and design resources for fixing unreal violations. In this paper, we propose a method to reduce pessimism in noise-aware STA by considering signal correlations of all nets associated with an entire timing path simultaneously, in a path-based approach. We first present an exact algorithm based on the branch-and-bound technique and then extend it with several heuristic techniques so that very large industrial designs can be analyzed efficiently. These techniques, which are implemented in an industrial crosstalk noise analysis tool, show as much as 75% reduction in the computed path delay variations.

Gate sizing is a practical and a feasible crosstalk noise correction technique in the post route design stage, especially for block level sea-of-gates designs. The difficulty in gate sizing for noise reduction is that, by increasing a driver size, noise at the driver output is reduced, but noise injected by that driver on other nets is increased. This can create cyclical dependencies between nets in the circuit with noise violations. In this paper, we propose a fast and effective heuristic postroute gate-sizing algorithm that uses a graph representation of the noise dependencies between nodes. Our method utilizes gate sizing in both directions and works in linear time as a function of the number of gates. The effectiveness of the algorithm is shown on several industrial high-performance designs.

Signal integrity closure is one of the key challenges in deep submicron physical design. In this paper, we propose a physical design methodology which includes signal integrity management through crosstalk noise analysis and repair at multiple phases of the design so that a quick noise convergence can be achieved. The methodology addresses both functional and delay noise problems in the design and is targeted for block-, platform-, and chip-level physical design of system-on-chip designs. A number of case studies are presented to illustrate the effectiveness of the proposed methodology and to provide valuable insights useful for successful signal integrity management.

Gate sizing is a practical and a feasible crosstalk noise repair technique in the post route design stage, especially for block level sea-of-gates designs. The difficulty in gate sizing for noise reduction is that by increasing a driver size, noise at the driver output is reduced, but noise injected by that driver on other nets is increased. This can create cyclical dependencies between nets in the circuit with noise violations. In this paper, we propose a fast and effective heuristic post-route gate sizing algorithm that uses a graph representation of the noise dependencies between nodes. Our method utilizes gate sizing in both directions and works in linear time as a function of the number of gates. The effectiveness of the algorithm is shown on several industrial high performance designs.

Signal integrity closure is one of the key challenges in DSM (Deep- SubMicron) physical design. In this paper, we propose a physical design methodology which includes signal integrity management through noise analysis and repair at multiple phases of the design so that a quick noise convergence can be achieved. The methodology addresses both functional and delay noise problems in the design and is targeted for block, platform, and chip level physical design of SoC (System-On-Chip) designs. A number of case studies are presented to illustrate the effectiveness of the proposed methodology and to provide valuable insights useful for successful signal integrity management.

With the increase in current densities, electromigration has become a critical concern in high-performance designs. Typically, electromigration has involved the process of time-domain simulation of drivers and interconnect to obtain average, root mean square (r.m.s.), and peak current values for each wire segment. However, this approach cannot be applied to large problem sizes where hundreds of thousands of nets must be analyzed, each consisting of many thousands of RC elements. The authors propose a static electromigration analysis approach. They show that the charge transfer through wire segments of a net can be calculated directly by solving a system of linear equations, derived from the nodal formulation of the circuit, thereby eliminating the need for time domain simulation. The authors account for the different possible switching scenarios that give rise to unidirectional or bidirectional current by separating the charge transfer from the rising and falling transitions and also propose approaches for modeling multiple simultaneous switching drivers. They implemented the proposed static analysis approach in an industrial electromigration analysis tool that was used on a number of industrial circuits, including a large microprocessor.

In this paper, we present a new approach to model the impact of cross-coupling noise on interconnect delay. We introduce a new linear driver model that accurately models the noise pulse induced on a switching signal net due to cross-coupling capacitance. The proposed model effectively captures the nonlinear behavior of the victim-driver gate during its transition and has an average error below 8% whereas the traditional approach using a Thevenin model incurs an average error of 48%. The proposed linear driver model enables the use of linear superposition which allows the analysis of large interconnects and an efficient determination of the worst-case transition times of the aggressor nets. We proposed a new approach to determine the worst-case alignment of the aggressor net transitions with respect to the victim net transition, emphasizing the need to maximize not merely the delay of the interconnect alone but the combined delay of the interconnect and receiver gate. We show that in the presence of multiple aggressor nets, the worst case delay may occur when their noise peaks are not aligned, although the error incurred from aligning all peaks is small in practice. We then show that the worst-case alignment time of the combined noise pulse from all aggressors with respect to the victim transition is a nonlinear function of the receiver gate output loading, the victim transition time, and the noise pulsewidth and height. To efficiently compute the worst-case alignment time, we propose a new representation of the alignment such that it closely fits a linear function of the input variables. The worst-case alignment time is then computed for a gate using a precharacterization approach, requiring only eight sample points while maintaining a small error. The proposed methods were implemented in an industrial noise analysis tool called ClariNet. Results on industrial designs, including a large PPCmicroprocessor design, are presented to demonstrate the effectiveness of our approach.

Noise analysis has become a critical concern in advanced chip designs. Traditional methods suffer from two common issues. First, noise that is propagated through the driver of a net is combined with noise injected by capacitively coupled aggressor nets using linear summation. Since this ignores the non-linear behavior of the driver gate the noise that develops on a net can be significantly underestimated. We therefore propose a new linear model that accurately combines propagated and injected noise on a net and which maintains the efficiency of linear simulation. After the propagated and injected noise are correctly combined on a victim net, it is necessary to determine if the noise can result in a functional failure. This is the second issue that we discuss in this paper. Traditionally, noise failure criteria have been based on unity gain points of the DC or AC transfer curves. However, we will show that for digital designs, these approaches can result in a pessimistic analysis in some cases, while in other cases, they allow circuit operation that is extremely close to regions that are unstable and do not allow sufficient margin for error in the analysis. In this paper, we compare the effectiveness of the discussed noise failure criteria and also present a propagation based method, which is intended to overcome these drawbacks. The proposed methods were implemented in a noise analysis tool and we demonstrate results on industrial circuits.

Presents a new approach for the estimation and optimization of standby power dissipation in large MOS digital circuits. We introduce a new approach for accurate and efficient calculation of the average standby or leakage current in large digital circuits by introducing the concepts of "dominant leakage states" and the use of state probabilities. Combined with graph reduction techniques and simplified nonlinear simulation, the method achieves speedups of three to four orders of magnitude over exhaustive SPICE simulations while maintaining very good accuracy. The leakage current calculation is then utilized in a new leakage and performance optimization algorithm for circuits using dual V/sub t/ processes. The approach is the first to consider the assignment of both the V/sub t/ and the width of a transistor, simultaneously. The optimization approach uses incremental calculation of leakage and performance sensitivities and can take into account a partially defined circuit state constraint for the standby mode of the device.

In this paper, we present a new approach to model the impact of cross-coupling noise on interconnect delay. We introduce a new linear driver model that accurately models the noise pulse induced on a switching signal net due to cross coupling capacitance. The proposed model effectively captures the non-linear behavior of the victim driver gate during the transition and has an average error below 8% whereas the traditional approach using a Thevenin model incurs an average error of 48%. We also discuss the worst case alignment of the aggressor net transitions with respect to the victim net transition, emphasizing the need to maximize not merely the delay of the interconnect alone but the combined delay of the interconnect and receiver gate. We show that the worst case alignment of an aggressor net transition is a function of the receiver gate output loading, victim transition edge rate, and the noise pulse width and height and hence propose a pre-characterization approach to efficiently predict the worst-case alignment. The proposed methods were implemented in an industrial noise analysis tool called ClariNet. Results on industrial designs are presented to demonstrate the effectiveness of our approach.

Cross-coupled noise analysis has become a critical concern in VLSI design. Typically, noise analysis makes the assumption that all aggressing nets can simultaneously switch in the same direction. This creates a worst-case noise pulse on the victim net that often leads to false noise violations. In this paper, we present a new approach that uses logic implications to identify the maximum set of aggressor nets that can inject noise simultaneously under the logic constraints of the circuit. We propose an approach to efficiently generate logic implications from a transistor-level description and propagate them in the circuit using ROBDD representations of the DC-connected components and a newly proposed lateral propagation method. We then show that the problem of finding the worst case logically feasible noise can be represented as a maximum weighted independent set problem and show how to efficiently solve it. Initially, we restrict our discussion to zero-delay implications, which are valid for glitch-free circuits and then extend our approach to timed implications. The proposed approaches were implemented in an industrial noise analysis tool and results are shown for a number of industrial test cases. We demonstrate that a significant reduction in the number of noise failures can be obtained from considering the logic implications as proposed in this paper, underscoring the need for false-noise analysis.

Coupled noise analysis has become a critical issue for deep-submicron, high performance design. In this paper, we present, ClariNet, an industrial noise analysis tool, which was developed to efficiently analyze large, high performance processor designs. We present the overall approach and tool flow of ClariNet and discuss three critical large-processor design issues which have received limited discussion in the past. First, we present how the driver gates of a coupled interconnect network are represented with accurate linear models. Second, we show how to speed the analysis of large designs by using noise filters based on reduced interconnect representations and then pruning the nets coupled to a signal net. Third, we show how to incorporate logic and timing correlations into noise analysis to reduce its pessimism. We present the results from several industrial circuits, including a large high performance microprocessor design and a DSP design.

Static timing analysis has traditionally used the PERT method for identifying the critical path of a digital circuit. Due to the influence of the slope of a signal at a particular node on the subsequent path delay, an earlier signal with a signal slope greater than the slope of the later signal may result in a greater delay. Therefore, the traditional method for timing analysis may identify the incorrect critical path and report an optimistic delay for the circuit. We show that the circuit delay calculated using the traditional method is a discontinuous function with respect to transistor and gate sizes, posing a severe problem for circuit optimization methods. We propose a new timing analysis algorithm which resolves both these issues. The proposed algorithm selectively propagates multiple signals through each timing edge in cases where there exists ambiguity regarding which arriving signal represents the critical path. The algorithm for propagating the corresponding required times is also presented. We prove that the proposed algorithm identifies a circuit's true critical path, where the traditional timing analysis method may not. We also show that under this method circuit delay and node slack are continuous functions with respect to a circuit's transistor and gate sizes. In addition, we present a heuristic method which reduces the number of signals to be propagated at the expense of a slight loss in accuracy. Finally, we show how the proposed algorithm was efficiently implemented in an industrial static timing analysis and optimization tool, and present results for a number of industrial circuits. Our results show that the traditional timing analysis method underestimates the circuit delay by as much as 38%, while that the proposed method efficiently finds the correct circuit delay with only a slight increase in run time.

We present a new approach for estimation and optimization of the average stand-by power dissipation in large MOS digital circuits.To overcome the complexity of state dependence in average leakage estimation, we introduce the concept of "dominant leakage states" and use state probabilities.Our method achieves speed-ups of 3 to 4 orders of magnitude over exhaustive SPICE simulations while maintaining accuracies within 9% of SPICE.This accurate estimation is used in a new sensitivity-based leakage and performance optimization approach for circuits using dual V t processes.In tests on a variety of industrial circuits, this approach was able to obtain 81-100% of the performance achievable with all low V t transistors, but with 1/3 to 1/6 the stand-by current.

Power management is an increasing concern for processor design. In this paper, we presented an overview of traditional power simulation tools and discussed two emerging power management design technologies: power distribution integrity analysis and standby current measurement and optimization. We present methods for accurate peak current simulation, which is needed for power grid integrity analysis, and discuss the generation and compression of the simulation vectors. Also, static approaches for calculating an upper-bound on the maximum peak current are presented. Standby leakage current is state dependent and we present methods for calculating both the average and maximum leakage current. Finally, optimization methods for minimizing the leakage current by either assigning a standby state to the circuit or by using a dual-Vt process are discussed.

As the operating speed of digital circuits dramatically increases with the advance of VLSI technology, it is becoming more critical to ensure that the circuits are free from timing-related design errors. In a traditional static timing approach nonfunctional paths cannot be distinguished from functional ones since the functionality of a circuit is ignored. This often results in overestimation of circuit delay and can degrade the circuit performance. In today's design methodology where the use of automated logic synthesis and module-based design are popular, circuits with a very large number of nonfunctional (false) paths are common. This paper describes an efficient logic-level timing analysis approach that can provide an accurate delay estimate of a digital circuit which may have many long false paths. By using logic incompatibilities in a circuit as constraints for critical path search, the algorithm determines the longest sensitizable path without explicit path enumeration. Since the number of false paths that can be implicitly eliminated is potentially exponential to the number of path constraints, performance improvement is significant.

A unified approach for modeling objects which are imaged by thermal (infrared) and visual cameras is presented. The model supports the generation of both infrared (8 mu m-12 mu m wavelength) images and monochrome visual images under different viewing and ambient-scene conditions. A modified octree data structure is used for object modeling. The octree serves two different purposes: surface information encoded in boundary nodes and efficient tree-traversal algorithms facilitate the generation of monochrome visual images; and the compact volumetric representation facilitates simulation of heat flow in the object which gives rise to surface temperature variation, which in turn is used to synthesize the thermal image. The detailed object model allows for more accurate prediction of thermal and visual images of objects. It also predicts the values of discriminatory features used in classification. The model developed is designed to be used in a model-based vision system which uses a hypothesize-and-verify strategy to interpret thermal and visual images of scenes. Several blocks-world examples are presented to show typical images generated by the approach.>