单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,自然对数底,E,值的并行计算,数学,10-02,班,朱建伟,摘要,e,是数学中最重要的数学符号之一，称为自然常数，是自然对数的底数它最先由瑞士数学家欧拉在,1727,年使用利用级数的方法求解,e,的值具有计算精确，速度较快的特点其基本计算公式为：,本文主要采用多线程技术，对,e,值的计算进行加速，得出计算时间与加速比，从而判断多线程技术加速效果，进而证明多核技术在数值计算方面的优越性并且文中采用不同的并行方式来比较不同结果，查看哪种方式在并行计算中具有优越性，获得最终结果关键字,e,的计算,多线程,加速比,高性能计算,引言,e,值在数学史上具有十分重要的意义，所以对,e,的计算进行研究也从未间断已经有多种方式对,e,值进行快速精确的计算，于是想到依托于现有算法，对其进行改造获得多线程算法，查看其计算速度，获得其加速比通过对其加速效果的观察，获得多线程计算式中高性能计算方式，可以用于数值计算重要常量值,const int numSteps=2000000;/,计算终止值,CRITICAL_SECTION cs;/,临界区声明,int k=1;double e=1.0;double fact=1.0;,/,获得电脑线程数（核数）,int numOfProcessors;,SYSTEM_INFO SysInfo;,GetSystemInfo(,numOfProcessors=SysInfo.dwNumberOfProcessors;,串行计算,double temp_e=1.0;,double temp_fact=1.0;,for(int i=1;inumSteps;i+),temp_fact*=I;,temp_e+=1.0/temp_fact;,利用临界区进行同步,方式一：,EnterCriticalSection(,while(k numSteps),fact*=k;,e+=1.0/fact;,k+;,LeaveCriticalSection(,方式二：,while(k numSteps),fact*=k;,e+=1.0/fact;,EnterCriticalSection(,k+;,LeaveCriticalSection(,利用线程,ID,号控制,int threadID=*(int*)arg);double fact=1.0;,for(int j=1;j=threadID+1;j+),fact*=j;,e+=1.0/fact;,for(int i=threadID;inumSteps;i+=numOfProcessors),for(int j=2;jnumOfProcessors+2;j+),fact*=(i+j);,e+=1.0/fact;,利用,Open MP,并,行,double temp_e1=0.0;,double*temp_fact1=new doublenumOfProcessors;,double temp=1.0;,int j=0;,int end_num=(numOfProcessors-1),*(numSteps/numOfProcessors);,/,初始化,for(int i=1;i=end_num+1;i+),if(i=(numSteps/numOfProcessors)*j+1),temp_fact1j=temp;,j+;,temp*=I;,#pragma omp parallel for firstprivate(temp_fact1)reduction(+:temp_e1),for(int i=1;i=numSteps;i+),temp_fact1omp_get_thread_num()*=I;,temp_e1+=1.0/,temp_fact1omp_get_thread_num();,加速比,序号,计算方式,计算结果,运行时间,/s,平均时间,/s,加速比,1,串行计算,2.71828,0.671,0.655,0.66300,1.000,0.64,0.686,2,临界区,2.71828,0.39,0.406,0.38225,1.734,0.374,0.359,3,线程,ID,2.71828,0.53,0.531,0.53825,1.232,0.562,0.53,4,Open MP,2.71828,0.219,0.203,0.20700,3.203,0.203,0.203,返回,numSteps=2,000,000,加速比,序号,计算方式,计算结果,运行时间,/s,平均时间,/s,加速比,1,串行计算,2.71828,6.614,6.505,6.59075,1.000,6.614,6.63,2,临界区,2.71828,3.588,3.822,3.72850,1.768,3.838,3.666,3,线程,ID,2.71828,5.195,5.397,5.52225,1.193,5.944,5.553,4,Open MP,2.71828,2.246,2.262,2.19175,3.007,2.075,2.184,numSteps=20,000,000,加速比,(,两线程,),序号,计算方式,计算结果,运行时间,/s,平均时间,/s,加速比,1,串行计算,2.71828,0.686,0.702,0.69000,1.000,0.67,0.702,2,临界区,2.71828,0.421,0.436,0.42475,1.624,0.437,0.405,3,线程,ID,2.71828,0.593,0.609,0.58925,1.171,0.562,0.593,4,Open MP,2.71828,实际调用四个线程,结果,一、,通过对表,1,与表,2,的比较可以看出，在计算,e,值的时候，运算量与计算时间成正相关，与实际加速效果联系不算太大，即运算量越大，计算时间越长，但加速比并未有明显提升。
二、,通过对表,1,与表,3,的比较可以看出，在计算,e,值的时候，同样运算量的情况下，加速效果双核与四核差别不大，运行时间也差别不大说明线程之间共享数据会占用一部分时间，在简单数值计算中，数据的交流与共享可能会浪费掉很多时间算法优化,fact *=i;,e +=1.0 /fact;,fact /=i;,e +=fact;,运行速度有巨大提升！,序号,计算方式,计算结果,运行时间,/s,平均时间,/s,加速比,1,串行计算,2.71828,0.015,0.015,0.01500,1.000,0.015,0.015,2,临界区,2.71828,0.125,0.094,0.10175,0.147,0.094,0.094,3,线程,ID,2.71828,0.047,0.047,0.05075,0.296,0.047,0.062,4,Open MP,2.71828,0.015,0.015,0.015,1.000,0.014,0.016,比较,算法优化时间,注意,1,、,实际计算过程中，,double,类型的数据能够存储数据十分有限，最多可以存储到,，实际就是计算阶乘到,170,时还在计算机数系之内，而计算到,171,时就不在表示范围之内了。
而除法计算可以稍微多计算一些步，但是已经超出,double,类型数据范围，也只能计算到,177,步，对于第,178,步则不能计算，所以选取,numSteps=2000000,是为了增加计算量，对数据结果精确度提高没有什么影响有效步数结果,上限步数结果,乘法,170,7.25742e+306,171,1.#INF,除法,177,2.96439e-323,178,0,2,、,OMP,并行的时候，,parallel for,采取是是分段并行的策略，必须做好初始化工作，因为不同线程开始工作的节点不同，所以要想得到正确结果，必须给予正确的初始值3,、,OMP,并行也可以采取复制执行的方式，即运用,parallel,，但是在此时线程函数必须做出较大改变，其实就是将第二种实现方式前面加上即可，二者在基本原理上并无本质不同，就是具体实现方式与封装性上差别5,、,在进行,OMP,并行计算时，必须了解其具体执行方式之后再进行改写串行算法，也不要只看表面结果前几位正确就以为万事大吉它的优点是封装性好，具体调度工作有操作系统完成，缺点是灵活性太差，如果不了解原理往往结果具有不确定性4,、,临界区进行同步的时候，避免频繁进入临界区，这样会浪费大部分时间。
但是在不同计算机上有很大差别，具体情况因计算机的不同而不同6,、,算法检测是否准确，由于在,170,步以后已经超出,double,类型数据所能表示最大值，可以减少步数，比如选取,100,进行算法准确性检测，尤其是对,OMP,并行检测结束语,经过对,e,值进行并行计算，更加深刻的明白多核计算的本质与内涵，与串行计算相比，并行计算就像是在赛道上跑步：,主程序进行准备安排好赛道，发令枪一响，多个线程同时开始运行就像是同时起跑，个人不会对其他人产生影响就像是线程间不会相互影响而同步的概念就是几个线程等到齐头并进临界区表示人为在跑道上营造一个每次只允许一个人通过的通道，所有人到达临界区必须按顺序一个一个通过而互斥量就像是一枚标志物，拿到标志物的人在与大家齐头并进后可以顺利通过，而其他人必须等标志物传给他之后才能继续行进信号量就是一段区域控制每次可以进去多个，可以出来多个，但是总量有限制在进行信息交流时如果不能及时把信息给另一个人，另一个人就会不管不顾直接继续跑，就会产生错误而,事件,就是跑步前的人为安排，安排好谁先谁后而,OMP,并行则是运动员要跑,玩一段路程,，具体哪条跑道让他们自己去选取,，但是初始状态你一定要给他们选好，及每个人要跑多少平均分配，但开始跑的时候拿的东西你要给他们，规约就是把收获合并到一起,。
所以设计程序时要充分考虑并行计算的特点，然后再进行妥善安排，这样才能获得想要的结果参考资料,1,多核系列教材编写组多核程序设计,M,北京：清华大学出版社,2007-09,2 http:/。
