并行算法的一般设计方法

第四章

并行算法的一般设计方法4.1串行算法的直接并行化

4.2从问题描述开始设计并行算法

4.3借用已有算法求解新问题

主要内容设计并行算法的方法串行算法直接并行化：检测串行算法中是否有可以并行执行的部分，然后将其并行化从问题本身出发，设计并行算法：从开始分析问题时，就考虑将其并行化借用已有算法求解新问题：根据问题的相似性，利用已有的并行算法来求解新问题

4.1串行算法的直接并行化方法描述发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。

4.1串行算法的直接并行化说明由串行算法直接并行化的方法是并行算法设计的最常用方法之一；不是所有的串行算法都可以直接并行化的；一个好的串行算法并不能并行化为一个好的并行算法；许多数值串行算法可以并行化为有效的数值并行算法。4.1.1快速排序及其串行算法基本思想：（1）将当前无序序列(A[q],…,A[r])分成两个非空子序列（A[q],…A[s])和(A[s+1],…A[r])，其中第一个子序列中的任意元素都小于等于后一个子序列中的任意元素（2）对划分后的两个子序列实行递归运算（3）直到子序列中仅有两个元素为止如何选定主元？如何将一个序列

划分成两个序列？4.1.1快速排序及其串行算法输入：无序序列(A[q],…,A[r])输出：有序序列(A[q],…,A[r])QUICKSORT(A,q,r){if(q<r)(1)x=A[q];(2)s=q;(3)for(i=q+1;i<=r;i++)if(A[i]<=x){s=s+1;swap(A[i],A[s]);}(4)swap(A[q],A[s])(5)QUICKSORT(A,q,s)(6)QUICKSORT(A,s+1,r)}递归结束条件划分后的第一个子序列划分后的第二个子序列快速排序（最坏情况）712345688123457651234412312345678123456782134567831245678567867881234567Step1:2:3:4:5:6:7:8:4.1.2快速排序的并行化思想：并行地调用串行的快速排序算法，对两个所

划分的子序列进行快速排序。4.1.2快速排序的并行化一、基于二叉树的并行选主元PRAM——CRCW上的快速排序算法

（1）构造一棵二叉排序树，其中主元是根（2）小于等于主元的元素处于左子树（3）大于等于主元的元素处于右子树（4）其左、右子树分别也是一棵二叉排序树1586424213102026对二叉树进行中序遍历可以得到排序序列4.1.2快速排序的并行化待排序序列（A1,A2

…An

）,分别存放到（P1,P2

…Pn

）,处理器Pi保存元素Ai排序树的树根为root（SM变量），左孩子为Lc[root]，右孩子为Rc[root]fi（局部变量）:存有主元的处理器号如果某处理器中的元素被选定为主元后，该处理器即可停止计算

构造出的二叉排序树是不唯一的PRAM-CRCW上的快排序二叉树构造算法Begin(1)foreachprocessoripar-do(1.1)root=i;(1.2)fi=root;(1.3)LCfi=RCfi=n+1;(2)repeatforeachprocessori!=rootdoif(Ai<Afi)||(Ai=Afi&&i<fi)

(2.1)LCfi=i;(2.2)if(i==LCfi)break;elsefi=LCfi;else

(2.3)RCfi=i

(2.4)if(i==RCfi)break;elsefi=RCfiEnd实例给定待排序序列：33，21，13，54，82，33，44，72一种候选答案一种候选答案一种候选答案问题描述：对a[1],a[2]…a[n]按照从小到大排序，排序后结果存入b[1],b[2]…b[n]思路：将a[1]与a[2]…a[n]比较，记录比其小的元素的个数，令其为k，a[1]就存入数组b[k+1]中；将a[2]与a[1]…a[n]比较，记录比其小的元素的个数，令其为k，a[2]就存入数组b[k+1]中；…4.1.3枚举排序时间复杂度为O(n2)串行枚举排序输入：无序数组a[1],a[2]…a[n]输出：有序数组b[1],b[2]…b[n]Beginfor(i=1;i<=n;i++)(1)k=0;(2)for(j=1;j<=n;j++)if((a[i]>a[j])||(a[i]==a[j]&&i>j))k=k+1;(3)b[k+1]=a[i];End并行枚举排序思想：一个长为n的输入序列，处理器个数为n每个处理器负责完成一个元素a[i]的定位处理器将所有的定位信息送到主进程主进程负责完成所有元素的最终排位并行枚举排序输入：无序数组a[1],a[2]…a[n]输出：有序数组b[1],b[2]…b[n]Begin

