《自然對數(shù)底E值的并行計(jì)算》由會員分享，可在線閱讀，更多相關(guān)《自然對數(shù)底E值的并行計(jì)算（26頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,自然對數(shù)底,E,值的并行計(jì)算,數(shù)學(xué),10-02,班,朱建偉,摘要,e,是數(shù)學(xué)中最重要的數(shù)學(xué)符號之一，稱為自然常數(shù)，是自然對數(shù)的底數(shù)。它最先由瑞士數(shù)學(xué)家歐拉在,1727,年使用。利用級數(shù)的方法求解,e,的值具有計(jì)算精確，速度較快的特點(diǎn)。其基本計(jì)算公式為：,本文主要采用多線程技術(shù)，對,e,值的計(jì)算進(jìn)行加速，得出計(jì)算時(shí)間與加速比，從而判斷多線程技術(shù)加速效果，進(jìn)而證明多核技術(shù)在數(shù)值計(jì)算方面的優(yōu)越性。,并且文中采用不同的并行方式來比較不同結(jié)果，查看哪種方式在并行計(jì)算中具有優(yōu)越性，獲得最終結(jié)果。,關(guān)鍵字,e,的計(jì)算

2、,多線程,加速比,高性能計(jì)算,引言,e,值在數(shù)學(xué)史上具有十分重要的意義，所以對,e,的計(jì)算進(jìn)行研究也從未間斷。已經(jīng)有多種方式對,e,值進(jìn)行快速精確的計(jì)算，于是想到依托于現(xiàn)有算法，對其進(jìn)行改造獲得多線程算法，查看其計(jì)算速度，獲得其加速比。通過對其加速效果的觀察，獲得多線程計(jì)算式中高性能計(jì)算方式，可以用于數(shù)值計(jì)算。,重要常量值,const int numSteps=2000000;/,計(jì)算終止值,CRITICAL_SECTION cs;/,臨界區(qū)聲明,int k=1;double e=1.0;double fact=1.0;,/,獲得電腦線程數(shù)（核數(shù)）,int numOfProcessors;,S

