Fast analysis of nontree-clock network considering environmental uncertainty by parameterized and incremental macromodeling

ABSTRACT

It is challenging to verify clock-skew for large-scale nontree clock network with environmental uncertainties such as supply voltage fluctuation and thermal temperature gradient. This paper presents a fast clock-skew analysis via parameterized incremental truncated-balanced-realization, called piTBR method. Environmental uncertainties are parametrically and structurally added into the state equation of clock network. A compact macromodel is obtained by the subspace projection constructed from the singular value decomposition (SVD) of circuit output waveforms. To reduce the computational cost, we propose an incremental SVD method that only needs to partially update the projection matrix by analyzing the perturbed output waveform owning to environmental uncertainties. Experiments on a number of clock networks show that compared with the macromodeling by the fast TBR method, our method reduces the computational cost in the order of 100x with a similar accuracy. In addition, compared with the macromodeling by the Krylov-subspace-based method, our method reduces the waveform error by 2x with a similar runtime.

REFERENCES

• 1: Jason Cong , Andrew B. Kahng , Cheng-Kok Koh , C.-W. Albert Tsao, Bounded-skew clock and Steiner routing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.341-388, July 1998 [doi>10.1145/293625.293628]
• 2: Ying Liu , Sani R. Nassif , Lawrence T. Pileggi , Andrzej J. Strojwas, Impact of interconnect variations on the clock skew of a gigahertz microprocessor, Proceedings of the 37th conference on Design automation, p.168-171, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337365]
• 3: Haihua Su , Sachin S. Sapatnekar, Hybrid structured clock network construction, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 4: Anand Rajaram , Jiang Hu , Rabi Mahapatra, Reducing clock skew variability via cross links, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996574]
• 5: Minsik Cho , S. Ahmedtt , D. Z. Pan, TACO: temperature aware clock-tree optimization, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.582-587, November 06-10, 2005, San Jose, CA
• 6: H. Yu, Y. Hu, C. Liu, and L. He, "Minimal skew clock embedding considering time variant temperature variation," in ACM ISPD, 2007.
• 7: Xiaoji Ye , Peng Li , Min Zhao , Rajendran Panda , Jiang Hu, Analysis of large clock meshes via harmonic-weighted model order reduction and port sliding, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 8: A. H. Ajami, K. Banerjee, and M. Pedram, "Modeling and analysis of nonuniform substrate temperature effects on global ULSI interconnects," IEEE TCAD, pp. 849--861, 2005.
• 9: Hao Yu , Joanna Ho , Lei He, Simultaneous power and thermal integrity driven via stapling in 3D ICs, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233666]
• 10: Joel Phillips , L. Miguel Silveira, Poor Man's TBR: A Simple Model Reduction Scheme, Proceedings of the conference on Design, automation and test in Europe, p.20938, February 16-20, 2004
• 11: J. R. Phillips, Variational interconnect analysis via PMTBR, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.872-879, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382697]
• 12: Duo Li , Sheldon X.-D. Tan , Bruce McGaughy, ETBR: extended truncated balanced realization method for on-chip power grid network analysis, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany [doi>10.1145/1403375.1403479]
• 13: Janet M. Wang , Tuyen V. Nguyen, Extended Krylov subspace method for reduced order analysis of linear circuits with multiple sources, Proceedings of the 37th conference on Design automation, p.247-252, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337407]
• 14: Y. Lee, Y. Cao, T. Chen, J. Wang, and C. Chen, "HiPRIME: Hierarchical and passivity preserved interconnect macromodeling engine for RLKC power delivery," IEEE TCAD, pp. 797--806, 2005.
• 15: E. J. Grimme, Krylov projection methods for model reduction (Ph. D Thesis). Univ. of Illinois at Urbana-Champaign, 1997.
• 16: A. Odabasioglu, M. Celik, and L. Pileggi, "PRIMA: Passive reduced-order interconnect macro-modeling algorithm," IEEE TCAD, pp. 645--654, 1998.
• 17: P. Feldmann , F. Liu, Sparse and efficient reduced order modeling of linear subcircuits with large number of terminals, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.88-92, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382548]
• 18: Pu Liu , S. X. -D. Tan , Hang Li , Zhenyu Qi , Jun Kong , B. McGaughy , Lei He, An efficient method for terminal reduction of interconnect circuits considering delay variations, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.821-826, November 06-10, 2005, San Jose, CA
• 19: K. J. Kerns and A. T. Yang, "Stable and efficient reduction of large, multiport RC network by pole analysis via congruence transformations," IEEE TCAD, pp. 734--744, 1998.
• 20: Xin Li , Peng Li , L. T. Pileggi, Parameterized interconnect order reduction with explicit-and-implicit multi-parameter moment matching for inter/intra-die variations, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.806-812, November 06-10, 2005, San Jose, CA
• 21: G. H. Golub and C. F. V. Loan, Matrix Computations. Baltimore, MD: The Johns Hopkins University Press, 3 ed., 1989.
• 22: M. Berry, "Large scale singular value computations," Int. J. of Supercomputer Appl., pp. 13--49, 1992.
• 23: Matthew Brand, Incremental Singular Value Decomposition of Uncertain Data with Missing Values, Proceedings of the 7th European Conference on Computer Vision-Part I, p.707-720, May 28-31, 2002