21.

GRIP: Scalable 3D Global Routing Using

Integer Programming

Tai-Hsuan Wu, Azadeh Davoodi Jeffrey T. Linderoth

Department of Electrical and Computer Department of Industrial and Systems
Engineering Engineering
University of Wisconsin - Madison WI 53706
{twu3,adavoodi,linderoth}@[Link]

ABSTRACT Among the two-categories of concurrent [8], [20], [21], [15],

We propose GRIP, a scalable global routing technique via [4], [3], [5] and sequential [19], [22], [6], [18], [17] global
Integer Programming (IP). GRIP optimizes wirelength and routers, the latter has been more successful in terms of the
via cost without going through a layer assignment phase. tradeoff between solution quality and execution runtime. Se-
GRIP selects the route for each net from a set of candi- quential approaches have much smaller runtime but rely on
date routes that are generated based on an estimate of con- an ordering of the nets and applying rip-up and re-route.
gestion generated by a linear programming pricing phase. Much attention has been given to sequential approaches
To achieve scalability, the original IP is decomposed into because the concurrent ones are inherently more time con-
smaller ones corresponding to balanced rectangular subre- suming. The most recent concurrent approach is the IP-
gions on the chip. We introduce the concept of a floating based BoxRouter [8]. BoxRouter is extremely fast, but it
terminal for a net, which allows flexibility to route long nets only considers L-shaped routes in the IP. Recently [15] pro-
going through multiple subregions. We also use the IP to poses the use of a few more basic patterns for routing each
plan the routing of long nets, detouring them from congested net in a progressive congestion-driven IP formulation. Simi-
subregions. For ISPD 2007 benchmarks, we obtain 3.9% and larly, [15] also has the downside of only considering a limited
11.3% average improvement in wirelength and via cost for number of pre-determined patterns in the IP formulation.
the 2D and 3D versions respectively, compared to the best This in turn requires applying complicated pre- and post-
results reported in the open literature. processing steps to generate a final solution [8]. Also re-
cently [21] proposes a hierarchical IP formulation for GR.
Categories and Subject Descriptors However, as we discuss, the major downside of any hierar-
B.7.2 [Integrated Circuits]: Design Aids chical GR is failure to effectively account for the impact of
short nets. In this paper, we make the following contribu-
General Terms tions to overcome some of these challenges:
Algorithms, Design 1. We propose an IP formulation that simultaneously min-
Keywords imizes wirelength and via cost, thereby skipping the
traditional layer assignment phase. The IP works with
Global Routing, Integer Programming 3D Steiner routes and heavily penalizes overflow.
1. INTRODUCTION 2. Promising routes for each net are generated by a linear
Design of Integrated Circuits in nanometer regime is sub- programming pricing phase that takes into account a
ject to many obstacles such as manufacturability, variabil- measure of current congestion at each iteration. The
ity, yield-loss and timing failures. With increasing design IP decides among these many promising routes for each
sizes and shrinking device geometries, the severity of many net while considering capacity constraints.
of these issues is impacted by the routing of interconnects. 3. To achieve scalability, we decompose the chip area into
Global routing (GR) is the primary step of routing during rectangular subregions to achieve balanced and smaller-
which the net regions will be planned. It has increasingly sized IPs and then effectively integrates their solutions.
gained significance in recent years due to its larger role on The execution runtime depends on the number of sub-
the above-mentioned issues. It is crucial that the GR gener- regions, some of which can be processed in parallel.
ates a high-quality routing solution in a manageable runtime
4. We introduce the concept of floating terminals for a
that scales well with the design size.
net. Floating terminals allow flexibility in routing long
nets through subregions while remaining compatible
with our pricing phase for candidate route generation.
Permission to make digital or hard copies of part or all of this work for We also discuss a pricing procedure for planning the
personal or classroom use is granted without fee provided that copies are regions through which long nets will travel during the
not made or distributed for profit or commercial advantage and that copies decomposition of the IP into subregions.
bear this notice and the full citation on the first page. To copy otherwise, Compared to [3], our candidate routes are generated by vary-
to republish, to post on servers or to redistribute to lists, requires prior
ing a base Steiner route, considering congestion as weights in
specific permission and/or a fee.
DAC’09, July 26-31, 2009, San Francisco, California, USA a grid-graph as well as the other candidate routes generated
Copyright 2009 ACM 978-1-60558-497-3/09/07....10.00 so far at each iteration of column generation.

Authorized licensed use limited to: FUDAN UNIVERSITY. Downloaded 320

