Transcript VLSI קורס קווי חיבור

Modeling and Optimization of VLSI Interconnect
049031
Lecture 4: Interconnect modeling
Avinoam Kolodny
Konstantin Moiseev
1
Outline

Delay modeling – continuation


Elmore delay for general input
Model reduction. Asymptotic Waveform Evaluation.
 Moments calculation
 Two-pole model example


Transition time modeling





Delay metrics based on moments.
Central moments and their relation to moments
Representation of response as a probability distribution.
Alpert estimation for receiver slope. Slope expressions based on moments
Explicit output slope calculation for singe RC-stage
Driver-receiver interaction





Driver modeling. K-equations
Admittance and impedance calculations
Representation of load as “PI-model”.
Effective capacitance and algorithm for its calculation.
Two-step delay approximation
2
Asymptotic Waveform Evaluation
(AWE)
 Elmore delay uses first moment to represent system response

Not very accurate
 For more accurate estimation, more moments are required
 AWE uses moments matching to calculate parameters of low-order
model:
ˆ  bˆ s   bˆ s q 1
b
0
1
q 1
Hˆ  s  
1  aˆ1s   aˆq s q
where the reduced order q is much less than the original order n
 AWE flow:
Generate moments from the circuit
Match the first
2q moments to low-order q  pole model
Calculate residues
Obtain time-domain response by inverse Laplace transform
“Asymptotic waveform evaluation for timing analysis”, L. Pillage and R. Rohrer, 1990
3
Calculating moments
 How to calculate moments without knowing transfer function?
 From circuit theory:

RC-tree solution can be represented by:
G  sC X  E0
Conductance and capacitance matrices
 Represent:
 Then
Initial excitation vector
Node voltages (unknowns) vector
X  m0  m1s  m2 s2 
 G  sC   m 0  m1 s  m 2 s 2 
E
0
Matching coefficients
Gm 0  E0
Gm i  Cm i-1 , i  1
4
Calculating moments
Gm 0  E0
 First equation meaning:


Solve system for DC ( s  0 ) with the original
excitation
I.e. all capacitors are open-circuited and node
voltages are calculated
Gm i  Cm i-1 , i  1
G  sC X  E0
 Second equation meaning:

Solve system for DC ( s  0 ) with the original
excitation is set to zero, a new excitation Cmi-1 is
applied instead and node voltages are calculated
 I.e. moments are calculated recursively
For m0 calculation
For mi calculation
5
Moments calculation example
All caps are 1F
All resistances are 1Ω
Input voltage is 1V
Moment 0: all capacitances are open
circuited
m0  1 1 1 1 1
Moment 1: all capacitances are replaced by
current sources and input is grounded
m1  0 4 7 9 10
m2  0 30 56 75 85
m3  0 246 462 622 707
6
Example: two-pole approximation
 Assume we calcuated moments of the circuit:
H  s   m0  m1s  m2 s2 
 Transfer function for reduced model:
 Cross-multiply:
b0  b1s
H s 
1  a1s  a2 s 2
1  a s  a s  m
2
1
2
2

m
s

m
s

0
1
2
b
0
 b1s
 Coefficient match:
Build as many
equations as needed
to resolve all
unknowns
s0 :
b0  m0
s1 :
b1  a1  m1
s 2 : 0  a2  a1m1  m2
s 3 : 0  a2 m1  a1m2  m3
In this case only 4
moments are required
7
Example: two-pole approximation
All caps are 1F
All resistances are 1Ω
Input voltage is 1V
Moments at node 5 are: 1, -10, 85, -707, …
1  10s  85s
b0  1
b1  a1  10
0  a2  10a 1 85
0  10a2  85a1  707
2
 707 s 3 
1  a s  a s   b
2
1
2
0
 b1s
7
s
15
Hˆ  s  
143
31
1
s  s2
15
3
1
8
AWE pros and cons
 Allows simplification of the model


Pretty accurate
Reduced model representation in memory is compact
 No exact formula for roots of polynomial with degree higher than 4

Using numerical methods – computationally expensive
 Higher-order AWE approximations are often unstable


Meaning positive poles
Special methods are needed
9
Some delay expressions based on first
two moments
“An analytical delay model for RLC interconnects”, A.B.Kahng and S.Muddu, 1997

m1
1
2
td  m1  4m2  3m1 ln 1 

2
4m2  3m12



 two pole,
 two moments


