并行處理與體系結(jié)構(gòu)試驗(yàn)指導(dǎo)書

1、Aaa4并行處理與體系結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書GuideBookofParallelProcessingandArchitectureExperiment編者：王瘠教務(wù)處2015年10月實(shí)驗(yàn)一MPI安裝與程序編譯、運(yùn)行和調(diào)試1實(shí)驗(yàn)二共享存儲(chǔ)模型與消息傳遞模型的比較3實(shí)驗(yàn)三矩陣運(yùn)算5實(shí)驗(yàn)四八皇后問題10實(shí)驗(yàn)五快速排序12實(shí)驗(yàn)六快速傅氏變換14實(shí)驗(yàn)一MPI安裝與程序編譯、運(yùn)行和調(diào)試一、實(shí)驗(yàn)?zāi)康拇罱∕PI并行編程環(huán)境，開發(fā)并行程序；學(xué)習(xí)并行程序的編寫、編譯、運(yùn)行步驟，了解系統(tǒng)結(jié)構(gòu)對(duì)編程模式和環(huán)境工具的影響。二、實(shí)驗(yàn)內(nèi)容在計(jì)算機(jī)局域網(wǎng)上安裝MPICH2虛擬機(jī)，用一個(gè)簡單的計(jì)算實(shí)例進(jìn)行測(cè)試。運(yùn)行實(shí)驗(yàn)代碼MPI運(yùn)行

2、程序文件夾下面的hello.c、who.c、message.c>isend.c和mtpi.c程序?qū)嵗?，體會(huì)MPI中獲取進(jìn)程標(biāo)識(shí)、消息傳遞及非阻塞通信等工作模式。三、實(shí)驗(yàn)步驟推薦的MPI使用環(huán)境是Linux，但實(shí)際應(yīng)用中Windows系統(tǒng)應(yīng)用廣泛。本實(shí)驗(yàn)主要給出Windows下MPI環(huán)境的搭建方法及MPI程序的編寫、編譯連接及運(yùn)行。大致步驟及說明如下：1 .創(chuàng)建用戶以管理員的身份登錄主機(jī)，在主機(jī)上建立一個(gè)MPI賬戶。如：用戶名：mympi密碼：mympi若在局域網(wǎng)環(huán)境下所有主機(jī)均推薦創(chuàng)建相同的MPI賬戶，且創(chuàng)建相同的工作目錄，如D:mpijob,將并行編譯成功的可執(zhí)行文件均存放在同一目錄下

3、。2 .安裝MPICH例如：本實(shí)驗(yàn)采用的mpich2-1.4.1p1-win-ia32安裝程序的下載地址為：/research/projects/mpich2downloads/tarballs/1.4.1p1/mpich2-1.4.1p1-win-ia32.msi推薦局域網(wǎng)中準(zhǔn)備進(jìn)行并行計(jì)算的所有計(jì)算機(jī)都要安裝MPICH2虛擬機(jī)，且要安裝在相同的路徑下。本實(shí)驗(yàn)以設(shè)置安裝在C:ProgramFilesMPICH2目錄下為例。運(yùn)行mpich2目錄下的mpich2-1.4.1p1-win-ia32.msi,將MPICH2虛擬機(jī)安裝到計(jì)算機(jī)上。(2)測(cè)試MP

4、I是否安裝成功前首先需要注冊(cè)一個(gè)用戶，具體操作如下：“開始”按鈕->所有程序->MPICH2->wmpiregister.exe。輸入用戶名、密碼，即我們第一步建立的系統(tǒng)管理員賬戶和系統(tǒng)登錄密碼。如圖1.1所示：圖1.1MPICH用戶注冊(cè)界面(3)用例程測(cè)試。選擇開始->所有程序->MPICH2->wmpiexec.exe;選才?Application為c:programfilesmpich2examplescpi.exe(就是自帶的一個(gè)計(jì)算圓周率的例子程序)?？稍贜umberofprocesses的數(shù)量選擇2表示用二個(gè)進(jìn)程來協(xié)同完成。選中"run

5、inseparatewindow”選項(xiàng)，再點(diǎn)擊Excute執(zhí)行。如圖1.2所示。E-1IMIPfEKECwrHpp«"r_,口圖1.2測(cè)試?yán)蘡pi.exe然后在控制臺(tái)窗口下提示輸入numberofintervals,隨便輸入個(gè)大點(diǎn)的數(shù)字(50000,5000000)就可以看到求的的圓周率值。如圖1.3所示。Enterthenumbei'ofintervals：<0quits)50603piisapproxinettely3.1415926536231167,Erroris0.0003000000333236allclocktine-0.0013770Ente

