A novel timing-driven global routing algorithm considering coupling effects for high performance circuit design

ABSTRACT

As the CMOS technology enters the very deep submicron era, inter-wire coupling capacitance becomes the dominant part of load capacitance. The coupling effects have brought new challenges to routing algorithms on both delay estimation and optimization. In this paper, we propose a timing-driven global routing algorithm with consideration of coupling effects. The two-phase algorithm based on timing-relax method includes a heuristic Steiner tree algorithm and an optimization algorithm. Experimental results are given to demonstrate the efficiency and accuracy of the algorithm.

REFERENCES

• 1: Jin Huang , Xian-Long Hong , Chung-Kuan Cheng , E. S. Kuh, An efficient timing-driven global routing algorithm, Proceedings of the 30th international conference on Design automation, p.596-600, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165063]
• 2: X. L. Hong, T. X. Xue, J. Huang, C. K. Cheng, E. S. kuh, "TIGER: An Efficient Timing-Driven Global Router for Gate Array and Standard Cell Layout Design", IEEE Trans. on CAD, 16(11), pp. 1323--1330, 1997.
• 3: Jiang Hu , Sachin S. Sapatnekar, A timing-constrained algorithm for simultaneous global routing of multiple nets, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 4: T. Jing, X. L. Hong, H. Y. Bao, Y. C. Cai, J. Y. Xu et al, "A Novel and Efficient Timing-Driven Global Router for Standard Cell Layout Design Based on Critical Network Concept", In: Proceedings of IEEE ISCAS, Scottsdale, Arizona, USA, pp. 1165--1168, 2002.
• 5: W. C. Elmore, "The Transient Response of Lumped Linear Networks with Particular Regard to Wideband Amplifiers", J. of Applied Physics, 19(1): pp. 55--59, 1948.
• 6: T. Sakurai, "Approximation of Wiring Delay in MOSFET LSI", IEEE J. of SSC, 18(4): pp. 418--426, 1983.
• 7: H. Zhou, and D. F. wang, "Global Routing with Crosstalk Constraints", IEEE Trans. on CAD, Vol. 18, No. 11, pp. 1683--1688, 1999.
• 8: S. S. Sapatnekar, "A Timing Model Incorporating the Effect of Crosstalk on Delay and its Application to Optimal Channel Routing", IEEE Trans. on CAD, Vol. 19, No. 5, pp. 550--559, 2000.
• 9: K. C. Hsu, Y. C. Lin, P. X. Chiu, and T. M. Hsieh, "Minimum Crosstalk Channel Routing with Dogleg", In: Proceedings of IEEE ISCAS, Geneva, pp. 73--76, 2000.
• 10: Jason Cong , Lei He , Cheng-Kok Koh , Zhigang Pan, Global interconnect sizing and spacing with consideration of coupling capacitance, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.628-633, November 09-13, 1997, San Jose, California, United States
• 11: T. Jing, X. L. Hong, Y. C. Cai, H. Y. Bao, J. Y. Xu, "The Key Technologies and Related Research Work of Performance-Driven Global Routing", J. of Software, 12(5): pp. 677--688, 2001.
• 12: X. D. Yang, A Reduced Order Modeling and Analysis for VLSI RLC Interconnect, Ph.D. thesis, CSE Dept., UCSD, USA, May, 2000.
• 13: Altan Odabasioglu , Mustafa Celik , Lawrence T. Pileggi, PRIMA: passive reduced-order interconnect macromodeling algorithm, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.58-65, November 09-13, 1997, San Jose, California, United States
• 14: John Lillis , Premal Buch, Table-lookup methods for improved performance-driven routing, Proceedings of the 35th annual conference on Design automation, p.368-373, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277146]
• 15: X. L. Hong, "A Performance-Driven Steiner Tree Algorithm Using Constructed Force Directed Approach for Global Routing", Chinese Journal of Semiconductors, 16(3): pp. 218--223, 1995
• 16: Jingyu Xu , Xianlong Hong , Tong Jing , Yici Cai , Jun Gu, An Efficient Hierarchical Timing-Driven Steiner Tree Algorithm for Global Routing, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.473, January 07-11, 2002