并行计算课程报告庄星

并行计算与多核多线程技术课程报告班级 计 1 2 1 - 2 学号 2 0 1 2 5 8 5 0 1 2 1 3 姓名 庄 星 2014 年 11 月 24 日班级计 121-2 学号 201258501213 姓名 庄星 蒙特卡洛球体体积目录1. 快速排序 并行算法设计与实现 .41.1 功能描述与解决方案 .41.1.1 功能描述 .41.1.2 解决方案 .41.2 算法设计 .41.2.1 串行算法设计 .41.2.2 并行算法设计 .41.2.3 理论加速比分析（选作） .51.3 基于 OpenMP 的并行算法实现 .51.3.1 代码及注释（变量名 名字首字母 开头） .51.3.2 执行结果截图（体现串行时间、并行时间和加速比） .71.3.3 遇到的问题及解决方案 .71.3.4 加速比分析（选作） .81.4 基于 MPI 的并行算法实现 .81.4.1 代码及注释 .81.4.2 执行结果截图（体现串行时间、并行时间和加速比） .101.4.3 遇到的问题及解决方案 .111.4.4 加速比分析（选作） .111.5 基于 Windows（API）的并行算法实现 .121.5.1 代码及注释 .121.5.2 执行结果截图（体现串行时间、并行时间和加速比） .151.5.3 遇到的问题及解决方案 .151.5.4 加速比分析（选作） .161.6 基于 Windows（MFC）的并行算法实现 .161.6.1 代码及注释 .161.6.2 执行结果截图（体现串行时间、并行时间和加速比） .181.6.3 加速比分析（选作） .191.7 基于 Windows (.net)的并行算法实现（选作） .191.7.1 代码及注释 .191.7.2 执行结果截图（体现串行时间、并行时间和加速比） .211.7.3 遇到的问题及解决方案 .221.7.4 加速比分析（选作） .222. 理论基础 .222.1 并行计算机体系结构、并行计算模型、并行算法的概念 .222.2 并行计算机体系结构、并行计算模型、并行算法的关系 .232.3 实例说明并行计算机体系结构、并行计算模型、并行算法的关系 .23班级计 121-2 学号 201258501213 姓名 庄星 蒙特卡洛球体体积评 价实践效果（正确度/加速比）理论基础难度工作量独立性班级计 121-2 学号 201258501213 姓名 庄 星 蒙特卡洛球体体积41. 快速排序 并行算法设计与实现1.1 功能描述与解决方案1.1.1 功能描述本算法是利用蒙特卡洛计算的方法求一个单位为一的球体的体积，计算机根据算法描述在三维坐标轴上随机取数，再根据上述输入，利用给定的球体体积的运算法则，快速实施充分大量的随机抽样，对随机抽样的数据进行必要的数学计算，求出结果。1.1.2 解决方案在此算法中我需要随机取得的大量的数据进行随机计算，具体实施方案如下：（1）首先，使用 FOR 循环在 110000000 之间取数，分别取 X,Y,Z 三个方向轴上的值，对所取值分别除以 32767 即可得到属于 01 的区间内的 XYZ 的值；（2）对所求的 xyz 做平方和运算，若所得值小于 1，这个值有效，此时定义另一个变量count，对判断有效的过程执行 count+1，在大量随机取数中这个值有效，将这个值保存。（3）利用蒙塔卡罗算法，对有效值进行数据运算，因为大数据取数，所以所求值一定接进于单位为 1 的球体的体积。（4）并行算法中需要对循环次数做并行化，分别在 Openmp，MPI，API ，MFC 以及 C#中使用不同的并行方法对循环函数做变化，在不同的并行方法中，还需要对随机取数的方法做不同的使用。1.2 算法设计1.2.1 串行算法设计根据上述所列的具体实现方案设计串行计算方法。1.2.2 并行算法设计在 1.2.1 的基础上，将循环体分成两个等长的循环，分别计算 COUNT 值，最后调用归并算法，将以计算好的 COUNT 带入球体积分计算公式，求出单位球的体积。班级计 121-2 学号 201258501213 姓名 庄 星 蒙特卡洛球体体积51.2.3 理论加速比分析（选作）因为我所用的为 Inter 双核处理器，理论上对同一个函数进行双核运行是单核速度的两倍，并且由于并行算法是将串行分成两个部分分别运行，理论加速比应该为 2，但是由于并行的调用时间还有归并调用的操作，所以加速比应当小于 2，且由于机器和随机取数的效率问题，加速比应在 1 和 2 之间。1.3 基于 OpenMP 的并行算法实现1.3.1 代码及注释（变量名 名字首字母 开头）/ zx_para.cpp : 定义控制台应用程序的入口点。/#include “stdafx.h“#include#include#include #include#includevoid serial()/串行程序long int zx_max=10000000;long int zx_i1,zx_count1=0;double zx_x1,zx_y1,zx_z1,zx_bulk;/start_time1,end_time1;/start_time1=clock();time_t zx_t1;srand(unsigned) time(/函数产生一个以当前时间开始的随机种子for(zx_i1=0;zx_i1#include#include#include“mpi.h“#include #include using namespace std;long long int MC(long long int mynumber,int myrank)int mycount=0;double x,y,z;int i=0;for(i;imynumber;i+)x=(double)rand()/RAND_MAX);y=(double)rand()/RAND_MAX);z=(double)rand()/RAND_MAX);if(x*x+y*y+z*z1.0)mycount+;return mycount;void serial() /串行程序int Allnumber=10000000;int count=0;班级计 121-2 学号 201258501213 姓名 庄 星 蒙特卡洛球体体积9double x,y,z,bulk;double stime,etime,atime;stime=clock();for(int i=0;iAllnumber;i+)x=（(double)rand()/RAND_MAX);/随机取数y=（(double)rand()/RAND_MAX);z=（(double)rand()/RAND_MAX)；if(x*x+y*y+z*z1.0)count+;bulk=8.0*count/Allnumber;etime=clock();atime=(etime-stime)/1000;cout“bulk=“bulkendl;cout“serial time=“atimeendl;/printf(“pi= %12.12f ,alltime=%.3f “,pi,atime);int main(int argc,char* argv)int myrank,size;MPI_Init(MPI_Comm_size(MPI_COMM_WORLD,MPI_Comm_rank(MPI_COMM_WORLD,long long int topinnumber,myinnumber,mynumber,allnumber;double bulk,stime,etime,atime;stime=MPI_Wtime();allnumber=10000000;mynumber=allnumber/size;if(myrank!=0)myinnumber=MC(mynumber,myrank);MPI_Send(coutmyrank“ of “size“ : “myinnumberendl;/printf(“%d of %d : %dn“,myrank,size,myinnumber);elsemyinnumber=MC(mynumber,myrank);/coutmyrank“ of “size“ : “myinnumberendl;topinnumber=myinnumber;班级计 121-2 学号 201258501213 姓名 庄 星 蒙特卡洛球体体积10for(int source=1;sourcesize;source+)MPI_Recv(topinnumber+=myinnumber;bulk=8.0*topinnumber/all