List of FiguresnList of TablesnPrefacenn1: Introduction n1. Motivationn1.1 Process Trendsn1.2 CMOS Circuitryn2. Background and Crosstalk Effectsn2.1 Static Timing Analysisn2.2 Crosstalk Effectsn2.3 Functional Failuren2.4 Timing Variationn3. Search Space Pruningn3.1 Spatial Pruningn3.2 Electrical Pruningn3.3 Temporal Pruningn3.4 Functional Pruningn3.5 Problem Complexity v.s. Accuracyn4. Overview nn2: Miller Factor Computation for Coupling Delay n1. Introductionn2. Gate Driving and Coupling Modeln2.1 Nonlinearity of Driver Model n2.2 Driver Modelingn3. Decoupling Approximationn3.1 Coupling Modeln3.1.1 Boundsn3.2 Simple Iterative Approachn3.2.1 Convergence of the Simple Iterative Approach n3.3 Newton-Raphson Iteration for Miller Factorn3.4 Multiple Miller Factors for Multiple Coupling Netsn3.5 Slew Rate (Transition Time) Calculationn4. Nonzero Initial Voltage Correctionn4.1 Glitch Waveform Approximationn5. Experimental Resultsn6. Review of Conservativism n7. Conclusionnn3: Convergence of Switching Window Computationn1. Introductionn2. Backgroundn2.1 Simple Upper and Lower Bounds for Switching Windowsn3. Fixed Point Computationn3.1 Formulation n3.2 Fixed Point Iteration for Switching Windows Computationn3.3 Multiple Convergence Points and Unstable Fixed Pointn3.4 Tightening Boundsn4. Coupling Modelsn4.1 Noise Calculation Modeln4.2 Switching Windows Overlapping Modeln4.3 Discontinuity in Discrete Modelsn4.4 Error Bound between Discrete and Continuous Modelsn4.5 Non-Monotone Propertyn5. Convergence of Switching Windows Computationn5.1 Proof of Convergencen5.2 Computational Complexityn5.3 Convergence Raten5.4 Least Evaluation of Coupling RC Networksn5.5 Speed-up of Convergencen6. Conclusionnn4: Speeding-Up Switching Window Computationn1. Introductionn2. Background and Definitionsn2.1 Piecewise Linear Waveformn3. Multiple Aggressor Alignment Problemn4. Coupling Delay Computation in Presence of Crosstalk Noisen4.1 Algorithmn4.2 Convergence of Our Algorithmn4.3 Properties of Our Algorithm n4.4 Event Pruningn4.5 Scheduling Techniquen5. Experimental Results n6. Review of Conservativismn7. Conclusionnn5: Refinement of Switching Windowsn1. Introductionn2. Formulation and Algorithmn2.1 Arrival Time Uncertainty in Interconnectn2.2 Switching Window Densityn2.3 Input Timing Uncertaintyn2.4 Complexityn2.5 Implementation Considerationn3. Resolution and Truncation Errorsn4. Experimental Resultsn5. Consideration of Slew Ratesn6. Property of Time Slots and Conservativismn7. Conclusionnn6: Functional Crosstalk Analysisn1. Introductionn2. Approaches and Related Workn3. Vector Pair Searching Algorithmn3.1 Overviewn3.2 BCOP: Boolean Constrained Optimization Problemn3.3 Constructing Circuit via SATn3.4 Maximum Noise under the Zero-Delay Model n3.5 Fixed Delay Circuit Construction via SAT n3.5.1 Using Timed Boolean Variables n3.5.2 Translation of Maximum Coupling Effects into an Objective Function n3.5.3 Boolean Constrained Optimizationn3.5.4 Discrete Required Time Analysisn3.5.5 Structural Hashingn3.5.6 Coarse Quantum Timen3.5.7 Boolean Constraint Relaxation 4. Experimental Results 5. Future Work 6. Conservativism Consideration 7. Conclusions 7: ConclusionsnReferences
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.