计算PI_101冯康28.docVIP

Pi值计算 计算圆周率采用的是割圆术，即把圆分割成若干个小矩形，通过求矩形的面积总和来近似圆的面积。这里采用计算半径为1的四分之一圆的扇形的面积，得出的值即为所求的圆周率。计算公式为： 使用该方法计算出来的圆周率，其精确度取决于[0,1]区间内划分的子区间数。该数值越大，圆周率的精度值越大，即其小数点后的位数越多。 使用单线程实现该算法的过程十分简单，但只适用于计算低精度值的圆周率。计算十位小数点后超过十位的圆周率在单线程下需要几分钟甚至几个小时的的运行时间，因此应用多线程来实现该算法具有十分重要的意义。 对于计算公式的得出过程不是本次试验的重点，这里不解释。其串行计算方法如下图所示： 利用所学到的Windows多线程编程方法改进该串行计算方法，实现算法并行化处理。 提示： 1、循环体能否分割？ 2、哪些变量可以本地化或全局化 3、哪些变量需要所有的线程所共享 实验过程： 串行程序核心代码如下： step=1.0/(double)num_steps; for (int i=0;inum_steps;++i){ x=(i+0.5)*step; sum=sum+4.0/(1.0+x*x); } 分析：这个for循环每执行一次便计算出一个小矩形的面积，将其结果加到总面积sum上去，而各个矩形的计算是相互独立的，也就是说可以将每个矩形的计算过程作为一个任务，分配给特定的线程。 每个小矩形的面积采用局部变量来保存，矩形总面积(PI)sum采用全局变量来保存。由于多线程程序是并发执行的，那么各个线程都可以访问sum(PI)。如果不对sum采用一定的保护措施，那么同一时间可能有多个线程对sum进行访问操作，势必会发生数据竞争，为了避免这种情况的产生，可以采用以下几种方法： 事件(Event) 临界区(Critical section) 互斥量(Mutex) 信号量(Semaphore 这里采用临界区来保证某一时刻只用一个线程访问sum(PI)： EnterCriticalSection(gCS); PI += partialSum * gStep; LeaveCriticalSection(gCS); 并行程序核心代码如下： DWORD WINAPI threadFunction(LPVOID pArg){ int myNum = *((int *)pArg); double partialSum = 0.0, x; for ( int i=myNum; igNumSteps; i+=gNumThreads ){ x = (i + 0.5f) / gNumSteps; partialSum += 4.0f / (1.0f + x*x); } EnterCriticalSection(gCS); PI += partialSum * gStep; LeaveCriticalSection(gCS); return 0; } 分析： 将0-NumThreads-1的进程分别交给编号为0,1,2，3………NumThreads-2, NumThreads-1的NumThreads个线程来执行，依次类推，一轮一轮进行执行，最后也可以将gNumSteps个任务均分给NumThreads个线程来执行。 数据测试： 1）计算量相同，线程数不同（gNumSteps=100000000） 线程数 运行时间（S） 1 1.772 2 1.092 3 0.910 4 0.889 5 0.924 6 0.894 7 0.900 8 0.907 9 0.911 10 0.900 11 0.915 分析：由表中的数据可看出，多线程比单线程的性能提高很多。此后随着线程数的增多性能变化并不明显，线程数为4的时候计算所需时间最少，但超过4个线程性能开始下降。 (2)计算量不同，线程数相同（比较单线程和四线程）单位（S） N 四线程 单线程 10000 0.000 0.000 100000 0.003 0.002 1000000 0.010 0.0080.096 0.090 100000000 0.810 0.889 1000000000 8.813 8.821 10000000000 11.917 12.484 分析：由表中的数据可看出，当N值小于100000000时，多线程的性能并不比单线程好，甚至比单线程更差。随着N值的增大，多线程的优势开始显现，N值越大，多线程对比单线程的优势越明显。 结论：当系统的计算量较大时，多线程较之单线程在性能上会有很大的提高，但是在计算量较小时多线程的优势并不明显，甚至有时会比单线程运行得更慢 。 理论上讲，线程越多，程序的并行化程度越高，其运行速度应该越