As the feature size decreases in deep sub-micron designs, coupling capacitance becomes the dominant factor in total capacitance. The resulting crosstalk noise may be responsible for signal integrity issues and significant timing variation. Traditionally, static timing analysis tools have ignored cross coupling effects between wires altogether. Newer tools simply approximate the coupling capacitance by a 2X Miller factor in order to compute the worst case delay. The latter approach not only reduces delay calculation accuracy, but can also be shown to underestimate the delay in certain scenarios. This book describes accurate but conservative methods for computing delay variation due to coupling. Furthermore, most of these methods are computationally efficient enough to be employed in a static timing analysis tool for complex integrated digital circuits. To achieve accuracy, a more accurate computation of the Miller factor is derived. To achieve both computational efficiency and accuracy, a variety of mechanisms for pruning the search space are detailed, including:

-Spatial pruning - reducing aggressors to those in physical proximity, -Electrical pruning - reducing aggressors by electrical strength, -Temporal pruning - reducing aggressors using timing windows, -Functional pruning - reducing aggressors by Boolean functional analysis.

List of Figures List of Tables Preface 1: Introduction 1. Motivation 1.1 Process Trends 1.2 CMOS Circuitry 2. Background and Crosstalk Effects 2.1 Static Timing Analysis 2.2 Crosstalk Effects 2.3 Functional Failure 2.4 Timing Variation 3. Search Space Pruning 3.1 Spatial Pruning 3.2 Electrical Pruning 3.3 Temporal Pruning 3.4 Functional Pruning 3.5 Problem Complexity v.s. Accuracy 4. Overview 2: Miller Factor Computation for Coupling Delay 1. Introduction 2. Gate Driving and Coupling Model 2.1 Nonlinearity of Driver Model 2.2 Driver Modeling 3. Decoupling Approximation 3.1 Coupling Model 3.1.1 Bounds 3.2 Simple Iterative Approach 3.2.1 Convergence of the Simple Iterative Approach 3.3 Newton-Raphson Iteration for Miller Factor 3.4 Multiple Miller Factors for Multiple Coupling Nets 3.5 Slew Rate (Transition Time) Calculation 4. Nonzero Initial Voltage Correction 4.1 Glitch Waveform Approximation 5. Experimental Results 6. Review of Conservativism 7. Conclusion 3: Convergence of Switching Window Computation 1. Introduction 2. Background 2.1 Simple Upper and Lower Bounds for Switching Windows 3. Fixed Point Computation 3.1 Formulation 3.2 Fixed Point Iteration for Switching Windows Computation 3.3 Multiple Convergence Points and Unstable Fixed Point 3.4 Tightening Bounds 4. Coupling Models 4.1 Noise Calculation Model 4.2 Switching Windows Overlapping Model 4.3 Discontinuity in Discrete Models 4.4 Error Bound between Discrete and Continuous Models 4.5 Non-Monotone Property 5. Convergence of Switching Windows Computation 5.1 Proof of Convergence 5.2 Computational Complexity 5.3 Convergence Rate 5.4 Least Evaluation of Coupling RC Networks 5.5 Speed-up of Convergence 6. Conclusion 4: Speeding-Up Switching Window Computation 1. Introduction 2. Background and Definitions 2.1 Piecewise Linear Waveform 3. Multiple Aggressor Alignment Problem 4. Coupling Delay Computation in Presence of Crosstalk Noise 4.1 Algorithm 4.2 Convergence of Our Algorithm 4.3 Properties of Our Algorithm 4.4 Event Pruning 4.5 Scheduling Technique 5. Experimental Results 6. Review of Conservativism 7. Conclusion 5: Refinement of Switching Windows 1. Introduction 2. Formulation and Algorithm 2.1 Arrival Time Uncertainty in Interconnect 2.2 Switching Window Density 2.3 Input Timing Uncertainty 2.4 Complexity 2.5 Implementation Consideration 3. Resolution and Truncation Errors 4. Experimental Results 5. Consideration of Slew Rates 6. Property of Time Slots and Conservativism 7. Conclusion 6: Functional Crosstalk Analysis 1. Introduction 2. Approaches and Related Work 3. Vector Pair Searching Algorithm 3.1 Overview 3.2 BCOP: Boolean Constrained Optimization Problem 3.3 Constructing Circuit via SAT 3.4 Maximum Noise under the Zero-Delay Model 3.5 Fixed Delay Circuit Construction via SAT 3.5.1 Using Timed Boolean Variables 3.5.2 Translation of Maximum Coupling Effects into an Objective Function 3.5.3 Boolean Constrained Optimization 3.5.4 Discrete Required Time Analysis 3.5.5 Structural Hashing 3.5.6 Coarse Quantum Time 3.5.7 Boolean Constraint Relaxation 4. Experimental Results 5. Future Work 6. Conservativism Consideration 7. Conclusions 7: Conclusions References