mpi冒泡排序并行化

北京科技大学计算机与通信工程学院实验报告实验名称:冒泡排序的并行化学生姓名：朱帅专业：计算机科学与技术班级：计1203学号：41255072指导教师：李建江实验成绩：实验地点：机电楼301实验时间：2015年4月8日一、实验目的与实验要求1、实验目的（1）学会将串行程序改为并行程序。(2)学会mpich2的使用。(3)学会openmp的配置。（4）mpi与openmp之间的比较。2、实验要求（1）将串行冒泡程序局部并行化，以降低时间消耗。(2)理论上求出时间复杂度之比，根据结果得出时间消耗之比，进行比对分析。二、实验设备（环境）及要求Vs2013，mpich2三、实验内容与步骤1、实验一mpi并行（1）实验内容1、写出一个冒泡排序程序，求出其时间复杂度，并运行得到相应的时间消耗。2、将冒泡程序改为mpi并行程序：将全部需要排序的数分成4等份，分给四个进程一起冒泡，最后将所得的结果归到一个进程，进行归并排序，得到结果，得到时间消耗。算出时间复杂度。3、对得出的结果进行讨论与分析。（2）主要步骤1、串行冒泡程序时间复杂度：取所要排序的数的个数为n个，时间复杂度为n*n/2。代码实现：//maopao.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includestdlib.h#includetime.hconstintARRAY_SIZE=120000;intmain(intargc,char*argv[]){intzongshu[ARRAY_SIZE];srand(10086);time_tnow_time,end_time;for(inti=0;iARRAY_SIZE;i++){zongshu[i]=rand();}now_time=time(NULL);for(inti=0;iARRAY_SIZE;i++){for(intj=ARRAY_SIZE-1;ji;j--){if(zongshu[j]=zongshu[j-1]){intz=zongshu[j-1];zongshu[j-1]=zongshu[j];zongshu[j]=z;}}}end_time=time(NULL);longshijian=end_time-now_time;for(inti=0;iARRAY_SIZE;i++){printf(%d,zongshu[i]);}printf(所用时间：%ld,shijian);while(true);}2、并行程序时间复杂度：取所要排序的数的个数为n个，进程数为m个。时间复杂度：(（n/m）*(n/m)/2)+n+4*n。代码实现：//MPITest.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includempi.h#includestdio.h#includemath.h#includestdlib.h#defineSIZE4//进程数constintARRAY_SIZE=30000;//每个进程分配的个数intshuzu[SIZE][ARRAY_SIZE];intzonghanshu[SIZE][ARRAY_SIZE];doubleendwtime;voidScatter_1(int);intmain(intargc,char*argv[]){intmyid;MPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&myid);Scatter_1(myid);MPI_Finalize();}voidScatter_1(intmyid){intnumtasks;srand(10086);for(inti=0;iSIZE;i++){for(intj=0;jARRAY_SIZE;j++){shuzu[i][j]=rand();}}//随机生成数组intxiaopaixu[ARRAY_SIZE];doublestartwtime=MPI_Wtime();MPI_Comm_size(MPI_COMM_WORLD,&numtasks);if(numtasks==SIZE){MPI_Scatter(shuzu,ARRAY_SIZE,MPI_INT,xiaopaixu,ARRAY_SIZE,MPI_INT,0,MPI_COMM_WORLD);for(inti=0;iARRAY_SIZE;i++){for(intj=ARRAY_SIZE-1;ji;j--){if(xiaopaixu[j]=xiaopaixu[j-1]){intz=xiaopaixu[j-1];xiaopaixu[j-1]=xiaopaixu[j];xiaopaixu[j]=z;}}}//每个进程里的冒泡排序MPI_Gather(xiaopaixu,ARRAY_SIZE,MPI_INT,zonghanshu,ARRAY_SIZE,MPI_INT,0,MPI_COMM_WORLD);inttime[SIZE];for(inti=0;iSIZE;i++){time[i]=0;}inta[SIZE];intzongpaixu2[ARRAY_SIZE*SIZE];for(intj=ARRAY_SIZE*SIZE-1;j=0;j--){for(intk=0;kSIZE;k++){if(time[k]=ARRAY_SIZE){a[k]=0;}else{a[k]=zonghanshu[k][ARRAY_SIZE-time[k]-1];}}intx=a[0];for(inti=1;iSIZE;i++){if(a[i]x){x=a[i];}}for(intn=0;nSIZE;n++){if(x==a[n]){time[n]=time[n]+1;break;}}zongpaixu2[j]=x;}endwtime=MPI_Wtime();if(myid);elsefor(inti=0;iSIZE*ARRAY_SIZE;i++){printf(%d,zongpaixu2[i]);}}if(myid);elseprintf(wallclocktime=%f\n,endwtime-startwtime);}2、实验2在实验一的基础上将程序改为openmp。代码实现：（水平不高，写的程序通用性不好，只写了四线程的）//Openmp.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includestdio.h#includemath.h#includestdlib.h#includetime.h#includeomp.h#defineSIZE4constintARRAY_SIZE=12000;intshuzu[SIZE][ARRAY_SIZE];intxiaopaixu1[ARRAY_SIZE];intxiaopaixu2[ARRAY_SIZE];intxiaopaixu3[ARRAY_SIZE];intxiaopaixu4[ARRAY_SIZE];intzonghanshu[SIZE][ARRAY_SIZE];intzongpaixu[ARRAY_SIZE*SIZE];voidxiaohansu(int*A,intl,intu){for(inti=l;iu;i++){for(intj=u-1;ji;j--){if(A[j]=A[j-1]){intz=A[j-1];A[j-1]=A[j];A[j]=z;}}}}//每个线程排序intmain(intargc,char*argv[]){intt1,t2;inti;intid;clock_tnow_time,end_time;srand(10086);for(inti=0;iSIZE;i++){for(intj=0;jARRAY_SIZE;j++){shuzu[i][j]=rand();}}//随机生成数组now_time=clock();#pragmaompparalleldefault(none)shared(shuzu,xiaopaixu1,xiaopaixu2,xiaopaixu3,xiaopaixu4,ARRAY_SIZE)private(i){#pragmaompforfor(i=0;iARRAY_SIZE;i++)//这个for循环是并行的,将数组分为四份{xiaopaixu1[i]=shuzu[0][i];xiaopaixu2[i]=shuzu[1][i];xiaopaixu3[i]=shuzu[2][i];xiaopaixu4[i]=shuzu[3][i];}}#pragmaompparalleldefault(none)shared(xiaopaixu1,xiaopaixu2,xiaopaixu3,xiaopaixu4,ARRAY_SIZE){#pragmaompparallelsections{#pragmaompsectionxiaohansu(xiaopaixu1,0,ARRAY_SIZE-1);//排序#pragmaompsectionxiaohansu(xiaopaixu2,0,ARRAY_SIZE);#pragmaompsectionxiaohansu(xiaopaixu3,0,ARRAY_SIZE);#pragmaompsectionxiaohansu(xiaopaixu4,0,ARRAY_SIZE);}}for(i=0;iARRAY_SIZE;i++)//合到一份{zonghanshu[0][i]=xiaopaixu1[i];zonghanshu[1][i]=xiaopaixu2[i];zonghanshu[2][i]=xiaopaixu3[i];zonghanshu[3][i]=xiaopaixu4[i];}inttime[SIZE];for(inti=0;iSIZE;i++){time[i]=0;}inta[SIZE];for(intj=ARRAY_SIZE*SIZE-1;j=0;j--){for(intk=0;kSIZE;k++){if(time[k]=ARRAY_SIZE){a[k]=0;}else{a[k]=zonghanshu[k][ARRAY_SIZE-time[k]-1];}}intx=a[0];for(inti=1;iSIZE;i++){if(a[i]x){x=a[i];}}for(intn=0;nSIZE;n++){if(x==a[n]){time[n]=time[n]+1;break;}}zongpaixu[j]=x;}//归并end_time=clock();doubleshijian=end_time-now_time;for(inti=0;iSIZE*ARRAY_SIZE;i++){printf(%d,zongpaixu[i]);}printf(所用时间：%lf,shijian/CLK_TCK);while(true);}四：实验结果与分析Mpi:串行Mpi1.2万2.4万3.6万4.8万6.0万7.2万串行（秒）0.4411.7663.9516.87710.46914.6876线（秒）0.0290.1080.2420.4350.6560.9404线（秒）0.0350.1510.3390.6150.9691.4092线（秒）0.1190.5021.1082.0403.1214.516从表中可以看出4线程的时候，并行程序的速度是串行程序速度的十倍之多，而理论上大概8倍。这就跟改的程序有关。在并行程序中，最后采用的是归并，由此，发生了这些奇妙的情况：实则本身的算法就比冒泡优一些，但又不能只采用冒泡算法，那样在最后又来个冒泡，其程序就没有意义了。Openmp：这是4.8万个数排序的结果，可以看出用了2.876秒，比MPI慢了四倍之多，这可能是程序的不合理，带来了多余的时间消耗（通信）。但比串行还是要快很多。五：结论（讨论）1、实验结论1、就这冒泡排序改为并行的，虽然