Transcript No Slide Title

Introduction to Model Order Reduction
Luca Daniel
Massachusetts Institute of Technology
[email protected]
http://onigo.mit.edu/~dluca/2006PisaMOR
www.rle.mit.edu/cpg
1
Introduction to Model Order Reduction
I.1 – Examples, Motivations and
Introduction
Luca Daniel
Thanks to Kin Sou, Deepak Ramaswamy, Michal Rewienski, Jacob
White, Shihhsien Kuo and Karen Veroy
www.rle.mit.edu/cpg
Circuit Analysis
From www.maxim.com
• Equations
– Current-voltage relations for circuit elements (resistors, capacitors,
transistors, inductors), current balance equations
• Recent Developments
– Matrix-Implicit Krylov Subspace methods
Systems on Chip
C (v )
dv
 G (v)  Bvin
dt
 4u
 2u
 2u
EI 4  S 2  Felec   ( p  pa )dy   2
x
x
t
0
w
  ((1  6 K )u 3 pp)  12 
4
 ( pu )
t
Electromagnetic
Analysis of Packages
Thanks to
Microcosm inc.
now Coventor
• Equations
– Maxwell’s Partial Differential Equations
• Recent Developments
– Fast Solvers for Integral Formulations
Structural Analysis of
Automobiles
• Equations
– Force-displacement relationships for mechanical elements (plates, beams,
shells) and sum of forces = 0.
– Partial Differential Equations of Continuum Mechanics
• Recent Developments
– Meshless Methods, Iterative methods, Automatic Error Control
Drag Force Analysis
of Aircraft
• Equations
– Navier-Stokes Partial Differential Equations.
• Recent Developments
– Multigrid Methods for Unstructured Grids
Engine Thermal
Analysis
Picture from
www.adina.com
• Equations
– The Poisson Partial Differential Equation.
• Recent Developments
– Fast Integral Equation Solvers, Monte-Carlo Methods
Micromachine Device
Performance Analysis
From www.memscap.com
• Equations
– Elastomechanics, Electrostatics, Stokes Flow.
• Recent Developments
– Fast Integral Equation Solvers, Matrix-Implicit Multi-level Newton
Methods for coupled domain problems.
Structure Engineering
Example
Application Examples
Swaying Tacoma Bridge
• Periodic Input
– Wind
• Response
– Oscillating Platform
• Desired Info
– Oscillation Amplitude
• Equations
– Elastomechanics
• Recent Developments
– Fast Integral Equation Solvers
10
Stock Option Pricing for
Hedge Funds
Option Price
Stock Price
t
• Equations
– Black-Scholes Partial Differential Equation
• Recent Developments
– Financial Service Companies are hiring engineers, mathematicians and
physicists.
Virtual Environments
for Computer Games
• Equations
– Multibody Dynamics, elastic collision equations.
• Recent Developments
– Multirate integration methods, parallel simulation
Virtual Surgery
• Equations
– Partial Differential Equations of Elastomechanics
• Recent Developments
– Parallel Computing, Fast methods
Biomolecule Electrostatic
Optimization
+
- - +
+ +
+
++
- -
+
+
Ligand
(drug
molecule)
+
-+
Receptor
(protein
molecule)
Ecm protein
• Equations
– The Poisson Partial Differential Equation.
• Recent Developments
– Matrix-Implicit Iterative Methods, Fast Integral Equation Solvers
The Simulation and Modeling Scenario
Problem too complicated for hand analysis
Toss out some
Terms
“Macromodel”
Solve a
Simplified
Problem
No
Make
Sense?
Yes
Anxiety
Simulate using a canned routine, a friend’s
advice, or a recipe book
Works!
D
R
O
P
C
L
A
S
S
Way too slow
Use available
Model Order Reduction
(MOR) techniques
Faster simulation
or optimization
New MOR
Algorithms
Happiness
Fame
Course Outline
Numerical Simulation
Quick intro to PDE Solvers
Quick intro to ODE Solvers
Model Order reduction
Linear systems
Common engineering practice
Optimal techniques in terms of model accuracy
Efficient techniques in terms of time and memory
Non-Linear Systems
Parameterized Model Order Reduction
Linear Systems
Non-Linear Systems
Numerical Simulation
What do we want?
• accurate analysis (based on solution of PDE)
• relatively fast (hours, not days or months)
• Application: verification and characterization of
component properties
17
Analysis example: power micro-inductor
18
Analysis example: power micro-inductor
19
Analysis example: power micro-inductor
20
Analysis
Example: power micro-inductor
How is the magnetic
fringing field from the core
effecting eddy current
losses?
Rac
Spattered laminated NiFe core,
electroplated windings
[Daniel96]
frequency [Hz]
21
Motivation: analysis produces
impedance vs. frequency curves
But what is the effect of Z(f) on the
behavior of the attached circuit
blocks?
PCB, package, IC
interconnects
- +
+ D
Q
C
Z(f)
22
Motivation.
Example: RF micro-inductor
• How are the substrate eddy
currents affecting the quality
factor of the inductor?
• How are the displacement
currents affecting the
resonance of the inductor?
• Analysis tools can produce for
instance impedance vs.
frequency curves.
4
10
3
10
|Z(jw)|
2
10
Picture thanks to Univ. of Pisa
1
10
0
10
6
10
7
10
8
10
frequency
9
10
10
10
23
Analysis
Example: accelerometer and RF resonator
What is the
Drag force on
the fingers of a
resonator or
accelerometer?
How does it
affect the
quality factor?
Pictures generated by FastStokes (Thanks
to Xin Wang)
24
Analysis
Example: Micro-mirror
z - direction drag forces
Picture by Xin Wang
Picture thanks to Lucent
• What are the forces applied on the mirror, how do
they affect the dynamic response of the mirror?
25
Analysis
Issues and state of the art
• Need to use PDE’s describing physical
systems
• Need to handle computation with very large
matrices
• Some are sparse but often are very dense
matrices (depending on PDE solver)
26
Course Outline
Numerical Simulation
Quick intro to PDE Solvers
Quick intro to ODE Solvers
Model Order Reduction
Linear systems
common engineering practice
optimal techniques in terms of model accuracy
efficient techniques in terms of time and memory
Non-Linear Systems
Parameterized Model Order Reduction
Linear Systems
Non-Linear Systems
Model Order Reduction
Example: micro-inductor in a DC/DC power converter
Vin(t)
Vout(t)
• How is the frequency dependency of the power loss
in the inductor affecting the dynamics of the power
converter and its overall efficiency?
28
Model Order Reduction. Example:
Micro-inductor and resonator in an Wireless Transceiver
RF Receiver
ADC
I
LNA
ADC
LO
• How is the resonator performance
(noise, quality factor, etc) affecting
the transceiver performance
(distortion, interference rejection)?
29
Q
Model Order Reduction
Example: MEM Accelerometer in a system on chip
• How is the performance of the accelerometer
affecting the functionality of the overall system?
30
Model Order Reduction
Example: Micromirror switch in a Dense Wavelength Division
Multiplexing Optical Communication System
Emitters
Optical
Reconfigurable CrossOptical Dispersal
Connect
Add/drop
Amplifier Compensation
Module
Module
Multiplexer
WDM
Transmitters
WDM
Mux/Demux
WDM
Amplifier
Demultiplexer
WDM
Switching
Receivers
WDM
Receivers
Picture thanks to MEMSCAP S. A.
• How is the micromirror
performance affecting
the communication
system functionality?
31
Conventional Integrated Circuits Design Flow
Funct. Spec
RTL
Behav. Simul.
Logic Synth.
Stat. Wire Model
Front-end
Gate-level Net.
Gate-Lev. Sim.
Back-end
Floorplanning
Parasitic Extrac.
Place & Route
Layout
32
Layout parasitics
• Wires are not ideal.
Parasitics:
– Resistance
– Capacitance
– Inductance
• Why do we care?
– Impact on delay
– noise
– energy consumption
– power distribution
Picture from “Digital Integrated Circuits”,
Rabaey, Chandrakasan, Nikolic
33
Parasitic Extraction
thousands of wires
e.g. critical path
e.g. gnd/vdd grid
• identify some ports
• produce equivalent circuit that
models response of wires at
those ports
Parasitic
Extraction
tens of circuit
elements for
gate level spice
simulation
34
Parasitic Extraction (the two steps)
Electromagnetic
Analysis
thin volume
filaments
with constant
current
small surface
panels
with constant
charge
million of elements
Model Order
Reduction
tens of elements
35
Why building reduced models?
• Compression for Efficiency
– It is possible to represent the system under study
“precisely” with millions of elements (PDE solvers)
– But the simulation is too slow with the complicated
representation
• Abstraction
– I do not care at all about the precise representation
– In fact I would rather those details were not even there.
I may not be able to create or manipulate the precise
representation at all.
36
Traditional Approach to
Generating Models
Application
Examples
6 months…
Interconnect Expert
6 months…
MEMS Expert
dxr (t )
 F ( xr (t ))  bru(t )
