《MPI排序算法编程.docx》由会员分享，可在线阅读，更多相关《MPI排序算法编程.docx（9页珍藏版）》请在三一办公上搜索。
1、1. 写出原算法串行处理的思路或流程2. 说明算法并行化的思路3. 并且写出算法流程，最终编码实现二. 实验环境硬件环境：Virtual PC 2007(XP)软件：VC+ 6.0； mpich.nt.1.2.5三. 实验步骤和结果1. 原插入排序原理gH 中向 III 5 V JQ 43*| 11 f 3D 31 3+3*上虹3, WtiFrt 小 0 12 is 3D 3! 24BtSI甲!AM E P Ll H JU jfj 2* 土H)甲时,a d r Ju h 11插入排序过程示例将n个元素的数列分为已有序和无序两个部分，如 下所示:, a2，a3，a4，ana1(1), a2(1)
2、，a3(1)，a4(1),an(1)a1(n-1), a2(n-1)，, an(nT)每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐 个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。 如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好 情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情 况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降 序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值 操作是比较操作的次数加上(n-1)次。平均来说插入排序算法的时间 复杂度为0(2)。因而，插入排序不适合对于数据量比较大的排序
3、应 用。2. 并行化思路上文所说的插入排序在数据量大的情况下，运算量比较大，因此适合 用并行计算来提高效率，下面是并行化算法的思路2.1首先需要输入排序元素的个数，并输入需要排序的原色，用一个数组保 存起来。2.2将数组按照进程的数目平均分段，每个进程各领取一段去做插入排序。2.3将进程排成一个二叉树的结构，每一个进程节点先将下面两个进程节点 排好的数组接收进来，做一次归并排序。再用这个归并排序结果跟进程 节点再做一次归并排序。2.4循环执行，直到树的根节点为止，排序完成。2.5输出并行排序结果3.程序运行结果4.源代码/此算法实现插入排序的并行运算/陈仲策2007034743011#incl
4、ude#include#include#includeint * merge(int *v1, int n1, int *v2, int n2);void swap(int *v, int i, int j);void sort(int *v, int n);double startT,stopT;double startTime;int * merge(int *v1, int n1, int *v2, int n2) int i,j,k;int * result;result = (int *)malloc(n1+n2)*sizeof(int);i=0; j=0; k=0;while(in
5、1 & jn2) if(v1iv2j) resultk = v1i; i+; k+;elseresultk = v2j; j+； k+;if(i=n1)while(jn2) resultk = v2j; j+; k+;elsewhile(in1)resultk = v1i; i+; k+;return result;/*插入排序算法*/void InsertionSort(int *v, int n)int i;int j;int temp;for(i=1;i0 & temp vj-1 ; j-)vj=vj-1;vj=temp;/*主函数*/void main(int argc, char *
6、argv)int m,n=500;int count;int *data;int *buf;int *other;int id,p;int s;int i;int step;MPI_Status status;/*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)/输入要排序的元素的个数/定义一个存放输入整数的指/将输入
7、的整数存入动态数组scanf(%d”,&count);n = count;int *a = (int *)malloc( count*sizeof(int);针，并分配空间for(int j=0;jcount;j+)scanf(%d,”,&aj);int r;s = n/p;r = n%p;data = (int *)malloc(n+p-r)*sizeof(int);for(i=0;in;i+)datai = ai;if(r!=0)for(i=n;in+p-r;i+)datai=0;s=s+1;startT = clock();/*从根处理机将数据序列广播到其他处理器*/* 1表示传送的输入
8、缓冲中的元素的个数*/* 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);elseMPI_Bcast(&s,1,MPI_INT,0,MPI_COMM_WORLD);buf = (int *)malloc(s*sizeof(int)
9、;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,
10、s,other,m);s = s+m;elseint nears = 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(element count %d ; n %d processors cost total times; %f secsn”,count,p,(stopT-startT)/CLOCKS_PER_SEC);fout = fopen(result”,w”);for(i=0;is;i+)if (bufi != 0)fprintf(fout,%dn”,bufi);/输出计算结果printf(%dn”,bufi);fclose(fout);MPI_Finalize();
