Unit 8: Special Net Routing & Performance Optimization

․ Course contents:
⎯ Clock net routing
⎯ Power/ground routing
⎯ Performance optimization
․ Readings
⎯ W&C&C: Chapter 13
⎯ S&Y: Chapter 7

1
Courtesy of Y.-W. Chang
 The Clock Routing Problem
․ Digital systems
⎯ Synchronous systems: Highly precise clock achieves

communication and timing.

⎯ Asynchronous systems: Handshake protocol achieves the
timing requirements of the system.
․ Clock skew: the difference in the minimum and the maximum
arrival times of the clock.

․ Clock routing: Routing clock nets such that

1. clock signals arrive simultaneously
2. clock delay is minimized
⎯ Other issues: total wirelength, power consumption

2
Courtesy of Y.-W. Chang
 Clock Routing
․ Given the routing plane and a set of points
P = {p1, p2, …, pn} within the plane and clock entry
point p0 on the boundary of the plane, the Clock
Routing Problem is to interconnect each pi  P such
that maxi, j  P|t(0, i) - t(0, j)| and maxi  P t(0, i) are both
minimized.

p4
p6
p1

p0 p0 p5
p2
p3

Clock-tree synthesis (CTS): make the clock nets a tree

3
Courtesy of Y.-W. Chang
 Clock Routing Algorithms
․ Pathlength-based Clock-Tree Synthesis (CTS)
1. H-tree: Dhar, Franklin, Wang, ICCD-84; Fisher & Kung, 1982.
2. Methods of means & medians (MMM): Jackson, Srinivasan,
Kuh, DAC-90.
3. Geometric matching: Cong, Kahng, Robins, DAC-91.
․ RC-delay based CTS
1. Exact zero skew: Tsay, ICCAD-91.
2. Deferred-merge embedding (DME) algorithm: Boese & Kahng,
ASICON-92; Chao & Hsu & Ho, DAC-92; Edahiro, NEC R&D, 1991.
3. Lagrangian relaxation: Chen, Chang, Wong, DAC-96.
․ Simulation-based CTS
⎯ ISPD-09 CTS contest (ASP-DAC-10, DATE-10)
․ Timing-model independent CTS
⎯ Shih & Chang, DAC-10
․ Mesh-based & tree-link-based clock routing
4
Courtesy of Y.-W. Chang
 H-Tree Based Algorithm
․ H-tree: Dhar, Franklin, Wang, “Reduction of clock
delays in VLSI structure,” ICCD-1984.

Similar topology: X-tree

5
Courtesy of Y.-W. Chang
 The MMM Algorithm
․ Jackson, Sirinivasan, Kuh, “Clock routing for high-performance
ICs,” DAC-1990.
․ Each block pin is represented as a point in the region, S.
․ The region is partitioned into two subregions, SL and SR.
․ The center of mass is computed for each subregion.
․ The center of mass of the region S is connected to each of the
centers of mass of subregion SL and SR.
․ The subregions SL and SR are then recursively split in Y-direction.
․ Steps 2--5 are repeated with alternate splitting in X- and Y-
direction.
․ Time complexity: O(n log n).

6
Courtesy of Y.-W. Chang
 The Geometric Matching Algorithm
․ Cong, Kahng, Robins, “Matching based models for high-
performance clock routing,” IEEE TCAD, 1993.
․ Clock pins are represented as n nodes in the clock tree (n = 2k).
․ Each node is a tree itself with clock entry point being node itself.
․ The minimum cost matching on n points yields n/2 segments.
․ The clock entry point in each subtree of two nodes is the point on
the segment such that length of both sides is same.
․ Above steps are repeated for each segment.
․ Apply H-flipping to further reduce clock skew (and to handle edges
intersection).
․ Time complexity: O(n2 log n).

7
Courtesy of Y.-W. Chang
 Elmore Delay: Nonlinear Delay Model
․ Parasitic resistance and capacitance dominate delay in deep
submicron wires.
․ Resistor ri must charge all downstream capacitors.
․ Elmore delay: Delay can be approximated as sum of sections:
resistance  downstream capacitance.

․ Delay grows as square of wire length.

․ Cannot apply to the delay with inductance consideration, which is
important in high-performance design.

8
Courtesy of Y.-W. Chang
 Wire Models
․ Lumped circuit approximations for distributed RC lines: -model
(most popular), T-model, L-model.

․ -model: If no capacitive loads for C and D,

A to B: AB = r1 (c1/2 + c2 + c3);
B to C: BC = r2 (c2/2);
B to D: BD = r3 (c3/2).

9
Courtesy of Y.-W. Chang
 Example Elmore Delay Computation
․ 0.18 m technology: unit resistance = 0.075  / m; unit
capacitance = 0.118 fF/m.
⎯ Assume CC = 2 fF, CD = 4 fF.

⎯ BC = rBC (cBC / 2 + CC) = 0.075  150 (17.7/2 + 2) = 120 fs

⎯  BD = rBD (cBD / 2 + CD) = 0.075  200 (23.6/2 + 4) = 240 fs

