并行报告双面

6.附录6.1基于OpenMP的并行程序设计6.1.1代码及注释#includestdafx.h#includestdio.h#includetime.h#includewindows.h#includeomp.h#includemath.h#defineNUM_THREADS2#defineSIZE100intxh_a[SIZE],xh_d[SIZE],xh_b[SIZE/2],xh_c[SIZE/2];voidquick_sort(intxh_s[],intl,intr){if(lr){inti=l,j=r,x=xh_s[l];while(ij){while(ij&&xh_s[j]=x)//从右向左找第一个小于x的数j--;if(ij)xh_s[i++]=xh_s[j];while(ij&&xh_s[i]x)//从左向右找第一个大于等于x的数i++;if(ij)xh_s[j--]=xh_s[i];}xh_s[i]=x;quick_sort(xh_s,l,i-1);//递归调用quick_sort(xh_s,i+1,r);}}int_tmain(intargc,_TCHAR*argv[]){printf(%d个随机数的排序\n,SIZE);omp_set_num_threads(2);inti=0,j=0,k=0,l=0;longn=SIZE/2;srand((unsigned)time(NULL));//初始化随机数种子for(i=0;iSIZE;i++)xh_a[i]=rand();clock_txh_t1,xh_t2;#pragmaompparallelforprivate(i)for(i=0;in;i++){xh_b[i]=xh_a[i];xh_c[i]=xh_a[i+n];}xh_t1=clock();#pragmaompparallelsections//快速排序的并行，分两个线程{#pragmaompsectionquick_sort(xh_b,0,n-1);//对b[]排序#pragmaompsectionquick_sort(xh_c,0,n-1);//对c[]排序}while(ln&&jn){if(xh_b[l]xh_c[j]){xh_d[k]=xh_b[l];l++;k++;}else{xh_d[k]=xh_c[j];j++;k++;}}while(ln){xh_d[k]=xh_b[l];l++;k++;}while(jn){xh_d[k]=xh_c[j];j++;k++;}xh_t2=clock();printf(paralleltime=%d\n,(xh_t2-xh_t1));xh_t1=clock();quick_sort(xh_a,0,SIZE-1);xh_t2=clock();printf(serialtime=%d\n,(xh_t2-xh_t1));system(pause);return0;}6.1.2执行结果截图（体现串行时间、并行时间和加速比）（1）小数据量验证正确性的执行结果图1（2）大数据量获得较好加速比的执行结果图2图36.1.3遇到的问题及解决方案（1）问题一错误代码及后果while(in&&jn){if(xh_b[i]xh_c[j]){xh_d[k]=xh_b[i];i++;k++;}……}while(in){xh_d[k]=xh_b[i];i++;k++;}正确代码while(ln&&jn){if(xh_b[l]xh_c[j]){xh_d[k]=xh_b[l];l++;k++;}……}while(ln){xh_d[k]=xh_b[l];l++;k++;}分析错误的使用了共享变量i,因为i的值在前面已经赋过值，值不是0,使得i的值不是从0开始，使得排序数组的靠后的几个随机数全变成了0，解决方法：重新给i赋值为0，或替换变量，或将归并排序封装成函数，然后调用。6.2基于MPI的并行程序设计6.1.1代码及注释（变量名名字首字母开头）#includestdafx.h#includestdio.h#includempi.h#includewindows.h#includetime.h#includemath.h#defineSIZE10000000intxh_a[SIZE],xh_d[SIZE],xh_b[SIZE/2],xh_c[SIZE/2],xh_s[SIZE/2];voidquick_sort(intxh_s[],intl,intr){if(lr){inti=l,j=r,x=xh_s[l];while(ij){while(ij&&xh_s[j]=x)//从右向左找第一个小于x的数j--;if(ij)xh_s[i++]=xh_s[j];while(ij&&xh_s[i]x)//从左向右找第一个大于等于x的数i++;if(ij)xh_s[j--]=xh_s[i];}xh_s[i]=x;quick_sort(xh_s,l,i-1);//递归调用quick_sort(xh_s,i+1,r);}}voidm_quick_sort(intxh_a[],intmyid,intl,intr){intm,i;m=r/2;if(myid==0){for(i=0;im;i++)xh_s[i]=xh_a[i];}if(myid==1){for(i=0;im;i++)xh_s[i]=xh_a[i+m];}m=m-1;if(lm){inti=l,j=m,x=xh_s[l];while(ij){while(ij&&xh_s[j]=x)//从右向左找第一个小于x的数j--;if(ij)xh_s[i++]=xh_s[j];while(ij&&xh_s[i]x)//从左向右找第一个大于等于x的数i++;if(ij)xh_s[j--]=xh_s[i];}xh_s[i]=x;quick_sort(xh_s,l,i-1);//递归调用quick_sort(xh_s,i+1,m);}m=m+1;}voidmain(intargc,char*argv[]){intmyid,numprocs;intm=SIZE;intn=SIZE/2;doublestartwtime,endwtime;inti=0,j=0,k=0,l=0;srand((unsigned)time(NULL));//初始化随机数种子for(i=0;iSIZE;i++)xh_a[i]=rand();MPI_Statusstatus;MPI_Init(&argc,&argv);MPI_Comm_size(MPI_COMM_WORLD,&numprocs);MPI_Comm_rank(MPI_COMM_WORLD,&myid);if(numprocs==1){startwtime=MPI_Wtime();quick_sort(xh_a,0,SIZE-1);endwtime=MPI_Wtime();printf(time=%f\n,endwtime-startwtime);}elseif(numprocs==2){if(myid==0){printf(%d个随机数的排序\n,SIZE);startwtime=MPI_Wtime();MPI_Bcast(&m,1,MPI_INT,0,MPI_COMM_WORLD);MPI_Send(xh_a,SIZE,MPI_INT,1,99,MPI_COMM_WORLD);}if(myid==1)MPI_Recv(xh_a,SIZE,MPI_INT,0,99,MPI_COMM_WORLD,&status);m_quick_sort(xh_a,myid,0,SIZE);if(myid==1){for(i=0;iSIZE/2;i++)xh_c[i]=xh_s[i];MPI_Send(xh_c,SIZE/2,MPI_INT,0,99,MPI_COMM_WORLD);}if(myid==0){for(i=0;iSIZE/2;i++)xh_b[i]=xh_s[i];MPI_Recv(xh_c,SIZE/2,MPI_INT,MPI_ANY_SOURCE,99,MPI_COMM_WORLD,&status);while(ln&&jn){if(xh_b[l]xh_c[j]){xh_d[k]=xh_b[l];l++;k++;}else{xh_d[k]=xh_c[j];j++;k++;}}while(ln){xh_d[k]=xh_b[l];l++;k++;}while(jn){xh_d[k]=xh_c[j];j++;k++;}/*for(i=0;iSIZE;i++)printf(%d,xh_d[i]);printf(\n);*/endwtime=MPI_Wtime();printf(paralleltime=%f\n,endwtime-startwtime);}startwtime=MPI_Wtime();if(myid==0){quick_sort(xh_a,0,SIZE-1);endwtime=MPI_Wtime();printf(serialtime=%f\n,endwtime-startwtime);}}elseprintf(线程数超出指定范围\n);MPI_Finalize();//结束计算}6.2.2执行结果截图（体现串行时间、并行时间和加速比）（1）小数据量验证正确性的执行结果图4（2）大数据量获得较好加速比的执行结果1000000个数的快速排序，加速比是0.174506/0.088146=1.98图510000000个数的快速排序，加速比是4.581212/1.627370=2.82图66.2.3遇到的问题及解决方案（1）问题一错误代码及后果intm,i;m=r/2;if(myid==0){for(i=0;im;i++)xh_s[i]=xh_a[i];}if(myid==1){for(i=0;im;i++)xh_s[i]=xh_a[i+m];}m=m-1;if(lm){………………}xh_s[i]=x;quick_sort(xh_s,l,i-1);//递归调用quick_sort(xh_s,i+1,m);}}正确代码intm,i;m=r/2;if(myid==0){for(i=0;im;i++)xh_s[i]=xh_a[i];}if(myid==1){for(i=0;im;i++)xh_s[i]=xh_a[i+m];}m=m-1;if(lm){………………}xh_s[i]=x;quick_sort(xh_s,l,i-1);//递归调用quick_sort(xh_s,i+1,m);}m=m+1;}分析变量m代表要排序数组长度的一半，由于数组从序号0开始，而在排序中需要m-1的值。排序结束后，必须要将m的值加1，才能将整个数组完整输出，否则会丢掉一个数。6.3基于Java的并行程序设计6.3.1代码及注释importjava.util.Scanner;publicclassQuicksortextendsThread{publicint[]array;privateint[]array1;privateint[]array2;privateintstart;privateintend;publicQuicksort(int[]array,intstart,intend){super();this.array=array;this.start=start;this.end=end;}publicQuicksort(int[]array,int[]array1,int[]array2,intn){this.array=array;this.array1=array1;this.array2=array;}publicvoidrun(){quick_sort(array,star