“Accurate analytical delay model for VLSI interconnects”, A.B.Kahng and S.Muddu, 1995
td  2m2  m ln  2 
2
1
one pole,
matching second moments
instead of first
“RC delay metrics for performance optimization”, C.J. Alpert, A. Devgan and C.V. Kashyap, 2001
m12
td 
ln  2 
m2
“D2M metric”
pure empirical
10
Central moments
 Elmore was the first who made a comparison between voltage
derivative waveform and PDF
 Keeping this analogy higher-order waveshape terms can be
characterized by central moments
 Central moments of the impulse response are the moments about
the mean:


k    t    h  t  dt
k
0

0   h  t  dt  m0  1

 th  t  dt
0

 h  t  dt

m1
m0
0
0



0

0
0
1    t    h  t  dt   th  t  dt   h t  dt  m1  m0  m1  m1  0



m1
m12
m12
2    t    h  t  dt   t h  t  dt  2  th  t  dt    h  t  dt  2m2  2  m1   2 m0  2m2 
m0
m0
m0
0
0
0
0
2
2
2

6m1m2
m13
3    t  h  h  t  dt   6m3 
2 2
m
m0
0
0
3
11
Understanding central moments
 Zero moment 0 is the area under the
curve. Usually 1
 First moment 1 the mean deviation
around mean, thus it is 0
mode
median
mean
 Second moment 2 is the variance of
the distribution
 Third moment 3 is the skewness of
the distribution

Distribution is symmetric if
3  0
12
Some important properties
 Second and third central moments add under convolution, i.e. for
h t   h1 t  * h2 t 
holds that:
2  h   2  h1    2  h2 
3  h   3  h1   3  h2 

Second and third central moments are always positive
13
Elmore delay for general inputs
 The real input is not a step voltage
 It is modeled usually by saturated ramp

For saturated ramp:  vi ' t  dt  1;
0
2  vi ' t   
tr2
;
12
3  vi ' t    0
 Following results hold:
 For an RC circuit with monotonically increasing, piecewise-smooth
input vi  t  such that vi ' t  is a nonnegatively skewed unimodal
function, Mode  Median  Mean holds for the output response vo  t  at
any node.
 For an RC circuit with monotonically increasing, piecewise-smooth
input vi  t  such that vi ' t  is a symmetric function, then the Elmore
delay of the output response reaches 50% delay as the rise-time of
input signal reaches infinity.
 The area between input and output response equals Elmore delay.
14
Ramp follower
 When input signal transition time is large, transient response is
negligible
 Such kind of response is called ramp follower

In ramp follower, Elmore delay is almost exact delay metric
Real circuit example
15
Another example – lumped RC circuit
R
Vin  t 
C
Vout  t 
tr  0
tr  RC
tr  10RC
16
Transition time modeling
 Transition time: requires calculation of two points

Usually less accurate
 Recall:
 Again Elmore proposal…
Transition time is proportional to
second central moment!!
17
Slew rate for step input
 Assume step response modeled by single time constant:
y t   1  e

t
r
 Impulse response is therefore:
h t  
1
r

e
t
r
 Second central moment for this distribution is:

2    t   
0
2
1
r

e
t
r
dt   r2
 Now, match second central moment of model and actual circuit to
find  r :
 r2  2m2  m12
 r  2m2  m12
“A simple metric for slew rate of RC circuits based on two moments”, Agarwal, Sylvester, Blaauw, 2004
18
Slew rate for step input
 To find 10%-90% slew rate, substitute back to step response and
obtain:
S2M metric
t10%90%  ln 9 2m2  m12
 Works good for far-end nodes
 For near-end nodes single pole apporximation fails
 Better metric is found empirically:
t10%90% 
m1
4
m2
ln 9 2m2  m12
scaled S2M metric
From D2M
Example:
19
Extension for ramp inputs
 We know that for LTI system holds:
y t   x t  * h t 
 According to convolution property:
y ' t   x ' t  * h t 
 And since h  t   s ' t  , we can write:
y ' t   x ' t  * s ' t 
 We have:
s ' t 
x ' t 
y ' t 
is a PDF of step response
is a PDF of input waveform
is a PDF of output waveform
Recall:
second central moments are
added after convolution
of two PDFs !!!
“Closed form expressions for extending Step Delay and Slew Metrics to Ramp Inputs”, Kashyap, Liu, Alpert, Devgan, 2003
20
Extension for ramp inputs
 Therefore
2  y   2  x  2  s 
 2  y    2  x   2  s 
 Taking Elmore assumption that slew rate is proportional to standard
deviation:
tr  x   kx  x 
tr  y   k y  y 
 And therefore:
tr  s   ks  s 
 tr  y    tr  x    tr  s  

  
 

k
k
k
 y   x   s 
