nt> Yahoo! is not affiliated with the authors of this page or responsible for its content.
Via-Aware Global Routing for Good VLSI Manufacturability and High Yield *
Via-Aware Global Routing for Good VLSI Manufacturability
and High Yield *


Yang Yang, Tong Jing, Xianlong Hong, Yu Hu Qi Zhu Xiaodong Hu, Guiying Yan
Computer Science & Technology Dept. EECS Dept. Inst Applied Math
Tsinghua Univ. UC at Berkeley CAS
Beijing, P. R. China U. S. A. Beijing, P. R. China


Abstract

CAD tools have become more and more important
for integrated circuit (IC) design since a complicated
system can be designed into a single chip, called
system-on-a-chip (SOC), in which physical design tool
is an essential and critical part. We try to consider the
via minimization problem as early as possible in
physical design. We propose a routing method focusing
on minimizing vias while considering routability and
wire-length constraint. That is, in the global routing
phase, we minimize the number of bends, which is
closely related to the number of vias. Previous work
only dealt with very small nets, but our algorithm is
general for the nets with any size. Experimental results
show that our algorithm can greatly reduce the count
of bends for various sizes of nets while meeting the
constraints of congestion and wire-length.




1. Introduction

Nowadays, the seriousness about effects of very
deep-submicron (VDSM) technology has led to a
greater and greater reliance on CAD tools in VDSM
physical design [1]-[3]. Global routing is an essential
part of physical design. It usually includes multiple
optimization goals. Congestion and wire-length have
long been focuses of research [4]-[7]. Besides,
interconnection delay [8]-[9] is an important issue for
high-performance routing.
While very large scale integrated circuits (VLSI)
feature size continues to shrink in the VDSM regime,
the number of vias becomes a critical issue, which has
a great effect on the circuit performance, layout size


* This work was supported in part by the NSFC under Grant
No.60373012, the SRFDP of China under Grant No.20020003008,
and the Hi-Tech Research and Development (863) Program of China
under Grant No.2004AA1Z1050.
and yield rate. In order to reduce the yield loss by via
failure, [10] proposed a redundant-via enhance maze
routing algorithm. On the other hand, minimizing the
count of vias is also an effective method to reduce the
yield loss, and moreover, it can meanwhile improve the
circuit performance and layout size. Traditionally, via
minimization is done in the detailed routing phase or
layer assignment [4], [11]-[12]. However, when the
size of design features keeps decreasing and the
complexity of circuits keeps increasing, it will be more
flexible and effective to minimize the number of vias
as early as in the global routing phase.
In the global routing phase, bends denote both the
corner points and the Steiner points in a Steiner tree. A
bend usually imply a switching of layers, therefore
cause the use of more vias. Also more bends require
more routing resources due to the larger via pitch and
reduce reliability [13]-[14]. Some papers focused on
bend minimization problem in global routing phase
[13]-[16]. [15] introduced a four-bend routing for 2-
terminal nets. [13] decomposed multi-terminal nets
into several 2-terminal nets, and presented an algorithm
to solve 2-terminal nets. [14] mainly used "Z-edge" to
bound the number of bends. [16] used "L-shaped" and
"Z-shaped" pattern routing to reduce the number of
bends for two-terminal nets.
Different from these previous works dealing with
some specific models or small nets, the main
contribution of this paper is to propose a general
method to effectively reduce the number of bends for
nets with any size, while still keeping the qualities of
congestion and wire-length.
The rest of this paper is organized as follows. In
Section 2, we formulate the problem and introduce
some basic definitions and theorems. In Section 3, a
new algorithm is proposed. The experimental results
are shown in Section 4. And in Section 5, we conclude
our work and introduce the future work.
2. Preliminaries

2.1. Problem formulation

Global routing problem is normally formulated as
follows: the entire routing region is tiled into an array
of rectangular "global routing cells (GRCs)". Based on
these GRCs, a "global routing graph (GRG)" G(V
G
,E
G
)
is constructed, where a vertex v V
G
corresponds to a
GRC, and an edge e E
G
corresponds to the border
between two GRCs. Since there is only finite routing
space on the borders, each edge has a capacity. A set of
nets N={N
1
, N
2
, ...} is given to represent the
interconnection between circuit elements. Each net
N
i N contains a set of terminals V
i
={v
0i
, v
1i
, ...} which
are represented by the corresponding vertices in V
G
. In
the global routing phase, every net is routed by a
Steiner tree.
In the routing phase, the number of wires routed
across an edge is designated as the demand of the edge.
If for an edge e, demand(e) > capacity(e), then the
edge e is called over-congested, or we say there is an
overflow [5] on edge e. In our model, we do not allow
over-congested edges.
We assign additional cost to the route once it
reaches 80% capacity [17], by defining the weight of
an edge e E as follows.
)
(
))
(
1
(
)
(
e
length
e
congest
k
e
weight
×
×
+
=

)
)
(
)
(
8
.
0
)
(
,
0
max(
)
(
e
capacity
e
capacity
e
demand
e
congest =

The weight of a route r is r
e
e
Weight )
( .
This paper focuses on the global routing problem
with the objective of reducing the number of bends,
eliminating over-congested edges, and satisfying the
constraint of wire-length, which can be formulated as
follows.
min N
N
i
i
b
s.t.
)
(
)
(
j
j
e
capacity
e
demand ,
G
j
E
e
+ N
N
i
i
W
w
0
)
1
(
In the above formulas, b
i
and w
i
respectively denote
the number of bends and the weight of the routing tree
of net N
i
;
is an adjustable parameter; W
0
denotes a
standard weight value. We use the total weight value
got by SSTT [7], an efficient global router focusing on
congestion and wire-length, as W
0
in our algorithm.

2.2. Definitions and theorems

2.2.1. Definition 1, STST.
The definition of STST in
our paper is extended from [18]. A special kind of
Steiner tree consisting of a single horizontal/vertical
line segment and vertical/horizontal line segments is
called STST-H (single horizontal trunk Steiner
trees)/STST-V (single vertical trunk Steiner trees). A
STST is either a STST-H or a STST-V, as shown in
Figure 1. The single horizontal/vertical line segment in
a STST-H/STST-V is called "trunk", and the
vertical/horizontal line segments are called "branches".


(a) A STST-H

(b) A STST-V

Figure 1. Examples of the STST

2.2.2. Definition2, MSTST.
A MSTST (minimal
single trunk Steiner tree) is the STST with minimal
total wire-length among all STSTs. A MSTST-H /
MSTST-V (minimal single horizontal / vertical trunk
Steiner tree) is the STST-H / STST-V with minimal
total wire-length among all STST-H / STST-Vs.
A MSTST must be either a MSTST-H or a MSTST-
V. It should be noticed that in most cases a MSTST is
not a SMT (Steiner minimal tree). In worst case, a
MSTST may have much longer wire-length than a
SMT.

2.2.3. Definition3, path and soft path.
In this paper, a
path in a Steiner tree denotes a sequence of adjacent
segments with no terminals or Steiner points sharing
two adjacent segments (however, the endpoints of the
line may be terminals or Steiner points).
[5] defined the "soft edge" of connecting 2-terminal
nets. We extend this definition to the "soft path" in a
Steiner tree. A soft path is a path connecting two
terminals or Steiner points v
i
(x
i
,y
i
),v
j
(x
j
,y
j
)
V, so that:
1. x
i
x
j
and y
i
y
j
; 2. its length l
ij
is fixed; 3. the precise
edge routing between v
i
and v
j
is not determined.

2.2.4. Theorem 1, location of the trunk in a MSTST.
In a STST, we denote the number of segments above
(or to the right of) the trunk as n
a
, below (or to the left
of) the trunk as n
b
, and the number of terminals on the
trunk but not on any of the segments as n
o
. Then the
trunk in a MSTST must have the property: |n
a
-n
b
|
n
o

(Examples are shown in Figure 2).

The proof is omitted
due to the paper length limitation.
This property helps us to find out the trunk location
of a MSTST quickly in our algorithm. Also it shows
that there may exists more than one MSTST for a set of
terminals, as shown in Figure 2.

n
a
=3, n
b
=5, n
o
=2
(a)


n
a
=5, n
b
=4, n
o
=1
(b)

Figure 2. Examples of two different MSTSTs
routing the same set of terminals

2.2.5. Theorem 2, the number of bends in a MSTST.
A unique character of a MSTST is that in a STST
connecting n points, the number of bends must be no
more than n. The proof