Vector Potential Equivalent Circuit Based on PEEC Inversion

Slide1Vector Potential Equivalent CircuitBased on PEEC Inversion Vector Potential Equivalent Circuit Based on PEEC Inversion Hao  Yu  and  Lei  He Hao  Yu  and  Lei  He Electrical Engineering Department, UCLA http://eda.ee.ucla.edu Partially Sponsored by NSF Career Award (0093273) , and UC-Micro fund from Analog Devices, Intel and LSI Logic

Slide2OutlineOutline  Introduction  Vector Potential Equivalent Circuit Model  VPEC Property and Sparsification  Conclusions and Future Work

Slide3Interconnect Model Interconnect  Model Interconnect  Model Interconnect  Model    de facto  PEEC model is expensive   Total 3,278,080 elements for 128b bus with 20 segments per line   162M storage of SPICE netlist small  surface  panels small  surface  panels with  constant  charge with  constant  charge thin  volume  filaments thin  volume  filaments with  constant  current with  constant  current   Accurate model needs detailed discretization of conductors   Distributed RLC circuit has coupling inductance between any two segments

Slide4Challenge of  Inductance  Sparisification Challenge  of  Inductance  Sparisification Challenge  of  Inductance  Sparisification Challenge  of  Inductance  Sparisification  Existing passivity-guaranteed sparsification methods lack accuracy or theoretical justification  Returned-loop  [Shepard:TCAD’00]  Shift-truncation (shell)  [Krauter:ICCAD’95]  K-element  [Devgan:ICCAD’00]  Localized VPEC  [Pacelli:ICCAD’02]  Partial inductance matrix L is not diagonal dominant   Direct truncation results loss of passivity

Slide5K-Element MethodK-Element Method    K-method   Observe that the inversion of L is M-matrix  [Devgan:ICCAD’00]   Need to extend SPICE to simulate K-element [ Ji: DAC’01]    Windowing   Extract the K-elements of sub-matrices to avoid full inversion [Beattie: DATE’01]    Wire-duplication    Improve the accuracy of windowing method  [Zhong: ICCAD’02, DAC’03]    Inductwise   Heuristic bi-section the longest wire to guarantee K as M-matrix [Chen:ICCAD’02]

Slide6Contribution of Our PaperContribution of Our Paper  Prove that circuit matrix in VPEC model is strictly diagonal dominant and hence passive  Enable various passivity preserved sparsifications  Derive inversion based VPEC model from first principles  Replace inductances with effective magnetic resistances  Develop closed-form formula for effective resistances  Enable direct and faster simulation in SPICE

Slide7OutlineOutline  Introduction  Vector Potential Equivalent Circuit Model  VPEC Property and Sparsification  Conclusions and Future Work   VPEC circuit model   Inversion based VPEC   Accuracy comparison

Slide8Vector Potential  Equations  for  Inductive  Effect Vector  Potential  Equations  for  Inductive  Effect   Vector potential for filament  i ith Filament ith Filament   Integral equation for inductive effect Volume Integration Volume Integration Line Integration Line Integration

Slide9VPEC model for any two filamentsVPEC Circuit Model VPEC Circuit Model Effective Resistances

Slide10VPEC model for two filamentsVPEC Circuit Model VPEC Circuit Model Vector Potential Current Source

Slide11VPEC Circuit ModelVPEC Circuit Model VPEC model for two filaments Vector Potential Voltage Source

Slide12Recap of VPEC Circuit ModelRecap of VPEC Circuit Model  Inherit resistances and capacitances from PEEC    Inductances are modeled by:     Effective resistances    Controlled current/voltage sources   Unit self-inductance     Much fewer reactive elements     leads to faster SPICE simulation

Slide13Comparison with Localized VPECComparison with Localized VPEC  Our solution (1) It is not accurate to consider only adjacent filaments  Solution in localized VPEC   [Pacelli:ICCAD’02] (2) There is no efficient and closed-form formula solution to  calculate effective resistances

Slide14Introduction of G-ElementIntroduction of G-Element

Slide15Closed-form Formula for Effective ResistanceClosed-form Formula for Effective Resistance    Major computing effort is inversion of inductance matrix    LU/Cholesky factorization   GMRES/GCR iteration (with volume decomposition)    System equation based on G-element    System equation based on K-element i.e. Inversion Based VPEC Inversion Based VPEC

