g in the presence of wire
and buffer obstacles. Recently several algorithms have been
published addressing the routing tree construction problem.
But all these algorithms are slow and not scalable. In this
paper, we propose an algorithm which is fast and scalable
with problem size. The main idea of our approach is to specify
some important high-level features of the whole routing tree so
that it can be broken down into several components. We apply
stochastic search to nd the best specication. Since we need
very few high-level features, the size of stochastic search space
is small and can be searched in very less time. The solutions for
the components are either pre-generated and stored in lookup
tables, or generated by extremely fast algorithms whenever
needed. Since it is efcient to obtain solutions for components,
it is also efcient to construct and evaluate the whole routing
tree for each specication. Experimental results show that,
for trees of moderate size, our algorithm out performs the
previous algorithms in both quality and runtime.
I. I
NTRODUCTION
As VLSI technology enters deep submicron era, inter-
connect delay becomes a dominant factor in determining
circuit performance. Interconnect optimization techniques
like buffer insertion and wire sizing have been shown to
be effective in reducing interconnect delay [5]. In modern
VLSI design, it is very common to consider buffer insertion
and wiring sizing during performance-driven routing. For
the routing of two-terminal nets and when there is no
restriction on buffer positions in the routing area, the route
with optimal delay can be constructed by inserting buffers
and sizing wires of the shortest path from source to sink.
In other words, routing and interconnect optimization can
be performed sequentially. However, for multi-terminal nets
or when there are macro blocks where wires can be passed
but buffers cannot be placed, the optimal routing tree can
only be found if routing, buffer insertion and wire sizing
are considered simultaneously.
Sampath Dechu is with Micron Technology Inc, Boise, ID 83716 USA
(email: sampath@iastate.edu)
Cien Shen is with Cadence Design Systems, Sanjose, CA USA (email:
zion@cadence.com)
Chris Chu is with Dept of Electrical and Computer Engg., Iowa State
University, Ames, IA 50011 USA (email: cnchu@iastate.edu)
Many algorithms have been proposed in the past few
years to construct routing trees with buffer insertion and
wire sizing in the presence of routing and buffer obstacles.
The approaches used can be classied as either sequential
or simultaneous approaches. In sequential approach, the
routing tree is constructed followed by buffer insertion
and wire sizing. In simultaneous approach, routing tree is
constructed by simultaneously considering routing, buffer
insertion and wire sizing. The C-Tree algorithm proposed
in [7] follows the sequential approach. However, it does not
consider wire obstacles, buffer obstacles and wire sizing.
As a step of a sequential approach, Hu et al. [8] presented
the RIATA algorithm which extended van Ginnekens al-
gorithm to solve the problem of buffer insertion on a given
routing tree with buffer blockage consideration.
Several algorithms have been proposed based on the
simultaneous approach. Topology search based algorithms
P-Tree [1], S-Tree [2], and SP-Tree [3] limit the routing
topology space to certain topologies and search exhaus-
tively for the best solution in that limited space. The nal
routing tree obtained from these algorithms depends on the
criteria used to limit the topology space and the initial
routing topology given to these algorithms. In order to
obtain a better solution, a larger topology space needs
to be considered and the exhaustive search usually takes
a signicant amount of time. All these algorithms are
not scalable and they cannot handle wiresizing. For two-
terminal nets, Zhou et al. [9] presented a dynamic program-
ming algorithm called fast path for simultaneous routing
with buffer insertion, considering both buffer and wire
obstacles. Lai and Wong [10] formulated the simultaneous
routing with buffer insertion and wire sizing in the presence
of buffer and wire obstacles as a graph-theoretic shortest
path problem. However, these two algorithms cannot be
easily extended to handle multi-terminal nets.
Recently, Tang et al. [4] presented an algorithm graph-
RTBW for multi-terminal nets that considers buffer in-
sertion, wire sizing, and buffer and wire obstacles si-
multaneously. In their approach, the routing problem is
converted into a collection of graph problems. One graph
is constructed for each subset of sinks. In the graph, one
vertex represents the subset, and other vertices represent
possible buffer choices at different buffer locations. The 2
shortest path from the subset vertex to every other vertex
�
in the graph corresponds to the optimal subtree with
appropriate buffer insertion and wire sizing connecting
�
and the subset of sinks. Dynamic programming is used to
construct routing solutions for larger subset of sinks based
on solutions for smaller subsets of sinks. Finally, the routing
solution for all sinks is obtained. They use Rubinstein
delay model [11] for interconnect delay calculation. As they
consider all the subsets of sinks, the runtime is exponential
to the number of sinks. Hence the algorithm is very slow.
In this paper, we present a very fast and scalable al-
gorithm named Fast-RTBW for solving this problem. The
main idea of our approach is to specify some important
high-level features of the whole routing tree so that it can be
broken down into several components. We apply stochastic
search to nd the best specication. Since we need very
few high-level features, the size of stochastic search space
is small. As size of the solution space is small, the time
required to search for high level specications of the routing
tree is very less. The solutions for the components are either
pre-generated and stored in lookup tables, or generated
by extremely fast algorithms whenever needed. Since it
is efcient to obtain solutions for components, it is also
efcient to construct and evaluate the whole routing tree for
each specication. Experimental results show that, for trees
of moderate size, our algorithm is at least several hundred
times faster than the recently proposed algorithms SP-Tree
and graph-RTBW, without much difference in delay and
resource consumption.
Our approach has the following advantages over previous
approaches:
1) Our approach is much faster and scalable. We ap-
ply stochastic search on a small search space. The
evaluation of a specic routing tree is also fast,
because lookup tables and fast algorithms are used to
nd component solutions. Runtime of our algorithm
decreases as number of blockages in the design
increases, because we have to search less number
of positions for buffers. The graph-RTBW algorithm
uses exhaustive search by trying all combinations of
subset of sinks, buffer positions and buffer sizes.
As a result, the algorithm is very slow. Topology
search based approaches try to reduce the runtime
by limiting the search space to certain topologies.
But these algorithms cannot handle wire sizing and
are not scalable with problem size. These algorithms
becomes slower as the number of blockages increases
in the design.
2) We do not have restriction on the fanout of buffers.
The graph-RTBW algorithm theoretically can han-
dle general fanout. However, the expensive term in
the time complexity of the algorithm is
���������
���� !�"�
, where
�
is the bound on fanout,
#
is the number of sinks,

