Convergence-provable statistical timing analysis with level-sensitive latches and feedback loops

Statistical timing analysis has been widely applied to predict the timing yield of VLSI circuits when process variations become significant. Existing statistical latch timing methods are either having exponential complexity or unable to treat the random variable´s self-dependence caused by the coexistence of level-sensitive latches and feedback loops. In this paper, an efficient iterative statistical timing algorithm with provable convergence is proposed for latch-based circuits with feedback loops. Based on a new notion of iteration mean, we prove that the algorithm converges unconditionally. Moreover, we show that the converged value of iteration mean ca be used to predict the circuit yield during design time. Tested by ISCAS´89 benchmark circuits, the proposed algorithm shows a error of 1.1% and speedup of 303 times on average when compared with the Monte Carlo simulation