open-MP计算PI&MPI快速排序

实验1openMP计算PI一、实验内容在VS环境下使用openMP让程序并行化执行计算PI的指值。并且掌握有关openMP程序设计的基本知识，并行程序设计的原理方法。二、实验原理OpenMPOpenMP应用编程接口API是在共享存储体系结构上的一个编程模型，其包含：编译制导(CompilerDirective)、运行库例程(RuntimeLibrary)和环境变量(EnvironmentVariables)三大部分，并支持增量并行化(IncrementalParallelization)，用于实现并行性运算的优化解决方法。OpenMP基于fork-join的编程模式而设计。OpenMP程序起初以一条单线程的形式开始运行。如果希望在程序中利用并行，那么就需将额外的线程进行分支，以创建线程组。这些线程在称为“并行区域”的代码区域内并行执行。在并行区域末尾，将等待所有线程全部完成工作，并将其重新结合在一起。那时，最初线程或“主”线程将继续执行，直至遇到下一个并行区域（或程序结束）。PI的计算方法：利用：∫11+x∗x10𝑑x来计算PI的值。三、实验过程和结果程序代码：//PI.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includestdio.h#includeomp.h#includetime.hint_tmain(intargc,_TCHAR*argv[]){longlongstep=1000000000;doubletemp,sum=0.0,PI;doubleper=1.0/(double)step;clock_tstart,stop;start=clock();inti;#pragmaompparallelforprivate(temp)reduction(+:sum)num_threads(4)for(i=0;istep;i++){temp=(i+0.5)*per;sum=sum+4.0/(1.0+temp*temp);}PI=sum*per;stop=clock();printf(PI=%15.12f\n,PI);printf(Runtime:%f\n,(double)((stop-start)/1000));return0;}程序执行结果：通过#pragmaompparallelforprivate(temp)reduction(+:sum)num_threads(num)设置并行num个线程并行执行语句块，然后对sum进行规约，得出计算结果，以下是线程数num对应的执行时间和PI的结果：a)Num＝1b)Num＝2c)Num＝4d)Num＝8四、分析与讨论通过设置多个线程并行执行PI的计算可以发现，刚开始的时候随着线程数的增加程序执行所花费的时间慢慢的减少，但是线程数增加到一定的数目时，程序执行时间不再增加。讨论：刚开始的时候程序执行的时间随着线程数的增加而减少，但是不是成比例减少的，我认为这个过程因为多个线程的通信还有开销，这个开销是不能减小的，而且线程数开的越多，这个开销越大（但是这个程序中的线程之间的开销很小）。后来线程数增长到一定数目时，计算PI时间不再减少，这个应该是因为CPU线程调度，CPU的利用率达到了一个极值，所以再增加线程数也没有效果。实验二MPI快速排序一．实验目的本实验的目的是通过练习掌握分布存储并行编程的知识和技巧。了解并行算法的设计方法掌握MPI并行程序编写的基本步骤掌握MPI编程环境和工具的使用二．实验原理（一）、MassagePassingInterface:是消息传递函数库的标准规范，由MPI论坛开发，支持Fortran和C（1）一种新的库描述，不是一种语言。共有上百个函数调用接口，在Fortran和C语言中可以直接对这些函数进行调用（2）MPI是一种标准或规范的代表，而不是特指某一个对它的具体实现（3）MPI是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准（二）、MPI基本数据类型（三）、MPI函数1、首先一个最重要的函数是intMPI_Init(int*argc,char**argv)MPI_INIT(IERROR)–MPI_INIT是MPI程序的第一个调用，它完成MPI程序的所有初始化工作。所有的MPI程序的第一条可执行语句都是这条语句。–启动MPI环境,标志并行代码的开始.–并行代码之前,第一个mpi函数(除MPI_Initialize()外).–要求main必须带参数运行,否则出错.其次是MPI结束-MPI_FINALIZEintMPI_Finalize(void)MPI_FINALIZE(IERROR)–MPI_FINALIZE是MPI程序的最后一个调用，它结束MPI程序的运行，它是MPI程序的最后一条可执行语句，否则程序的运行结果是不可预知的。–标志并行代码的结束,结束除主进程外其它进程.–之后串行代码仍可在主进程(rank=0)上运行(如果必须).•2、在写MPI程序时，我们常需要知道以下两个问题的答案：–任务由多少个进程来进行并行计算？–我是哪一个进程?•MPI提供了下列函数来回答这些问题：–用MPI_Comm_size获得进程个数pintMPI_Comm_size(MPI_Commcomm,int*size);–用MPI_Comm_rank获得进程的一个叫rank的值，该rank值为0到p-1间的整数,相当于进程的IDintMPI_Comm_rank(MPI_Commcomm,int*rank);3、最基本的MPIMPI调用借口的总数虽然庞大，但根据实际编写MPI的经验，常用的MPI调用的个数确实有限。下面是6个最基本的MPI函数。1.MPI_Init(…);2.MPI_Comm_size(…);3.MPI_Comm_rank(…);4.MPI_Send(…);5.MPI_Recv(…);6.MPI_Finalize();（四）、MPI消息•MPI消息包括信封和数据两个部分，信封指出了发送或接收消息的对象及相关信息，而数据是本消息将要传递的内容•数据：起始地址、数据个数、数据类型•信封：源/目的、标识、通信域•MPI标识一条消息的信息包含四个域:•Source:发送进程隐式确定,由进程的rank值唯一标识•Destination:Send函数参数确定•Tag:Send函数参数确定,用于识别不同的消息(0,UB),UB:MPI_TAG_UB=32767.•Communicator:缺省MPI_COMM_WORLD•Group:有限/N，有序/Rank[0,1,2,…N-1]•Contex:Super_tag,用于标识该通讯空间.（五）、阻塞与非阻塞•用户发送缓冲区的重用:–非阻塞的发送：仅当调用了有关结束该发送的语句后才能重用发送缓冲区，否则将导致错误；对于接收方，与此相同，仅当确认该接收请求已完成后才能使用。所以对于非阻塞操作，要先调用等待MPI_Wait()或测试MPI_Test()函数来结束或判断该请求，然后再向缓冲区中写入新内容或读取新内容。•阻塞发送将发生阻塞,直到通讯完成.•非阻塞可将通讯交由后台处理，通信与计算可重叠.•发送语句的前缀由MPI_改为MPI_I,I:immediate:–标准模式:MPI_Send(…)-MPI_Isend(…)–Buffer模式:MPI_Bsend(…)-MPI_Ibsend(…)–非阻塞的发送与接收…•intMPI_Isend(void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Commcomm,MPI_Request*request)–INbuf发送缓冲区的起始地址–INcount发送缓冲区的大小(发送元素个数)–INdatatype发送缓冲区数据的数据类型–INdest目的进程的秩–INtag消息标签–INcomm通信空间/通信子–OUTrequest非阻塞通信完成对象(句柄)•intMPI_Irecv(void*buf,intcount,MPI_Datatypedatatype,intsource,inttag,MPI_Commcomm,MPI_Request*request)三、实验要求(1)在vs2008上配置MPI环境(2)熟悉MPI编程环境(3)使用MPI编程实现快速排序的并行化四、实验内容（一）环境的配置vs2008中MPI的配置步骤：(1)安装mpich2-1.4.1p1-win-ia32.exe(2)在vs中，工具-选项-项目和解决方案-vc++目录-包含文件,添加安装的mpich2下的include目录，如图：(3)同样是vc++目录下，库文件下添加安装的mpich2目录下的lib目录，如图：(4)右键点击项目属性--配置属性--链接器—输入的附加依赖项，填写mpi.lib，如图：(5)所有以上的都配置好了，编译程序（不要运行）。会在Debug下生成exe文件。(6)到安装目录下找到wmpiregister.exe这个程序并打开，在里面填入一个用户名和密码(此处需要创建一个windows用户名，并设置密码)，点击注册(7)运行wmpiconfig.exe启动配置程序，点ScanHosts可以查到安装MPICH2的计算机，如果成功的话，可以看到安装了MPICH2的计算机名称编程草绿色。(8)现在到安装目录下找到mpiexec.exe程序打开，填入你的程序地址并制定执行的任务数目。如图：（二）快速排序算法的实现#includestdio.h#includestdlib.h#includempi.h#defineTRUE1/*输出错误信息*/voidErrMsg(char*msg){printf(Error:%s\n,msg);}/**函数名:exp2*功能：求的num次幂*输入：int型数据num*返回:2的num次幂*/intexp2(intnum){inti;i=1;while(num0){num--;i=i*2;}returni;}/**函数名:log2*功能：求以为底的num的对数*输入：int型数据num*返回:以为底的num的对数*/intlog2(intnum){inti,j;i=1;j=2;while(jnum){j=j*2;i++;}if(jnum)i--;returni;}/**函数名:GetDataSize*功能：读入待排序序列长度*/intGetDataSize(){inti;while(TRUE){printf(InputtheDataSize:);scanf(%d,&i);/*读出正确的i，返回；否则，继续要求输入*/if((i0)&&(i=65535))break;ErrMsg(WrongDataSize,mustbetween[1..65535]);}returni;}/**函数名:Partition*功能：对起止位置为start和end的数组序列，将其分成两个非空子序列，*其中前一个子序列中的任意元素小于后个子序列的元素。*输入：无序数组data[1,n]*返回:两个非空子序列的分界下标*/intPartition(int*data,intstart,intend){intpivo;inti,j;inttmp;pivo=data[end];i=start-1;/*i(活动指针)*/for(j=start;jend;j++)if(data[j]=pivo){i++;/*i表示比pivo小的元素的个数*/tmp=data[i];data[i]=data[j];data[j]=tmp;}tmp=data[i+1];data[i+1]=data[end];data[end]=tmp;/*以pivo为分界，data[i+1]=pivo*/returni+1;}/**函数名:para_QuickSort*功能：并行快速排序，对起止位置为start和end的序列，使用的m次幂个处理器进行