⎯  AB = rAB (cAB/2 + CB) = 0.075  100 (11.8/2 + 17.7 + 2 + 23.6

+ 4) = 400 fs
⎯ Critical path delay:  AB +  BD = 640 fs.

10
Courtesy of Y.-W. Chang
 Exact Zero Skew Algorithm
․ Tsay, “Exact zero skew algorithm,” ICCAD-91.
․ To ensure the delay from the tapping point to leaf nodes of subtrees T1
and T2 being equal, it requires that
r1 (c1/2 + C1) + t1 = r2 (c2/2 + C2) + t2.
․ Solving the above equation, we have

where  and  are the per unit values of resistance and capacitance, l the
length of the interconnecting wire, r1 = xl, c1 = xl, r2 = (1 - x) l, c2 = (1
- x)l.

11
Courtesy of Y.-W. Chang
 Zero-Skew Computation
․ Balance delays: r1(c1/2 + C1) + t1 = r2 (c2/2 + C2) + t2.
․ Compute tapping points:  (): per
unit values of resistance (capacitance); l: length of the wire;
r1 = xl, c1 = x l; r2 = (1 - x) l, c2 =  (1 - x) l.
․ If x  [0, 1], we need snaking to find the tapping point.
․ Exp:  = 0.1  /unit,  = 0.2 F/unit (tapping points: E, F, G)

merging segment

merging segment 12
Courtesy of Y.-W. Chang
 Deferred Merge Embedding (DME)
․ Boese & Kahng, ASICON-92; Chao & Hsu & Ho, DAC-92;
Edahiro, NEC R&D, 1991
․ Consists of two stages: bottom-up + top-down
․ Bottom-up: Build the potential embedding locations of
clock sinks (i.e., a segment for potential tapping points)
․ Top-down: Determine exact locations for the embedding

13
Courtesy of Y.-W. Chang
 Delay Computation for Buffered Wires
․ Wire:  = 0.068  /m,  = 0.118 fF/ m2; buffer:  ' = 180  / unit
size, ' = 23.4 fF/unit size; driver resistance Rd = 180 ; unit-sized
wire, buffer.

14
Courtesy of Y.-W. Chang
Buffering and Wire Sizing for Skew Minimization
․ Discrete wire/buffer sizes: dynamic programming
⎯ Chung & Cheng, “Skew sensitivity minimization of buffered
clock tree,” ICCAD-94.
․ Continuous wire/buffer sizes: mathematical
programming (e.g., Lagrangian relaxation)
⎯ Chen, Chang, Wong, “Fast performance-driven optimization for
buffered clock trees based on Lagrangian relaxation,” DAC-96.
⎯ Considers clock skew, area, delay, power, clock-skew
sensitivity simultaneously.

15
Courtesy of Y.-W. Chang
 Clock Meshes
․ More alternative paths to clock sinks
⎯ Good for high-performance circuits with stringent skew and
variation constraints
․ Drive mesh from the boundary or from grid points
․ H-tree is a good candidate to drive mesh

Alpha 21264 processor [Bailey et al. 1998] IBM Power4 processor [Anderson et al. 2001]

16
Courtesy of Y.-W. Chang
 Power Integrity: IR (Voltage) Drop
⚫ Power consumption and rail parasitics cause actual supply
voltage to be lower than ideal
− Metal width tends to decrease with length increasing in
nanometer design
⚫ Effects of IR drop
− Reducing voltage supply reduces circuit speed (5% IR drop =>
15% delay increase)
− Reduced noise margin may cause functional failures
1.8V 1.46V 2.23V

violation
HM1 SM2 HM3
HM1
SM1 HM1
SM1

HM2 HM3 HM2

HM2 HM3

SM2 SM2 SM1

SM2

2.89V 3V 2.95V
17
Courtesy of Y.-W. Chang
 Power/Ground (P/G) Routing
․ Are usually laid out entirely on metal layers for
smaller parasitics.
․ Two steps:
1. Construction of interconnection topology: non-crossing
power, ground trees.
2. Determination of wire widths: prevent metal migration,
keep voltage (IR) drop small, widen wires for more power-
consuming modules and higher density current (1.5 mA per
 m width for Al). (So area metric?)

18
Courtesy of Y.-W. Chang
 Power/Ground Network Optimization
․ Use the minimum amount of chip area for wiring P/G networks
while avoiding potential reliability failures due to electromigration
and excessive IR drops.
․ Tan and Shi, “Fast power/ground network optimization based on
equivalent circuit modeling”, DAC-2001.
⎯ Build the equivalent models for series resistors and apply a

sequence of the linear programming (SLP) method to solve the

problem.
⎯ Size wire segments assuming the topologies of P/G networks

to be fixed.
․ Wu and Chang, “Efficient power/ground network analysis for power
integrity driven design methodology,” DAC-2004.
․ Liu and Chang, “Floorplan and power/ground co-synthesis for fast
design convergence,” ISPD-06 (TCAD-07).

19
Courtesy of Y.-W. Chang
 Problem Formulation
․ Let G = {N, B} be a P/G network with n nodes N = {1, …, n} and b
branches B = {1, …, b}; branch i connects two nodes: i1 and i2 with
current flowing from i1 to i2.
․ Let li and wi be the length and width of branch i, respectively. Let ρ
be the sheet resistivity. Then the resistance ri of branch i
vi − vi li
is ri = = .
1 2