Slide16Interconnect Analysis Based on VPECInterconnect Analysis Based on VPEC 1. Calculate PEEC elements via either formula or FastHenry/FastCap 2. Invert L matrix 3.    Generate full VPEC including effective resistances, current and voltage sources. 4.    Sparsify full VPEC using numerical or geometrical truncations 5.     Directly simulate in SPICE PEEC (R,L,C) L^(-1) Full VPEC Sparsified VPEC SPICE Simulation

Slide17Spice Waveform ComparisonSpice Waveform Comparison Full PEEC vs. full VPEC vs. localized VPEC Full VPEC is as accurate as Full PEEC Localized VPEC model is not accurate

Slide18Spiral InductorSpiral Inductor Non-bus Structure: Three-turn single layer on-chip spiral inductor Full VPEC model is accurate and can be applied for general layout

Slide19OutlineOutline    Introduction   Vector Potential Equivalent Circuit Model    VPEC Property and Sparsification   Conclusions and Future Work

Slide20Property of  VPEC  Circuit  Matrix Property  of  VPEC  Circuit  Matrix Property  of  VPEC  Circuit  Matrix Property  of  VPEC  Circuit  Matrix Main Theorem     The circuit matrix     is strictly diagonal-dominant and positive-definite Corollary     The VPEC model is still passive after truncation Sketch proof:

Slide21Numerical SparsificationNumerical Sparsification Example: truncation of 5-bit bus with threshold 0.09  Drop off-diagonal elements with ratio below the threshold  Larger effective resistors are less sensitive to current change   Calculate the ratio between off-diagonal elements and the diagonal element of every row Given the full      matrix

Slide22Truncation ThresholdTruncation Threshold  Supply voltage is 1V  VPEC runtime includes the LU inversion  Full VPEC model is as accurate as full PEEC model but yet faster  Increased truncation ratio leads to reduced runtime and accuracy Models and Settings (threshold) No. of Elements Run-time (s) Average Volt. Diff. (V) Standard Dev. (V) Full PEEC 8256 281.02 0V 0V Full VPEC 8256 36.40 -1.64e-6V 3.41e-4V Truncated VPEC (5e-5) 7482 30.89 4.64e-6V 4.97e-4V Truncated VPEC (1e-4) 5392 19.55 1.29e-5V 1.37e-3V Truncated VPEC (5e-4) 2517 8.35 3.77e-4V 5.20e-3V 128-bit bus with one segment per line

Slide23Waveforms ComparisonWaveforms Comparison   Full VPEC is as accurate as full PEEC   Sparsified VPEC has high accuracy for up to 35.7% sparsification

Slide24Geometry Based  Sparsification  -  Windowed Geometry  Based  Sparsification  -  Windowed Geometry  Based  Sparsification  -  Windowed Geometry  Based  Sparsification  -  Windowed  Windowed VPEC  neighbor-window ( nix  ,  niy  ) for aligned coupling and forwarded coupling  consider only forward coupling of same wire For the geometry of aligned bus line

Slide25Geometry Based  Sparsification  -  Normalized Geometry  Based  Sparsification  -  Normalized Geometry  Based  Sparsification  -  Normalized Geometry  Based  Sparsification  -  Normalized         Normalized VPEC    normalized aligned coupling n: segments number

Slide26Geometrical Sparsification ResultsGeometrical Sparsification Results 32-bit bus with 8 segment per line    Decreased window size leads to reduced runtime and accuracy   Windowed VPEC has high accuracy for window size as small as  (16,2)   Normalized model is still efficient with bounded error Models and Settings No. of Elements Run Time (s) Avg. Volt. Diff. (V) Standard Dev. (V) Full PEEC 32896 2535.48 0 0 Full VPEC (32, 8) 32896 772.89 1.00e-5 6.26e-4 Windowed (32, 2) 11392 311.22 5.97e-5 1.84e-3 Windowed (16, 2) 3488 152.57 -1.23e-4 4.56e-3 Windowed (8, 2) 2240 85.14 -2.17e-4 8.91e-3 Normalized 4224 255.36 -6.05e-4 2.96e-3

Slide27Runtime ScalingRuntime Scaling  Circuit: one segment per line for buses  The runtime grows much faster for full PEEC than for full VPEC  full PEEC is 47x faster  for  256-bit bus due to reduced number of reactive elements  Sparsified VPEC reduces runtime by 1000x with bounded error for large scale interconnects

Slide28Conclusions and Future WorkConclusions and Future Work  Derived inversion based VPEC from first principle  Shown that Full VPEC has the same accuracy as full PEEC but faster  Proved that VPEC model remains passive after truncation    To work on  Fast iteration algorithms for inversion of L  Model-order-reduction for VPEC   (see ICCAD’2006)