Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Timing performance and routability are two main issues of global routing. In this paper, we adopt a shadow price mechanism to incorporate the two issues into one unified objective function. The shadow price of a net is the sum of its congestion price and timing price. Based on the new formulation, this paper presents the UTACO algorithm for standard cell (SC) global routing. The experimental results show that UTACO is efficient for both timing and congestion optimization.

REFERENCES

• 1: Ryan Kastner , Elaheh Bozorgzadeh , Majid Sarrafzadeh, An exact algorithm for coupling-free routing, Proceedings of the 2001 international symposium on Physical design, p.10-15, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369711]
• 2: 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.
• 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: W. C. Elmore, "The Transient Response of Lumped Linear Networks with Particular Regard to Wideband Amplifiers", Journal of Applied Physics, 19(1), pp. 55--59, 1948.
• 5: T. Sacurai, "Approximation of Wiring Delay in MOSFET LSI", IEEE Journal of Solid-State Circuits, 18(4), pp. 418--426, 1983.
• 6: Xianlong Hong , Tianxiong Xue , Ernest S. Kuh , Chung-Kuan Cheng , Jin Huang, Performance-driven Steiner tree algorithm for global routing, Proceedings of the 30th international conference on Design automation, p.177-181, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164658]
• 7: 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
• 8: Jason Cong , Zhigang Pan , Lei He , Cheng-Kok Koh , Kei-Yong Khoo, Interconnect design for deep submicron ICs, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.478-485, November 09-13, 1997, San Jose, California, United States
• 9: C. C. N. Chu, D. F. Wong, "An Efficient and Optimal Algorithm for Simultaneous Buffer and Wire Sizing", IEEE Trans. on CAD, 18(9), pp. 1297--1304, 1999.
• 10: J. Lillis, C. K. Cheng, "Timing Optimization for Multisource Nets: Characterization and Optimal Repeater Insertion", IEEE Trans. on CAD, 18(3), pp. 322--331, 1999.
• 11: 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]
• 12: Y. Fujihara , Y. Sekiyama , Y. Ishibashi , M. Yanaka, DYNAJUST: an efficient automatic routing technique optimizing delay conditions, Proceedings of the 26th ACM/IEEE conference on Design automation, p.791-794, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74531]
• 13: M. A. B. Jackson, E. S. Kuh, M. Marek-Sadowska, "Timing Driven Routing for Building Block Layout", In: Proceedings of IEEE ISCAS, pp. 518--519, 1987.
• 14: A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
• 15: M. Rose, M. Wiesel, D. Kirkpatrick, N. Nettleton, "Dense, Performance Directed, Auto Place and Route", In: Proceedings of IEEE CICC, Rochester, NY, pp. 11.1.1--11.1.4, 1988.
• 16: 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.
• 17: D. G. Luenberger, Linear and Nonlinear Programming, Second Edition, Addison Wesley, 1984.
• 18: R. C. Carden IV, J. M. Li, C. K. Cheng, "A Global Router with a Theoretical Bound on the Optimal Solution", IEEE Trans. on CAD, 15(2), pp. 208--216, 1996.
• 19: Christoph Albrecht, Provably good global routing by a new approximation algorithm for multicommodity flow, Proceedings of the 2000 international symposium on Physical design, p.19-25, May 2000, San Diego, California, United States [doi>10.1145/332357.332368]
• 20: E. Shragowitz , S. Keel, A global router based on a multicommodity flow model, Integration, the VLSI Journal, v.5 n.1, p.3-16, March 1987 [doi>10.1016/S0167-9260(87)80003-2]
• 21: T. Jing, X. L. Hong, H. Y. Bao, Y. C. Cai, J. Y. Xu et al, "An Efficient Congestion Optimization Algorithm for Global Routing Based on Search Space Traversing Technology", In: Proceedings of IEEE International Conference on ASIC, Shanghai, China, pp. 114--117, 2001.
• 22: R. E. Tarjan, "Algorithms for Maximum Network Flow", Mathematical Programming Study, 26, pp. 1--11, 1986.