随机行走的电路分析应用及并行化改进  

Random walk for circuit analysis and improving by parallel computing

作　　者：郭军[1,2] 李明辉[2] 董社勤[1] 申卫昌[2] 

机构地区：[1]清华大学计算机系,北京100084 [2]西北大学计算机系,西安710069

出　　处：《计算机工程与应用》2010年第18期199-201,243,共4页Computer Engineering and Applications

基　　金：陕西省教育厅自然科学专项基金No.05JK293;the Special Foundation of Shaanxi Education Bureau of China under Grant No.05JK293

摘　　要：论述了随机行走算法的基本原理,理论分析了给定允许误差和置信概率下,随机行走算法的结束条件;讨论了随机行走算法在电路分析中的应用,并结合应用实例分析了算法的性能;讨论了算法的时间复杂性和影响算法执行时间的主要因素,重点分析了算法的并行特征,提出了采用并行计算技术提高算法性能的新方法,通过与串行算法的实验比较,表明了并行计算技术是提高随机行走算法执行速度的有效方法,比现有的方法适应性更广。The random walk algorithm is introduced basically.The stop criterion of random walk algorithm is analyzed theoretically.Techniques of circuit analysis by random walk algorithm are discussed in details.Through an instance circuit,the performance of algorithm is studied carefully.And the complexity of random walk algorithm is analyzed.The factors related with algorithm runtime are discussed as well.As analyzing the parallel characteristics of random walk algorithm,a novel parallel computing technique is adopted to speedup the random walk algorithm.The experiment results indicate that parallel computing technique can improve random walk algorithm greatly.Moreover,the parallel computing techniques for random walk algorithm are much more adaptable than other methods.

关 键 词：随机行走 电路分析 并行计算 

分 类 号：TP311.5[自动化与计算机技术—计算机软件与理论]