A Min-area Solution to Performance and RLC Crosstalk Driven Global Routing Problem

ABSTRACT

This paper presents a novel global routing algorithm, AT-PO-GR, to minimize the routing area under both congestion, timing, and RLC crosstalk constraints. The proposed algorithm is consisted of three key parts: (1) timing and congestion optimization; (2) crosstalk budgeting and estimation; and (3) crosstalk elimination and local refinement. Compared with the recent work introduced in [9] and [10], the proposed algorithm can achieve smaller routing area and fewer shields under the same design constraints, yet use less running time.

REFERENCES

• 1: T. Jing, X. L. Hong. "The Key Technologies of Performance Optimization for Nanometer Routing". In: Proc. IEEE ASICON, Beijing, China, 2003, pp. 118--123.
• 2: T. Sakurai, S. Kobayashi, and M. Node. "Simple expressions for interconnecting delay, coupling and crosstalk in VLSI's", In: Proc. IEEE ISCAS, Singapore, 1991, pp.2375--2378.
• 3: Lei He , Kevin M. Lepak, Simultaneous shield insertion and net ordering for capacitive and inductive coupling minimization, Proceedings of the 2000 international symposium on Physical design, p.55-60, May 2000, San Diego, California, United States [doi>10.1145/332357.332374]
• 4: T. X. Xue, E. S. Kuh, and D. S. Wang. "Post global routing crosstalk synthesis", IEEE Trans on CAD, 1997, 16(12): pp. 1418--1430.
• 5: J. J. Xiong and L. He. "Full-Chip Routing Optimization With RLC Crosstalk Budgeting", IEEE Trans on CAD, 2004, 23(3) pp. 366--377.
• 6: H. Zhou and D. F. Wong. "Global routing with crosstalk constraints", IEEE Trans on CAD, 1999, 18(11): pp. 1683--1688.
• 7: James D. Z. Ma , Lei He, Towards global routing with RLC crosstalk constraints, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514088]
• 8: Jingyu Xu , Xianlong Hong , Tong Jing , Ling Zhang , Jun Gu, A coupling and crosstalk considered timing-driven global routing algorithm for high performance circuit design, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.677-682, January 27-30, 2004, Yokohama, Japan
• 9: L. Zhang, T. Jing, X. L. Hong, J. Y. Xu, J. J. Xiong, L. He. "Performance Optimization Global Routing with RLC Crosstalk Constraints", In: Proc. IEEE ASICON, Beijing, China, 2003, pp. 191--194.
• 10: L. Zhang, T. Jing, X. L. Hong, J. Y. Xu, J. J. Xiong, L. He. "Performance and RLC Crosstalk Driven Global Routing", In: Proc. IEEE ISCAS, 2004, Vancouver, Canada, pp. V65--68.
• 11: T. Jing, X. L. Hong, H. Y. Bao, et al, "A novel and efficient timing-driven global router for standard cell layout design based on critical network concept", In: Proc. IEEE ISCAS, Scottsdale, Arizona, USA, 2002, pp. I165--168.
• 12: Tong Jing , Xian Long Hong , Hai Yun Bao , Jing Yu Xu , Jun Gu, SSTT: efficient local search for GSI global routing, Journal of Computer Science and Technology, v.18 n.5, p.632-639, September 2003 [doi>10.1007/BF02947123]
• 13: Fred Glover, Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, v.13 n.5, p.533-549, May 1986 [doi>10.1016/0305-0548(86)90048-1 ]