Optimal wiresizing for interconnects with multiple sources.
The optimal wiresizing problem for nets with multiple sources is studied under the distributed Elmore delay model. We decompose such a net into a source subtree (SST) and a set of loading subtrees (LSTs), and show the optimal wiresizing solution satisfies a number of interesting properties, including: the LST separability, the LST monotone property, the SST local monotone property and the general dominance property. Furthermore, we study the optimal wiresizing problem using a variable grid and reveal the bundled refinement property. These properties lead to efficient algorithms to compute the lower and upper bounds of the optimal solutions. Experiment results on nets from an Intel processor layout show an interconnect delay reduction of up to 35.9\% when compared to the minimum-width solution. In addition, the algorithm based on a variable grid yields a speedup of two orders of magnitude without loss of accuracy, when compared with the fixed grid based methods.
INTRODUCTION
Interconnect delay has become the dominating factor in determining system
performance in deep submicron VLSI designs. Recently developed
techniques for interconnect delay minimization in the physical design level
This work is partially supported by ARPA/CSTO under contract J-FBI-93-112, the NSF Young
Investigator Award MIP-9357582, and a grant from Intel Corporation under the NYI matching
award program. An extended abstract of this paper was presented in ICCAD'95.
Authors' addresses: Department of Computer Science, University of California, Los Angeles,
Permission to make digital / hard copy of part or all of this work for personal or classroom use
is granted without fee provided that the copies are not made or distributed for profit or
commercial advantage, the copyright notice, the title of the publication, and its date appear,
and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to
republish, to post on servers, or to redistribute to lists, requires prior specific permission
and / or a fee.
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996, Pages 478 -511.
fall into two categories. One is topology optimization, such as the constructions
of bounded-radius bounded-cost trees [Cong et al. 1992], AHHK trees
[Alpert et al. 1993], A-trees [Cong et al. 1993], low-delay trees [Boese et al.
1993], and IDW/CFD trees [Hong et al. 1993]. In essence, these methods
construct an interconnect tree to minimize both the total tree length and
the paths between the input pin (also called the source) and a set of
timing-critical output pins (also called critical sinks), whereas the conventional
Steiner tree algorithms minimize only the total tree length. In
addition, the nontree routing for delay minimization was explored in
McCoy and Robins [1994] and Xue and Kuh [1995].
The other type of interconnect optimization methods is wiresizing optimi-
zation, which computes optimal wire width for each wire segment in the
interconnect to minimize the interconnect delay. In the earlier works [Cong
et al. 1993; Cong and Leung 1993, 1995], Cong et al. modeled the routing
tree as a distributed RC tree and formulated the wiresizing problem under
the Elmore delay model to minimize a weighted average delay from the
source to a set of critical sinks. They developed the first polynomial-time
optimal algorithm based on the separability, the monotone property, and
the dominance property. Later on, Sapatnekar [1994] used the sensitivity-based
heuristic and the convex programming technique [Sancheti and
Sapatnekar 1994] for the optimal wiresizing problem to minimize the
maximum interconnect delay, since the Elmore delay along a RC tree is a
posynomial function of wire widths as first pointed out in Fishburn and
Dunlop [1985]. Other recent wiresizing works include the greedy algorithm
for performing wiresizing during tree construction [Hodes et al. 1994], the
nonuniform wiresizing during the multilink insertion for existing interconnects
[Xue and Kuh 1995], and the continuous nonuniform wiresizing based
on a Lagrangian relaxation procedure [Chen et al. 1996a,b]. The Elmore
delay model is used in Hodes et al. [1994], Xue and Kuh [1995], Chen et al.
[1995a,b]. In addition, more accurate delay models are used in the following
works: the moment-fitting based wiresizing [Menezes et al. 1994] under a
higher-order RC delay model, and the sensitivity-based wiresizing [Xue et
al. 1996] under a lossy transmission line model for trees of transmission
lines.
Recently, wiresizing has been conducted simultaneously with device
sizing to further reduce the interconnect delay. Cong and Koh [1994]
formulated the simultaneous driver and wire sizing (SDWS) problem under
the Elmore delay model. They revealed a dominance relation between the
driver sizing and the correspondent optimal wire sizing, and developed an
efficient SDWS algorithm. Later, Menezes et al. [1995] treated the simultaneous
gate and wire-sizing problem as a posynomial program under both
the Elmore delay model and a higher-order RC delay model. The posynomial
program is further transformed into a convex program and then solved
by the sequential quadratic programming method. Furthermore, Lillis et
al. [1995] proposed a simultaneous wiresizing and buffer insertion algorithm
under the Elmore delay model, based on the dynamic programming
Optimal Wiresizing for Interconnects . 479
scheme originally developed for the optimal buffer placement of van Ginneken
[1990].
All these interconnect optimization methods assume that there is a
unique source in each interconnect tree (called a single source interconnect
tree (SSIT)) and minimize the delay between the source and a set of
critical sinks. However, there exist many important interconnect structures
with multiple potential sources, each driving the interconnect at a different
time, such as those in global signal buses. None of the existing interconnect
optimization methods consider such multisource interconnect trees
(MSITs), except a very recent work by Cong and Madden [1995], where an
MSIT topology optimization method based on the construction of min-cost
min-diameter A-trees was developed, and a smaller delay was achieved
when compared with the conventional routing methods. Although those
single-source wiresizing algorithms based on mathematical programming 1
or sensitivity analysis [Sapatnekar 1994; Xue et al. 1996] might be adapted
to minimize the delay between the multiple source-sink pairs by modifying
their objective functions, it is of both theoretical and practical interest to
understand the properties of the optimal wiresizing solutions for MSITs
and develop efficient algorithms directly for MSITs.
In this paper, we study the optimal wiresizing problem for MSITs under
the RC tree model and the Elmore delay model. We decompose an MSIT
into a source subtree (SST) and a set of loading subtrees (LSTs), and show
a number of interesting properties of the optimal wiresizing solutions
under this decomposition, including: the LST separability, the LST monotone
property, the SST local monotone property, and the dominance prop-
erty. These properties lead to effective algorithms to compute the optimal
wire width assignment for any given MSIT. We have tested our algorithm
on multisource nets extracted from the multilayer layout of a high-performance
Intel processor. SPICE simulation shows that our methods reduce
the average delay by up to 23.5% and the maximum delay by up to 37.8%
for the submicron CMOS technology. Furthermore, we study the optimal
wiresizing problem using a variable segment-division rather than an a
priori fixed segment-division as used in all previous works. We show the
bundled refinement property that leads to a very efficient wiresizing
algorithm based on bundled refinement operations and segment-division
refinement operations. The algorithm yields a speedup of over 1003 time
and does not lose any accuracy, when compared to the method based on a
priori fixed segment-division. Finally, we also investigate the fidelity of the
Elmore delay model for wiresizing optimization using the ranking technique
similar to that of Boese et al. [1993]. We have found that the optimal
wiresizing solution selected according to the Elmore delay model is about
worse than the optimal wiresizing solution selected according to the
SPICE-computed delay, when the delays of both solutions are measured by
SPICE simulation. This experiment convincingly justifies our formulation
1 Sancheti and Sapatnekar [1994], Menezes et al. [1994, 1995], Xue and Kuh [1995], Chen et
al. [1996a].
480 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
based on the Elmore delay model for the current submicron CMOS technol-
ogy. To the best of our knowledge, it is the first work that presents an
in-depth study of both the optimal wiresizing problem for MSITs and the
optimal wiresizing problem under a variable segment-division.
The remainder of this paper is organized as follows. In Section 2, we
present the formulation of the MSIT wiresizing problem. In Sections 3 and
4, we study the properties of the optimal wiresizing solutions for MSIT
designs, under the a priori fixed and the variable segment-divisions,
respectively. These properties lead to efficient algorithms given in Section
5. Section 6 shows experimental results, including the fidelity study of the
Elmore delay model. Section 7 concludes the paper with discussions of
future work. The proofs of the Theorems 3, 5, and 6 are given in the


