Delay bounded buffered tree construction for timing driven floorplanning.
As devices and lines shrink into the deep submicron range, the propagation delay of signals can be effectively improved by repowering the signals using intermediate buffers placed within the routing trees. Almost no existing timing driven floorplanning and placement approaches consider the option of buffer insertion. As such, they may exclude solutions, particularly early in the design process, with smaller overall area and better routability. In this paper, we propose a new methodology in which buffered trees are used to estimate wire delay during floorplanning. Instead of treating delay as one of the objectives, as done by the majority of previous work, we formulate the problem in terms of Delay Bounded Buffered Trees (DBB-tree) and propose an efficient algorithm to construct a DBB spanning tree for use during floorplanning. Experimental results show that the algorithm is very effective. Using buffer insertion at the floorplanning stage yields significantly better solutions in terms of both chip area and total wire length.
Introduction
In high speed design, long on-chip interconnects can be modeled as distributed delay lines,
where the delay of the lines can often be reduced by wire sizing or intermediate buffer
insertion. Simple wire sizing is one degree of freedom available to the designer, but often it
is ineffective due to area, routability, and capacitance considerations. On the other hand,
driver sizing and buffer insertion are powerful tools for reducing delay, given reasonable
power constraints. Intermediate buffers can effectively decouple a large load off of a critical
path or divide a long wire into smaller segments, each of which has less line resistance
and makes the path delay more linear with overall length. As the devices and lines shrink
into deep submicron, it is more effective, in terms of power, area, and routability, to insert
intermediate buffers than to rely solely on wire sizing.
Because floorplanning and placement have a significant impact on critical path delay,
research in the area has focused on timing driven approaches. Almost no existing floorplanning
and placement techniques consider the option of buffer insertion, particularly early
in the design cycle. Typically, only wire length or Elmore delay is used for delay calcula-
tion. This practice is too restrictive as evidenced by the reliance industry has placed on
intermediate buffering as a means for achieving aggressive cycle times. It is commonplace
for production chips to contain tens of thousands of buffers. This paper attempts to leverage
the additional freedom gained by inserting buffers during floorplanning and placement.
The resulting formulation provides an additional degree of freedom not present in past
approaches and typically leads to solutions with smaller area and increased routability.
To incorporate buffer insertion into early planning stage, we propose a new methodology
of floorplanning and placement using buffered trees to estimate the wiring delay. We
formulate the Delay Bounded Buffered Tree (DBB-tree) problem as follows: Given a net
with delay bounds on the critical sinks that are associated with critical paths, construct
a tree with intermediate buffers inserted to minimize both the total wiring length and the
number of buffers, while satisfying the delay bounds. We propose an efficient algorithm
based on the Elmore delay model to construct DBB spanning trees for use during floorplanning
and placement. The experimental results of the DBB spanning tree show that using
buffer insertion at the floorplanning stage yields significantly better solutions in terms of
both chip area and total wiring length.
The remainder of the paper is organized as follows. Section 2 reviews the related works
on interconnect optimization and intermediate buffer insertion, and introduces the idea of
our DBB spanning tree algorithm. Section 3 describes the DBB algorithm in detail. The
experimental results of DBB spanning tree algorithm applied for signal nets and for general
floorplanning are given in Section 4, followed by conclusions in Section 5.
Related Works and Overview of DBB-tree Algorithm
2.1 Elmore Delay Model
As VLSI design reaches deep submicron, interconnect delay models have evolved from the
simplistic lumped RC model to the sophisticated high-order moment-matching delay model
[1]. The Elmore delay model [2] provides a simple closed-form expression with greatly
improved accuracy for delay compared to the lumped RC model. Elmore is the most
commonly used delay model in recent works of interconnect design.
For each wire segment modeled as a - \Gammatype circuit, given the interconnect tree T , the
Elmore delay from the source s 0 to sink s i can be expressed as follows:
rl u;v ( cl u;v
where R 0 is the driver resistance at the source and C 0 is the total capacitance charged by the
driver. Path(0; i) denotes the path from s 0 to s i and wire e(u; v) connecting s v to its parent
s u . Given a uniform wire width, r and c denote the unit resistance and unit capacitance
respectively. The wire resistance rl u;v and wire capacitance cl u;v are proportional to the
wire length l u;v . Let C v denote the total capacitance of a subtree rooted at s v , which is
charged through wire e(u; v). The first term of -(0; i) is linear with the total wire length
of T , while the second term has quadratic dependence on the length of the path from the
source to s i .
2.2 Topology Optimization for Interconnect
From the previous discussion of Elmore delay, we can conclude that for interconnect topology
optimization, two major concerns are the total wire length and the path length from the
driver to the critical sinks. The early work of Cohoon Randall [3] and Cong et al. [4]
observed the existence of conflicting min-cost and min-radius (the longest source-to-sink
path length of the tree) objectives in performance-driven routing [5].
A number of algorithms have been proposed to make the trade-offs between the total
wiring length and the radius of the Steiner or spanning tree [6, 7, 8, 9]. Cong et al.
2.3 Buffered Tree Construction 3
proposed the "Bounded Radius, Bounded Cost" (BRBC) spanning tree algorithm which
uses the shallow-light approach. BRBC constructs a routing tree with total wire length no
greater than (1 times that of a minimum spanning tree and radius no greater than
times that of a shortest path tree where ffl - 0. Alpert et al. [10] proposed AHHK
trees as a direct trade-off between Prim's MST algorithm and Dijkstra's shortest path tree
algorithm. They used a parameter 0 - c - 1 to adjust the preference between tree length
and path length.
For deep submicron design, path length is no longer an accurate estimate of path delay.
Several attempts have been made to directly optimize Elmore delay taking into account
different loading capacitances of the sinks. With exponential timing complexity, the branch
and the bound algorithms proposed by Boese et al. [11, 12] provide the optimal and
near-optimal solutions that minimize the delay from the source to an identified critical
sink or a set of critical sinks of Steiner tree. For a set of critical sinks, it minimizes a
linear combination of the sink delays. However it is very difficult to choose the proper
weights, or the criticality, for this linear combination. Hong et al. [13] proposed a modified
Dreyfus-Wagner Steiner tree algorithm for minimizing the maximal source-to-sink delay,
The maximal source-to-sink delay is not necessarily interesting when the corresponding
sink is off the critical path. Also, there may be more than one critical sink in the same
net associated with multiple critical paths. Prasitjutrakul and Kubitz [14] proposed an
algorithm for maximizing the minimal delay slack, where the delay slack is defined as the
difference between the real delay and the given delay bound at a sink.
2.3 Buffered Tree Construction
Intermediate buffer insertion creates another degree of freedom for interconnect optimiza-
tion. Early works on fanout optimization problem focused on the construction of buffered
trees during logic synthesis [15, 16, 17] without taking into account the wiring effect. Re-
cently, layout driven fanout optimization have been proposed [18, 19]. For a given Steiner
tree, a polynomial time dynamic programming algorithm was proposed in [20] for the delay-optimal
buffer insertion problem. Using dynamic programming, Lillis et al. [21] integrated
wire sizing and power minimization with the tree construction under a more accurate delay
model taking signal slew into account. Inspired by the same dynamic programming
algorithm, Okamoto and Cong [22] proposed a simultaneous Steiner tree construction and
buffer insertion algorithm. Later the work was extended to include wire sizing [23]. In the
formulation of the problem [22, 23], the main objective is to maximize the required arrival
time at the root of the tree, which is defined as the minimum among the differences between
the arrival time of the sinks and the delay from the root to the sinks.
To achieve optimal delay, multiple buffers may be necessary for a single edge. An early
work of S. Dhar and M. Franklin [24] developed the optimal solution for the size, number
and position of buffers driving a uniform line that minimizes the delay of the line. The work
further considered the area occupied by the buffers as a constraint. Recently C. Alpert and
A. Devgan [25] calculated the optimal number of equally spaced buffers on a uniform wire
to minimize the Elmore delay of the wire.
2.4 Delay Minimized vs. Delay Bounded
Since timing driven floorplanning and placement are usually iterated with static timing
analysis tools, the critical path information is often available and the timing requirement for
critical sinks converges as the design and layout progresses. It is sufficient to have bounded
delay rather than minimized delay. On the other hand, the minimization of total wire length
is of interest since total wire length contributes to circuit area and routing congestion. In
addition, total wire capacitance contributes a significant factor to the switching power. The
reduction of wire length reduces circuit area and improves routability, also reduces power
consumption, which are important factors for manufacturing cost and fabrication yield [1].
In this paper, instead of minimizing the source to sink delays, we will present an algorithm
that constructs buffered spanning trees to minimize the total wire length subject to timing
constraints.
Zhu [26] proposed the "Delay Bounded Minimum Steiner Tree" (DBMST) algorithm to
construct a low cost Steiner tree with bounded delay at critical sinks. The DBMST algorithm
consists of two phases: (1) initialization of Steiner tree subject to timing constraints
and (2) iterative refinement of the topology to reduce the wiring length while satisfying
the delay bounds associated with critical sinks. Since the Elmore delays at sinks are very
sensitive to topology and they have to be recomputed every time the topology is changed,
DBMST algorithm searches all possible topological updates exhaustively at each iteration
and so it is very time consuming.
2.5 Overview of DBB-tree Algorithm
In this paper, we formulate the new Delay Bounded Buffered tree (DBB-tree) problem as
follows: Given a signal net and delay bounds associated with critical sinks, construct a
routing tree with intermediate buffers inserted to minimize the total wiring length and the
number of buffers while satisfying the delay bounds. Based on Elmore delay, we develop an
efficient algorithm for DBB spanning tree construction.
The DBB-tree algorithm consists of three phases: (1) Calculate the minimum Elmore
delay for each critical sink to allow immediate exclusion of floorplanning/placement solutions
that are clearly infeasible from a timing perspective; (2) Construct a buffered spanning tree
to minimize the total wire length subject to the bounded delay; (3) Based on the topology
obtained in (2), delete unnecessary buffers without violating timing constraints to minimize
the total number of buffers. The overall time complexity of DBB-tree algorithm is O(kn 2 ),
where k is the maximum number of buffers inserted on a single edge, and n the number of
sinks in the net. Our DBB-tree algorithm makes the following three major contributions:
ffl Treating the delay bounds provided by static timing analysis tools as constraints
rather than formulating the delay into the optimization objectives.
ffl Constructing a spanning tree and placing intermediate buffers simultaneously. The
algorithm is very effective to minimize both wire length and the number of buffers.
ffl Allowing more than one buffer to be inserted on each single edge and calculating
the precise buffer positions for the optimal solution. In contrast, most previous work
assumes at most one buffer is inserted for each edge and the buffer location is fixed.
3 Description of DBB-tree Algorithm
For floorplanning purpose, we assume uniform wire width. In the DBB-tree algorithm
presented here, we consider only non-inverting buffers. However, the algorithm can be
easily extended to handle inverting buffers. Given a signal net
the source and s sinks. The geometric location for each terminal of S is determined
by floorplanning. Let ~
denote the vector describing the parameters of non-inverting
buffers, in which t b , r b and c b are the internal delay, resistance and capacitance
of each buffer respectively. Before presenting the detailed DBB-tree algorithm, we first
state some theoretical results developed by Alpert and Devgan [25] which will be used to
calculate the number and position of identical buffers placed on a single edge to minimize
the edge delay in DBB-tree algorithm:
Theorem 1 Given a uniform line e(0; i) connecting sink s i to source s 0 , and the parameter
vector ~
B, the number of buffers placed on the wire to obtain the minimum Elmore delay of

Figure

1: Given a uniform line e(0; i) connecting sink s i to source s 0 , -(0; i) buffers are
placed on the wire in such way that the wire delay is minimized: the first buffer is ff - away
from source s 0 , the distance between two adjacent buffers equals to ffi - and the last buffer
is fi - away from sink s i .
e is given by:
s
where R 0 is the driver output resistance at source s 0 and c i the loading capacitance at sink
s i . Given - buffers inserted on e(0; i), the optimal placement of buffers which obtains the
minimum wire delay is places the buffers at equal spacing from each other. Let ff - be the
distance from the source to the first buffer, ffi - the distance between two adjacent buffers,
and fi - the distance from the last buffer to sink s i . They can be derived as follows:
r
c
r
c
The minimized wire delay with - buffers is given by:
cl 0;i (R
c
r
buffers instead of - buffers are placed on wire e the wire delay will be increased by:
\Delta- (0;
3.1 Lower Bound of Elmore Delay for Critical Sinks 7

Figure

2: If we place a buffer right after s 0 as in (a), the total capacitance driven by the
driver at source is reduced to c b and the first term of -(0; i) equals to R 0 c b . The second
term, the propagation delay of the path from source to s i , can be minimized by directly
connecting s i to the source and placing -(0; i) buffers on the wire as in (b). Combining (a)
and (b), we calculate the lower bound of Elmore delay for s i .
By replacing R 0 with 0, Equations 2 - 5 can be applied to the wire connecting any two
sinks in routing tree T . Based on the theoretical results discussed above, we will present
the detailed DBB-tree algorithm in the following section.
3.1 Lower Bound of Elmore Delay for Critical Sinks
The first phase of DBB-tree algorithm calculates the lower bound of Elmore delay for each
sink s i . It may not be possible to achieve this delay simultaneously for all sinks, but no
achievable delay will exceed it. The floorplanning is timing infeasible if there exists s i in S
such that the lower bound -   (0; i) is greater than the given delay bound D i
The first term in Eq.1, R 0 C 0 , can be reduced to R 0 c b by placing a buffer right after s 0 as
shown in Fig. 2 (a). And the second term, the propagation delay of the path from source
to s i , can be minimized by directly connecting source to s i and placing buffers as shown in
Fig. 2 (b). Formally, the lower bound of Elmore delay for s i can be given by:
If for all sinks in S, the lower bound of Elmore delay is less than the given delay bound,
then the algorithm continues to phases 2 and 3, otherwise the timing constraints are too

Figure

3: For particular sink s is the last buffered edge on the path
from the source to s v and the last buffer on edge through the resistance
between the buffer and s v , defined as driving resistance of T v , denoted by R(T v ). Since there
is no buffer between s u and s v , the driver of T v also drives T i for
are the intermediate sinks from s u to s v . After adding the new edge
e(v; w), the loading capacitance of T v is increased by \DeltaC v , the Elmore delay of sinks in
will be increased by R(T i )\DeltaC v . On the other hand, due to
the buffers on edge not affect on the delay of sinks which are not in T u .
Therefore the timing constraints of T will be satisfied if and only if the timing constraints
of T u are satisfied.
tight for the given floorplanning and the solution is excluded.
3.2 DBB Spanning Tree Construction
The second phase of DBB-tree algorithm constructs a buffered spanning tree to minimize
the total wire length subject to the timing constraints. Similar with Prim's MST algorithm,
it starts with the trivial tree: g. Iteratively edge e(v; w) with -(v; w) buffers is added
into T , where s are chosen such that l v;w is minimized and timing
constraints are satisfied. T grows incrementally until it spans all terminals of S, or there
is no edge e(v; w) that can be added without violating the timing constraints. In the later
case, the floorplanning is considered to be timing infeasible and the solution is excluded.
For the incremental construction of the DBB-tree, the key issue is how to quickly
evaluate the timing constraints each time a new edge is added, i.e. whether or not the
3.2 DBB Spanning Tree Construction 9
delay bound at each critical sink is satisfied. For particular edge e(v; w) where s
the number and the precise positions of buffers inserted on the edge which
minimize the edge delay can be calculated according to Equations 2 and 3. Let T v denote
the subtree rooted at s v , after adding edge e(v; w) into T , the loading capacitance of T v , is
increased by \DeltaC
cl
denote the last buffered edge on the path from the source to s v as shown in
Fig. 3, the last buffer on edge . If there is no buffer from the source
to s v , the source drives T v . According to Elmore delay, T v is driven through the resistance
between the driver and s v , defined as driving resistance of T v , denoted by R(T v ). Given
s v\Gamma1 is the parent of s v , R(T v ) can be calculated as follows:
Since there is no buffer on the path from s u to s v , the driver of T v also drives T i for
are the intermediate sinks from s u to s v as
shown in Fig. 3. Let T denote the set of sinks in subtree T i but not in T i+1 . Due
to the increased loading capacitance \DeltaC v of T v , the Elmore delay of sinks in T
On the other hand, due to the buffers on edge the increased loading capacitance
of T v will not affect on the delay of sinks which are not in T u . We define the delay slack of
a sink s 2 T as:
and the delay slack of T i to be:
the timing constraints will be satisfied for the sinks in T if and only if the following
condition holds:
By introducing the loading capacitance slack of each subtree
Eq. 12 can be rewritten as:
Let oe   (v) denote the minimum slack of loading capacitance among the subtrees T i for
oe
the condition in Eq. 14 can be simply rewritten as:
oe   (v) - \DeltaC
By keeping track of oe   (v), this condition can be checked in constant time. The Elmore
delay of s w can be calculated from the Elmore delay of s
where - (v; w) is calculated from Eq. 4 and the timing bound at s w can also be checked in
constant time. From above analysis, we can conclude that the necessary and sufficient
condition for satisfying the timing constraints of T after adding the new edge e(v; w) is:
oe   (v) - \DeltaC v and Dw -(0; w); (18)
and this condition can be checked in constant time.
At each iterative step of DBB-tree construction, s can be selected
in linear time such that l v;w is minimum and the timing constraints are satisfied. After
adding the new edge e(v; w), a two-pass traversal of T is sufficient to update the delay slack
and loading capacitance slack of each subtree in T : (1) traverse T bottom up and calculate
the delay slack and loading capacitance slack of each subtree T i according to Equations 11
and 13; (2) traverse T top down and calculate oe   (i) from oe   (i \Gamma 1), given s i\Gamma1 is the parent
of
oe
Since each new edge can be added into T in linear time, the overall DBB spanning tree can
be constructed in O(n 2 ) time for net S with n sinks.
3.3 Buffer Deletion
In phase 2, one or more buffers are inserted on each edge to minimize wire delay. Some
of the buffers may not be necessary for meeting the delay bound. The third phase of the
3.3 Buffer Deletion 11

Figure

4: In case of -(v; shown in (a), edge e(v; w) becomes unbuffered edge
after deleting the buffer, the load capacitance of subtree T v is increased by: \DeltaC
cl v;w buffers are re-inserted on e(v; w), as
shown
DBB-tree algorithm deletes buffers from the spanning tree obtained in the second phase to
reduce the total number of buffers. In general the buffers closest to the source can unload
the critical path the most. The algorithm traverses T bottom up and deletes one buffer at
a time without violating timing constraints. The deletion continues until all the buffers left
in T are necessary, that is, the timing constraints would not be satisfied if one more buffer
is deleted.
For particular edge e(v; w) with - ? 0 buffers, if one buffer is deleted from e(v; w), this
wire delay will be increased by \Delta- (v; w) according to Eq. 5, and buffers will be
re-inserted: In case of shown in Fig. 4 (a), wire
e(v; w) becomes unbuffered edge after deleting the buffer, the load capacitance of subtree
T v is increased by: \DeltaC cl v;w buffers are re-inserted
on edge e(v; w), as shown in Fig. 4 (b): \DeltaC
Similar to phase 2, let denote the last buffered edge from the source to s v . The
delay of the sinks in subtree T u will be increased due to the increased loading capacitance
of T v . In addition, the delay of sinks in subtree Tw will be further increased due to the
increased edge delay of e(v; w). Based on the analysis in phase 2, a buffer can be deleted
without causing timing violation if and only if following condition holds:
oe   (v) - \DeltaC v and -(Tw

Table

1: Experimental Parameters of DBB-tree Algorithm on Signal Nets
Output Resistance of Driver R 0
500\Omega \Gamma1000\Omega Unit Wire Resistance c
0:12\Omega =-m
Unit Wire Capacitance r 0:15fF=-m
Output Resistance of Buffer r b
500\Omega Loading Capacitance of Buffer c b 0:05pF
Intrinsic Delay of Buffer t b 0:1ns
Loading Capacitance of Sink c i 0:05pF \Gamma 0:15pF
Therefore the timing constraints of T can be evaluated in constant time for deleting a buffer
from edge e(v; w). The buffer can be found by searching at most n \Gamma 1 edges. After deleting
a buffer, the delay slack and loading capacitance slack of subtrees in T are incrementally
updated in O(n) time as in phase 2. So one buffer will be deleted in linear time. There are at
most kn buffers in T where k is the maximum number of buffers on single edge, the timing
complexity of buffer deletion is O(kn 2 ) which dominates the overall DBB-tree algorithm.
Following experimental results show that the buffer deletion effectively minimizes the total
number of buffers and it can delete more than 90% of the buffers inserted in the previous
phase.
4 Experimental Results
In the first part of the experiments, we implemented the DBB spanning tree algorithm on
a Sun SPARC 20 workstation under the C/UNIX environment. The algorithm was tested
on signal nets with 2; 5; 10; 25; 50 and 100 pins. For each net size, 100 nets were randomly
generated on a 10mm \Theta 10mm routing region, and we report the average results. The driver
output resistance at the source and the loading capacitances of sinks are randomly chosen
from the
respectively. The parameters used in
the experiments are based on [22], which are summarized in Table 1.
The average results of the DBB spanning tree construction are shown in Table 2. The
delay bounds of critical sinks for each net size are randomly chosen from the interval titled
"Delay Bounds". The average wire length and number of buffers for DBB spanning tree are
reported in this table. The average CPU time consumed per net shows that DBB spanning
tree algorithm is fast enough that can be applied during the stochastic optimization.
Table

2: Experimental Results of DBB Spanning Trees on Signal Nets
Pins(#) Delay Bounds(ns) Wire Length(mm) Buffers(#) CPU (sec:)
To evaluate the DBB spanning trees generated by the experiments, we constructed
both minimum spanning tree (MST) and shortest path tree (SPT) for the same signal
nets using the same parameters. The comparison of the average results is shown in Table
3. "DBB/MST" and "DBB/SPT" is the average length ratio of DBB-tree to MST and
DBB-tree to SPT respectively. The column "% sinks meeting bound" gives the average
percentage of critical sinks which satisfy the delay bounds. For the nets with small number
of terminals, the length of DBB-tree is very close to MST. As the number of terminals
in the nets increases, the length of DBB-tree to MST is increased, but only 9% through
0% critical sinks can meet the bound in MST for 25-pin through 100-pin nets. It can be
concluded that it is very difficult to satisfy the timing constraints using MST especially for
the large nets. On the other hand, the length ratio of DBB-tree to SPT is decreased from
1:0 down to 0:24, and SPT is also not ideal to meet the delay bounds for the large nets.
The DBB-tree approach can achieve the short wire length with 100% critical sinks meeting
the delay bounds.
In

Table

4, the average number of buffers inserted in DBB spanning trees are listed and
the result is very reasonable considering the number of terminals in the net. To evaluate
the buffer deletion algorithm, we compare the average number of buffers inserted in DBB
spanning tree before and after buffer deletion. The percentage of buffers reduced by the
third phase of DBB-tree algorithm is as high as 79% through 93%. The results presented
in

Table

4 demonstrate that the third phase of the algorithm is quite effective at removing
any unnecessary buffers estimated during phase 2 and the DBB-tree algorithm will not lead
to unrealistic, impractical results.
In the second part of the experiments, we apply DBB-tree to evaluate the wiring delay of
floorplanning solutions considered by the Genetic Simulated Annealing method [27]. Table

Table

3: Comparison of DBB-tree, MST and SPT of Signal Nets.
Pins (#) Legnth (mm) % sinks meeting bound
DBB MST DBB/MST SPT DBB/SPT DBB MST SPT

Table

4: Average Number of Buffers Before vs. After Buffer Deletion.
Pins(#) w/o Deletion with Deletion Reduced (%)
Table

5: Four Examples of Floorplanning Applying DBB-tree Algorithm.
Blocks Block size Aspect ratio Nets Net size Delay bound CPU
(#) (mm) of blocks (#pins/net) (ns) (min:)

Table

Achieved Floorplanning Solutions by Using DBB-tree, MST and SPT Approaches.
Blocks sinks meeting bound
(#) DBB MST SPT DBB MST SPT DBB MST SPT
100 213.57 274.77 274.02 6039.93 7037.06 16339.61 100 90.82 95.61
5 presents four examples which includes 10, 25, 50 and 100 rectangular blocks, respectively.
The sizes (widths and heights) and aspect ratios of blocks are randomly chosen within a
nominal range. Netlists are also randomly generated for the four examples. The technology
parameters are consistent with those shown in Table 1.
To compare with the traditional approaches which do not consider buffer insertion during
the floorplanning, we also apply MST and SPT methods to evaluate the floorplanning
solution in the same examples. Based on the same stochastic search strategy, the floorplanning
solutions achieved by the three methods are shown in Table 6. Similarly, the column
"% sinks meeting bound" measures the percentage of critical sinks which satisfy the tim-
Table

7: The Improvement by Considering Buffer Insertion in Floorplanning Stage.
Blocks Area Improvement(%) Wire Length Improvement(%) Buffers(#)
(#) DBB vs. MST DBB vs. SPT DBB vs. MST DBB vs. SPT in DBB

Figure

5: Floorplanning of 50 blocks with 150 nets sized from 2-pin to 25-pin. SPT is
applied to evaluated the wiring delay. Achieved chip area is 124:38mm 2 and total wire
length 2696:10mm with 97:7% critical sinks meeting the delay bounds.
ing bounds. Table 7 calculates the improvement of both chip area and total wire length
by using DBB-tree method. For the examples, the area can be improved up to 31% over
MST and 22% over SPT, respectively. On the other hand, the total wire length can be
improved up to 19% over MST and 63% over SPT, respectively. This substantial improvement
demonstrates that using buffer insertion at the floorplanning stage yields significantly
better solutions in terms of both chip area and total wire length. In addition, the total
number of buffers estimated by the DBB-tree approach are also shown in this table. Figures
5 and 6 show the floorplanning solution with 50 blocks by using SPT and DBB-tree
algorithm, respectively. In addition, Fig. 6 also displays the buffers estimated by DBB-
tree approach. It should be noted that future research is needed to extend the approach
to distribute buffers into the empty space between macros subject to timing constraints.
However, the area of such buffers is typically a small fraction of a given macro area and can
be typically accommodated.
5 Conclusion
In this paper, we propose a new methodology of floorplanning and placement where intermediate
buffer insertion is used as another degree of freedom in the delay calculation. An
efficient algorithm to construct Delay Bounded Buffered(DBB) spanning trees has been de-
veloped. One of the key reasons this approach is effective is that we treat the delay bounds
as constraints rather than formulating the delay into the optimization objectives as is done
Figure

Floorplanning of the same example in Fig. 5. DBB-tree is applied to evaluate the
wiring delay. Achieved chip area is 112:59mm 2 and total wire length 1455:47mm with 100%
critical sinks meeting the delay bounds. The area and total wire length are improved by
9:48% and 46:02% respectively. The dots shown in the figure represent the buffers estimated
by DBB-tree.
in most of the previous work. In fact, our problem formulation is more realistic for the
path based timing driven layout design. The timing constraints of a floorplan are evaluated
many times during our stochastic optimization process. The efficient DBB spanning tree
algorithm made our buffered tree based floorplanning and placement highly effective and
practically applicable to industrial problems.



--R


"The transient response of damped linear networks with particular regard to wide-band amplifiers,"
"Critical net routing,"

"A new class of iterative steiner tree heuristics with good perfor- mance,"
"A direct combination of the prim and dijkstra constructions for improved performance-driven global routing,"
"Performance-Driven interconnect design based on distributed RC delay model,"
"Performance oriented rectilinear steiner trees,"
"Bounded-diameter spanning tree and related problems,"
"Prim-Dijkstra tradeoffs for improved performance-Driven routing tree design,"
"Rectilinear steiner trees with minimum elmore delay,"
"High-Performance routing trees with identified critical sinks,"
"Performance-Driven steiner tree algorithms for global routing,"
"A timing-Driven global router for custom chip design,"
"A heuristic algorithm for the fanout problem,"
"Performance oriented technology mapping,"
"The fanout problem: From theory to practice,"
"A methodology and algorithms for post-Placement delay optimization,"
"Routability-Driven fanout optimization,"
"Buffer placement in distributed RC-tree networks for minimal elmore delay,"
"Optimal and efficient buffer insertion and wire sizing,"
"Interconnect layout optimization by simultaneous steiner tree construction and buffer insertion,"
"Buffered steiner tree construction with wire sizing for interconnect layout optimization,"
"Optimum buffer circuits for driving long uniform lines,"
"Wire segmenting for improved buffer insertion,"
Chip and Package Co-Synthesis of Clock Networks
"Genetic simulated annealing and application to non-slicing floorplan design,"
--TR
Bounded diameter minimum spanning trees and related problems
The fanout problem: from theory to practice
Performance-oriented technology mapping
A heuristic algorithm for the fanout problem
Performance oriented rectilinear Steiner trees
Performance-driven Steiner tree algorithm for global routing
High-performance routing trees with identified critical sinks
Routability-driven fanout optimization
Performance-driven interconnect design based on distributed RC delay model
A methodology and algorithms for post-placement delay optimization
Rectilinear Steiner trees with minimum Elmore delay
Buffered Steiner tree construction with wire sizing for interconnect layout optimization
Wire segmenting for improved buffer insertion
Performance-Driven Global Routing for Cell Based ICs
Critical Net Routing
Chip and package cosynthesis of clock networks

--CTR
Weiping Shi , Zhuo Li, An O(nlogn) time algorithm for optimal buffer insertion, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
Yuantao Peng , Xun Liu, Power macromodeling of global interconnects considering practical repeater insertion, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
Xun Liu , Yuantao Peng , Marios C. Papaefthymiou, Practical repeater insertion for low power: what repeater library do we need?, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
Ruiming Chen , Hai Zhou, Efficient algorithms for buffer insertion in general circuits based on network flow, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.322-326, November 06-10, 2005, San Jose, CA
Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion for noise and delay optimization, Proceedings of the 35th annual conference on Design automation, p.362-367, June 15-19, 1998, San Francisco, California, United States
I-Min Liu , Adnan Aziz , D. F. Wong, Meeting delay constraints in DSM by minimal repeater insertion, Proceedings of the conference on Design, automation and test in Europe, p.436-440, March 27-30, 2000, Paris, France
Hur , Ashok Jagannathan , John Lillis, Timing driven maze routing, Proceedings of the 1999 international symposium on Physical design, p.208-213, April 12-14, 1999, Monterey, California, United States
Jason Cong , Tianming Kong , David Zhigang Pan, Buffer block planning for interconnect-driven floorplanning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.358-363, November 07-11, 1999, San Jose, California, United States
Probir Sarkar , Vivek Sundararaman , Cheng-Kok Koh, Routability-driven repeater block planning for interconnect-centric floorplanning, Proceedings of the 2000 international symposium on Physical design, p.186-191, May 2000, San Diego, California, United States
Jason Cong , Tianming Kong , Zhigang (David) Pan, Buffer block planning for interconnect planning and prediction, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.929-937, 12/1/2001
Feodor F. Dragan , Andrew B. Kahng , Ion Mndoiu , Sudhakar Muddu , Alexander Zelikovsky, Provably good global buffering using an available buffer block plan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
Ali Selamat , Sigeru Omatu, Web page feature selection and classification using neural networks, Information SciencesInformatics and Computer Science: An International Journal, v.158 n.1, p.69-88, January 2004
Dian Zhou , Rui-Ming Li, Design and verification of high-speed VLSI physical design, Journal of Computer Science and Technology, v.20 n.2, p.147-165, March 2005
Total Wire Length;MST;floorplanning;DBB-tree;SPT;elmore delay;buffer insertion;delay bounds