on January 19,2024 at 07:25:45 UTC from IEEE Xplore. Restrictions apply.
 In our simulation results, we achieve an average 11.3% has some “net-breaking” to define subproblems for scal-
improvement in total wirelength and via cost of 3D ISPD ability. (See Section 3).
2007 benchmarks, compared to the best result reported for 3. The slack variables si and the corresponding objective
each benchmark. This is due to the concurrent nature of our penalty factor M push the optimization to generate a
approach, the pricing phase for candidate route generation, no-overflow routing solution. The model is quite flex-
and directly working with the 3D model of the problem. ible, as with minor modifications, the integer program
The organization of the paper is as follow. In Section 2, can be set to minimize the total overflow.
we discuss the IP formulation and customized column gener-
A significant disadvantage of the formulation (ILP-GR)
ation procedure. In Section 3, we discuss IP decomposition,
is its size. First, for a given net Ti , the number of decision
subregion extraction, long net planning, and subregion so-
variables for this net is equal to |T (Ti )|—the number of pos-
lution integration. Simulation results are in Section 4.
sible Steiner trees connecting the terminals in Ti . Second,
the number of nets N may also be very large. Nevertheless,
2. PRICE AND BRANCH FOR GR we use (ILP-GR) as the basis of our GR algorithm. In the
The algorithm proposed for global routing is based on subsequent discussion, we outline the manner in which we
the (approximate) solution of a large-scale integer program deal with the issues posed by large formulation size.
(IP). The solution procedure begins with a column genera-
tion (pricing) phase, followed by branch-and-bound. 2.2 Column Generation
The first step in an IP-based approach to global rout-
2.1 An Integer Program for the GR Problem ing is to solve the linear-programming (LP) relaxation of
In a mathematical description of the global routing prob- (ILP-GR), a relaxation obtained by replacing the binary re-
lem, we are given a grid-graph G = (V, E) describing the quirement on the variable xit ∈ {0, 1} with a nonnegativity
network topology, a set of (multi-terminal) nets given by restriction 0 ≤ xit ≤ 1. The linear program is solved by a
N = {T1 , T2 , . . . , TN }, (with Ti ⊂ V ), and edge capacities column-generation (CG) procedure [11, 12].
ue and weights ce ∀e ∈ E. Denote by T (Ti ) the collection To describe the column generation procedure it is helpful
of all Steiner trees (routes) connecting the terminals in Ti , to consider the dual (LPD-GR) of the linear programming
and let the parameter ate = 1 if Steiner tree t contains edge relaxation of (ILP-GR):
e ∈ E, ate = 0 otherwise. Define the binary decision vari-  
able xit that is equal to 1 if and only if net Ti is routed with max λi + πe ue (LPD-GR)
λ≤M,π≤0
route t ∈ T (Ti ). An integer program for the global routing i∈N e∈E
problem can be written as 
N  
N s.t. λi + πe ≤ cit ∀i = 1, . . . , N, ∀t ∈ T (Ti ). (1)
min cit xit + M si (ILP-GR) et
x,s
i=1 t∈T (Ti ) i=1
In a column generation procedure, only a small subset of all
⎧  possible routes is explicitly included in the LP relaxation of
⎪
⎪ (Ti ) xit + si = 1 ∀i = 1, . . . , N (ILP-GR). Let S(Ti ) ⊂ T (Ti ) be the set of routes considered
⎨ t∈T
N 
i=1 t∈T (Ti ) a te x it ≤ ue ∀e ∈ E for net Ti . The restricted master problem for (ILP-GR) is
⎪
⎪ xit = {0, 1} ∀i = 1, . . . , N, ∀t ∈ T (Ti ),
⎩ 
N  
N
si ≥ 0 ∀i = 1, . . . , N . min cit xit + M si (RMLP-GR)
x≥0,s≥0
The parameter cit is the cost of route t for net Ti which is i=1 t∈S(Ti ) i=1

computed as the total length of the 3D route, cit = et ce ,  

