Efficient statistical timing analysis through error budgeting

ABSTRACT

We propose a technique for optimizing the runtime in statistical timing analysis. Given a global acceptable error budget at the primary output which signifies the difference in the area of the accurate and approximate timing CDFs, we propose a formulation of budgeting this global error across all nodes in the circuit. This node error budget is used to simplify the computation of arrival time CDFs at each node using approximations. This simplification reduces the runtime of statistical timing analysis. We investigate two ways of exploiting this node error budget, firstly through piecewise linear approximation (see ibid., A. Devgan and C. Kashyap, 2003) and secondly though hierarchical quadratic approximation. Experimental results on ISCAS/MCNC benchmarks show that our approach is at most 3 times faster than accurate statistical timing analysis and had a very small error. We also found quadratic piecewise approximation to be more accurate than linear approximation but at lesser gains in runtime.

REFERENCES

• 1: Aseem Agarwal , David Blaauw , Vladimir Zolotov, Statistical Timing Analysis for Intra-Die Process Variations with Spatial Correlations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.900, November 09-13, 2003 [doi>10.1109/ICCAD.2003.130]
• 2: Aseem Agarwal , David Blaauw , Vladimir Zolotov , Sarma Vrudhula, Computation and Refinement of Statistical Bounds on Circuit Delay, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775922]
• 3: [3] A. Agarwal, V. Zolotov and D. Blaauw. "Statistical Timing Analysis Using Bounds and Selective Enumeration". In IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 22, Sept. 2003.
• 4: Anirudh Devgan , Chandramouli Kashyap, Block-based Static Timing Analysis with Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.607, November 09-13, 2003 [doi>10.1109/ICCAD.2003.41]
• 5: Chandu Visweswariah, Death, taxes and failing chips, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775921]
• 6: [6] C. Visweswariah et al. "First-Order Parameterized Block-Based Statistical Timing Analysis". In Procs of TAU, 2004.
• 7: [7] E.M. Sentovich, K.J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P.R. Stephan, R.K. Brayton, A.L. Sangiovanni-Vincentelli. SIS: A System for Sequential Circuit Synthesis, Memorandum No. UCB/ERL M92/41, Department of EECS. UC Berkeley, May 1992.
• 8: Hongliang Chang , Sachin S. Sapatnekar, Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.621, November 09-13, 2003 [doi>10.1109/ICCAD.2003.129]
• 9: [9] H. J. Bungartz. "Higher Order Finite Elements on Sparse Grids". In Technical Report SFB-Bericht Nr. 342/01/95 A, Institut fur Informatik, TU Munich 1995.
• 10: [10] H. J. Bungartz and T. Dornseifer. "Sparse Grids: Recent Developments for Elliptic Partial Differential Equations". In Technical Report TUM-19702, SFB-Bericht Nr. 342/02/97 A, Institut fur Informatik, TU Munich 1997.
• 11: J. A. G. Jess , K. Kalafala , S. R. Naidu , R. H. J. M. Otten , C. Visweswariah, Statistical timing for parametric yield prediction of digital integrated circuits, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776066]
• 12: Rubil Ahmadi , Farid N. Najm, Timing Analysis in Presence of Power Supply and Ground Voltage Variations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.176, November 09-13, 2003 [doi>10.1109/ICCAD.2003.142]
• 13: Sarvesh Bhardwaj , Sarma B. K. Vrudhula , David Blaauw, "AU: Timing Analysis Under Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.615, November 09-13, 2003 [doi>10.1109/ICCAD.2003.1]