基于层次化随机游走算法的静态P/G网分析

将随机游走法和层次法相结合,采用层次化随机游走法对静态P/G网(Power and Ground Networks)进行分析.针对大规模的电路,在通过多层的参数提取和建模得到静态P/G网模型后,运用层次法将P/G网分割,在子网内采用随机游走法,并且在此基础上比较5种加速算法.实验数据表明,改进的双共轭梯度(BCG)随机游走法的计算速度是普通随机游走法的6倍以及是层次法的14倍.新方法有效地节省了计算时间,有益于对P/G网的研究.

Analysis of Static P/G Network Based on Hierarchical Random Walk Algorithm

The static power and ground network is analyzed based on the strategy by the combination of hierarchical algorithm and random algorithm, which is called as hierarchical random walk algorithm. The model of power and ground networks can be made by parameter extraction and model building from the whole chip. All network is divided into different level parts by hierarchical algorithm, then, the random walk algorithm is used to solve each part. The comparison of five iterative algorithms for the static power grid analysis has been made based on hierarchical random walk algorithm. As a result of the improved BCG random walk algorithm, the applications of presented algorithm show that the speed of the improved BCG random walk algorithm is 6 times faster than the normal random walk algorithm and 14 times than the normal hierarchical algorithm. So theapplications of presented algo- rithm can greatly shorten the CPU time.