where the notation e  t denotes that edge e ∈ E is con- xit + si = 1 ∀i = 1, . . . , N
t∈S(T
N 
i)
tained in route t ∈ T (Ti ). The first set of equations in the i=1 t∈S(Ti ) ate xit ≤ ue ∀e ∈ E.
model enforces the routing of each net. The decision vari-
able si will be positive if net Ti cannot be routed, and the Solving (RMLP-GR) yields a (primal) solution (x̂, ŝ) as well
objective function trades off the total routing length with as values λ̂ ≤ M and π̂ ≤ 0 for the dual variables in
the number of nets that are routed. Typically M is chosen (LPD-GR). By linear programming duality, if the solution
sufficiently large to ensure that all nets are routed. The sec- (λ̂, π̂) satisfies all the dual constraints (1), then (x̂, ŝ) is an
ond set of equations in the model ensure that the given edge optimal solution to the LP relaxation of (ILP-GR). If not,
capacities are not exceeded. The formulation (ILP-GR) has then the violated dual constraint suggests a column (vari-
a number of appealing properties. able) that may be added to (RMLP-GR) to reduce its ob-
1. The exact properties of the route, such as topology jective value.
and metal layer can be incorporated into the “cost” of To determine if the dual solution (λ̂, π̂) is feasible, we
a route. The objective is to minimize this cost. The must
 determine if there exists a route t ∈ T (Ti ) with λ̂i +
formulation can thus handle the 3D GR problem to et π̂e > cit . This is itself an optimization problem, known
include both wirelength and via cost as the cost of a as the pricing problem, that can be decomposed into in-
route. It then avoids a traditional layer-assignment dependent problems for each individual net i = 1, . . . , N .
phase which can be a source of sub-optimality. Specifically, given net Ti , for each edge e ∈ E define the bi-
2. The formulation does not require that the nets be a nary decision variables te , taking value 1 if and only if edge
priori broken into two-terminal segments. Breaking e is used in a route for net Ti . The pricing problem for net
nets before doing routing can be a significant source of Ti is then

sub-optimality in the resulting final routing [19]. We min{ (ce − π̂e )te | t ∈ T (Ti )}. (PP(Ti ))
note that the final version of our proposed algorithm t
e∈E

Authorized licensed use limited to: FUDAN UNIVERSITY. Downloaded 321

on January 19,2024 at 07:25:45 UTC from IEEE Xplore. Restrictions apply.
 
Let t∗ be an optimal solution to (PP(Ti )). If e∈E π̂e t∗e +
 ∗ ∗ v
e∈E ce te < λ̂i , then t identifies a violated constraint (1)
in (LPD-GR), and the current solution to (RMLP-GR) can
u
be improved. The CG procedure is summarized as follows:
Figure 1: Improving routes via a shortest path al-
0. For each i = 1, . . . , N , initialize S(Ti ) with at least
gorithm on a weighted grid-graph
one route. (In our implementation, we use the route
generated for net Ti by the package Flute [9]). An important component of our pricing algorithm for a
given net Ti is the selection of the starting terminals from
1. Solve (RMLP-GR), yielding primal solution (x̂, ŝ) and which Dijkstra’s algorithm to identify improving routes is
dual values (λ̂, π̂). run. In our implementation, Dijkstra’s algorithm is run us-
2. For each i=1,. . . , N , solve (PP(Ti )), yielding a route ing the most congested terminals as starting points.
  We identify these congested terminals as follows. For each
t∗ . If λ̂i + e∈E π̂e t∗e > e∈E ce te , then Si = Si ∪{t∗ }.
terminal we compute the weight of the path P  that connects
3. If improving routes for some net Ti were found, return it to the base Steiner tree. The most congested terminals are
to step 1. Otherwise, stop—the solution (x̂, ŝ) is an those for which the corresponding P  has maximum weight.
optimal solution to the LP relaxation of (ILP-GR).
2.4 Selecting Nets to Price
In order to speed solution time, we typically stop the pro- For large instances of (ILP-GR), the CG procedure can be
cedure once the solution value has “tailed off.” Specifically, significantly accelerated by only solving the pricing problem
if the objective value of (RMLP-GR) has made little or no (PP(Ti )) for a subset of all the nets. To select the nets
improvement in the last 10 iterations, the CG procedure is Ti ∈ N for which (PP(Ti )) is solved, our procedure takes
terminated. advantage of information provided by the solution of the
restricted master problem. Specifically, if ŝi > 0, then the
2.3 Solving the Pricing Problem net Ti is not completely routed using the existing routes in
In the pricing phase (step 2) of the CG procedure, small- Si , so net Ti is priced by step (2) of the CG procedure.
weight Steiner trees with respect to the weights ŵe = ce − Nets for pricing are also selected based on measures of con-
π̂e must be identified. Finding a minimum-weight Steiner gestion in the current LP solution to (RMLP-GR). Conges-
tree is in general NP-Hard [14], so our approach for find- tion may be identified in one of two ways. First, congested
ing columns that reduce the optimal value of (RMLP-GR) edges are those edges e that have the most negative value
is based on local search. Given a dual solution (λ̂, π̂), the of π̂e . The intuition behind this choice is that π̂e provides
 the rate of change in the objective function of (RMLP-GR)
