《并行計(jì)算劃分和分治策略》由會員分享，可在線閱讀，更多相關(guān)《并行計(jì)算劃分和分治策略（43頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,,,,*,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,第四章 劃分和分治策略,劃分,(partitioning),：將問題分為若干個獨(dú)立的部分。,,分治法,(divide and conquer method),：將一個大問題,逐步分割,成若干個原問題的子問題，用,簡單且相同,的方法對這些子問題進(jìn)行求解，然后將這些子問題的解組合成原問題的解。,,在分治法中,分解問題,和,合并結(jié)果,常使用,遞歸技術(shù),來實(shí)現(xiàn)。遞歸分治法能使各個子問題并行化執(zhí)行，即各個進(jìn)程用來執(zhí)行被分解的部分。,,通常數(shù)據(jù)的劃分也同時局部化。,劃分策略,Partitioning

2、Strategies,,數(shù)據(jù)劃分,(data partitioning or domain decomposition),,----,數(shù)據(jù)域并行,(SIMD,或,SPMD),,數(shù)據(jù)劃分是并行計(jì)算中的主要策略,,功能劃分,(functional decomposition),,----,控制并行,(MIMD,或,MPMD),,正如前面給出的一些例子的并行處理方法所示，我們總是將問題要處理的數(shù)據(jù)集盡可能,均勻地,分配給各個處理機(jī)（或進(jìn)程），這是因?yàn)閿?shù)據(jù)并行往往能夠帶來更高的效率。,例：利用數(shù)據(jù)劃分技術(shù)對數(shù)列求和。,,假設(shè)有,p,個處理機(jī)，數(shù)列元素個數(shù)為,n,。,A,0,… A,n/p-1,A,n/

3、p,… A,2n/p-1,A,2n/p,………… A,(p-1)n/p,… A,n-1,,+,,+,,+,,+,………,局部和,總和,序列求和方法,主從結(jié)構(gòu),,點(diǎn)到點(diǎn)通信,(,send&recv,),,廣播通信,(broadcast),,散射通信,(scatter),,分治法,master:,,/*,每個處理器計(jì)算,s,個數(shù)之和*,/,,,s = n / p;,,for (i =0,x=0; i

4、,P,any,);,,sum +=,part_sum,;,,},slave:,,,recv(&numbers,, s,,P,master,);,,part_sum,= 0;,,for (i=0; i

5、自己擁有的,n/p,個數(shù)據(jù)局部和的時間：,,,n/p,– 1,,3.,主進(jìn)程從,p,個從進(jìn)程接收局部和的時間：,,,p * (,t,start,,+,t,data,),,4.,主進(jìn)程計(jì)算,p,個局部和的總和的時間：,,,p,,整個算法的執(zhí)行時間為：,,2 p,t,start,,+ (,n+p,),t,data,,+,n/p,– 1 + p =,O(n+p,),master:,s = n / p;,bcast (numbers, s, P,slave_group,);,sum = 0;,for (i=0; i

6、art_sum;,},slave:,,bcast,(numbers, s,,P,master,);,,/*,slave_number,: 0..m-1 */,,start =,slave_number,* s;,,end = start + s;,,part_sum,= 0;,,for (i=start; i

7、&s, P,group,, root );,reduce(&sum, &s, ADD, P,group,, root);,slave:,,scatter(numbers,, &s,,P,group,, root);,,part_sum,= 0;,,for (i=0; i

8、的所有進(jìn)程必須都執(zhí)行相同的例程,群體操作要求參與操作的所有進(jìn)程必須都執(zhí)行相同的例程,分治法,用數(shù)列求和來說明分治法的基本思想：,,int,add (,int,s[ ]),//,順序算法,,{,,if (,number(s,)<=2),,return (n1+n2);,,else {,,,Divide(s,, s1,s2);,,part_sum1=,add (s1);,,part_sum2=,add (s2);,,return (part_sum1+ part_sum2);,,},,},分治法是將大問題遞歸地分解為容易處理的小問題，并且保持解決小問題與解決大問題的方法是一致的。,,,,,,,,,

9、,,,,,,,P,0,P,2,P,0,P,4,P,0,P,6,P,4,P,0,P,1,P,2,P,3,P,4,P,5,P,6,P,7,分治法的并行實(shí)現(xiàn)：,SPMD,并行算法,,,Divide_conquer(T,,,pro_id,, &k),,//,假設(shè)有,n=2,k,個處理器,,,{,,if |T|>,given_limit,,/* |T|,表示任務(wù),T,的規(guī)模 *,/,,,{,,,divide(T,, T1,T2);,,k--;,,,除,pro_id,進(jìn)程，再激活一個編號為,pro_id,,^,2,k,的進(jìn)程,;,,Divide_conquer(T1,,pro_id,, ,,// ^,

10、為異或操作,,,Divide_conquer(T2,,pro_id,,^,2,k,, &k,);,,,組合,,T1,和,,T2,的結(jié)果作為,,T,的結(jié)果，返回；,,,},,else,,,處理,T,，,并將,T,的結(jié)果返回；,,,},算法的時間分析,假設(shè)有,p = 2,k,個處理機(jī)，共計(jì)算,N,個數(shù)的和,,計(jì)算時間：,N/,p+log,p,,通信時間：,,T,comm1,= t,startup,+N/2,t,data,,+ t,startup,+N/4,t,data,,+…,,+,t,startup,+N/p,,t,data,,,= k t,startup,+(N(p-1)/p),t,data,

