本文選題：并行計算 + 隨機行走�。� 參考：《西北大學》2013年碩士論文

【摘要】：隨機行走算法是一個廣泛應用于工程應用領域的經典統(tǒng)計算法。隨著科技的不斷發(fā)展,工程研究中的問題規(guī)模和復雜度越來越大,如何高效利用隨機行走算法是人們面臨的一個新問題。面對求解問題復雜度不斷增加、處理數(shù)據不斷增大的事實,迫切需要新的技術或方法促使隨機行走算法能夠勝任這些新的挑戰(zhàn)。并行計算是提高算法執(zhí)行效率的有效途徑之一。程序設計者把具有并行特征的串行算法并行化實現(xiàn),并運行在高效的并行系統(tǒng)中,從而提高算法的執(zhí)行效率。因此,可以利用并行計算技術來提高隨機行走算法的執(zhí)行效率 本文主要研究并行隨機行走算法的設計和應用技術。首先,研究了隨機行走算法的基本理論,介紹了并行計算的主要方法,通過分析隨機行走算法的可并行性特征,提出了基于MPI的并行隨機行走算法。接著,對基于MPI的并行隨機行走算法的設計思路和算法流程進行了詳細的分析。最后,將設計好的并行隨機行走算法應用于電路分析領域,對大規(guī)模集成電路的電源噪聲進行計算分析。本文提出的并行隨機行走算法基于主-從模式進行設計,并通過MPI實現(xiàn)進程間的通信,采用C語言編程實現(xiàn),并在IBM Blade HS22刀片服務器上進行并行算法的性能測試。通過串行隨機行走算法與并行隨機行走算法的對比實驗,證明并行技術能夠有效的提高隨機行走算法的執(zhí)行效率。
[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

【參考文獻】

相關期刊論文 前10條

1 蘇浩航;張義門;張玉明;滿進財;;基于層次化隨機游走算法的靜態(tài)P/G網分析[J];電子器件;2007年03期

2 王萊;布朗運動和隨機行走的計算機仿真[J];工科物理;1998年06期

3 郭軍;李明輝;董社勤;申衛(wèi)昌;;隨機行走的電路分析應用及并行化改進[J];計算機工程與應用;2010年18期

4 駱祖瑩,王國璞,蔡懿慈,洪先龍,Sheldon,X.-D.Tan;基于部分隨機行走的電源線/地線(P/G)網絡快速求解方法[J];計算機輔助設計與圖形學學報;2004年11期

5 康樂;蔡懿慈;洪先龍;;隨機行走算法研究及其在電源/地線網絡瞬態(tài)優(yōu)化中的應用[J];計算機輔助設計與圖形學學報;2007年09期

6 郭軍;董社勤;;隨機行走算法在IC芯片熱分析中的應用[J];計算機輔助設計與圖形學學報;2010年04期

7 蘇浩航;張義門;張玉明;解敏;滿進財;;基于改進的壓縮式隨機游走算法對靜態(tài)電源/地網的模擬[J];計算物理;2007年06期

8 陳國良;孫廣中;徐云;龍柏;;并行計算的一體化研究現(xiàn)狀與發(fā)展趨勢[J];科學通報;2009年08期

9 鄧俊勇;錢江華;卓成;周金芳;陳抗生;;用于電源/地網絡分析的隨機行走算法改進[J];浙江大學學報(工學版);2007年08期

10 鄧俊勇;錢江華;卓成;周金芳;陳抗生;;基于隨機行走的電源pads分配算法[J];浙江大學學報(工學版);2008年06期

相關博士學位論文 前3條

1 鄧俊勇;深亞微米芯片設計中的電源完整性相關問題研究[D];浙江大學;2011年

2 孫建明;甚高頻交易數(shù)據的金融計量研究[D];華中科技大學;2004年

3 姚震;并行程序設計模型若干問題研究[D];中國科學技術大學;2006年

相關碩士學位論文 前9條

1 陳科;基于高性能計算機的并行計算研究[D];大連理工大學;2011年

2 孫晗琦;并行計算在計算流體力學中的研究[D];大連理工大學;2005年

3 張治宏;基于MPI的并行計算研究[D];中國地質大學（北京）;2006年

4 霍旭光;基于MPI高性能計算方法的研究[D];中國地質大學（北京）;2006年

5 袁健美;SGI服務器并行計算環(huán)境建設及并行作業(yè)管理[D];湘潭大學;2006年

6 姚成浪;基于MPI的集群計算系統(tǒng)設計與實現(xiàn)[D];哈爾濱工程大學;2007年

7 李永旭;基于MPI標準的并行計算平臺的設計與實現(xiàn)[D];東北師范大學;2007年

8 許廷霆;隨機行走模型在交通中的應用[D];北京交通大學;2009年

9 張國春;平面上的一種隨機行走模型及其計算機模擬[D];河北大學;2010年

，

本文編號：1961576