Ii wi i1 i2
․ Total P/G routing area is as follows:
wi
li
․ P/G network optimization is to minimize f(V, I) subject to the
constraints listed in the next slide.
․ Relax the nonlinear objective function and then translate the
constrained nonlinear programming problem into a SLP problem.

20
Courtesy of Y.-W. Chang
 Constraints
․ The voltage IR drop constraints.
⎯ Vi  Vh, min for power networks.
⎯ Vi  Vl , max for ground networks.
liIi
․ The minimum width constraints: wi =   wi , min
Vi1 − Vi 2
․ The electro-migration constraints: Ii/wi ≤ σ => Vi − Vi  li 1 2

⎯ σ is a constant for a particular routing layer with a fixed

thickness.
․ Equal width constraints: wi = wj or vi1 − vi 2 = vj1 − vj 2
liIi ljIj

․ Kirchoff ’s current law (KCL): I = 0

iB ( j )
i

⎯ For each node j = {1, …, n}, B(j) is the set of indices of

branches connecting to node j.

21
Courtesy of Y.-W. Chang
Reducing the Problem Size with Equivalent Circuits
․ Consider a series resistor chain commonly seen in the P/G
network below.

Series resistor chain Equivalent circuit

․ The equivalent
n −1
resistor Rs is just the sum of all the resistors in
series, Rs =
R.
i =1
i

․ By superposition, the equivalent currents Ie1, and Ien can be

computed as follows:

22
Courtesy of Y.-W. Chang
 Equivalent Circuit (cont’d)
․ The voltages at the intermediate nodes are calculated
based on superposition as follows:
Ri
Vi + 1 = Vi − Vs − RiIei
Rs
Iei + 1 = Iei − Ii

Series resistor chain Equivalent circuit

23
Courtesy of Y.-W. Chang
Equivalent Circuit Example

24
Courtesy of Y.-W. Chang
 Design Methodology Evolution
․ IR-drop aware design methodology for faster design
convergence
Floorplanning Floorplanning
Floorplanning IR-drop Analysis
IR-drop Analysis
P&R no
OK
iterative loop yes P&R
RC Extraction
P&R
RC Extraction
Simulation
RC Extraction
Simulation
SI Analysis
Simulation
no
OK SI Analysis
iterative loop yes
SI Analysis
ISPD-06 (TCAD-07) flow
Traditional flow DAC-04 flow (Liu & Chang)
(Wu & Chang)
25
Courtesy of Y.-W. Chang
 Ideal Scaling of MOS Transistors
․ Feature size scales down by S times:

26
Courtesy of Y.-W. Chang
 Ideal Scaling of Interconnections
․ Feature size scales down by S times:

27
Courtesy of Y.-W. Chang
 Techniques for Higher Performance
․ In very deep submicron technology, interconnect delay
dominates circuit performance.
․ Techniques for higher performance
⎯ SOI: lower gate delay.
⎯ Copper interconnect: lower resistance.
⎯ Dielectric with lower permittivity: lower capacitance.
⎯ Buffering: Insert (and size) buffers to “break” a long
interconnection into shorter ones.
⎯ Wire sizing: Widen wires to reduce resistance (careful for
capacitance increase).
⎯ Shielding: Add/order wires to reduce capacitive and inductive
coupling.
⎯ Spacing: Widen wire spacing to reduce coupling.
⎯ Others: padding, track permutation, net ordering, etc.

28
Courtesy of Y.-W. Chang
Interconnect Dominates Circuit Performance!!
70 Worst-case
interconnect
60
delay due
to crosstalk
50
Delay (ps)

40

30
Interconnect
20 delay

10
Gate delay

650 500 350 250 180 150 100 70 (nm)

Technology Node

In ≦ 0.18μm wire-to-wire
CS CW
capacitance dominates (CW>>CS)

29
Courtesy of Y.-W. Chang
 Optimal Buffer Sizing w/o Considering Interconnects
․ Delay through each stage is  tmin, where tmin is the average delay
through any inverter driving an identically sized inverter.
․ n = CL/Cg  n = ln (CL/Cg)/ln , where CL is the capacitive load
and Cg the capacitance of the minimum size inverter.
․ Total delay .
․ Optimal stage ratio:
․ Optimal delay:
․ Buffer sizes are exponentially tapered ( = e).

30
Courtesy of Y.-W. Chang
 Wire Sizing
․ Wire length is determined by layout architecture, but we can
choose wire width to minimize delay.
․ Wire width can vary with distance from driver to adjust the
resistance which drives downstream capacitance.
․ Wire with minimum delay has an exponential taper.
․ Can approximate optimal tapering with segments of a few
widths.
․ Recent research claims that buffering is more effective than
wire sizing for optimizing delay, and two wire widths are
sufficient for area/delay trade-off.

31
Courtesy of Y.-W. Chang
 Optimal Wire-Sizing Function
