用于电源/地网络分析的随机行走算法改进

为了克服用于芯片上电源/地(P/G)网络分析的一般随机行走算法在求解整个网络时效率比较低下、求解时间与理想电压源节点(VDD)所占比例成反比变化，以及求解wire-bond类型的P/G网络时运算时间与网络规模呈超线性复杂度等缺点，提出了一种改进的随机行走算法.该算法充分利用一次行走所获得的信息，将节点的一次行走分解为所经过节点的若干次随机行走，每到达一个未知电压值节点等效为该节点一次随机行走的开始.仿真结果表明，在可以忽略的误差范围内，改进后算法的求解速度比一般随机行走算法求解速度要快十多倍，求解时间不随VDD所占比例而变化，且对于wire-bond类型的P/G网络具有线性时间复杂度.

Improvement of random walk algorithm for power/ground grid analysis

Generic random walk algorithm for on-chip power/ground(P/G) network analysis has low efficiency when solving the whole P/G network,and its runtime is greatly influenced by perfect voltage sources(VDD) percentage,and also shows super linear runtime complexity for wire-bond P/G networks.This work proposed an improved random walk algorithm,which made full use of the information obtained from a walk.A walk for a certain node was divided into multiple random walks for the visited nodes,and the reach of every unknown node was interpreted as the start of another random walk for the currently visited node.Simulation indicated that,compared with the generic random walk algorithm,the improved algorithm gained over ten times speedup with negligible error,and its linear complexity did not vary with VDD percentage.Also the improved algorithm had linear runtime complexity for wire-bond P/G network.