reduced cost of route t of net Ti is c̄it = cit − λ̂i − et π̂e .
Note that the pricing problem (PP(Ti )) can be viewed as a per unit additional capacity on edge e. A second way to
procedure for identifying a Steiner tree t for net Ti whose identify a congested edge is to let ri ∈ arg maxt∈S(Ti ) x̂ti
reduced cost c̄it < 0. By the complementary slackness con- be the route for net Ti with the Nlargest solution value in
ditions of linear programming, for any optimal solution (x̂, ŝ) (RMLP-GR). The value ηe = i=1 ari e is the number of
units of capacity on edge e that would be used if the routes
to (RMLP-GR) and corresponding dual solution (λ̂, π̂), the
ri were used for each net Ti ∈ N . If the value (ηe − ue ) is
reduced cost c̄it = 0 if x̂it > 0.
large, then edge e is highly-congested. In our algorithm, a
Our local improvement procedure for solving (PP(Ti ))
bounding box around a congested edge e (identified by either
uses this fact as well as the following simple observation.
of the two measures) is created, and all nets Ti that contain
Given a route t ∈ S(Ti ), let V (t) be the set of vertices in t.
a terminal inside the bounding box are also candidates to
If the variable x̂it > 0, and if there exists a path P  from
be priced by (PP(Ti )) in step 2 of the CG procedure.
some terminal u ∈ Ti to a vertex v ∈ V (t) such that the
weight of P  (with respect to weights ŵ) is less than the 2.5 Branch and Bound
weight of the path P from u to v using edges in t, the re- Once the CG procedure for the solution of the LP relax-
duced cost of tree t = t ∪ P  \ P is negative. Thus, adding ation of (ILP-GR) is complete, either because no improv-
the variable corresponding to route t to (RMLP-GR) may ing routes were found in the pricing phase, or because an
reduce its objective value. Figure 1 demonstrates how new iteration limit was reached, a promising candidate subset
routes can be constructed by finding short u-v paths from of routes S(Ti ) ⊂ T (Ti ) has been identified for each net
u ∈ Ti to a vertex v on the base Steiner tree. An interesting Ti . Using only these route variables, the integer program
feature of this pricing algorithm is that the new routes can (ILP-GR) is formulated and solved by the commercial in-
use different Steiner points than the original routes. teger programming solver CPLEX (v9) [10]. The solution
To approximately solve (PP(Ti )) for a net Ti , our pro- returned by CPLEX is a feasible solution to the problem.
cedure starts with the tree t ∈ S(Ti ) with largest value of The proposed approach, based on the direct solution of
x̂ti . Using edge weights ŵe = ce − π̂e , a single-source short- (ILP-GR), has significant promise to improve the solution
est path problem from some terminal u ∈ Ti to each vertex quality of existing GRs. For example, using this approach,
v ∈ V (t) is solved. If the uv path length is smaller than the we solved the 2D IBM01 circuit of the ISPD1998 suite [1]
existing path length, a new route has been identified. and were able to improve the wirelength by approximately
Dijkstra’s single-source shortest path algorithm [13] gen- 5% compared to the best solution found by FGR [19], with-
erates an entire tree of shortest path weights, thus possi- out any overflows. However, the runtime to achieve this
bly identifying many routes that would reduce the objective high-quality solution was prohibitively long—a few hours.
value of (RMLP-GR). In our implementation, we add a Thus, in the following section, we discuss mechanisms for
pre-specified maximum number of routes selected uniformly decomposing the full global routing (ILP-GR) into smaller
from the set of all identified negative cost routes per net. instances in order to accelerate the overall runtime.

Authorized licensed use limited to: FUDAN UNIVERSITY. Downloaded 322