6、rthenumberofintervals：(0quits)5060000piisapproximately3.1415926535896412.Erropis0-0000000000001519vmIIclocktine=0.074561Enterthenumhei*ofintervals:(0quits)0請(qǐng)按任意鍵繼續(xù).圖1.3cpi.exe執(zhí)行結(jié)果顯示3.在VC6.0中配置MPI(1)新建Win32ConsoleApplication工程(2)先在VC6.0中加入mpi的includeoVC6.0程序菜單中“工具”->“選擇”->“目錄”然后添加，如圖1.4所示。加入lib

7、方法相同。圖1.4在VC6.0中添加MPI的include(3)在所在工程一設(shè)置一link中，加入mpi.libcxx.lib。(4)加入講過的helloworld程序，測(cè)試運(yùn)行結(jié)果。注：這里以windows下MPI+VC實(shí)現(xiàn)為例進(jìn)行的說明，同學(xué)可以根據(jù)自己的操作系統(tǒng)或開發(fā)語言自行選擇版本下載安裝。實(shí)驗(yàn)二共享存儲(chǔ)模型與消息傳遞模型的比較一、實(shí)驗(yàn)?zāi)康谋容^共享存儲(chǔ)模型與消息傳遞模型之間的區(qū)別。了解多線程并行和消息傳遞并行的工作機(jī)制。二、實(shí)驗(yàn)內(nèi)容(1)統(tǒng)計(jì)10000個(gè)隨機(jī)數(shù)中3出現(xiàn)的次數(shù)。OPENMP線程數(shù)可為1、2、4等。MPI程序進(jìn)程數(shù)可為1、2、4等。(2)比較相同線程/進(jìn)程數(shù)下，采用OPEN

8、MP和MPI實(shí)現(xiàn)N-BODY問題的性能。如：OPENMP線程數(shù)可為1、2、4等。MPI程序進(jìn)程數(shù)可為1、2、4等。三、實(shí)驗(yàn)步驟(1)共享存儲(chǔ)模型中，用openMP寫一個(gè)程序，實(shí)現(xiàn)在一個(gè)長度為10,000的隨機(jī)array里面，計(jì)算出3出現(xiàn)的次數(shù)，線程數(shù)為1,2或者4等。openMP可以拆分循環(huán)，比如2個(gè)線程，第一個(gè)線程負(fù)責(zé)array15000,第二個(gè)線程負(fù)責(zé)500110000,各循環(huán)5000次。這樣兩個(gè)線程可以同時(shí)遍歷數(shù)組的兩部分進(jìn)行搜索計(jì)數(shù)。4個(gè)線程也類似，拆分成4部分同時(shí)進(jìn)行。(OPENMP在VS2005以上支持，其他版本可查閱文獻(xiàn)進(jìn)行適當(dāng)配置即可使用。)消息傳遞編程模型循環(huán)拆分的思量類似。

9、比如2個(gè)進(jìn)程，第一個(gè)進(jìn)程負(fù)責(zé)array15000,第二個(gè)線程負(fù)責(zé)500110000,各循環(huán)5000次。這樣兩個(gè)線程可以同時(shí)遍歷數(shù)組的兩部分進(jìn)行搜索計(jì)數(shù)。4個(gè)線程也類似，拆分成4部分同時(shí)進(jìn)行。最后結(jié)果可以返回0號(hào)進(jìn)程。源代碼清單：1 .共享存儲(chǔ)模型計(jì)算隨機(jī)數(shù)中3的個(gè)數(shù)(參考程序如下，可根據(jù)自己掌握的多線程知識(shí)自己編寫新的OPM程序。)#include<stdio.h>#include<stdlib.h>#include<omp.h>#defineN10000intmain(intargc,char*argv)inti;intarrayN;intcount,nt

10、hreads,tid,chunk;unsignednum;chunk=100;count=0;doublestart,end;printf("pleasechoosenumberofthreads:1,2or4.n")scanf("%d",&num);提示輸入計(jì)算線程數(shù)omp_set_num_threads(num);#pragmaompparallelshared(nthreads)tid=omp_get_thread_num();if(tid=0)(nthreads=omp_get_num_threads();printf("nSt

11、artingcountwith%dthreadsn",nthreads);)start=omp_get_wtime();#pragmaompparallelforreduction(+:count)schedule(static,chunk)for(i=0;i<N;i+)(arrayi=rand()%10;if(arrayi=3)count+;)end=omp_get_wtime();printf("Thecountcost%fsec.time.n",end-start);printf("Thenumberof3appearedinthearray

