Transcript ppt

EE 201A
(Starting 2005, called EE 201B)
Modeling and Optimization
for VLSI Layout
UCLA
Instructor:
Lei He
Email:
[email protected]
DAC Tutorial 1997
Chapter 9
 Transistor/gate
sizing *
 Buffer Insertion
* Part of slides is provided by Prof. Sapatnekar from U. of
Minnesota.
Transistor/Gate Sizing Optimization

Given:
Find:



Logic network with or without cell library
Optimal size for each transistor/gate to minimize
area or power, both under delay constraint
Static sizing: based on timing analysis and consider all paths at once
[Fishburn-Dunlop, ICCAD’85][Sapatnekar et al., TCAD’93]
[Berkelaar-Jess, EDAC’90][Chen-Onodera-Tamaru, ICCAD’95]
Dynamic sizing: based on timing simulation and consider paths
activated by given patterns [Conn et al., ICCAD’96]
Transistor sizing versus gate sizing
The Transistor Sizing Problem
Problem statement
minimize Area(x)
subject to Delay(x)  Tspec
Comb.
Logic
or
minimize Power(x)
subject to Delay(x)  Tspec
Mathematical Background

n - dimensional space



Any ordered n-tuple x = (x1, x2, ... , xn) can be thought of as a
point in an n-dimensional space
f(x1,x2, ..., xn) is a function on the n-dimensional space
Convex functions
f(x) is a convex function if given
any two points x a and x b, the
line joining the two points lies
on or above the function
f(x)
xa
xb
x
f(x)
Nonconvex f:
xa
xb x
Math Background (Contd.)

Convex functions in two dimensions
f(x1,x2) = x12 + x22
Formally, f(x) is convex if
f( xa + [1 - ] xb)   f(xa) + [1 - ] f(xb)
0   1
Math Background (Contd.)

Convex sets
A set S is a convex set if given any two points xa and xb in the set, the
line joining the two points lies entirely within the set

Examples
Shape of
Wyoming

Shape of a
pizza
Nonconvex Sets
Shape of CA
Silhouette of
the Taj Mahal
Math Background (Contd.)

Mathematical characterization of a convex set S

If x1, x2 S, then
 x1 + (1 - ) x2 S, for 0   1
x2
x1
If f(x) is a convex function, f(x)  c is a convex set
 An intersection of convex sets is a convex set

Math Background (Contd.)

Convex programming problem
minimize convex function f(x)
such that [fi(x)  ci]

Global minimum value is unique!
(Nonrigorous) explanation
(from “The Handwaver’s Guide
to the Galaxy”)
f(x)
xa
xb
x
Math Background (Contd. in English)

A posynomial is like a polynomial except



all coefficients are positive
exponents could be real numbers (positive or negative)
Are these posynomials?
6.023 x11.23 + 4.56 x13.4 x27.89 x3-0.12
YES
x1 - 9.78 x24.2 x3-9.1
NO
(x1 + 2 x2 + 2 x3 + 5)/x1 + (x3 + 2 x4 + 3)/x3 YES
Math Background (Contd.)

In any posynomial function f(x1, x2, ... , xn),
substitute
xi = exp(zi)
to get F(z1, z2, ... , zn)

Then F(z1, z2, ... , zn) = convex function in (z1,... , zn) !
minimize (posynomial objective in xi’s)
s.t. (posynomial function in xi’s)i  K for 1  i  m
[xi = exp(zi)]
minimize (convex objective)
over a convex set
Therefore, any local minimum is a global minimum!
Properties of Tr. Sizing under the Elmore
Model

x is the set (vector) of transistor sizes
minimize Area(x) subject to Delay(x)  Tspec

Area(x) =  i = 1 to n x i

Each path delay =  R C



(posynomial!)
R  xi-1, C  xi posynomial path delay function
Delay(x)  Tspec
Pathdelay(x)  Tspec for all paths
Therefore, problem has a unique global min. value
TILOS™ (TImed LOgic Synthesis)

Philosophy

Since min. value is unique, a simple method should find it!

Problem
minimize Area(x) subject to Delay(x)  Tspec
 Strategy



Set all transistors in the circuit to minimum size
Find the critical path (largest delay path)
Reduce delay of critical path, but with a minimal increase in the
objective function value
(TILOS™ is a registered trademark of Lucent Technologies)
TILOS (Contd.)
minimize Area(x) subject to Delay(x)  Tspec
 Find D/A for all transistors on critical path
 Bump up the size of transistor with the largest D/A
x i  M x i + a (default: M = 1; a = 1 contact head width)
IN
OUT
Critical Path
Circuit
Sensitivity Computation
Rprev
C
w
“1”

D(w) = K + Rprev (Cu . w)
+ Ru . C / w

D/w = Rprev . Cu - Ru . C / w2

Could minimize path delay by setting
derivative to zero
 Problem: may cause another path
delay to become very high!
Why Isn’t This THE Perfect Solution?

