精简版第6章并行算法的一般设计策略.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分布式系统,Distributed System,计算机学院软件工程系,主讲：陈 蕾,E-mail:,chenleijx,1,第六章 并行算法的一般设计策略,6.1,串行算法的直接并行化,6.2,从问题描述开始设计并行算法,6.3,借用已有算法求解新问题,6.4,串行算法的直接并行化补充实例,:,八皇后问题和单源最短路径问题,2,设计并行算法一般有,3,种方法：（,1,）检查和开拓现有串行算法中固有的并行性，直接将其并行化，该方法并不是对所有问题总是可行的，但对很多应用问题仍不失为一种有效的方法；（,2,）从问题本身的描述出发，根据问题的固有属性，从头设计一个全新的并行算法，这种方法有一定难度，但所设计的并行算法通常是高效的；（,3,）借助已有的并行算法求解新问题。,3,6.1,串行算法的直接并行化,方法描述,发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。,评注,由串行算法直接并行化的方法是并行算法设计的最常用方法之一；,并非所有的串行算法都可以并行化；,一个好的串行算法并不能并行化为一个好的并行算法，相反一个不好的串行算法则有可能产生很优秀的并行算法，例如枚举排序不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法；,显著优点：无需考虑算法的稳定性、收敛性等复杂问题。,4,积分算法的直接并行化,-,的计算,5,计算,的串行,C,代码,#define N 1000000,main(),double local,pi=0.0,w;,long i;,w=1.0/N;,for(i=0;iN;i+),local=(i+0.5)*w;,pi=pi+4.0/(1.0+local*local);,printf(“pi,is%f n”,pi*w);,6,k,个处理器并行地计算部分和,7,计算,的,MPI,代码,#define N 100000,main(),double local=0.0,，,pi,，,w,，,temp=0.0,；,long i,，,taskid,，,numtask,；,A,：,w=1.0/N,；,MPI_,Init(&argc,，,&,argv,),；,/*MPI,初始化*,/,MPI _,Comm,_rank(MPI_COMM_WORLD,，,&,taskid,),；,/*,每个处理器确定各自,ID*/,MPI _,Comm,_Size(MPI_COMM_WORLD,，,&,numtask,),；,/*,每个处理器确定总处理,器个数*,/,B,：,for(i=,taskid,；,i,aj,then,k=k+1,end if,end for,(3)bk=ai,end for,End,10,枚举排序的并行算法,对该算法的并行化是很简单的，假设对一个长为,n,的输入序列使用,n,个处理器进行排序，只需每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。,11,枚举排序并行算法,输入：无序数组,a1,an,输出：有序数组,b1,bn,Begin,(1)P,0,播送,a1,an,给所有,P,i,(2)for all P,i,where 1in,para,-do,(2.1)k=1,(2.2)for j=1 to n do,if(,ai,aj,)or(,ai,=,aj,and ij)then,k=k+1,end if,end for,(3)P,0,收集,k,并按序定位,End,步骤的时间复杂度为,O,（,n,）；步骤中主进程完成的数组元素重定位操作的时间复杂度为,O,（,n,），通信复杂度分别为,O,（,n,）；同时中的通信复杂度为,O,（,n,2,）；所以总的计算复杂度为,O,（,n,），总的通信复杂度为,O,（,n,2,）。,12,快速排序（,Quick Sort,）,快速排序（,Quick Sort,）是一种最基本的排序算法,基本思想：在当前无序区,R1,n,中取一个记录作为比较的“基准”，用此基准将当前的无序区,R1,n,划分成左右两个无序的子区,R1,i-1,和,Ri,n(1in),，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字。,快速排序算法的性能主要决定于输入数组的划分是否均衡，而这与基准元素的选择密切相关。,在最坏情况下，划分的结果是一边有,n-1,个元素，而另一边有,0,个元素。如果每次递归排序中的划分都产生这种极度的不平衡，那么整个算法的复杂度将是,（,n,2,）。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的复杂度为,O,（,n,log,n,）。在一般的情况下该算法仍能保持,O,（,n,log,n,）的复杂度，只不过其具有更高的常数因子。,13,快速排序算法的串行实现,SISD,上的快排序算法,输入：无序序列,(,A,q,A,r,),输出：有序序列,(,A,q,A,r,),Procedure QUICKSORT,（,A,q,r,）,Begin,if q 8 then,OutputResult(chessboard,)/*,结束递归并输出结果*,/,else,for,col,=1 to 8 do/*,判断是否有列、对角线或反对角线冲突*,/,（,1,）,no_collision,=true,（,2,）,i=1,（,3,）,while,no_collision,and i 0 do,（,2.1,）从某个从进程,i,接收信号,signal,（,2.2,）,if signal=Accomplished then,从从进程,i,接收并记录解,end if,（,2.3,）,if,has_more_boards,then,(),向从进程,i,发送,NewTask,信号,(),向从进程,i,发送一个新棋盘,else,(),向从进程,i,发送,Terminate,信号,(),active_slaves,=,active_slaves,-1,end if,end while,End/*,EightQueensMaster,*/,35,从进程算法,procedure,EightQueenSlave,Begin,（,1,）向主进程发送,Ready,信号,（,2,）,finished=false,（,3,）,while not finished do,（,3.1,）从主进程接收信号,signal,（,3.2,）,if signal=,NewTask,then,(),从主进程接收新棋盘,()if,新棋盘合法,then,在新棋盘的基础上找出所有合法的解，并将解发送,给主进程,end if,else,/*signal=Terminate*/,finished=true,end if,end while,End,/*,EightQueenSlave,*/,36,附,2,：单源最短路径问题,单源最短路径,(Single Source Shortest Path),问题是指求从一个指定顶点,s,到其它所有顶点,i,之间的距离，因为是单一顶点到其它顶点的距离，所以称为单源。设图,G(V,E),是一个有向加权网络，其中,V,和,E,分别为顶点集合和边集合，其边权邻接矩阵为,W,，边上权值,w(i,j,)0,，,i,jV,，,V=0,1,N-1,。,设,dist(i),为最短的路径长度，即距离，其中,sV,且,is,。这里采用著名的,Dijkstra,算法，并将其并行化。,37,把,V,分成两组：,（1）,S,：存放,已求,得,最短路径的顶点的集合,（2）,T=V-S,：,尚未确定最短路径的顶点集合,将,T,中顶点按最短路径,非递减,的次序加入到,S,中,。,迪杰斯特拉（,Dijkstra,）算法思想,：,这个过程中，总,保,持,：,从源点,V,0,到,S,中各顶点,的最短路径长度都,不大于,从,V,0,到,T,中任何顶点,的最短路径长度,。,而且,每个顶点对应一个距离值,：,S,中顶点,对应的距离值,，是,从,V,0,到此顶点的,最短路径长度,；,T,中顶点,对应的距离值,，是,从,V,0,到此顶点的,只包括,S,中顶点作中间顶点,的,当前,最短路径长度,。,38,迪杰斯特拉算法求单源最短路径步骤：,首先求得长度,最短,的一条最短路径，再求得长度,次短,的一条最短路径，,依此类推,，直到从源点到其它所有顶点之间的最短路径都已求得为止。,初始状态,下,集合,S,中只有源点,v,0,，即：,S,=,v,0,，,T,=,其余顶点,。,T,中顶点,v,i,对应的,当前最短路径长度,：,若,存在,，为,弧上的权值,w(v,0,v,i,),若,不存在,，,为,39,从,T,中选取一个,当前最短路径长度最小,的顶点,v,k,加入,S,。,对,T,中剩余顶点,v,i,的,当前最短路径长度,进行,修改,：,若加进,v,k,作中间顶点，从,v,0,到,v,i,的距离值比不加,v,k,的路径,要短,，则,修改此,距离值,。,重复上述步骤，按照当前最短路径长度的,非减次序,产生,下一条最短路径,，并将该路径的,终点,t,T,加入,S,中，并,更新,T,中剩余顶点的,当前最短路径长度,。,直到,S,V,时（即,从源点,v,0,到其他所有结点之间的最短路径都已求得,为止），算法结束。,40,选择数据结构,一维数组,d,di,中存放从,源点,v,0,到,v,i,的,当前最短路径长度,，,一维整型数组,path,pathi,给出从,v,0,到顶点,v,i,的最短路径,上，,位于顶点,v,i,前面的那个顶点,。,例如：从,v,0,到,v,1,的最短路径为,（,v,0,v,2,v,3,v,1,）,则有,path1=3,，,path3=2,，,path2=0,一维布尔数组,s,若,si,为,true,，,表示顶点,v,i,在,S,中；,否则表示,v,i,在,V-S,中,。,41,S,d0,path0,d1,path1,d2,path2,d3,path3,d4,path4,d5,path5,0,0,，,-1,初始状态,S=v,0,，,T=,其余顶点,。,0,2,4,1,70,5,3,50,10,35,30,3,15,20,10,15,20,源点,v,0,到自身的路径长度为,0,，路径上,0,前面的顶点,不存在,因此为,-1,。,50,，,0 10,，,0 ,，,-1 70,，,0 ,，,-1,0,42,第一条最短路径,是,T=V-v,0,集合中所有顶点的,当前最短路径,中,最短者,：,求第一条最短路径,S,d0,path0,d1,path1,d2,path2,d3,path3,d4,path4,d5,path5,0,0,，,-1,50,，,0,10,，,0,，,-1,70,，,0,，,-1,0,2,4,1,70,5,3,50,10,35,30,3,15,20,10,15,20,选择顶点,v,2,加入集合,S,，则,d2,为源点,v,0,到顶点,v,2,的,最短路径,，,path2,为该最短路径上,顶点,v,2,前面的那个顶点,v,0,。,0,2,43,0,2,4,1,70,5,3,50,10,35,30,3,15,20,10,15,20,S,d0,path0,d1,path1,d2,path2,d3,path3,d4,path4,d5,path5,0,0,，,-1,50,，,0,10,，,0,，,-1,70,，,0,，,-1,0,2,0,，,-1,50,，,0,10,，,0,25,，,2,70,，,0,，,-1,顶点,v,k,加入,S,后，对所有,T=V-S,集合中的剩余顶点,v,i,，按公式修正从源点,v,0,到该顶点的,当前最短路径长度：,更新,d,和,path,若,di,值被更新，则,pathi,值也随之更新为,k,。,0,2,44,重复下面步骤：,（,1,）,按照,非减次序,选择,下一条最短路径,的终点（,T=V-S,中具有,最短,的,当前最短路径长度,的顶点,v,k,），满足：,直到,S,V,时算法结束。,（,2,）,v,k,加入,S,集合中后，,修正,T,中剩余顶点,v,i,的,当前最短路径长度,di,和,pathi,值：,若,di,更新，则,pathi,也相应的更新为,k,45,0,2,4,1,70,5,3,50,10,35,30,3,15,20,10,15,20,S,d0,path0,d1,path1,d2,path2,d3,path3,d4,path4,d5,path5,0,0,，,-1,50,，,0,10,，,0,，,-1,70,，,0,，,-1,0,2,0,，,-1,50,，,0,10,，,0,25,，,2,70,，,0,，,-1,选择顶点,v,3,加入,S,。则,d3,为源点,v,0,到顶点,v,3,的最短路径，,path3,为最短路径上,顶点,v,3,前面的那个顶点。,0,2,3,46,0,2,4,1,70,5,3,50,10,35,30,3,15,20,10,15,20,S,d0,path0,d1,path1,d2,path2,d3,path3,d4,path4,d5,path5,0,0,，,-1,50,，,0,10,，,0,，,-1,70,，,0,，,-1,0,2,0,，,-1,50,，,0,10,，,0,25,，,2,70,，,0,，,-1,0,2,3,0,，,-1,45,，,3,10,，,0,25,，,2,60,，,3,，,-1,0,2,3,47,0,2,4,1,70,5,3,50,10,35,30,3,15,20,10,15,20,S,d0,path0,d1,path1,d2,path2,d3,path3,d4,path4,d5,path5,0,0,，,-1,50,，,0,10,，,0,，,-1,70,，,0,，,-1,0,2,0,，,-1,50,，,0,10,，,0,25,，,2,70,，,0,，,-1,0,2,3,0,，,-1,45,，,3,10,，,0,25,，,2,60,，,3,，,-1,0,2,3,1,将顶点,v,1,加入,S,。则,d1,为源点,v,0,到顶点,v,1,的最短路径，,path1,为最短路径上,顶点,v,1,前面的那个顶点。,48,0,2,4,1,70,5,3,50,10,35,30,3,15,20,10,15,20,S,d0,path0,d1,path1,d2,path2,d3,path3,d4,path4,d5,path5,0,0,，,-1,50,，,0,10,，,0,，,-1,70,，,0,，,-1,0,2,0,，,-1,50,，,0,10,，,0,25,，,2,70,，,0,，,-1,0,2,3,0,，,-1,45,，,3,10,，,0,25,，,2,60,，,3,，,-1,0,2,3,1,0,，,-1,45,，,3,10,，,0,25,，,2,55,，,1,，,-1,0,2,3,1,49,0,2,4,1,70,5,3,50,10,35,30,3,15,20,10,15,20,S,d0,path0,d1,path1,d2,path2,d3,path3,d4,path4,d5,path5,0,0,，,-1,50,，,0,10,，,0,，,-1,70,，,0,，,-1,0,2,0,，,-1,50,，,0,10,，,0,25,，,2,70,，,0,，,-1,0,2,3,0,，,-1,45,，,3,10,，,0,25,，,2,60,，,3,，,-1,0,2,3,1,0,，,-1,45,，,3,10,，,0,25,，,2,55,，,1,，,-1,0,2,3,1,选择顶点,v,4,加入,S,。则,d4,为源点,v,0,到顶点,v,4,的最短路径，,path4,为最短路径上,顶点,v,4,前面的那个顶点。,4,50,0,2,4,1,70,5,3,50,10,35,30,3,15,20,10,15,20,S,d0,path0,d1,path1,d2,path2,d3,path3,d4,path4,d5,path5,0,0,，,-1,50,，,0,10,，,0,，,-1,70,，,0,，,-1,0,2,0,，,-1,50,，,0,10,，,0,25,，,2,70,，,0,，,-1,0,2,3,0,，,-1,45,，,3,10,，,0,25,，,2,60,，,3,，,-1,0,2,3,1,0,，,-1,45,，,3,10,，,0,25,，,2,55,，,1,，,-1,0,2,3,1,4,0,，,-1,45,，,3,10,，,0,25,，,2,55,，,1,，,-1,0,2,1,4,3,51,Dijkstra,串行算法,输入：边权邻接矩阵,W,（约定顶点,i,，,j,之间无边连接时,w(i,j)=,，且,w(i,i,)=0,）、待计算顶点的标号,s,输出：,dist(0:N-1),，其中,dist(i,),表示顶点,s,到顶点,i,的最短路径,(1iN),procedure,Dijkstra,Begin,（,1,）,dist(s,)=0,（,2,）,for i=0 to N-1 do,if i,s then,dist(i,)=,w(s,i,),endfor,（,3,）,VL=V-s,（,4,）,for i=1 to N-1 do,(4.1),从,VL,中找一个顶点,u,，使得,dist(u,),最小,(4.2)for(,每个顶点,vVL,)and(E)do,if dist(u)+w(u,v)dist(v)then dist(v)=dist(u)+w(u,v),endif,endfor,（,5,）,VL=VL-u,endfor,End,每个处理器可分派,n=N/p,个节点进行初始化。,首先每个处理器分派,n,个节点分别求局部最小值，然后再,p,个处理器合作求全局最小值，最后再将这一最小值广播出去。,每个处理器分配,n,个顶点，然后独立进行更新,dist,的操作。,根据以上思路，最短路径的并行算法使用了,p,个处理器，处理器,0,只进行输入输出工作，不参与任何其它计算；因此实际参加运算的处理器为,p-1,个，所以有,n=N/(p-1),。,52,Dijkstra,串行算法并行思路,p,个处理器合作方法如下：当,p,为偶数时，后,p/2,个处理器将自己的局部最小值分别发送到对应的前,p/2,个处理器中，由前,p/2,个处理器比较出,2,个局部最小值中相对较小者并保留。,当,p,为奇数时，设,p=2h+1,则后,h,个处理器的值分别发送到前,h,个处理器中，比较并保留小值。一次这样的循环过后，,p,个最小值减少了一半，两次后，变为,1/4,，如此一层一层的比较，,p,次循环后，就可以得出唯一的全局最小值。,53,输入：边权邻接矩阵,W,（约定顶点,i,，,j,之间无边连接时,w(i,j,)=,，且,w(i,i,)=0,）、待计算顶点的标号,s,输出：,dist(0:N-1),，其中,dist(i,),表示顶点,s,到顶点,i,的最短路径,(1iN),procedure,Dijkstra,-parallel,Begin,(1),处理器,0,读入边权邻接矩阵,W,/*,以下初始化,dist,和,bdist,数组*,/,(2),for,每个顶点,i,par_do,if i=s then,dist(i,)=0,bdist(i,)=TRUE,/,布尔数组,bdist,用来标记各顶点是否已从,VL,中取出,else,dist(i,)=,w(i,s,),bdist(i,)=FALSE,endif,endfor,Dijkstra,并行算法,54,/*,以下是算法主循环*,/,(3),for i=1 to N-1 do,/*,各处理器找出自己负责范围内未搜索节点中最小的,dist*/,(3.1)for,每个顶点,j,par_do,index=min j|,bdist(j,)=FALSE,/index,表示节点标号,num=,dist(index,),endfor,/*,以下各处理器协作对,p-1,个,index,求最小*,/,(3.2)calnum=p-1,for j=1 to(p-1),par_do,if,calnum,mod 2=0 then,/,本次循环参加比较的处理器个数为偶数,(),calnum,=calnum/2,(),序号大于,calnum,的处理器将,index,和,num,发送给序号比自己小,calnum,的,处理器,(),序号小于,calnum,的处理器（不包含,0,号）在自己原有的和收到的两个,num,之间，比较并保留较小者，同时记录对应的,index,else,/,本次循环参加比较的处理器个数为奇数,(),calnum,=(calnum+1)/2,(),序号大于,calnum,的处理器将,index,和,num,发送给序号比自己小,calnum,的,处理器,(),序号小于,calnum,的处理器（不包含,0,号）在自己原有的和收到的两个,num,之间，比较并保留较小者，同时记录对应的,index,endif,endfor,55,(3.3),处理器,1,广播通知其它处理器自己的,num,和,index,/*,以下并行更新*,/,(3.4)for,每个顶点,j,par_do,if,bdist(j,)=FALSE then,dist(j,)=min,dist(j,),num+w(j,index,),endif,endfor,(3.5),顶点,index,对应处理器将对应的,bdist(index,),更改为,TRUE,endfor,End,56,