12、are%d",count);)消息傳遞編程模式統(tǒng)計(jì)隨機(jī)數(shù)中3的個(gè)數(shù)采用消息傳遞機(jī)制，結(jié)果返回0號(hào)進(jìn)程。可參考helloworld或課程第7章中計(jì)算兀值程序的例子自行編寫程序。2 2)N-BODY問題分析OPENMP并行化N-BODY基本算法或簡化算法分析MPI并行化N-BODY基本算法或簡化算法比較這兩種方法的性能。參考程序見“代碼”文件夾。實(shí)驗(yàn)三矩陣運(yùn)算一、實(shí)驗(yàn)?zāi)康木仃囘\(yùn)算是數(shù)值計(jì)算中最重要的一類運(yùn)算，特別是在線性代數(shù)和數(shù)值分析中，它是一種最基本的運(yùn)算。許多科學(xué)問題的基礎(chǔ)都是矩陣。掌握在MPI虛擬機(jī)上進(jìn)行矩陣運(yùn)算求解算法及其程序設(shè)計(jì)、運(yùn)行。二、實(shí)驗(yàn)內(nèi)容求矩陣乘Cmxk=Amxn*B

13、Nk,以簡單劃分方法為例分析串并算法的性能。在單機(jī)或多機(jī)上，完成多個(gè)進(jìn)程（如2、4、16等），兩個(gè)方陣相乘運(yùn)算（階數(shù)可以自定如16X16、32X32128X128等），并比較運(yùn)行時(shí)間，計(jì)算加速比。進(jìn)一步了解棋盤劃分方法進(jìn)行矩陣運(yùn)算的實(shí)例，以矩陣cannon相乘為例進(jìn)行串并算法的分析和比較。三、實(shí)驗(yàn)步驟1、矩陣相乘及其串行算法矩陣是一些數(shù)的二維數(shù)組。一個(gè)mxn的矩陣有m行和n列元素，通常用二維數(shù)組來存儲(chǔ)一個(gè)矩陣。一個(gè)mxn階矩陣A=aj乘以一個(gè)nxk的矩陣B=bij就可以得到一個(gè)mxk的矩陣C=cij,它的元素Cj為A的第i行向量與B的第j列向量的內(nèi)積。矩陣相乘的關(guān)鍵是相乘的兩個(gè)元素的下標(biāo)要滿足

14、一定的要求（即對(duì)準(zhǔn)）。為此常采用適當(dāng)旋轉(zhuǎn)矩陣元素的方法（如后面將要闡述的Cannon乘法）,或采用適當(dāng)復(fù)制矩陣元素的辦法，或采用流水線的辦法使元素下標(biāo)對(duì)準(zhǔn)。由矩陣乘法定義容易給出其串行算法3.1,若一次乘法和加法運(yùn)算時(shí)間為一個(gè)單位時(shí)間，則顯然其時(shí)間復(fù)雜度為O（mnk）。算法3.1單處理器上矩陣相乘算法輸入：AmXn,BnXk輸出：CmXkBeginfori=0tom-1doforj=0tok-1doci,j=0forr=0ton-1doci,j=ci,j+ai,r*br,jendforendforendforEnd2.矩陣運(yùn)算的并行算法矩陣的兩種常見的劃分方法，即行列劃分（又稱為帶狀劃分）和棋

15、盤劃分（又稱為塊狀劃分）。所謂帶狀劃分（StripedPartitioning）就是將矩陣整行或整列地分成若干個(gè)組，每組指派給一個(gè)處理器。所謂棋盤劃分（CheckerBoardPartitioning）就是將方陣劃分成若干個(gè)子方陣，每個(gè)子方陣指派給一個(gè)處理器，此時(shí)任意處理器均不包含整行或整列。2.1 簡單的矩陣并行分塊乘法算法矩陣乘法可以用分塊的思想實(shí)現(xiàn)并行，即分塊矩陣乘法（BlockMatrixMultiplication）,將矩陣A按行劃分為p塊（p為處理器個(gè)數(shù)），設(shè)u=16/pl,每塊含有連續(xù)的u行向量，這些行塊依次記為Ao,Ai,Ap-1,分別存放在標(biāo)號(hào)為0,1,p-1的處理器中。對(duì)矩

16、陣B按列劃分為P塊，記v=k/p,每塊含有連續(xù)的v列向量，這些列塊依次記為B0,Bl,Bp-1,分別存放在標(biāo)號(hào)0,1,p-1為的處理器中。將結(jié)果矩陣C也相應(yīng)地同時(shí)進(jìn)行行、列劃分，得到pxp個(gè)大小為uxv的子矩陣，記第i行第j列的子矩陣為Cij,顯然有Cij=AiXBj,其中，Ai大小為uXn,Bj大小為nXv。處理器編號(hào)存儲(chǔ)內(nèi)容0A0B01AiBi2A2二B2,P-1a.p-1Bp-1(a)處理器編號(hào)存儲(chǔ)內(nèi)容0A0B11AiB22A2IB3,P-1a.p-1B0(b)圖3.1矩陣相乘并行算法中的數(shù)據(jù)交換開始，各處理器的存儲(chǔ)內(nèi)容如圖3.1(a)所示。此時(shí)各處理器并行計(jì)算CH=AKBj其中i=0,