dt
T
y (t )  cr xr (t )
Lucent
6 months…
Resonator Expert
Model for the
System Simulator
37
Modeling Approach #1: By Hand
• Analytic
Models
- Generate a set of mathematical equations
- Fit parameters to circumstances
• Good choice when
- System to be modeled is simple
- Static ; model does not have to be changed often
- Nothing else is available
38
Modeling Approach #2: Reduction
• Motivation : Complicated Structures
- Layout-dependent 3D effects
- Substrate Loss
- High-Order EM Modes
- Typical Example : Designed passives in RF circuits
• Can provide vastly superior performance when
internal system structure is available
39
The Numerical Macromodeling or Model
Reduction Paradigm
Generate a Reduced-Order Model Directly from
3-D Geometry and Physics
dxr (t )
 F ( xr (t ))  br u(t )
dt
y (t )  cr xr (t )
T
Complicated Geometry,
Coupled Electrostatics,
Fluids, Elastics
Cheap to evaluate model
which captures
input (u)/output(y)
behavior
40
From 3D geometry to small state space systems
Model Order Reduction (MOR)
dH
dt
dE
H  
dt
  E  


dx 

A
dt 


1M equations
Field solvers discretize
geometry and produce large
state space (ODE) systems

  

  

  
  x(t )   B  u (t )

  

  
 
  
