Tong Jing
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.
- R. Kastner, E. Bozorgzadeh, M. Sarrafzadeh, "An Exact Algorithm for Coupling-Free Routing", In: Proceedings of ACM ISPD, Sonoma, CA, pp. 10--15, 2001. Google Scholar
Digital Library
- 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.Google Scholar
- J. Hu, S. S. Sapatnekar, "A Timing-constrained Algorithm for Simultaneous Global Routing of Multiple Nets", In: Proceedings of IEEE/ACM ICCAD, San Jose, CA, pp. 99--103, 2000. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- T. Sacurai, "Approximation of Wiring Delay in MOSFET LSI", IEEE Journal of Solid-State Circuits, 18(4), pp. 418--426, 1983.Google ScholarCross Ref
- X. L. Hong, T. X. Xue, E. S. Kuh, C. K. Cheng, J. Huang, "Performance-Driven Steiner Tree Algorithm for Global Routing", In: Proceedings of ACM/IEEE DAC, Dallas, Texas, pp. 177--181, 1993. Google ScholarDigital Library
- J. Y. Xu, X. L. Hong, T. Jing, Y. C. Cai, J. Gu, "An Efficient Hierarchical Timing-Driven Steiner Tree Algorithm for Global Routing", In: Proceedings of IEEE/ACM ASP-DAC, Bangalore, India, pp. 473--478, 2002. Google ScholarDigital Library
- J. Cong, L. He, K. Y. Khoo, C. K. Koh, Z. G. Pan, "Interconnect Design for Deep Submicron ICs", In: Proceedings of IEEE/ACM ICCAD, San Jose, CA, pp. 478--485, 1997. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. Huang, X. L. Hong, C. K. Cheng, E. S. Kuh, "An Efficient Timing-Driven Global Routing Algorithm", In: Proceedings of ACM/IEEE DAC, Dallas, Texas, pp. 596--600, 1993. Google ScholarDigital Library
- Y. Fujihara, Y. Sekiyama, Y. Ishibashi, M. Yanaka, "DYNAJUST: An Efficient Automation Routing Technique Optimizing Delay Conditions", In: Proceedings of ACM/IEEE DAC, Las Vegas, Nevada, pp. 791--794, 1989. Google ScholarDigital Library
- 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.Google Scholar
- A. E. Dunlop, V. D. Agrawal, D. N. Deutsch, M. F. Jukl, P. Kozak et al, "Chip Layout Optimization Using Critical Path Weighting", In: Proceedings of ACM/IEEE DAC, Albuquerque, New Mexico, pp. 133--136, 1984. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- D. G. Luenberger, Linear and Nonlinear Programming, Second Edition, Addison Wesley, 1984.Google Scholar
- 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. Google ScholarDigital Library
- C. Albrecht, "Provably Good Global Routing by a New Approximation Algorthm for Multicommodity Flow", In: Proceedings of ACM ISPD, San Diego, CA, pp. 19--25, 2000. Google ScholarDigital Library
- E. Shragowitz, S. Keel, "A global router based on a multi-commodity flow model", Integration, the VLSI J., 5, pp. 3--16, 1987. Google ScholarDigital Library
- 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.Google Scholar
- R. E. Tarjan, "Algorithms for Maximum Network Flow", Mathematical Programming Study, 26, pp. 1--11, 1986.Google ScholarCross Ref
Recommendations
UTACO: a unified timing and congestion optimization algorithm for standard cell global routing
Timing performance and routability are two main goals of global routing. These two targets are mutually conflicting if we view and handle their effects independently. In this paper, we adopt a shadow price mechanism to incorporate the two issues into ...
Implications of a Reserve Price in an Agent-Based Common-Value Auction
Auction sellers can use a reserve price to require a minimum bid before items are sold. Theoretical and experimental research has tested the influence of a reserve price in an independent private values auction, but little focus has been given to the ...
Sequential auctions and externalities
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithmsIn many settings agents participate in multiple different auctions that are not necessarily implemented simultaneously. Future opportunities affect strategic considerations of the players in each auction, introducing externalities. Motivated by this ...
Comments