Optimal wire sizing and buffer insertion for low power and a generalized delay model.
We present efficient, optimal algorithms for timing optimization by discrete wire sizing and buffer insertion. Our algorithms are able to minimize dynamic power dissipation subject to given timing constraints. In addition, we compute the complete power-delay tradeoff curve for added flexibility. We extend our algorithm to take into account the effect of signal slew on buffer delay which can contribute substantially to overall delay. The effectiveness of these methods is demonstrated experimentally.
Introduction
Timing optimization techniques for VLSI circuits have received much attention in recent years
due to increasingly aggressive designs and the impact of technological trends such as shrinking
geometries. Among these techniques are performance driven placement and routing, gate
sizing, buffer insertion (often referred to as fanout optimization in pre-layout works), and wire
sizing. In this work, we focus on wire sizing and buffer insertion
Wire Sizing: Automatic sizing of wire widths is an attractive technique for timing optimization
in signal nets, particularly with the advent of sub-micron technology. The benefit of wire
sizing lies in the fact that, with shrinking geometries, wire resistance is now a significant contributor
to overall delay. As a result, it makes sense to tune the widths of wires to balance the
tradeoff between added capacitance and decreased resistance. Wire sizing can be of significant
benefit for both on-chip and for inter-chip (e.g. MCM) interconnects.
Cong, Leung, Zhou and Koh provided several studies of wire sizing in [4, 2, 3] and demonstrated
the potential of wire sizing in improving delay. In these works the problem was formulated
as the task of minimizing the weighted sum of the source-to-sink Elmore delays for a set
of identified critical sinks in a given routing tree. The weighting coefficients are presumably
provided by the user. Under this formulation they prove several properties which lead to an
O(n r ) algorithm for a net with n segments each having r possible widths. The authors also
propose a greedy heuristic procedure with run time of O(n 3 r). Cong et. al. also attack the
problem of incorporating a cost function such as area or power. Their formulation is, again, a
weighted sum of their stated timing objective function and the cost function.
Later, in [12], Sapatnekar studied the more common metric of maximum source-to-sink
delay - or, more generally, the task of minimizing cost subject to given timing constraints. He
noted that the key property of separability used by Cong and Leung in designing their algorithm
did not hold for this case. In addition, the property of monotonicity utilized by Cong et. al.
does not apply when the length of all wire segments is not identical. In the same paper
Sapatnekar proposed a geometric programming formulation of the maximum delay, continuous
wire-sizing problem followed by a mapping heuristic to discretize the solution.
Later, in [8], a dynamic programming algorithm which exploited the fact that the lengths of
wire segments are discrete in nature (i.e., that they are integer multiples of a basic grid length)
was given. This led to the observation that, over all possible width assignments to a subtree,
the number of distinct capacitive values at the root is polynomially bounded. This yielded a
polynomial time minimum delay wire sizing dynamic programming algorithm. However, power
considerations were not explicitly taken into account.
Buffer Insertion: Research on buffer insertion includes the early works of Berman et. al.,
[1], Touati [16] and van Ginneken [17]. Other contributions in this area include [9, 14, 8, 7].
With the exceptions of [17], [7] and more recently [8], these works have focussed on timing
optimization prior to layout by imposing buffer trees on the network. There are important
engineering considerations associated with such an approach. Perhaps most important among
these considerations are the difficulty of accurately taking into account the resistive and capacitive
effects of interconnect, as observed in [7], and potential routability problems created
by pre-layout buffer trees as mentioned in [1].
As a result of these practical considerations, we focus on a post-layout methodology where
topological information is available. Previous work on post-layout buffer insertion includes
[17], in which van Ginneken gave an elegant polynomial time algorithm for delay-optimal
buffer insertion into a given topology. He extended his algorithm to minimize the number of
buffers subject to given timing constraints. He noted that this extension was not, in general,
polynomial, but that efficient run-time was observed in practice. Implementation details of
this extension were not given. His algorithm did not consider the effect of signal slew on buffer
delay.
In [8], a delay-optimal algorithm for simultaneous buffer insertion and wire sizing was given.
However, neither power (or area) considerations or signal slew were taken into account.
Contributions of This Paper: In this paper we present efficient algorithms for wire sizing,
buffer insertion and both techniques simultaneously. Our main contributions are summarized
as follows.
ffl We give optimal, polynomial-time algorithms for the min power wire sizing problem and
the simultaneous wire sizing, buffer insertion problem. This includes computation of the
power-delay curve and a novel data-structure for efficiently pruning sub-optimal
solutions.
ffl We incorporate signal slew into the buffer delay model by manipulation of piece-wise
linear functions.
In this work, timing constraints are given explicitly as required arrival times at the sinks of
the net rather than as coefficients of a weighted sum of the sink delays. We suggest that
computation of the entire power-delay trade off curve is of practical significance as it provides
added flexibility to the designer.
The incorporation of signal slew is also significant since its contribution of to total delay
can be over 50% (see e.g. [6]) and therefore cannot be neglected in practice.
The ability to use inverters as buffers rather than resorting to pairs of inverters to ensure
proper signal polarity is also of practical utility.
The complexity of our algorithms without signal slew taken into account is summarized in
the following table.
Max Req-Time Min Power
wire-sizing
buffer-insertion O(n 2
both
In the table, n is the number of sinks in the net, m is the number of sizeable wire segments
and c max is the largest possible capacitive value of any component in the tree. Set B is
the given buffer library and W is the largest multiple of the basic wire width allowed. Where
component of the complexity, we assume the capacitive parameters of the problem
are given as or translated into polynomially-bounded integers. As such, these algorithms are
pseudo-polynomial. However, in these cases, the bounds are very pessimistic versus observed
behavior.
When signal slew is incorporated into the delay model, we are not able to give polynomial
bounds due to degenerate situations. However, in practice we observe these algorithms to
perform similarly to their simpler counterparts - usually a constant factor slower.
To the best of our knowledge, this work represents the most efficient optimal algorithms
to date for these problems. We also improve on the results of [8] in terms of run-time when
minimizing maximum delay independent of power is the goal.
Our algorithms adopt a bottom-up dynamic programming approach. Rather than computing
a single solution for each subtree, we compute a set of solutions where each member of the
set is characterized by both the timing properties and capacitance of the associated solution.
Solution sets are kept small by employing an observation made by van Ginneken [17] which
essentially says that when combining the solution sets of a node's left and right children to
create a new solution set, the new set need not consider all pairs of left and right solutions;
rather only a linear number of pairs need be considered since one branch will always dominate.
In addition, when minimizing power, we employ a similar observation to identify inherently
sub-optimal solutions and thereby drastically reduce the size of solution sets. This property is
identified efficiently by use of a novel tree data-structure. Generalizations of these techniques
are developed to handle the case where slew is taken into account.
The remainder of the paper is organized as follows. Section 2 gives notational conventions.
Section 3 gives delay models and problem formulations. Section 4 gives the overall algorithmic
framework. Section 5 addresses the min-delay/max-required time formulation. Section 6 generalizes
the algorithm to minimize power subject to timing constraints. Section 7 generalizes
the algorithm further to account for the contribution of signal slew to delay by the manipulation
of piece-wise linear functions. Section 8 gives experimental results and we conclude in
section 9.
Notational Conventions
Throughout this paper we use the following notation.
routing tree rooted at node v
l(v), r(v) The left and right children of node v respectively
e v Tree edge (wire) from node v to its parent
l e Length of edge e
c e Capacitance of edge e
c v Input capacitance of sink v
r e Resistance of edge e
c b Input capacitance of buffer b
Output resistance of buffer b or gate g
delay of buffer b or gate g
usually referring to a signal,
b Polarity of buffer b; indicating b is an inverter,
Required arrival time of sink node v
Largest possible wire width (1::W are possible)
library
of leaves of tree T
3 Models and Problem Formulation
3.1 Delay Models
As in previous works, we adopt the Elmore delay model [5] for interconnect delay and standard
RC models for buffer delay.
For a given routing tree possibly containing buffers, delay along a root-sink path is made
of (1) delay along wires and (2) delay through buffers and the driving gate. The computation
of these delays is detailed in the following.
The capacitance c e and resistance r e of wire segment e having width w e are given as:
where ff and fi are characteristic constants 1 .
To compute the Elmore delay of a wire e v in tree T , we first recursively define c(T v ), the
total lumped capacitance of T v , as follows:
c v if v is a sink node
c b else if buffer b placed at v
otherwise
(1)
While our algorithms are presented with this model, we note that it is not key - e.g., such phenomenon as
fringe capacitance can be taken into account
Intuitively, c(T v ) is simply the capacitive load seen at v - i.e., the sum of the loads of
the left and right subtrees, c(T l(v) ), and c(T r(v) ), and the capacitance of the wires to those
sub-trees, c e l(v)
and c e r(v)
. Given this notation, the Elmore delay of wire e v , is defined as
Similarly, the delay through a buffer b at node v in a basic model is determined by the
parameters c(T v ), b's intrinsic (load independent) delay d b and output resistance r b . The delay
through the buffer with load c l on its output is
buf delay(b; c l
The key to buffer insertion in optimizing delay is the well-known isolation property of buffers
exhibited in Equation 1. Namely, the capacitance of a subtree rooted at a buffer, as seen by
ancestors in the tree, is determined entirely by the input capacitance of that buffer. In other
words, the buffer decouples the capacitance of its descendants from its ancestors by the buffer.
A common generalization of this basic buffer delay model includes an additive term to
account for the slew of the signal entering the buffer. One model for this delay is the product
of a buffer dependent constant - b and the load delay of the previous stage, D Lprev - i.e. the
RC delay of the driving buffer. Thus we denote the augmented delay equation as
buf delay slew (b; c l
This and similar models have been proposed in various contexts (e.g., [15],[7]). An extension
of our algorithms to accommodate this delay model is discussed in section 7.
3.2 Maximum Required Time Formulation
We adopt maximization of required arrival time at the root of the net as our timing metric.
The required arrival time at node v, q(T v ), is the latest time at which the input(s) of v
must be available for the required arrival times of all sinks in T v to be met. This measure is
particularly useful since it allows a straight-forward application of our algorithms to optimize
a combinational network by proceeding in bottom-up order. Formally, q(T v ) is defined as:
If the required arrival time, q(T ) at the root is non-negative, the tree T is said to meet
its timing requirements. Note that the required time formulation is a generalization of the
maximum delay formulation - i.e., if q for each sink v then
3.3 Minimizing Power Subject to Timing Requirements
The dynamic power dissipation for CMOS technology P d is given in [18] as
where CL is load capacitance and f p is the switching frequency. Thus, with respect to buffer
insertion and wire sizing, total capacitance is the correct measure of dynamic power dissipation
since f p and VDD are unaffected by these methods.
If we let C total be the total capacitance associated with a buffered and sized routing tree
we have the following problem:
minimize C total
subject to q(T
Alternatively, an attractive approach to the problem is to provide the designer with a
power-delay tradeoff curve from which the desired solution may be chosen.
Implicitly we have assumed that dynamic power dissipation dominates short-circuit power
dissipation. We justify this by the assumption that design techniques have been employed to
eliminate or drastically reduce short-circuit power dissipation.
4 Algorithmic Framework
We first give the framework for a high level dynamic programming algorithm into which all
subsequent algorithms will fit. The framework covers all variants of interest. For instance, if
we are only interested in wire sizing, we simply run the algorithm with an empty buffer library
B. The specific algorithms will differ in their implementation of the basic routines called by
the general algorithm and the characteristics of the solution sets they compute.
This General Dynamic Programming algorithm GDP() is given as pseudo-code in Figure
1. The algorithm computes the solution sets S bot (v) and S top (v). The set S bot (v) can be
thought of as the set of solutions for subtree T v , including the possibility of inserting a buffer
at v. Similarly, the set S top (v) can be thought of as the set of solutions for T v augmented by
the wire from its parent e v and including possible sizing of e v .
The four procedures Base Case(), Bot Solutions(), Top Solutions(), Optimal Soln() are
routines which inductively compute solution sets from the solution sets of descendants. For
each particular algorithm, these sets are parameterized differently. Intuitively, these routines
can be thought of as follows.
Base Case() Compute the singleton set giving relevant parameters at sink v
Bottom Solutions() Given solution sets for left and right children, compute the solution
set at v including the possibility of inserting a buffer at v
Top Solutions() Given the solution set at v, construct the solution set for T v
augmented by wire e v
Optimal Soln() Given the solution set at the root, select the best solution when
combined with the driver
The key to solving a particular problem (e.g. minimizing power subject to timing con-
straints), is in the content of the solution sets, their efficient computation by the above routines
and limiting their size as much as possible to ensure computational efficiency.
In the next section we detail the simplest scenario: maximizing the required arrival q(T )
time at the root of the tree under the basic RC delay model. Subsequently we generalize
this to the problem of minimizing power dissipation subject to given timing constraints again
under the basic RC model. Finally, we further generalize the algorithm to solve either of the
preceding problems with the generalized delay model taking into account the effect of signal
slew. In each of these cases, the algorithms are sketched based on the framework of this section.
Maximizing Required Arrival Time
In this case we maximize q(T ), the required arrival time at the root of T , under the basic
RC delay model. The solution sets S bot (v) and S top (v) are each partitioned into two disjoint
subsets as
bot (v)
top (v):
The reason for this partitioning is to deal appropriately with the fact that, since we may
be using inverters as buffers, the signal may be inverted for some portions of the net. The sets
with superscript "+" contain solutions where we assume the incoming signal is non-inverted
and the sets with superscript "-" contain solutions where the incoming signal is assumed to be
The solutions themselves are load, required-time, or (c; q) pairs. Intuitively, the English
meaning of these sets is, for example,
bot (v) , "There exists an assignment to T v with
upward load c and required time q at v
when the incoming signal is not inverted."
An important initial observation made by van Ginneken [17] is the following.
Property 5.1 For (c; q);
This is clear since a larger load can only worsen delay of ancestor components. In words,
we always prefer smaller load and larger required time. Suppose these sets are arranged in
increasing order of load. This leads to the following property.
Property 5.2 Any load-required time set S in increasing order of load, may be replaced by
strictly increasing in required time.
We maintain this sorted order as an invariant so that we may easily exploit this property.
In the context of our algorithmic framework, we fully specify the algorithm as follows.
Recall that c v and q v are the input capacitance and required arrival time of sink v respectively.
The routine to compute Base Case(v) is simply sets S
bot (v) /
bot (v) / ; since
no valid solution will have an inverted signal at a sink.
Algorithm GDP(T,B,W)
Foreach node v 2 T in topological order from leaves to root
If v is a leaf
Compute
Else
Compute
If v is not the root
Compute
Else /* v is the root */
Compute Optimal

Figure

1: General algorithm structure
Algorithm: Bottom Solutions(v; S top (l(v)); S top (r(v)))
1. /* First compute unbuffered solutions */
2.
bot (v)
3. Let S l
top (l(v))
4. Let S r
top (r(v))
5. /* S l are indexed and ordered by c */
7. While (i - jS l j and j - jS r
8. Let (c l ; q l
9. Let (c r ; q r
bot (v)
11. If (q l - q r ) /* Left Critical */
12. If (q r - q l ) /* Right Critical */
13. Compute
bot (v) analogously
14. /* Now compute buffered solutions */
15. Foreach buffer
16. If b is an inverter
17. Find (c; q)
bot (v) s.t.
c is maximized
18. Else
19. Find (c; q)
bot (v) s.t.
c) is maximized
20. Analogously compute
bot (v)
bot (v)
23.
bot (v) and S \Gamma
bot (v) by Property 5.2

Figure

2: Bottom Solutions() routine for max required time
Computation of Bottom Solutions() is described in pseudo-code in Figure 2. The algorithm
first computes the optimal (c; q) pairs for unbuffered solutions in lines 2-13. For each achievable
arrival time q, we find the smallest load achieving q. This is done in a manner similar to the
merging of two sorted lists time and ensures that Property 5.2 holds. The key is that this is
a linear time operation and the size of the resulting set is linear as observed by van Ginneken
[17]. Next we find the optimal buffer configurations in lines 15-20 by pairing buffers b with
unbuffered solutions at v. We then perform merging and additional pruning in lines 21-23.
Also note that the final pruning step is also linear since the sets are in sorted order.
We give the implementation of Top Solutions() in Figure 3. We examine all pairings of
widths w for wire e v (having length l ev ) with solutions (c; q) at v. Since the loads c 0 are of the
fixed and w 2 f1::Wg, we can visit all c 0 's in order without explicitly
sorting them. For each such pairing, we obtain a new required time. In a final sweep we again
apply Property 5.2 to ensure that the set is in strictly increasing order of both c and q.
Finally, we must implement Optimal Soln(v; S bot (v)). This is done simply by pairing all
of the previously computed non-buffered (c; q)
bot (v)) (since the signal leaving the driver
is non-inverted) with the properties (i.e., output resistance) of the driver and selecting the
solution with the largest resulting required arrival time.
To construct the solution achieving this timing we recursively re-visit the tree to determine
which choices of buffering and wire sizing yield the optimal solution. This is accomplished by
storing with each (c; q) pair, local information indicating the choices which led to that solution.
Comments: For simplicity, we have presented our algorithm in terms of a binary tree, but
note that the algorithm is easily applied to general trees. One straight-forward method to
achieve this is to convert a non-binary tree to an equivalent binary tree simply by adding
zero-length wires. For instance, suppose we have a node v with fanout 3 to nodes A; B and
C. We replace v with two nodes v 0 and v 00 where node v 0 will have children A and B, and v 00
will have children C and v 0 with the wire from v 00 to v 0 having length 0. The algorithm can be
modified to prohibit the placement of buffers at particular nodes - v 0 in this case.
Another issue is that, as described, the algorithm assumes exactly one sizeable wire segment
between nodes and buffer insertion only at nodes in the tree. However, the algorithm
is generalizable to accommodate multiple sizeable segments in a single wire and and buffer
insertion within a wire by introduction of intermediate nodes.
We further note that the algorithm can easily be extended to allow for optimal sizing of the
driving gate if desired. However, it should be realized that such sizing may have global effects
by altering the input capacitance of the driver thereby affecting the timing requirements and
the system as a whole.
These comments apply to subsequent algorithms in this paper.
5.1 Run-Time
We analyze the running time of the basic algorithm in three scenarios:
sizing alone).
insertion alone).
In scenario 1 (wire sizing alone), we introduce the notion of "basic grid-width" to analyze
the complexity.
Property 5.3 In scenario 1 the size of each load-required time set S is bounded by mW where
m is the total number of basic grid lengths in the tree.
This can be seen by considering that the load at node v can be expressed as
where Sink Load is fixed and Interconnect
is the width of
the ith wire and fl is a constant derived from ff, the basic grid length and the minimum width.
Thus, the load is entirely determined by P
w i which can take on any integer value in range
of m::mW . This gives an upper-bound of mW on the sizes of the load-required time sets the
algorithm computes since it bounds the number of distinct load values. Thus, even though
there are an exponential number of width assignments, there are only a polynomial number
of distinct resulting loads. The resulting run-time is O(nW (mW In the case
where every sizeable segment is of identical size, we have O(n 2 W 2 ) since in such a case.
Scenario 2 is a generalization of the situation for the algorithm of van Ginneken [17]. Since
case, computation of S top sets is trivial. Thus the size of the S bot sets is the
key factor in the run-time. We first state the following properties alluded to earlier.
Property 5.4 For S bot (v), let S l and S r be the S top sets of v's left and right children respectively
of the same polarity. The following inequality holds: jS bot (v)j - jS l j
Property 5.5 In scenario 2, for all load-required time sets S, jSj
These properties coupled with the fact that the merging operation is linear in jS l j
an overall worst-case complexity of O(njBj(n
Scenario 3 is complicated by the fact that the input capacitance of the buffers may not be
simple multiples of the capacitance of a unit-length wire. However, in practice it is reasonable
to assume that capacitive values can be linearly mapped onto a polynomially-bounded integer
domain with sufficient precision or are given as such. In such a situation we introduce another
value c max , which is the largest capacitance possible among the individual components of the
tree (e.g., it may be the capacitance of the longest wire at the maximum width). Under this
formulation we upper bound the size of the load-required time sets by ncmax and the overall
run-time by O(n 2 c max (max(W; jBj))). In practice, observed run-times are typically much less
than this bound.
6 Minimizing Power for Given Timing Constraints
We now extend the algorithm to accommodate dynamic power considerations. For clarity, we
present this and subsequent algorithms without regard to signal polarity. Application of the
ideas of the previous section is straight-forward. We note also that the extension presented in
this section can easily be modified by minimize area subject to timing constraints.
The first issue is how to parameterize the solution sets. Now we are not only concerned
with the load and required-time of a sub-solution, but also the power it consumes.
Therefore, solution sets S bot (v) and S top (v) now contain pairs (p; S p ) where p is power
consumption as a capacitive value, and S p is an ordered set of load, required time pairs (c; q)
as in the previous algorithm. For example, (p; indicates that for power p and
every (c; q) 2 S, there exists an assignment for T v consuming power p, presenting load c upward
and yielding required time q at v.
We organize these sets first by sorting them in increasing order of power. Each set S p is
ordered by load c as in the basic algorithm.
One might think that the sets S p are typically singleton sets, however, this is not the case.
Because many different configurations may consume precisely the same power (by, for example,
assigning an identical set of buffers to different locations), these sets can be quite dense.
Recalling that for dynamic power dissipation, capacitance is the correct measure and c v is
the "power" associated with sink v, Base Case(v) simply sets S bot )g)g.
Pseudo-code for Bottom Solutions() is given in Figure 4. We visit all possible values of
total power consumption at v. These values are from among the buffered and unbuffered
configurations. We introduce the notion of a "non-buffer" OE to unify the notation. In this
case, we explicitly sort the values . However, we observe that the number
of such distinct values p is often orders of magnitude less than the worst case (quadratic).
Because of this observation we utilize a hash table to make an initial pass over all pairs to
extract the distinct values which we then sort. This avoids an expensive sorting operation.
Top Solutions() is implemented in a similar manner; its pseudo-code appears in Figure 5.
As described, these algorithms implement two types of pruning. First we prune solutions
for a power p in the same way as before by Property 5.2. However, an additional
pruning condition is utilized in Figures 4 and 5 on lines 9 and 6 respectively. This pruning is
captured in the following property.
Property 6.1 For solution (c; q) consuming power p, if 9 solution
Algorithm: Top Solutions(v; S bot (v))
2. Foreach (c; q)
bot (v); w 2 f1::Wg in increasing
order of c
top (v)
/* elmore delay evaluated at width w */
4. Compute
top (v) analogously
5.
top (v) and S \Gamma
top (v) by Property 5.2

Figure

3: Top Solutions() routine for max required time
Algorithm: Bottom Solutions(v; S top (l(v)); S top (r(v)))
1. Let B
2. S bot (v)
3. Foreach triple (p l ; S p l
in increasing order of
4. Combine S p l
pr as in lines 7-12 of Figure 2 to give S 0
5. If (b 6= OE)
6. Find c) is maximized
7.
8. Else
9.
10. If (p; (previous triple gave same p)
12. Prune S p by property 5.2
13. Else
14. S bot (v) / S bot (v) [

Figure

4: Bottom Solutions() routine for low power
Algorithm: Top Solutions(v; S bot (v))
1. S top is a possible powerg
2. Foreach pair w 2 1::W , (p bot
in increasing order of
3. Foreach (c; q) 2 S p
bot
4. S p /
/* elmore delay evaluated at width w */
5. Prune S p by Property 5.2
7. If (S p 6= ;)
8. S top (v) / S top (v) [

Figure

5: Top Solutions() routine for low power
and q 0 - q then the solution (c; q) is sub-optimal.
The application of this property has proven essential in giving reasonable running times in
practice. Efficient detection of Property 6.1 is addressed subsequently.
We implement Optimal Soln(v; S bot (v)) simply by selecting the lowest power un-buffered
solution at the root giving required-time q(T paired with the driver. Alternatively,
this set of un-buffered solutions gives the full tradeoff curve.
Detection of Property 6.1: When computing the load-required time set S p for power p
in the previous algorithms, we have already computed the load-required time sets S p 0 for all
p. We now want a data-structure to efficiently determine, for each (c; q) 2 S p if Property
6.1 holds. Since the solution sets can grow to be of substantial size, a linear scan to detect this
property would likely be a disaster.
Since we visit the power values in order, we know that the entries in the data structure are
for power values p. Thus the data structure need only concern itself with c and q values.
Thus we need a data structure which efficiently supports the following operations.
update the data structure to reflect solution (c; q)
ffl sub opt(c; q): returns TRUE if 9(c previously inserted s.t. c 0 - c and q 0 - q, FALSE
otherwise.
Such a data-structure solves a special case of the Orthogonal Range Query problem from
Computational Geometry (see e.g., [19]). Our problem is a special case in the sense that
we need not retrieve or count all satisfying the property and the subspace we are
interested in is defined by two inequalities, c 0 - c and q 0 - q, rather than four. In other words,
our subspace is the intersection of the half-planes formed by the inequalities rather than a
rectangle formed by four such inequalities. These special properties of our problem allow us
to support the operations above in O(log m) time and O(m) space for m entries by use of
an augmented binary search tree. In contrast, the fastest known approaches to the general
2-dimensional orthogonal range query problem also run in O(log m) time but use O(m log m)
space.
To support the operations we order a binary search tree tree by load values c. At each node
t of the search tree we store the load value c and the largest q value in the left sub-tree. We refer
to this value as t:q l max . Given this augmentation, insert() is easily implemented recursively
and sub opt() can be implemented by examining the four following cases with respect to c; q
(given) and t:c and t:q l max stored at the current node in the tree (boundary conditions are
not given for clarity):
By following these guidelines recursively down the search tree, we can detect the property in
time proportional to the depth of the tree.
6.1 Run Time
With respect to wire-sizing alone, i.e. we notice that for every power-load-
required time triple since there is no decoupling by buffers. Thus the basic algorithm is sufficient
to solve the low-power problem: we get power minimization "for free".
In the general case of simultaneous wire sizing and buffer insertion (or buffer insertion
alone if we have to take into account the quadratic nature of the algorithm. Since we
examine all pairs of power values from the left and right children the solution sets are no longer
assured to be linear in size. However, when the capacitive values are given as polynomially-
bounded integers or can be mapped to such, once again we can show the run-time of the
algorithm to be polynomial.
As in Section 5.1 let c max be the largest possible capacitive value among the compo-
nents. Under this scenario, we bound the number of load-required time pairs at a node by
This gives an overall run time bound of O(n(jBj
))). The log factor is an artifact of the sorting performed on
the power values.
In practice, we observe much better run times as a result of the additional pruning described
in the previous section (and not included in this analysis since we cannot prove it improves
the worst case performance).
7 Accounting for Signal Slew
We now give a further generalization of the algorithm to account for the effect of signal slew
on buffer delay. The key to our approach is the manipulation of piece-wise linear functions to
model the effect of signal slew.

Overview

By Equation 2, buffer delay is augmented by the term - b D Lprev (recall that - b
is a characteristic constant of buffer b and that D Lprev is the RC delay of the previous stage).
Since our algorithm proceeds in bottom-up order, this is an unknown value when computing
the delay associated with a buffer. Conceptually, we would like to support queries of the form
"What is the optimal solution at v with capacitance c and D
is linear in D Lprev , we utilize piece-wise linear functions to model this ef-
fect. Where we previously had load-required time pairs (c; q), we now have load-required time func
pairs (c; f) where f is a piece-wise linear is the optimal required time q at
v for load c and D
We illustrate the modeling of delay by a piece-wise linear function in Figure 6. Figure 6b
shows the piece-wise linear delay function f at node v in Figure 6a. The left and right subtrees
have maximum delays of 5 and 4 units respectively when D However, since the
left and right subtrees are driven by different buffer types, they have different sensitivities - l
and - r . The straight lines in Figure 6b correspond to the two delay functions contributed by
the two subtrees with slopes corresponding to the sensitivities - l and - r . The resulting delay
function f at node v is shown as a solid line, which is the max of the two. Thus, different
values of D Lprev can result in different critical paths.
We represent a piece-wise linear function f by a linked list of quadruples
each quadruple is a segment starting at point ending at x end and having slope s.
Our manipulation of piece-wise linear functions is based on three basic operations:
The first two of these operations can be performed in a manner similar to the merging of two
sorted lists in linear time by stepping through the lists and examining points of intersection.
Further, they can be generalized to operate on sets of functions rather than pairs by repeated
application, giving for example, pwl max(f 1 ; ::; f k ). The third operation is achieved simply by
adding d to the starting y-coordinate (y 0 ) of each segment in the function.
With respect to the dynamic programming algorithm, we must also associate with each
segment in the piece-wise linear function f the relevant configuration information which yields
the solution (e.g. wire-width, buffer type).
The algorithm modifications are summarized as follows:
(1) Where we had load-required time pairs (c; q), we now have load-required time func pairs
(2) Where we computed scalar max and min operations on arrival times q, we now compute
pwl max and pwl min operations on piece-wise linear functions.
(3) Where we eliminated sub-optimal solutions (c; q) by Properties 5.2 and 6.1, we now
eliminate sub-optimal portions of solutions (c; f) by analogous properties. These sub-optimal
solutions now give required arrival time of \Gamma1 for certain values of D Lprev .
A detailed description of the generalized algorithm follows. For generality, we focus on the
low power formulation of the problem.
Pruning Operations: Before presenting Bottom Solutions() and Top Solutions(), we first
discuss the basic pruning operations used in the algorithm.
Previously, a basic operation in our algorithms was the merging of two load-required time
sets. If we had two sets S 1 and S 2 where the solutions in each set consumed identical power p
(or we were not concerned with power), we computed a new set S
was a set of provably sub-optimal solutions by Property 5.2; i.e., (c; q) 2 S   implied that
We generalize this concept for load-required time func sets. The property analogous to
Property 5.2 is the following:
Property 7.1 Let load-required time set be ordered by load; i.e.
. For
i be defined as:
We may replace
maintaining optimality. Further, if f 0
may be eliminated altogether.
This property is implemented in Figure 7 as the routine Merge Load Func Sets() and is used
by both Bottom Solutions() and Top Solutions().
In addition, the previous low power algorithm utilized a more general pruning method given
by Property 6.1 which said that, for a pair of solutions (p; c; q) and (p
and q - q 0 then (p sub-optimal and may be eliminated. The analogous property for
the slew sensitive generalization is as follows.
Property 7.2 For a solution (p; c; f), let S 0 be the set of all other solutions s.t. (p
iff that In a manner
similar to Property 7.1, we may replace f with
Again, if f 0 may be eliminated entirely.
A generalization of the data-structure in Section 6 is be presented later in this section to
efficiently implement the pruning of Property 7.2.
Finally, we give pseudo-code for Bottom Solutions() and Top Solutions() in Figures 8 and
9 respectively. The routines follow the previous versions quite closely. However, because
Properties 7.1 and 7.2 introduce partially defined functions there is no total order on the (c; f)
sets. Therefore, when combining solutions of children, we may look at all such pairs in the
worst case rather than performing a simple "merge" as previously (Figure 2, lines 7-12). This
can be seen in the for loop of Bottom Solutions() in Figure 8 - for a particular f l [i], we must
find the appropriate f r [j]'s to pair with f l [i]. In the worst case, all j's may be candidates - and
this may hold for all i's. However, in practice these sets tend to remain linear in size. A related
issue is the complexity of the functions themselves. In principle, the size of the functions can
grow exponentially. However, again we do not observe this phenomenon in practice.
Examples: To give intuition on the operation of the algorithm, we now give some illustrations.

Figure

shows function f having load c before and after buffer b is considered for insertion at
v as is performed in Bottom Solutions(). Since b will drive load c, D Lprev for its descendants
l r5
delay
v->sink
(b)
(a)
l l =0.1 =0.2
d=5 d=4

Figure

linear function modelling effect of signal slew
Algorithm: Merge Load-Func
Foreach (c; f) 2 S 0 in increasing order of c
If 9x s.t. f 0
/* Otherwise, (c; f 0 ) is useless */
Return S 0

Figure

7: Algorithm for merging load-func sets (presumably consuming the same power)
Algorithm: Bottom Solutions(v; S top (l(v)); S top (r(v)))
Foreach triple (p l ; S p l
in increasing order of
and pr be indexed */
/* E.g. (c l [i]; f l [i]) is the ith smallest load in */
/* and corresponding piece-wise linear function in S p l
*/
For
Else
Let j be the smallest index s.t. f l [i
While 9x s.t. f r [j](x) ! f l [i](x)
f min /pwl min(f l [i]; f r [j])
Else
arrival time at output of buffer */
segment pwl func. */
Prune solutions in S 0 per Property 7.2
If
Else /* New power value */

Figure

8: Bottom Solutions() routine for low power and signal slew
Algorithm: Top Solutions(v; S bot (v))
1. S top (v)
2. Foreach pair w 2 1::W , (p bot in increasing order of
3. Foreach (c; f) 2 S p bot
4. S p /
5. Prune sub-optimal solutions from S p by Property 7.1
6. Prune sub-optimal solutions from S p by Property 7.2
7. If (S p 6= ;)
8. S top (v) / S top (v) [

Figure

9: Top Solutions() routine for low power and signal slew
is cr b . Therefore, the required arrival time at the output of the buffer is t1. Subtracting the
buffer delay buf delay, we have the required arrival time function at the input of the buffer
shown as a solid line in the right figure with slope \Gamma- b .

Figure

12 illustrates the operation of combining left and right ("top") solutions. For some
values of D Lprev , the left subtree is critical and for others, the right is. The solid line in
the graph on the right shows the function resulting from the pwl min function to capture the
combination of these two solutions.
Algorithm: Prop7.2(t; c; f)
if t=NULL return f
else if c ! t:c
return Prop7.2(t:left; c; f)
else if c - t:c
return f 0
else
return

Figure

10: Implementation of Property 7.2
Implementation of Property 7.2: We now give a generalization of the data-structure of
Section 6 to implement Property 7.2. Given a set of pairs
we want to efficiently compute f 0 as described in Property 7.2. (Recall that as the algorithm
is organized, the power p associated with (c; f) is strictly greater than each p i associated with
each
To accomplish this we alter the previous augmented tree data structure to store the pair
at each tree node t rather than (t:c; t:q l max ). As before, the search tree is
ordered by c. The piece-wise linear function t:f l max is pwl
resides either at t (c or in its left subtree.
Pseudo code implementing Property 7.2 is given in Figure 10 - i.e., given (c; f) we return
the portions of f which are not sub-optimal in the form of f 0 . Updating the data-structure
can be done by recursively traversing the search tree and updating the f l max function at each
node as we go.
The complexity of these operations is logarithmic in the number of entries in the data
structure multiplied by the average complexity of the piece-wise linear operations (which has
been very small in our experiments).
D Lprev D Lprev
buf_delay
cr cr
req-time req-time

Figure

11: Effect of inserting a buffer
8 Experimental Results
We have implemented our algorithms under the C/UNIX environment on a Sun SPARC 20
workstation. We ran our algorithms on randomly generated routing topologies of various
sizes with non-uniform segment lengths. In these experiments, discretization was done on an
arbitrarily large integer domain (e.g. 1; 000; 000), and yet impressive run-times were obtained.
Since our algorithms derive optimal solutions, the main focus of our experiments were
run-time, the nature of the tradeoff curves and the effect of signal slew.
We used 5 different buffer types; the smallest (1X) buffer having r b
:08. The largest buffer was 8X. Intrinsic delay d b was identical for all
buffers and - b was assumed to be inversely proportional to width (largest - b being 0:8, smallest
0:1). Our experiments used a variety of wire widths from 0:5-m to 5-m (additional benefit
typically wasn't observed for our test cases beyond this width). In these experiments, we used
maximum delay as the metric (i.e., all required times of sinks were 0).

Figure

13 shows the optimal power vs. delay curve for a 20 sink net. We utilized both
wire sizing and buffer insertion on this example. Observed run times for nets of this size are
typically in the 20-30 second range. The unsized/unbuffered delay is at the left-most point
and the minimum delay solution is at the right-most point of the curve. Clearly much better
engineering choices appear at the "elbow" of the curve.
Our second set of experiments appear in Table 1. Here we show the importance of taking
slew into account for buffer insertion. We performed experiments on nets ranging from 10 to
sinks. The other variable was a scaling factor K which is a coefficient for - b . We replace
each - b with K- b . For each K we have two columns: B is the result of running the basic
algorithm for min delay and evaluating the delay of the resulting tree taking slew into account
and S is the result of the extended algorithm of section 6. The right-most column is the worst
run-time among all experiments in that row. As K and n grow we see large variation between
observed delays, approaching 50% in one case. For the 10 sink net, the critical path never
included any buffers accounting for the identical delays.
D Lprev D Lprev
f r
req-time req-time

Figure

12: Combination of left and right solutions
4.6 4.8 5.0 5.2 5.4
Power (nF)3.55.5Delay
(ns)

Figure

13: Power-Delay curve for a 20 sink net

Table

1: Basic Algorithm vs. Slew Algorithm for various sensitivities
9 Conclusions
We have presented efficient algorithms for optimal wire sizing and buffer insertion. We adopt
the flexible problem formulation of minimizing power subject to timing constraints and alternatively
can compute the entire power-delay tradeoff curve with no additional complexity.
The algorithm can easily be adapted to perform area minimization. In addition we incorporate
the contribution of signal slew into the delay model which has been shown to be a significant
contributor to overall delay.



--R

"The Fanout Problem: From Theory to Practice,"
"Optimal Wiresizing Under Elmore Delay Model,"
"Simultaneous driver and wire sizing for performance and power optimiza- tion"
"Performance-driven interconnect design based on distributed RC delay model,"
"The Transient Response of Damped Linear Network with particular Regard to Wideband Amplifiers,"
"CMOS Circuit Speed and Buffer Optimization,"
"A Methodology and Algorithms for Post-Placement Delay Optimization,"
"Optimal and Efficient Buffer Insertion and Wire Sizing,"
"A fast and Efficient Algorithm for Determining Fanout Trees in Large Networks,"
"Signal Delay in RC Tree Networks,"
"A Unified Theory for Mixed CMOS/BiCMOS Buffer Optimization,"
"RC Interconnect Optimization under the Elmore Delay Model,"
"Wiresizing and Buffer Sizing for Power-Delay Tradeoffs Using a Sensitivity Based Heuristic,"
"A Heuristic Algorithm for the Fanout Problem,"
"Static Timing Analysis."
"Performance-Oriented Technology Mapping,"
"Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,"
Principles of CMOS VLSI Design
"Computational Geometry,"
--TR
Principles of CMOS VLSI design: a systems perspective
Performance-oriented technology mapping
Performance-driven interconnect design based on distributed RC delay model
Simultaneous driver and wire sizing for performance and power optimization
A methodology and algorithms for post-placement delay optimization
RC interconnect optimization under the Elmore delay model

--CTR
King Ho Tam , Lei He, Power optimal dual-Vdd buffered tree considering buffer stations and blockages, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
Norman Kojima , Yukiko Parameswar , Christian Klingner , Yukio Ohtaguro , Masataka Matsui , Shigeaki Iwasa , Tatsuo Teruyama , Takayoshi Shimazawa , Hideki Takeda , Kouji Hashizume , Haruyuki Tago , Masaaki Yamada, Repeater insertion method and its application to a 300MHz 128-bit 2-way superscalar microprocessor, Proceedings of the 2000 conference on Asia South Pacific design automation, p.641-646, January 2000, Yokohama, Japan
King Ho Tam , Tom Tong Jing , Lei He, Fast dual-vdd buffering based on interconnect prediction and sampling, Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA
Chowdhury , John Lillis, Repeater insertion for concurrent setup and hold time violations with power-delay trade-off, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
Jeng-Liang Tsai , Tsung-Hao Chen , Charlie Chung-Ping Chen, Optimal minimum-delay/area zero-skew clock tree wire-sizing in pseudo-polynomial time, Proceedings of the international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
X. Zeng , D. Zhou , Wei Li, Buffer insertion for clock delay and skew minimization, Proceedings of the 1999 international symposium on Physical design, p.36-41, April 12-14, 1999, Monterey, California, United States
Jin Fuw Lee , D. L. Ostapko , Jeffery Soreff , C. K. Wong, On the signal bounding problem in timing analysis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
Rajeev Murgai, Layout-driven area-constrained timing optimization by net buffering, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
Xiaoping Tang , D. F. Wong, Planning buffer locations by network flows, Proceedings of the 2000 international symposium on Physical design, p.180-185, May 2000, San Diego, California, United States
Hamid Reza Kheirabadi , Morteza Saheb Zamani, An efficient net ordering algorithm for buffer insertion, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
Jason Cong , Lei He, An efficient technique for device and interconnect optimization in deep submicron designs, Proceedings of the 1998 international symposium on Physical design, p.45-51, April 06-08, 1998, Monterey, California, United States
Arlindo L. Oliveira , Rajeev Murgai, An exact gate assignment algorithm for tree circuits under rise and fall delays, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
Jason Cong , Cheng-Kok Koh, Interconnect layout optimization under higher-order RLC model, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.713-720, November 09-13, 1997, San Jose, California, United States
Rajeev Murgai, Performance optimization under rise and fall parameters, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.185-190, November 07-11, 1999, San Jose, California, United States
Minghorng Lai , D. F. Wong, Maze routing with buffer insertion and wiresizing, Proceedings of the 37th conference on Design automation, p.374-378, June 05-09, 2000, Los Angeles, California, United States
Xiaoping Tang , Martin D. F. Wong, Tradeoff routing resource, runtime and quality in buffered routing, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.430-433, January 27-30, 2004, Yokohama, Japan
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
D. Baeres , J. Cortadella , M. Kishinevsky, Layout-aware gate duplication and buffer insertion, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
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
Charles Alpert , Anirudh Devgan, Wire segmenting for improved buffer insertion, Proceedings of the 34th annual conference on Design automation, p.588-593, June 09-13, 1997, Anaheim, California, United States
P. Sarkar , C. Koh, Repeater block planning under simultaneous delay and transition time constraints, Proceedings of the conference on Design, automation and test in Europe, p.540-545, March 2001, Munich, Germany
Takumi Okamoto , Jason Cong, Buffered Steiner tree construction with wire sizing for interconnect layout optimization, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.44-49, November 10-14, 1996, San Jose, 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
Minghorng Lai , D. F. Wong, Memory-efficient interconnect optimization, Proceedings of the 2001 conference on Asia South Pacific design automation, p.198-202, January 2001, Yokohama, Japan
J. Cong , C. Koh , K. Leung, Simultaneous buffer and wire sizing for performance and power optimization, Proceedings of the 1996 international symposium on Low power electronics and design, p.271-276, August 12-14, 1996, Monterey, California, United States
Feodor F. Dragan , Andrew B. Kahng , Ion Mandoiu , Sudhakar Muddu , Alexander Zelikovsky, Provably good global buffering by multi-terminal multicommodity flow approximation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.120-125, January 2001, Yokohama, Japan
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
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
Xiaoping Tang , Ruiqi Tian , Hua Xiang , D. F. Wong, A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin , Ching-Yen Ho, New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing, Proceedings of the 33rd annual conference on Design automation, p.395-400, June 03-07, 1996, Las Vegas, Nevada, United States
Chakraborty , Rajeev Murgai, Layout-driven Timing Optimization by Generalized De Morgan Transform, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.647, January 07-11, 2002
Ruiming Li , Dian Zhou , Jin Liu , Xuan Zeng, Power-Optimal Simultaneous Buffer Insertion/Sizing and Wire Sizing, Proceedings of the IEEE/ACM international conference on Computer-aided design, p.581, November 09-13,
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 , Lei He, An efficient approach to simultaneous transistor and interconnect sizing, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.181-186, November 10-14, 1996, San Jose, California, United States
Sampath Dechu , Zion Cien Shen , Chris C. N. Chu, An efficient routing tree construction algorithm with buffer insertion, wire sizing and obstacle considerations, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.361-366, January 27-30, 2004, Yokohama, Japan
Henrik Esbensen , Ernest S. Kuh, A performance-driven IC/MCM placement algorithm featuring explicit design space exploration, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.1, p.62-80, Jan. 1997
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
Jason Cong , Lei He, Optimal wiresizing for interconnects with multiple sources, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.4, p.478-511, Oct. 1996
Christoph Bartoschek , Stephan Held , Dieter Rautenbach , Jens Vygen, Efficient generation of short and fast repeater tree topologies, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
Rajeev Murgai, Technology-based transformations, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
Jason Cong , Patrick H. Madden, Performance driven global routing for standard cell design, Proceedings of the 1997 international symposium on Physical design, p.73-80, April 14-16, 1997, Napa Valley, California, United States
Jason Cong , Zhigang Pan , Lei He , Cheng-Kok Koh , Kei-Yong Khoo, Interconnect design for deep submicron ICs, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.478-485, November 09-13, 1997, San Jose, California, United States
Massoud Pedram , Hirendu Vaishnav, Power Optimization in VLSI Layout: A Survey, Journal of VLSI Signal Processing Systems, v.15 n.3, p.221-232, March 1997
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
timing optization;elmore delay;Dynamic Power Dissipation;dynamic programming;signal slew