并行計(jì)算實(shí)驗(yàn)報(bào)告(高性能計(jì)算與網(wǎng)格技術(shù))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)高性能計(jì)算和網(wǎng)格技術(shù)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目OpenMP和MPI編程姓名學(xué)號(hào)專業(yè)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)指導(dǎo)教師助教所在學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院論文提交日期一、實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)的目的是通過練習(xí)掌握 OpenMP 和MPI 并行編程的知識(shí)和技巧。1、熟悉 OpenMP 和MPI 編程環(huán)境和工具的使用；2、掌握并行程序編寫的基本步驟；3、了解并行程序調(diào)試和調(diào)優(yōu)的技巧。二、實(shí)驗(yàn)要求1、獨(dú)立完成實(shí)驗(yàn)內(nèi)容；2、了解并行算法的設(shè)計(jì)基礎(chǔ)；3、熟悉OpenMP和MPI的編程環(huán)境以及運(yùn)行環(huán)境；4、理解不同線

2、程數(shù)，進(jìn)程數(shù)對(duì)于加速比的影響。三、實(shí)驗(yàn)內(nèi)容3.1、矩陣LU分解算法的設(shè)計(jì)：參考文檔sy6.doc所使用的并行算法：在LU分解的過程中，主要的計(jì)算是利用主行i對(duì)其余各行j，(ji)作初等行變換，各行計(jì)算之間沒有數(shù)據(jù)相關(guān)關(guān)系，因此可以對(duì)矩陣A按行劃分來實(shí)現(xiàn)并行計(jì)算。考慮到在計(jì)算過程中處理器之間的負(fù)載均衡，對(duì)A采用行交叉劃分：設(shè)處理器個(gè)數(shù)為p，矩陣A的階數(shù)為n，對(duì)矩陣A行交叉劃分后，編號(hào)為i(i=0,1,p-1)的處理器存有A的第i, i+p, i+(m-1)p行。然后依次以第0,1,n-1行作為主行，將其廣播給所有處理器，各處理器利用主行對(duì)其部分行向量做行變換，這實(shí)際上是各處理器輪流選出主行并廣播

3、。若以編號(hào)為my_rank的處理器的第i行元素作為主行，并將它廣播給所有處理器，則編號(hào)大于等于my_rank的處理器利用主行元素對(duì)其第i+1,m-1行數(shù)據(jù)做行變換，其它處理器利用主行元素對(duì)其第i,m-1行數(shù)據(jù)做行變換。根據(jù)上述算法原理用代碼表示如下（關(guān)鍵代碼）：for(k = 0;kN;k+)for (i = 0; i THREADS_NUM; i+) thread_data_arrrayi.thread_id = i;thread_data_arrrayi.K_number = k;thread_data_arrrayi.chushu = akk;/創(chuàng)建線程rc = pthread_crea

4、te(&pidi, NULL, work, (void*)&thread_data_arrrayi); for (i = 0; i thread_id;/線程IDint myk = my_data-K_number;/外層循環(huán)計(jì)數(shù)Kfloat mychushu = my_data-chushu;/對(duì)角線的值int s, e;int i, j;s = (N-myk-1) * myid / THREADS_NUM;/確定起始循環(huán)的行數(shù)的相對(duì)位置e = (N-myk-1) * (myid + 1) / THREADS_NUM;/確定終止循環(huán)的行數(shù)的相對(duì)位置for (i = s+myk+1; i e+

5、myk+1; i+)/由于矩陣規(guī)模在縮小，找到偏移位置aimyk=aimyk/mychushu;for (j = myk+1; j N; j+)aij=aij-aimyk*amykj;/printMatrix(a);return NULL; 第一部分為入口函數(shù)，其創(chuàng)建指定的線程數(shù)，并根據(jù)不同的線程id按行劃分矩陣，將矩陣的不同部分作為參數(shù)傳遞給線程，在多處理器電腦上，不同的線程并行執(zhí)行，實(shí)現(xiàn)并行計(jì)算LU分解。在LU分解的過程中，主要的計(jì)算是利用主行i對(duì)其余各行j，（j）i）做初等行變換，由于各行計(jì)算之間沒有數(shù)據(jù)相關(guān)關(guān)系，因此可以對(duì)矩陣按行劃分來實(shí)現(xiàn)并行算法。考慮到計(jì)算過程中處理器負(fù)載的均衡，對(duì)

6、矩陣采用行交叉劃分；假設(shè)處理器個(gè)數(shù)為p，矩陣的階數(shù)為n，則每個(gè)處理器處理的行數(shù)為。由于在OpenMP和MPI中并行算法的實(shí)現(xiàn)不太一樣，所以接下來的兩小節(jié)中我將分別針對(duì)兩個(gè)編程環(huán)境設(shè)計(jì)LU分解的并行實(shí)現(xiàn)。3.2、OpenMP編程 因?yàn)镺penMP是基于線程的編程模型，所以設(shè)計(jì)了一個(gè)基于多線程的OpenMP的LU分解算法，關(guān)鍵代碼如下：for(k = 0;kN;k+)omp_set_num_threads(THREADS_NUM);#pragma omp parallel private(tid)tid=omp_get_thread_num(); /當(dāng)前線程IDint myid = tid;pri