on January 19,2024 at 07:25:45 UTC from IEEE Xplore. Restrictions apply.
3. DECOMPOSITION FOR SCALABILITY floating
terminals
Many existing global routing algorithms define reasonably-
sized subproblems and create a full global routing out of so-
auxiliary
lutions to these subproblems. For example, to achieve a good nodes
runtime, BoxRouter [8] starts by solving an IP over a small
rectangular box on the chip and then progressively increases
(a) (b)
the size of the box to generate new IPs, fixing the solution
to the previous IP. Fixing the solution of previous IP when Figure 2: Modifying grid-graph of a subregion to
increasing the box size may lead to a degradation in solution handle floating terminals within our IP procedure.
quality. SideWinder [15] solves an IP over the entire chip by
gradually introducing more base patterns for the nets in the Each subregion defines a new grid-graph G (V  , E  ) and
congested areas at each iteration. However, Sidewinder only set of nets N  ⊂ N . The set N  is composed of two types
works with three simple-shaped patterns which are defined of nets, nets that have all terminals inside the subregion
a priori. The work [21] proposes a hierarchical IP approach (Ti ⊆ V  ), and nets that have at least one terminal outside
that first solves a small IP to plan the routing of the longest the subregion (Ti ⊆ V  ). Figure 2(a) shows the latter type of
nets. However, the impact of the shorter nets is neglected. these nets. The net in the figure belongs to three different
As demonstrated in Section 2, our proposed algorithm for subregions. The common boundaries of these subregions
global routing has potential to find high-quality solutions, are shown in bold. Considering the top-right subregion, we
but also requires a mechanism to accelerate the procedure. can think of having a net with one fixed and two “floating”
In this section, we first discuss a decomposition of the in- terminals. Each floating terminal represents a portion of a
teger program (ILP-GR) into smaller ones that correspond subregion boundary through which the net will connect to
to non-overlapping rectangular “subregions” on the chip. We another subregion.
introduce the concept of “floating-terminals” to define the IP To specify such nets in our IP, we represent each float-
of each subregion, providing significant flexibility for routing ing terminal using an auxiliary node. The auxiliary node
nets that might enter or exit that subregion. We then discuss is added to the set of nodes V  in the grid-graph. Edges
effective integration of the subregion solutions to generate a connecting the nodes that are on the subregion boundary
valid and high quality final solution. Finally, we discuss a to their corresponding auxiliary node are added to the set
technique to plan long nets that pass multiple subregions. E  . The added edges have infinite capacity and zero cost in
3.1 Subregion Extraction / IP Decomposition the definition of the integer program (ILP-GR). Figure 2(b)
The goal of our decomposition procedure is to define non- illustrates the addition of auxiliary nodes and edges. Af-
overlapping rectangular subregions on the chip. Each sub- ter applying this simple construction, the integer program
region defines the boundaries of a smaller-sized GR prob- (ILP-GR) is well-defined, and can be solved by the proce-
lem which we solve using the IP-based procedure outlined dure outlined in Section 2.
in Section 2. The objective of the subregion definition is to The example of Figure 2 is for 2D routing, but in the gen-
define balanced subregions, resulting in “equally-difficult” op- eral 3D case, each boundary of a subregion is a plane and
timization problems that take approximately the same time graph G extends to the third dimension. The nodes on this
to solve. We first tried a coarse, uniform grid to define the vertical boundary plane are connected to their correspond-
subregions. However, we noticed that the IPs corresponding ing auxiliary node.
to the congested subregions were taking significantly longer
time to be solved by our procedure (e.g., hours for congested 3.2 Handling Long Nets
subregion and minutes for the less congested ones). In our subregion extraction procedure, the regions through
To decrease the gap in solution times, our procedure at- which net Ti are routed, and hence the locations of floating
tempts to create subregions having the same average edge terminals for Ti are taken from a given Steiner topology
utilization (AEU). To define the AEU, we first assume that (e.g., the route generated by Flute for Ti ). Even though the
all nets are routed using the Steiner route generated by [9] subregion IP has significant flexibility in implementing the
in the 2D-projected problem. For each edge, we define a uti- routes that connect floating terminals, the entire procedure
lization factor as the ratio of the number of routes that cross relies on knowing the assignment of each net to one or more
the edge to the edge capacity. Many edges might have a uti- subregions. For long nets that are assigned to more than two
lization factor higher than one, indicating an overflow. For subregions, the subregion assignment issue becomes particu-
a subregion, the AEU is the the average utilization factor of larly important. (This is in spite of the fact that the number
all edges contained in the subregion. of subregions is typically much smaller than the number of
The subregions are defined using a partitioning-based strat- bins of the routing grid). Figure 3 illustrates this point. The
egy, depicted graphically in Figure 3. We recursively apply two long nets are routed using their Steiner routes, both of
bi-partitioning to subregions to obtain two new smaller-sized which pass from subregion A. If A is congested, it is better
subregions, at each step ensuring that the generated subre- to detour these nets from A.
gions have similar AEU. During one bi-partitioning step,
to decide between a vertical or horizontal partitioning, we
choose the one that results in the smaller aspect ratio of A
B
the generated subregions. The partitioning of a subregion is
stopped when any of its sides reaches 32 units of the routing
grid, a size empirically set to generate an IP that can be
typically solved by the procedure outlined in Section 2 in an Figure 3: Assigning long nets to subregions using an
acceptable runtime. initial Steiner route can cause unresolvable overflow.

