Bounded-skew clock and Steiner routing under Elmore delay.
We study the minimum-cost bounded-skew routing tree problem under the Elmore delay model. We present two approaches to construct bounded-skew routing trees: (i) the Boundary Merging and Embedding (BME) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the Interior Merging and Embedding (IME) algorithm which employs a sampling strategy and dynamic programming to consider merging points that are interior to, rather than on the boundary of, the merging regions. Our new algorithms allow accurate control of Elmore delay skew, and show the utility of merging points inside merging regions.
Introduction
In layout synthesis of high-performance systems, it has become increasingly important to control signal delays, e.g., for clock
skew minimization or the timing-driven routing of large global nets. At the same time, routing solutions should have low wiring
area to reduce die size and capacitive effects on both performance and power dissipation. Thus, the "zero-skew" clock tree and
performance-driven routing literatures have seen rapid growth over the past several years; see [22] for a detailed review. Recent
works have accomplished exact zero skew under the Elmore delay model [30, 6, 15], and have given new methods for single-layer
(planar) clock routing [32, 23, 24]. Over the past two years, a number of authors have applied wiresizing optimizations
and/or buffer optimizations to minimize phase delay [18, 28, 16, 26, 27, 33, 34], skew sensitivity to process variation [28, 8, 25],
and/or power dissipation [28]. The work of [29] developed a clock router that accomplishes specified pin-to-pin delays.
"Exact zero skew" is typically obtained at the expense of increased wiring area and higher power dissipation. In practice,
circuits still operate correctly within a given skew tolerance, and indeed exact zero skew is never an actual design requirement
[22]. The works of Zhu and Dai [33, 34] and Pullela et al. [27] are notable in that they use initial non-zero skew routing solutions
which are then wiresized to satisfy a given skew bound. Construction of a minimum-cost bounded-skew routing tree (BST)
is a key underlying optimization. 1 Given these antecedents, two recent works [10, 19] have addressed the BST problem, and
proposed clock and Steiner global routing algorithms that construct BSTs under the linear, i.e., pathlength, delay model. The
enabling concept in [10, 19] is that of a merging region, which generalizes the merging segment concept of [2, 5, 13] for zero-
skew clock trees.
Unfortunately, in practice we find that bounding the pathlength skew does not afford any reliable control of the actual delay
skew.

Figure

1(a) shows HSPICE delay skew against pathlength delay skew for routing trees generated by the ExG-DME algorithm
[19] on the r1-5 benchmark clock sink placements. Not only is the correlation poor, In general, not only is the correlation
poor, but the pathlength-based BST solutions of [10, 19] are simply unable to meet tight skew bounds (of 100ps or less). On the
other hand, Figure 1(b) demonstrates the accuracy and fidelity of Elmore delay skew to actual skew; cf. [3]. While it is possible
to "convert", e.g., a zero pathlength skew routing into a zero Elmore delay skew routing, via the use of "snaking" to balance
wirelengths [30], such an approach will usually entail over 30% increase in total wirelength. With this in mind, we pursue new
approaches to the minimum-cost BST problem under Elmore delay. Our three main contributions are:
ffl First, we prove that the merging region under Elmore delay is bounded by well-behaved segments on which the skew values
are piecewise-linearly increasing, then constant, then piecewise-linearly decreasing. We also prove that the merging
region is a convex polygon with at most 4n sides, where n is the number of leaves in the tree topology; a given merging
region can be constructed in O(n) time. One minor caveat is that the "merging region" that we construct is not a complete
1 Vittal and Marek-Sadowska [31] showed that the minimum-cost BST problem also arises in power distribution topology design.
HSPICE Skew
(ps)
Pathlength Skew (-m)3
HSPICE Skew (ps)
Elmore Skew (ps)
HSPICE Skew
(ps)
Pathlength Skew (-m)33 3330200400600
HSPICE Skew (ps)
Elmore Skew (ps)
HSPICE Skew
(ps)
Pathlength Skew (-m)33330200400600
HSPICE Skew (ps)
Elmore Skew (ps)
HSPICE Skew
(ps)
Pathlength Skew (-m)333302004006000 100 200 300 400 500
HSPICE Skew (ps)
Elmore Skew (ps)
HSPICE Skew
(ps)
Pathlength Skew (-m)333301002003004005000 100 200 300 400 500
HSPICE Skew (ps)
Elmore Skew (ps)

Figure