․ Suppose a wire of length L is partitioned into n equal-length wire segments,
each of length x = L/n; unit resistance and capacitance: , .
․ The respective resistance and capacitance of i-th wire segment can be
approximated by x / f(xi) and x f(xi), where f(xi) is the width at
position xi.
․ Elmore delay:

․ As n → , Dn → D:

․ Optimal wire sizing function f(x) = ae-bx, where

x
32
Courtesy of Y.-W. Chang
 Simultaneous Wire & Buffer Sizing
․ Input: Wire length L, driver resistance Rd, load capacitance CL,
unit wire area capacitance c0, unit wire fringing capacitance cf, unit-
sized wire resistance r0, unit-size capacitance of a buffer cb, unit-
size buffer resistance rb, intrinsic buffer delay Tin, and the number
of buffers N.
․ Objective: Determine the stage ratio  for buffer sizes and the
stage ratio  for wire widths such that the wire delay is minimized.

33
Courtesy of Y.-W. Chang
Wire/Buffer Size Ratios for Delay Optimization
․ Chang, Chang, Jiang, ISQED-2002.

․ In practice, the delay of a wire DN(, ) is a convex function of the

stage ratio  for practical buffer sizes and the stage ratio  for
practical wire widths.
․ Can apply efficient search techniques (e.g., binary search) to find
the optimum ratios.

34
Courtesy of Y.-W. Chang
Performance Optimization: A Sizing Problem
• Minimize the maximum delay Dmax by changing w1,…,wn

Minimize Dmax
subject to Di ( w)  D max , i = 1..m
L  wi  U , i = 1..n

w9 w7 w4
a w1
D1<Dmax

w10 w5

b D2<Dmax
w11 w6 w3 w2
w8
35
Courtesy of Y.-W. Chang
 Popular Sizing Works
․ Algorithmic approaches: faster, non-optimal for general problems
⎯ TILOS (Fishburn, Dunlop, ICCAD-85)
⎯ Weighted Delay Optimization (Cong et al., ICCAD-95)
․ Traditional mathematical programming: often slower, optimal
⎯ Geometric Programming (TILOS)
⎯ Augmented Lagrangian (Marple et al., 86)
⎯ Sequential Linear Programming (Sapatnekar et al.)
⎯ Interior Point Method (Sapatnekar et al., TCAD-93)
⎯ Sequential Quadratic Programming (Menezes et al., DAC-95)
⎯ Augmented Lagrangian + Adjoin Sensitivity (Visweswariah, et
al., ICCAD-96, ICCAD-97)
․ Lagrangian relaxation based mathematical
programming: (Chen, Chang, Wong, DAC-96; Jiang,
Chang, Jou, DAC-99 [TCAD, Sept. 2000]; and many
more)
◼ Fast and optimal

36
Courtesy of Y.-W. Chang
 TILOS: Heuristic Approach
• Finds sensitivities associated with each gate
• Up-sizes the gate with the maximum sensitivity
• Minimizes the objective function

Minimize Dmax

w9 w7 w4
a w1
D1<Dmax

w10 w5

b D2<Dmax
w11 w6 w3 w2
w8
37
Courtesy of Y.-W. Chang
 Weighted Delay Optimization
• Cong, et. al., ICCAD-95
• Sizes one wire at a time in the DFS order
• Minimize the weighted delay
• Best weights?
Minimize 1D1 +2D2
Loads
Driver w1 w2 w3 1D 1

2D 2
w4 w5

38
Courtesy of Y.-W. Chang
From Mathematical Prog. to Lagrangian Relaxation

min cx
Posynomial min L()=cx + (Ax-b)
st Axb forms st xX
xX

Mathematical Positive coefficient

Lagrange multipliers 
formulation polynomials

39
Courtesy of Y.-W. Chang
 Mathematical Programming

• Formulation: Minimize f ( x)
subject to g i ( x)  0, i = 1..m

m
• Lagrangian: L( ) = f ( x) +   g ( x), where   0
i i i
i =1
• Optimality (Necessary) Condition (Kuhn-Tucker theorem):
L( ) m
= 0  f ( x ) +   g ( x ) = 0
xi i i
i =1
 g = 0 (Complementary Condition)
i i
g ( x)  0,   0 (Feasibility Condition)
i i

40
Courtesy of Y.-W. Chang
 Lagrangian Relaxation
n
Minimize f ( x) LRS Minimize f ( x) +  i g i ( x)
i =1
subject to g i ( x)  0, i = 1..n
subject to gi ( x)  0, i = n + 1..m
g i ( x)  0, i = n + 1..m

․ LRS (Lagrangian Relaxation Subproblem)

․ There exist Lagrangian multipliersλthat lead LRS to
the optimal solution for convex programming
⎯ When f(x), gi(x)’s are all positive polynomials
(posynomials)
․ The optimal solution for any LRS is a lower bound
of the original problem

41
Courtesy of Y.-W. Chang
 Lagrangian Relaxation
Minimize Dmax
subject to Di ( w)  D max , i = 1..m
L  wi  U , i = 1..n
Lagrangian Relaxation
m
Minimize Dmax +  i ( Di ( w) − D max ) Lλ
i =1

subject to L  wi  U , i = 1..n
L λ m
By = 0, we have  λi = 1
Dmax i =1
m
Minimize   D (w )
i =1
i i