Authorized licensed use limited to: FUDAN UNIVERSITY. Downloaded 323

on January 19,2024 at 07:25:45 UTC from IEEE Xplore. Restrictions apply.
 Temporarily fix the nets first Steiner point
using the Steiner routes Extract subregions
generated by Flute
i=0
Detour long net segments
from subregion i
i++
fixed terminal
Solve IP for subregion i
Figure 5: We remove the segment connecting the
fixed boundary terminal (previously floating) to the
Figure 4: Dynamic planning of long nets first Steiner point in the route backbone. We
reroute these connecting segments given the fixed
boundary terminals using our IP procedure.
Many procedures for assigning the subregions of long nets
were investigated. First, similar to [21], we tried a stan- In phase 1, we visit and process the subregions in the
dard hierarchical IP formulation in terms of long nets. This following order. We first compute the total edge overflow
approach helped considerably with the removal of overflow, (TEO) based on the initial Flute Steiner-routes in each sub-
but its failure to accurately consider the impact of short nets region. Subregions are then processed in decreasing order
falling completely inside a subregion led to poor quality so- of their TEOs. Every time a subregion is solved, the float-
lutions in terms of wirelength. Instead, we use the procedure ing terminals for a net Ti will get fixed at a boundary of the
depicted in Figure 4, which is explained below: region. Specifically, the net Ti is partially routed, and subse-
quent subregion IPs must respect this partial routing. If two
1. Before extracting the subregions, all nets are broken consecutive subregions (in terms of TEO) are not physically
into two-terminal segments using the Steiner trees gen- adjacent, we process them in parallel.
erated by Flute. Phase 1 fixes the locations of the floating terminals on
the subregion boundaries and also generates an initial rout-
2. Next, the subregion extraction begins. The routes used
ing solution. For this routing solution, we fix all the (short)
to compute the AEU during subregion extraction are
nets that completely fall within a subregion. For the (long)
those generated by step 1.
nets covering more than one subregion, we fix a “backbone”
3. Once the subregions are created, we begin solving the inside each of its subregions as follows. For a long net we
IPs for each subregion in a congestion-based order that visit each of its subregions. Inside each subregion, we remove
is discussed in the next subsection. Before solving a the “branch” that connects the fixed terminal on the subre-
subregion IP, we use a procedure to detour as many gion boundary to the route backbone. Figure 5 illustrates.
long nets that pass from the subregion as possible. Considering the route that goes within two subregions, for
Once a subregion is solved, its solution remains fixed. each subregion, we remove the segment that connects the
Before solving the IP for the next subregion, we apply identified fixed terminal on the boundary to the backbone
the same procedure to detour as many passing nets as of the route. Specifically, the removed segment is one that
possible to the remaining subregions. connects the boundary terminal to the first Steiner point of
the route in the subregion.
To detour long net segments outside a subregion, as required In phase 2, once these “connecting segments” are removed,
by step 3, we apply a shortest path algorithm on the grid- routing resources will be freed and we reconnect these seg-
graph. We set the edge weights inside the target subregion to ments using the formulation (ILP-GR) while fixing the routes
a large number to avoid getting re-routed inside that subre- of short nets and backbones of long nets from phase 1.
gion. Also, outside the target subregion, the edges that have In summary, our procedure uses the IP formulation of
overflow will also have a large weight. The weights of the Section 2 as a basic component throughout the routing pro-
grid-graph gets updated every time a long net is detoured. cess. Subregion extraction aims to generate equally-difficult
Our procedure provides two significant benefits. First, it optimization problems. Subregions are initially solved while
detours the long nets dynamically, every time a new subre- using the flexibility of floating terminals on their boundaries
gion is processed. Second, it considers an estimate of the as they are visited in the order of their TEO. After the initial
current congestions based on continually updating the edge phase, all the short nets and the backbone of long nets within
weights to detour long nets. each subregion are routed. In addition, the locations of the
floating terminals on the subregion boundaries will get fixed
3.3 Subregion Integration to ones that ensure obtaining a feasible solution. The final
So far we explained how the subregions are extracted and phase effectively connects the backbones of the long nets in
the long nets are dynamically planned. We then finalize the different subregions. In our simulation results, we observed
routing solution using a two-phase approach. In the first significant improvement in solution quality from phase 2 for
phase, we fix the locations of the floating terminals and gen- connecting the subregions using integer programming.
erate a routing solution for all the routes that completely The result is a scalable, effective global router, called
fall within a subregion. For the routes that cover more than GRIP (Global Routing via Integer Programming). GRIP
one subregion, we fix a “backbone” inside each of its sub- is a robust tool and does not rely on any design-dependent
regions. In the second phase, we connect the backbones of tuning. Everything is based on integer programming. The
these longer nets in adjacent subregions. This two-phase ap- defined parameters AEU (for defining subregions) and TEO
proach is entirely based on integer programming and solved (for ordering them) both depend on our congestion estimate
using formulation (ILP-GR) as we elaborate next. which is only based on the Flute-Steiner routes.

