Abstract
This paper presents a comprehensive survey on global routing research over about the last two decades, with an emphasis on the problems of simultaneously routing multiple nets in VLSI circuits under various design styles. The survey begins with a coverage of traditional approaches such as sequential routing and rip-up-and-reroute, and then discusses multicommodity flow-based methods, which have attracted a good deal of attention recently. The family of hierarchical routing techniques and several of its variants are then overviewed, in addition to other techniques such as move-based heuristics and iterative deletion. While many traditional techniques focus on the conventional objective of managing congestion, newer objectives have come into play with the advances in VLSI technology. Specifically, the focus of global routing has shifted so that it is important to augment the congestion objective with metrics for timing and crosstalk. In the later part of this paper, we summarize the recent progress in these directions. Finally, the survey concludes with a summary of possible future research directions.[rule]
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1-49 |
| Number of pages | 49 |
| Journal | Integration, the VLSI Journal |
| Volume | 31 |
| Issue number | 1 |
| DOIs | |
| State | Published - Nov 2001 |
Bibliographical note
Funding Information:This paper presents a comprehensive survey on global routing research works, largely focusing on publications between 1983 and 2000. Due to the inherent difficulty of the problem and the increasingly complicated requirements resulting from advances in VLSI technology, global routing has been an active research area in the field of electronic design automation. Many academic and industrial researchers contributed to the numerous techniques and methods currently available. As in most cases, there is no perfect solution, and each method has its advantages and weaknesses. If one needs a simple and reasonably effective approach, perhaps rip-up-and-reroute is the best choice. When computation speed is a crucial issue, hierarchical methods can be applied. For cases that are very hard to solve, the multicommodity flow-based algorithm may be the best solution technique. Even though there is no completely satisfactory answer to the most basic congestion-driven global routing problem, the rapid progress in VLSI technology continues to impose new requirements on global routing. Currently, one of the most eminent problems is that of crosstalk avoidance in global routing. Except Zhou and Wong's work [84,85] and the post-processing method of Xu et al. [86] , few other works have been reported on crosstalk avoidance in global routing. Crosstalk avoidance in global routing has both the appealing feature of providing greater flexibility for optimization, and the difficulty of dealing with fuzzy information at the early routing stage. However, a simple observation tells us that the correlation between congestion and crosstalk may help to determine a satisfactory solution to this problem. For a specific grid cell boundary, it is generally true that greater congestion implies a greater probability of crosstalk effects. Therefore, at least we can have some probabilistic estimation on crosstalk for a cell boundary. Moreover, in comparison with delay optimization, crosstalk avoidance is less contradictory to the objective of congestion reduction. However, while congestion reduction usually can help to ease the crosstalk, the reverse is not true. Investigation on the correlation between the congestion and crosstalk may help to integrate crosstalk avoidance with congestion reduction into a unified approach. Another interesting candidate for future research is related to the area of interconnect planning, which is the notion of helping to transform the layout at an early stage to enable wire routes that reduce congestion, crosstalk, delay and other important objectives. One manifestation of this is in buffer planning. Since buffer insertion [87] is becoming a major technique for interconnect performance optimization and numerous buffers are projected for future designs [88] , buffer insertion greatly affects global routing. In order to ensure that there is no conflict between positions where buffer insertion is required and the locations of other placed cells, since spaces for buffer insertion are limited, the global routing must let the wires pass through the buffer-allowed regions so that buffer insertion optimization can be feasibly performed. Recently, buffer planning works [89–92] have been reported, and buffer congestion and wire congestion are simultaneously handled in Ref. [93] . Jiang Hu received the B.S. degree in optical engineering from Zhejiang University, Hangzhou, China, in 1990, the M.S. degree in physics from the University of Minnesota, Duluth, in 1997, and the Ph.D. degree in electrical engineering from the University of Minnesota, Minneapolis, in 2001. He is currently with IBM Microelectronics Division working on VLSI CAD tools development. His current research interest is on VLSI physical design, especially on interconnect routing, optimization and planning. Dr. Hu received a best paper award at the Design Automation Conference in 2001. Sachin Sapatnekar received the B.Tech. degree from the Indian Institute of Technology, Bombay in 1987, the M.S. degree from Syracuse University in 1989, and the Ph.D. degree from the University of Illinois at Urbana-Champaign in 1992. From 1992 to 1997, he was an assistant professor in the Department of Electrical and Computer Engineering at Iowa State University. He is currently an Associate Professor in the Department of Electrical and Computer Engineering at the University of Minnesota. He has coauthored two books, “Timing Analysis and Optimization of Sequential Circuits”, and “Design Automation for Timing-Driven Layout Synthesis”, and is a co-editor of a forthcoming volume, “Layout Optimizations in VLSI Designs”, all published by Kluwer. He has been an Associate Editor for the IEEE Transactions on VLSI Systems and the IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, has served on the Technical Program Committee for various conferences, as Technical Program and General chair for Tau and ISPD, and is currently a Distinguished Visitor for the IEEE Computer Society and a Distinguished Lecturer for the IEEE Circuits and Systems Society. He is a recipient of the NSF Career Award and best paper awards at DAC 1997, ICCD 1998, and DAC 2001.