并行算法性能簡析

何怡芝

（1．西北大學 陜西 西安 710069；2．陜西職業技術學院 陜西 西安 710100）

近年來，在市場需求的推動下，并行計算已經大量的應用于各個領域，如核武器、石油勘探、數值天氣預報、地震數據處理、飛行器數值模擬和大型事務處理等，都需要每秒執行萬億次甚至百萬億次運算的計算機，然而基于這些應用問題本身存在的并行性和單機性能的限制，并行計算就成為滿足計算機計算速度的惟一可行途徑[2]。所謂并行計算[1]，就是將一個任務分解成多個子任務，同時分配給幾個不同的處理器，各個處理器之間相互協同，并行地執行子任務，從而能夠加速求解問題的速度，或者擴大求解應用問題的規模。

1 求PI值的MPI并行計算程序

#include “mpi．h”/* 是預處理指令，用于包含 mpi的頭文件。

#include ＜stdio．h＞

double f（ double a ）{return （4．0/ （1．0+a*a））；} /*定義被積函數 f（x）。

intmain（int argc，char*argv[]） /*argc和 argv分別是命令行參數的個數和參數數組的指針。

{

intn，myid，numprocs，i，namelen；/*n ： 計算區間分區數；myid：本進程的進程號；numprocs：進程組中進程數；i：進程中計算各個小區間的循環控制變量；namelen：處理器名長度。

double PI25DT=3．141592653589793238462643；/* 定義一個比較精確的25位π值作為標準值，以分析本程序計算結果的誤差。

doublemypi， pi， h， sum， x； /*mypi：進程中所有小區間面積的求和值；pi：最終的計算π值；h：小區間寬度；sum：進程中所有小區間高的和；x：每個小區間中點的x值。

double startwtime，endwtime； /*定義變量開始時間startwtime和結束時間endwtime。均為MPI_Wtime（）的返回值。

char processor_name[MPI_MAX_PROCESSOR_NAME]； /*processor_name：處理器名存儲單元。

MPI_Init（＆argc，＆argv）； /*argc 和 argv 分別是命令行參數的個數和參數數組的指針。

MPI_Comm_size（MPI_COMM_WORLD，＆numprocs）； /*用numprocs返回通信域MPI_COMM_WORLD中的進程數。

MPI_Comm_rank（MPI_COMM_WORLD，＆myid）； /* 用myid返回通信域MPI_COMM_WORLD中本進程的進程號。

MPI_Get_processor_name（processor_name，＆namelen）； /*該函數返回運行本進程的處理器名稱。

fprintf（stderr，“Process%on%s ”，myid， processor_name）；

if（myid==0） {

n=10000；

startwtime=MPI_Wtime（）；

}/*是僅進程0執行的代碼，給n賦值10 000意味著將0-1的積分區間分成10 000小塊，對每一個小塊計算面積。同時，獲取計算機開始的時間。

MPI_Bcast（＆n， 1， MPI_INT， 0， MPI_COMM_WORLD）；/*表示通信器MPI_COMM_WORLD中進程號為0的進程將自己n中的內容發送給通信器中所有其他進程。

If（n==0）

done=1；

else{

h=1．0/（double） n；

sum=0．0；

for（i=myid； i＜ n； i+=numprocs） {

x=h* （（double）i+0．5）；

sum+=f（x）；

}/*計算本進程所分配的各小塊的高度和。每一進程均從i=myid開始，每做一次計算往后跳numprocs塊。

mypi=h*sum；/*mypi=h*sum將每個進程所得的各小塊的高度和與小塊寬度相乘即得本進程所得的小塊面積和即PI的部分值。

MPI_Reduce（＆mypi， ＆pi， 1， MPI_DOUBLE， MPI_SUM，0，MPI_COMM_WORLD）；/*將各進程所得的PI的部分值進行歸約。

if（myid==0） {

printf （“pi is approximately%．16f， error is%．16f ”， pi，pi-PI25DT）；

endwtime=MPI_Wtime（）；

printf（“wall clock time=%f ”， endwtime-startwtime）；

}}/*0號進程執行的代碼，進程首先獲取時間，再用現在的時候減去初始獲取的時間即得到程序執行的時間并顯示。

MPI_Finalize（）；/*讓系統釋放分配給MPI的資源。

return 0；

}

所有的進程都是從前到后依次執行該程序。

2 并行計算的加速比和效率分析

加速比和效率[1]是衡量一個并行程序性能的最基本的評價參數。其計算的方式如下：在處理器資源獨享的前提下，假設某個串行應用程序在某臺并行機單處理器上的執行時間為Ts，而該程序并行化后，P個進程在P個處理器并行執行所需要的時間為Tp，該并行程序在該并行機上的加速比Sp可定義為：效率定義為

2.1 并行算法中的幾種假設

2.1.1 假設一

計算規模n=20 000，節點變化

1）節點為 1時

Process 0 on node9

pi is approximately 3．1415926537981260， Error is 0．0000000002083329

wall clock time=0．001900

2）節點為 2時

當測試兩個結點時：

Process 0 on node9

Process 1 on node8

pi is approximately 3．1415926537981315， Error is 0．0000000002083368

wall clock time=0．001545

3）節點為 3時

Process 0 on node9

Process 1 on node8

Process 2 on node6

pi is approximately 3．1415926537981351， Error is 0．0000000002083415

wall clock time=0．001238

2.1.2 假設二

結點個數固定為3，計算規模n不斷變化

1）當 n=30 000時

Process 0 on node9

Process 1 on node8

Process 2 on node6

圖1 計算規模n=20 000，節點變化時，加速比和效率的值Fig．1 Scale of calculate n=20 000， the node changes，speedup and efficiency

pi is approximately 3．1415926628490523， Error is 0．0000000092592591

wall clock time=0．000913

2）當 n=55 000 時

Process 0 on node9

Process 1 on node8

Process 2 on node6

pi is approximately 3．1415926536173409， Error is 0．0000000000275477

wall clock time=0．002289

3）當 n=222 000時

Process 0 on node9

Process 1 on node8

Process 2 on node6

pi is approximately 3．1415926535914891， Error is 0．0000000000016960

wall clock time=0．006891

圖2 結點個數固定為3，計算規模n不斷變化時，加速比和效率的值Fig．2 Number of nodes is 3， n changing， speedup and efficiency

2.2 加速比和效率分析結果

由以上的加速比和效率圖可知，問題規模較小n等于20 000時，進程執行的墻上時間和加速比隨著節點數的增加而增大，效率隨著節點數的增加而減少，原因是進程啟動、調用、切換等時間開銷所占的比例相對較大；而問題規模較大時，加速比和效率均隨著規模的增加而增加，進程啟動、調用、切換等時間開銷所占的比例相對較小，說明該程序適合進行并行計算，并行的優勢體現的更明顯。

3 結束語

本文通過對PI計算程序的研究，以及對并行計算加速比和效率兩個并行程序性能評價參數的分析，提出了應用并行計算程序是提高計算機計算速度的有效途徑的結論。該結論將對復雜的多個進程計算問題提供了有效地解決方案。

[1]張林波，遲學斌．并行計算導論[M]．北京：清華大學出版社，2006．

[2]陳國良，安虹．并行算法實踐[M]．北京：高等教育出版社，2004．

[3]于澤德．基于SIMD-MC2的并行FFT算法 [J]．現代計算機：專業版，2008（10）：57-58．

YU Ze-de．Based on the SIMD-MC2 parallel FFT algorithm[J]．Modern Computer：Professional Edition，2008（10）：57-58．

[4]陳文光．并行計算的普及與挑戰[N]．中國電子報，2008．

[5]陳良育．并行符號算法若干問題的研究與應用[D]．上海：華東師范大學，2008．

[6]文劍．并行計算平臺的建立及性能分析[D]．廣州：廣東工業大學，2007．