**Unformatted text preview:**

SMM: Scalable Analysis of Power Delivery Networks by Stochastic Moment MatchingOutlineP/G Supply Voltage Integrity AnalysisRandom WalkSlide 5Problem FormulationSlide 7Random Walk in a Resistive NetworkMoment Computation in an RLC TreeSlide 10Stochastic Moment Matching (SMM)Slide 12SMM AlgorithmNumerical StabilitiesRuntimeSlide 16ConvergenceAccuracyScalabilitySMM vs. Transient Random WalkSummaryThank you !SMM: Scalable Analysis of Power Delivery Networks by Stochastic Moment MatchingSMM: Scalable Analysis of Power Delivery Networks by Stochastic Moment Matching Andrew B. Kahng, Bao Liu, Sheldon X.-D. Tan*UC San Diego, *UC RiversideOutlineOutlineBackgroundProblem FormulationRandom WalkMoment Computation in an RLC TreeSMM TheoryExperimentsConclusionP/G Supply Voltage Integrity AnalysisP/G Supply Voltage Integrity AnalysisIncreasing Power/Ground supply voltage degradation in latest technologiesIR drop (DC/AC)L dI/dt dropEffects: Malfunction Performance degradationP/G supply networks are special interconnectsComplex topology, numerous nodes, IOsScalability improvement schemesTop-down: multigrid-like, hierarchical, partitionBottom-up: random walkRandom WalkRandom WalkA stochastic process which gives voltage of a specific P/G nodeAdvantages:Localization Parallelism Limitations: DC analysisTransient analysisOur contribution: Frequency domain analysisOutlineOutlineBackgroundProblem FormulationRandom WalkMoment Computation in an RLC TreeSMM TheoryExperimentsConclusionProblem FormulationProblem FormulationGiven an RLC P/G supply networkpower padssupply current sources Find P/G node voltagesChallengesScalability AccuracyKirchoff’s current law:A random wanderer pays for lodging every night, and has a probability to go to a neighboring location, until he reaches homeA Monte Carlo method to a boundary value problem of partial differential equationsRandom WalkRandom WalkI G V VVG V IGq p q p qp q Eqp q pp q Eqp qp q E ( )( , )( , )( , )IqInput: resistive network N, nodes B with known voltages Output: voltage of node sStart walking from a node sWhile (not reaching a node b B) Pay A(q) at node q Walk to an adjacent node p with Pr(p, q)Gain Vb the voltage of the boundary node b BVs = net gain of the walk Random Walk in a Resistive NetworkRandom Walk in a Resistive NetworkMoment Computation in an RLC TreeMoment Computation in an RLC TreeCurrent through Rpq charges all downstream capacitorsExpanding the voltages in momentsV V R s C VM q M p R C m kq p p q k kk T pi i p q k ik T p ( ) ( ) ( )1pqRpqInput: RLC tree T, input nodes voltage momentsOutput: Output node voltage momentsFor each moment order j Depth-first traversal of the tree T In pre-order, compute mi-1(p) for each node p In post-order, compute Sk Tp Ck mi-1(k) for each Tp Moment Computation in an RLC TreeMoment Computation in an RLC TreeExpanding moment computation in a tree to a general structure networkStochastic Moment Matching (SMM)Stochastic Moment Matching (SMM)VR s LVR s Ls C V Iqp q p qp q Epp q p qp q Eq q q ( , ) ( , )IqCqqA random walk processPr(p, q) transition probabilityA(q) lodging costStochastic Moment Matching (SMM)Stochastic Moment Matching (SMM)m q p q m p A qp qGGA qC m q m IGj jp qp qp q Eq j j qp qp q E( ) P r ( , ) ( ) ( )P r ( , )( )( ) ( )( , )( , ) 1Input: RLC P/G network N, nodes B with known voltages, current sources SOutput: P/G node voltages1. For each current source s S2. Walk from s to a power pad with Pr(p, q)3. For each node q in the path4. For each moment order j5. Compute mj(q) 6. Collect node moments7. Compute poles and residues by moment matching 8. Output time domain waveforms and voltage drops SMM AlgorithmSMM AlgorithmNumerical StabilitiesNumerical StabilitiesCompute moments of all orders of a node based on the same random walk process See algorithmReduce number of random walks by reducing the number of node voltage moments neededMMM vs. SMMFiltering out numerically instable solutions Unvisited nodes, positive poles, etc.Take averageRuntimeRuntimeNumber of moments MAverage path length P (dominant)= average distance from the node to a power padIndependent to P/G network sizeNumber of poles/residues for moment matchingTime domain binary search for delayOutlineOutlineBackgroundProblem FormulationRandom WalkMoment Computation in an RLC TreeSMM TheoryExperimentsConclusionConvergenceConvergenceI. Solid curve: Random walk III. Dashed curve: Random walk IIIII. Dotted curve: Liebmann’s methodAccuracyAccuracyRandomly generated 100x100 power mesh of R=100W~1KW, C=0.1pF~1.0pF, L=0.1pH~1.0pH, Tr=0.5ns~2.5ns, Ip=0.5mA~2.0mA1000 random walks vs. SPICEScalability Scalability Power mesh of R=1KW, C=1pF, Tr=1ns, Ip=1mAN/G 1 2 3 4CPU Vdop CPU Vdrop CPU Vdrop CPU Vdrop10 0.14 0.04 0.07 1.09 0.04 1.10 0.04 1.1220 0.48 0.95 0.21 1.04 0.09 1.10 0.06 1.1150 5.54 0.85 1.86 0.98 0.44 1.03 0.26 1.03100 23.08 0.91 7.79 0.93 1.97 0.97 1.15 1.02SMM vs. Transient Random Walk SMM vs. Transient Random Walk I. SMM: 100 random walksII. TRW: 100 random walks for each time step, each of 5ps1 2 3 4 5 6 7I CPU 12.8 7.3 9.5 12.8 4.4 4.6 6.9Vdrop 1.05 0.97 0.94 1.04 0.97 0.96 1.03II CPU 142.1 141.5 139.3 135.0 192.6 107.6 100.3Vdrop 1.12 1.15 1.09 1.21 1.32 1.09 0.94SummarySummaryWe extend random walk to frequency domain analysis by computing moments for RLC P/G networksMuch better efficiency/accuracy than transient analysis random walk Advantages of random walk: locality, runtime which depends on average distance to a power pad, parallelism More stable moment computation in a bunch of stochastic processesThank you !Thank you