subject to L  wi  U , i = 1..n
42
Courtesy of Y.-W. Chang
 Lagrangian Relaxation

Lagrangian
Relaxation
Augmented
Weighted Lagrangian
Delay
SQP
TILOS
SLP
Sink Weights = Multipliers
Algorithmic Mathematical
approaches Programming

43
Courtesy of Y.-W. Chang
Lagrangian Relaxation Framework

Update Multipliers

Weighted Delay
Optimization

Converge? No

Yes
done
44
Courtesy of Y.-W. Chang
 Lagrangian Relaxation Framework

More Critical -> More Resource -> Larger Weight

D1

D2

1 2 1 2
Dmax
Dmax

D1 D2 D1 D2 45
Courtesy of Y.-W. Chang
 Weighted Minimization
․ Traverse the circuit in the topological order
․ Resize each component to minimize Lagrangian during
visit
Minimize 1D1 +2D2

w1
a D1

D2
b
w2 w3

46
Courtesy of Y.-W. Chang
Multiplier Adjustment: A Subgradient Approach

Step 1 : 
new
i =
old
i +  k ( Di − Dmax ),

where lim  k → 0,  k → 
k →
k =1

Step 2 : Project λ to the nearest feasible solution

․ Subgradient: An extension definition of gradient for
non-smooth functions.
․ Experience: Simple heuristic implementation can
achieve a very good convergence rate.

47
Courtesy of Y.-W. Chang
 Convergence Sequence
m
Minimize  i Di ( w )
i =1
Max Delay subject to L  wi  U , i = 1..n

Any Feasible Maximum Delay =

Upper Bound

Optimal Solution

Lagrangian = Lower Bound

Weighted Delay <= Maximum Delay

# Iterations
48
Courtesy of Y.-W. Chang
 Path Delay Formulation

d1
d2
Aa D1
Ab
d3
Ac D2

Aa + d1 + d 2  D1
Ab + d1 + d 2  D1 • Exponential growth
Ab + d1 + d 3  D2 • More accurate
• Can exclude false paths
Ac + d 3  D2

49
Courtesy of Y.-W. Chang
 Stage Delay Formulation

d1
Ae d2
Aa D1
Ab
d3
Ac D2
Aa + d1  Ae
Ab + d1  Ae
• Polynomial size
Ae + d 2  D1 • Less accurate
Ae + d 3  D2 • Contains false paths
Ac + d 3  D2

50
Courtesy of Y.-W. Chang
Both Multipliers Satisfy KCL (Flow Conservation)

Stage Based Path Based

41
43
4 31 1 
1 51
4
3
2 2
3 42
5 32 5
53
52
43 +53=31 +32 3,in =3,out


jinput ( i )
ji =  ik
koutput ( i )
i 
jinput ( i )
ji =  ik
koutput ( i )
i

51
Courtesy of Y.-W. Chang
 Appendix A:

Shih and Chang

“Fast timing-model independent clock-tree synthesis”
DAC-2010

52
Courtesy of Y.-W. Chang
 Introduction
․ Skew-minimized buffered clock-tree synthesis plays an
important role in VLSI designs for synchronous circuits
․ Due to the insufficient accuracy of timing models,
embedding simulation into synthesis becomes
inevitable
․ Runtime becomes prohibitively huge as design
complexity grows
merging timing vdd

? ?
timing vss

? insufficient accuracy time-consuming

solution?
53
Courtesy of Y.-W. Chang
 Symmetrical Structure
․ Skew is minimized by structural optimization
․ Buffering and wiring of all paths are almost the same
⎯ Is timing-model independent
⎯ Do not need simulation information

n4 (1,57) n4 snaking
n1 (12,26) n6 (33,29) n6
n2 n2 n1
(3,29)
n3 (33,19) n'3 (21,23)

n7 (33, 9) n7
n5 (5,1) n5
0ps skew (Elmore delay) 0ps skew (Elmore delay)
0.123ps skew (simulation) 0ps skew (simulation)

54
Courtesy of Y.-W. Chang
 Problem Formulation
․ Problem: Buffered Clock-Tree Synthesis (BCTS)

․ Instance
⎯ Given a set of clock sinks, a slew-rate constraint,
and a library of buffers

․ Question
⎯ Construct a buffered clock tree to minimize its skew,
subject to no slew-rate violation

55
Courtesy of Y.-W. Chang
 Symmetrical Clock Tree Synthesis
․ Specification
⎯ Number of branches, wirelength and inserted buffers are the
same at each level
․ Flow
Input
⎯ Assign specific branch numbers to
Branch-Number Planning each tree level
⎯ Cluster sub-trees level by level bottom-
Tree Construction up
⎯ Lengthen shorter connection by
snaking
Buffer Insertion
⎯ Insert identical buffers along trees
Output

56
Courtesy of Y.-W. Chang
 Branch-Number Planning
․ Observation
⎯ Total branch number of some level equals the number of
preceding level times its branch number
⎯ The multiplication sequence forms a factorization

prime
total number of primes

․ Planning
⎯ Branch-Number Plan (BNP) is arranged in non-increasing order

level-1 branch number

