蒙特卡罗算法实验报告.docx
多核软件设计试验指导蒙特卡洛算法求"项目开发者：开发时间:版本号:、问题描述蒙特卡洛算法可理解为通过大量试验，模拟实际行为，来收集统计数据。本例中，算法随机产生一系 列点，模拟这些点落在如下图所示的正方形区域内的状况。其几何解释如下图1如图1所示，正方形边长为1,左下顶点与原点重合，两边分别与x, y轴重合。曲线为1/4圆弧，圆12 _ 1心位于原点，与正方形左下定点重合，半径为1。正方形面积S = l ,圆弧内面积S2= Z 勿 ="。 算法模拟大量点随机落在此正方形区域内，落在圆弧内的点的数量(由)与点的总数(m)的比例与面积 成正比关系。即-3 (1)几2 S? 兀由此可得4722兀=(2)因此，只要计算出落在圆弧内的点的数量在点总数中所占的比例，就能求出的值。由图1可知，全部点均落在正方形范围内，因此点的x坐标满意又，当点落在圆弧范围 内，则点的二维坐标关系满意*2+W1。检验每一个点是否满意此关系即可判定改点是否落在 圆弧内。二、串行算法描述本项目中使用了标准c语言库中的产生随机数函数。该函数原型为：int rand( void );此函数产生随机数列，每次调用时均返回0到RAND.MAX之间的一个整数。void srand( unsigned int seed );此函数为rand ()函数所生成的伪随机数序列设置起始点，使之产生不同的伪随机数。算法：产生2n个随机数据，范围0, 1,对每个数据点计算其坐标是否满意1+丁1,统计满意此关系count的点的数量count,则4 4M示例见附件Serial, c三、并行算法3.1并行算法描述算法步骤：1、确定需要产生的点的个数n,参加运行的处理器数m；2、对每一个处理器，生成两个随机数x, y,范围0, 1；3、推断两个随机数x, y是否满意12+2工1；4、若满意，则变量COUNT汁+；5、重复步骤2-4,直至每个处理器均生成n/m个随机点；6、收集COUNT的值，并累加至变量COUNT中，此即为随机点落在圆弧内的数量；7、通过(2)式计算乃的值。3.2 并行算法的一个例子在这个试验中，采纳Linux操作系统pthread接口来实现程序的并行化。这些接口函数和数据类型都在 头文件vpthread.h中声明。由于pthread并没有包含在C的标准库中，编译的时候需要加上-Ipthread选项，使程序链接到libpthread,才能编译胜利。例子程序参见附件Parallels。3.3 并行算法正确性证明本并行算法只是简洁的把独立的任务进行分派，经多次试验测试，结果正确。四、试验结果硬件平台：惠普刀片集群编译器：gcc&g+操作系统：Linux测试数据集合：由随机数函数产生的数据集合4.1 算法运行时间表1N （千万）串行算法运行时间（秒）并行算法运行时间（秒）加速比10.8140.9590.84882.51.6182.6730.605354.0245.7160.70397.56.0697.3760.8228108.08910.0010.808812.510.10512.2270.82641512.11514.8420.816217.514.11919.5220.72322016.12122.0330.73163024.18332.5920.74194032.25941.5420.77655040.72649.7250.8109注:N：算法生成随机点的个数算法运行时间为某一次运行时间，非多次运行之平均时间4.2 算法计算量时间比、加速比并行、串行算法运算量时间比、加速比如下图所示运算量时间比450.90.80. 70.6五0.5眼k 0. 40. 30.20. 100加速比 力口速比11111102030405060运算规模（千万）图3五、试验结果分析如表1、图3所示，加速比在(0.6,0.9)区间，与理论上的值2相去甚远。对同一运算量多次运行并行算法得到如下表2所示结果。(图4)表2规模123456710.9591.2050.9631.0431.0021.0531.01155.7164.8775.0944.7615.2124.8755.2961010.0019.8929.99010.1519.94110.16810.1692022.03320.75720.12020.64719.91820.79820.1605049.72549.78551.53549.42050.99252.37947.015并行算法 1- 510-20502468算法运行次数而对同样的运算量多次运行串行算法得到如下表3所示结果。(图5)表3规模123456710.8140.8140.8140.8130.8100.8150.81354.0244.0534.0624.0574.0444.0904.053108.0898.1528.1538.1348.1608.0958.1082016.12116.28916.29016.31816.28816.24516.2925040.72640.72140.70140.69640.70640.69540.694串行算法卜椰 聚卜椰 聚1- 510-2050如图4图5所示，对同一计算量，串行算法每次运行时间相差较小，而并行算法则相差明显。因此， 通过分析源代码可得出以下结论：程序所用的rand ()函数在同一时间只允许一个处理器调用，当两个处理器都需调用rand ()函数时, 后调用的将被挂起，等待另一个处理器运行完毕。两线程在就绪和执行态之间不断变化，铺张了大量CPU 时间，因此对同一运算量，并行程序运行时间反而比串行程序慢，而且线程状态转换次数范围为0, n, 平均为次，因此，相比于串行程序的无状态转换，并行算法的运行时间才会有如此大的波动。2六、并行算法改进为了改进并行算法，得到更高的加速比，有两种途径可以尝试：削减线程状态转化次数和使用可并行的随 机数产生算法。简介如下：6.1削减线程转态转换次数此方法详细为：在并行程序中使用互斥锁，当某一线程进入临界区后，一次性产生m个随机点，然后 再退出临界区，开头对m个点进行计算；与此同时: 若另一线程也要进入临界区，则被挂起，等待该线程 退出。如此循环，直至两个线程均计算完所要求的点的个数，则计算输出乃值，程序结束。算法:1、确定产生点n的个数和缓冲区m (m<=n)的值，声明互斥锁2、某一线程进入临界区，上锁3、该线程一次性生成m个数，其他线程若想进入则挂起等待4、该线程退出临界区，解锁，开头对刚才生成的随机点进行计算5、重复2-4步，直至每个线程均完成对所要求点的操作6、统计COUNTi的值7、计算"的值在此算法中，每一线程由于争用rand ()函数而产生的状态转化次数范围为0,-,平均次数为， m2m调整m的值，使生成m个随机点的时间与对m个随机点进行计算的时间相等时，则算法执行速度可达到 最大值，即加速比最大。示例程序参见附件Pmutex.Co6.2使用可并行的随机数生成函数生成随机数最常用的方法为线性同余法，其c语言源代码如下：/myrand ()用的种子unsigned static Y =568731;unsigned d=l«31;生成伪随机数算法 double inline myrand() Y二(15625*Y+22221)%d;return (double)Y/(double) (d-1);)通过转变种子的值，算法可生成不同的伪随机数列并且可以满意多个处理器同时调用。但调用所需时间略大 于调用系统库函数rand ()。(调用myrand ()函数的串行算法，见附件Smyrand. c)示例程序见附件Pmyrand. c
