电源线/地线网络单点SOR统计分析方法  

Single-Node SOR Method for Statistic Analysis of Power/Ground Networks

作　　者：骆祖莹[1] 潘月斗[2] 余先川[1] 

机构地区：[1]北京师范大学信息科学与技术学院,北京100875 [2]北京科技大学信息科学与技术学院,北京100083

出　　处：《电子学报》2007年第11期2043-2049,共7页Acta Electronica Sinica

基　　金：国家863高技术研究发展计划(No.2007AA01Z109;No.2006AA01Z223)

摘　　要：随着集成电路工艺进入纳米工艺时代,VLSI规模在增大的同时,还伴随着显著的工艺参数变化,使得电源线/地线网络(P/G网)分析从确定式分析算法转变为统计式分析算法,迫切需要能够降低算法复杂度的局部分析算法.为了计算设计者感兴趣的P/G网少数IR电压降比较大的问题节点电压变化,必须分别计算出这些点的相关电阻向量,本文提出了一种单点SOR(Successive Over Relaxation:连续过松弛-超级松弛)的统计分析方法(SN-SOR).与传统的全局SOR方法相比,SN-SOR方法有如下三个优点:(1)局部松弛.由于计算一个问题节点q的相关电阻向量,必须仅在q点加一个激励,所以SN-SOR方法不是采用全局电路节点的顺序松弛方法,而是采用从q点不断向周围节点进行松弛的波状松弛方法,当某些节点的IR电压降小于一个极小的设定值时(即相关电阻足够小),这些节点就不再向外进行松弛计算,因此SN-SOR方法具有局部松弛的特性.(2)高效.与传统的全局SOR方法相比,SN-SOR方法不仅松弛点非常少,而且松弛次数也有所减少.(3)低空间复杂度.当计算出q点相关电阻向量后,SN-SOR方法不是将所有相关电阻都存起来,而是只将强相关电阻存起来,对于大多数的弱相关电阻,仅将少数代表节点上的弱相关电阻存起来,所以本文方法的空间复杂度比较低.大量的实验数据表明,与全局SOR求解方法相比,SN-SOR方法在保持较高精度(误差小于0.38%)的前提下,速度可以提高20倍.With technology scaling into nanometer regime,VLSI chips become much more complex and suffer from rampant process variations.Therefore,statistical methods are replacing deterministic counterparts for power/ground（P/G）grid analysis and efficient local analysis methods are badly needed to reduce the analysis complexity.A novel single-node Successive Over Relaxation （SN-SOR）method is proposed to efficiently solve correlated resistor vectors and then to directly compute voltage variations for question nodes of large IR droop.Compared with traditional global SOR methods,the SN-SOR method shows following advantages. Ftrst one is locality.Because only one stimuli is located at the question node q to compute the correlated resistor vector Rq,SN-SOR relaxes nodes from q to its surround nodes as wave transmission and the wave stops at some nodes whose IR droop is less than one assigned little value.Second one is efficiency.SN-SOR only relaxes small parts of nodes in P/G circuits but also needs slightly less relaxation reiterations.Third one is low memory complexity.Among Rq,SN-SOR only needs some strong correlated resistors and less weak resistors of typical nodes to compute the voltage variation.Experiments show SN-SOR is 20 times faster than global SOR methods with only 0.38% accuracy loss.

关 键 词：VLSI P/G网 统计分析 SOR 单点分析 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]