（1）P0播送a[1],a[2]…a[n]给所有的Pi

（2）forallPi

（1in）par-do(2.1)k=0;(2.2)for(j=1;j<=n;j++)if((a[i]>a[j])||(a[i]==a[j]&&i>j))k=k+1;（3）P0收集k并按序排位End4.1.4并行正则采样排序（PSRS）思想：均匀划分局部排序正则采样（抽取样本）采样排序选择主元主元划分全局交换归并排序方法描述从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法评注挖掘问题的固有特性与并行的关系设计全新的并行算法是一个挑战性和创造性的工作利用串的周期性的PRAM-CRCW算法是一个很好的范例4.2从问题描述开始设计

并行算法4.2从问题描述开始设计

并行算法串匹配：计算机领域研究较为广泛的问题之一应用领域文字编辑处理、图像处理、文献检索、自然语言识别、生物学定义一种模式匹配问题，在给定的文本串中找出与模式串匹配的子串的起始位置。串匹配串匹配常见问题精确匹配：KMP随机串匹配近似串匹配由两个设计者的姓名命名4.2.1KMP串匹配算法例1：正文串T：abaabaabcac模式串P：abaabcac你的匹配算法是什么？4.2.1KMP串匹配算法例2：正文串T：abcdefabcdefabcdeg模式串P：abcdefabcdeg

i=12，j=12时，T[12]≠P[12]

关键问题：如何移动模式串，重新进行P与T的比较？ij4.2.1KMP串匹配算法例2：正文串T：abcdefabcdefabcdeg模式串P：abcdefabcdeg当T[12]≠P[12]时，比较T[12]与P[6]

ijnext[12]=6KMP思想文本串T[1,n]，模式串P[1,m]，执行T[i]和P[j]的匹配情况：若T[i]=P[j]:若T[i]≠P[j]:继续检查T[i+1]和P[j+1]是否匹配模式串右移1位，检查T[i+1]和P[1]是否匹配模式串右移j-next[j]位，检查T[i]和P[next[j]]是否匹配j=11<j≤mnext函数如何构造？不断重复上述过程，直到i=n或j=m结束

next函数next函数：根据模式串本身的信息构造的。函数作用：当模式串中第j个字符与正文串的第i个字符匹配失败后，需要通过next函数将模式串进行右移。next函数定义方法：模式串有局部相同的子串next函数例：求模式串P=abaabcac的next函数j12345678模式串abaabcacnext[j]01122312next[j]=k:k为模式串中重新与T[i]字符比较的位置next函数T：ababaabcacP：T[4]≠P[4]，而next[4]=2所以比较T[4]与P[2]，模式串右移j-next[j]ijabaabcacnext函数课堂练习：P1=aaabcaabaP2=abcabcacbP3=babbabab01231123101112345101122343next函数的算法输入：模式串P[1…m]输出：next[1…m]Beginj=1;k=0;next[1]=0;while(j<P.length)if(k==0||P[j]==P[k])

