TY - GEN
T1 - Incremental and on-demand random walk for iterative power distribution network analysis
AU - Shit, Yiyu
AU - Yao, Wei
AU - Xiong, Jinjun
AU - He, Lei
PY - 2009
Y1 - 2009
N2 - Power distribution networks (PDNs) are designed and analyzed iteratively. Random walk is among the most efficient methods for PDN analysis. We develop in this paper an incremental and on-demand random walk to reduce iterative analysis time. During each iteration, we map the design changes as positive or negative random walks for observed nodes. To update PDN analysis result, we only need to apply these extra positive or negative walks, instead of doing all walks from scratch. We show that different execution orders for these walks do not affect accuracy but do affect the runtime because of the cancellation between positive and negative walks. Considering this cancellation effect, we optimize the walk order by solving a min-energy electromagnetic particles placement problem and, as a result, further reduce the runtime to about 8× compared to the worst order. Experiments show that, compared to random walk from scratch, our algorithm has similar accuracy but reduces the iterative analysis time by up to 18 x for on-chip PDN sizing, and by up to 13 × for package ball assignment with substrate routing. In addition, our incremental random walk has a linear time complexity with respect to the number of observed nodes and is more suitable for on-demand analysis, compared to random walk from scratch and its big warm-up cost.
AB - Power distribution networks (PDNs) are designed and analyzed iteratively. Random walk is among the most efficient methods for PDN analysis. We develop in this paper an incremental and on-demand random walk to reduce iterative analysis time. During each iteration, we map the design changes as positive or negative random walks for observed nodes. To update PDN analysis result, we only need to apply these extra positive or negative walks, instead of doing all walks from scratch. We show that different execution orders for these walks do not affect accuracy but do affect the runtime because of the cancellation between positive and negative walks. Considering this cancellation effect, we optimize the walk order by solving a min-energy electromagnetic particles placement problem and, as a result, further reduce the runtime to about 8× compared to the worst order. Experiments show that, compared to random walk from scratch, our algorithm has similar accuracy but reduces the iterative analysis time by up to 18 x for on-chip PDN sizing, and by up to 13 × for package ball assignment with substrate routing. In addition, our incremental random walk has a linear time complexity with respect to the number of observed nodes and is more suitable for on-demand analysis, compared to random walk from scratch and its big warm-up cost.
UR - https://www.scopus.com/pages/publications/64549106898
U2 - 10.1109/ASPDAC.2009.4796478
DO - 10.1109/ASPDAC.2009.4796478
M3 - Conference contribution
AN - SCOPUS:64549106898
SN - 9781424427482
T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
SP - 185
EP - 190
BT - Proceedings of the ASP-DAC 2009
T2 - Asia and South Pacific Design Automation Conference 2009, ASP-DAC 2009
Y2 - 19 January 2009 through 22 January 2009
ER -