并行计算划分和分治策略

《并行计算划分和分治策略》由会员分享，可在线阅读，更多相关《并行计算划分和分治策略（43页珍藏版）》请在装配图网上搜索。

1、,单击此处编辑母版标题样式,,,,*,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,第四章 划分和分治策略,划分,(partitioning),：将问题分为若干个独立的部分。,,分治法,(divide and conquer method),：将一个大问题,逐步分割,成若干个原问题的子问题，用,简单且相同,的方法对这些子问题进行求解，然后将这些子问题的解组合成原问题的解。,,在分治法中,分解问题,和,合并结果,常使用,递归技术,来实现。递归分治法能使各个子问题并行化执行，即各个进程用来执行被分解的部分。,,通常数据的划分也同时局部化。,划分策略,Partitioning

2、Strategies,,数据划分,(data partitioning or domain decomposition),,----,数据域并行,(SIMD,或,SPMD),,数据划分是并行计算中的主要策略,,功能划分,(functional decomposition),,----,控制并行,(MIMD,或,MPMD),,正如前面给出的一些例子的并行处理方法所示，我们总是将问题要处理的数据集尽可能,均匀地,分配给各个处理机（或进程），这是因为数据并行往往能够带来更高的效率。,例：利用数据划分技术对数列求和。,,假设有,p,个处理机，数列元素个数为,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,,+,,+,,+,,+,………,局部和,总和,序列求和方法,主从结构,,点到点通信,(,send&recv,),,广播通信,(broadcast),,散射通信,(scatter),,分治法,master:,,/*,每个处理器计算,s,个数之和*,/,,,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,个数据局部和的时间：,,,n/p,– 1,,3.,主进程从,p,个从进程接收局部和的时间：,,,p * (,t,start,,+,t,data,),,4.,主进程计算,p,个局部和的总和的时间：,,,p,,整个算法的执行时间为：,,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、的所有进程必须都执行相同的例程,群体操作要求参与操作的所有进程必须都执行相同的例程,分治法,用数列求和来说明分治法的基本思想：,,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,分治法的并行实现：,SPMD,并行算法,,,Divide_conquer(T,,,pro_id,, &k),,//,假设有,n=2,k,个处理器,,,{,,if |T|>,given_limit,,/* |T|,表示任务,T,的规模 *,/,,,{,,,divide(T,, T1,T2);,,k--;,,,除,pro_id,进程，再激活一个编号为,pro_id,,^,2,k,的进程,;,,Divide_conquer(T1,,pro_id,, ,,// ^,

10、为异或操作,,,Divide_conquer(T2,,pro_id,,^,2,k,, &k,);,,,组合,,T1,和,,T2,的结果作为,,T,的结果，返回；,,,},,else,,,处理,T,，,并将,T,的结果返回；,,,},算法的时间分析,假设有,p = 2,k,个处理机，共计算,N,个数的和,,计算时间：,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,),,对于计算时间而言，其最大加速比可以达到,p,；但分割和合并操作使并行算法的加速比可能远远小于,p,。,M,路分治法,用,M,路分治法对数列求和,（顺序算法）,：,,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);,,},,},划分,/,分治技术实例,应用,1----,以递归方法进行的一些排序算法,,应用,2----,数值积分,,应用,3----N,体问题,应用,1----,排序算法,顺序算法及其时间复杂性,,桶排序的并行化,快速排序的顺序算法：,,从小到大排列,a1, a2,…, an,,已知数列元素的最大值,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);,,},,},,该算法的执行时间为：,,( n log n ),桶排序的顺序算法,,假设被排序的数据在一个已知的区域（如：,0,到,a-1),内,均匀分布,，将该区域平均分为,m,个子区域，即：,0 ~ (a / m,,1),,,(a / m) ~ (2a / m,,1),,,…,,(m – 1) a / m ~ a-1,,,构成

14、,m,个桶,串行算法：,,对待排序的,n,个数依次判断它属于哪个桶，设每次判断需一次计算，则共计算,n,次。,,对,m,个桶内的约,n/m,,个数分别采用最好的排序算法，如,quicksort,，则时间复杂度为,:,,m * (,n/m,) log (,n/m,) = n log (,n/m,),,桶排序算法仅在每个区域中的,数据的个数大致相等,时才会得到好的性能。,桶排序顺序算法的执行时间：,,n + m * n / m log ( n / m ) =,O(n,,log(n,/ m)),… … … … … … … … … … … … … … … … … …,,,,,,,,,… … … … …

15、 …,未排序的数列,,… … … … …,已排好序的数列,合并数列,对桶内数列进行排序,桶排序并行算法,1,… … … … … … … … … … … … … … … … … …,,,,,,,,,… … … … … …,未排序的数列,,… … … … …,已排好序的数列,合并数列,对桶内数列进行排序,P,0,P,1,P,2,P,p-1,… … … … … …,该并行算法的执行过程：,,每个处理机拥有所有的数据副本；,,各处理机用,O(n,),的时间将数据分给各个处理机负责的桶中；,,各处理机同时对自己拥有的数据利用顺序算法进行排序；,,然后合并数列，得到排好序的数列。,,,并行算法的执行时间：

16、,,n + n / p log ( n / p ),桶排序并行算法,2,,将数列划分为,p,个区域，每个处理机拥有一个区域；,,通信时间,——,广播数据：,t,comm1,= t,startup,+ n t,data,,每个处理机都有,p,个“小”桶，并将自己区域中的,n/p,个数据分散到这些小桶中；计算时间：,t,comp1,=,n/p,,将小桶中的,n / p,2,个数据倒入,p,个大桶；,,通信时间,——,将,p-1,个小桶的内容发送给其它处理机，并从,p-1,个处理机接收属于该处理机的大桶的数据：,,t,comm2,=2 (p -1) (t,startup,+ n/p,2,t,data

17、,),,对大桶中的数据排序，计算时间：,t,comp2,= (,n/p,) log (,n/p,),,算法执行时间,=,,,n/p,+ (,n/p)log(n/p,) + (2p-1)t,startup,+ (n+2n/p-2n/p,2,) t,data,,未排序的数列,n/p,个数,…………,数据分段,P,2,个小桶,,,,,…,,,,,…,,,,,…,,,,,…,合并数列,,……,腾空小桶,已排好序的数列,P,个处理机,,,,,…………,对大桶数据排序,,,,,,,,,…………,各种算法的执行时间对比,串行算法：,,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),如果原有数列在一个已知区域,[0,，,a –1],均匀地分布，那么，我们才会得到高效率的桶排序的串行和并行算法。,,对于采用了,p,2,个小桶的并行算法,2,中，腾空各个,(p,个,),处理机拥有的,p,个小桶的内容是指将自己拥有的,p -1,个小桶的内容分别发送给其它,p -1,个处理机。在

19、,MPI,中该操作可由一个群体操作例程来实现：,,,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,发送缓冲区,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,接收缓冲区,应用,2 ----,数值积分,将积分区域分割为一系列矩形，利用这些矩形的面积近似求出积分区域的值。,矩形面积,=,d * f ( p + d / 2 ),x,f(x,),a p,d,q b,,,,,将积分区域分割为一系列梯形，利用这些梯形的面积近似积分区域的值。,矩形面积,=,d * ( f ( p ) + f ( q ) ) / 2 ),x,f(x,),a p,d,q b,,,,,,当,d,越小,，算法求出的近似值越精确。,,显然我们能很容

21、易地将数值积分问题分解为多个相互独立的部分，每个部分由一个单独的进程完成计算。,,一般的静态分配的并行算法,是将积分区域按处理机的个数,p,分为,p,块，然后每个处理机（进程）计算一块区域的面积，最后将其归并，得到整个区域的积分值。,采用矩形方法，即计算每个小区间的中间点的函数值的矩形面积的并行算法：,,面积,=,,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),：并行编程环境中的虚拟存储器，由一组有序的元组构成。并行执行的进程通过共享数据元组进行交互。,,见,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.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,体问题是利用牛顿的万有引力定律和运动定律模拟太空中星体的运动轨迹。,,万有引力定律：质量为,m,a,和,m,b,,的两个物体间的引力为：,应用,3 ---- N,体问题,其中：,G (6.67259*10,-11,米,3,/(,千克,.,秒,2,)),是引力常数，

28、,r,为两物体间的距离。,G m,a,m,b,,,r,2,F =,————,—,应用,3 ---- N,体问题,一个物体在受力的情况下，将根据牛顿第二定律产生加速度：,,,F = ma,,,m,是物体的质量，,F,是物体所受的力，,a,是物体获得的加速度 。,实现细节：,,设模拟天体运动的时间间隔为,Δ,t,，物体的质量为,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,,时间后，其位置的变化为

29、：,,,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]

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,体问题的并行算法,,顺序算法的时间复杂性为：,O(N,2,),。,,将串行代码简单地并行化，会产生大量的信息交换。因为,N,体问题中计算每一个物体新的位置和新的速度都受其它,N-1,个物体信息,(,位置,),的影响。,,

31、并行算法的时间复杂性可以利用簇化方法减少，即一簇远距离的物体可以大略地作为一个簇的总质量位于该簇物体重心的单个远距离物体。,,这种簇化思想可以递归使用。,,,,,,,,,,,,质量中心,远距离物体簇,r,Barnes-Hut,算法,----,创建,8,叉树,,假设在一个三维立方体空间中包含有,N,个星体,,1.,将立方体分为,8,个子立方体；,,2.,如果某个子立方体不含有星体，则删除该子立方体，以后不再考虑它；,,3.,如果某立方体仅含有,1,个星体，则保留该子立方体；,,4.,如果某立方体含有多于,1,个的星体，则继续递归地分割这个子立方体，直到每个子立方体仅含有一个星体为止。,,8,叉树

32、,----,每个节点都有,8,条边的树。,,树的叶子表示含有,1,个星体的单元；,,当树建立后，子立方体的总质量和该子立方体的重心将储存在各个节点中。,Barnes-Hut,算法：,,for (t = 0; t <,t,max,; t++),/* for each time period */,,{,,,Build_Octatree,( );,/*,建立,8,叉树 *,/,,,Total_Mass_Center,( );,/*,计算各簇的总质量和重心 *,/,,,Compute_Force,( );,/*,遍历树计算物体所受的力 *,/,,Update( );,/*,更新物体的位置和速度 *

33、,/,,},说明：,,Build_Octatree,( ),：,利用空间中的各物体原有的位置计算。,,Total_Mass_Center,( ),：,是从叶子节点开始到根节点，计算每个子立方体总的质量和重心位置，非叶子节点（一簇）的质量通过其孩子的质量累加得到，而重心则通过孩子们的质量和重心合成得到。,说明（续）：,,Compute_Force,( ),：,每个物体所受的力可以通过从根遍历这棵树来获得。当到达某个节点时，若簇的估计值已近似实际物体的值，则遍历结束，否则继续向下遍历。,,在模拟,N,体问题中，判断何时获得近似值的简单标准：,,假设簇包含在一个体积为,d,×d×d,的立方体中，到重心的距离是,r,，当,r, d / ,,时，就可以使用估计值了。  为一个等于或小于,1.0,的常数。,Barnes-Hut,算法：,,for (t = 0; t <,t,max,; t++),/* for each time period */,,{,,,Build_Octatree,( );,/*,建立,8,叉树 *,/,,,Total_Mass_Center,( );,/*,计算各簇的总质量和重心 *,/,,,Compute_Force,( );,/*,遍历树计算物体所受的力 *,/,,Update( );,/*,更新物体的位置和速度 *,/,,},