17、1,p-1,此后第i號(hào)處理器將其所存儲(chǔ)的B的列塊送至第i-1號(hào)處理器(第0號(hào)處理器將B的列塊送至第p-1號(hào)處理器中，形成循環(huán)傳送)，各處理器中的存儲(chǔ)內(nèi)容如圖3.1(b)所示。它們?cè)俅尾⑿杏?jì)算Cj=aixBj,這里j=(i+1)modp。B的列塊在各處理器中以這樣的方式循環(huán)傳送p-1次并做p次子矩陣相乘運(yùn)算，就生成了矩陣C的所有子矩陣。編號(hào)為i的處理器的內(nèi)部存儲(chǔ)器存有子矩陣Ci0,Ci1,-Ci(p-1)O為了避免在通信過程中發(fā)生死鎖，奇數(shù)號(hào)及偶數(shù)號(hào)處理器的收發(fā)順序被錯(cuò)開，使偶數(shù)號(hào)處理器先發(fā)送后接收；而奇數(shù)號(hào)處理器先將B的列塊存于緩沖區(qū)buffer中，然后接收編號(hào)在其后面的處理器所發(fā)送的B的列塊

18、，最后再將緩沖區(qū)中原矩陣B的列塊發(fā)送給編號(hào)在其前面的處理器，具體并行算法框架描述如下：算法3.2矩陣并行分塊乘法算法輸入：Amixn,Bnxk,輸出：CmxkBegin對(duì)所有處理器my_rank(my_rank=0,p-1)同時(shí)執(zhí)行如下的算法：(1)目前計(jì)算C的子塊號(hào)l=(i+my_rank)modp(2)forz=0tou-1doforj=0tov-1docl,z,j=0fors=0ton-1docl,z,j=cl,z,j+az,s*bs,jendforendforendfor(3)計(jì)算左鄰處理器的標(biāo)號(hào)mm1=(p+my_rank-1)modp計(jì)算右鄰處理器的標(biāo)號(hào)mp1=(my_rank+1

19、)modp(4) if(i半p-1)then(4.(1) if(my_rankmod2=0)then/*編號(hào)為偶數(shù)的處理器*/(i)將所存的B的子塊發(fā)送到其左鄰處理器中(ii)接收其右鄰處理器中發(fā)來的B的子塊endif(4.(2) if(my_rankmod2豐th)en/*編號(hào)為奇數(shù)的處理器*/(i)將所存的B子塊在緩沖區(qū)buffer中做備份(ii)接收其右鄰處理器中發(fā)來的B的子塊(iii)將buffer中所存的B的子塊發(fā)送到其左鄰處理器中endifendifEnd設(shè)一次乘法和加法運(yùn)算時(shí)間為一個(gè)單位時(shí)間，由于每個(gè)處理器計(jì)算p個(gè)uxn與nxv階的子矩陣相乘，因此計(jì)算時(shí)間為u*v*n*p;所有處

20、理器交換數(shù)據(jù)p-1次，每次的通信量為v*n,通信過程中為了避免死鎖，錯(cuò)開奇數(shù)號(hào)及偶數(shù)號(hào)處理器的收發(fā)順序，通信時(shí)間為2(p-1)(ts+nv*tw)=O(nk),所以并行計(jì)算時(shí)間Tp=uvnp+2(p-1)(ts+nvtw)=mnk/p+2(p-1)(ts+nvtw)。2.2Cannon乘法2.2.1 Cannon乘法的原理Cannon算法是一種存儲(chǔ)有效的算法。為了使兩矩陣下標(biāo)滿足相乘的要求，它和上一節(jié)的并行分塊乘法不同，不是僅僅讓B矩陣的各列塊循環(huán)移動(dòng)，而是有目的地讓A的各行塊以及B的各列塊皆施行循環(huán)移位，從而實(shí)現(xiàn)對(duì)C的子塊的計(jì)算。將矩陣A和B分成p個(gè)方塊Aj和Bij,(0<i,j<

21、;/_1),每塊大小為-n/lx/l,并將它們分配給種黑種個(gè)處理器(P00,P01,，Pjp行)。開始時(shí)處理器Pj存放塊Aj和Bj,并負(fù)責(zé)計(jì)算塊Cj,然后算法開始執(zhí)行：將塊Aj向左循環(huán)移動(dòng)i步；將塊Bj向上循環(huán)移動(dòng)j步；Pj執(zhí)行乘加運(yùn)算后將塊Aj向左循環(huán)移動(dòng)1步，塊Bj向上循環(huán)移動(dòng)1步；重復(fù)第步，總共執(zhí)行寸增次乘加運(yùn)算和J6次塊Aj和Bj的循環(huán)單步移位。2.2.2 Cannon乘法的并行算法圖3.2示例了在16個(gè)處理器上，用Cannon算法執(zhí)行A4X4XB4X4的過程。其中(a)和(b)對(duì)應(yīng)于上述算法的第步；(c)、(d)、(e)、(f)對(duì)應(yīng)于上述算法的第和第步。在算法第步時(shí)，A矩陣的第0列不

22、移位，第1行循環(huán)左移1位，第2行循環(huán)左移2位，第3行循環(huán)左移3位；類似地，B矩陣的第0行不移位，第1列循環(huán)上移1位，第2列循環(huán)上移2歹U,第3列循環(huán)上移3歹U。這樣Cannon算法具體描述如下：算法3.3Cannon乘法算法輸入：AnXn,BnXn輸出：CnxnBegin對(duì)所有處理器my_rank(my_rank=0,p-1)同時(shí)執(zhí)行如下的算法：(1)計(jì)算子塊的行號(hào)i=my_rank/sqrt(p)計(jì)算子塊的歹U號(hào)j=my_rankmodsqrt(p)(2)fork=0to,p-1doif(i>k)thenLeftmoveonestep(a)endif/*a循環(huán)左移至同行相鄰處理器中*/

23、if(j>k)thenUpmoveonestep(b)endif/*b循環(huán)上移至同列相鄰處理器中*/endfor(3)fori=0tom-1doforj=0tom-1doci,j=0endforendfor(4)fork=0top-1dofori=0tom-1doforj=0tom-1dofork1=0tom-1doci,j=ci,j+ai,k1*bk1,jendforendforendforLeftmoveonestep(a)/*子塊a循環(huán)左移至同行相鄰的處理器中*/Upmoveonestep(b)/*子塊b循環(huán)上移至同列相鄰的處理器中*/endforEndA0,0A0,1A0,2A0

24、,3A1,0A1,1.A1,2.*A1,3,A2,0A2,12,2A2,3TA3,01-A3,1AA3,2A3,3B0,0B0,1AB0,2B0,3jLB1,0B1,1AB1,2A'B1,3B2,0B2,1BB212TB2,3B3,0BB311BB312BB3,3(a) A陣起始對(duì)準(zhǔn)(b) B陣起始對(duì)準(zhǔn)A0,0-jB0,0A0,1B1,1A0,2-.B2,2A0,3B3,34A1,1Ji,0A1,2<B2,1A1,3.B3,2A1,0-B0,3A2,2.B2,0A2,3.B3,1A2,0.B0,2A2,1.B1,34A3,3.B3,0A3,0.B0,1A3,1.B1211,2A3

25、,2.B2,3A0,1JB1,0A0,2-.B2,1A0,3-.B3,2A0,0dB0,3A1,24B2,0A1,3B3,1A1,0.B0,2A1,1/B1,3A2,3.產(chǎn),0A2,0<B0,1A2,1.B1,2A2,2B2,3A3,0.B0,0A3,1.B1,1A3,2.B2,2A3,3BB3,3(c)對(duì)準(zhǔn)后的A和B(d)第一次移位后的子陣位置A0,2A0,3A0,0A0,1/2,0B3,1上B0,2B1,3<4.A1,3tA1,0A1,1.A1,2.產(chǎn),01rB0,1*B1,2*B2,3A2,0.A2,1A2,2.A2,3.0,04B1,1.B2,2-J3,3_A3,1.A3,

26、2A3,3.A3,0.B1,0BB2,1.B3,2*B0,3A0,3B3,0A0,0B0,1A0,1B1,2A0,2B2,3A1,0A1,1A1,2A1,3B0,0B1,1B2,2B3,3A2,1A2,2A2,3A2,0B1,0B2,1B3,2B0,3A3,2A3,3A3,0A3,1B2,0B3,1B0,2B1,3(e)第二次移位后的子陣位置(f)第三次移位后的子陣位置圖3.216個(gè)處理器上的Cannon乘法過程這里函數(shù)Leftmoveonestep(a)表示子塊a在編號(hào)處于同行的處理器之間以循環(huán)左移的方式移至相鄰的處理器中；函數(shù)Upmoveonestep(b)表示子塊b在編號(hào)處于同列的處理器

27、之間以循環(huán)上移的方式移至相鄰的處理器中。這里我們以函數(shù)Leftmoveonestep(a)為例，給出處理器間交換數(shù)據(jù)的過程：算法3.4函數(shù)Leftmoveonestep(a)的基本算法Begin(1) if(j=0)then/*最左端的子塊*/(1.(1) 存的A的子塊發(fā)送到同行最右端子塊所在的處理器中(1.(2) 其右鄰處理器中發(fā)來的A的子塊endif(2)if(j=sqrt(p)-1)and(jmod2=0)then/*最右端子塊處理器且塊列號(hào)為偶數(shù)*/(2.(1) 存的A的子塊發(fā)送到其左鄰處理器中(2.(2) 其同行最左端子塊所在的處理器發(fā)來的A的子塊endif(3)if(j=sqrt(

28、p)-1)and(jmod2網(wǎng))then/*最右端子塊處理器且塊列號(hào)為奇數(shù)*/(3.(1) 存的A的子塊在緩沖區(qū)buffer中做備份(3.(2) 其同行最左端子塊所在的處理器發(fā)來的A的子塊(3.(3) 緩沖區(qū)buffer中所存的A的子塊發(fā)送到其左鄰處理器中endif(3.(4) (j豐sqrt(p)-1)and(jmod2=0)and(jw0)then/*其余的偶數(shù)號(hào)處理器*/(4.(1) 存的A的子塊發(fā)送到其左鄰處理器中(4.(2) 其右鄰處理器中發(fā)來的A的子塊endif(3.(5) (jwsqrt(p)-1)and(jmod2=1)and(jw0)then/*其余的奇數(shù)號(hào)處理器*/(5.(

29、1) 存的A的子塊在緩沖區(qū)buffer中做備份(5.(2) 其右鄰處理器中發(fā)來的A的子塊(5.(3) 緩沖區(qū)buffer中所存的A的子塊發(fā)送到其左鄰處理器中endifEnd當(dāng)算法執(zhí)行在布乂布的二維網(wǎng)孔上時(shí)，若使用切通CT選路法，算法18.7第(2)步的循環(huán)移位時(shí)間n2n2為2(ts卅w)/,第(4)步的單步移位時(shí)間為2(ts+tw)Jp、運(yùn)算時(shí)間為n3/p。所以在一維網(wǎng)孔pp上Cannon乘法的并行運(yùn)行時(shí)間為Tp=4(ts+tw吧)Jp+n3/poyp簡單劃分的矩陣相乘源代碼和Cannon相乘源代碼見附件。實(shí)驗(yàn)四八皇后問題一、實(shí)驗(yàn)?zāi)康?1)八皇后問題是計(jì)算機(jī)中經(jīng)典智能搜索問題。掌握在MPI虛擬

30、機(jī)上進(jìn)行八皇后問題求解算法及其程序設(shè)計(jì)、運(yùn)行。(2)在分析八皇后的并行算法和MPI源程序基礎(chǔ)上。查找相關(guān)參考資料，對(duì)于一般的n皇后問題，設(shè)計(jì)其并行算法及其程序，并運(yùn)行結(jié)果。二、實(shí)驗(yàn)內(nèi)容在單機(jī)或多機(jī)上完成8、12、16、32等n皇后問題求解，并比較運(yùn)行時(shí)間，計(jì)算加速比。三、實(shí)驗(yàn)步驟1、了解八皇后問題及其串行算法所謂八皇后問題(EightQueensProblem),是在8*8格的棋盤上，放置8個(gè)皇后。要求每行每列放一個(gè)皇后，而且每一條對(duì)角線和每一條反對(duì)角線上最多只能有一個(gè)皇后，即對(duì)同時(shí)放置在棋盤的任意兩個(gè)皇后(i1,1)和(i2,j2),不允許(i1-i2)=(j1-j2)或者(i1+%)=4+

31、j2)的情況出現(xiàn)。八皇后問題的串行解法為如下的遞歸算法。算法4.1八皇后問題的串行遞歸算法/*從chessboard的第row行開始放置皇后*/procedurePlaceQueens(chessboard,row)Beginifrow>8thenOutputResult(chessboard)/*結(jié)束遞歸并輸出結(jié)果*/elseforcol=1to8do/*判斷是否有列、對(duì)角線或反對(duì)角線沖突*/(1) no_collision=true(2) i=1(3) whileno_collisionandi<rowdo(3.(1) ifcollides(i,chessboardi,row,

32、col)thenno_collision=falseendif(3.(2) i=i+1endwhile(4) ifno_collisionthen(4.(1) chessboardrow=col/*在當(dāng)前位置放置一個(gè)皇后*/(4.(2) go(step+1,place)/*遞歸地從下一行開始放置皇后*/endifendforendifEnd/*PlaceQueens*/2、八皇后問題的并行算法該算法是將八皇后所有可能的解置于相應(yīng)的棋盤上，主進(jìn)程負(fù)責(zé)生成初始化的棋盤，并將該棋盤發(fā)送到某個(gè)空閑的從進(jìn)程，由該從進(jìn)程求出該棋盤上滿足初始化條件的所有的解。這里，我們假10定主進(jìn)程只初始化棋盤的前兩列，即

33、在棋盤的前兩列分別放上2個(gè)皇后，這樣就可以產(chǎn)生8*8=64個(gè)棋盤。算法4.2八皇后問題的并行算法(1)主進(jìn)程算法procedureEightQueensMasterBegin(1) active_slaves=n(2) whileactive_slaves>0do(2.(1) 個(gè)從進(jìn)程i接收信號(hào)signal(2.(2) ifsignal=Accomplishedthen從從進(jìn)程i接收并記錄解endif(2.(3) ifhas_more_boardsthen(i)向從進(jìn)程i發(fā)送NewTask信號(hào)(ii)向從進(jìn)程i發(fā)送一個(gè)新棋盤else(i)向從進(jìn)程i發(fā)送Terminate信號(hào)(ii)act

34、ive_slaves=active_slaves-1endifendwhileEnd/*EightQueensMaster*/(2)從進(jìn)程算法procedureEightQueenSlaveBegin(1)向主進(jìn)程發(fā)送Ready信號(hào)(2) finished=false(3) whilenotfinisheddo(3.(1) 進(jìn)程接收信號(hào)signal(3.(2) ifsignal=NewTaskthen(i)從主進(jìn)程接收新棋盤(11) if新棋盤合法then在新棋盤的基礎(chǔ)上找出所有合法的解，并將解發(fā)送給主進(jìn)程endifelse/*signal=Terminate*/finished=trueen

35、difendwhileEnd/*日ghtQueenSlave*/八皇后問題源代碼見附件。11實(shí)驗(yàn)五快速排序一、實(shí)驗(yàn)?zāi)康目焖倥判蚴怯?jì)算機(jī)中常用的、典型非數(shù)值算法。熟悉并掌握在MPI虛擬機(jī)上進(jìn)行快速排序的算法及其程序設(shè)計(jì)、運(yùn)行。二、實(shí)驗(yàn)內(nèi)容在單機(jī)或多機(jī)上完成快速排序，并比較運(yùn)行時(shí)間，計(jì)算加速比，并與枚舉排序?qū)Ρ确治鼋Y(jié)果。三、實(shí)驗(yàn)步驟1、了解快速排序及其串行算法快速排序(QuickSort)是一種最基本的排序算法，它的基本思想是：在當(dāng)前無序區(qū)R1,n中取一個(gè)記錄作為比較的“基準(zhǔn)”(一般取第一個(gè)、最后一個(gè)或中間位置的元素)，用此基準(zhǔn)將當(dāng)前的無序區(qū)R1,n劃分成左右兩個(gè)無序的子區(qū)R1,i-1和Ri,n(

36、1<i<n),且左邊的無序子區(qū)中記錄的所有關(guān)鍵字均小于等于基準(zhǔn)的關(guān)鍵字，右邊的無序子區(qū)中記錄的所有關(guān)鍵字均大于等于基準(zhǔn)的關(guān)鍵字；當(dāng)R1,i-1和Ri,n非空時(shí)，分別對(duì)它們重復(fù)上述的劃分過程，直到所有的無序子區(qū)中的記錄均排好序?yàn)橹?。算?.1單處理機(jī)上快速排序算法輸入：無序數(shù)組data1,n輸出：有序數(shù)組data1,nBegincallprocedurequicksort(data,1,n)Endprocedurequicksort(data,i,j)Begin(1) if(i<j)then(1.(1) =partition(data,i,j)(1.(2) quicksort(

37、data,i,r-1);(1.(3) quicksort(data,r+1,j);endifEndprocedurepartition(data,k,l)Beginpivo=datal(2) i=k-1(3) forj=ktol-1doifdataj<pivotheni=i+1exchangedataianddatajendifendfor(4) exchangedatai+1anddatal(5) returni+1End12快速排序算法的性能主要決定于輸入數(shù)組的劃分是否均衡，而這與基準(zhǔn)元素的選擇密切相關(guān)。在最壞的情況下，劃分的結(jié)果是一邊有n-1個(gè)元素，而另一邊有0個(gè)元素(除去被選中的

38、基準(zhǔn)元素)如果每次遞歸排序中的劃分都產(chǎn)生這種極度的不平衡，那么整個(gè)算法的復(fù)雜度將是©(n2)。在最好的情況下，每次劃分都使得輸入數(shù)組平均分為兩半，那么算法的復(fù)雜度為O(nlogn)。在一般的情況下該算法仍能保持O(nlogn)的復(fù)雜度，只不過其具有更高的常數(shù)因子。2、快速排序的并行算法快速排序算法并行化的一個(gè)簡單思想是，對(duì)每次劃分過后所得到的兩個(gè)序列分別使用兩個(gè)處理器完成遞歸排序。例如對(duì)一個(gè)長為n的序列，首先劃分得到兩個(gè)長為n/2的序列，將其交給兩個(gè)處理器分別處理；而后進(jìn)一步劃分得到四個(gè)長為n/4的序列，再分別交給四個(gè)處理器處理；如此遞歸下去最終得到排序好的序列。當(dāng)然這里舉的是理想的

39、劃分情況，如果劃分步驟不能達(dá)到平均分配的目的，那么排序的效率會(huì)相對(duì)較差。算法13.4中描述了使用2m個(gè)處理器完成對(duì)n個(gè)輸入數(shù)據(jù)排序的并行算法。算法5.2快速排序并行算法輸入：無序數(shù)組data1,n,使用的處理器個(gè)數(shù)2m輸出：有序數(shù)組data1,nBeginpara_quicksort(data,1,n,m,0)Endprocedurepara_quicksort(data,i,j,m,id)Begin(1) if(j-i)<korm=0then(1.(1) Pidcallquicksort(data,i,j)else(1.(2) Pid:r=patrition(data,i,j)，.一_

40、-_m-1(1.(3) Pidsenddatar+1,m-1toPid+2(1.(4) para_quicksort(data,i,r-1,m-1,id)(1.(5) para_quicksort(data,r+1,j,m-1,id+2m-1)(1.(6) Pid+2m-1senddatar+1,m-1backtoPidendifEnd在最優(yōu)的情況下該并行算法形成一個(gè)高度為logn的排序樹，其計(jì)算復(fù)雜度為O(n),通信復(fù)雜度也為O(n)。同串行算法一樣，在最壞情況下其計(jì)算復(fù)雜度降為O(n2)。正常情況下該算法的計(jì)算復(fù)雜度也為O(n),只不過具有更高的常數(shù)因子?？焖倥判騿栴}源代碼見附件13實(shí)驗(yàn)六

41、快速傅氏變換、實(shí)驗(yàn)?zāi)康拈L期以來，快速傅氏變換(FastFourierTransform,FFT)和離散小波變換(DiscreteWaveletTransform,DWT)在數(shù)字信號(hào)處理、石油勘探、地震預(yù)報(bào)、醫(yī)學(xué)斷層診斷、編碼理論、量子物理及概率論等領(lǐng)域中都得到了廣泛的應(yīng)用。各種FFT和DWT算法不斷出現(xiàn)，成為數(shù)值代數(shù)方面最活躍的一個(gè)研究領(lǐng)域，而其意義遠(yuǎn)遠(yuǎn)超過了算法研究的范圍，進(jìn)而為諸多科技領(lǐng)域的研究打開了一個(gè)嶄新的局面。掌握在MPI虛擬機(jī)上進(jìn)行快速傅氏變換求解算法及其程序設(shè)計(jì)、運(yùn)行。二、實(shí)驗(yàn)內(nèi)容在單機(jī)或多機(jī)上完成快速傅氏變換問題求解，并比較運(yùn)行時(shí)間，計(jì)算加速比。三、實(shí)驗(yàn)步驟1、了解快速傅里葉變

42、換FFT離散傅里葉變換是20世紀(jì)60年代是計(jì)算復(fù)雜性研究的主要里程碑之一，1965年Cooley和Tukey所研究的計(jì)算離散傅里葉變換(DiscreteFourierTest)的快速傅氏變換(FFT)將計(jì)算量從0(n2)下降至Onlogn),推進(jìn)了FFT更深層、更廣法的研究與應(yīng)用。FFT算法有很多版本，但大體上可分為兩類：迭代法和遞歸法，本實(shí)驗(yàn)采用迭代法。b0,b1,bn-1為離散傅里葉變換的結(jié)2rWn=e-,實(shí)際上，上式可寫成矩陣W和向假定a0,a1,an-1為一個(gè)有限長的輸入序列,n1果序列，則有：bk=£akWnkm(kH,1,2，,n1),其中m衛(wèi)量a的乘積形式：一-b01Iw0w0w0w0為1b1w0w1w2wn1a1b2aw0w2w4w2(n)amm+ma2b一w0w(n)w2(n)“w(n二)(n)an(公式6.1)般的n階矩陣和n維向量相乘，計(jì)算時(shí)間復(fù)雜度為n2,但由于W是一種特殊矩陣，故可以降低計(jì)算量。FFT的計(jì)算流圖如圖6.1所示，其串行算法如下:算法6.1單處理器上的FFT迭代算法輸入：a=(a0,a1,an-1)輸出：b=(b0,b1,bn-1)Begin(1)fork=0ton-1dock=akendfor(2)forh=logn-1downto0doh(2.(1) p=2(2