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 主要功能模块
2021-06-20 17:02:16
654KB
1
本书介绍目前最常见的并行程序—MPI并行程序的设计方法它适合高校三四年级本科生非计算机专业研究生作为教材和教学自学参考书也适合于广大的并行计算高性能计算用户作为自学参考书使用对于有FORTRAN和C编程经验的人员都可以阅读并掌握本书的内容。
首先介绍了并行程序设计的基础提供给读者进行并行程序设计所需要的基本知识然后介绍了MPI的基本功能从简单的例子入手告诉读者MPI程序设计的基本过程和框架这一部分是具有C或/FORTRAN串行程序设计经验的人员很容易理解和接受的接下来介绍MPI程序设计的高级特征是已经掌握了MPI基本程序设计的人员进一步编写简洁高效的MPI程序使用各种高级和复杂的MPI功能所需要的最后一部分介绍了MPI的最新发展和扩充MPI-2 主要包括三个部分动态进程管理远程存储访问和并行文件读写。
2021-06-11 09:49:28
806KB
1