文件名称：并行计算课程设计（代码+执行文件+文档）
文件大小：12.84MB
文件格式：ZIP
更新时间：2019-01-31 10:22:13
并行计算 课程设计
1. 设计目的、意义（功能描述）
蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。本次大作业主要是对蒙特·卡罗方法进行并行处理，通过OpenMP、MPI、.NET、Java、Win32API等一系列并行技术和并行机制对该算法进行并行处理，从而也进一步熟悉了蒙特·卡罗方法的串行算法和并行算法，实现了用蒙特·卡罗方法计算出半径为1单位的球体的体积，体会到了并行技术在实际生活中的应用。
2. 方案分析（解决方案）
蒙特·卡罗方法（Monte Carlo method）是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。球的体积可以估算为：位于点模型内随机点个数与全体随机点个数的比值乘以包围盒的体积算的。
3. 设计分析
3.1 串行算法设计
假定球体用B表示，半径r=1单位，B1是包含B的参考立方体（在本例中是边长为2的正方体），在B1中产生N个均匀分布的伪随机点。对每个随机点检测其是否在B内，假设位于B内的随机点个数为N（in）（<=N），应用蒙特卡洛算法，则B的体积为
V=V1（N（in）/N）
其中V1是B1的体积。如果产生足够多的随机点，理论上可以获得任意逼近精度。
算法描述如下：
BEGIN
N=_MAX;
FOR I=0;I<_MAX;I++
X=RANDOM();
Y=RANDOM();
Z=RANDOM();
IF (X*X+Y*Y+Z*Z)<=1
COUNT++;
END IF;
END FOR;
BULK=V1*（COUNT/_MAX）;
END;
本算法主要是在参考立方体的选取上和定义的_MAX的值对结果影响较大，所以应该选择合适的数。
3.2 并行算法设计
对FOR循环进行划分使用两个处理器完成计算。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到结果。当然这是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么结果的效率会相对较差。
伪代码如下：
BEGIN
N=_MAX;
FOR1 I=0;I<_MAX/2;I++
X1=RANDOM();
Y1=RANDOM();
Z1=RANDOM();
IF (X1*X1+Y1*Y1+Z1*Z1)<=1
COUNT1++;
END IF;
END FOR1;
FOR2 I=_MAX/2+1;I<_MAX;I++
X2=RANDOM();
Y2=RANDOM();
Z2=RANDOM();
IF (X2*X2+Y2*Y2+Z2*Z2)<=1
COUNT2++;
END IF;
END FOR2;
BULK=V1*(（COUNT1+ COUNT2）/_MAX）;
END;
3.3 理论加速比分析
实验中大量数据所产生的加速比比小量数据所产生的加速比要体现得更明显，并且数据生成的并行加速比随着处理器核的增加而增加。设处理器个数为p，数据量为n，由于正常情况下该快速排序算法的复杂度为O(nlogn),并行处理的时间复杂度为O(klogk),其中k=n/p,所以并行算法的时间复杂度为O((n/p)log(n/p)),理论加速比为nlogn/((n/p)log(n/p))=p+logp.
4. 功能模块实现与最终结果分析
4.1 基于OpenMP的并行算法实现
4.1.1 主要功能模块与实现方法
利用了OpenMP里面的#omp parallel sections将对两个for循环用两个线程并行化执行，以多线程方式并行运行程序，并行的算法步骤如下：
（1）初始化_max = 10000000；
（2）创建两个线程；
（3）由OpenMP编译指导语句控制产生并行执行代码区段；
（4）将数据存放到tianqing_count;
（5）各线程调用算法得出结果；
并行算法的部分代码如下：
#pragma omp parallel for private(tianqing_x,tianqing_y,tianqing_z) reduction(+:tianqing_count2)
for (tianqing_i = 0; tianqing_i