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 RiversideOutlineOutlineBackgroundProblem FormulationRandom WalkMoment Computation in an RLC TreeSMM TheoryExperimentsConclusionP/G Supply Voltage Integrity AnalysisP/G Supply Voltage Integrity AnalysisIncreasing Power/Ground supply voltage degradation in latest technologiesIR drop (DC/AC)L dI/dt dropEffects: Malfunction Performance degradationP/G supply networks are special interconnectsComplex topology, numerous nodes, IOsScalability improvement schemesTop-down: multigrid-like, hierarchical, partitionBottom-up: random walkRandom WalkRandom WalkA stochastic process which gives voltage of a specific P/G nodeAdvantages:Localization Parallelism Limitations: DC analysisTransient analysisOur contribution: Frequency domain analysisOutlineOutlineBackgroundProblem FormulationRandom WalkMoment Computation in an RLC TreeSMM TheoryExperimentsConclusionProblem FormulationProblem FormulationGiven an RLC P/G supply networkpower padssupply current sources Find P/G node voltagesChallengesScalability AccuracyKirchoff’s current law:A random wanderer pays for lodging every night, and has a probability to go to a neighboring location, until he reaches homeA 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 sStart walking from a node sWhile (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  BVs = 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 TreeCurrent through Rpq charges all downstream capacitorsExpanding 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 momentsFor 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 TreeExpanding 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   ( , ) ( , )IqCqqA random walk processPr(p, q) transition probabilityA(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 StabilitiesCompute moments of all orders of a node based on the same random walk process See algorithmReduce number of random walks by reducing the number of node voltage moments neededMMM vs. SMMFiltering out numerically instable solutions Unvisited nodes, positive poles, etc.Take averageRuntimeRuntimeNumber of moments MAverage path length P (dominant)= average distance from the node to a power padIndependent to P/G network sizeNumber of poles/residues for moment matchingTime domain binary search for delayOutlineOutlineBackgroundProblem FormulationRandom WalkMoment Computation in an RLC TreeSMM TheoryExperimentsConclusionConvergenceConvergenceI. Solid curve: Random walk III. Dashed curve: Random walk IIIII. Dotted curve: Liebmann’s methodAccuracyAccuracyRandomly 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.0mA1000 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.94SummarySummaryWe extend random walk to frequency domain analysis by computing moments for RLC P/G networksMuch 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