Clustering based pruning for statistical criticality computation under process variations

ABSTRACT

We present a new linear time technique to compute criticality information in a timing graph by dividing it into "zones". Errors in using tightness probabilities for criticality computation are dealt with using a new clustering based pruning algorithm which greatly reduces the size of circuit-level cutsets. Our clustering algorithm gives a 150X speedup compared to a pairwise pruning strategy in addition to ordering edges in a cutset to reduce errors due to Clark's MAX formulation. The clustering based pruning strategy coupled with a localized sampling technique reduces errors to within 5% of Monte Carlo simulations with large speedups in runtime.

REFERENCES

• 1: 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]
• 2: K. Chopra , S. Shah , A. Srivastava , D. Blaauw , D. Sylvester, Parametric yield maximization using gate sizing based on efficient statistical power and delay gradient computation, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1023-1028, November 06-10, 2005, San Jose, CA
• 3: C. E. Clark, "The greatest of a finite set of random variables," Operations Research, vol. 9, no. 2, pp. 145--162, Mar-Apr 1961.
• 4: T. F. Gonzalez, "Clustering to minimize the maximum intercluster distance," Theoretical Computer Science, vol. 38, no. 2--3, pp. 293--306, 1985.
• 5: Xin Li , Jiayong Le , Mustafa Celik , L. T. Pileggi, Defining statistical sensitivity for timing optimization of logic circuits with large-scale process and environmental variations, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.844-851, November 06-10, 2005, San Jose, CA
• 6: Sani R. Nassif, Design for Variability in DSM Technologies, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.451, March 20-22, 2000
• 7: Predictive technology model (PTM). {Online}. Available: http://www.eas.asu.edu/~ptm/
• 8: Debjit Sinha , Hai Zhou , Narendra V. Shenoy, Advances in Computation of the Maximum of a Set of Random Variables, Proceedings of the 7th International Symposium on Quality Electronic Design, p.306-311, March 27-29, 2006 [doi>10.1109/ISQED.2006.22]
• 9: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 10: Jinjun Xiong , Vladimir Zolotov , Natesan Venkateswaran , Chandu Visweswariah, Criticality computation in parameterized statistical timing, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146929]
• 11: T. Yoshimura and E. S. Kuh, "Efficient algorithms for channel routing," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 1, no. 1, pp. 25--35, Jan. 1982.