Transcript Interconnect Layout Optimization Under Higher-Order

Lecture 12
Review and Sample Exam Questions
Professor Lei He
EE 201A, Spring 2004
http://eda.ee.ucla.edu
Partitioning and Clustering

Formulations: min-cut, min ratio cut, two-way partition and N-way
partitioning

Kernighan and Lin Algorithm

Fiduccia and Mattheyses Algorithm

Simulated annealing algorithm

Lawler’s Labeling Algorithm

Overview of multi-level partitioning
Floorplanning

Stockmeyer algorithm

Dynamic programming to decide optimal orientation for slicing
floorplanning (i.e., tree for slicing floorplanning is given)

Simulated annealing algorithm to find slicing
floorplanning

Name and explain at least one data structure for nonslicing floorplanning
Placement

Simulated Annealing



Partitioning-Based Placement





Capo [DAC-00]
Fengshui [DAC-2001]
Analytical Placement


Timberwolf package [JSSC-85, DAC-86]
Dragon (multi-level placement) [ICCAD-00]
Gordian (Multi-level placement) [TCAD-91]
FastPlace [ISPD-04]
Able to outline Pro’s and Con’s of all above algorithms
Able to outline at least two algorithms
Power and Thermal Modeling

Power Components




Dynamic power (f * s * C * Vdd**2)
• f: clock frequency
• S: switching possibility
Short circuit power
Leakage power = subthreshold + gate tunneling
Power trends



Relative significance between power components
Which one gains importance in scaled technology and future system
Design freedoms to reduce each power component with respect to
performance constraints
Power and Thermal Modeling

Duality between electrical and thermal


Thermal time constant is much bigger
Interdependency between leakage and temperature
Thermal quantity
Unit
Electrical quantity
Unit
P, Heat flow
W
I, Current flow
A
T, Temperature
K
V, Voltage
V
Rth, Thermal Resistance
K/W
R, Electrical resistance
Ω
Cth, Thermal capacitance
J/K
C, Electrical capacitance
F
τ=Rth*Cth,
Thermal RC constant
s
τ=R*C,
Electrical RC constant
s
Interconnect Modeling

Capacitance characteristics and table based capacitance
model


Inductance characteristics and table based inductance
model



Capacitance is a local effect
Inductance is a long-range effect
Partial inductance (PEEC) is independent of current return path
Full RCLM model and normalized RCLM model
Interconnect Delay Model

Elmore delay model and Elmore delay calculation for RC
tree

Definition of moments and overview of moment matching

Ceff model

Steps of delay analysis for a stage containing a driver and
interconnect tree
Circuit Tuning

TILOS algorithm
1.
2.
3.
4.

Explain why TILOS can achieve good solutions


Find critical path
Calculate sensitivity of each gate/transistor in the path
Size up the one with largest sensitivity
Goto step 1
Use the concept and property of posynomial program, convex program
Extend TILOS to consider power minimization via dual-Vdd, dualVt, dual-tox
Buffer and FF Insertion

Analytical solution to buffer insertion for two-pin net


Van Ginneken dynamic programming



Extend to find the FF insertion length for two-pin net *
Extend to consider buffer type, polarity
Extend to consider FF insertion*
Buffer block planning

Key ideas, pro’s and con’s
Noise Aware Routing

Design freedoms to alleviate capacitive and inductive
crosstalk

Figure of merit for crosstalk



LSK model
Shielding length
Multi-level routing
Emerging Technologies

Structured ASIC and 3D IC

Motivations and advantages

CAD implications

Sample questions:

How to expand partition/floorplan/placement/routing for 3D