7、ntf(hello world from OMP thread %d n,tid);int myk = k;float mychushu = Akk;int s, e;int i, j;s = (N-myk-1) * myid / THREADS_NUM;/確定起始循環(huán)的行數(shù)的相對(duì)位置e = (N-myk-1) * (myid + 1) / THREADS_NUM;/確定終止循環(huán)的行數(shù)的相對(duì)位置for (i = s+myk+1; i e+myk+1; i+)/由于矩陣規(guī)模在縮小，找到偏移位置Aimyk=Aimyk/mychushu;for (j = myk+1; j j的元素，其對(duì)角線上元素為

8、1.0，其它為0，U為Akj中k=j的元素，其余為0。這里如果我們使用的是一般的多線程編程，則在開啟THREAD _NUMS個(gè)線程后，在下次循環(huán)開始之前，需要手動(dòng)配置等待線程同步，不然可能出現(xiàn)錯(cuò)誤。但由于OpenMP使用Fork-Join并行執(zhí)行模型，其會(huì)在線程隊(duì)執(zhí)行完以后才轉(zhuǎn)到主線程執(zhí)行，所以不需要等待線程同步。詳細(xì)的代碼請(qǐng)參看附帶源程序。3.3、MPI編程設(shè)處理器個(gè)數(shù)為p，矩陣A的階數(shù)為n，對(duì)矩陣A行交叉劃分后，編號(hào)為i(i=0,1,p-1)的處理器存有A的第i, i+p, i+ (m-1)p行。然后依次以第0,1,n-1行作為主行，將其廣播給所有處理器，各處理器利用主行對(duì)其部分行向量做行

9、變換，這實(shí)際上是各處理器輪流選出主行并廣播。若以編號(hào)為my_rank的處理器的第i行元素作為主行，并將它廣播給所有處理器，則編號(hào)大于等于my_rank的處理器利用主行元素對(duì)其第i+1,m-1行數(shù)據(jù)做行變換，其它處理器利用主行元素對(duì)其第i,m-1行數(shù)據(jù)做行變換，計(jì)算完成后，編號(hào)為0的處理器收集各處理器中的計(jì)算結(jié)果，并從經(jīng)過初等行變換的矩陣A中分離出下三角矩陣L和上三角矩陣U。 關(guān)鍵代碼如下：/*0號(hào)進(jìn)程采用行交叉劃分將矩陣A劃分為大小m*M的p塊子矩陣，依次發(fā)送給1至p-1號(hào)進(jìn)程*/ if (my_rank=0) for(i=0;im;i+) for(j=0;jM;j+) a(i,j)=A(i*

10、p),j); for(i=0;iM;i+) if (i%p)!=0)i1=i%p;i2=i/p+1;MPI_Send(&A(i,0),M,MPI_FLOAT,i1,i2,MPI_COMM_WORLD); else for(i=0;im;i+) MPI_Recv(&a(i,0),M,MPI_FLOAT,0,i+1,MPI_COMM_WORLD,&status); for(i=0;im;i+) for(j=0;jp;j+)/*j號(hào)進(jìn)程負(fù)責(zé)廣播主行元素*/if (my_rank=j)v=i*p+j;for (k=v;kM;k+)fk=a(i,k);MPI_Bcast(f,M,MPI_FLOAT,my

11、_rank,MPI_COMM_WORLD);elsev=i*p+j;MPI_Bcast(f,M,MPI_FLOAT,j,MPI_COMM_WORLD);/*編號(hào)小于my_rank的進(jìn)程（包括my_rank本身）利用主行對(duì)其第i+1,m-1行數(shù)據(jù)做行變換*/if (my_rank=j)for(k=i+1;km;k+)a(k,v)=a(k,v)/fv;for(w=v+1;wj)for(k=i;km;k+)a(k,v)=a(k,v)/fv;for(w=v+1;wM;w+)a(k,w)=a(k,w)-fw*a(k,v); /*0號(hào)進(jìn)程從其余各進(jìn)程中接收子矩陣a，得到經(jīng)過變換的矩陣A*/ if (my_

12、rank=0) for(i=0;im;i+) for(j=0;jM;j+) A(i*p,j)=a(i,j); if (my_rank!=0) for(i=0;im;i+) MPI_Send(&a(i,0),M,MPI_FLOAT,0,i,MPI_COMM_WORLD); else for(i=1;ip;i+) for(j=0;jm;j+)MPI_Recv(&a(j,0),M,MPI_FLOAT,i,j,MPI_COMM_WORLD,&status);for(k=0;kM;k+)A(j*p+i),k)=a(j,k); 3.4、程序調(diào)優(yōu)：OpenMP和MPI混合編程 我們知道OpenMP是基于線程