3、YSTEM_INFO SysInfo;,GetSystemInfo(,numOfProcessors=SysInfo.dwNumberOfProcessors;,串行計(jì)算,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;,利用臨界區(qū)進(jìn)行同步,方式一：,EnterCriticalSection(,while(k numSteps),fact*=k;,e+=1.0/fact;,k+;,LeaveCriticalSection(,方式二：,wh

4、ile(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;

5、,利用,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 first

6、private(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();,加速比,序號,計(jì)算方式,計(jì)算結(jié)果,運(yùn)行時(shí)間,/s,平均時(shí)間,/s,加速比,1,串行計(jì)算,2.71828,0.671,0.655,0.66300,1.000,0.64,0.686,2,臨界區(qū),2.71828,0.39,0.406,0.38225,1.734,0.374,0.359,3,線程,ID,2.71

7、828,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,加速比,序號,計(jì)算方式,計(jì)算結(jié)果,運(yùn)行時(shí)間,/s,平均時(shí)間,/s,加速比,1,串行計(jì)算,2.71828,6.614,6.505,6.59075,1.000,6.614,6.63,2,臨界區(qū),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

8、,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,加速比,(,兩線程,),序號,計(jì)算方式,計(jì)算結(jié)果,運(yùn)行時(shí)間,/s,平均時(shí)間,/s,加速比,1,串行計(jì)算,2.71828,0.686,0.702,0.69000,1.000,0.67,0.702,2,臨界區(qū),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 M

9、P,2.71828,實(shí)際調(diào)用四個(gè)線程,結(jié)果,一、,通過對表,1,與表,2,的比較可以看出，在計(jì)算,e,值的時(shí)候，運(yùn)算量與計(jì)算時(shí)間成正相關(guān)，與實(shí)際加速效果聯(lián)系不算太大，即運(yùn)算量越大，計(jì)算時(shí)間越長，但加速比并未有明顯提升。,二、,通過對表,1,與表,3,的比較可以看出，在計(jì)算,e,值的時(shí)候，同樣運(yùn)算量的情況下，加速效果雙核與四核差別不大，運(yùn)行時(shí)間也差別不大。說明線程之間共享數(shù)據(jù)會占用一部分時(shí)間，在簡單數(shù)值計(jì)算中，數(shù)據(jù)的交流與共享可能會浪費(fèi)掉很多時(shí)間。,算法優(yōu)化,fact *=i;,e +=1.0 /fact;,fact /=i;,e +=fact;,運(yùn)行速度有巨大提升！,序號,計(jì)算方式,計(jì)算結(jié)果,

10、運(yùn)行時(shí)間,/s,平均時(shí)間,/s,加速比,1,串行計(jì)算,2.71828,0.015,0.015,0.01500,1.000,0.015,0.015,2,臨界區(qū),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,比較,算法優(yōu)化時(shí)間,注意,1,、,實(shí)際計(jì)算過程中，,double,類型的數(shù)據(jù)能夠存儲數(shù)據(jù)十分有限，最多可以存儲到,，實(shí)際就是計(jì)算階乘到

11、,170,時(shí)還在計(jì)算機(jī)數(shù)系之內(nèi)，而計(jì)算到,171,時(shí)就不在表示范圍之內(nèi)了。而除法計(jì)算可以稍微多計(jì)算一些步，但是已經(jīng)超出,double,類型數(shù)據(jù)范圍，也只能計(jì)算到,177,步，對于第,178,步則不能計(jì)算，所以選取,numSteps=2000000,是為了增加計(jì)算量，對數(shù)據(jù)結(jié)果精確度提高沒有什么影響。,有效步數(shù)結(jié)果,上限步數(shù)結(jié)果,乘法,170,7.25742e+306,171,1.#INF,除法,177,2.96439e-323,178,0,2,、,OMP,并行的時(shí)候，,parallel for,采取是是分段并行的策略，必須做好初始化工作，因?yàn)椴煌€程開始工作的節(jié)點(diǎn)不同，所以要想得到正確結(jié)果，必

12、須給予正確的初始值。,3,、,OMP,并行也可以采取復(fù)制執(zhí)行的方式，即運(yùn)用,parallel,，但是在此時(shí)線程函數(shù)必須做出較大改變，其實(shí)就是將第二種實(shí)現(xiàn)方式前面加上即可，二者在基本原理上并無本質(zhì)不同，就是具體實(shí)現(xiàn)方式與封裝性上差別。,5,、,在進(jìn)行,OMP,并行計(jì)算時(shí)，必須了解其具體執(zhí)行方式之后再進(jìn)行改寫串行算法，也不要只看表面結(jié)果前幾位正確就以為萬事大吉。它的優(yōu)點(diǎn)是封裝性好，具體調(diào)度工作有操作系統(tǒng)完成，缺點(diǎn)是靈活性太差，如果不了解原理往往結(jié)果具有不確定性。,4,、,臨界區(qū)進(jìn)行同步的時(shí)候，避免頻繁進(jìn)入臨界區(qū)，這樣會浪費(fèi)大部分時(shí)間。但是在不同計(jì)算機(jī)上有很大差別，具體情況因計(jì)算機(jī)的不同而不同。,6

13、,、,算法檢測是否準(zhǔn)確，由于在,170,步以后已經(jīng)超出,double,類型數(shù)據(jù)所能表示最大值，可以減少步數(shù)，比如選取,100,進(jìn)行算法準(zhǔn)確性檢測，尤其是對,OMP,并行檢測。,結(jié)束語,經(jīng)過對,e,值進(jìn)行并行計(jì)算，更加深刻的明白多核計(jì)算的本質(zhì)與內(nèi)涵，與串行計(jì)算相比，并行計(jì)算就像是在賽道上跑步：,主程序進(jìn)行準(zhǔn)備安排好賽道，發(fā)令槍一響，多個(gè)線程同時(shí)開始運(yùn)行就像是同時(shí)起跑，個(gè)人不會對其他人產(chǎn)生影響就像是線程間不會相互影響。,而同步的概念就是幾個(gè)線程等到齊頭并進(jìn)。臨界區(qū)表示人為在跑道上營造一個(gè)每次只允許一個(gè)人通過的通道，所有人到達(dá)臨界區(qū)必須按順序一個(gè)一個(gè)通過。而互斥量就像是一枚標(biāo)志物，拿到標(biāo)志物的人在與

14、大家齊頭并進(jìn)后可以順利通過，而其他人必須等標(biāo)志物傳給他之后才能繼續(xù)行進(jìn)。信號量就是一段區(qū)域控制每次可以進(jìn)去多個(gè)，可以出來多個(gè)，但是總量有限制。,在進(jìn)行信息交流時(shí)如果不能及時(shí)把信息給另一個(gè)人，另一個(gè)人就會不管不顧直接繼續(xù)跑，就會產(chǎn)生錯(cuò)誤。而,事件,就是跑步前的人為安排，安排好誰先誰后。而,OMP,并行則是運(yùn)動員要跑,玩一段路程,，具體哪條跑道讓他們自己去選取,，但是初始狀態(tài)你一定要給他們選好，及每個(gè)人要跑多少平均分配，但開始跑的時(shí)候拿的東西你要給他們，規(guī)約就是把收獲合并到一起,。,所以設(shè)計(jì)程序時(shí)要充分考慮并行計(jì)算的特點(diǎn)，然后再進(jìn)行妥善安排，這樣才能獲得想要的結(jié)果。,參考資料,1,多核系列教材編寫組多核程序設(shè)計(jì),M,北京：清華大學(xué)出版社,2007-09,2011/01/25/1944598.html,