MOR

•MOR produces a dynamical model:

–automatically
dxˆ 

dt

–with field solver accuracy

10 equations 
–small (10-15 ODEs)
41
Aˆ

  

  

  
  xˆ (t )   Bˆ  u (t )

  

  
 
  
Model Order Reduction
What do we want?
• accurate (based on solution of PDE)
• model construction relatively fast (hours, not
days or months)
• model evaluation in msec (e.g. get dynamical
response from any input)
• Application: analysis of functionality and
interaction with other components
42
Model Order Reduction
Issues and state of the art
• Model Order Reduction for simple linear systems is
well understood (e.g. interconnect, heat diffusion)
dx
 A x (t )  B u (t )
dt
y (t )  C x (t )
• But still ongoing research for time varying matrices
dx
 A(t ) x(t )  B u (t )
dt
y (t )  C x(t )
• Lots of practical systems are NON-LINEAR
dx
 F x (t )  B u (t )
dt
y (t )  C x (t )
– not many techniques yet
43
Course Outline
Numerical Simulation
Quick intro to PDE Solvers
Quick intro to ODE Solvers
Model Order reduction
Linear systems
common engineering practice
optimal techniques in terms of model accuracy
efficient techniques in terms of time and memory
Non-Linear Systems
Parameterized Model Order Reduction
Linear Systems
Non-Linear Systems
Parameterized Model Order Reduction
Example: micro-inductor in a DC/DC power converter
• How is the functionality and the efficiency of the
overall power converter changing when I change
wire widths and wire separations?
45
Parameterized Model Order Reduction. Example:
Micro-inductor and resonator in an Wireless Transceiver
RF Receiver
ADC
I
LNA
ADC
d
LO
W
• How is the transceiver performance
changing when I change wire
widths and wire separation?
46
Q
Parameterized Model Order Reduction
Example: MEM Accelerometer in a system on chip
• How is the performance of the overall system changing when I
change the fingers widths and separations?
47
Parameterized Model Order Reduction
Example: Micromirror switch in a Dense Wavelength Division
Multiplexing Optical Communication System
Emitters
Optical
Reconfigurable CrossOptical Dispersal
Connect
Add/drop
Amplifier Compensation
Module
Module
Multiplexer
WDM
Transmitters
WDM
Mux/Demux
WDM
Amplifier
Demultiplexer
WDM
Switching
Receivers
WDM
Receivers
Picture thanks to MEMSCAP S. A.
• How are is the
communication system
functionality chancing
when I change the
radius or thickness?
48
Parameterized Model Order Reduction
What do we want?
• accurate (based on solution of PDE)
• model construction relatively fast (hours, not days or
months)
• model evaluation in msec (e.g. get dynamical
response from any input)
• parameterized (get a different model for each
different combination of values of some design
parameters)
• Application: design optimization
49
Course Overview Summary
Numerical Simulation
Can only produce analysis “curves” (e.g. impedance)
Model Order Reduction
- produce small ODE models from PDE systems
- preserving PDE accuracy
Parameterized Model Order Reduction
- For fast Design Exploration
- and Optimization