{j=j+1;k=k+1;next[j]=k;}elsek=next[k];End有了next函数，KMP算法便可以实现KMP算法输入：模式串P[1…m]，正文串T[1…n]输出：模式串在正文串中的匹配位置Begini=1;j=1;while(i<=n&&j<=m)if(T[i]==P[j]){i++;j++}elseif(j==1)i++;elsej=next[j];(3)if(j==m+1)returni-m;End串匹配算法的并行化设计并行算法的出发点：正文串与模式串是否匹配，与串的自身前缀有关，这种前缀特性，就是串的周期性。如何判断串的周期性？WIT函数WIT函数定义：对于给定的j（1<j≤m/2），如果P[j:m]≠p[1:m-j+1]，则存在某个w（1≤w≤m-j+1），使得P[w]≠P[s]，其中s=j+w-1，记WIT[j]=w。（若P[j:m]=p[1:m-j+1]，则WIT[j]=0）串的周期性非周期串：对于所有2≤j≤m/2，当且仅当WIT[j]≠0周期串：

对于所有2≤j≤m/2，当存在某个j，使得WIT[j]=0串的周期性例：P1=abaababaP2=baabaabaWIT[1]=0WIT[2]=1WIT[3]=2WIT[4]=4WIT[1]=0WIT[2]=1WIT[3]=1WIT[4]=0非周期串周期串主要研究非周期串的并行串匹配算法非周期串的匹配思想：

根据WIT函数来计算模式串在正文串中的匹配位置，为了减少P和T的比较次数，引入竞争函数duel()。duel()函数：

若duel(p,q)=p，则表示当模式串在正文的位置p处匹配时，那么在另一个位置q处一定不匹配。当模式串P为非周期串时，模式串P不会同时在正文串的p处和q处匹配。

采用淘汰机制，从而减少P和T的比较次数duel()函数计算duel(p,q)过程：j=q-p+1w=WIT[j]判断T[q+w-1]与P[w]的关系：T[q+w-1]=P[w]T[q+w-1]≠P[w]duel(p,q)=q，WIT’[p]=jduel(p,q)=p，WIT’[q]=wduel()函数令text=abaababaababaaba，p=abaababa，计算duel（6,9）WIT[1]=0，WIT[2]=1，WIT[3]=2，WIT[4]=4j=q-p+1=9-6+1=4w=WIT[4]=4T[q+w-1]=T[9+4-1]=T[12]=bP[w]=P[4]=a∵T[q+w-1]≠P[w]∴duel(6,9)=6，WIT’[9]=4并行思路12345678910111213141516abaababaababaaba

14689111416161116并行思路各个处理器并行执行duel(1,2)，duel(3,4)…找出胜者各个处理器在上一轮的胜者之间执行duel函数最后经过log2n轮竞争后，有若干可能匹配的位置，然后再一一进行验证4.3借用已有算法求解新问题方法描述找出求解问题和某个已解决问题之间的联系改造或利用已知算法应用到求解问题上评注使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例

1.利用矩阵乘法求所有点对间最短路径问题说明

有向图G=(V,E)，边权矩阵W=(wij)n×n，求最短路径长度矩阵D=(dij)n×n，dij为vi到vj的最短路径长度。假定图中无负权有向回路，记d(k)ij为vi到vj至多有k-1个中间结点的最短路径长，Dk=(d(k)ij)n×n利用矩阵乘法求所有点对间最短路径计算原理(1)d(1)ij=wij

当<i,j>E，则wij=∞d(1)ij=0当i=j

(2)

利用最优性原理：d(k)ij=min1≤l≤n{d(k/2)il+d(k/2)lj}

视：”+”“×”，“min”“∑”，则上式变为d(k)ij=∑1≤l≤n{d(k/2)il×d(k/2)lj}

(4)应用矩阵乘法：D1D2D4…D2logn(=Dn)顶点间最短路径算法读入矩阵Dfor(k=1;k<=log2n;k++)(2.1)for(i=0;i<n;i++)for(j=0;j<n;j++)(2.1.1)min=MAX；flag=0;(2.1.2)for(s=0;s<n;s++)if(D[i][s]>=0&&D[s][j]>=0){flag=1;if(min>D[i][s]+D[s][j])min=D[i][s]+D[s][j]}(2.1.3)if(flag==1)M[i][j]=min;elseM[i][j]=-1;48(2.2)for(i=0;i<n;i++)for(j=0;j<n;j++)D[i][j]=M[i][j];2.利用布尔矩阵求