实验二-快速排序的mpi并行程序.doc

精品文档实验二 快速排序的MPI并行程序（一）实验时间： 2015年11月5日（二）实验名称： 快速排序的mpi并行化设计（三）内容与要求：1、内容：快速排序（以下简称快排）是对冒泡排序的一种改进，它的思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。而此次试验要将mpi运用到快速排序中，达到并行化排序的效果。2、要求：（1）请使用MPI并行程序设计实现快速排序的并行化；（2）正文格式：宋体，小四，首行缩进两字符，单倍行距，两端对齐（四）实验步骤1.运行mpi环境2.初始化一个数组3.定义m=log2N，然后2m为程序确定进程个数的个数，N是指整个程序调用的进程数。4.将数组中的数据依照快排的方式划分成2m份，然后发送给各个进程5各进程按串行快排，并将结果按层次返回给跟进程（五）关键代码实现（只写出关键代码）void MpiQs(int *a,int left,int right,int m,int id,int myid)int *temp;/定义的接收数组信息的存储位置int leftSize,rightSize;MPI_Status status;/如果进程分完则串行快排if(m=0)if(id=myid)quikSort(a,left,right);return;/给下个进程分发数据位置int mid;if(id=myid)mid=order_qs(a,left,right);rightSize=right-mid;leftSize=mid-left;/printf(n对下个进程发送进程号:%d l:%dr%dn,myid,leftSize,rightSize);MPI_Send(&rightSize,1,MPI_INT,id+exp2(m-1),myid,MPI_COMM_WORLD);/MPI_Recv(&rightSize,1,MPI_INT,id+exp2(m-1),id,MPI_COMM_WORLD,&status);/printf(排序中 发送排序个数 the procs:%dn,myid);if(rightSize!=0)MPI_Send(a+mid+1,rightSize,MPI_INT,id+exp2(m-1),myid,MPI_COMM_WORLD);/printf(排序中 发送数据 the procs:%dn,myid);/对上个进程数据的接收if(myid=id+exp2(m-1)/printf(n对上个进程接收进程号:%d l:%dr%dn,myid,leftSize,rightSize);MPI_Recv(&rightSize,1,MPI_INT,id,id,MPI_COMM_WORLD,&status);/printf(排序中 接收排序个数 the procs:%dn,myid);if(rightSize!=0)temp=(int *)malloc(rightSize*sizeof(int);if(temp=0)printf(申请临时数组内存出错);/MPI_Recv(temp,67,MPI_INT,id,id,MPI_COMM_WORLD,&status);MPI_Recv(temp,rightSize,MPI_INT,id,id,MPI_COMM_WORLD,&status);/printf(排序中 接收数据 the procs:%dn,myid);/快排递归MPI_Bcast(&leftSize,1,MPI_INT,id,MPI_COMM_WORLD);if(leftSize0)/printf(递归中n);MpiQs(a,left,mid-1,m-1,id,myid);MPI_Bcast(&rightSize,1,MPI_INT,id,MPI_COMM_WORLD);if(rightSize0)/printf(递归中n);MpiQs(temp,0,rightSize-1,m-1,id+exp2(m-1),myid);/发送与接收数据if(myid=id+exp2(m-1)&(rightSize!=0)MPI_Send(temp,rightSize,MPI_INT,id,id+exp2(m-1),MPI_COMM_WORLD);/printf(排序后 发送数据 the procs:%dn,myid);if(myid=id)&(rightSize!=0)MPI_Recv(a+mid+1,rightSize,MPI_INT,id+exp2(m-1),id+exp2(m-1),MPI_COMM_WORLD,&status);/printf(排序后 接收数据 the procs:%dn,myid);截图效果：20个进程计算 快排数组序列为100（六）实验总结与思考本次实验根据老师讲解步骤，自己思考了一番，似懂非懂并没有什么思路。在百度上找了一份关于快速排序实验报告和代码，仔细阅读其设计过程，和源码，了解了其设计步骤，思路。在并行化快速排序中最关键的就是处理数据的划分，及其处理各进程数据的发送及汇总。这部分的代码是整个实验的关键。在整个实验