MPI排序算法编程

一．实验要求1.写出原算法串行处理的思路或流程2.说明算法并行化的思路3.并且写出算法流程，最终编码实现二．实验环境硬件环境：VirtualPC2007(XP)软件：VC++6.0；mpich.nt.1.2.5三．实验步骤和结果1.原插入排序原理插入排序过程示例将n个元素的数列分为已有序和无序两个部分，如下所示：{，{a2，a3，a4，…,an}}{{a1(1)，a2(1)}，{a3(1)，a4(1)…,an(1)}}…{{a1(n-1)，a2(n-1)，…},{an(n-1)}}每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。2.并行化思路上文所说的插入排序在数据量大的情况下，运算量比较大，因此适合用并行计算来提高效率，下面是并行化算法的思路2.1首先需要输入排序元素的个数，并输入需要排序的原色，用一个数组保存起来。2.2将数组按照进程的数目平均分段，每个进程各领取一段去做插入排序。2.3将进程排成一个二叉树的结构，每一个进程节点先将下面两个进程节点排好的数组接收进来，做一次归并排序。再用这个归并排序结果跟进程节点再做一次归并排序。2.4循环执行，直到树的根节点为止，排序完成。2.5输出并行排序结果3.程序运行结果4.源代码//此算法实现插入排序的并行运算//陈仲策2007034743011#includestdio.h#includempi.h#includetime.h#includestdlib.hint*merge(int*v1,intn1,int*v2,intn2);voidswap(int*v,inti,intj);voidsort(int*v,intn);doublestartT,stopT;doublestartTime;int*merge(int*v1,intn1,int*v2,intn2){inti,j,k;int*result;result=(int*)malloc((n1+n2)*sizeof(int));i=0;j=0;k=0;while(in1&&jn2)if(v1[i]v2[j]){result[k]=v1[i];i++;k++;}else{result[k]=v2[j];j++;k++;}if(i==n1)while(jn2){result[k]=v2[j];j++;k++;}elsewhile(in1){result[k]=v1[i];i++;k++;}returnresult;}/*插入排序算法*/voidInsertionSort(int*v,intn){inti;intj;inttemp;for(i=1;in;i++){temp=v[i];for(j=i;j0&&tempv[j-1];j--){v[j]=v[j-1];}v[j]=temp;}}/*主函数*/voidmain(intargc,char**argv){intm,n=500;intcount;int*data;int*buf;int*other;intid,p;ints;inti;intstep;MPI_Statusstatus;/*MPI初始化*/MPI_Init(&argc,&argv);/*确定自己的进程标志号id*/MPI_Comm_rank(MPI_COMM_WORLD,&id);/*组内进程数是p*/MPI_Comm_size(MPI_COMM_WORLD,&p);/*根处理机（id=0）获取必要的信息，并协调各处理机工作*/if(id==0){scanf(%d,&count);//输入要排序的元素的个数n=count;int*a=(int*)malloc(count*sizeof(int));;//定义一个存放输入整数的指针，并分配空间for(intj=0;jcount;j++){scanf(%d,,&a[j]);//将输入的整数存入动态数组}intr;s=n/p;r=n%p;data=(int*)malloc((n+p-r)*sizeof(int));for(i=0;in;i++)data[i]=a[i];if(r!=0){for(i=n;in+p-r;i++)data[i]=0;s=s+1;}startT=clock();/*从根处理机将数据序列广播到其他处理器*//*1表示传送的输入缓冲中的元素的个数*//*MPI_INT表示输入元素的类型*//*0表示跟进程的id*/MPI_Bcast(&s,1,MPI_INT,0,MPI_COMM_WORLD);buf=(int*)malloc(s*sizeof(int));MPI_Scatter(data,s,MPI_INT,buf,s,MPI_INT,0,MPI_COMM_WORLD);/*id号为0的处理器调度执行插入排序*/InsertionSort(buf,s);}else{MPI_Bcast(&s,1,MPI_INT,0,MPI_COMM_WORLD);buf=(int*)malloc(s*sizeof(int));MPI_Scatter(data,s,MPI_INT,buf,s,MPI_INT,0,MPI_COMM_WORLD);InsertionSort(buf,s);}step=1;while(stepp){if(id%(2*step)==0){if(id+stepp){MPI_Recv(&m,1,MPI_INT,id+step,0,MPI_COMM_WORLD,&status);other=(int*)malloc(m*sizeof(int));MPI_Recv(other,m,MPI_INT,id+step,0,MPI_COMM_WORLD,&status);buf=merge(buf,s,other,m);s=s+m;}}else{intnears=id-step;MPI_Send(&s,1,MPI_INT,nears,0,MPI_COMM_WORLD);MPI_Send(buf,s,MPI_INT,nears,0,MPI_COMM_WORLD);break;}step=step*2;}if(id==0){FILE*fout;stopT=clock();/*显示执行并行运算后各个进程的总共所耗时间*/printf(elementcount%d;\n%dprocessorscosttotaltimes;%fsecs\n,count,p,(stopT-startT)/CLOCKS_PER_SEC);fout=fopen(result,w);for(i=0;is;i++)if(buf[i]!=0){fprintf(fout,%d\n,buf[i]);//输出计算结果printf(%d\n,buf[i]);}fclose(fout);}MPI_Finalize();}