并行計(jì)算劃分和分治策略

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

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

2、Strategies,,數(shù)據(jù)劃分,(data partitioning or domain decomposition),,----,數(shù)據(jù)域并行,(SIMD,或,SPMD),,數(shù)據(jù)劃分是并行計(jì)算中的主要策略,,功能劃分,(functional decomposition),,----,控制并行,(MIMD,或,MPMD),,正如前面給出的一些例子的并行處理方法所示，我們總是將問(wèn)題要處理的數(shù)據(jù)集盡可能,均勻地,分配給各個(gè)處理機(jī)（或進(jìn)程），這是因?yàn)閿?shù)據(jù)并行往往能夠帶來(lái)更高的效率。,例：利用數(shù)據(jù)劃分技術(shù)對(duì)數(shù)列求和。,,假設(shè)有,p,個(gè)處理機(jī)，數(shù)列元素個(gè)數(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:,,/*,每個(gè)處理器計(jì)算,s,個(gè)數(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,個(gè)數(shù)據(jù)局部和的時(shí)間：,,,n/p,– 1,,3.,主進(jìn)程從,p,個(gè)從進(jìn)程接收局部和的時(shí)間：,,,p * (,t,start,,+,t,data,),,4.,主進(jìn)程計(jì)算,p,個(gè)局部和的總和的時(shí)間：,,,p,,整個(gè)算法的執(zhí)行時(shí)間為：,,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ù)列求和來(lái)說(shuō)明分治法的基本思想：,,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);,,},,},分治法是將大問(wèn)題遞歸地分解為容易處理的小問(wèn)題，并且保持解決小問(wèn)題與解決大問(wèn)題的方法是一致的。,,,,,,,,,

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,個(gè)處理器,,,{,,if |T|>,given_limit,,/* |T|,表示任務(wù),T,的規(guī)模 *,/,,,{,,,divide(T,, T1,T2);,,k--;,,,除,pro_id,進(jìn)程，再激活一個(gè)編號(hào)為,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í)間分析,假設(shè)有,p = 2,k,個(gè)處理機(jī)，共計(jì)算,N,個(gè)數(shù)的和,,計(jì)算時(shí)間：,N/,p+log,p,,通信時(shí)間：,,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,),,對(duì)于計(jì)算時(shí)間而言，其最大加速比可以達(dá)到,p,；但分割和合并操作使并行算法的加速比可能遠(yuǎn)遠(yuǎn)小于,p,。,M,路分治法,用,M,路分治法對(duì)數(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,體問(wèn)題,應(yīng)用,1----,排序算法,順序算法及其時(shí)間復(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í)行時(shí)間為：,?,( n log n ),桶排序的順序算法,,假設(shè)被排序的數(shù)據(jù)在一個(gè)已知的區(qū)域（如：,0,到,a-1),內(nèi),均勻分布,，將該區(qū)域平均分為,m,個(gè)子區(qū)域，即：,0 ~ (a / m,?,1),,,(a / m) ~ (2a / m,?,1),,,…,,(m – 1) a / m ~ a-1,,,構(gòu)成

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

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

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

17、,),,對(duì)大桶中的數(shù)據(jù)排序，計(jì)算時(shí)間：,t,comp2,= (,n/p,) log (,n/p,),,算法執(zhí)行時(shí)間,=,,,n/p,+ (,n/p)log(n/p,) + (2p-1)t,startup,+ (n+2n/p-2n/p,2,) t,data,,未排序的數(shù)列,n/p,個(gè)數(shù),…………,數(shù)據(jù)分段,P,2,個(gè)小桶,,,,,…,,,,,…,,,,,…,,,,,…,合并數(shù)列,,……,騰空小桶,已排好序的數(shù)列,P,個(gè)處理機(jī),,,,,…………,對(duì)大桶數(shù)據(jù)排序,,,,,,,,,…………,各種算法的執(zhí)行時(shí)間對(duì)比,串行算法：,,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ù)列在一個(gè)已知區(qū)域,[0,，,a –1],均勻地分布，那么，我們才會(huì)得到高效率的桶排序的串行和并行算法。,,對(duì)于采用了,p,2,個(gè)小桶的并行算法,2,中，騰空各個(gè),(p,個(gè),),處理機(jī)擁有的,p,個(gè)小桶的內(nèi)容是指將自己擁有的,p -1,個(gè)小桶的內(nèi)容分別發(fā)送給其它,p -1,個(gè)處理機(jī)。在

19、,MPI,中該操作可由一個(gè)群體操作例程來(lái)實(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ù)值積分問(wèn)題分解為多個(gè)相互獨(dú)立的部分，每個(gè)部分由一個(gè)單獨(dú)的進(jìn)程完成計(jì)算。,,一般的靜態(tài)分配的并行算法,是將積分區(qū)域按處理機(jī)的個(gè)數(shù),p,分為,p,塊，然后每個(gè)處理機(jī)（進(jìn)程）計(jì)算一塊區(qū)域的面積，最后將其歸并，得到整個(gè)區(qū)域的積分值。,采用矩形方法，即計(jì)算每個(gè)小區(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)境中的虛擬存儲(chǔ)器，由一組有序的元組構(gòu)成。并行執(zhí)行的進(jìn)程通過(guò)共享數(shù)據(jù)元組進(jìn)行交互。,,見(jià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,:,:,問(wèn)題的描述：,,N,體問(wèn)題是利用牛頓的萬(wàn)有引力定律和運(yùn)動(dòng)定律模擬太空中星體的運(yùn)動(dòng)軌跡。,,萬(wàn)有引力定律：質(zhì)量為,m,a,和,m,b,,的兩個(gè)物體間的引力為：,應(yīng)用,3 ---- N,體問(wèn)題,其中：,G (6.67259*10,-11,米,3,/(,千克,.,秒,2,)),是引力常數(shù)，

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

29、：,,,x,t+1,-,x,t,,= v,Δ,tftrerrn,,smnd,h,N,體計(jì)算問(wèn)題模擬程序演示：,,,N,體計(jì)算問(wèn)題順序算法：,,,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,體問(wèn)題的并行算法,,順序算法的時(shí)間復(fù)雜性為：,O(N,2,),。,,將串行代碼簡(jiǎn)單地并行化，會(huì)產(chǎn)生大量的信息交換。因?yàn)?N,體問(wèn)題中計(jì)算每一個(gè)物體新的位置和新的速度都受其它,N-1,個(gè)物體信息,(,位置,),的影響。,,

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

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

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