并行算法性能簡析

何怡芝

（1．西北大學 陜西 西安 710069；2．陜西職業(yè)技術(shù)學院 陜西 西安 710100）

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

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

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

#include ＜stdio．h＞

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

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

{

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

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

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

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

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

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

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

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

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

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

if（myid==0） {

n=10000；

startwtime=MPI_Wtime（）；

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

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

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號進程執(zhí)行的代碼，進程首先獲取時間，再用現(xiàn)在的時候減去初始獲取的時間即得到程序執(zhí)行的時間并顯示。

MPI_Finalize（）；/*讓系統(tǒng)釋放分配給MPI的資源。

return 0；

}

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

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

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

2.1 并行算法中的幾種假設(shè)

2.1.1 假設(shè)一

計算規(guī)模n=20 000，節(jié)點變化

1）節(jié)點為 1時

Process 0 on node9

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

wall clock time=0．001900

2）節(jié)點為 2時

當測試兩個結(jié)點時：

Process 0 on node9

Process 1 on node8

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

wall clock time=0．001545

3）節(jié)點為 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 假設(shè)二

結(jié)點個數(shù)固定為3，計算規(guī)模n不斷變化

1）當 n=30 000時

Process 0 on node9

Process 1 on node8

Process 2 on node6

圖1 計算規(guī)模n=20 000，節(jié)點變化時，加速比和效率的值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 結(jié)點個數(shù)固定為3，計算規(guī)模n不斷變化時，加速比和效率的值Fig．2 Number of nodes is 3， n changing， speedup and efficiency

2.2 加速比和效率分析結(jié)果

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

3 結(jié)束語

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

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

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

[3]于澤德．基于SIMD-MC2的并行FFT算法 [J]．現(xiàn)代計算機：專業(yè)版，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]陳文光．并行計算的普及與挑戰(zhàn)[N]．中國電子報，2008．

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

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