13、的并行編程模型，一個(gè)共享存儲(chǔ)的進(jìn)程由多個(gè)線程組成，OpenMP就是基于已有線程的共享編程模型；而MPI屬于消息傳遞的并行編程模型，這個(gè)從前兩小節(jié)中可以看到，因?yàn)樵贚U的MPI實(shí)現(xiàn)中，我們對(duì)矩陣采用交叉劃分，根據(jù)p（處理器號(hào)）劃分行，因此可以對(duì)每個(gè)劃分出來的矩陣采用多線程并行算法，也即可以采用OpenMP計(jì)算。 在MPI的編號(hào)大于等于my_rank的處理器利用主行元素對(duì)其第i+1,m-1行數(shù)據(jù)做行變換，其它處理器利用主行元素對(duì)其第i,m-1行數(shù)據(jù)做行變換部分采用OpenMP計(jì)算，所以混合編程的核心代碼如下：/*編號(hào)小于my_rank的進(jìn)程（包括my_rank本身）利用主行對(duì)其第i+1,m-1行數(shù)

14、據(jù)做行變換*/if (my_rank=j)int tid;omp_set_num_threads(THREADS_NUM);#pragma omp parallel private(tid)tid = omp_get_thread_num();int myid = tid;int myk = i+1;float mychushu = fv;int s,e;int c,d;s = (m-myk-1)*myid/THREADS_NUM;e = (m-myk-1)*(myid+1)/THREADS_NUM;for(c=s+myk+1;ce+myk+1;c+)a(c,v)=a(c,v)/mychush

15、u;for(d=v+1;dM;d+)a(c,d)=a(c,d)-fd*a(c,v);四、程序運(yùn)行效果及分析這里將通過測(cè)試在確定的線程下，對(duì)于隨機(jī)生成的不同大小的矩陣，串行及OpenMP&MPI的運(yùn)行時(shí)間來分析程序性能。并通過改變線程的數(shù)量，在不同情況下多次測(cè)量，測(cè)試編譯參數(shù)對(duì)程序性能的影響。4.1、固定線程數(shù)時(shí)，不同矩陣大小下性能測(cè)試當(dāng)線程數(shù)為5時(shí)：測(cè)試得到的不同矩陣大小下的加速比數(shù)據(jù)如圖1所示：圖1 根據(jù)圖1中所示測(cè)得的數(shù)據(jù)，生成折線圖如下：b當(dāng)線程數(shù)為100時(shí)，測(cè)得的實(shí)驗(yàn)數(shù)據(jù)如圖2所示：圖2根據(jù)圖2中所示測(cè)得實(shí)驗(yàn)數(shù)據(jù)生成的折線圖如下：結(jié)果分析：從以上的結(jié)果可以看出在不同的線程下，OpenM

