,單擊此處編輯母版標題樣式,,,,*,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,第四章 劃分和分治策略,劃分,(partitioning),：將問題分為若干個獨立的部分。,,分治法,(divide and conquer method),：將一個大問題,逐步分割,成若干個原問題的子問題，用,簡單且相同,的方法對這些子問題進行求解，然后將這些子問題的解組合成原問題的解。,,在分治法中,分解問題,和,合并結(jié)果,常使用,遞歸技術(shù),來實現(xiàn)。遞歸分治法能使各個子問題并行化執(zhí)行，即各個進程用來執(zhí)行被分解的部分。,,通常數(shù)據(jù)的劃分也同時局部化。,劃分策略,Partitioning Strategies,,數(shù)據(jù)劃分,(data partitioning or domain decomposition),,----,數(shù)據(jù)域并行,(SIMD,或,SPMD),,數(shù)據(jù)劃分是并行計算中的主要策略,,功能劃分,(functional decomposition),,----,控制并行,(MIMD,或,MPMD),,正如前面給出的一些例子的并行處理方法所示，我們總是將問題要處理的數(shù)據(jù)集盡可能,均勻地,分配給各個處理機（或進程），這是因為數(shù)據(jù)并行往往能夠帶來更高的效率。,例：利用數(shù)據(jù)劃分技術(shù)對數(shù)列求和。,,假設(shè)有,p,個處理機，數(shù)列元素個數(shù)為,n,。,A,0,… A,n/p-1,A,n/p,… A,2n/p-1,A,2n/p,………… A,(p-1)n/p,… A,n-1,,+,,+,,+,,+,………,局部和,總和,序列求和方法,主從結(jié)構(gòu),,點到點通信,(,send&recv,),,廣播通信,(broadcast),,散射通信,(scatter),,分治法,master:,,/*,每個處理器計算,s,個數(shù)之和*,/,,,s = n / p;,,for (i =0,x=0; i<p; i++, x=,x+s,),,,send(&numbers[x,], s, P,i,);,,sum=0;,,for (i=0; i<p; i++),,{,,,recv(&part_sum,,,P,any,);,,sum +=,part_sum,;,,},slave:,,,recv(&numbers,, s,,P,master,);,,part_sum,= 0;,,for (i=0; i<s; i++),,,part_sum,+=,numbers[i,];,,send(&part_sum,,,P,master,);,主從結(jié)構(gòu)劃分求和算法,(,send&recv,),利用,send,和,recv,例程進行通信的并行求和算法的執(zhí)行時間：,,1.,主進程將,p,段數(shù)據(jù)分別發(fā)送給各個從進程的時間：,,,p * (,t,start,,+ (,n/p,),t,data,),,2.,各從進程計算自己擁有的,n/p,個數(shù)據(jù)局部和的時間：,,,n/p,– 1,,3.,主進程從,p,個從進程接收局部和的時間：,,,p * (,t,start,,+,t,data,),,4.,主進程計算,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<p; i++),{,recv(&part_sum, P,any,);,sum += part_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<end; i++),,,part_sum,+=,numbers[i,];,,send(&part_sum,,,P,master,);,主從結(jié)構(gòu)劃分求和算法,(broadcast),master:,s = n / p;,root = P,master,;,scatter(numbers, &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<s; i++),,,part_sum,+=,numbers[i,];,,reduce(&part_sum,, &s, ADD,,P,group,, root);,主從結(jié)構(gòu)劃分求和算法,(scatter),群體操作要求參與操作的所有進程必須都執(zhí)行相同的例程,群體操作要求參與操作的所有進程必須都執(zhí)行相同的例程,群體操作要求參與操作的所有進程必須都執(zhí)行相同的例程,群體操作要求參與操作的所有進程必須都執(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);,,},,},分治法是將大問題遞歸地分解為容易處理的小問題，并且保持解決小問題與解決大問題的方法是一致的。,,,,,,,,,,,,,,,,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,分治法的并行實現(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,進程，再激活一個編號為,pro_id,,^,2,k,的進程,;,,Divide_conquer(T1,,pro_id,, ,,// ^,為異或操作,,,Divide_conquer(T2,,pro_id,,^,2,k,, &k,);,,,組合,,T1,和,,T2,的結(jié)果作為,,T,的結(jié)果，返回；,,,},,else,,,處理,T,，,并將,T,的結(jié)果返回；,,,},算法的時間分析,假設(shè)有,p = 2,k,個處理機，共計算,N,個數(shù)的和,,計算時間：,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,,= O(N),,T,comm2,=,k(t,startup,+t,data,) = log p (,t,startup,+t,data,),,對于計算時間而言，其最大加速比可以達到,p,；但分割和合并操作使并行算法的加速比可能遠遠小于,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);,,part_sum3= add (s3);,,part_sum4= add (s4);,,return(part_sum1+part_sum2+,,part_sum3+ part_sum4);,,},,},劃分,/,分治技術(shù)實例,應(yīng)用,1----,以遞歸方法進行的一些排序算法,,應(yīng)用,2----,數(shù)值積分,,應(yīng)用,3----N,體問題,應(yīng)用,1----,排序算法,順序算法及其時間復雜性,,桶排序的并行化,快速排序的順序算法：,,從小到大排列,a1, a2,…, an,,已知數(shù)列元素的最大值,end,和最小值,start,。,,,quicksort(list,, start, end),,{,,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)成,m,個桶,串行算法：,,對待排序的,n,個數(shù)依次判斷它屬于哪個桶，設(shè)每次判斷需一次計算，則共計算,n,次。,,對,m,個桶內(nèi)的約,n/m,,個數(shù)分別采用最好的排序算法，如,quicksort,，則時間復雜度為,:,,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)),… … … … … … … … … … … … … … … … … …,,,,,,,,,… … … … … …,未排序的數(shù)列,,… … … … …,已排好序的數(shù)列,合并數(shù)列,對桶內(nèi)數(shù)列進行排序,桶排序并行算法,1,… … … … … … … … … … … … … … … … … …,,,,,,,,,… … … … … …,未排序的數(shù)列,,… … … … …,已排好序的數(shù)列,合并數(shù)列,對桶內(nèi)數(shù)列進行排序,P,0,P,1,P,2,P,p-1,… … … … … …,該并行算法的執(zhí)行過程：,,每個處理機擁有所有的數(shù)據(jù)副本；,,各處理機用,O(n,),的時間將數(shù)據(jù)分給各個處理機負責的桶中；,,各處理機同時對自己擁有的數(shù)據(jù)利用順序算法進行排序；,,然后合并數(shù)列，得到排好序的數(shù)列。,,,并行算法的執(zhí)行時間：,,n + n / p log ( n / p ),桶排序并行算法,2,,將數(shù)列劃分為,p,個區(qū)域，每個處理機擁有一個區(qū)域；,,通信時間,——,廣播數(shù)據(jù)：,t,comm1,= t,startup,+ n t,data,,每個處理機都有,p,個“小”桶，并將自己區(qū)域中的,n/p,個數(shù)據(jù)分散到這些小桶中；計算時間：,t,comp1,=,n/p,,將小桶中的,n / p,2,個數(shù)據(jù)倒入,p,個大桶；,,通信時間,——,將,p-1,個小桶的內(nèi)容發(fā)送給其它處理機，并從,p-1,個處理機接收屬于該處理機的大桶的數(shù)據(jù)：,,t,comm2,=2 (p -1) (t,startup,+ n/p,2,t,data,),,對大桶中的數(shù)據(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,個處理機,,,,,…………,對大桶數(shù)據(jù)排序,,,,,,,,,…………,各種算法的執(zhí)行時間對比,串行算法：,,m * (,n/m,) log (,n/m,) = n log (,n/m,),,并行算法,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,個,),處理機擁有的,p,個小桶的內(nèi)容是指將自己擁有的,p -1,個小桶的內(nèi)容分別發(fā)送給其它,p -1,個處理機。在,MPI,中該操作可由一個群體操作例程來實現(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,D4,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,越小,，算法求出的近似值越精確。,,顯然我們能很容易地將數(shù)值積分問題分解為多個相互獨立的部分，每個部分由一個單獨的進程完成計算。,,一般的靜態(tài)分配的并行算法,是將積分區(qū)域按處理機的個數(shù),p,分為,p,塊，然后每個處理機（進程）計算一塊區(qū)域的面積，最后將其歸并，得到整個區(qū)域的積分值。,采用矩形方法，即計算每個小區(qū)間的中間點的函數(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+x,2,?,1 +,( ),,4,,,i + 0.5,2,,,n,0,?i<n,1,,n,,?,=,dx,? ?,利用,C+MPI,例程計算,p,值的程序見,,ComputePi,. doc,文件。,采用第二種方法，即計算每個小區(qū)間的梯形面積的計算公式：,d (,f(a)+f(a+d,)),,2,d,(f(a+,d,)+f(a+2d)),,2,d,,(f(a+(n-1)d)+f(b)),,2,面積,= + +…+,=,d,+,f(a+d,),+,f(a+2d),+…+,f(a+(n-1)d),+,f(b,),,2,f(a,),,2,,,算法只需做少量修改：,,,part_sum,= 0.5 *,(,f(start)+f(end,));,,for (x = start + d; x<end; x = x + d),,{,//,calcs,partial sums,,,part_sum,+=,f(x,);,,},,,part_sum,= d *,part_sum,;,除以上計算數(shù)值積分方法，我們還可以用遞歸的分治法來解決問題。如用,C-Linda,實現(xiàn)的計算,p,的程序。,,C-Linda,,含有幾個在“元組空間”上的操作。,,元組空間,(,tuple,space),：并行編程環(huán)境中的虛擬存儲器，由一組有序的元組構(gòu)成。并行執(zhí)行的進程通過共享數(shù)據(jù)元組進行交互。,,見,ComputePi,. doc,文件。,元組空間,進程,進程,進程,元組,元組,元組,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.0000025 ),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”, 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(,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,體問題是利用牛頓的萬有引力定律和運動定律模擬太空中星體的運動軌跡。,,萬有引力定律：質(zhì)量為,m,a,和,m,b,,的兩個物體間的引力為：,應(yīng)用,3 ---- N,體問題,其中：,G (6.67259*10,-11,米,3,/(,千克,.,秒,2,)),是引力常數(shù)，,r,為兩物體間的距離。,G m,a,m,b,,,r,2,F =,————,—,應(yīng)用,3 ---- N,體問題,一個物體在受力的情況下，將根據(jù)牛頓第二定律產(chǎn)生加速度：,,,F = ma,,,m,是物體的質(zhì)量，,F,是物體所受的力，,a,是物體獲得的加速度 。,實現(xiàn)細節(jié)：,,設(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,,時刻的速度。,,當物體以速度,v,移動了,Δ,t,,時間后，其位置的變化為：,,,x,t+1,-,x,t,,= v,Δ,tftrerrn,,smnd,h,N,體計算問題模擬程序演示：,,,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],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,體問題的并行算法,,順序算法的時間復雜性為：,O(N,2,),。,,將串行代碼簡單地并行化，會產(chǎn)生大量的信息交換。因為,N,體問題中計算每一個物體新的位置和新的速度都受其它,N-1,個物體信息,(,位置,),的影響。,,并行算法的時間復雜性可以利用簇化方法減少，即一簇遠距離的物體可以大略地作為一個簇的總質(zhì)量位于該簇物體重心的單個遠距離物體。,,這種簇化思想可以遞歸使用。,,,,,,,,,,,,質(zhì)量中心,遠距離物體簇,r,Barnes-Hut,算法,----,創(chuàng)建,8,叉樹,,假設(shè)在一個三維立方體空間中包含有,N,個星體,,1.,將立方體分為,8,個子立方體；,,2.,如果某個子立方體不含有星體，則刪除該子立方體，以后不再考慮它；,,3.,如果某立方體僅含有,1,個星體，則保留該子立方體；,,4.,如果某立方體含有多于,1,個的星體，則繼續(xù)遞歸地分割這個子立方體，直到每個子立方體僅含有一個星體為止。,,8,叉樹,----,每個節(jié)點都有,8,條邊的樹。,,樹的葉子表示含有,1,個星體的單元；,,當樹建立后，子立方體的總質(zhì)量和該子立方體的重心將儲存在各個節(jié)點中。,Barnes-Hut,算法：,,for (t = 0; t <,t,max,; t++),/* for each time period */,,{,,,Build_Octatree,( );,/*,建立,8,叉樹 *,/,,,Total_Mass_Center,( );,/*,計算各簇的總質(zhì)量和重心 *,/,,,Compute_Force,( );,/*,遍歷樹計算物體所受的力 *,/,,Update( );,/*,更新物體的位置和速度 *,/,,},說明：,,Build_Octatree,( ),：,利用空間中的各物體原有的位置計算。,,Total_Mass_Center,( ),：,是從葉子節(jié)點開始到根節(jié)點，計算每個子立方體總的質(zhì)量和重心位置，非葉子節(jié)點（一簇）的質(zhì)量通過其孩子的質(zhì)量累加得到，而重心則通過孩子們的質(zhì)量和重心合成得到。,說明（續(xù)）：,,Compute_Force,( ),：,每個物體所受的力可以通過從根遍歷這棵樹來獲得。當?shù)竭_某個節(jié)點時，若簇的估計值已近似實際物體的值，則遍歷結(jié)束，否則繼續(xù)向下遍歷。,,在模擬,N,體問題中，判斷何時獲得近似值的簡單標準：,,假設(shè)簇包含在一個體積為,d,×d×d,的立方體中，到重心的距離是,r,，當,r,? d / ?,,時，就可以使用估計值了。 ? 為一個等于或小于,1.0,的常數(shù)。,Barnes-Hut,算法：,,for (t = 0; t <,t,max,; t++),/* for each time period */,,{,,,Build_Octatree,( );,/*,建立,8,叉樹 *,/,,,Total_Mass_Center,( );,/*,計算各簇的總質(zhì)量和重心 *,/,,,Compute_Force,( );,/*,遍歷樹計算物體所受的力 *,/,,Update( );,/*,更新物體的位置和速度 *,/,,},