2
2
2
 Assuming all constants are equal we get:
tr 2  y   tr 2  x   t r 2  s 
21
Extension for ramp inputs
 We get:
tr  y   tr 2  x   t r 2  s 
 In other words, the output slew rate is the root-mean square of the
input signal slew and step response skew.
 Example: lumped RC circuit
Area 1
Area 2
for
t  0.3RC
Exact calculation gives
Vout  1 
RC
t
t
t  t

  RC
e
 e RC






t20%80%  1.38RC
Vout 
Using PERI:
t20%80% 
  t

1 
t  RC e RC  1 

t 


t
 0.6  0.3RC    RC ln 4  1.397 RC
2
2
22
Using PERI for delay estimation
 Using PERI, the following expression is obtained for 50% delay:
td (ramp)  1    TD  td (step)
where


2
2
m

m
2
1
 
2


t
 
2
2
m

m

 2
1

12







5
Elmore
2
If t   , then   0 and td  ramp   TD
23
Interacting with gate delay models
 Interconnect does not exist standalone
 Usually we want to calculate stage delay / slew rather than pure
interconnect delay / slew
output waveform
 The problem:


Interconnect is linear system
Gate is not !
stage
input waveform
 To model stage delay / slew
we need:


Develop simple and accurate
gate model
Be able to combine gate and
interconnect models without
loss of accuracy
24
Gate modeling
 How to model non-linear gate?
 First option – switch resistor model (i.e. linear model)
Rdr
Cin
Vdr
CL
 Advantage:

Is able to capture the interaction of the gate’s output resistance
and the RC load
 Disadvantages:


Requires calculating a single linear resistor that captures the
switching behavior of CMOS gate
Neglects effecy of the input transition time on delay
25
K-factor equations
 Model delay and output transition time as functions of capacitive
load and input transition time
k-factor equations

td  k  ttr in , CL 


ttr out  k '  ttr in , CL 
 For example:
td   k1  k2C L  ttr in  k3CL3  k4CL  k5
 All parameters are set empirically
Input waveform is modeled by
saturated ramp (single number)
26
Table-lookup model
 Empirical models usually do not scale well
 Preferred approach is pre-characterize each cell for bunch of input
transitions and output loads
 Exact value for specific inputs is found using interpolation
 This approach requires two two-dimensional tables (delay and
output slew) for each in-out cell transition
27
Two–step delay approximation
 For non-linear gate model the delay and slew at stage outputs is
calculated in two steps:
1. Given input slew and driver load, delay and slew at the gate output
are calculated from gate model (either empirical or table-based).
Gate output waveform is approximated by saturated ramp
2. The delay and the slew at the interconnect output are calculated
using interconnect model with given sturated ramp input
Should take into
account gate nonlinearity
Linear interconnect
model
28
Handling cell load
 Cell output is loaded by interconnect tree
 The characterization expects single load capacitance number
 For pure capacitive interconnect the characterization will work as is

Can use
Ctotal
as a load
 It will not work for resistive interconnect !!!
The solution: map complex load to single effective capacitance
Allows using table-lookup model
Ceff
Handles complex interconnect structure
29
Effective capacitance
C0  Ceff  Ctotal
30
Calculating Ceff
 Effective capacitance itself is calculated in two stages:


RC-tree is reduced to two-pole 
 model
Ceff is calculated iteratively by comparing average current drawn
from a source by   model and by single capacitance up to 50%
delay point
31
Representing RC load by
 model
 Recall from circuit theory:
 Input admittance is defined by Yin 
I in
Vin
 Input admittance represents “load” seen by external source
connected to the system input
 Admittance moments:
Yin  s   y0  y1s  y2 s2  y3s3 
32
Representing RC load by
 model
 On the other hand,   model admittance is given by:
s  C1  C2   s 2 RC1C2
Y  s  
1  sRC1
 Matching admittance moments we have:
 y0  0
C  C  y  y RC
 1
2
1
0
1

 RC1C2  y2  y1 RC1
 y3  y2 RC1  0
 Solving system obtain:
y22
C2  y1 
y3
y22
C1 
y3
y32
R 2
y3
33
Constructing Thevenin model
 Thevenin model (non-constant voltage source + resistance) is used
to model input waveform
34
Iterative Ceff calculation process
td  k  ttr in , Ceff 


ttr out  k '  ttr in , Ceff 
t0  f  td , t tr out , Ceff , Rd 


t  f '  ttr out , Ceff , Rd 
I avg  Ceff , t , t0 , Rd   I avg  , t , t0 , Rd 
35
Backup
36