计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (18): 199-201.DOI: 10.3778/j.issn.1002-8331.2010.18.062

• 工程与应用 • 上一篇    下一篇

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

郭 军1,2,李明辉2,董社勤1,申卫昌2   

  1. 1.清华大学 计算机系,北京 100084
    2.西北大学 计算机系,西安 710069
  • 收稿日期:2009-03-03 修回日期:2009-06-22 出版日期:2010-06-21 发布日期:2010-06-21
  • 通讯作者: 郭 军

Random walk for circuit analysis and improving by parallel computing

GUO Jun1,2,LI Ming-hui2,DONG She-qin1,SHEN Wei-chang2   

  1. 1.Department of Computer Science,Tsinghua University,Beijing 100084,China
    2.Department of Computer Science,Northwest University,Xi’an 710069,China
  • Received:2009-03-03 Revised:2009-06-22 Online:2010-06-21 Published:2010-06-21
  • Contact: GUO Jun

摘要: 论述了随机行走算法的基本原理,理论分析了给定允许误差和置信概率下,随机行走算法的结束条件;讨论了随机行走算法在电路分析中的应用,并结合应用实例分析了算法的性能;讨论了算法的时间复杂性和影响算法执行时间的主要因素,重点分析了算法的并行特征,提出了采用并行计算技术提高算法性能的新方法,通过与串行算法的实验比较,表明了并行计算技术是提高随机行走算法执行速度的有效方法,比现有的方法适应性更广。

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

Abstract: 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.

Key words: random walk, circuit analysis, parallel computing

中图分类号: