并行算法的一般设计策略.ppt

1,分布式系统开发,计算机学院计算机科学与技术系主讲：陈 蕾E-mail:,2,第六章 并行算法的一般设计策略,6.1 串行算法的直接并行化6.2 从问题描述开始设计并行算法6.3 借用已有算法求解新问题6.4 串行算法的直接并行化补充实例:八皇后问题和单源最短路径问题,3,设计并行算法一般有3种方法：（1）检查和开拓现有串行算法中固有的并行性，直接将其并行化，该方法并不是对所有问题总是可行的，但对很多应用问题仍不失为一种有效的方法；（2）从问题本身的描述出发，根据问题的固有属性，从头设计一个全新的并行算法，这种方法有一定难度，但所设计的并行算法通常是高效的；（3）借助已有的并行算法求解新问题。,4,6.1 串行算法的直接并行化,方法描述发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。评注由串行算法直接并行化的方法是并行算法设计的最常用方法之一；并非所有的串行算法都可以并行化；一个好的串行算法并不能并行化为一个好的并行算法，相反一个不好的串行算法则有可能产生很优秀的并行算法，例如枚举排序不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法；显著优点：无需考虑算法的稳定性、收敛性等复杂问题。,5,积分算法的直接并行化-的计算,6,计算的串行C代码,#define N 1000000main()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);,7,k个处理器并行地计算部分和,8,计算的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 N；i=i+numtask)temp=(i+0.5)*w；local=4.0/(1.0+temp*temp)+local；C：MPI_Reduce(&local,&pi,1,MPI_Double,MPI_SUM,0,MPI_COMM_WORLD)；/*MPI 归约操作*/D：if(taskid=0)printf(“pi is%f n”，pi*w)；MPI_Finalize()；/*MPI 结束*/,9,枚举排序,枚举排序是一种最简单的排序算法。该算法的具体思想是（假设按关键字递增排序），对每一个待排序的元素统计小于它的所有元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a1an中。首先将a1与a2 an比较，记录比其小的数的个数，令其为k，a1就被存入有序的数组b1bn的bk+1位置上；然后将a2与a1，a3an比较，记录比其小的数的个数，依此类推。时间复杂度为O（n2）。,10,枚举排序串行算法,输入：a1an输出：b1bnBeginfor i=1 to n do(1)k=1(2)for j=1 to n do if aiaj thenk=k+1 end ifend for(3)bk=aiend forEnd,11,枚举排序的并行算法,对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。,12,枚举排序并行算法,输入：无序数组a1an输出：有序数组b1bnBegin(1)P0播送a1an给所有Pi(2)for all Pi where 1in para-do(2.1)k=1(2.2)for j=1 to n doif(ai aj)or(ai=aj and ij)then k=k+1end if end for(3)P0收集k并按序定位End,步骤的时间复杂度为O（n）；步骤中主进程完成的数组元素重定位操作的时间复杂度为O（n），通信复杂度分别为O（n）；同时中的通信复杂度为O（n2）；所以总的计算复杂度为O（n），总的通信复杂度为O（n2）。,13,快速排序（Quick Sort）,快速排序（Quick Sort）是一种最基本的排序算法基本思想：在当前无序区R1,n中取一个记录作为比较的“基准”，用此基准将当前的无序区R1,n划分成左右两个无序的子区R1,i-1和Ri,n(1in)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字。快速排序算法的性能主要决定于输入数组的划分是否均衡，而这与基准元素的选择密切相关。在最坏情况下，划分的结果是一边有n-1个元素，而另一边有0个元素。如果每次递归排序中的划分都产生这种极度的不平衡，那么整个算法的复杂度将是（n2）。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的复杂度为O（nlogn）。在一般的情况下该算法仍能保持O（nlogn）的复杂度，只不过其具有更高的常数因子。,14,快速排序算法的串行实现,SISD上的快排序算法 输入：无序序列(Aq,Ar)输出：有序序列(Aq,Ar)Procedure QUICKSORT（A,q,r）Begin if qr then x=Aq s=q/s为计数器，表示比基准元素小或等于的元素个数 for i=q+1 to r do if Aix then s=s+1 swap(As,Ai)endif swap(Aq,As)QUICKSORT(A,q,s)QUICKSORT(A,s+1,r)endif End,15,快速排序算法的并行思路,快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。,16,快速排序并行算法,输入：无序数组data1,n，使用的处理器个数2m输出：有序数组data1,nBeginpara_quicksort(data,1,n,m,0)End假设quicksort(data,i,j)表示快速排序串行算法,17,快速排序并行算法,procedure para_quicksort(data,i,j,m,id)Begin(1)if m=0 then(1.1)Pid call quicksort(data,i,j)else(1.2)Pid:r=patrition(data,i,j)(1.3)P id send datar+1,j to Pid+2m-1(1.4)para_quicksort(data,i,r-1,m-1,id)(1.5)para_quicksort(data,r+1,j,m-1,id+2m-1)(1.6)Pid+2m-1send datar+1,j back to Pidend ifEnd,18,6.2 从问题描述开始设计并行算法,方法描述从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。评注挖掘问题的固有特性与并行的关系；设计全新的并行算法是一个挑战性和创造性的工作。,19,串匹配问题,串匹配（String Matching）问题是计算机科学中的一个基本问题，也是复杂性理论中研究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学等领域有着广泛的应用。而且，串匹配是这些应用中最耗时的核心问题，好的串匹配算法能显著地提高应用的效率。因此，研究并设计快速的串匹配算法具有重要的理论价值和实际意义。,20,串匹配问题,串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配（Keyword Matching）。所谓关键词匹配，是指给定一个长为n的文本串T1，n和长为m的模式串P1，m，找出文本串T中与模式串所有精确匹配的子串的起始位置。,21,KMP串匹配算法,KMP算法首先是由D.E.Knuth、J.H.Morris以及V.R.Pratt分别设计出来的，所以该算法被命名为KMP算法。KMP串匹配算的基本思想是：对给出的的主串（文本串）T1，n与模式串P1，m，假设在模式匹配的进程中，执行Ti和Pj的匹配检查。若Ti=Pj，则继续检查Ti+1和Pj+1是否匹配。若TiPj，则文本串指针无需回溯，模式串指针回溯至失败函数处。,22,KMP算法,23,并行串匹配算法的设计思路,设计的思路为：将长为n的文本串T均匀划分成互不重叠的p段，分布于处理器0到p-1中，且使得相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长度为（最后一个处理器可在其段尾补上其它特殊字符使其长度与其它相同）。再将长为m的模式串P和模式串的失败函数newnext播送到各处理器中。各处理器使用改进的KMP算法并行地对局部文本段进行匹配，找到所有段内匹配位置。,24,并行串匹配算法的设计思路,但是每个局部段（第p-1段除外）段尾m-1字符中的匹配位置必须跨段才能找到。一个简单易行的办法就是每个处理器（处理器p-1除外）将本局部段的段尾m-1个字符传送给下一处理器，下一处理器接收到前一处理器传来的字符串后，再接合本段的段首m-1个字符构成一长为2(m-1)的段间字符串，对此字符串做匹配，就能找到所有段间匹配位置。但是这样做算法的通信量很大，必须采用改进通信的方法降低通信复杂度。,25,降低通信复杂度的设计思路,降低播送模式串和newnext函数的通信复杂度。利用串的周期性质，先对模式串P作预处理，获得其最小周期长度|U|、最小周期个数s及后缀长度|V|（P=UsV），只需播送U，s，|V|和部分newnext函数就可以了，从而大大减少了播送模式串和newnext函数的通信量。而且串的最小周期和next函数之间的关系存在着某种简单规律，使得能够设计出常数时间复杂度的串周期分析算法。,26,降低通信复杂度的设计思路,降低每个处理器（处理器p-1除外）将本局部文本段的段尾m-1个字符传送给下一处理器的通信复杂度。每个处理器在其段尾m-1个字符中找到模式串P的最长前缀串，因为每个处理器上都有模式串信息，所以只需传送该最长前缀串的长度就行了。这样就把通信量从传送模式串P的最长前缀串降低到传送一个整数，从而大大地降低了通信复杂度。,27,判断串周期性的见证函数,定义5.4 对于给定的j(1j m/2)，如果Pj:m P1:m-j+1，则存在某个（1 m-j+1），使得P()P(s)，其中s=j-1+，记WITj=.根据WITj函数可以区分串是周期的还是非周期的：1）、对于所有的2j m/2，当且仅当WITj 0时，则串是非周期的；2）、对于所有的2j m/2，若存在某个j，使得WITj=0，则串是周期的；例：p137 5.7假定P1=abaababa,P2=abaabaaab,P3=abaabaaabaabab,试计各自的WITj函数，并判断他们的周期性,28,研究发现，两串能否匹配是与串本身的特性有关的。这种特性，就是串的周期性。串可以分为周期的和非周期的。可以引入见证函数（Witness Function）来判断串的周期性。确定了串的周期性后就可以先研究非周期串的匹配，然后在此基础上再研究周期串的匹配。对于非周期串的研究，就是如何利用见证函数快速地找出P在T中的位置。为此，引入竞争函数。先把正文串分成小段，借助于见证函数并行地计算竞争函数值，找出那些可能匹配的位置。然后逐步扩大正文串分段的长度，并计算竞争函数值，在可能匹配的位置中排除那些不可能匹配的位置。最后在剩下的可能位置中验证哪些是符合要求的位置。,29,假设T=abaababaababaababaababa，n=23，P=abaababa，m=8。由见证函数可知P是非周期串。因为P只可能在前16个位置上与T匹配，所以在找所有“可能位置”时只考虑T的前16个字符。匹配时，先要计算见证函数值，然后由其计算 的值，找到可能匹配的位置。计算 时，可以所有的块并行计算。先将P和T分成长度为2的块，用模式块(ab)与正文块(ab)(aa)(ba)(ba)(ab)(ab)(aa)(ba)进行匹配可知模式块(ab)在位置1，4，6，9，11，14，16出现匹配。再把P与T划分成长度为4的块，用模式块(abaa)与正文块(abaa)(baba)(abab)(aaba)进行匹配可知在位置 1，6，11，16出现匹配（位置4、9、14被淘汰）；最后用模式串(abaababa)在正文串的位置1，6，11，16进行检查，排除那些不匹配的 位置。本例中这4个位置都匹配。,30,6.3 借用已有算法求解新问题,方法描述找出求解问题和某个已解决问题之间的联系；改造或利用已知算法应用到求解问题上。评注 这是一项创造性的工作，两类问题表面上往往完全不同，因此很难联想到被借用的方法，需要设计者有敏锐的观察力和丰富的并行算法设计经验。欲使用借用法时，要注意观察问题的特征和算法的结构、形式，联想与本问题相似的已有算法。可以注意寻找要解决的问题与某些著名问题之间的相似性或本问题的算法与某些著名算法之间的相似性。使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。,31,小结,设计并行算法是一件复杂的事情，而并行算法的设计这门学科还属于发展中的一门学科，所以目前尚无一套普遍实用的、系统的设计方法学；本章介绍的三种并行程序设计方法显然不能涵盖并行程序设计的全部。算法设计是很灵活而无定规可循的。以上介绍的三种方法只是为并行算法设计提供了三条可以尝试的思路。,32,附1：八皇后问题,所谓八皇后问题（Eight Queens Problem），是在8*8格的棋盘上，放置8个皇后。要求每行每列放一个皇后,而且每一条对角线和每一条反对角线上最多只能有一个皇后，即对同时放置在棋盘的任意两个皇后 和，不允许 或者 的情况出现。,33,八皇后问题的串行递归算法,procedure PlaceQueens(chessboard,row)/*从chessboard的第row行开始放置皇后*/Begin if row 8 then OutputResult(chessboard)/*结束递归并输出结果*/elsefor col=1 to 8 do/*判断是否有列、对角线或反对角线冲突*/（1）no_collision=true（2）i=1（3）while no_collision and i row do（3.1）if collides(i,chessboardi,row,col)thenno_collision=false end if（3.2）i=i+1 end while（4）if no_collision then（4.1）chessboardrow=col/*在当前位置放置一个皇后*/（4.2）go(step+1,place)/*递归地从下一行开始放置皇后*/end if end for end ifEnd/*PlaceQueens*/,34,八皇后问题的并行算法,该算法是将八皇后所有可能的解置于相应的棋盘上，主进程负责生成初始化的棋盘，并将该棋盘发送到某个空闲的从进程，由该从进程求出该棋盘上满足初始化条件的所有的解。这里，我们假定主进程只初始化棋盘的前两列，即在棋盘的前两列分别放上2个皇后，这样就可以产生8*8=64个棋盘。,35,主进程算法,procedure EightQueensMasterBegin（1）active_slaves=n/活动从进程（2）while active_slaves 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 whileEnd/*EightQueensMaster*/,36,从进程算法,procedure EightQueenSlaveBegin（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 ifend whileEnd/*EightQueenSlave*/,37,附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算法，并将其并行化。,38,最短路径问题,用带权的有向图表示一个交通运输网，图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图中的边是否有路可达另一顶点？若有多条路径可达，则在所经过的路径中，各边上权值之和最小的一条路径最短路径。,这就是路由选择。如：邮政自动分拣机的路选装置、计算机网络中的路由选择等。,问题提出,39,单源最短路径：指的是对已知图G=(V,E)，给定源点sV，找出s到图中其它各顶点的最短路径。每对结点间的最短路径指的是对已知图G=(V,E)，任意的顶点Vi,Vj V，找出从Vi到Vj的最短路径。,两种最常见的最短路径算法：求单源最短路径的迪杰斯特拉（Djikstra）算法和求所有顶点之间的最短路径的弗洛伊德（Floyd）算法。,40,单源最短路径问题：给定带权有向图G=(V,E)，求从某个给定的源点v0V到其余各顶点的最短路径。,迪杰斯特拉算法,41,(a)带权的有向图G,(b)图G顶点0的单源最短路径,迪杰斯特拉算法按从源点到其他各顶点的最短路径长度的从小到大的次序逐一产生最短路径。,42,把V分成两组：（1）S：存放已求得最短路径的顶点的集合（2）T=V-S：尚未确定最短路径的顶点集合将T中顶点按最短路径非递减的次序加入到S中。,迪杰斯特拉（Dijkstra）算法思想：,这个过程中，总保持：从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度。而且每个顶点对应一个距离值：S中顶点对应的距离值，是从V0到此顶点的最短路径长度；T中顶点对应的距离值，是从V0到此顶点的只包括S中顶点作中间顶点的当前最短路径长度。,43,单源最短路径图例,求上图中源点0到其他各顶点的最短路径,10,50,70,44,单源最短路径图例,求上图中源点0到其他各顶点的最短路径,10,50,25,70,45,单源最短路径图例,求上图中源点0到其他各顶点的最短路径,10,45,25,60,46,单源最短路径图例,求上图中源点0到其他各顶点的最短路径,10,45,25,55,47,单源最短路径图例,求上图中源点0到其他各顶点的最短路径,10,45,25,55,48,单源最短路径图例,求上图中源点0到其他各顶点的最短路径,10,45,25,55,49,迪杰斯特拉算法求单源最短路径步骤：,首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有顶点之间的最短路径都已求得为止。,初始状态下集合S中只有源点v0，即：S=v0，T=其余顶点。T中顶点vi对应的当前最短路径长度：若存在，为弧上的权值w(v0,vi)若不存在，为,50,从T中选取一个当前最短路径长度最小的顶点vk加入S。对T中剩余顶点vi的当前最短路径长度进行修改：若加进vk作中间顶点，从v0到vi的距离值比不加vk的路径要短，则修改此距离值。重复上述步骤，按照当前最短路径长度的非减次序产生下一条最短路径，并将该路径的终点tT加入S中，并更新T中剩余顶点的当前最短路径长度。直到SV时（即从源点v0到其他所有结点之间的最短路径都已求得为止），算法结束。,51,选择数据结构,一维数组d di中存放从源点v0到vi的当前最短路径长度，该路径上除顶点vi自身外，其余顶点都属于S，并且是所有这些路径中的最短者。,一维整型数组path pathi给出从v0到顶点vi的最短路径上，位于顶点vi前面的那个顶点。例如：从v0到v1的最短路径为（v0,v2,v3,v1）则有path1=3，path3=2，path2=0,一维布尔数组s 若si为true，表示顶点vi在S中；否则表示vi在V-S中。,52,初始状态,S=v0，T=其余顶点。,源点v0到自身的路径长度为0，路径上0前面的顶点不存在因此为-1。,初始状态下T中顶点vi对应的当前最短路径长度di和该路径上i前面的结点pathi值为：若存在，则di为弧上的权值w(v0,vi)，且pathi=0；若不存在，则di为，且pathi=-1。,50，0 10，0，-1 70，0，-1,53,第一条最短路径是T=V-v0集合中所有顶点的当前最短路径中最短者：,求第一条最短路径,选择顶点v2加入集合S，则d2为源点v0到顶点v2的最短路径，path2为该最短路径上顶点v2前面的那个顶点v0。,54,顶点vk加入S后，对所有T=V-S集合中的剩余顶点vi，按公式修正从源点v0到该顶点的当前最短路径长度：,更新d和path,若di值被更新，则pathi值也随之更新为k。,55,重复下面步骤：,（1）按照非减次序选择下一条最短路径的终点（T=V-S中具有最短的当前最短路径长度的顶点vk），满足：,直到SV时算法结束。,56,选择顶点v3加入S。则d3为源点v0到顶点v3的最短路径，path3为最短路径上顶点v3前面的那个顶点。,57,58,将顶点v1加入S。则d1为源点v0到顶点v1的最短路径，path1为最短路径上顶点v1前面的那个顶点。,59,60,选择顶点v4加入S。则d4为源点v0到顶点v4的最短路径，path4为最短路径上顶点v4前面的那个顶点。,61,62,Dijkstra算法(Dijkstra Algorithm),Dijkstra算法(Dijkstra Algorithm)是单源最短路径问题的经典解法之一，基本思想如下：假定有一个待搜索的顶点表VL，初始化时做：dist(s)0，dist(i)=(is)，VL=V。每次从VL（非空集）中选取这样的一个顶点u，它的dist(u)最小。将选出的u点作为搜索顶点，对于其它还在VL内的顶点v，若E,而且dist(u)+w(u,v)dist(v)，则更新dist(v)为dist(u)+w(u,v)，同时从VL中将u删除，直到VL 成为空集时算法终止。,63,Dijkstra串行算法,输入：边权邻接矩阵W（约定顶点i，j之间无边连接时w(i,j)=，且w(i,i)=0）、待计算顶点的标号s输出：dist(0:N-1)，其中dist(i)表示顶点s到顶点i的最短路径(1iN)procedure DijkstraBegin（1）dist(s)=0（2）for i=0 to N-1 do if is then dist(i)=endfor（3）VL=V（4）for i=0 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 endforEnd,64,Dijkstra串行算法并行思路,上述算法的(1)(2)两步中，每个处理器分派n=N/p个节点进行初始化。第(4.1)步可以并行化为：首先每个处理器分派 n个节点分别求局部最小值，然后再p个处理器合作求全局最小值，最后再将这一最小值广播出去。p个处理器合作方法如下：当p为偶数时，后p/2个处理器将自己的局部最小值分别发送到对应的前p/2个处理器中，由前p/2个处理器比较出2个局部最小值中相对较小者并保留。当p为奇数时，设p=2h+1,则后h个处理器的值分别发送到前h个处理器中，比较并保留小值。一次这样的循环过后，p个最小值减少了一半，两次后，变为1/4，如此一层一层的比较，P次循环后，就可以得出唯一的全局最小值。,65,Dijkstra串行算法并行思路,第(4.2)步可以每个处理器分配n个顶点，然后独立进行更新dist的操作。根据以上思路，最短路径的并行算法使用了p个处理器，处理器0只进行输入输出工作，不参与任何其它计算；因此实际参加运算的处理器为p-1个，所以有n=N/(p-1)；另外，布尔数组bdist用来标记各顶点是否已从VL中取出。,