自然對數(shù)底E值的并行計算

單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,自然對數(shù)底,E,值的并行計算,數(shù)學,10-02,班,朱建偉,摘要,e,是數(shù)學中最重要的數(shù)學符號之一，稱為自然常數(shù)，是自然對數(shù)的底數(shù)。它最先由瑞士數(shù)學家歐拉在,1727,年使用。利用級數(shù)的方法求解,e,的值具有計算精確，速度較快的特點。其基本計算公式為：,本文主要采用多線程技術，對,e,值的計算進行加速，得出計算時間與加速比，從而判斷多線程技術加速效果，進而證明多核技術在數(shù)值計算方面的優(yōu)越性。,并且文中采用不同的并行方式來比較不同結果，查看哪種方式在并行計算中具有優(yōu)越性，獲得最終結果。,關鍵字,e,的計算,多線程,加速比,高性能計算,引言,e,值在數(shù)學史上具有十分重要的意義，所以對,e,的計算進行研究也從未間斷。已經(jīng)有多種方式對,e,值進行快速精確的計算，于是想到依托于現(xiàn)有算法，對其進行改造獲得多線程算法，查看其計算速度，獲得其加速比。通過對其加速效果的觀察，獲得多線程計算式中高性能計算方式，可以用于數(shù)值計算。,重要常量值,const int numSteps=2000000;/,計算終止值,CRITICAL_SECTION cs;/,臨界區(qū)聲明,int k=1;double e=1.0;double fact=1.0;,/,獲得電腦線程數(shù)（核數(shù)）,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;,利用臨界區(qū)進行同步,方式一：,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,臨界區(qū),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,臨界區(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,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,臨界區(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 MP,2.71828,實際調用四個線程,結果,一、,通過對表,1,與表,2,的比較可以看出，在計算,e,值的時候，運算量與計算時間成正相關，與實際加速效果聯(lián)系不算太大，即運算量越大，計算時間越長，但加速比并未有明顯提升。,二、,通過對表,1,與表,3,的比較可以看出，在計算,e,值的時候，同樣運算量的情況下，加速效果雙核與四核差別不大，運行時間也差別不大。說明線程之間共享數(shù)據(jù)會占用一部分時間，在簡單數(shù)值計算中，數(shù)據(jù)的交流與共享可能會浪費掉很多時間。,算法優(yōu)化,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,臨界區(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)化時間,注意,1,、,實際計算過程中，,double,類型的數(shù)據(jù)能夠存儲數(shù)據(jù)十分有限，最多可以存儲到,，實際就是計算階乘到,170,時還在計算機數(shù)系之內，而計算到,171,時就不在表示范圍之內了。而除法計算可以稍微多計算一些步，但是已經(jīng)超出,double,類型數(shù)據(jù)范圍，也只能計算到,177,步，對于第,178,步則不能計算，所以選取,numSteps=2000000,是為了增加計算量，對數(shù)據(jù)結果精確度提高沒有什么影響。,有效步數(shù)結果,上限步數(shù)結果,乘法,170,7.25742e+306,171,1.#INF,除法,177,2.96439e-323,178,0,2,、,OMP,并行的時候，,parallel for,采取是是分段并行的策略，必須做好初始化工作，因為不同線程開始工作的節(jié)點不同，所以要想得到正確結果，必須給予正確的初始值。,3,、,OMP,并行也可以采取復制執(zhí)行的方式，即運用,parallel,，但是在此時線程函數(shù)必須做出較大改變，其實就是將第二種實現(xiàn)方式前面加上即可，二者在基本原理上并無本質不同，就是具體實現(xiàn)方式與封裝性上差別。,5,、,在進行,OMP,并行計算時，必須了解其具體執(zhí)行方式之后再進行改寫串行算法，也不要只看表面結果前幾位正確就以為萬事大吉。它的優(yōu)點是封裝性好，具體調度工作有操作系統(tǒng)完成，缺點是靈活性太差，如果不了解原理往往結果具有不確定性。,4,、,臨界區(qū)進行同步的時候，避免頻繁進入臨界區(qū)，這樣會浪費大部分時間。但是在不同計算機上有很大差別，具體情況因計算機的不同而不同。,6,、,算法檢測是否準確，由于在,170,步以后已經(jīng)超出,double,類型數(shù)據(jù)所能表示最大值，可以減少步數(shù)，比如選取,100,進行算法準確性檢測，尤其是對,OMP,并行檢測。,結束語,經(jīng)過對,e,值進行并行計算，更加深刻的明白多核計算的本質與內涵，與串行計算相比，并行計算就像是在賽道上跑步：,主程序進行準備安排好賽道，發(fā)令槍一響，多個線程同時開始運行就像是同時起跑，個人不會對其他人產生影響就像是線程間不會相互影響。,而同步的概念就是幾個線程等到齊頭并進。臨界區(qū)表示人為在跑道上營造一個每次只允許一個人通過的通道，所有人到達臨界區(qū)必須按順序一個一個通過。而互斥量就像是一枚標志物，拿到標志物的人在與大家齊頭并進后可以順利通過，而其他人必須等標志物傳給他之后才能繼續(xù)行進。信號量就是一段區(qū)域控制每次可以進去多個，可以出來多個，但是總量有限制。,在進行信息交流時如果不能及時把信息給另一個人，另一個人就會不管不顧直接繼續(xù)跑，就會產生錯誤。而,事件,就是跑步前的人為安排，安排好誰先誰后。而,OMP,并行則是運動員要跑,玩一段路程,，具體哪條跑道讓他們自己去選取,，但是初始狀態(tài)你一定要給他們選好，及每個人要跑多少平均分配，但開始跑的時候拿的東西你要給他們，規(guī)約就是把收獲合并到一起,。,所以設計程序時要充分考慮并行計算的特點，然后再進行妥善安排，這樣才能獲得想要的結果。,參考資料,1,多核系列教材編寫組多核程序設計,M,北京：清華大學出版社,2007-09,2011/01/25/1944598.html,