11、,= O(N),,T,comm2,=,k(t,startup,+t,data,) = log p (,t,startup,+t,data,),,對于計(jì)算時間而言，其最大加速比可以達(dá)到,p,；但分割和合并操作使并行算法的加速比可能遠(yuǎn)遠(yuǎn)小于,p,。,M,路分治法,用,M,路分治法對數(shù)列求和,（順序算法）,：,,int,add (,int,s[ ]) {,,if (,number(s,)<=4),,return (n1+n2+n3+n4);,,else {,,,Divide(s,, s1,s2, s3, s4);,,part_sum1= add (s1);,,part_sum2= add (s2);

12、,,part_sum3= add (s3);,,part_sum4= add (s4);,,return(part_sum1+part_sum2+,,part_sum3+ part_sum4);,,},,},劃分,/,分治技術(shù)實(shí)例,應(yīng)用,1----,以遞歸方法進(jìn)行的一些排序算法,,應(yīng)用,2----,數(shù)值積分,,應(yīng)用,3----N,體問題,應(yīng)用,1----,排序算法,順序算法及其時間復(fù)雜性,,桶排序的并行化,快速排序的順序算法：,,從小到大排列,a1, a2,…, an,,已知數(shù)列元素的最大值,end,和最小值,start,。,,,quicksort(list,, start, end),,{,

13、,if (start < end),,{,,partition (list, start, end, pivot);,,,quicksort,(list, start, pivot -1);,,,quicksort,(list, pivot +1, end);,,},,},,該算法的執(zhí)行時間為：,?,( n log n ),桶排序的順序算法,,假設(shè)被排序的數(shù)據(jù)在一個已知的區(qū)域（如：,0,到,a-1),內(nèi),均勻分布,，將該區(qū)域平均分為,m,個子區(qū)域，即：,0 ~ (a / m,?,1),,,(a / m) ~ (2a / m,?,1),,,…,,(m – 1) a / m ~ a-1,,,構(gòu)成

14、,m,個桶,串行算法：,,對待排序的,n,個數(shù)依次判斷它屬于哪個桶，設(shè)每次判斷需一次計(jì)算，則共計(jì)算,n,次。,,對,m,個桶內(nèi)的約,n/m,,個數(shù)分別采用最好的排序算法，如,quicksort,，則時間復(fù)雜度為,:,,m * (,n/m,) log (,n/m,) = n log (,n/m,),,桶排序算法僅在每個區(qū)域中的,數(shù)據(jù)的個數(shù)大致相等,時才會得到好的性能。,桶排序順序算法的執(zhí)行時間：,,n + m * n / m log ( n / m ) =,O(n,,log(n,/ m)),… … … … … … … … … … … … … … … … … …,,,,,,,,,… … … … …

15、 …,未排序的數(shù)列,,… … … … …,已排好序的數(shù)列,合并數(shù)列,對桶內(nèi)數(shù)列進(jìn)行排序,桶排序并行算法,1,… … … … … … … … … … … … … … … … … …,,,,,,,,,… … … … … …,未排序的數(shù)列,,… … … … …,已排好序的數(shù)列,合并數(shù)列,對桶內(nèi)數(shù)列進(jìn)行排序,P,0,P,1,P,2,P,p-1,… … … … … …,該并行算法的執(zhí)行過程：,,每個處理機(jī)擁有所有的數(shù)據(jù)副本；,,各處理機(jī)用,O(n,),的時間將數(shù)據(jù)分給各個處理機(jī)負(fù)責(zé)的桶中；,,各處理機(jī)同時對自己擁有的數(shù)據(jù)利用順序算法進(jìn)行排序；,,然后合并數(shù)列，得到排好序的數(shù)列。,,,并行算法的執(zhí)行時間：

16、,,n + n / p log ( n / p ),桶排序并行算法,2,,將數(shù)列劃分為,p,個區(qū)域，每個處理機(jī)擁有一個區(qū)域；,,通信時間,——,廣播數(shù)據(jù)：,t,comm1,= t,startup,+ n t,data,,每個處理機(jī)都有,p,個“小”桶，并將自己區(qū)域中的,n/p,個數(shù)據(jù)分散到這些小桶中；計(jì)算時間：,t,comp1,=,n/p,,將小桶中的,n / p,2,個數(shù)據(jù)倒入,p,個大桶；,,通信時間,——,將,p-1,個小桶的內(nèi)容發(fā)送給其它處理機(jī)，并從,p-1,個處理機(jī)接收屬于該處理機(jī)的大桶的數(shù)據(jù)：,,t,comm2,=2 (p -1) (t,startup,+ n/p,2,t,data

17、,),,對大桶中的數(shù)據(jù)排序，計(jì)算時間：,t,comp2,= (,n/p,) log (,n/p,),,算法執(zhí)行時間,=,,,n/p,+ (,n/p)log(n/p,) + (2p-1)t,startup,+ (n+2n/p-2n/p,2,) t,data,,未排序的數(shù)列,n/p,個數(shù),…………,數(shù)據(jù)分段,P,2,個小桶,,,,,…,,,,,…,,,,,…,,,,,…,合并數(shù)列,,……,騰空小桶,已排好序的數(shù)列,P,個處理機(jī),,,,,…………,對大桶數(shù)據(jù)排序,,,,,,,,,…………,各種算法的執(zhí)行時間對比,串行算法：,,m * (,n/m,) log (,n/m,) = n log (,n/m

18、,),,并行算法,1,：,,O (n / p log ( n / p ) + n),,并行算法,2,：,,=,n/p,+ (,n/p)log(n/p,) +,,(2p-1)t,startup,+ (n+2n/p-2n/p,2,) t,data,,= O (n / p log ( n / p ) + n),如果原有數(shù)列在一個已知區(qū)域,[0,，,a –1],均勻地分布，那么，我們才會得到高效率的桶排序的串行和并行算法。,,對于采用了,p,2,個小桶的并行算法,2,中，騰空各個,(p,個,),處理機(jī)擁有的,p,個小桶的內(nèi)容是指將自己擁有的,p -1,個小桶的內(nèi)容分別發(fā)送給其它,p -1,個處理機(jī)。在

19、,MPI,中該操作可由一個群體操作例程來實(shí)現(xiàn)：,,,MPI_Alltoall,,(void *,sendbuf,,,int,,sendcount,, type,sendtype,,,,void *,recvbuf,,,int,,recvcount,, type,recvdtype,,,,,MPI_Comm,,comm,);,All-to-all,操作示意圖：,,All-to-all,A4,A3,A2,A1,P,0,B4,B3,B2,B1,P,1,C4,C3,C2,C1,P,2,D4,D3,D2,D1,P,3,發(fā)送緩沖區(qū),D1,C1,B1,A1,D2,C2,B2,A2,D3,C3,B3,A3,D

20、4,C4,B4,A4,P,0,P,1,P,2,P,3,接收緩沖區(qū),應(yīng)用,2 ----,數(shù)值積分,將積分區(qū)域分割為一系列矩形，利用這些矩形的面積近似求出積分區(qū)域的值。,矩形面積,=,d * f ( p + d / 2 ),x,f(x,),a p,d,q b,,,,,將積分區(qū)域分割為一系列梯形，利用這些梯形的面積近似積分區(qū)域的值。,矩形面積,=,d * ( f ( p ) + f ( q ) ) / 2 ),x,f(x,),a p,d,q b,,,,,,當(dāng),d,越小,，算法求出的近似值越精確。,,顯然我們能很容

21、易地將數(shù)值積分問題分解為多個相互獨(dú)立的部分，每個部分由一個單獨(dú)的進(jìn)程完成計(jì)算。,,一般的靜態(tài)分配的并行算法,是將積分區(qū)域按處理機(jī)的個數(shù),p,分為,p,塊，然后每個處理機(jī)（進(jìn)程）計(jì)算一塊區(qū)域的面積，最后將其歸并，得到整個區(qū)域的積分值。,采用矩形方法，即計(jì)算每個小區(qū)間的中間點(diǎn)的函數(shù)值的矩形面積的并行算法：,,面積,=,,d,f(a+d,/2)+d,f(a+d+d,/2)+d f(a+2d+d /2)+…,,+d f(a+(n-1)d+d /2),,,= d,{,f(a+d,/2)+f(a+d+d /2)+f(a+2d+d /2)+…,,+,f(a+(n,-1)d +d /2),},1,4,,0,1

22、+x,2,?,1 +,( ),,4,,,i + 0.5,2,,,n,0,?i

23、),+…+,f(a+(n-1)d),+,f(b,),,2,f(a,),,2,,,算法只需做少量修改：,,,part_sum,= 0.5 *,(,f(start)+f(end,));,,for (x = start + d; x

24、e,space),：并行編程環(huán)境中的虛擬存儲器，由一組有序的元組構(gòu)成。并行執(zhí)行的進(jìn)程通過共享數(shù)據(jù)元組進(jìn)行交互。,,見,ComputePi,. doc,文件。,元組空間,進(jìn)程,進(jìn)程,進(jìn)程,元組,元組,元組,work(,1,, 0, 400000 , 1.0/400000 ),work(1, 0, 400000 , 0.0000025 ),work(,2,, 0, 200000 , 0.0000025 ),work(,3,, 200000, 400000 , 0.0000025 ),work(1, 0, 400000 , 0.0000025 ),work(2, 0, 200000 , 0.0000

25、025 ),work(3, 200000, 400000 , 0.0000025 ),work(,4,, 0, 100000 , 0.0000025 ),work(,5,, 100000, 200000 , 0.0000025 ),work(,6,, 200000, 300000 , 0.0000025 ),work(,7,, 300000, 400000 , 0.0000025 ),”worker”, 1,,work(2, 0, 200000, 0.0000025 ),”worker”, 1, work(3, 200000,,400000, 0.0000025 ),eval,”worker”

26、, 2,,work(4, 0, 100000, 0.0000025 ),”worker”, 2, work(5, 100000,,200000, 0.0000025 ),”worker”, 3, work(6, 200000,,300000, 0.0000025 ),”worker”, 3, work(7, 300000,,400000, 0.0000025 ),”worker”, 2, 0.9799,”worker”, 2, 0.8747,”worker”, 3, 0.7194,”worker”, 3, 0.5676,work(1, 0, 400000 , 0.0000025 ),work(

27、,2,, 0, 200000 , 0.0000025 ),work(,3,, 200000, 400000 , 0.0000025 ),in,”worker”, 1, 1.8546,”worker”, 1, 1.2870,work(,1,, 0, 400000 , 1.0/400000 ),in,eval,:,:,問題的描述：,,N,體問題是利用牛頓的萬有引力定律和運(yùn)動定律模擬太空中星體的運(yùn)動軌跡。,,萬有引力定律：質(zhì)量為,m,a,和,m,b,,的兩個物體間的引力為：,應(yīng)用,3 ---- N,體問題,其中：,G (6.67259*10,-11,米,3,/(,千克,.,秒,2,)),是引力常數(shù)，

28、,r,為兩物體間的距離。,G m,a,m,b,,,r,2,F =,————,—,應(yīng)用,3 ---- N,體問題,一個物體在受力的情況下，將根據(jù)牛頓第二定律產(chǎn)生加速度：,,,F = ma,,,m,是物體的質(zhì)量，,F,是物體所受的力，,a,是物體獲得的加速度 。,實(shí)現(xiàn)細(xì)節(jié)：,,設(shè)模擬天體運(yùn)動的時間間隔為,Δ,t,，物體的質(zhì)量為,m,，物體所受的力為：,m(v,t+1,-,v,t,),,Δ,t,F =,,新的速度為：,F,Δ,t,,m,v,t+1,=,,v,t,,+,v,t+1,，,v,t,,分別為物體在,,t+1,和,t,,時刻的速度。,,當(dāng)物體以速度,v,移動了,Δ,t,,時間后，其位置的變化為