Problems with interacting paths
B
C
A
D
(1) Better to size A than to size all
of B, C and D
(2) If X-E is near-critical and A-D is
critical, size A (not D)
E
X

False paths, layout considerations not incorporated
 AND YET..



TILOS (the commercial tool) gives good solutions
It has handled circuits with 250K transistors
It has linear time performance with increasing circuit size
CONTRAST

Solves the convex optimization problem exactly
 Uses an interior point method that is guaranteed to find the
optimal solution
Delay spec.
satisfied
Optimal solution

Can handle circuits with about a thousand transistors
(Convex) Polytopes

Polytope = n-dimensional convex polygon


Half-space:
aT x  b
(aT x = b is a hyperplane)
e.g. a1 x1 + a2 x2  b
(in two dimensions)
Polytope = intersection of half-spaces, i.e.,
a1T x  b1
AND a2T x  b 2
AND amT x  bm
Represented as A x  b
Convex Optimization Algorithm
(Vaidya)
(1) Enclose solution within a polytope (invariant)

Typically, take a “box” represented by
wi  wMAX and wi  wMIN
as the starting polytope.
(2) Find center of polytope, wc
(3) Does wc satisfy constraints (timing specs)?

Take transistor widths corresponding to wc and perform a static
timing analysis
(4) Add a hyperplane through the center so that the solution
lies entirely in one half-space

Hyperplane equation depends on feasibility of wc
Equation of the New Half-Space
Half-space:

f (wc) . w  f (wc) . wc
If wc is feasible
then f = objective function
Find gradient of area function

If wc is infeasible
then f = violated constraint
Find gradient of critical path delay
wc
Illustrative Example
w2
w1
S
S
f (w) = c, f decreasing
solution
S
S
Calculating the Polytope Center

Finding exact centroid is computationally expensive
 Estimate center by minimizing log-barrier function
F(x) = - i=1 to m log (aiT x - bi)
Happy “coincidence”:
F(x) is a convex function!

Physical meaning:
maximize product of perpendicular
distances to each hyperplane
that defines the polytope
Linear Programming Methods

LP-based approaches

Delay
Model gate delay as a piecewise linear function
Parameters:
• transistor widths wn , wp
• fanout transistor widths
• input transition time
wn


Formulate problem as a linear program (LP)
Use an efficient simplex package to solve LP
Power-Delay Sizing
minimize Power(w)
subject to Delay(w)  Tspec
Area  Aspec
Each gate size  Minsize
Power = dynamic power +
short-circuit power
Dynamic Power

POST-IT
Dynamic Power

Power required to charge/discharge capacitances
Pdynamic = CL Vdd2 f pT
CL = load capacitance, f = clock frequency, pT = transition probability



Posynomial function in w’s (if pT constant)
Constitutes dominant part of power in a well-designed circuit
Minimize dynamic power  minimize CL
 minimize all transistor sizes!
RIGHT? (Unfortunately not!)
Short-Circuit Power

POST-IT
Short-circuit Power


Power dissipated when a direct Vdd-ground path exists
Approximate formula by Veendrick (many assumptions)
Pshort-ckt = Vdd -2VT)2f pT
 = transconductance,= transition time




Posynomial function in w’s (if pT const)
Other (more accurate) models: table lookup, curve-fitting
“Less than 10-20% of total power in a well-designed circuit”
So what’s the catch?
The Catch

Delay of gate A is large

B
C
A
X

D
E

F
G
H


Therefore, the value of for B,
C, ... , H is large
Therefore short-circuit power for
B, C, ... , H is large
Can be reduced by reducing the
delay of A
In other words, size A!
Tradeoff dynamic and
short-circuit power!
 Minpower  minsize
Solution Technique
begin
Calculate pT's ‘for minsized gates
error < ?
Yes
end
No
Solve gate sizing problem for current pT
Calculate pT's for new sizes
error = ||old pT - new pT ||
Problem: inaccuracies in short-ckt. power model
Transistor/Gate Sizing
[Borah-Owens-Irwin, ISLPD’95, TCAD’96]
n
n
i 1
i 1
P  V  (c W  f   CLi  fi )  k  (  in W  f     Wi  fi )
2
dd
  W 

W

Optimal transistor size
O ( p )  n  (i 1Wi ( n )  CI )  (i 1Wi ( n ))
n
W p* 
n
p  
O (n)  p  (i 1Wi ( p )  CI )  (i 1Wi ( p ))
n
Wn* 
CI = int. cap
n
n  
Power Optimal Sizes and
Corresponding Power Savings
Power-Delay Optimization
Power, Delay and Power-Delay Curves
Power-Delay Optimal Transistor
Sizing Algorithm

Power-Optimal initial sizing
 Timing analysis
 While exists path-delay > target-delay




Power-delay optimal sizing critical path
if path-delay > target-delay
 upsize transistor with minimum power-delay slope
if path-delay < target-delay
 downsize transistor with minimum power-delay
slope
Incremental timing analysis
Effect of Transistor Sizing