并行随机行走算法设计及其在IC电源噪声分析中的应用

发布时间：2018-05-31 22:32

本文选题：并行计算 + 随机行走　；参考：《西北大学》2013年硕士论文

【摘要】：随机行走算法是一个广泛应用于工程应用领域的经典统计算法。随着科技的不断发展,工程研究中的问题规模和复杂度越来越大,如何高效利用随机行走算法是人们面临的一个新问题。面对求解问题复杂度不断增加、处理数据不断增大的事实,迫切需要新的技术或方法促使随机行走算法能够胜任这些新的挑战。并行计算是提高算法执行效率的有效途径之一。程序设计者把具有并行特征的串行算法并行化实现,并运行在高效的并行系统中,从而提高算法的执行效率。因此,可以利用并行计算技术来提高随机行走算法的执行效率本文主要研究并行随机行走算法的设计和应用技术。首先,研究了随机行走算法的基本理论,介绍了并行计算的主要方法,通过分析随机行走算法的可并行性特征,提出了基于MPI的并行随机行走算法。接着,对基于MPI的并行随机行走算法的设计思路和算法流程进行了详细的分析。最后,将设计好的并行随机行走算法应用于电路分析领域,对大规模集成电路的电源噪声进行计算分析。本文提出的并行随机行走算法基于主-从模式进行设计,并通过MPI实现进程间的通信,采用C语言编程实现,并在IBM Blade HS22刀片服务器上进行并行算法的性能测试。通过串行随机行走算法与并行随机行走算法的对比实验,证明并行技术能够有效的提高随机行走算法的执行效率。
[Abstract]:Random walk algorithm is a classical statistical algorithm widely used in engineering applications. With the development of science and technology, the scale and complexity of the problems in engineering research are becoming larger and larger. How to efficiently utilize the random walk algorithm is a new problem that people face. In the face of the increasing complexity of solving the problem and the increasing data processing, new techniques or methods are urgently needed to enable the random walk algorithm to meet these new challenges. Parallel computing is one of the effective ways to improve the efficiency of algorithm execution. The program designer parallelizes the serial algorithm with parallel characteristics and runs in an efficient parallel system, thus improving the efficiency of the algorithm. Therefore, parallel computing technology can be used to improve the execution efficiency of random walk algorithm. This paper mainly studies the design and application of parallel random walk algorithm. Firstly, the basic theory of random walk algorithm is studied, and the main methods of parallel computing are introduced. By analyzing the parallelism characteristics of random walk algorithm, a parallel random walk algorithm based on MPI is proposed. Then, the design idea and algorithm flow of parallel random walk algorithm based on MPI are analyzed in detail. Finally, the designed parallel random walk algorithm is applied to the field of circuit analysis to calculate and analyze the power noise of LSI. The parallel random walk algorithm proposed in this paper is designed based on master-slave mode, and interprocess communication is realized by MPI. The parallel algorithm is programmed in C language, and the performance of parallel algorithm is tested on IBM Blade HS22 blade server. By comparing the serial random walk algorithm with the parallel random walk algorithm, it is proved that the parallel technology can effectively improve the execution efficiency of the random walk algorithm.
【学位授予单位】：西北大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP338.6

【参考文献】