is number of buffer types,

is number of possible buffer locations. So, in
practice, the algorithm can only handle a fanout of
$
. The example given in Figure 1 demonstrates the
disadvantage of having a restriction on fanout. Figure
1 (a) shows routing tree obtained by graph-RTBW for
�&%
$
and Figure 1(b) shows routing tree obtained
by our algorithm. The delay of routing tree shown in
Figure 1(b) is 37.7% better than the delay of routing
tree shown in Figure 1(a). Also, we observe that
routing resources are wasted in the rst case.
(a)
(b)
S
t2
t1
S
t2
t1
t3
t3
Fig. 1.
(a) Routing solution by graph-RTBW. (b) Routing solution by
our algorithm
3) We use Elmore delay model [12] for calculating the
delay of interconnects. It gives better estimation of
delay when compared to Rubinstein delay model
used in [4]. By using Elmore delay model, we can
minimize the delay of critical path of multi-terminal
net, which is not feasible by using Rubinstein model.
The rest of the paper is organized as follows: Section 2
presents the problem formulation. Section 3 explains the
notation and the proposed algorithm in detail. Section 4
presents the complexity analysis of our algorithm. Experi-
mental results are given in Section 5.
II. P
ROBLEM
F
ORMULATION
The goal of the algorithm is to construct a routing tree
with buffer insertion and wire sizing in the presence of
wire and buffer obstacles, such that the maximum delay
from source to among all the sinks is minimized. We use
'
-type
(0)
model for wires and switch-level
(0)
model
for buffers. We use Elmore delay model to calculate the
interconnect delay. The problem formulation given below
is the same as in [4].
Problem: Given a routing grid graph
1
%2�436587
�
, a
buffer library

, a wire library
9
, a source node
@BA
3
and
#
sink nodes
�

5C�EDF5HGIGHGI5��

A
3
of net. Find a buffered
routing tree
P
rooted at
@
and leafed at
��QC5�RS%
�
5HGHGIG"5
#
, such
that the maximum delay from
@