Bhavana Thudi firstname.lastname@example.org
In static timing analysis, delay noise has traditionally been modeled using a simple switch-factor based noise model and the computation of switching windows is performed using an iterative algorithm, resulting in an overall run time of O(n^2), where n is the number of gates in the circuit. It has also been shown that the iterations converge to different solutions, depending on the initial assumptions, making it unclear which solution is correct. In this research, we show that the iterative nature of the problem is due to the switching-factor based noise model and the order in which events are evaluated. We utilize a delay noise model based on superposition and propose a new algorithm with a run time that is linear with the circuit size. Since the algorithm is non-iterative and does not operate with initial assumptions, it also eliminates the multiple solution problem. We tested the algorithm on a number of designs and show that it achieves significant speedup of upto 5X over the iterative approach.
Bhavana Thudi, David Blaauw, “Non-Iterative Timing Window Computation for Delay Noise,” ACM/IEEE Design Automation Conference (DAC), June 2003, pg. 390-395 ©IEEE