Timing driven track routing considering coupling capacitance

ABSTRACT

As VLSI technology enters the ultra-deep submicron era, wire coupling capacitance starts to dominate self capacitance and can no longer be neglected in timing driven routing. In this paper, a coupling aware timing driven track routing heuristic is proposed. Given a global routing solution and timing constraint for each net, major trunks of wire segments are assigned to routing tracks such that the minimum timing slack among all nets is maximized. Delay penalties from both coupling capacitance and wire detour are considered in a unified graph model. The core problem is formulated and solved as a Sequential Ordering Problem (SOP). Routing blockages are handled in a post processing procedure. The experimental results on benchmark circuits show that the effect of coupling capacitance on timing is significant and the proposed heuristic results in greater improvement on coupling aware timing compared with other approaches.

REFERENCES

• 1: X. Hong, T. Xue, J. Huang, C.-K. Cheng, and E. S. Kuh. TIGER: an efficient timing-driven global router for gate array and standard cell layout design. IEEE TCAD, 16(11):1323--1331, November 1997.
• 2: J. Hu and S. S. Sapatnekar. A timing-constrained simultaneous global routing algorithm. IEEE TCAD, 21(9):1025--1036, September 2002.
• 3: Tong Jing , Xianlong Hong , Haiyun Bao , Yici Cai , Jingyu Xu , Chungkuan Cheng , Jun Gu, UTACO: a unified timing and congestion optimizing algorithm for standard cell global routing, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119956]
• 4: T. Gao and C. L. Liu. Minimum crosstalk channel routing. IEEE TCAD, 15(5):465--474, May 1996.
• 5: A. Vittal and M. Marek-Sadowska. Crosstalk reduction for VLSI. IEEE TCAD, 16(3):290--298, March 1997.
• 6: T. Xue, E. S. Kuh, and D. Wang. Post global routing crosstalk synthesis. IEEE TCAD, 16(12):1418--1430, December 1997.
• 7: Phiroze N. Parakh , Richard B. Brown, Crosstalk constrained global route embedding, Proceedings of the 1999 international symposium on Physical design, p.201-206, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300077]
• 8: H. Zhou and D. F. Wong. Global routing with crosstalk constraints. IEEE TCAD, 18(11):1683--1688, 1999.
• 9: Rony Kay , Rob A. Rutenbar, Wire packing: a strong formulation of crosstalk-aware chip-level track/layer assignment with an efficient integer programming solution, Proceedings of the 2000 international symposium on Physical design, p.61-68, May 2000, San Diego, California, United States [doi>10.1145/332357.332375]
• 10: C.-C. Chang and J. Cong. Pseudopin assignment with crosstalk noise control. IEEE TCAD, 20(5):598--611, May 2001.
• 11: J. Cong, L. He, C.-K. Koh, and Z. Pan. Interconnect sizing and spacing with consideration of coupling capacitance. IEEE TCAD, 20(9):1164--1169, September 2001.
• 12: 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]
• 13: P. Saxena and S. Gupta. On integrating power and signal routing for shield count minimization in congested regions. IEEE TCAD, 22(4):437--445, April 2003.
• 14: Tsung-Yi Ho , Yao-Wen Chang , Sao-Jie Chen , D. T. Lee, A Fast Crosstalk- and Performance-Driven Multilevel Routing System, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.382, November 09-13, 2003 [doi>10.1109/ICCAD.2003.3]
• 15: Jingyu Xu , Xianlong Hong , Tong Jing , Yici Cai , Jun Gu, A novel timing-driven global routing algorithm considering coupling effects for high performance circuit design, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119958]
• 16: Shabbir Batterywala , Narendra Shenoy , William Nicholls , Hai Zhou, Track assignment: a desirable intermediate step between global routing and detailed routing, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.59-66, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774581]
• 17: H.-P. Tseng, L. Sheffer, and C. Sechen. Timing- and crosstalk- driven area routing. IEEE TCAD, 20(4):528--544, April 2001.
• 18: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 19: S. Chen and S. Smith Commonality and genetic algorithm. Technical Report CMU-RI-TR-96-27, Carnegie Mellon University, Pittsburgh, 1996. http://www-2.cs.cmu.edu/ chens/