29、：,,,x,t+1,-,x,t,,= v,Δ,tftrerrn,,smnd,h,N,體計(jì)算問題模擬程序演示：,,,N,體計(jì)算問題順序算法：,,,for (t = 0; t <,t,max,; t++),/* for each time period */,,for (i = 0; i < N; i++),,{,/* for each body */,,F =,Force_routine(i,);,/* compute force on,ith,body */,,,v[i],new,=,v[i,] + F *,dt,/ m;,/* compute new velocity */,,,pos[i]

30、,new,=,pos[i,] +,v[i],new,*,dt,;,/* and new position */,,},,for (i = 0; i < N; i++),,{,/* for each body */,,,pos[i,] =,pos[i],new,;,/* update velocity & position*/,,,v[i,] =,v[i],new,;,,},N,體問題的并行算法,,順序算法的時間復(fù)雜性為：,O(N,2,),。,,將串行代碼簡單地并行化，會產(chǎn)生大量的信息交換。因?yàn)?N,體問題中計(jì)算每一個物體新的位置和新的速度都受其它,N-1,個物體信息,(,位置,),的影響。,,

31、并行算法的時間復(fù)雜性可以利用簇化方法減少，即一簇遠(yuǎn)距離的物體可以大略地作為一個簇的總質(zhì)量位于該簇物體重心的單個遠(yuǎn)距離物體。,,這種簇化思想可以遞歸使用。,,,,,,,,,,,,質(zhì)量中心,遠(yuǎn)距離物體簇,r,Barnes-Hut,算法,----,創(chuàng)建,8,叉樹,,假設(shè)在一個三維立方體空間中包含有,N,個星體,,1.,將立方體分為,8,個子立方體；,,2.,如果某個子立方體不含有星體，則刪除該子立方體，以后不再考慮它；,,3.,如果某立方體僅含有,1,個星體，則保留該子立方體；,,4.,如果某立方體含有多于,1,個的星體，則繼續(xù)遞歸地分割這個子立方體，直到每個子立方體僅含有一個星體為止。,,8,叉樹

32、,----,每個節(jié)點(diǎn)都有,8,條邊的樹。,,樹的葉子表示含有,1,個星體的單元；,,當(dāng)樹建立后，子立方體的總質(zhì)量和該子立方體的重心將儲存在各個節(jié)點(diǎn)中。,Barnes-Hut,算法：,,for (t = 0; t <,t,max,; t++),/* for each time period */,,{,,,Build_Octatree,( );,/*,建立,8,叉樹 *,/,,,Total_Mass_Center,( );,/*,計(jì)算各簇的總質(zhì)量和重心 *,/,,,Compute_Force,( );,/*,遍歷樹計(jì)算物體所受的力 *,/,,Update( );,/*,更新物體的位置和速度 *

33、,/,,},說明：,,Build_Octatree,( ),：,利用空間中的各物體原有的位置計(jì)算。,,Total_Mass_Center,( ),：,是從葉子節(jié)點(diǎn)開始到根節(jié)點(diǎn)，計(jì)算每個子立方體總的質(zhì)量和重心位置，非葉子節(jié)點(diǎn)（一簇）的質(zhì)量通過其孩子的質(zhì)量累加得到，而重心則通過孩子們的質(zhì)量和重心合成得到。,說明（續(xù)）：,,Compute_Force,( ),：,每個物體所受的力可以通過從根遍歷這棵樹來獲得。當(dāng)?shù)竭_(dá)某個節(jié)點(diǎn)時，若簇的估計(jì)值已近似實(shí)際物體的值，則遍歷結(jié)束，否則繼續(xù)向下遍歷。,,在模擬,N,體問題中，判斷何時獲得近似值的簡單標(biāo)準(zhǔn)：,,假設(shè)簇包含在一個體積為,d,×d×d,的立方體中，到重心的距離是,r,，當(dāng),r,? d / ?,,時，就可以使用估計(jì)值了。 ? 為一個等于或小于,1.0,的常數(shù)。,Barnes-Hut,算法：,,for (t = 0; t <,t,max,; t++),/* for each time period */,,{,,,Build_Octatree,( );,/*,建立,8,叉樹 *,/,,,Total_Mass_Center,( );,/*,計(jì)算各簇的總質(zhì)量和重心 *,/,,,Compute_Force,( );,/*,遍歷樹計(jì)算物體所受的力 *,/,,Update( );,/*,更新物體的位置和速度 *,/,,},