57
Courtesy of Y.-W. Chang
 Branch-Number Planning
․ Factorization may result in a big branch number,
implying a large fan-out size that could not be driven
․ Pseudo sinks are added to increase the total sink
number until all branch numbers are feasible
BNP = B(216) = < 3, 3, 3, 2, 2, 2 > BNP = B(212+4) = < 3, 3, 3, 2, 2, 2 >
branches branches
3 3
… 3 … 3
… 3 … 3
… 2 … 2
… 2 … 2
… 2 … … 2

sinks pseudo sinks

58
Courtesy of Y.-W. Chang
 Tree Construction
․ Achieve identical wirelength in this stage
⎯ Cluster sub-trees level by level bottom-up
⎯ Lengthen shorter connection by snaking
․ Flow
Partitioning ⎯ Divide sub-trees into desired clusters
⎯ Apply a common connection length to
Embedding-Region each cluster, and locate potential
Construction embedding positions to which snaked
wires can reach
N ⎯ Repeat the two stages till the
Root?
embedding region of the root is built
Y
⎯ Find exact physical locations for nodes
Node Embedding and route wires top-down

59
Courtesy of Y.-W. Chang
 Tilted Rectangular Region (TRR)
․ Represents potential embedding positions (embedding
region)
․ Is a 45- or 135-degree rectangular region
⎯core: a 45- or 135-degree line segment
⎯ radius: the Manhattan distances from the core to the region

boundaries
Configuration Operation Definition

extended TRR TRRi

core

Manhattan
distance

radius
extended
radius
TRRj
60
Courtesy of Y.-W. Chang
 Partitioning
․ The objective is to minimize cluster diameter
⎯ Cluster diameter: the maximum distance among sub-trees
within the same cluster
⎯ Maximum cluster diameter is the upper bound of the common
connection length
․ Sub-trees are divided recursively along the BNP in a
top-down manner
․ Non-binary tree can also be handled by this technique

maximum
cluster diameter

61
Courtesy of Y.-W. Chang
 Dividing: Cake Cutting
․ Borrow the idea of cake cutting, i.e., slicing a cake into
pieces from the center of the cake
․ Sort the polar angles of sub-trees relative to the
geometric center of the cluster
․ Apply dynamic programming to find the minimum cluster
diameter by restricting the dividing on this sorted order
Input Sinks Polar-Angles Sorting Divided Result

center point
cluster diameter
62
Courtesy of Y.-W. Chang
 Recursive Dividing
․ For i-th level partitioning along the given BNP
<b1, b2, …, bq>, dividing is performed recursively until
b1 x b2 x … x bi-1 clusters are derived
․ Desired cluster diameter could be obtained since global
sub-tree distribution is considered throughout the whole
process
Recursive Dividing Final Divided Result Corresponding Clusters

63
Courtesy of Y.-W. Chang
 Embedding-Region Construction
․ Assign the common connection length (CCL) as the half
length of the maximum cluster diameter
․ Extend the TRRs of children nodes and make
intersection to construct the embedding region of their
parents
Given Divided Result Region Extension/Intersection Resulting Regions

CCL CCL

embedding
region
64
Courtesy of Y.-W. Chang
 Node Embedding
․ Set the tree root as the closest position of the embedding
region w.r.t. the clock source
․ Propagate embedding information level by level top-down
․ Perform snaking to meet the uniform length, if necessary

Root Embedding Level-1 Embedding Level-2 Embedding

clock source

tree root level -1

level -2
CCL
CCL

the closest
position snaking

65
Courtesy of Y.-W. Chang
 Pseudo-Sink Handling
․ For partitioning
⎯ Relax the sizes of clusters in a partition which can
differ by at most one for the first recursion
․ For embedding-region construction
⎯ Construct no embedding regions for pseudo sinks to

reserve the flexibility of snaking

․ For node embedding
⎯ Let the embedding regions of pseudo sinks cover

entire chip
․ Dangling wires can be identified and attached to proper
sub-trees successfully

66
Courtesy of Y.-W. Chang
 Buffer Insertion
․ Align buffer distribution on the symmetrical tree
topology
․ Insert identical buffers level by level top-down

First-Time Insertion Second-Time Insertion Third-Time Insertion

67
Courtesy of Y.-W. Chang
 Experimental Results on IBM Benchmarks
․ Our approach can obtain much smaller skews in much
shorter runtime than the state of the art, with marginal
overheads of snaking for symmetry
Shih et al. Shih et al.
[ASPDAC’10] [ASPDAC’10] Ours
Circuit # sinks w/o simulation w/ simulation
skew usage runtime skew usage runtime skew usage runtime
(ps) (fF) (s) (ps) (fF) (s) (ps) (fF) (s)
r1 267 14.005 14001 2 5.012 15229 5126 1.510 13829 0.070
r2 598 16.012 28011 11 6.421 29234 7374 1.770 31056 0.280
r3 862 16.532 39123 26 5.611 41431 12739 2.310 44188 1.050
r4 1903 17.792 89312 165 5.418 91015 17871 2.540 98450 3.350
r5 3101 21.557 149875 498 7.028 156854 26045 3.010 171228 5.560
avg.
comparison
7.93 0.92 46.29 2.77 0.96 24343.13 1.00 1.00 1.00