1: Plots of (a) Pathlength skew versus actual (HSPICE simulation) delay skew for BST solutions obtained by the ExG-
DME algorithm [19], and (b) Elmore delay skew versus actual (HSPICE simulation) skew for BST solutions obtained by the
IME algorithm for the r1-5 benchmark clock sink placements.
generalization of the DME merging segment: when detour wiring is needed or when merging regions of subtree roots
overlap, our construction may not return a region containing all the minimum-cost merging points.
ffl Second, we develop a tradeoff approach which minimizes total wirelength for any given skew bound under Elmore delay.
We call this the Boundary Merging and Embedding (BME) method, since it merges boundary points of merging regions in
the same manner as in [10, 19]. Using our new construction of the merging region under Elmore delay, the BME method
can extend Extended-DME (Ex-DME, for fixed topology) and Extended-GreedyDME (ExG-DME, for variable topology)
[19] from bounded pathlength skew to bounded Elmore delay skew.
ffl Third, we note that the BME strategy, as well as those in previous works, will utilize merging points that are restricted
to the boundaries of merging regions. This restriction prevents the skew bound from being fully exploited in the tree
cost minimization. We thus develop an improved Interior Merging and Embedding (IME) algorithm which employs a
sampling strategy and dynamic programming to consider merging points that are interior to, rather than on the boundary
of, the merging regions.
The rest of this paper is organized as follows. In Section 2, we give several basic definitions and formulate the bounded-
skew routing tree problem. We also review previous DME-based methods for zero-skew routing and bounded-skew routing.
In Section 3, we develop our results on the merging region construction under Elmore delay; this construction can be used by
BME to replace the merging region construction under pathlength delay. In Section 4, we present our IME algorithm, which
uses sampling within the set of feasible merging points based on a dynamic programming approach. Section 5 summarizes
experimental results and Section 6 concludes with directions for future work.
Preliminaries
Assume that we are given a set clock sink locations in the Manhattan plane. A clock source location
may also be given. A routing topology G is a rooted binary tree with n leaves corresponding to the sinks in S. A clock tree
G (S) is an embedding of routing topology G, i.e. each internal node v 2 G is mapped to a location l(v) in the Manhattan plane.
are understood, we may simply use T(S) or T to denote the clock tree.) In the rooted topology, each node v is
connected to its parent by edge e v , and the cost of edge e v is its wirelength, denoted by je v j. The cost of a routing tree T is
the sum of its edge costs. If t(u; v) denotes the signal delay between nodes u and v, then the skew of clock tree T is given by
recent works [10, 19] were the first to address the following problem:
Minimum-Cost Bounded Skew Routing Tree (BST) Problem: Given a set sink locations and a skew
bound B, find a routing topology G and a minimum-cost clock tree T G (S) that satisfies skew(T G (S)) - B.
We will consider both this formulation and the BST variant where a fixed topology G has been specified. We do not include
clock source location s 0 in our formulation since our methods can transparently accommodate any prescribed s 0 .
In [10, 19], the BST problem was solved under the pathlength delay model, i.e., t(s the sum of edgelengths in the
path. Given the poor correlation between pathlength delay/skew and actual delay/skew (recall Figure 1), our work
addresses the BST problem under Elmore delay, which is defined as follows. For any edge e v , let r v and c v respectively denote
its lumped resistance and capacitance. For any node v in G, we use T v to denote the subtree of T that is rooted at v, and we use
C v to denote the total capacitance of T v . For any nodes u; v 2 G with u an ancestor of v, let Path(u;v) denote the unique path
from u to v in G. Then, under the Elmore model the signal delay t(u; v) is given by t(u;
2.1 The DME Approach
The Deferred-Merge Embedding (DME) algorithm, proposed independently in [13, 5, 2], achieves exact zero skew given any
delay model for which sink delays are monotone in the length of each edge of the clock tree (e.g., pathlength delay and Elmore
delay). For pathlength delay, DME returns the optimal solution, i.e., a tree with minimum cost and minimum source-sink
pathlength for any input sink set S and topology G.
Since the methods of [10, 19] as well as those we propose below are generalizations of DME, we now review the original
DME method and the Greedy-DME variant of Edahiro [14], following notation of [2, 6]. We use d(s; t) to denote the Manhattan
distance between points s and t; the distance between two pointsets P and Q is Qg.
I. The DME Algorithm. Given a set of sinks S and a topology G, DME embeds internal nodes of G via: (i) a bottom-up
phase that constructs a tree of merging segments which represent loci of possible placements of internal nodes in a zero-skew
tree (ZST) T ; and (ii) a top-down embedding phase that determines exact locations for the internal nodes in T .
In the bottom-up phase, each node v 2 G is associated with a merging segment, denoted ms(v), which represents a set
of possible placements of v in a minimum-cost ZST. The segment ms(v) will always be a Manhattan arc, i.e., a segment with
possibly zero length that has slope +1 or \Gamma1. Let a and b be the children of node v, and let TS a and TS b denote the subtrees of
merging segments rooted at a and b. The construction of ms(v) depends on ms(a) and ms(b), hence the bottom-up processing
order. We seek placements of v which allow TS a and TS b to be merged with minimum added wire je a preserving
zero skew in T v . Given the tree of merging segments, the top-down phase embeds each internal node v of G as follows: (i) if v
is the root node, then DME selects any point in ms(v) to be l(v); or (ii) if v is an internal node other than the root, DME chooses
l(v) to be any point on ms(v) that is at distance je v j or less from the embedding location of v's parent.
II. The Greedy-DME Algorithm. Note that DME requires an input topology. Several works [2, 5, 14] have thus studied
topology constructions that lead to low-cost routing solutions when DME is applied; the most successful is the "Greedy-DME"
method of Edahiro [14], which determines the topology of the merging tree in a greedy bottom-up fashion. Let K denote a set of
merging segments which initially consists of all the sink locations, i.e., iteratively finds the pair of
nearest neighbors in K, that is, ms(u) and ms(v) such that d(ms(u);ms(v)) is minimum. A new parent merging segment ms(v)
is computed for node v from a zero-skew merge of ms(u) and ms(v); K is updated by adding ms(v) and deleting both ms(u) and
ms(v). After consists of the merging segment for the root of the topology.
In [15], O(nlogn) time complexity was achieved by finding several nearest-neighbor pairs at once, i.e., the algorithm first
constructs a "nearest-neighbor graph" which maintains the nearest neighbor of each merging segment in K. Via zero-skew
merges, jKj=k nearest-neighbor pairs are taken from the graph in non-decreasing order of distance, where k is a constant typically
between 4. The solution is improved by a post-processing local search that adjusts the resulting topology (cf. "CL
I6" in [15]). Greedy-DME achieves 20% reduction in wiring cost compared with the methods of [5].
2.2 Previous DME-Based BST Heuristics
In generalizing the DME construction to bounded-skew routing, the enabling concept is that of the merging region. Intuitively,
for node v 2 G with children a and b, the merging region of v corresponds to the set of all locations l(v) at which subtrees T a
and T b can be joined with minimum wiring cost while still maintaining the skew bound B. In the remainder of this section, we
briefly outline some concepts behind the Ex-DME and ExG-DME constructions [10, 19]. We defer most of the ideas to Section
3, which in some sense re-develops and generalizes a number of these ideas within the Elmore delay context.
The works of [10, 19] showed that under the linear delay model, the merging region for any node is a convex polygonbounded
by Manhattan arcs (i.e., segments with slope +1 or \Gamma1) and rectilinear segments (i.e., horizontal or vertical segments). Thus,
under pathlength delay the merging region has at most eight sides; furthermore, it can be computed in constant time. For the
case where a fixed topologyG has been prescribed, the Extended-DME (Ex-DME) method essentially parallels the original DME
construction and is optimal for the limitingcases of zero skew and infinite skew (i.e., the Steiner minimal tree problem with fixed
topology G).
When the topology is variable, [10, 19] propose an Extended-Greedy-DME (ExG-DME) method which again uses the merging
region construction, and generates a topology via iterated clustering operations analogous to those of Greedy-DME. The
ExG-DME method not only provides a smooth skew-cost tradeoff but also closely matches the best known heuristics for zero-
skew routing [15]. Notice that in maintaining zero skew, the original DME approach always merges two subtrees at their roots.
However, when the skew bound is non-zero, the shortest connection between two subtrees is not necessarily at their roots - and
there is no reason that subtrees cannot be merged at non-root nodes as long as the resulting skew is - B. The ExG-DME version
of [19] exploits the flexibility stemming from allowed non-zero skew B by dynamically re-rooting subtrees as they are merged
so that the roots of subtrees (after re-rooting) become closer without much change in the subtree costs.
(a)
r
r
r
r'
(b)

Figure

2: (a) An example showing that given skew bound B AE 0, changing the subtree topology before merging will reduce the
merging cost. (b) Repositioning the root in changing the topology.
In Figure 2a, eight sinks are equally spaced on a horizontal line. When B is near zero, the minimum tree cost can be obtained
by merging subtrees T 1 and T 2 at their roots as shown in the top example. However, this topology is highly suboptimal when
B is large, even if the costs of the two subtrees are minimum. Ideally, for large B the subtree topologies should be modified
so that the subtree roots are closer (and merging cost is reduced), as in the bottom example. The ExG-DME method of [19]
adjusts a subtree topology by changing the position of the root as illustrated in Figure 2b; the root can be repositioned as the
parent of nodes u and v, where u and v are the endpoints of any edge in the current tree. In practice, both the subtree cost and
most of the topology remain intact. As a result, this version of ExG-DME also very closely matches the best known heuristics
for unbounded-skew routing [4, 21]. The work of [19] also gives an Extended-Planar-DME method which again matches the
best known heuristics [23] when the routing tree must be embeddable on a single layer. However, when evaluated according to
Elmore delay skew, the pleasing "skew-cost tradeoff" properties of Ex-DME and ExG-DME vanish.
3 The Boundary Merging and Embedding Method
We now present our Boundary Merging and Embedding (BME) method, which encompasses the straightforward generalizations
of Ex-DME and ExG-DME from pathlength to Elmore delay. The difference from [10, 19] lies in the computation of merging
regions, i.e., we may execute the previous Ex-DME or ExG-DME strategies to achieve an Elmore delay skew bound simply
by substituting the new merging region construction. We do not state a specific "BME algorithm template" since the merging
region construction can be used by all variants (fixed-topology, variable-topology, single-layer, etc.
3.1 Notation and Definitions
Let t max (p) and t min (p) denote the maximum and minimum delay values (max-delay and min-delay, for short) from point p to
all leaves in the subtree rooted at p. The skew of point p, denoted skew(p), is t (p). (If all points of a pointset
have identical max-delay and min-delay, we similarly use the terms t max (P), t min (P) and skew(P).) As p moves along any
line segment the values of t max (p) and t min (p), along with skew(p), respectively define the delay and skew functions over the
segment. If B is the given skew bound, then the slack of point p, denoted slack(p), is defined to be
non-negative slack(p)) is a feasible merging point. For any region P, the feasible merging region FMR(P)
consists of all feasible merging points in P. The minimum skew region MSR(P) is the set of points in P with minimum skew.
Well-Behaved Elmore Delay Property. Figure 3 illustrates that Elmore delay values over a horizontal line segment l connecting
sinks a and b enjoy a convenient property: for p 2 l, the delay functions t max (p) and t min (p) are each the sum of a
piecewise-linear function and a unique quadratic term K
2 . To see this, let
C a and C b be the loading capacitances at sinks a and b. Then we express the max-delay and min-delay from point p to sink
a b
x=d(p,a)
min
a min
(a a )
a
(a a
a 2
min
a
a 1(x) max
a
a
min
min

Figure

3: Properties of Elmore delays and skew over straight-line segment l connecting sinks a and b.
piecewise-
linear
concave
piecewise-
linear
convex
(a)
min
piecewise-
linear
concave
a b a b
a b

Figure

4: (a) Delay and (b) skew functions for a well-behaved line segment. Skew turning points are indicated by the hollow
circles on ab.
a as functions of this corresponds to functions t b
in the Figure, with coefficients
a . Similarly, we denote the max-delay and min-delay from point p to sink b as t b
in the Figure, with
(b). We then have t
are each the sum of a piecewise-linear function of x and the same quadratic term K \Delta x 2 , we have that skew(p)
over segment ab is a piecewise-linear function of x (with up to 3 linear regions). If sinks a and b are not located on the same
horizontal or vertical line segment, we can still prove similarly that this same delay/skew property exists over the boundary and
interior segments (with any slopes) of the smallest rectangle containing a and b.
We may formalize this delay/skew property as follows. Let functions f 1 (x) =max i=1;\Delta\Delta\Delta;n 1
g. Then a line segment l = ab is well-behaved if the max-delay and min-delay functions of point p on l are of the forms
We say that is an n 1 -piecewise-
linear concave (n 2 -piecewise-linear convex) function since f 1 linear regions with slopes strictly increasing
(decreasing) from one endpoint of l to the other one, i.e., from a to b or vice versa (Figure 4). A point p 2 l is called a turning
A
between C and D
l 1
l 5 l 6

Figure

5: Examples of Shortest Distance Segments (shown as thick dashed lines or solid dots), and Shortest Distance Regions
(shown as dotted regions). Note that there are three pairs of Shortest Distance Segments between the overlapping polygons C
and D.
point if the slope of a piecewise-linear function defined over l changes at p. Lemma 1 in the Appendix shows that skew(p)
defined over the line segment l will be an n-piecewise-linear concave function, i.e.,
such that
each skew turning point of l corresponds to one of the max-delay or min-delay turning points. A
region P is a well-behaved region if it is a convex polygon whose boundary and interior segments are all well-behaved. Notice
that given a well-behaved line segment l, computing FMR(l) and MSR(l) takes time linear in the number of skew turning points
of l.
Shortest Distance Segments/Regions. To construct a merging region with minimum merging cost, we begin by defining two
more terms. First, for any two convex polygonal regions P and Q with boundaries -(P) and -(Q), the shortest distance segments
between P and Q, denoted SDS(P) and SDS(Q), are a pair of straight line segments on -(P) and -(Q) which are closest to each
other. Note that when P and Q overlap, there could be many pairs of shortest distance segments between P and Q (see Figure 5).
For simplicity, we will arbitrarily take one pair of them as SDS(P) and SDS(Q). 2 Given any two line segments l 1 and l 2 , the
shortest distance region between l 1 and l 2 , denoted SDR(l 1 ; l 2 ), is the set of points which have minimum sum of Manhattan
distances to l 1 and l 2 . We will construct each merging region within the corresponding shortest distance region.
Joining Segments. In the Appendix, we prove in Theorem 1 that each merging region that we construct under the Elmore
model is well-behaved. Thus, for any merging regions P and Q, l must be well-behaved segments.
However, not be a well-behaved region if either
Case I. l 1 and l 2 are parallel Manhattan arcs with non-constant delay functions, or
Case II. The delay functions on l 1 and l 2 have different quadratic terms.
In our method, the delays of each point in SDR(l 1 ; l 2 ) can be determined by any pair of points (p;q) with
long as In Case I, the delay value defined for a point in SDR(l 1 ,l 2 ) will not be unique, and line segments
2 If we allow multiple pairs of shortest distance segments between two polygons, then there will be more than one merging region for each node in the given
topology. The IME method in Section 4 will discuss how to deal with this case.
within SDR(l 1 ,l 2 ) will not even be well-behaved in Case II. To guarantee well-behaved regions, we define the joining segments
merging regions will be constructed within SDR(JS(P), JS(Q)).)
ffl If Case I or II holds, then JS(P) and JS(Q) are chosen to be (arbitrary) single points on l 1 and l 2 , respectively.
ffl Otherwise,
Merging Regions. Finally, given a routing topology G, the merging region of each internal node v 2 G, denoted mr(v), is
defined recursively as follows:
ffl If v is a sink s i , then mr(s g.
ffl If v is an internal node with children a and b, then let L a and L b be the joining segments of mr(a) and mr(b). The merging
region mr(v) is the set of possible locations of v within SDR(L a ; L b ) such that (i) the difference in Elmore delays from v to
any pair of sinks in T v is within the skew bound, and (ii) the merging cost je a subject to the constraint
that point p 2 L a can merge with point q 2 L b only if
We can show that the merging region under this definition always exists. Because of the constraints that we have incorporated
within the construction of merging regions, the "merging region" that we construct does not necessarily contain all feasible
merging points having minimum merging cost je a
3.2 Construction of the Merging Regions
Given merging regions mr(a) and mr(b) of v's children, the following rules can be used to construct the new merging region
mr(v). The construction rules for merging regions are similar to those presented in [19], except that the joining segments can
be parallel segments with any slopes, i.e., besides Manhattan arcs and rectilinear line segments (see Figure 6).
M0 Compute joining segments L a and L b on the boundaries of mr(a) and mr(b).
M1 Compute delay and skew functions and then FMR(l) for the boundary segments l of SDR(L a ; L b ).
M2 If L a and L b are parallel segments with slopes ! \Gamma1 or ? +1, compute FMR(l) for each horizontal line segment l = pq
such that p 2 L a , q 2 L b , and either p or q is a skew turning point of L a or L b (see Figure 6b). Similarly, if L a and L b are
parallel segments with slopes between +1 and \Gamma1, compute FMR(l) for each vertical line segment l = pq such
or q is a skew turning point of L a or L b .
M3 Let F be the set of FMRs computed via rules M1 and M2. If F 6= /
0, then mr(v) is equal to the smallest convex polygonal
region containing F. Otherwise,
(b)
mr(a)
(a)
mr(a)
L a
skew
turning
points
skew
turning
points

Figure

Construction of merging region mr(v) given the merging regions for v's children a and b. The joining segments L a
and L b , shown as thick dashed lines, are parallel Manhattan arcs (with constant max-delay and min-delay) in (a) and parallel
line segments in (b). Note that merging region mr(v) (heavily shaded) is constructed inside (lightly shaded). Each
thick solid line represents the FMR(l) for a line segments l such that l is either the boundary segments of SDR(L a ; L b ) or the
horizontal line segments incident to the skew turning points (shown as hollow circles) on L a or L b .
otherwise. 3
Similar to the proof of Theorem 1 in [19], we can show that each merging region mr(v) for a node v in topology G is a well-behaved
region. Lemma 5 in the Appendix shows that the delay functions on the boundary segments of mr(v) will consist of
m-piecewise-linear functions and a quadratic term, where m - n (n is the number of leaves in the subtree T v rooted at node v).
Based on this lemma, we can show that mr(v) has at most 4n sides. We thus have the following theorem. The detailed proof is
given in the Appendix.
Theorem 1 Under the Elmore delay model, each merging region mr(v) for a node v 2G is a well-behaved region with at most
4n sides, and can be computed by the above construction rules in O(n) time, where n is the number of leaves in T v . 4
It is easy to see that for node v 2G with children a and b, if (i) mr(a) and mr(b) do not overlap, (ii)
and detour wiring is needed, then mr(v) will contain all points having minimum merging
cost. In practice, the above condition holds for most nodes in a good routing topology. Thus, for example, in the zero-skew case
mr(v) is equivalent to the merging segment constructed by the original DME method if no detour wiring is needed. Thus, we
can expect that the performance of our method will be very close to that of DME.
3 In the case where
0, minimum merging cost d(L a ; L b ) cannot meet the skew bound. Thus detour wiring is needed to satisfy the skew bound. To
minimize the detour wiring, mr(v) must be MSR(SDR(L a ; L b )), which is shown to be either MSR(L a ) or MSR(L b ) in Lemma 4 in the Appendix.
4 In all our experiments, no merging region has more than 9 sides. Thus, each merging region is in practice computed in constant time.
30fF,
p'
p"
q"

Figure

7: The Manhattan arc pq has a capacitance of F. It is to be merged with the merging regions defined by two sinks
of capacitance Each pair of coordinates associated with a point p or segment pq represents its max-delay and min-
delay, respectively. Merging of p and p 0 with a skew bound of 24 units requires a merging cost of - 2:44 units and a detour is
necessary. Merging of pq with p 00 q 00 under the same skew bound does not require detour and has a merging cost of 2 units, a
22% reduction of merging cost. We assume that an unit length wire has unit resistance and unit capacitance.
When the skew boundB =-, then the merging regions constructed under the Elmore delay model will be the same rectangles
that are constructed under the pathlength delay model. Thus, the performance of ExG-DME under both the pathlength and
Elmore delay models will be the same. [19] reported that the Steiner trees constructed by ExG-DME average only 0:21% higher
cost than those constructed by one of the best known Steiner tree heuristics [4].
4 The Interior Merging and Embedding Method
As outlined in the previous section, the construction of a merging region is based on the boundary segments of its children's
merging regions: no interior points of the child merging regions are used to construct the new merging regions. This is, of
course, also the case for the pathlength-based BST algorithms in [10, 19]. However, such an approach produces a sub-optimal
merging cost when detouring occurs during the merging. For example, in Figure 7, merging of points p and p 0 requires a detour
and an additional merging cost of - 0:44 unit when compared to the merging of segments pq with p 00 q 00 . Therefore, it is possible
to reduce the merging cost if we consider merging of interior points. Furthermore, even if no detour is required, it is not always
advisable to use only boundary segments for merging. For example, instead of fully utilizing the available slack at the bottom
level (which is the case of the BME method) as in Figure 8(b), we can conserve the slack by merging interior points and thus
reduce the merging cost at a higher level (Figure 8(c)).
Given the above considerations, merging of interior points of the merging regions has strong potential to reduce total wire-
2.5,62.5) 3.4
x
y
(a) Topology (b) Using only boundary segments
for merging
(c) Using samples for merging

Figure

8: An example of routing 4 sinks (filled squares) with a skew bound of 60 units. The merging regions are indicated by
shaded regions. Each internal node (filled circle) is embedded in its merging region. Each pair of coordinates associated with
a point or a segment represents its max-delay and min-delay. For a fixed topology in (a), (b) the routing cost is - 26:5 units if
only joining segments are considered for merging. (c) We can however reduce merging cost by merging interior points in order
to save slack for higher level use. We assume that an unit length wire has unit wire resistance and capacitance.
length. However, merging interior points may cause ambiguity in the delay functions for a point p in the new merging region:
this point may be merging point for infinitely many pairs of interior points from its child merging regions, and may therefore
have different max-delay and min-delay values. Since max-delay and min-delay information is required to construct merging
regions at a higher level, this ambiguity (which is avoided when only nearest boundary segments are considered as in the BME
algorithm) causes difficulty in the merging process. To overcome ambiguity and yet exploit the interiors of merging regions, we
propose the Interior Merging and Embedding (IME) algorithm which employs a sampling strategy and dynamic programming
to consider merging points which are interior to, rather than on the boundary of, the merging region.
In the remainder of this section, we describe the use of samples from the merging regions to construct the next layer of
merging regions. We focus our attention on the use of Manhattan arc to sample the merging regions, i.e. we represent each
merging region by a set of Manhattan arcs, some of which are in the interior of the merging region. However, the idea can be
extended easily to handle sampling segments which are horizontal and vertical. In fact, we can have a mixture of any type of
sampling segments for a merging region as long as they are well-behaved.
4.1 Overview of IME Algorithm
The IME algorithm does bottom-up construction of the merging regions at each internal node, similar to the BME algorithm
presented in the previous section. The key difference is that in the IME algorithm, each node v in the topology G is associated
with a set of merging regions. The interior points in two sets of merging regions can be used to construct
merging regions of their parent node, via the use of sampling. Each merging region R i is sampled by a set of well-behaved line
segments (or sampling segments, denoted ss) in R i . We denote the sampling set of R i by SS(R i ). The sampling set of R , denoted
SS(R ), is S k
As mentioned, we focus our attention on the use of Manhattan arcs to sample the merging regions. The
slope of the Manhattan arcs is chosen to +1 or \Gamma1 such that the points on the Manhattan arc in the merging region have constant
max-delay and min-delay.
Consider the merging of two nodes u and v in G. Let R u and R v be the set of merging regions associated with u and v,
respectively. The parent of u and v in G has as many as jSS(R u )j \Theta jSS(R v )j possible merging regions due to the merging of each
sampling segment in SS(R u ) with each sampling segment in SS(R v ). Since the sampling segments are all Manhattan arcs, the
merging operation is straightforward, as discussed earlier.
Generally speaking, given a merging region, there are infinite number of sampling segments. Furthermore, even if we select
only a constant number of sampling segments for each region, the size of the overall number of merging regions may grow
exponentially during our bottom-up construction of merging regions. In other words, even if each region is sampled by no more
than s sampling segments, the number of merging regions at the root of the routing topology is O(s n ), where n is the total number
of sinks.
To achieve an efficient implementation, we limit the number of merging regions of an internal node by a constant, say k. Each
region is in turn sampled by exactly s sampling segments when the region is being merged with other regions at the sibling node.
When we merge two sampling set, each with - k \Delta s sampling segments, we use the dynamic programming method to compute
the best possible sampling regions for the new node, again using no more than k regions. A key step in the IME algorithm lies
in choosing the "best" k merging regions for the new node.
In what follows, we require the following terminology. A merging region R is associated with three values: (i) Cap(R), the
total capacitance in the subtree rooted at R, (ii) min skew(R), the minimum skew possible within the merging region, and (iii)
skew(R) the maximum skew possible within the merging region. In the IME algorithm, merging regions are constructed in
such a way that (i) Cap(R) =Cap(ss a ) +Cap(ss b ) +c a +c b is constant for all points in R, which is constructed by merging two
sampling segments, say ss a and ss b , of its children a and b with merging cost je a respectively, and (ii) max skew(R) is
kept within the skew bound B. If we plot a graph with the horizontal axis representing the skew and the vertical axis representing
the capacitance, then each merging region R i of node v is a horizontal line segment with y-coordinate Cap(R i ) and x-coordinates
for the left and right endpoints, respectively.
Consider a node v in G with a set of more than k merging regions associated with it after merging its two children. A merging
region R of v is said to be "redundant" if there exists another merging region R 0 of v such that min skew(R
redundant merging
regions Skew
bound
skew
capacitance
(a) Set of Merging Regions
Skew
bound
skew
capacitance
(b) Set of Irredundant Merging Regions with
Skew
bound
skew
capacitance
(c) Staircase
Skew
bound
skew
capacitance
(d) Staircase with a step removed
step removed
error of new staircase
irredundant merging
regions
area(v) min_skew(R )
extended

Figure

9: (a) Set of merging regions. (b) Set of irredundantmerging regions with extended max-skew = B. (c) Forming a staircase
from min skew(R i ) to merging region R i\Gamma1 . (d) Removing an intermediate step results in a new staircase with an error depicted
by the shaded region.
and Cap(R 0 ) !Cap(R) (See Figure 9(a)). Let denote the set of irredundant merging regions of v with
arranged in descending order of Cap(R i ), then min skew(R
The set of irredundant merging regions forms a staircase with steps as shown in Figure 9. First, we extend the line
segment representing such irredundant merging region such that it touches the vertical line representing skew bound B (Figure
9(b)). Hence, each irredundant merging region has an extended max-skew equals to B, the skew bound. By creating a step from
at a height ofCap(R i ) to Cap(R i\Gamma1 ) for all i with 1! 1-m, we have a staircase starting at min skew(Rm )
as shown in Figure 9(c).
The area of the staircase of a set of merging regions of node v, denoted area(v), is defined to be the area under the staircase
between the skews min skew(R 1 ) and min skew(R k
fmin skew(R
If we remove one of the intermediate steps, say R m), we obtain a (m \Gamma 2)-step staircase which approximates the
original staircase with error (min skew(R Therefore, in order to
retain a good spectrum of no more than k merging regions at each step, we solve the following problem:
The Optimal (m;k)-Sampling Problem: Given a set of m irredundant merging regions, find a subset
of k (2 - k - m) merging regions such that after removing each of the merging regions, the total error of
the resulting staircase IMR ae IMR is minimum (or equivalently, area(IMR
area(IMR) is minimal), where strictly monotonically increasing function. Note that both R 1 and Rm
are retained in IMR 0 .
4.2 Optimal Solution to the (m;k)-Sampling Problem
We developed an optimal algorithm to the (m;k)-sampling problem using the dynamic programming approach. Effectively, we
compute an optimal (m )-sampling solution S by choosing the
best k 0 -sampling from m 0 merging regions fR i under the condition that R i and R i+m 0 \Gamma1 are in the k 0 -sampling.
be the minimum error for the optimal (m )-sampling solution S We can show that
Theorem 2 For each 2 -m for the optimal (m
sampling solution is:
(2)
Proof: For each 1 -
Case (i) If m , we can select all m 0 merging regions and therefore err i [m
Case (ii) If 2, we are forced to retain the region R i and R i+m \Gamma1 . Therefore, the optimal error optimal error
is the error of the optimal solution S are retained, plus the error incurred for removing
R i+m \Gamma2
from
Case (iii) If we have to choose another k regions from fR besides the two mandatory
regions R i and R i+m
. Suppose i 0 is the index of the region after i in the optimal solution S then the error of the new
staircase between the skews min skew(R i ) and min skew(R which is computed in Case (ii). Now,
we have to select the optimal solutionS i 0 [m from the regions fR Note that R i is retained
in both sub-solutions S i [i 1. Therefore, we iterate i 0 from i +1 to
compute the optimal error err to be smallest among all the sums of err i [i
Skew
bound
skew
capacitance
err [m'-1,2]

Figure

10: The lightly shaded region is the area error for the optimal solution S and the darker region is the
skew-capacitance product term in case (ii) of Eqn. (2).
Skew
bound
skew
Cap
err [i'-i+1,2]
err [m'-i'+i,k'-1]

Figure

11: The lightly shaded region is the area error for the optimal solution S and the two darker regions account
for the error of the optimal solution S case (iii) of Eqn. (2).
A straightforward implementation of the above computation gives an O(k \Delta m 3 )-time optimal (m;k)-sampling algorithm. After
careful pruning of the solution space, we can achieve a better time complexity. First, note that for case (i) and (ii) of Eqn. (2),
the solution is straightforward and we can compute all S i [m
the conditions stated in case (i) and (ii) of Eqn. (2) in O(m 2 )-time.
In the following,we assume m? k ? 2. We are interested in obtainingthe optimalsolutionS 1 [m;k]. To determine the index of
the region after R 1 in the optimal solution, we compute err 1 [m;k] with err 1 [i; 2] and err i 2.
Assuming that apply case (iii) of Eqn. (2) to solve for err using err i [i
2. Continuing this recursion, we observe a pattern shared by the errors err 1 [m;k],
2], and so on. If we denote these errors generically by err i [m then we observe that
cases. Therefore, we do not have to compute err i [m for every valid combination of i, m 0 and k 0 , each
Optimal (m;k)-Sampling Algorithm
for each k
next
for each
next
for each k 0 s.t.
for each i s.t.
next
for each i s.t.
if err [i
next
do

Figure

12: The optimal (m;k)-Sampling Algorithm. Note that m- k.
in its respective range 1). Instead, only errors err i [m are
required.
The Optimal (m;k)-Sampling Algorithm is given in Figure 12. The matrix next i [m in the algorithm records the index
of the mergion region immediately after R i in the optimal subset (of size k 0 ) of the set fR i g. We first initialize
for the first two cases of Eqn. (2). Then, for each k 0 and i such that
apply case (iii) of Eqn. (2) to compute the minimum error err Therefore, we have the following
result:
Theorem 3 The time complexity of the optimal (m;k)-Sampling Algorithm is O(k
4.3 Summary of the IME Algorithm
To summarize, the IME algorithm still retains the flow of other DME-based algorithms, namely compute a tree of merging regions
in a bottom-up fashion and perform embedding in a top-down manner. The key difference between the IME and other
Boundary-Based algorithm is that a set of no more than k irredundant merging regions are associated with each node and most
importantly, some of these merging regions are due to merging of interior points.
In our implementation, a sampling set for each node is obtained by representing each irredundant merging region using a
set of s parallel Manhattan arcs. The slope of the Manhattan arcs is chosen such that max-delays and min-delays for any two
IME Merging Procedure
Let u and v be the children of w;
using - s Manhattan arcs;
Let Rw be the set of merging regions of w, initially /
For each segment from SS(R u ) and each segment from SS(R v )
Merge to produce a merging region of w; Put in Rw ;
Sort Rw in descending order of region capacitance of w;
Scan Rw in one pass to weed out "redundant" merging regions;
Apply Optimal (m;k)-Sampling Algorithm on IMR of w if necessary;

Figure

13: Outline for the merging operation of the IME algorithm.
points on the Manhattan arc in the merging region are the same. Therefore, the merging operation is performed on Manhattan
arcs which is straightforward as illustrated in Figure 6.
We then sort the resultant merging regions in descending order of their capacitance. Redundant regions are weeded out and
the resultant irredundant merging regions are sampled by the optimal (m;k)-sampling algorithm. The outline of the merging
process is given in Figure 13. We can observe that the most expensive operation in the merging process is due to the optimal
(m;k)-sampling algorithm which is polynomial in terms of m - is a constant, the merging process can be performed
in constant time and the time complexity of the clock tree construction algorithm is still in the same order.
5 Experimental Results
We have implemented the BME and IME algorithms in ANSI C on Sun SPARC-20 machines. The benchmark test cases r1-r5
[30] were used to evaluate our algorithms for skew bounds in the range of 0-10ns. Table 1 compares the zero-skew clock routing
costs of the best known algorithm (CL+I6 from [15]) with the various bounded-skew routing costs obtained by our algorithms.
Also included in the Table is the CPU time for both BME and IME.
In this experiment, the IME algorithm keeps at most merging regions for each internal node, and slices each merging
region to sampling segments for merging with other nodes. Both of our methods have comparable results. It appears
that IME produces better results for larger circuits when the skew bound is large, but at the expense of longer running time.
In general, we see a decrease in total wirelength as the skew increases. However, our results do not compare favorably with
[15] when it comes to zero skew. We believe that this is due to the fact that the CL+I6 algorithm performs local optimization
using exhaustive search and calculates an optimum sequence, which we did not implement in our algorithm. The other reason
is that [15] used the best result from eight different values of the k parameter ranging from 2 to 4 (recall the discussion of the
Greedy-DME algorithm in Section 2.1), while we only set one value of the k parameter of [15] to be 1.
We alo compare the performance of BME and IME using the same topologies, which are generated by BME and IME respec-
tively. The results are shown in Tables 2 and 3. For the zero-skew bound, IME is equivalent to DME while BME is equivalent to
Skew Bound r1 r2 r3 r4 r5
(ps) Wirelengths (CPU time: hr:min:sec)

Table

1: The cost-skew tradeoff and running time of the BME and IME algorithms for benchmark circuits r1-5 [30]. We mark
the cases where IME outperforms BME by *.
DME only if no detour wiring is required. 5 Thus, IME is expected to have better performance than BME. However, for non-zero
skew bounds, IME will not compete favorably with BME unless IME uses a large sampling set (i.e., at the expense of larger CPU
time). For instance, Table 2 shows that BME outperforms IME for non-zero skew bounds when IME uses 7. On
the other hand, Table 3 shows that when closely match the BME performance, albeit with much longer CPU
time.
Skew r1 r2 r3 r4 r5
Bound(ps) Wirelengths (CPU time: min:sec)

Table

2: The performance comparison between BME and IME using the topologies generated by IME. Total wirelengths of IME
for different skew bounds are in Table 1. BME results are better than those of IME in most cases except where marked by *.
A more detailed experiment for all benchmark circuits was conducted to investigate the tradeoff between total wirelength
and skew, and the tradeoff between power dissipation and skew for realistic skew bounds in the range of 0 \Gamma 150ps. We used
HSPICE simulations to measure the power dissipation for benchmarks r1-3 at 50MHz, and r4-5 at 5MHz (due to the rise/fall time
constraints). The results of IME for the benchmark circuits r1-r5 are shown in Figure 14. When the skew bound is relaxed from
zero to 150ps, we achieved a average power reduction of up to 18:4%. We also achieved 26:6% average wirelength reduction
5 It is easy to modify the construction rules M0-M3 so that For example, for each node v with children a and b, if
mr(a) and mr(b) are Manhattan arcs with constant delays and skew = B, then mr(v) will be a merging segment and can be constructed using the DME method.
Skew r1 r2 r3 r4 r5
Bound(ps) Wirelengths (CPU time: hr:min:sec)

Table

3: The performance comparison between BME and IME using the same topologies generated by BME. The total wire-
lengths of BME for different skew bounds are given in Table 1. We mark the cases where IME outperforms BME by *.
when compared to the best reported zero-skew solutions (by the CL+I6 algorithm in [15]).
6 Conclusion and Future Work
In conclusion, we have presented new bounded-skew routing tree approaches under the Elmore delay model. We prove several
key properties of the merging regions under the Elmore delay model. Our first approach, called BME, utilizes merging points that
are restricted to the boundaries of merging regions. A second approach, called IME, employs a sampling strategy and dynamic
programming to consider merging points that are interior to the merging regions.
Recall from Section 4 that the IME algorithm can handle more general sampling segments other than Manhattan arcs. As
our current implementation uses only Manhattan arcs for sampling, future work includes extending the IME approach to include
well-behaved sampling segments other than Manhattan arcs. We are also studying better sampling strategies for speed-up of the
IME method. Our final goal is to combine the techniques of BST topology generation with our recent work on optimal sizing
of interconnects and drivers [9, 11], and develop a practical clock routing algorithm which carries out simultaneous topology
generation, buffer insertion, and wiresizing to achieve bounded skew with minimum power dissipation under various layout
constraints.



--R

"A Symmetric Clock-Distribution Tree and Optimized High-Speed Interconnections for Reduced Clock Skew in ULSI and WSI Circuits,"
"Zero-Skew Clock Routing Trees With Minimum Wirelength"
"Near-Optimal Critical Sink Routing Tree Constructions,"
"An Edge-Based Heuristic for Rectilinear Steiner Trees"
"Zero Skew Clock Net Routing,"
"Zero Skew Clock Routing With Minimum Wirelength,"
"A Buffer Distribution Algorithm for High-Speed Clock Routing,"
"Skew Sensitivity Minimization of Buffered Clock Tree,"
"Simultaneous Driver and Wire Sizing for Performance and Power Optimization,"
"Minimum-CostBounded-SkewClock Routing,"
"Optimal Wiresizing Under Elmore Delay Model,"
"Matching-BasedMethods for High-Performance Clock Routing,"
"Minimum Skew and Minimum Path Length Routing in VLSI Layout Design,"
"Minimum Path-Length Equi-Distant Routing,"
"A Clustering-Based Optimization Algorithm in Zero-Skew Routing,"
"Delay Minimization for Zero-Skew Routing"
"Clock Distribution Design in VLSI Circuits - An Overview"
"Buffer Placement in Distributed RC-Tree Networks for Minimal Elmore Delay,"
"On the Bounded-SkewRouting Tree Problem"
"Clock Routing for High Performance ICs,"
"A New Class of Iterative Steiner Tree Heuristics with Good Performance"
On Optimal Interconnections for VLSI
"Planar-DME: Improved Planar Zero-Skew Clock Routing with Minimum Pathlength Delay,"
"Low-Cost Single-Layer Clock Trees with Exact Zero Elmore Delay Skew,"
"Process-Variation-Tolerant Clock Skew Minimization,"
"Skew Reduction in Clock Trees Using Wire Width Optimization"
"Reliable Non-Zero Skew Clock Tree Using Wire Width Optimization"
"Skew and Delay Optimization for Reliable Buffered Clock Trees,"
"A Specified Delay Accomplishing Clock Router Using Multiple Layers,"
"Exact Zero Skew,"
"Power Distribution Topology Design"
"Perfect-balance planar clock routing with minimal path-length,"
"Delay Bounded Minimum Steiner Tree Algorithms for Performance-Driven Routing"

--TR
Zero skew clock net routing
A clustering-based optimization algorithm in zero-skew routings
Low-cost single-layer clock trees with exact zero Elmore delay skew
Simultaneous driver and wire sizing for performance and power optimization
On the bounded-skew clock and Steiner routing problems
Perfect-balance planar clock routing with minimal path-length

--CTR
Nan Guofang , Li Minqiang , Kou Jisong, Multi-level genetic algorithm (MLGA) for the construction of clock binary tree, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
Joe G. Xi , Wayne W.-M. Dai, Jitter-tolerant clock routing in two-phase synchronous systems, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.316-320, November 10-14, 1996, San Jose, California, United States
Andrew B. Kahng , C.-W. Albert Tsao, More practical bounded-skew clock routing, Proceedings of the 34th annual conference on Design automation, p.594-599, June 09-13, 1997, Anaheim, California, United States
Joe G. Xi , Wayne W.-M. Dai, Useful-skew clock routing with gate sizing for low power design, Proceedings of the 33rd annual conference on Design automation, p.383-388, June 03-07, 1996, Las Vegas, Nevada, United States
Uday Padmanabhan , Janet M. Wang , Jiang Hu, Statistical clock tree routing for robustness to process variations, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
Anand Rajaram , Bing Lu , Wei Guo , Rabi Mahapatra , Jiang Hu, Analytical Bound for Unwanted Clock Skew due to Wire Width Variation, Proceedings of the IEEE/ACM international conference on Computer-aided design, p.401, November 09-13,
Andrew B. Kahng , C.-W. Albert Tsao, Practical Bounded-Skew Clock Routing, Journal of VLSI Signal Processing Systems, v.16 n.2-3, p.199-215, June/July 1997
Hailin Jiang , Kai Wang , Malgorzata Marek-Sadowska, Clock skew bounds estimation under power supply and process variations, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
M. Saitoh , M. Azuma , A. Takahashi, Clustering based fast clock scheduling for light clock-tree, Proceedings of the conference on Design, automation and test in Europe, p.240-245, March 2001, Munich, Germany
Atsushi Takahashi , Kazunori Inoue , Yoji Kajitani, Clock-tree routing realizing a clock-schedule for semi-synchronous circuits, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.260-265, November 09-13, 1997, San Jose, California, United States
Jason Cong , Andrew B. Kahng , Cheng-Kok Koh , C.-W. Albert Tsao, Bounded-skew clock and Steiner routing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.341-388, July 1998
I-Min Liu , Tan-Li Chou , Adnan Aziz , D. F. Wong, Zero-skew clock tree construction by simultaneous routing, wire sizing and buffer insertion, Proceedings of the 2000 international symposium on Physical design, p.33-38, May 2000, San Diego, California, United States
Joe Gufeng Xi , Wayne Wei-Ming Dai, Useful-Skew Clock Routing with Gate Sizing for Low Power Design, Journal of VLSI Signal Processing Systems, v.16 n.2-3, p.163-179, June/July 1997
Arif Ishaq Abou-Seido , Brian Nowak , Chris Chu, Fitted Elmore delay: a simple and accurate interconnect delay model, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.7, p.691-696, July 2004
Yehea I. Ismail , Eby G. Friedman , Jose L. Neves, Equivalent Elmore delay for
RLC
bounded-skew;zero-skew;elmore delay;routing trees;global routing;pathlength delay;clock routing;VLSI