研究生課程作業(yè)《并行程序設(shè)計(jì)原理》桶排序?qū)崿F(xiàn)

《并行程序設(shè)計(jì)原理》作業(yè)要求：用MPI語言實(shí)現(xiàn)課本89頁圖4-10所示的并行桶排序（必須采用此算法），數(shù)組大小和處理器數(shù)不限，數(shù)組中所有元素的取值區(qū)間為[0,1]。完成下面并行程序中的bucket_sort函數(shù)，MPI程序中要有簡單的中文注釋。在192.168.150.197上測試完成表1和表2的相關(guān)測試（數(shù)據(jù)必須準(zhǔn)確），并對表1和表2作簡單的分析。評分標(biāo)準(zhǔn)：在MPI程序正確的前提下，主要根據(jù)程序執(zhí)行時間的快慢來評分。并行程序：#include<mpi.h>#include<ctime>#include<algorithm>#include<iostream>usingnamespacestd;intrank,size;voidbucket_sort(double*a,intn){ inti; intbucket; /*幾號小桶*/ intbigBucketSize=n/size; /*大桶大小*/ intsortSize=0; /*待排序大桶數(shù)組大小*/ int*sdispls; /*發(fā)送步長*/ int*rdispls; /*接受步長*/ int*sendcnts; /*發(fā)送的各小桶大小*/ int*recvcnts; /*接受的各小桶大小*/ double*sourcebuf; /*大桶數(shù)組*/ double*sendbuf; /*Alltoall發(fā)送數(shù)組*/ double*recvbuf; /*Alltoall接收數(shù)組*/ sourcebuf=newdouble[bigBucketSize]; /*將數(shù)據(jù)平均分散到各處理機(jī)*/ MPI_Scatter(a,bigBucketSize,MPI_DOUBLE,sourcebuf,bigBucketSize,MPI_DOUBLE,0,MPI_COMM_WORLD); sdispls=newint[size]; rdispls=newint[size]; sendcnts=newint[size]; recvcnts=newint[size]; sendbuf=newdouble[n]; recvbuf=newdouble[n]; for(i=0;i<size;i++){ sendcnts[i]=0; } /*設(shè)置發(fā)送緩沖區(qū)數(shù)據(jù)*/ for(i=0;i<bigBucketSize;i++){ /*計(jì)算放置到幾號小桶*/ bucket=sourcebuf[i]==size?(size-1):(int)(sourcebuf[i]*size); sendbuf[bucket*bigBucketSize+sendcnts[bucket]]=sourcebuf[i]; sendcnts[bucket]++; } /*交換各個處理器的發(fā)送數(shù)據(jù)大小，來計(jì)算接收數(shù)據(jù)大小*/ MPI_Alltoall(sendcnts,1,MPI_INT,recvcnts,1,MPI_INT,MPI_COMM_WORLD); /*計(jì)算發(fā)送步長和接收步長*/ sdispls[0]=0; rdispls[0]=0; for(i=1;i<size;i++){ sdispls[i]=sdispls[i-1]+bigBucketSize; rdispls[i]=rdispls[i-1]+recvcnts[i-1]; } /*計(jì)算待排序數(shù)據(jù)總數(shù)*/ sortSize=rdispls[size-1]+recvcnts[size-1]; /*交換待排序數(shù)據(jù)*/ MPI_Alltoallv(sendbuf,sendcnts,sdispls,MPI_DOUBLE,recvbuf,recvcnts,rdispls,MPI_DOUBLE,MPI_COMM_WORLD); /*對接收到的數(shù)據(jù)排序*/ sort(recvbuf,recvbuf+sortSize); /*1.收集各個處理器的數(shù)據(jù)大小，用于計(jì)算接收步長*/ MPI_Gather(&sortSize,1,MPI_INT,recvcnts,1,MPI_INT,0,MPI_COMM_WORLD); /*計(jì)算接收步長*/ rdispls[0]=0; for(i=1;i<size;++i){rdispls[i]=rdispls[i-1]+recvcnts[i-1];} /*2.收集最后的數(shù)據(jù)*/ MPI_Gatherv(recvbuf,sortSize,MPI_DOUBLE,a,recvcnts,rdispls,MPI_DOUBLE,0,MPI_COMM_WORLD); delete[]sourcebuf; delete[]sdispls; delete[]rdispls; delete[]sendcnts; delete[]recvcnts; delete[]sendbuf; delete[]recvbuf;}voidmain(intargv,char*argc[]){ intn=10000000; doubleduration=0,sduration=0; double*a,*b; MPI_Init(&argv,&argc); MPI_Comm_rank(MPI_COMM_WORLD,&rank); MPI_Comm_size(MPI_COMM_WORLD,&size); if(rank==0) { a=newdouble[n]; b=newdouble[n]; for(inti=0;i<n;i++) a[i]=b[i]=rand()/double(RAND_MAX); duration-=MPI_Wtime(); } bucket_sort(a,n); if(rank==0) { duration+=MPI_Wtime(); sduration-=MPI_Wtime(); sort(b,b+n); sduration+=MPI_Wtime(); for(inti=0;i<n;i++) if(a[i]!=b[i]) { cout<<"error!"<<endl; break; } cout<<"串行執(zhí)行時間："<<sduration<<endl; cout<<"并行執(zhí)行時間："<<duration<<endl; cout<<"加速比："<<sduration/duration<<endl; cout<<"效率："<<sduration/duration/size<<endl; delete[]a; delete[]b; } MPI_Finalize();}表1并行桶排序程序在不同處理器數(shù)下的執(zhí)行時間、加速比和效率(數(shù)組大小為107)處理器數(shù)12481632執(zhí)行時間(秒)1.620250.8913950.5279920.3339750.2626810.263484加速比0.8115031.473932.512134.007484.972324.98271效率0.8115030.7369660.6280320.5009340.310770.15571分析：在處理器少于16個之內(nèi)，隨著處理器的增加，執(zhí)行時間越來越少，加速比不斷增大。但是增加到16個處理器之后，執(zhí)行時間減少幅度不大，由于處理器越多處理器之間的同步和數(shù)據(jù)傳輸所消耗時間也越多。 另外，隨著處理器的增加，單個處理器的效率不斷下降，這也是由于處理器越多處理器之間的同步和數(shù)據(jù)傳輸所消耗時間也越多。表2并行桶排序程序在不同數(shù)組大小下的執(zhí)行時間、加速比和效率(處理器數(shù)為8)