Appendix

. Proofs of other theorems, together with more experimental
results, can be found in a technical report [Cong and He 1995b].
2. PROBLEM FORMULATION
2.1 Multisource Wiresizing (MSWS) Problem
We call the wiresizing problem for MSITs the multisource wiresizing
(MSWS) problem. For an MSIT, each pin in the MSIT can be a source
(driver), or a sink (receiver), or both at different times. We assume,
however, no two sources in the MSIT are active at the same time. Let a
node be either a pin or a Steiner point in the MSIT and src(MSIT) the set
of pins that can be sources of the MSIT. We say that sink i (MSIT) is the set
of sinks in the MSIT when pin N i is the source of the MSIT. In addition, let
a segment connect two nodes and {S 1 , S 2 , . , S m } be the set of segments
in the MSIT. In order to capture the distributed resistive property of
interconnects and achieve better wiresizing solutions, a segment is divided
into a sequence of unisegments. The term "unisegment" is coined based on
this assumption that the wire width is uniform within a unisegment. The
segment-division determines the set of all unisegments, {E 1
in the MSIT. Our wiresizing problem is formulated to find a wire width for
each unisegment from a set of given choices {W 1 , W 2 , . , W r } (W 1 , W 2
, . , W r ). Different from our formulation, a segment in Cong and Leung
[1993, 1995] is not further divided and is simply treated as a unisegment; 2
a segment in Cong and Koh [1994] is divided into a sequence of wires of
unit length, and such a wire of unit length is treated as a unisegment.
Thus, both segment-divisions in Cong and Leung [1993, 1995] and Cong
and Koh [1994] are given a priori and fixed during the wiresizing proce-
dure. In our formulation, the segment-division is in fact a variable during
the wiresizing procedure and is defined by the wiresizing procedure, which
is discussed later in Section 4. For simplicity, we assume that an a priori
fixed segment-division is given in this section.
We note that artificial degree-2 Steiner points can be introduced within a segment in Cong
and Leung [1993, 1995] to achieve certain segment-division.
Optimal Wiresizing for Interconnects . 481
The modeling technique similar to those used in Cong and Leung [1993,
1995] and Cong and Koh [1994] is applied. Each unisegment is treated as a
p-type RC circuit containing resistance r E and capacitance c E , respectively.
Let the unit-width unit-length wire have wire resistance r 0 , wire area
capacitance c 0 , and wire fringing capacitance c 1
length l E . The driver at source N i is modeled by an output capacitance C d
and a fixed-value resistor R d
i connected to an idle voltage source, and the
receiver at sink N j by a loading capacitor c s
. Thus, a given interconnect
including its drivers and receivers is modeled by a distributed RC tree. The
Elmore [1948] delay t ij in the RC tree from source N i to sink N j is a
function of the segment-division % and the wiresizing solution 0. It can be
written as Equation (1) according to the Elmore delay formulation for RC
trees [Rubinstein et al. 1983].
where the summation is taken over all unisegments on the unique path
to sink N j , and C E is the total downstream
capacitance of unisegment E with respect to source N i . In order to handle
multiple source-sink pairs, we further introduce the following weighted
delay formulation Equation (2).
t~MSIT, %, 0! 5 O
O
l ij is the penalty weight to indicate the priority of the Elmore delay
source N i and sink N j .
With these definitions, we give the general formulation of the MSWS
problem as follows.
Formulation 1. Given an MSIT, a segment-division % and a set of
possible wire width choices, the multisource wiresizing (MSWS) problem
for delay minimization is to determine a wiresizing solution 0 that gives a
wire width w E for every unisegment E under %, such that the weighted
delay t(MSIT, %, 0) is minimized.
When there is only one source in an interconnect tree, the MSWS
problem degenerates into the single-source wiresizing (SSWS) problem.
Note that we assume a given segment-division in Formulation 1. A more
general wiresizing problem, the multisource wiresizing problem without an
a priori given segment-division (the MSWS/E problem) is presented in
Section 4.
2.2 Weighted Delay Formulation
For simplicity, we assume that all interconnects belong to the same layer
and the assumption is removed later in Section 3.3. It is not difficult to
482 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
verify that the Elmore delay t ij between source N i and sink N j can be
formulated as follows.
l Ew E
are, respectively, the (wire) width and length of the
unisegment E. _ 0
are constants independent of the
wiresizing solution, as given in the following.
c s
1Recall that R d
i are the driving resistance and output capacitance
for the driver at source N i , and c s
u the sink capacitance at sink N u . These
parameters can take account the different sizes of drivers/receivers at
different sources/sinks of an MSIT. Besides, f ij (E, E9),
defined in the following, again are constants independent of the wiresizing
solution.
Optimal Wiresizing for Interconnects . 483
where Des i (E) is the set of downstream unisegments of E with respect to
source N i , and sink i (E) the set of downstream sinks of E with respect to
source N i .
Assume that l ij s are normalized, that is,
O
O
the objective function Equation (2) becomes:
F~E, E9! z
F~E, E9! z
G~E! z
H~E! z
l Ew E
where
O
O
O
O
O
484 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
Our MSWS problem is aimed at finding the optimal w E s to minimize the
weighted delay formulation Equation (7). Although this weighted delay
formulation for multiple sources and multiple sinks is very similar to that
for the single source and multiple sinks in Cong and Koh [1994], the
coefficient functions F, G, and H have very different properties, which lead
to much higher complexity and very different properties for the MSWS
problem when compared to the SSWS problem. These properties are
discussed in Section 3.
3. PROPERTIES OF OPTIMAL MSWS SOLUTIONS
The SSWS problem under an a priori fixed segment-division was studied in
Cong and Leung [1993, 1995], and the polynomial-time optimal algorithm
was developed based on a separability, the monotone property, and the
dominance property. The presence of multiple sources, however, greatly
complicates the wiresizing problem. For example, with multiple sources,
even a monotone wiresizing solution is not well defined. Nevertheless, our
research has revealed a number of interesting properties of the optimal
MSWS solutions under the decomposition of MSITs. Some of them generalize
the results on the SSWS problem, and others are unique for the MSWS
problem. These properties (presented in this section and Section enable
us to apply the algorithms developed in Cong and Leung [1993, 1995] to the
MSWS problem to a certain extent and to develop even more efficient
algorithms in Section 5.
3.1 Decomposition of an MSIT
When there is only one source in the routing tree, each segment has a
unique signal direction and the ancestor-descendant can be defined with
respect to the direction. The MSWS problem is most complicated by the fact
that, in general, there is no fixed signal direction for a segment. In order to
reduce the complexity with the MSWS problem, we decompose an MSIT
into the source subtree (SST) and a set of loading subtrees (LSTs) (see

Figure

1). The SST 3 is the subtree spanned by all source nodes in the
MSIT. After we remove the SST from the MSIT, the remaining segments
form a set of subtrees, each of them called an LST. When every pin of an
MSIT can be a source at different times, the entire MSIT becomes the SST
and there is no LST.
Parallel to the ancestor-descendant relation in an SSIT, the left-right
relation is introduced in an MSIT. We choose an arbitrary source as the
leftmost node Lsrc. The direction of the signal flowing out from Lsrc is
defined as the right direction along each segment S. Under such definition,
the signal in any LST always flows rightward, but the signal may flow
either leftward or rightward in a segment in the SST. The properties of
3 Note that SST defined in this paper is different from that defined in Cong and Leung [1993,
1995], where SST is used to denote a single stem tree.
Optimal Wiresizing for Interconnects . 485
optimal MSWS solutions are studied in the context of the MSIT decomposition

3.2 Properties of Optimal MSWS Solutions
LST Separability.
THEOREM 1. Given the wire width assignment of the SST, the optimal
width assignment for each LST branching off from the SST can be carried
out independently. Furthermore, given the wire width assignment of both
the SST and a path P originated from the root of an LST, the optimal wire
width assignment for each subtree branching off from P can be carried out
independently.
The first part of Theorem 1 is the separability between LSTs. Thus, for
the MSIT in Figure 1, the optimal wire widths for LST 1 , LST 2 , and LST 3
can be computed independently if the wire widths for the SST are given.
The second part of Theorem 1 is the separability within an LST, which is
the counterpart of the separability in the SSWS problem since an LST can
be viewed as an SSIT with its driver located at the branching node from the
SST. Because the separability may not hold within the SST, the MSWS
problem has much higher complexity than the SSWS problem in general.
LST Monotone Property.
THEOREM 2. For an MSIT, there exists an optimal wiresizing solution 0*
where the wire widths decrease monotonically rightward within each LST
in the MSIT.
Again, with respect to the analogy between an LST and an SSIT, and
replacing the left-right relation in the LST with the ancestor-descendent
relation in an SSIT, the LST monotone property is just like the monotone
property for the SSWS problem. Because the optimal wiresizing algorithm
OWSA developed in Cong and Leung [1993, 1995] for the SSWS problem is
based on the separability and the monotone property, according to Theorems
1 and 2, it can be applied independently to each LST when the wire
width assignments for the SST are given. Since OWSA is a polynomial-time
Fig. 1. MSIT decomposed into the source subtree SST and a set of loading subtrees (three
LSTs here) branching off from the SST. Dark segments belong to the SST.
486 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
algorithm, the optimal wire widths for the entire MSIT will be computed in
the polynomial-time with respect to the given wire widths for the SST.
Furthermore, it is worthwhile emphasizing that the monotone property
for the MSWS problem just holds within an LST. The root unisegment in
an LST may be wider than the unisegment from which the LST branches.
An optimal MSWS solution based on the parameter for the second metal
layer (M2) given in Table I is shown in Figure 2. The total wire length is
600 mm. In the optimal solution, the wire width assignment is monotone
within the LST, however, the root unisegment of the LST is wider than
unisegments in the SST. This example also shows that the monotone
property like that in the SSWS problem does not hold for any particular
source in an MSIT.
SST Local Monotone Property. Although the signal direction is changeable
in the segments of the SST when different sources are active, surpris-
ingly, our study shows the optimal MSWS solutions still satisfy a local
monotone property (Theorem
LEMMA 1. Given an MSIT and a segment S in the MSIT, for any
unisegments defined in
Equation (10) is an invariant (denoted F l (S)) if E 1 is left of
right of E 2 .
THEOREM 3. There exists an optimal wiresizing solution for an MSIT,
such that the wire widths within each segment are monotone: (1) if F l (S) .
F r (S), the wire widths within S decrease monotonically rightward; (2) if
F l (S) 5 F r (S), the wire width within S does not change; (3) if F l (S) ,
F r (S), the wire widths within S increase monotonically rightward.
Of course, the local monotone property holds for segments in LSTs, where
the F l (S) is always greater than F r (S) [in fact, F r (S) 5 0] and the wire
widths always decrease rightward, just as given by the LST monotone
property in an even stronger sense.
Fig. 2. Optimal wire width assignments for a two-source net with w being the minimum wire
width. Dashed curve surrounds the SST. Segments outside curve belong to the LST.
Optimal Wiresizing for Interconnects . 487
Dominance Property.
Definition 1. Given two wiresizing solutions 0 and 09, we define %
dominates unisegment E.
Definition 2. Given a wiresizing solution 0 for the routing tree, and any
particular unisegment E in the tree, a local refinement on E is defined to
be the operation to minimize the objective function Equation (7) by changing
only the wire width of E while keeping the wire width assignment of 0
on other unisegments unchanged.
THEOREM 4. Suppose that 0* is an optimal wiresizing solution for an
MSIT. If a wiresizing solution 0 dominates 0*, then the wiresizing
solution obtained by any local refinement of 0 still dominates 0*. Simi-
larly, if 0 is dominated by 0*, then the wiresizing solution obtained by any
local refinement of 0 is still dominated by 0*.
Although the dominance property was proven based on the ancestor-
descendent relation in Cong and Leung [1993, 1995] for the SSWS problem,
we proved that it not only holds for the MSWS problem, but is also
independent of the ancestor-descendent relation in the SSWS problem, or
the left-right relation in the MSWS problem. Theorem 4 enables efficient
computations of lower and upper bounds of the optimal wiresizing solution
for the MSWS problem by the greedy wiresizing algorithm GWSA [Cong
and Leung 1993, 1995] originally developed for the SSWS problem. It
applies the local refinement operation iteratively to every unisegment to
compute the lower or the upper bound of the optimal wiresizing solution. A
much more powerful refinement operation, called the bundled refinement
operation, which may compute the lower or the upper bound for a number
of unisegments in a single operation, is introduced in Section 4.2.
3.3 Extensions to Multilayer Layout
Up to now, all properties have been discussed under the assumption that
all wires lay in the same routing layer. In real layout designs, interconnects
are often routed using more than one layer. Similar to the extension made
for the SSWS problem in Cong and Leung [1995], the MSWS formulation
can be extended to the multilayer cases. In the multilayer formulation, the
LST separability and the dominance property still hold. The LST monotone
property holds within each layer; that is, there always exists an optimal
wiresizing solution such that the wire widths decrease monotonically
rightward within each layer for each LST. Furthermore, even in the same
layer, if the allowable minimum and maximum wire widths are different
from segment to segment due to obstacles in the routing area or reliability
considerations, the LST monotone property holds only within segments in
the same layer such that these segments have uniform allowable minimum
and maximum wire widths. Moreover, it is reasonable to assume that each
segment always stays in the same layer and its allowable minimum and
maximum wire widths remain unchanged within the segment. In this case,
488 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
the local monotone property always holds. Note that all discussions and the
bundled refinement property to be presented in Section 4, just as the
dominance property, hold for any layer assignment and any allowable
minimum or maximum wire width.
4. PROPERTIES OF OPTIMAL MSWS/E SOLUTIONS
Up to now, both the MSWS problem defined in this article and the SSWS
problem studied in the literature 4 are only studied in the context of an a
priori fixed segment-division. Intuitively, a finer segment-division may lead
to a better wiresizing solution. However, it is difficult to choose a proper
segment-division. For the best accuracy, a very fine, often uniform seg-
ment-division needs to be chosen, which results in high memory usage and
computation time due to the large number of unisegments. We now
investigate methods to obtain the optimal wiresizing results using a
nonuniform and coarser segment-division. A novel contribution of our work
is to introduce an MSWS formulation based on a variable segment-division.
The segment-division might be finer in some regions but coarser in others.
Moreover, we begin with a coarser segment-division and then proceed to a
finer one. Theorem 5, to be presented in Section 4.2, justifies this strategy
and leads to much more efficient algorithms with the same accuracy when
compared with previous work. All properties in this section hold for both
the MSWS problem and the SSWS problem, but we concentrate on the
MSWS problem since the SSWS problem can be treated as a special case.
4.1. Segment-Division and Bundled-Segment
We assume that minLength is a constant determined by the user or the
technology such that the wire widths are allowed to change every min-
Length long; in other words, minLength is the minimum length that a
unisegment can be. Given an MSIT, let % 0 be the segment-division where
each unisegment is a segment in the MSIT, and % F the uniform segment-
division where each unisegment is minLength long. 5 Given two segment-
divisions % and %9, if each unisegment in % corresponds to single or
multiple unisegments in %9, we say that %9 is a refinement of %. A
segment-division % is valid only if % is a refinement of % 0 and the length of
every unisegment is a multiple of minLength. Clearly, among all valid
segment-divisions, % 0 is coarsest and % F is finest.
With these definitions, the variable segment-division multisource wire-sizing
(MSWS/E) problem, can be formulated as follows.
Formulation 2. Given an MSIT, the minimum unisegment length min-
Length, and a set of possible wire width choices, the MSWS/E problem for
delay minimization is to determine both a segment-division % and a
4 Cong and Leung [1993, 1995], Cong and Koh [1994], Sapatnekar [1994], Menezes et al. [1994,
1995], Lillis et al. [1995], Xue and Kuh [1995], Xue et al. [1996].
5 For simplicity, we assume that the length of any segment in an MSIT is a multiple of
minLength.
Optimal Wiresizing for Interconnects . 489
wiresizing solution 0, such that the weighted delay t(MSIT, %, 0) is
minimized.
Definition 1 is extended to consider the variable segment-division cases.
Definition 3. Given two wiresizing solutions 0 and 09, we define 09
dominates unisegment E under the finest
segment-division % F .
The concept of bundled-segment is defined in order to achieve a segment-
division as coarse as possible without the loss of wiresizing accuracy.
Definition 4. Given an MSIT, a segment S and the finest segment-
division be a maximal sequence of successive uniseg-
ments in S and under % F such that all unisegments in this sequence have
the same wire width in the optimal wiresizing solution under % F , we say
that these unisegments in the sequence form a bundled-segment.

Figure

3 illustrates the concept of the bundled-segment by showing the
optimal wiresizing solution for segment S in an MSIT. It has 12 uniseg-
ments under the finest segment-division % F (Figure 3.a), but just 3 bun-
dled-segments (Figure 3.b). Clearly, the segment-division defined by the
bundled-segments can achieve the same wiresizing solution as that obtained
by the finest segment-division % F . For a long segment or a small
minLength used in order to achieve a better wiresizing solution, the
number of unisegments under the finest segment-division tends to be quite
large whereas the number of bundled-segments in the segment is always
bounded by a really small constant, as given by the following corollary of
the local monotone property (Theorem 3).
COROLLARY 1. Each segment in an MSIT has at most r bundled-segments
where r is the number of possible wire width choices.
Fig. 3. Optimal wiresizing solution for segment S: (a) under the finest segment-division; (b)
under a coarser segment-division with fewer computation costs.
490 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
Obviously, using the segment-division defined by the bundled-segments
can achieve the required wiresizing solution for the lowest costs. A bundled
refinement operation that leads to the computation of the optimal width for
a bundled-segment directly, instead of treating it as a sequence of uniseg-
ments under the finest segment-division % F , is presented in the next
subsection.
4.2 Bundled Refinement Property
Let 0 be a wiresizing solution that dominates the optimal solution 0*, and
E be a unisegment under the current segment-division % and in segment S.
Without loss of generality, we assume F l (S) r (S) and treat E as two
unisegments E l and E l during the bundled refinement operation. E l is the
leftmost part of E, with length minLength (recall minLength is the length
for a unisegment in the finest segment-division % F ); E l is the remaining
part of E. Let w- E l
be the locally optimized width for E l based on the
objective function Equation (7) while keeping the width assignment of 0 on
l and any unisegment E9 other than E. Then, w- E l
is regarded as a refined
upper bound of the entire unisegment E (not only E l ). This operation is
called a bundled refinement operation for the upper bound (BRU).
The rationale for the BRU operation is as follows: if F l (S) r (S), in the
optimal solution 0*, E l is always wider than all unisegments under % F in
l (according to the local monotone property). The refinement of an upper
bound of w* E is still an upper bound of it (according to the dominance
property), thus it also gives an (possibly refined) upper bound of the
optimal wire width assignment for any unisegment under % F in E l . Note
that E will not be divided into E l and E l when performing the BRU
operation on unisegments other than E.
Similarly, the bundled refinement operation for the lower bound (BRL)
can be defined for a wiresizing solution 0 dominated by 0*. Again,
assuming F l (S) r (S), we treat E as two unisegments E r and E r . E r is
the rightmost part of E, with length minLength; E r is the remaining part of
be the locally optimized width for E r based on the objective
function Equation (7) while keeping the assignment of 0 on E r and any
unisegment E9 other than E. Then, w- E r
is regarded as a refined lower
bound of the entire unisegment E.
Concerning the bundled refinement operation, the bundled refinement
property similar to the dominance property for the local refinement operation
is given as Theorem 5, which leads to the bundled wiresizing algorithm
presented in Section 5.1.
THEOREM 5. Let 0* be an optimal wiresizing solution under % F . If a
wiresizing solution 0 dominates 0*, then the wiresizing solution obtained
by any BRU operation on 0 under any segment-division % still dominates
0*. Similarly, if 0 is dominated by 0*, then the wiresizing solution
obtained by any BRL operation on 0 under any segment-division % is still
dominated by 0*.
Optimal Wiresizing for Interconnects . 491
5. OPTIMAL MSWS ALGORITHM
5.1 Bundled Wiresizing Algorithm
Based on the dominance property (Theorem 4), the greedy wiresizing
algorithm GWSA [Cong and Leung 1993, 1995] originally developed for the
SSWS problem is applicable to the MSWS problem. Working on an a priori
defined segment-division, GWSA can use local refinement operations to
compute the lower or the upper bound of the optimal wiresizing solution
starting with the minimum or the maximum wire width assignment,
respectively. Based on the bundled refinement property, a new algorithm,
the bundled wiresizing algorithm (BWSA) (Figure 4) is proposed to compute
the lower and upper bounds of the optimal wiresizing solution for an MSIT.
BWSA also starts with the minimum and maximum wire width assign-
ments, but uses bundled refinement operations instead of local refinement
operations, and a gradually refined segment-division rather than a fixed
one. BWSA achieves the same optimal lower and upper bounds for much
less computation costs when compared with GWSA.

Overview

. Starting with the coarsest segment-division % 0 , we perform
BRU and BRL iteratively through an MSIT. We assign the minimum width
to all unisegments (in this case, each unisegment is a segment), then
traverse MSIT and perform BRL operation on each unisegment. This
process is repeated until no improvement is achieved on any unisegment in
the last round of traversal. Because the minimum wire width assignment is
dominated by the optimal wiresizing solution, according to the bundled
refinement property, the resulting wiresizing solution is still dominated by
the optimal wiresizing solution and is a lower bound of it. Similarly, we
assign the maximum width to all unisegments and perform BRU opera-
tions, obtain an upper bound of the optimal wiresizing solution. This is the
first pass of BWSA.
After each pass, we check the lower and upper bounds. If there is a gap
between the lower and upper bounds for a unisegment (which is called a
nonconvergent unisegment) and it is still longer than the minimum uniseg-
ment length minLength, we divide it into two unisegments of almost equal
length (they may differ by minLength in order to maintain a valid segment-
division), and let each unisegment inherit the lower and upper bounds from
the parent. After the refinement of all nonconvergent unisegments, another
pass to tighten the lower and upper bounds is carried out by performing
bundled refinement operations under the refined segment-division. Note
that the bundled refinement is only needed for unisegments that are just
refined, because only these unisegments are not convergent.
This BWSA algorithm iterates through a number of passes until we
either have the identical lower and upper bounds for all unisegments under
current segment-division (in this case we get an optimal wiresizing solu-
tion), or each nonconvergent unisegment is minLength long.
492 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
Optimality. In order to discuss the optimality of the lower and upper
bounds obtained by the BWSA algorithm, we define the following % F -tight
lower and upper bounds.
Fig. 4. Bundled wiresizing algorithm (BWSA).
Optimal Wiresizing for Interconnects . 493
Definition 5. If a wiresizing solution 0 dominates the optimal solution
0* and cannot be further refined by any local refinement operation under
the finest segment-division % F , 0 is an % F -tight upper bound. Similarly, 0
is an % F -tight lower bound if 0 is dominated by 0* and cannot be further
refined by any local refinement operation under % F .
It is easy to find that the lower and upper bounds given by the GWSA
algorithm are % F -tight. In addition, it is worthwhile mentioning that there
may be more than one % F -tight upper (or lower) bound for a 0*. An
experimental example of nonunique % F -tight bounds is given in Section 6.2.
With this definition, we proved the following important result concerning
the optimality of the BWSA algorithm.
THEOREM 6. The lower and upper bounds provided by BWSA are % F -
tight.
Basically, Theorem 6 suggests that the quality of the wiresizing solutions
obtained by the BWSA algorithm starting from the coarsest segment-
division is as good as those obtained by the GWSA algorithm using the
finest segment-division % F .
Complexity. Recall that our MSWS/E problem aims to find the optimal
wiresizing solution for every wire that is minLength long. In order to
achieve the required accuracy, the finest segment-division % F where each
unisegment is minLength long must be used by GWSA, whereas BWSA can
determine a proper, usually coarser, segment-division during the wiresizing
procedure. If we use minLength as the wire length unit, the total wire
length n is a natural metric to measure the problem size. We proved the
following Theorem 7.
THEOREM 7. Given an MSIT and r wire width choices, if the total wire
length is n when regarding minLength as the length unit, both GWSA and
BWSA have the worst-case complexity of O(n 3 z r) for the MSWS/E problem

It is worthwhile emphasizing that the final unisegment produced by
BWSA is often much longer than minLength and BWSA runs much faster
than GWSA in the practice, which is supported by extensive experiments in
Section 6.2 and Cong and He [1995b]. In fact, because BWSA runs much
faster than GWSA and obtains the same tight lower and upper bounds as
those obtained by GWSA, we always use BWSA instead of GWSA. Further-
more, due to the fact that the BWSA computes both lower and upper
bounds of the optimal wiresizing solution based on the bundled refinement
property, we can tell easily when the optimal wire widths are achieved for
those unisegments where their lower and upper bounds meet, so that we do
not have to further refine the segment-division for them. Similar segment-
division refinement schemes may not be used optimally in other wiresizing
494 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
methods 6 until there is an easy way to determine that the current wiresizing
solution is the optimal wiresizing solution or part of it belongs to the
optimal wiresizing solution.
5.2 Optimal Wiresizing Algorithm Using Bundled Refinement
Given an MSIT, BWSA can be used to compute the % F -tight lower/upper
bounds of the optimal wiresizing solution. If the lower and upper bounds
meet, which is very likely in practice, we get the optimal wiresizing
solution immediately. Otherwise, the optimal solution shall be found between
the lower and upper bounds. Because of the LST separability and the
LST monotone property, OWSA, originally developed for the SSWS problem
in Cong and Leung [1993, 1995], can be used independently for every LST
with respect to the given wire width assignments for the SST. However,
since the separability in SST does not hold in general, the optimal wire
width assignments for nonconvergent unisegments in the SST will be found
by enumeration between the % F -tight lower and upper bounds and subject
to the local monotone property. Thus, the optimal wiresizing algorithm
using bundled refinement (OWBR algorithm) has been developed, which
works like the following.
(1) Compute the % F -tight lower and upper bounds by BWSA;
(2) Enumerate the wire width assignments for the SST between the
lower and upper bounds and subject to the local monotone
(3) Apply OWSA independently to each LST during the enumeration of
wire width assignments for the SST and subject to the % F -tight lower
and upper bounds.
Our experiments show that BWSA gives the convergent bounds on all
unisegments in an MSIT for almost all cases. For those cases that have
nonconvergent unisegments, the percentage of nonconvergent unisegments
is very small. Moreover, the gap between the lower and upper bounds on
each nonconvergent unisegment is also very small (usually being one in our
experiments). Therefore, OWBR runs very fast in practice. Note that the
OWBR algorithm can be extended to the multilayer case the same as the
extension of the OWSA algorithm in Cong and Leung [1995]. Experimental
results with multilayer MSIT designs are presented in Section 6.
6. EXPERIMENTAL RESULTS
We have implemented the OWBR algorithm in ANSI C for the Sun SPARC
station environment and tested our algorithm on multisource nets extracted
from the multilayer layout of an Intel high-performance micropro-
cessor. In this section, we present the comparison of different wiresizing
solutions, the comparison between the BWSA algorithm and the GWSA
6 Sapatnekar [1994], Menezes et al. [1994, 1995], Xue and Kuh [1995], Xue et al. [1996], Lillis
et al. [1995].
Optimal Wiresizing for Interconnects . 495
algorithm, and the fidelity study of the Elmore delay model versus the
SPICE-computed delay to justify our formulation based on the Elmore
delay model.
The parameters used in our experiments are summarized in Table I.
These parameters are based on the 0.5 mm CMOS technology of the North
Carolina Microelectronic Center (MCNC) designers manual. Since only
parameters about the first and the second metal layers (M1 and M2) are
available, we only use layers M1 and M2 in our experiments. The wire
width choices in each layer are {W, 2W, 3W, 4W, 5W} with W being the
minimum allowable wire width in the layer. Note that our algorithms are
still valid if wire widths are not multiples of the minimum width. The
minimum unisegment length minLength is set to be 10 mm. We assume
that the driver is an inverter, its p-type transistor is 105.9mm-wide and
n-type 53.5mm-wide. Its effective resistance is 156V based on SPICE
simulation. We model the driver as a resistor of this value during the
wiresizing procedure. In addition, the loading capacitance in every loading
is set to be 3.720 fF. Note that both our formulation and implementation
can handle cases where different sources have different driver resistances
and different sinks have different loading capacitances.
6.1 Comparison Among Different Wiresizing Solutions
We report SPICE-computed delays instead of calculated Elmore delay
values in the comparison among different wiresizing solutions. For the
SPICE simulation in this paper (the driver is modeled by the SPICE
Level-3 MOSFET model given in MCNC designers manual), and every wire
of minLength long (10mm) by an RC circuit. The use of SPICE simulation
results not only shows the quality of our MSWS solutions, but also verifies
the validity of our interconnect modeling and the correctness of our MSWS
problem formulation.
The test suite used for our algorithms comprises real multisource nets
provided by Intel [Chan 1995]. These nets were extracted from the top-level
floor-plan of a high-performance microprocessor. Most pins of these nets
can serve as both sources and sinks at different times, and almost all pairs
between sources and sinks (excluding feed-through pins) are timing criti-
cal. We use the 1-Steiner tree algorithm [Kahng and Robins 1992] to route
these nets. Table II summarizes the routing trees for these nets.
We applied our OWBR algorithm to these MSITs. First, we assume all
wires in M2; then, we assume all wires parallel to the X-axis in M1, the

Table

I. Parameters Based on MCNC 0.5 mm Submicron CMOS Technology
496 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
rest in M2. Let min_width be the wiresizing solution with minimum wire
width W everywhere, and opt_msws the multisource wiresizing solution
given by our OWBR algorithm. Also, let wire length denote the total wire
length of a routing tree, and normalized area denote the area ratio of the
wiresizing solution versus the min_width wiresizing solution, which is
equivalent to the average wire width if the minimum wire width W is
scaled to 1. Both average delay and maximum delay are only measured on
critical source-sink pairs. In these experiments, we assign l ij 5 1 for a
critical source-sink pair and l ij 5 0 otherwise. Thus, the objective in
Equation (7) is equivalent to the average delay among critical source-sink
pairs. Comparisons among different wiresizing solutions are shown in

Table

III. In terms of the average delay, the objective of our MSWS
formulation, the opt_msws solutions consistently outperform the min_
width solutions. The delay reduction is up to 23.5% and 12.6% for the
single-layer and multilayer cases, respectively. It is interesting to observe
that although the average delay is our objective, experimental results show
that this formulation reduces the maximal delay substantially (only in one
example, opt_msws loses 0.69% in terms of the maximum delay, but still
wins in terms of the average delay). The maximum delay reduction is up to
36.3% and 37.8% for the single-layer and multi-layer cases, respectively. In
addition, the delay reduction for nets with larger spans is observed to be
more significant. It often happens in our experiments that the optimal
wiresizing solution for nets with fewer pins and shorter total wire lengths
is simply the minimum wire width solution. In general, the optimal
wiresizing is more effective for global nets with more pins and longer total
wire lengths.
6.2 Speedup Using Variable Segment-Division
We applied both BWSA and GWSA algorithms to the test suite of Intel
nets. Because the time for BWSA to compute the % F -tight lower and upper
bounds for most nets in the test suite is too small to measure, we compared
the total running time. In Table IV, the BWSA-based algorithm is just
OWBR, that is, BWSA to compute % F -tight lower and upper bounds,
followed by enumerating for the SST and OWSA for LSTs. The GWSA-
based algorithm is just to replace BWSA by GWSA in the OWBR scheme.
The BWSA-based algorithm is observed to run more than 1003 faster than
the GWSA-based algorithm.

Table

II. Routing Trees for Extracted Multisource Nets
Optimal Wiresizing for Interconnects . 497
It is worthwhile mentioning that BWSA gives identical % F -tight lower
and upper bounds for net3 whereas GWSA does not, which is also an
example of existence of multiple % F -tight bounds for the optimal solution as
mentioned in Section 5.1. Also note that, in the case of OWBR, the total
running time is not dominated by the time to compute % F -tight lower and
upper bounds: one reason is that the current implementation builds the
data structure for the finest segment-division even if the bundled refinement
does not need it at all. Thus, the total running time still can be
further reduced in future implementation without building the data structure
for the finest segment-division. 7
6.3 Fidelity of the Elmore Delay Model
The concept of fidelity for the Elmore delay model was introduced by Boese
et al. [1993] for the routing tree topology optimization to measure if an
optimal or near-optimal solution selected according to the Elmore delay
model is nearly optimal according to the actual delay (e.g., computed using
SPICE). We investigate the fidelity of the Elmore delay model for the
7 It has been done in Cong and He [1995c, 1996].

Table

IV. Total Running Time Comparison

Table

III. Multisource Wiresizing Result Comparison
498 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
optimal wiresizing problem, that is, to find out how good the solution given
by our optimal wiresizing formulation based on the Elmore delay model is
in terms of the real delay.
We measure the fidelity again on the test suite of Intel nets and assume
all wires in the M2 layer. Since the number of total wiresizing solutions is
prohibitively large to enumerate, we randomly generate 1,000 wiresizing
solutions for every MSIT. In a solution, a random wire width is assigned for
every wire minLength long (10 mm). We obtain both the weighted average
Elmore delay and the weighted average 50% delay computed by SPICE for
each solution and then rank the 1,000 solutions for each MSIT, using the
technique similar to Boese et al. [1993]: first rank solutions according to
their weighted Elmore delays; then rank them according to their weighted
SPICE-computed delay. The absolute difference between the two rankings
of a wiresizing solution is its ranking difference and we average ranking
differences over 1,000 solutions for every MSIT. In order to know how large
the SPICE-computed delay difference may be with respect to the average
ranking difference, delay difference is computed in the following way: let
the average ranking difference be d. For a wiresizing solution whose
SPICE-computed delay ranking is i, we compute the relative difference
between the (i 1 d)th and ith SPICE-computed delays, as well as that
between the (i 2 d)th and ith SPICE-computed delays. Between the two
values, the one with the larger absolute value is defined as the delay
difference for the average ranking difference d. We average delay differences
over 1,000 solutions for every MSIT.
The average ranking differences and the associated average delay differences
are given in Table V. Let us take net1 as an example to show how
good the optimal solution selected according to the Elmore delay model
might be. The average rank difference for 1,000 wiresizing solutions is
23.61. Thus, the optimal solution selected according to the Elmore delay, on
average, might be -23.61- away from the top one in the ranking according
to SPICE-computed delays. Since the ranking difference of -23.61- accounts
for only 0.1448% SPICE-computed delay difference, on average, the optimal
solution selected according to Elmore delay is only 0.1448% worse than the

Table

V. Average Differences in Ranking and SPICE-Computed Delay Based on 0.5 mm
CMOS Technology
Optimal Wiresizing for Interconnects . 499
optimal one selected according to the SPICE-computed delays, when delays
of both solutions are measured by SPICE simulation. 8
Over the 1,000 random solutions for each net, the average ranking
differences are between 23.61 and 170.7, and average delay differences
between 0.1648% and 0.8517%. In addition, we measure the average delay
difference for the best-100 and best-10 wiresizing solutions according to the
Elmore delay model for each random solution set, respectively. It is
interesting to find that the better the wiresizing solutions according to the
Elmore delay model, the less the average delay difference they have.
Taking net1 as an example, the average delay difference is 0.1048% for the
1,000 solutions, but only 0.0150% for the best-100, and even less, 0.0017%
for the best-10. It implies that, in general, in the area near the optimum in
the solution space, the Elmore delay model has an even higher fidelity.
Based on data of the best-10 in every random solution set, the optimal
wiresizing solution selected according to the Elmore delay model is less
than 0.06% worse than the optimal solution selected according to the
SPICE-computed delay. 9 Thus, we believe that the Elmore delay model has
really high fidelity for wiresizing optimization; that is, the optimal solution
selected according to the Elmore delay model is also the optimal solution or
nearly the optimal solution selected according to the SPICE-computed
delay. Note that the inductance is not taken into consideration in our
SPICE simulation, since the inductive effect is negligible under the current
CMOS technology. The higher-order delay model used in Menezes et al.
[1994, 1995] does not consider the inductance, either.
7. CONCLUSIONS AND FUTURE WORK
The results in this paper have shown convincingly that proper sizing of the
wire segments in multisource nets can lead to significant reduction in the
interconnect delay. We have also developed an efficient wiresizing algorithm
named the BWSA algorithm. It achieves the same wiresizing solution
as the GWSA algorithm [Cong and Leung 1993, 1995], but runs 1003 time
faster and uses much less memory space. Thus, the BWSA algorithm shall
be used instead of the GWSA algorithm, not only for the multisource
wiresizing problem, but also for the single-source wiresizing problem [Cong
and Leung 1993, 1995] and the simultaneous driver and wiresizing problem
[Cong and Koh 1994]. Compared to the minimum wire width solution, the
optimal wiresizing solution obtained by our algorithm reduces the average
delay by up to 23.5% and the maximum delay by up to 37.8%, respectively.
It takes several seconds to obtain the optimal wiresizing solution for the
8 Note that the Elmore delay value of the optimal solution selected according to the Elmore
delay model is often quite different from the SPICE-computed delay of the same solution, with
24% error for the optimal wiresizing solution for net1.
9 We also enumerate the wiresizing solutions for net1 and net2 by assuming that each segment
in the routing tree has a uniform wire width. Even higher fidelity is observed when compared
with this set of random wiresizing experiments. For these two nets, the Elmore delay model
gives the best-5 solutions the same as those given by the SPICE-computed delay.
500 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
largest example in our test suite extracted from a high-performance Intel
microprocessor.
Extensions have been made in Cong and He [1995c, 1996]. By revealing
the dominance property for a class of optimization problems named CH-
posynomial programs, the BWSA algorithm has been generalized to approach
the simultaneous transistor and interconnect sizing (STIS) problem.
The simultaneous driver and wiresizing problem (or the simultaneous
buffer and wiresizing problem) can be solved as a simple case of the STIS
problem. Different from the simultaneous driver and wiresizing formulation
[Cong and Koh 1994] applicable only to the single-source nets, it has
been used to further reduce the delay for multisource nets by sizing drivers
and wires simultaneously. Furthermore, the STIS formulation uses a
transistor delay model with consideration of the waveform slope effect. It is
more accurate than the fixed-value resistor model used in this paper and in
Cong and Leung [1993, 1995], Cong and Koh [1994], Sapatnekar [1994],
and Chen et al. [1996a, b]. Moreover, the STIS formulation can combine
delay and area (or power) minimizations and a smooth delay and area
tradeoff has been yielded. However, our MSWS formulation does not
consider the coupling between wires, which becomes important when the
technology moves into the deep submicron. We plan to develop an efficient
wiresizing algorithm to take account of the coupling effect.
Another wiresizing optimization objective is to minimize the maximum
delay in interconnects under the Elmore delay model. If we assume the
single-source net and the fixed-value resistor model for the driver, approaches
in Sancheti and Sapatnekar [1994], Menezes et al. [1995], and
Chen et al. [1996a] are able to achieve the optimal continuous wiresizing
solution, and the approach in Lillis et al. [1995] is able to achieve the
optimal discrete wiresizing solution. It is worthwhile mentioning that the
approach in Chen et al. [1996a] is based on a Lagrangian relaxation
procedure to iteratively apply the weighted delay minimizations (same as
that in Cong and Leung [1993, 1995] and similar to our formulation). It
adjusts the weight assignments after each iteration until the optimal
weight assignments are achieved to minimize the maximum delay by using
the weighted delay minimization. In order to minimize the maximum delay
for multisource nets, the optimal continuous solution might be achieved by
extensions of approaches in Sancheti and Sapatnekar [1994], Menezes et
al. [1994a], and Chen et al. [1996a]. However, the optimal algorithm for
obtaining the discrete solution is still open. We have shown experimentally
that our weighted delay formulation could reduce the maximum delay very
well. More work is planned to find out whether an optimal algorithm exists.
The topologies of MSITs may affect the delay reductions that can be
achieved by the optimal wiresizing even though our OWBR algorithm is
able to achieve the optimal wiresizing solution for any MSIT topology. For
single-source nets, simultaneous tree construction and wiresizing has been
explored very recently in Lillis et al. [1996] and Okamoto and Cong [1996].
However, the question of how to combine the routing tree construction and
Optimal Wiresizing for Interconnects . 501
wiresizing to achieve the largest delay reduction for multisource nets is
still open. We plan to study the problem in the future.




Since the proofs for the LST separability (Theorem 1), the LST monotone
property (Theorem 2), the dominance property (Theorem 4), and Theorem 7
concerning the complexities of GWSA and BWSA algorithms are similar to
those in Cong and Leung [1995], the full proofs of these theorems are given
in Cong and He [1995b]. In this appendix, we first discuss the properties
for the coefficient functions and then prove the SST local monotone
property (Theorem 3), the bundled refinement property (Theorem 5), and
Theorem 6 concerning the optimality of the BWSA algorithm.
Properties of Coefficient Functions
Careful study of the definitions of f ij Equations (4)-(6), as
well as F, G, and H in Equations (10)-(12) reveals Lemma 1 (presented in
Section and the following Lemmas 2 and 3 for the coefficient functions F,
G, and H.
LEMMA 2. Given an MSIT and a segment S in the MSIT, for any
unisegments E and E9, if E is in segment S, and E9 in segment S9 (- S),
F(E, E9) is an invariant (denoted F(S, S9)).
LEMMA 3. Given an MSIT and a segment S in the MSIT, for any
unisegment E within segment S, G(E) and H(E) are invariants (denoted
G(S) and H(S), respectively).
Although the coefficient functions F, G, and H are defined for uniseg-
ments in Equations (10)-(12), Lemmas 1-3 enable us to compute these
functions based on segments rather than unisegments. Because the number
of segments in an MSIT may be much smaller than the number of
unisegments in the MSIT, we can compute these coefficient functions for
much reduced costs. These coefficient functions are computed before the
wiresizing procedure and viewed as constants during the wiresizing procedure.
Proof of Theorem 3
We prove Theorem 3 (the SST local monotone property) based on a series of
lemmas. For simplicity, we assume the finest segment-division in this
proof. Recall that a unisegment under any valid segment-division corresponds
to single or multiple unisegments in the finest segment-division; it
is easy to verify that the local monotone property holds for any valid
segment-division if and only if it holds for the finest segment-division.
LEMMA 4. Given an MSIT and a segment S in the MSIT, if E l and E r are
two adjacent unisegments within segment S and E l is just left of E r , then
502 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
PROOF. There are two cases for Lemma 4.
Case 1. E is in segment S. According to Lemma 1,
if E is right of E l (as well as E r ), F(E l , E) 5 F(E r , E) 5 F l (S) and F(E,
if E is left of E l (as well as E r ), F(E l , E) 5 F(E r , E) 5 F r (S) and F(E,
Case 2. E is in segment S9 (- S). According to Lemma 2,
l , E) 5 F(E r , E) 5 F(S, S9) and F(E, E l ) 5
LEMMA 5. Given an MSIT and a segment S in the MSIT, let E l and E r be
unisegments in a segment S with E l just left of E r . Concerning the optimal
wiresizing solution, if F l (S) . F r (S), then E l cannot be narrower than
F l (S) , F r (S), then E l cannot be wider than E r .
be the wiresizing solution
defined on M by 0. The objective function (7) can be written as:
t~MSIT, %, 0!
F~E l , E9! z
Let 0* be the optimal wiresizing solution. After swapping the width
assignments for E l and E r with respect to 0* (see Figure 5), we denote the
resulting wiresizing solution 0*/E l ,
Optimal Wiresizing for Interconnects . 503
According to Lemmas 3 and 4,
thus,
t~MSIT, %, 0*/E l ,
w* E1
z w* E l
J .
We know that (_ 2 z(w*
Equation (18)
since 0* is the optimal solution. Clearly, if F l (S) . F r (S), according to
. Similarly, if
F l (S) , F r (S), then F(E l ,
. As a
result, Lemma 5 holds. e
By applying Lemma 5 to any adjacent unisegments in a segment, we
obtain Lemma 6.
LEMMA 6. Given an MSIT and a segment S in the MSIT, concerning the
optimal wiresizing solution, if F l (S) . F r (S), then the wire widths within
Fig. 5. (a) Width assignments for E l and E r in optimal solution 0*; (b) wiresizing solution
obtained by swapping width assignments for E l and E r .
504 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
segment S decrease monotonically rightward. Similarly, they increase
monotonically rightward if F l (S) , F r (S).
LEMMA 7. Given an MSIT and any segment S in the MSIT, if F l (S) 5
F r (S), there exists an optimal wiresizing such that all unisegments in
segment S have the same wire width.
PROOF. Assume that Lemma 7 fails for an MSIT, then for any optimal
solution 0*, there must exist two unisegments in a segment S of the MSIT
such that E l is just left of E r and w*
. Since 0* is optimal, the
increase in the objective function when we change the width of E r in 0*
from w* E r
to w* E (see Figure 6.b), by using Equation (13), is
Fig. 6. Width assignments for E l and E r in optimal solution 0*; (b) wiresizing solution
obtained by replacing width of E r with that of E l ; (c) wiresizing solution obtained by replacing
width of E l with that of E r .
Optimal Wiresizing for Interconnects . 505
Similarly, the increase in the objective function when we change the width
of E l in 0* from w* E to w* E r
(see

Figure

6c) is:
F~E l , E9! z
Recall Equations (14)-(17); it is not difficult to verify the following,
According to Equations (19)-(21), Dt1 5 Dt2 5 0. That is, both
are optimal.
Therefore, if there is an optimal solution 0* where the wire widths are
not uniform in a segment S, let w* l be the wire width of the leftmost
unisegment in S, from left to right, we can successively replace the wire
width for every unisegment in S by w* l , without increase in the objective
function. That is, the resulting wiresizing solution is an optimal wiresizing
solution such that the wire widths are uniform in segment S. e
In conclusion, we obtain the SST local monotone property (Theorem 3) by
combining Lemmas 6 and 7.
Proof of Theorem 5
In order to prove Theorem 5 (the bundled refinement property), we define
the following equations with respect to any particular unisegment E.
C~MSIT, %, E, 0!
F~E9, E0! z
506 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
F(MSIT, %, E,
Q~MSIT, %, E, 05 _ 2 z O
F~E, E9!
Then, we can rewrite the objective function (7) as follows.
. (25)
We show the following Lemma 8.
LEMMA 8. Given an MSIT, a segment-division %, and a wiresizing
solution 0, for any particular unisegment E under %, if we divide E into a
sequence of unisegments let each new unisegment
inherit the wire width assignment of E, and denote the resulting segment-
division and wiresizing solution %9 and 09, respectively, then the following
relations hold for any unisegment E9 other than E.
C~MSIT, %, E9, 0! 5 C~MSIT, %9, E9, 09!
F~MSIT, %, E9, 0! 5 F~MSIT, %9, E9, 09!
Q~MSIT, %, E9, 0! 5 Q~MSIT, %9, E9,
PROOF. It is not difficult to verify that Lemma 8 is true if the following
hold:
In general, under the modeling method used in Cong and Leung [1995], Cong and Koh
[1994], Cong and He [1995a], and Sapatnekar [1994], for the Elmore delay t ij between source
That is, the Elmore delay is independent of
the segment-division when given the wiresizing solution.
Optimal Wiresizing for Interconnects . 507
Assume unisegment E is in segment S. There are two cases for unisegment
E9.
Case 1. E9 is also in the same segment S. According to Lemma 1, if E is
left of E9.
if E is right of E9,
Case 2. E9 is in segment S9 different from segment S. According to
Lemma 2,
Again assuming unisegment E is in segment S, according to Lemma 3,
As a result, Lemma 8 holds. e
Recall the definition for the local refinement operation; according to
Lemma 8 and Equation (25), we can conclude that the following Lemma 9
holds.
LEMMA 9. When given the wiresizing solution 0 and any particular
unisegment E, the local refinement result for E with respect to 0 is
independent of the segment-division for unisegments other than E.
We give the following proof for Theorem 5 (the bundled refinement prop-
erty).
PROOF. For any particular unisegment E under the current segment-
division % in segment S of an MSIT, it may be divided into k unisegments
508 . J. Cong and L. He
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 4, October 1996.
under the finest segment-division % F . From left to right, let them be E l 5
Without loss of generality, we assume F l (S) (S). For a wiresizing
solution 0 that dominates the optimal solution 0*, let 0 b be the wiresizing
solution after performing an BRU operation of 0 on E under %. Then,
we have w l
b according to the definition of the
BRU operation. Meanwhile, in the optimal wiresizing solution 0*, we have
r according to the local monotone property.
According to Lemma 9, w l
b is also the local refinement result for uniseg-
ment E l under the finest segment-division % F . Therefore, w l
l . As a
result, w l
Recall that the bundled refinement of unisegment E does not change the
wire width in the wiresizing solution 0 (dominating 0*) for any uniseg-
ment E9 other than E l , dominates 0*.
The BRL case can be proved in a similar way. e
Proof of Theorem 6
THEOREM 6. The lower and upper bounds provided by BWSA are % F -
tight.
PROOF. Let % be the wiresizing segment-division after BWSA. For any
unisegment E under %, l E is longer than minLength (the length for all
unisegments under the finest segment-division % F ) if and only if E is a
convergent unisegment, whose bounds can not be tightened any more.
If E is minLength long, according to Lemma 9, its lower and upper
bounds given by the bundled refinement operations are the same as those
given by local refinement operations under % F . Thus, if the bundled
refinement operations cannot tighten the lower and upper bounds, neither
can the local refinement operations under % F .
In conclusion, Theorem 6 holds. e

ACKNOWLEDGMENTS

The authors thank Heming Chan at Intel Design Technology Department
for providing the multiple source routing examples, and Cheng-Kok Koh
and Patrick Madden at UCLA for their helpful discussions.



--R

A direct combination of the Prim and Dijkstra constructions for improved performance-driven routing

Private communication.
Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation
Optimal Wiresizing for Interconnects
Optimal wiresizing for interconnects with multiple sources.
Optimal wiresizing for interconnects with multiple sources.
UCLA Computer Science
Simultaneous transistor and interconnect sizing based on the general dominance property.
An efficient approach to simultaneous transistor and interconnect sizing.
Simultaneous driver and wire sizing for performance and power optimization.
Optimal wiresizing under the distributed Elmore delay model.
Optimal wiresizing under the distributed Elmore delay model.

Provably good performance-driven global routing

The transient response of damped linear network with particular regard to wideband amplifier.
TILOS: A posynomial programming approach to transistor sizing.
Buffer placement in distributed RC-tree networks for minimal Elmore delay


A new class of iterative Steiner tree heuristics with good performance.
Optimal wire sizing and buffer insertion for low power and a generalized delay model.
New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing.

MANUAL. North Carolina Microelectronic Center.


RC interconnect synthesis-a moment fitting approach
Buffered Steiner tree construction with wire sizing for interconnect layout optimization.
Signal delay in RC tree networks.
IEEE Trans.
Interconnect design using convex optimization.

RC interconnect optimization under the Elmore delay model.
Post routing performance optimization via multi-link insertion and non-uniform wiresizing
A sensitivity-based wiresizing approach to interconnect optimization of lossy transmission line topologies
revised May
Optimal Wiresizing for Interconnects
--TR
High-performance routing trees with identified critical sinks
Performance-driven interconnect design based on distributed RC delay model
Simultaneous driver and wire sizing for performance and power optimization
RC interconnect optimization under the Elmore delay model
Simultaneous gate and interconnect sizing for circuit-level delay optimization

--CTR
John Lillis , Chung-Kuan Cheng, Timing optimization for multi-source nets: characterization and optimal repeater insertion, Proceedings of the 34th annual conference on Design automation, p.214-219, June 09-13, 1997, Anaheim, California, United States
Lieven Vandenberghe , Stephen Boyd , Abbas El Gamal, Optimal wire and transistor sizing for circuits with non-tree topology, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.252-259, November 09-13, 1997, San Jose, California, United States
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
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
Youxin Gao , D. F. Wong, Optimal shape function for a bi-directional wire under Elmore delay model, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.622-627, November 09-13, 1997, San Jose, California, United States
Chung-Ping Chen , Hai Zhou , D. F. Wong, Optimal non-uniform wire-sizing under the Elmore delay model, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.38-43, November 10-14, 1996, San Jose, California, United States
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
Chin-Chih Chang , Jason Cong, An efficient approach to multi-layer layer assignment with application to via minimization, Proceedings of the 34th annual conference on Design automation, p.600-603, June 09-13, 1997, Anaheim, California, United States
Yehea I. Ismail , Eby G. Friedman , Jose L. Neves, Equivalent Elmore delay for
RLC
performance driven layout;optimal wiresizing;VLSI routing;interconnect optimization