Authorized licensed use limited to: FUDAN UNIVERSITY. Downloaded 324

on January 19,2024 at 07:25:45 UTC from IEEE Xplore. Restrictions apply.
 Table 1: Results for ISPD 2007 benchmarks. Table 2: Our grid size, subregion count and runtime
Benchmark Best Approach GRIP benchmark #nets grid #subregions 2D 3D
tool TOF WL TOF WL %Impr adaptec1 176715 324x324 91 290 440
adaptec1.2D FGR 0 54.7 0 52.8 3.5 adaptec2 207972 424x424 169 229 366
adaptec2.2D FGR 0 52.4 0 50.1 4.4 adaptec3 368494 774x779 562 262 387
adaptec3.2D FGR 0 131.5 0 125.9 4.3 adaptec4 401060 774x779 558 240 398
adaptec4.2D FGR 0 125 0 122.1 2.3 adaptec5 548073 465x468 199 410 688
adaptec5.2D FGR 0 153.2 0 144.5 5.7 newblue1 270713 399x399 137 319 513
newblue1.2D FGR 400 46.3 0 44.9 3.1 newblue2 373790 557x463 242 230 296
newblue2.2D FastRoute 0 76.4 0 73.2 4.1 newblue3 442005 973x1256 1162 701 1389
newblue3.2D NTHU-R 31454 110.8 35573 107.9 N/A
adaptec1.3D FGR 0 88.6 0 78.9 10.94 5. CONCLUSIONS
adaptec2.3D FGR 0 90.1 0 80.7 10.41 We presented GRIP, a tool for global routing using inte-
adaptec3.3D FGR 0 200.6 0 182.2 9.17
adaptec4.3D FGR 0 183.0 0 167.7 8.36 ger programming. We introduced a novel IP formulation to
adaptec5.3D NTHU-R 0 260.2 0 227.8 12.45 select candidate routes for each net based on a continually-
newblue1.3D NTHU-R 0 91.0 0 78.1 14.14 updated congestion metric, while directly working with the
newblue2.3D FGR 0 132.5 0 114.7 13.46
newblue3.3D NTUgr 31454 167.0 33158 162.7 N/A
3D model of the routing problem. To achieve reasonable
runtime, we discussed subregion extraction and IP decom-
4. SIMULATION RESULTS position as well as a method for planning long nets and in-
tegrating the subregion solutions.
We implemented GRIP using C++. For solving individual
LPs and IPs we used CPLEX (v9) [10]. We demonstrate 6.[1] ISPD
REFERENCES
1998 global routing benchmark suite, 1998.
the performance of GRIP on the ISPD 2007 benchmarks
[2] ISPD global routing contest and benchmark suite, 2007.
[2]. Table 2 reports the total number of routed nets and the [3] C. Albrecht. Global routing by new approximation algorithms
grid size for each benchmark. Each benchmark has a 3D as for multicommodityflow. IEEE TCAD, 20(5):622–632, 2001.
well as a projected-2D version, and the grid size is the same [4] L. Behjat and A. Chiang. Fast integer linear programming
in both versions. The 2D and 3D benchmarks have two and based models for VLSI global routing. In ISCAS (6), pages
6238–6243, 2005.
six metal layers, respectively. [5] M. Burstein and R. Pelavin. Hierarchical wire routing. IEEE
We compare the summation of wirelength and via cost TCAD, 2(4):223–234, 1983.
(denoted by WL) in Table 11 . The comparison is made [6] Y.-J. Chang, Y.-T. Lee, and T.-C. Wang. Nthu - route 2.0: A
against the best reported solution for each benchmark, found fast and stable global router. In ICCAD, pages 338–343, 2008.
[7] H.-Y. Chen, C.-H. Hsu, and Y.-W. Chang. High-performance
by either FGR 1.1 [19], NTHU-Route 2.0 [6], FastRoute 3.0 global routing with fast overflow reduction. In ASPDAC, pages
[22] or NTUgr [7]. For the 2D and 3D benchmarks, we 582–587, 2009.
obtained an average improvement of 3.9% and 11.3%. The [8] M. Cho, K. Lu, K. Yuan, and D. Z. Pan. Boxrouter 2.0:
architecture and implementation of a hybrid and robust global
improvement in the 3D benchmarks were more significant router. In ICCAD, pages 503–508, 2007.
than in the 2D case, because GRIP considers explicit 3D [9] C. C. N. Chu and Y.-C. Wong. Flute: Fast lookup table based
Steiner routes, skipping the layer assignment phase. rectilinear Steiner minimal tree algorithm for VLSI design.
The total overflow (denoted by TOF) is also given in Ta- IEEE TCAD, 27(1):70–83, 2008.
ble 1. The GRIP solutions had zero overflow for all the [10] CPLEX Optimization, Inc., Incline Village, NV. Using the
CPLEX Callable Library, Version 9, 2005.
benchmarks except newblue3 which is known to be unroutable. [11] G. Dantzig and P. Wolfe. Decomposition principle for linear
For newblue3 we report NTUgr as the best tool only because programs. Operations Research, 8:101–111, 1960.
it generates the smallest overflow (and not the smallest WL). [12] J. Desrosiers and M. E. Lübbecke. A primer in column
Table 2 reports the running time (wall clock time) of both generation. In G. Desaulniers, J. Desrosiers, and M. M.
Solomon, editors, Column Generation, chapter 1. Springer,
2D (column 5) and 3D (column 6) benchmarks. The runtime 2005.
unit is minutes. The number of subregions created by the [13] E. W. Dijkstra. A note on two problems in connetion with
subregion extraction procedure described in Section 3.1 for graphs. Numerische Mathematik, 1:269–271.
[14] M. R. Garey and D. S. Johnson. The rectilinear Steiner tree
each benchmark is given in column 4. In reporting the run- problem is NP-complete. SIAM Journal of Applied Math,
times we process independent subregions in parallel, which 32:826–834, 1977.
is why wall time is the appropriate measure. GRIP was run [15] J. Hu, J. A. Roy, and I. L. Markov. Sidewinder: a scalable
on a heterogenous grid of CPUs, shared by many users, and ILP-based router. In SLIP, pages 73–80, 2008.
controlled by the Condor grid computing toolkit [16]. When [16] M. J. Litzkow, M. Livny, and M. W. Mutka. Condor—A hunter
of idle workstations. In Proceedings of the 8th International
solving the IP formulation, the majority of runtime was Conference on Distributed Computing Systems, pages
spent on the linear program (for column generation) rather 104–111, 1998.
than solving the integer program using branch-and-bound. [17] M. D. Moffitt. Maizerouter: Engineering an effective global
router. In ASPDAC, pages 226–231, 2008.
This helped us to effectively identify candidate routes; the [18] M. M. Ozdal and M. D. F. Wong. Archer: a history-driven
number of candidate routes reached up to a hundred for global routing algorithm. In ICCAD, pages 488–495, 2007.
some nets, while for some nets only a few routes were gener- [19] J. A. Roy and I. L. Markov. High-performance routing at the
ated in the linear program. Overall, our runtimes are scal- nanometer scale. In ICCAD, pages 496–502, 2007.
[20] T. Terlaky, A. Vannelli, and H. Zhang. On routing in VLSI
able and adjustable, since they depend on the number of design and communication networks. Discrete Applied
subregions we chose to create. Continuing work is aimed at Mathematics, 156(11):2178–2194, 2008.
further exploiting parallelism to obtain similar high-quality [21] Z. Yang, S. Areibi, and A. Vannelli. An ILP based hierarchical
solutions in a smaller run time. global routing approach for VLSI ASIC design. Optimization
Letters, pages 281–297, 2007.
[22] Y. Zhang, Y. Xu, and C. Chu. Fastroute3: a fast and high
1
Benchmark solutions are available for download at: quality global router based on virtual capacity. In ICCAD,
[Link] pages 344–349, 2008.

Authorized licensed use limited to: FUDAN UNIVERSITY. Downloaded 325

on January 19,2024 at 07:25:45 UTC from IEEE Xplore. Restrictions apply.