More than 80000X faster than the ISPD-09 contest winners

(simulation-based methods)
68
Courtesy of Y.-W. Chang
Resulting Clock Tree: ispd09f22

69
Courtesy of Y.-W. Chang
 Appendix B:
Liu and Chang
“Floorplan and power/ground network co-synthesis
for fast design convergence”
ISPD-06 (TCAD-07)

A B

B
A

70
Courtesy of Y.-W. Chang
 Floorplan & P/G Network Co-Synthesis
․ Liu and Chang, “Floorplan and power/ground network
co-synthesis for fast design convergence,” ISPD-06
(TCAD-07).
․ Apply the B*-tree floorplan representation and
simulated annealing (SA)
․ Analyze the P/G network (typical flow)
⎯ Circuit modeling

⎯ Global P/G network construction

⎯ P/G network modeling/reduction

⎯ P/G network evaluation (IR-drop computation)

․ Reduce floorplan solution space

71
Courtesy of Y.-W. Chang
 Implementation of the Design Flow

Data preparation RTL code

․ Power profile Synopsys .Lib

Design Compiler
⎯ Power consumption data of the files

modules generated by Nestlist

PrimePower
․ Hierarchical circuit partition
Hierarchical Circuit
PrimePower
Partition

⎯ Organize the design into hard

Power Profile
modules and soft modules
Our Floorplanner
according to the hierarchy
Calculate Current Consumption
Post-layout verification Yes

․ AstroRail Astro Current Model &

Power Integrity
Constraints
⎯ Static cell-level P/G analysis
AstroRail

72
Courtesy of Y.-W. Chang
 Simulated Annealing Process
․ Non-zero probability for up-hill
Initialize B*-tree
climbing:  −

 and temperature T

p = min1, e T 

 
․ Perturbations (neighboring solutions) Pack B*-tree Perturb B*-tree

⎯ Op1: Rotate a block

Construct Update T
⎯ Op2: Move a node/block to P/G network
another place Update P/G
Evaluate cost Ψ pitch Dpitch
⎯ Op3: Swap two nodes/blocks

⎯ Op4: Resize a soft block N

Better ?
․ The cost function Ψ is based
Accept?
Y
on the floorplan cost and P/G Y N
Keep solution
network cost
Recover last
․ T is decreased every n cycles, solution
where n is proportional to the Cool/Good
enough? N
number of blocks
Y

73
Courtesy of Y.-W. Chang
 Cost Function
․ Cost function:
Wirelength Area P/G cost P/G Density
A
 =  W +   A +    +   2
,
․ W: Wirelength D pitch
․ A : Area
․ Φ : P/G network cost (penalty of power integrity violation)
․ Dpitch: pitch of P/G network
⎯ Increasing power mesh density (reducing D pitch) reduces Φ

ˆ
⎯ Update Dpitch by multiplying  / 
avg
⎯  avg : Average P/G network cost at a temperature

ˆ
⎯ ̂ : 0    1, a factor for adjusting the density of P/G networks

Smaller ̂ for higher P/G density and larger one for lower P/G
density

74
Courtesy of Y.-W. Chang
 Pitch Updating: An Example
․ At the beginning of SA, Dpitch = 2 and ˆ = 0.02
․ During SA process, D pitch   /  avg  D pitch
1000 4

100 3

ˆ /  avg 10
 Dpitch
2
Dpitch
ˆ /  avg

1 1

0.1 0
SA process
0.01 -1
1 0.1 0.01 0.001 0.0001 0.00001
Temperature
ˆ /  avg
 converges to 1 while temperature cools down
75
Courtesy of Y.-W. Chang
 P/G Network Cost
Φ: P/G network cost
EM cost IR-drop cost

 = 
Bem
+ (1 −  ) 
 pvi Pv
v pvi
, 0  1
B  PiP
Vlim, pi
․ Bem: set of branches violating electromigration constraints
․ B : total branches of the P/G mesh
․ vpvi: amount of the violation at the pin p vi
․ P : set of all P/G pins
․ Pv : set of violating P/G pins
․ Vlim,pi : IR-drop constraint of the P/G pin pi

76
Courtesy of Y.-W. Chang
 P/G Network Construction
․ For each floorplan, we construct a uniform global P/G
network according to Dpitch
․ The number of trunks is defined by
round[width/Dpitch]+1 & round[height/D pitch]+1

2X4 uniform P/G network is constructed

1+1 =2

Height
Floorplan
1

1 2 3 3+1 =4

Width
Calculate the P/G network dimension
77
Courtesy of Y.-W. Chang
 P/G Network Modeling
Apply static analysis for fast P/G network evaluation
․ Use resistive P/G Model
․ Model P/G pins by current sources
⎯ Current value: maximum current drawn from P/G pins
․ Reduce circuit size
⎯ Connect current sources to nearest global trunk nodes
Power pad Module Global trunk
node

Power
trunk

Power strap
Power pin
78
Courtesy of Y.-W. Chang
 P/G Network Modeling
