The “background” description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description which may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present invention.
The advances in nanometer Very Large Scale Integration (VLSI) have produced chips that contain billions of transistors within a very small die area. For example, the Intel Xeon processor uses a feature size of 20 nm and has over 5 billion transistors within a die size of just 661 mm2. Chip limitations include interconnections between die because the devices have very small feature sizes. The routing step in the physical design of Integrated Circuits (ICs) is responsible for determining a suitable path for the interconnections. The interconnections are deposited or printed on the chip in order to connect different components. The routing process improves the chip timing as well as production costs. However, routing has become complex due to the presence of a very large number of components within a very small die area and a very small space available for interconnections.
The complexity of routing is reduced by dividing it into two steps, which are (a) global routing and (b) detailed routing. Global routing determines approximate paths for the interconnections and is a Non-deterministic Polynomial-time (NP)-hard problem. See T. Lengauer, Combinatorial Algorithms for integrated Circuit Layout. New York: John Wiley & Sons, Inc., 1990; S. M. Sait and H. Youssef, VLSI Physical Design and Automation: Theory and Practice. Singapore: World Scientific Publishers, 1999; Iterative Computer Algorithms with Applications in Engineering. California: IEEE Computer Society Press, 1999, each incorporated herein by reference in their entirety. In global routing, nets of wires (i.e. interconnections) are mapped to a coarse grid of global routing cells. Each global routing cell has a fixed horizontal and vertical capacity. An objective of global routing is to assign the nets while satisfying capacity constraints (horizontal and vertical) of the global routing cells. Each net is routed by generating a spanning tree that covers all of its pins. Detailed routing assigns segments of interconnections to specific routing tracks, vias, and metal layers in a manner which is consistent with the solution of global routing.
The International Symposium on Physical Design (ISPD) has conducted global routing contests in 2007 and 2008 and proposed several benchmarks for the nanometer scale VLSI global routing. See “ISPD 2007 global routing contest announcements;” G.-J. Nam, M. Yildiz, D. Z. Pan, and P. H. Madden, “ISPD placement contest updates and ISPD 2007 global routing contest,” in Proceedings of the 2007 international symposium on Physical design, Austin, Tex., 2007, pp. 167-167; and “ISPD 2008 global routing contest,” 2008, each incorporated herein by reference in their entirety.
Modern global routers generally include two processing steps. The first step is an initial routing of all nets in which the nets have been routed with little or no effort to minimize congestion. The second step is the-Rip-up and Re-route (R&R) in which congestion is minimized or eliminated from the solution through ripping-up and re-routing the nets whose spanning tree has at least one congested edge. A conventional R&R process includes sequentially ripping-up and re-routing nets in a predetermined order. However, global routing problems are becoming complex, making it necessary to employ many enhancement techniques in the R&R process.
The R&R process in modern global routers includes many different types of enhancements in order to solve complex and large-size problems. The R&R process attempts to find a valid solution (i.e., a solution whose total overflow is zero), as well as minimize the wire length of the solution. A solution whose total overflow is zero is very likely to be successfully routed in the subsequent detailed routing step. The wire length of a solution has an effect on chip delay and manufacturing cost. Therefore, solutions of smaller wire length are highly desirable. The R&R processes of existing global routers can minimize the total overflow and wire length up to a certain extent, but they subsequently produce little or no improvement in total overflow and wire length.
FIG. 1 is a graph illustrating overflow versus runtime for a test case in which a benchmark is solved using a global router NCTU-GR 2.0. The global router has reduced the total overflow during the first hour, but could not make any further progress. These observations indicate that the R&R process requires enhancement.