16、P的性能都會(huì)隨著矩陣規(guī)模的增大而變好，也就是在矩陣規(guī)模變大時(shí)，OpenMP的加速比變大，雖然在實(shí)驗(yàn)中有出現(xiàn)下降，但總體來說加速比在增大。同時(shí)，可以看到在矩陣很小時(shí)，加速比幾乎為零，也即此時(shí)的OpenMP運(yùn)行時(shí)間比串行時(shí)間久，這主要是在矩陣規(guī)模很小時(shí)，OpenMP多線程減少的計(jì)算時(shí)間相比為維護(hù)這么多線程花費(fèi)的時(shí)間要少很多，所以在數(shù)據(jù)規(guī)模很小時(shí)，不應(yīng)該采用OpenMP編程并行編程。相反，在數(shù)據(jù)規(guī)模很大時(shí)，采用OpenMP并行編程模型，將帶來巨大的性能提升。4.2、固定矩陣大小時(shí)，不同線程數(shù)下的性能測(cè)試a當(dāng)矩陣大小為2000時(shí)，測(cè)得的數(shù)據(jù)如圖3所示：圖3根據(jù)圖3測(cè)得實(shí)驗(yàn)數(shù)據(jù)，生成的折線圖如下：b當(dāng)矩

17、陣大小為4000時(shí)，測(cè)得的數(shù)據(jù)如圖4所示：圖4根據(jù)圖4測(cè)得實(shí)驗(yàn)數(shù)據(jù)，生成的折線圖如下：結(jié)果分析：從上面的實(shí)驗(yàn)測(cè)試可以看出，在不同的線程數(shù)量下，OpenMP運(yùn)行的加速比不同，同線程數(shù)量變大時(shí)，OpenMP的加速比并沒有如所期望的一樣變大，相反隨線程數(shù)量的增加，OpenMP的加速比變小了。因?yàn)镺penMP是基于多線程的編程模型，而我們知道多線程程序性能的提高是基于多CPU同時(shí)運(yùn)行線程，而本次程序測(cè)試的主機(jī)為4核的，也即可以同時(shí)運(yùn)行4個(gè)線程，因此當(dāng)線程數(shù)量增多到超過CPU數(shù)量時(shí)，多余的線程實(shí)際上并沒有得到執(zhí)行，相反這個(gè)時(shí)候還需要額外維護(hù)這大量的線程，因此性能降低，所以加速比隨線程增多而有所降低。因此

18、，在進(jìn)行OpenMP并行編程時(shí)，我們需要根據(jù)所運(yùn)行的主機(jī)的CPU數(shù)量合理的設(shè)置線程的數(shù)量，以獲得最大的加速比。以上是針對(duì)OpenMP并行算法與串行算法的性能的比較，下面再簡(jiǎn)單對(duì)不同進(jìn)程情況下MPI的LU并行算法與串行算法的性能比較。c. 分別在矩陣大小為3000和4000時(shí)測(cè)得的實(shí)驗(yàn)數(shù)據(jù)如下：根據(jù)測(cè)得的實(shí)驗(yàn)數(shù)據(jù)，生成的折線圖如下：結(jié)果分析：從上面的實(shí)驗(yàn)測(cè)試結(jié)果，可以看出，在進(jìn)程為4時(shí)，MPI的加速比為最大，而在兩邊變化時(shí)，加速比有所下降。也即在進(jìn)行MPI并行編程時(shí)，合理設(shè)置進(jìn)程也是非常重要的，一般也是根據(jù)運(yùn)行主機(jī)的CPU的數(shù)量來設(shè)置，如本次主機(jī)的CPU數(shù)量為4，所以設(shè)置進(jìn)程數(shù)為4，每個(gè)CPU分別負(fù)責(zé)執(zhí)行一個(gè)進(jìn)程，在進(jìn)程數(shù)量過多時(shí)，進(jìn)程沒有被執(zhí)行，反而還增加了維護(hù)進(jìn)程的開銷，我們知道這個(gè)開銷是很大的。結(jié)論：無論是MPI并