Apply static analysis for fast P/G network evaluation
․ Use resistive P/G Model
․ Model P/G pins by current sources
⎯ Current value: maximum current drawn from P/G pins
․ Reduce circuit size
⎯ Connect current sources to nearest global trunk nodes
Power pad Module Reduced circuit

Power
trunk

Power strap
Power pin
Courtesy of Y.-W. Chang
79
 Macro Current Modeling
․ Divide the floorplan into regions
․ For hard macros
⎯ Connect P/G pins to the nearest global trunk nodes
․ For soft macros (worst-case scenario)
⎯ Collect the largest current drawn by standard cells in the
overlapping area of the region and the soft macro

Hard module
The border line of the region is
defined by the center of the global
trunk nodes

Soft module

d/2 d d/2

80
Courtesy of Y.-W. Chang
 Macro Current Modeling
․ Divide the floorplan into regions
․ For hard macros
⎯ Connect P/G pins to the nearest global trunk nodes
․ For soft macros (worst-case scenario)
⎯ Collect the largest current drawn by standard cells in the
overlapping area of the region and the soft macro
Assign current to the global
trunk nodes of the regions

Overlapping Area
d/2 d d/2

81
Courtesy of Y.-W. Chang
 Soft Macro Modeling
․ Derive the largest current drawn by standard cells of the
overlapping area
⎯ Maximize the current of the overlapping area
⎯ Constraint: total standard cell area < the overlapping area
⎯ The problem is known as 0-1 Knapsack Problem (NP-complete)
․ Approximate it by Fractional Knapsack Algorithm
⎯ Assume standard cells can be broken into arbitrary smaller pieces
⎯ Rank cells by current to area ratio
⎯ Apply a greedy algorithm (complexity O(n lg n))
Standard Cells of the soft module
1mA 1mA 3mA

1mA 1mA
Overlapping 5mA
Area 4mA
82
Courtesy of Y.-W. Chang
 Evaluation of P/G Network
․ The static analysis of a P/G network is formulated as
the following modified nodal analysis (MNA) formula:
Gx = i
⎯ G: conductance matrix (sparse positive definite matrix)
⎯ x: vector of node voltages
⎯ i: vector of current loads and voltage sources
⎯ Dimensions of G, i and x are equal to the number of nodes in
the P/G network
․ Solve the linear equation
⎯ Apply Preconditioned Conjugated Gradient (PCG) method
⎯ The time complexity is linear

83
Courtesy of Y.-W. Chang
 Idea of Solution Space Reduction
․ The IR-drop of a P/G pin is proportional to the effective
resistance between the P/G pin and the power pad
⎯ The closer the P/G pin is placed to the power pad, the smaller
the IR-drop
․ A technique to reduce solution space
⎯ Place the modules consuming larger current (power-hungry
modules) near the boundary of the floorplan
⎯ Place power pads close to them

10Ω 3.4V 1.9V 0.6V -0.4V 10Ω 3.4V 2.8V 2.5V 2.4V

5V 5V

10mA 20mA 30mA 100mA 100mA 30mA 20mA 10mA

84
Courtesy of Y.-W. Chang
 B*tree Boundary Properties
․ Bottom boundary modules: the leftmost branch
․ Left-boundary condition
⎯ Left boundary modules: the rightmost branch
․ Right-boundary condition
⎯ Right boundary modules: the bottom-left branch
․ Top-boundary condition
⎯ Top boundary modules: bottom-right branch
n0
leftmost rightmost
branch n1 n3 branch
m9
m7 m8 n2 n4 n7
m6
m4 n5 n8
m3 m5
bottom-left bottom-right
m0 m1 m2 branch n6 n9 branch

85
Courtesy of Y.-W. Chang
 Power-Hungry Modules Handling
․ Power-Hungry Modules
⎯ Are clustered and restricted to satisfy the boundary
property during B*-tree perturbation
⎯ P/G pads are placed near these modules
Clustered modules
Desired power pad locations n0

n1 n3
m9
m7 m8 n2 n4 n7
m6
m4 n5 n8
m3 m5
m0 m1 m2 n6 n9

Desired power pad locations

86
Courtesy of Y.-W. Chang
 Results on OpenRISC1200
․ Improve on runtime and max IR-drop with little overheads
on delay & wirelength (UMC 0.18 um technology)
Our
*Astro w/ Improv.
*Astro IR-drop Our
OpenRISC1200 vs.
Flow Driven Flow
Placement Astro w/
IR-drop
Die Area (mm2) 3.86 3.86 3.33 15.9%
Utilization (%) 62 62 72 13.9%
Wirelength (μm) 1655463 1539125 1540172 -0.1%
Avg. Delay (ns) 8.62 8.54 8.55 -0.1%
Max IR-drop (mv) 80.18 78.20 55.14 41.8%
CPU Runtime (s) 505 346 135 2.56X
Iterations 4 3 1 -
*Need iterative and manual P/G network fix
87
Courtesy of Y.-W. Chang
 Resulting Voltage Map
Astro design flow Our design flow
Power-hungry blocks (register files A&B) Power-hungry blocks are
are placed far away from the power pad placed beside the power pad

A B

88
Courtesy of Y.-W. Chang