并行计算实验一多线程计算π

并行计算实验一：多线程计算π学院计算机科学与技术专业计算机科学与技术年级2013级学号姓名2016年5月27日目录一、实验内容...................................................................................................................................3二、实验原理...................................................................................................................................32.1计算原理...........................................................................................................................32.2并行思想...........................................................................................................................4三、程序流程图...............................................................................................................................4四、实验结果及分析.......................................................................................................................64.1实验结果数据统计...........................................................................................................64.2加速比曲线.......................................................................................................................74.3结果分析...........................................................................................................................8五、实验总结...................................................................................................................................8一、实验内容（1）利用蒙特卡罗方法求圆周率PI（2）编写串行和多线程的代码分别计算并记录时间（3）统计数据并画出加速比曲线（4）对实验结果分析及感想二、实验原理2.1计算原理在数值积分法中，我们利用求单位圆的1/4的面积来求得Pi/4从而得到Pi。单位圆的1/4面积是一个扇形，它是边长为1单位正方形的一部分，只要能求出扇行面积S1在正方形面积S中占的比例K=S1/S就立即能得到S1，从而得到Pi的值。怎样求出扇形面积在正方形面积中占的比例K呢？一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数m与所投点的总数n的比m/n作为k的近似值。怎样实现这样的随机投点呢？任何一款计算机语言都有这种功能，能够产生在区间[0，1]内均匀分布的随机数，产生两个这样的随机数x,y,则以(x,y)为坐标的点就是单位正方形内的一点P，它落在正方形内每个位置的机会均等，P落在扇形内的充要条件是x^2+y^2=1。设投入的总点数为S1，根据判定条件可计算出落入园内的为S2，则有𝜋4=P=S2S1由上式即可算出𝜋的值。2.2并行思想在上述计算过程中唯一可以并行化的地方是随机数模拟了，假设投入的总点数为kSamplePoints，开启num_threads个线程，这样每个线程平均的去投kSamplePoints/num_threads个点，最后将所有线程的结果求和并计算概率P，这样比串行的效率高很多。三、程序流程图(1)串行流程图：串行流程图只需要调用hits函数即可（hits函数如下图），在此不再赘述。(2)并行流程图四、实验结果及分析4.1实验结果数据统计(1)随机点个数为107串、并行运行结果：线程数012345678910PI的值3.141133.141133.141133.141133.141133.141133.141133.141133.141133.141133.14113运行时间/微秒15394715477010755210480490905619377704648302414253952456181加速比10.9946821.4313731.4689041.6934932.4855421.9981183.1871773.7162823.8950262.740197（2）随机点个数为108串、并行运行结果：线程数012345678910PI的值3.14173.14173.14173.14173.14173.14173.14173.14173.14173.14173.1417运行时间/微秒15373611547753797449546993419115382572335235289131230452244811286534加速比10.9932861.9278492.8105683.6681134.0184884.585925.3171786.6710686.2797875.365374.2加速比曲线柱形图：折线图：012345678012345678910加速比线程数随机点个数为10^7随机点个数为10^8012345678012345678910加速比线程数随机点个数为10^7随机点个数为10^84.3结果分析分析结果得：(1)串行比单线程运行时间短(即加速比小于1)，此结果很好解释：单线程相比于串行还要花费时间创建一个线程，自然运行时间比串行慢。(2)理论上，随着线程数线性增大，运行速度应该相应的线性增大，但实际上我们通过加速比曲线可以看出，随着线程数的增大加速比大于1且总体趋势在递增，但其增幅远远小于线性，分析此结果我认为是由于一下两个方面：1)随着线程数的增大，运行时需要开辟更多的内存空间，需要额外消耗一部分时间。2)本实验中的数据规模小于108，故即使是采用int型的最大值CPU都可以在很短的时间内计算完毕，而开启线程所用的时间相对于此问题的计算时间来说不能近似忽略，故采用多线程对速度的提升并不理想。（3）对比107个随机点和108个随机点的加速比曲线，我们发现当数据点越多时PI的计算越准确，而且由于计算时间的增大，创建线程所需的时间对总时间的影响越小，从而多线程的优势越发明显。五、实验总结通过这次实验我学会了很多内容，以前虽然学习过关于线程、进程的概念，但是并没有真正的使用线程编写代码，利用随机数生成PI的多线程思想很简单，但是从零开始的我花了好久才调通多线程的程序，当运行产生正确的输出结果时，心里十分高兴。随后让我绝望的是，随着线程数的增加，运行时间成倍的上升，这与实际矛盾，最后终于知道是由于在线程中生成随机数的原因，修改代码，并行程序快的多了。通过编写这个小的多线程程序，对计算机的线程、进程等资源的调度有了更加深刻的认识。通过对实验的串行、并行结果的分析，更加清晰的认识到并行化的重要性。