Abstract
In this paper, a novel global routing algorithm is presented for congestion optimization based on efficient local search, named SSTT (search space traversing technology). This method manages to traverse the whole search space. A hybrid optimization strategy is adopted, consisting of three optimization sub-strategies: stochastic optimization, deterministic optimization and local enumeration optimization, to dynamically reconstruct the problem structure. Thus, “transition” can be made from a local minimum point to reach other parts of the search space, traverse the whole search space, and obtain the global (approximate) optimal routing solution. Since any arbitrary initial routing solution can be used as the start point of the search, the initialization in SSTT algorithm is greatly simplified. SSTT algorithm has been tested on both MCNC benchmark circuits and industrial circuits, and the experimental results were compared with those of typical existing algorithms. The experimental results show that SSTT algorithm can obtain the global (approximate) optimal routing solution easily and quickly. Moreover, it can meet the needs of practical applications. The SSTT global routing algorithm gives a general-purpose routing solution.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Hong X L, Yan X L, Qiao C G. Theories and Algorithms for VLSI Layout Design. Science Press, 1998.
Parkhurst J, Sherwani N, Maturi Set al. SRC physical design top ten problems. InProc. ACM International Symposium on Physical Design, Monterey, CA, USA, 1999, pp. 55–58.
Jing T, Hong X L, Cai Y Cet al. The key technologies and related research work of performance-driven global routing.J. of Software, 2001, 12(5): 677–688.
Ting B S, Tien B N. Routing techniques for gate array.IEEE Trans. CAD, 1983, 2(4): 301–312.
Chiang C, Sarrafzadeh M, Wong C K. Global routing based on Steiner Min-Max trees.IEEE Trans. CAD, 1990, 9(12): 1318–1325.
Chiang C, Sarrafzadeh M, Wong C K. A powerful global router: Based on Steiner Min-Max trees. InProc. IEEE/ACM International Conference on Computer-Aided Design, Santa Clara, CA, USA, 1989, pp. 2–5.
Shragowitz E, Keel S. A global router based on a multicommodity flow model.Integration, the VLSI J., 1987, 5: 3–16.
Meixner G, Lauther U. A new global router based on a flow model and linear assignment. InProc. IEEE/ACM International Conference on Computer-Aided Design, Santa Clara, CA, USA, 1990, pp. 44–47.
Vecchi M P, Kirkpatrick S. Global wiring by simulated annealing.IEEE Trans. CAD, 1983, 2(2): 215–222.
Sechen C, Sangiovanni-Vincentelli A. The Timber Wolf placement and routing package.IEEE J. SSC, 1985, 20(2): 432–439.
Kirkpatrick S, Jr. Gelatt C D, Vecchi M P. Optimization by simulated annealing.Science, 1983, 220(4598): 671–680.
Moosa Z, Brown M, Edwards D. An application of simulated annealing to maze routing. InProc. IEEE European Design Automation Conference, Grenoble, France, 1994, pp. 211–216.
Aarts E H L, Laarhoven P J M V. Statistical cooling: A general approach to combinatorial optimization problems.Philips J. Research, 1985, 40: 193–226.
Lundy M. Convergence of an annealing algorithm.Math Program, 1986, 34: 111–124.
Carden IV R C. Microelectronics global routing and feasibility estimation using a multicommodity flow approach [Dissertation]. San Diego, CA, USA, University of California, 1991.
Carden IV R C, Cheng C K. A global router using an efficient approximate multicommodity multiterminal flow algorithm. InProc. ACM/IEEE Design Automation Conference, San Francisco, CA, USA, 1991, pp. 316–321.
Carden IV R C, Li J M, Cheng C K. A global router with a theoretical bound on the optimal solution.IEEE Trans. CAD, 1996, 15(2): 208–216.
Huang J, Hong X L, Cheng C Ket al. An efficient timing-driven global routing algorithm. InProc. ACM/IEEE Design Automation Conference, Dallas, TX, USA, 1993, pp. 596–600.
Hong X L, Xue T X, Huang Jet al. TIGER: An efficient timing-driven global routing algorithm for standard cell and gate array design.IEEE Trans. CAD, 1997, 16(11): 1323–1331.
Bao H Y, Jing T, Hong X Let al. A novel random global routing algorithm independent of net ordering.Chinese J. Computers, 2001, 24(6): 574–579.
Sarrafzadeh M, Wong C K. An Introduction to VLSI Physical Design. McGraw Hill, USA, 1996.
Garey M R, Johnson D S. The rectilinear Steiner problem is NP-complete.SIAM J. on Appl. Math., 1977, 32(4): 826–834.
Gu J, Huang X F. Efficient local search with search space smoothing: A case study of the traveling salesman problem (TSP).IEEE Trans. Systems, Man, and Cybernetics, 1994, 24(5): 728–735.
Bao H Y, Hong X L, Cai Y Cet al. A hierarchical Steiner tree algorithm based on Dreyfus-Wagner method.Microelectronics & Computer, 1998, Ext. Iss: 41–44.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported partly by the National Hi-Tech Research and Development 863 Program of China under Grant No.2002AA1Z1460, Key Faculty Support Program of Tsinghua University under Grant No.[2002] 4, NSFC under Grant No.60121120706, and NSF of USA under Grant No.CCR-0096383.
JING Tong was born in 1966. He received the B.S. degree in electronic engineering, the M.S. and Ph.D. degrees in computer science and engineering from Northwestern Polytechnical University (NPU) in 1989, 1992 and 1999, respectively. From Sept. 1999 to Apr. 2001, he was a postdoctoral researcher of the Electronic Design Automation (EDA) Lab. at Department of Computer Science and Technology, Tsinghua University, Beijing, P. R. China. He is an associate professor there, and a IEEE member. From Dec. 2000 to Feb. 2001, he was a visiting scholar in University of California, San Diego (UCSD). His research interest is performance-driven layout. He has published more than 50 papers.
HONG XianLong was born in 1940. He is a professor at the Department of Computer Science and Technology in Tsinghua University, Beijing, P. R. China. His research interests include layout algorithms and systems.
BAO HaiYun was born in 1972. He is a Ph.D. candidate. His research interest is performance-driven global routing.
XU JingYu was born in 1976. She is a Ph.D. candidate. Her research interest is performance-driven global routing.
GU Jun received his B.S. degree in electrical engineering (with honors) from the University of Science and Technology of China in 1982 and his Ph.D. degree in computer science (with honors) from the University of Utah in 1989. Since 1994, he has been a professor of electrical and computer engineering at University of Calgary, Canada.
Rights and permissions
About this article
Cite this article
Jing, T., Hong, X., Bao, H. et al. SSTT: Efficient local search for GSI global routing. J. Comput. Sci. & Technol. 18, 632–639 (2003). https://doi.org/10.1007/BF02947123
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02947123