Transcript Slide 1
Process Variation Aware
Clock Tree Routing
Bing Lu
Jiang Hu
Gary Ellis
Haihua Su
Cadence
Texas A&M Univ
IBM Corp
IBM Corp
ISPD'03
1
Outline
•
•
•
•
•
•
•
Introduction
Previous work
Problem formulation
Minimum skew violation clock tree
Experimental results
Extension to bounded skew clock tree
Conclusion
ISPD'03
2
Process Variation
Gate length
Etching
errors
Spot
defects
tox
Junction
depth
T
W
S
Gate width
Mask
misalignment
H
Ground plane
ISPD'03
3
Impact to Clock Skew
• 20-30% variation on clock skew, mostly
due to clock buffers
( Zanella, et al., TCAD 12/2000 )
• Interconnect variations may cause up to
25% variation on clock skew
( Y. Liu, et al., DAC 2000 )
• Undesired skew bottleneck of clock
frequency
ISPD'03
4
Outline
•
•
•
•
•
•
•
Introduction
Previous work
Problem formulation
Minimum skew violation clock tree
Experimental results
Extension to bounded skew clock tree
Conclusion
ISPD'03
5
Previous Work
• Buffer insertion/sizing
[Chung and Cheng, ICCAD 94]
[Xi and Dai, DAC 95]
• Wire sizing [Pullela, Menezes and Pillage, DAC 93]
• Non-tree topology
[Lin and Wong, ICCAD 94]
[Su and Sapatneker, ICCAD 01]
• Abstract topology
[Velenis, Friedman and Papaefthymiou, ISCAS 01]
ISPD'03
6
Focus on Clock Tree Routing
• Interconnect variation is significantly
important
• Unlike transistors, worst case skew from
interconnect variation is not at corner
points
• Result can be applied as a sub-network in
buffered/non-tree clock network
ISPD'03
7
Wire Width Variation Model
Wl
Wu
Ws
-3 -2 -1 +1 +2 +3
68.26%
95.44%
99.74%
ISPD'03
Wire width: w = Ws +
Ws = W0 + • x + • y
Lower limit: Wl = Ws - 3
Upper limit: Wu = Ws + 3
: standard deviation
= = 3 dmax
dmax max dist between sinks
8
Outline
•
•
•
•
•
•
•
Introduction
Previous work
Problem formulation
Minimum skew violation clock tree
Experimental results
Extension to bounded skew clock tree
Conclusion
ISPD'03
9
Problem Formulation
• Permissible range for sink si and sj
[ LPRij, UPRij ]
• Skew violation
max ( LPRij – skewij, skewij – UPRij )
• Minimizing Skew Violation ( MinSV ):
Given a set of clock sinks { s1, s2, …, sn }, skew
permissible ranges for all pairs of sinks, [Wl, Wu], find
a clock routing tree such that the max skew violation
among all sink pairs is minimized
ISPD'03
10
Assumptions
• Elmore delay model
• Given abstract topology
ISPD'03
11
Outline
•
•
•
•
•
•
•
Introduction
Previous work
Problem formulation
Minimum skew violation clock tree
Experimental results
Extension to bounded skew clock tree
Conclusion
ISPD'03
12
DME Based Framework
• Deferred Merge Embedding (DME)
– Bottom-up, find merging segments
– Top-down, find locations for internal nodes
ISPD'03
13
Find Merging Locations
• For particular z value
– Skew range [ skew ij, min, skew ij, max ]
• z , range shifts to greater values
• z , range shifts to smaller values
• Adjust z such that
center of skew range is aligned to
center of permissible range
• In DME, adjust z such that
skew ij = 0
Dij
z
ni
nj
n
si
ISPD'03
sj
14
Align Skew Range
Skew range
z=0
Dij
Skew range
z = Dij
z
ni
nj
n
si
Permissible
range
sj
ISPD'03
15
When Snaking Necessary
Skew range
z=0
Skew range
z = Dij
Skew range
z=0
Skew range
z = Dij
Permissible
range
Permissible
range
Dij
n
ni
si
Dij
nj
n
nj
ni
sj
si
ISPD'03
sj
16
Worst Case Skew Estimation
• skew ij,min = t i,min – t j,max
• skew ij,max = t i,max – t j,min
• Need to estimate min and max delay to a
sink under process variation
ISPD'03
17
Worst Case Delay Estimation:
Single Sink
l
w
•
•
•
•
•
Wire capacitance clw
Wire resistance rl/w
t = rcl2/2 + rl C/w
tmin = rcl2/2 + rl C/WU
tmax = rcl2/2 + rl C/WL
ISPD'03
C
18
Worst Case Delay Estimation:
Multiple Sinks
sk
np
si
• t pi,min
sj
– Width of path np -> si is WU
– Width of wires not on np->si is WL
• t pi,max
– Width of path np -> si is WL
– Width of wires not on np->si is WU
ISPD'03
19
How to Choose Sink Pair
• How to choose si in left subtree and sj in right
subtree?
• Ideally, need to evaluate all sink pairs between
left and right subtree
– Greatly increase computation cost
• Heuristic: pick the most critical pair
Criticalityij = dij dmax + PRmin PRij
dmax: max sink pair distance
PRmin: min permissible range
ni
n
si
ISPD'03
nj
sj
20
Outline
•
•
•
•
•
•
•
Introduction
Previous work
Problem formulation
Minimum skew violation clock tree
Experimental results
Extension to bounded skew clock tree
Conclusion
ISPD'03
21
Experiments
• Benchmark circuits r1-r5
• SUN Blade-100 workstation, 512M memory
• Compare with extended DME
– Align nominal skew to center of permissible range
• S: permissible range LPR, UPR symmetric wrt 0
• NS: LPR, UPR asymmetric wrt 0
ISPD'03
22
Number of Skew Violations
1200
1000
800
600
DME
MinSV
400
200
0
r1-S r1- r2-S r2- r3-S r3- r4-S r4- r5-S r5NS
NS
NS
NS
NS
ISPD'03
23
Maximum Skew Violation
1600
1400
1200
1000
800
DME
MinSV
600
400
200
0
r1-S r1- r2-S r2- r3-S r3- r4-S r4- r5-S r5NS
NS
NS
NS
NS
ISPD'03
24
Outline
•
•
•
•
•
•
•
Introduction
Previous work
Problem formulation
Minimum skew violation clock tree
Experimental results
Extension to bounded skew clock tree
Conclusion
ISPD'03
25
Pair-wise Bounded Skew Routing
• Minimizing Wirelength s.t. Skew Constraints:
Given a set of clock sinks { s1, s2, …, sn }, skew permissible ranges
for all pairs of sinks, find a clock routing tree such that the total
wirelength is minimized while all permissible range are satisfied
• Find merging regions instead of merging segments
• Similar to Bounded Skew Clock Routing
[Cong, et al., ACM TODAES 98]
• Pair-wise skew permissible range vs. global skew bound
• More wirelength reduction
ISPD'03
26
Outline
•
•
•
•
•
•
•
Introduction
Previous work
Problem formulation
Minimum skew violation clock tree
Experimental results
Extension to bounded skew clock tree
Conclusion
ISPD'03
27
Conclusion
• Wire width variation needs to be
considered in clock tree routing
• Worst delay variation can be estimated
given the wire width variation range
• Our MinSV method significantly improves
tolerance to wire width variation
• Our method can be extended to pair-wise
bounded skew routing to further reduce
the total wire length
ISPD'03
28
Thank you!
ISPD'03
29