并行算法的设计与分析

并行算法的设计与分析第一页，共六十四页，2022年，8月28日第9章串匹配并行算法精确串匹配并行算法多模式串匹配并行算法允许k-差别的近似串匹配并行算法允许k-误配的近似串匹配并行算法异构机群系统上近似串匹配并行算法第二页，共六十四页，2022年，8月28日串匹配技术的应用

1、Internet信息搜索2、生物信息学

3、网络入侵检测4、网络远程教学

5、电子商务6、数据挖掘

7、模式识别8、文本编辑

9、数据压缩10、图象处理

11、信号检测与处理12、其他

第三页，共六十四页，2022年，8月28日9.1分布式存储系统的精确串匹配并行算法

陈国良，林洁，顾乃杰.软件学报,2000,11(6):771-778

9.1.1顺序的KMP串匹配算法定义：精确串匹配问题是指,给定一个长度为n的正文串T[1~n]和一个长度为m的模式串P[1~m],字符T[i](1≤i≤n)和P[j](1≤j≤m)∈

(

为字符集)，查找出P在T中所有成功匹配的起始位置。顺序的KMP(Knuth

MorrisPratt)精确串匹配算法的时间复杂度为O(m+n)。

KMP算法的关键是根据给定的模式串P[1~m]定义一个next函数，next函数包含了模式串本身局部匹配的信息.

KMP算法的基本思想：

假设模式匹配进程正在执行T[i]和P[j]的匹配检查，若T[i]=P[j],则继续检查T[i+1]和P[j+1]是否匹配。

若T[i]≠P[j]，则分成两种情况：

若j=1,则模式串“右移”一位,检查T[i+1]和P[1]是否匹配;

若1<j≤m,则模式串“右移”

j-next(j)位,检查T[i]和P[next(j)]是否匹配。重复此过程，直到j=m或i=n结束。KMP算法结束时,模式串指针j-1的值就是正文串尾模式串最大前缀的长度。

第四页，共六十四页，2022年，8月28日

9.1.2改进的KMP算法、计算next函数和newnext函数的算法

算法1.改进的KMP串匹配算法procedureKMP输入:正文串T[1‥

n]和模式串P[1‥

m]输出:匹配结果match[1‥

n]Begini=1；j=1；

whilei<=ndo{while(j!=0andP[j]!=T[i])do

j=newnext[j]；

ifj=mthen{match[i-(m-1)]=1;j=next[m+1];i++;}else{j++;i++;}}

max-prefix-len=j–1;End在模式串字符重复多的情况下,利用newnext[j]使得改进的KMP算法更有效.算法2.next函数和newnext函数的计算算法procedureNEXT输入:模式串P[1‥

m];输出:next[1‥

m+1]和newnext[1‥

m]Beginnext[1]=newnext[1]=0;j=2;//newnext[j]函数同时要求满足P[next[j]]!=P[j]whilej<=m+1do{i=next[j-1];while(i!=0andP[i]!=P[j-1])doi=next[i];next[j]=i+1;ifj!=m+1then{IfP[j]!=P[i+1]thennewnext[j]=i+1elsenewnext[j]=newnet[i+1]}j++;}End第五页，共六十四页，2022年，8月28日9.1.3分布式并行串匹配算法的思想（1）将长为n的正文串T均匀划分成互不重叠的p段

分布存储于处理器0～p-1中，且使相邻的正文段分存储布在相邻处理器中，每个处理器中局部正文段的长度为[n/p](最后一个处理器可在其段尾补上其他特殊字符，

使其长度为[n/p])。（2）将长为m的模式串P和模式串的newnext函数播送到各处理器中。

各处理器使用改进的KMP算法并行地对局部正文段进行匹配，以找到所有段内匹配位置。（3）每个局部正文段（第p-1段除外）段尾m-1字符中的匹配位置必须跨段才能找到。为此，每个处理器(处理器p-1除外)将本局部段的段尾m-1个字符传送给下一处理器,下一个处理器接收前一处理器传来的m-1个字符之后,再结合本段的段首m-1个字符构成一个长为2(m-1)的段间字符子串,对此字符子串作匹配,就能找到所有段间匹配位置。但是,当m较大时这样做通信量较大。解决办法是每个处理器在其段尾m-1个字符中找到模式串P的最长前缀子串。因每个处理器都有模式串P的信息，故只需传送此前缀子串的长度Max-prefix-len即可,这样大大降低了通信量。（4）进一步降低播送模式串和newnext函数的通信复杂度：利用模式串的周期性质,对模式串P预处理，获得其最小周期长度|U|、最小周期个数s及后缀长度|V|

，其中

P=UsV

，只需播送U,s和|V|以及部分newnext函数即可，从而大大减少播送模式串和

newnext函数的通信量。第六页，共六十四页，2022年，8月28日

字符串的周期性分析

字符串的最小周期和next函数之间的关系存在着如下定理所述的规律,据此可设计出常数时间复杂度的串周期分析算法。定义：给定字符串P,如果存在字符串U以及正整数k≥2,使得串Uk是串P的前缀,则称字符串U为串P的周期.在字符串P的所有周期中长度最短的周期称为串P的最小周期。

定理：字符串P的长度为m,记u=m+1-next(m+1),则u为串P的最小周期长度.

算法3

字符串周期性分析算法输入:next[m+1]

输出:最小周期长度period-len,最小周期个数period-num,模式串后缀长度pattern-suffixlenProcrdurePERIOD-ANALYSISbeginperiod-len=m+1-next(m+1);period-num=(int)m/period-len;pattern-suffixlen=mmodperiod-len;end第七页，共六十四页，2022年，8月28日9.1.3KMP串匹配的分布式并行算法及其复杂度分析

输入:文本子串Ti[1~[n/p]]分布存储于处理器PEi的(i=0~p-1)和模式串P[1~m]存储于PE0；输出:匹配结果(1)PE0callprocedureNEXT

//PE0求模式串P的next函数和newnext函数

PE0callprocedurePERIOD-ANALYSIS//PE0对模式串P进行周期分析(2)PE0broadcastperiod-len,period-num,period-suffix-len//

播送模式串最小周期长度,最小周期个数,后缀长度

PE0broadcastP[1‥period-len]//播送模式串的最小周期

ifperiod-num=1thenBroadcastNewnext[1‥m]函数//播送模式串部分newnext函数,若周期数为1,则播送整个newnext函数

else

Broadcastnewnext[1‥2*period-len]//否则,播送两倍周期长度的newnext(3)fori=1top-1doinparallel

callprocedureREBUILD;//由传来的模式串周期和部分newnext函数并行重构整个模式串和newnext函数

fori=0top-1doinparallelKMP(Ti,P,n,0,match);//各处理器调用过程KMP并行匹配局部段,并获得局部段尾最大前缀串的长度(4)fori=0top-2doinparallel

PEisend

max-prefix-lentoPEi+1//PEi把max-prefix-len发送给处理器PEi+1fori=1top-1doinparallel

{PEi

receive

max-prefix-lenfromPEi-1//PEi接收PEi-1发送来的max-prefix-lenPEicallKMP(Ti

,P,m-1,max-prefix-len,match+m-1);}//调用KMP并行进行段间匹配算法的计算时间由步(1)中算法2的时间复杂度O(m)和算法3的时间复杂度O(1),步(3)和步(4)的改进的KMP算法的时间O(n/p)和O(m)构成.所以,算法总的计算时间复杂度为O(n/p+m)。通信复杂度由步(2)播送模式串信息(最小周期串U及最小周期长度、周期个数和后缀长度3个整数)和Newnxt函数(长度为2u的整数数组,u为串U的长度)以及步(4)传送最大前缀串长度组成,采用二分树通信技术,所以总的通信复杂度为O(ulogp)。

第八页，共六十四页，2022年，8月28日9.1.4算法实验性能

在大规模并行机曙光1000上测试了模式串长为128KB和周期串长为4KB,16KB,64KB的3组数据,每组数据的处理器数分别为1,2,4,8,16和31,文本串长分别为28MB,56MB,112MB,224MB,448MB和868MB.利用曲线拟合分别拟合周期串长为4KB,16KB,64KB

的数据,得到3个计算时间复杂度方程：

(1)周期长为4KB：t(n,p)=0.631076n/p+2.41241/p+12.4404×10-6

n-0.2106.(2)周期长为16KB：t(n,p)=0.63114n/p+2.41422/p+8.32277×10-6

n-0.214093.(3)周期长为64KB：t(n,p)=0.631078n/p+2.42302/p+6.14216×10-6

n-0.228162.

拟合结果和实验测量数据吻合。这3个拟合公式与理论推导的计算时间O(n/p+m)一致(由于固定m,所以拟合公式中没有出现m)。另外，上面3个拟合公式所对应的系数相差非常小,这说明计算时间和模式周期长几乎没有关系。曲线拟合得到通信时间与模式周期和处理器数的关系式：

comm(u,p)=0.00452519ulnp+0.00479584ln

此拟合公式和理论推导的通信复杂度O(ulogp)吻合。分析和实验结果表明算法的通信时间只和模式串的周期相关,而与文本串、模式串长度无关。.因主要关注计算量、机器数目和效率之间的关系,故把模式串长和周期看成是常数.从曲线拟合中得到计算时间和通信时间分别为：

t(n,p)=0.63n/p+2.41/p-0.21，comm(u,p)=0.0045ulnp+0.0048lnp-0.0016.

效率E=(n/p)/((t(n,p)+comm(u,p))=(n/p)(0.63n/p+2.41/p-0.21+0.045ulnp+0.0048lnp-0.0016)

工作量（数据规模）n=(E/(1-0.63E))*(0.45uplnp-0.21p+2.41).

上述表明工作量n与p

lnp成比例,该算法是可扩放的，

但不是线性可扩放的。第九页，共六十四页，2022年，8月28日9.2可重构光计算模型的多模式串并行匹配算法

钟诚，中国科技大学博士学位论文，2003.5

多模式串匹配问题所谓多模式串匹配是指，对于一个给定的总长度为M的k个模式串所构成的集合D={Pat1，Pat2，…，Patk}，Patj为第j个模式，1≤j≤k，M=

，在线输入的一个长度为n的正文T，希望使用与M成线性关系的时间预处理集合D中的所有模式串，并尽可能在O(n+tocc)时间内能够检查出那些模式在正文中匹配出现以及匹配出现的所有起始位置，其中tocc为集合D中所有模式串在正文中匹配出现的总次数。

多模式串匹配问题的特点：（1）集合D中的模式串事先知道，正文在线输入。（2）每个模式串的长度｜Patj｜比n小得多，1≤j≤k，因k值通常较大，故M远远大于n。（3）预处理集合D中所有模式串所需的时间希望与M成线性关系，正文匹配检查所需的时间应与集合D中模式串的个数k和总长度M无关。

第十页，共六十四页，2022年，8月28日

9.2.2可重构光网孔模型ORM(OpticalReconfigurableMesh)

处理层处理器偏传部件偏传层

（1）ORM由偏转层（Deflectionlayer）和处理层（Processinglayer）构成。每个处理器拥有3个光转发器和1个接收器。（2）偏转层由n2个组织成n×n网格的偏转部件（光可重构镜）构成，每个偏转部件用D(i,j)表示，1≤i,j≤n。

（3）处理层由n2个处理器组成。处理层上的n2个处理器通过总线互连成n×n可重构网孔RMESH，并且利用偏转层实现任意处理器之间单位时间的光通信。（4）每个处理器用PR(i,j)表示，1≤i,j≤n，它都有一个局部可控总线开关（处理器设置开关的连接方式为{E,W,S,N}），允许动态地将广播总线划分成若干子总线，提供规模较小的RMESH或者可重构总线段。

第十一页，共六十四页，2022年，8月28日RMESH结构

第十二页，共六十四页，2022年，8月28日9.2.2可重构光网孔模型ORM(OpticalReconfigurableMesh)

定理对于可重构光网孔模型ORM，任意n个处理器的并发读和并发写操作可以在O(1)时间内完成。

9.2.33D-ORM模型的多模式串并行匹配算法算法思想数据对准:

动态构造行总线、列总线、对角线总线处理器阵列将正文和模式字符播送到指定的位置（处理器）中，使得第l个2D-MESH上的各条行总线上的处理器存储模式串Patl，同时第l个2D-MESH上的第i条行总线上的处理器存储正文子串T[i‥i+m’-1]，1≤i≤n-m’+1，1≤l≤k。匹配比较:3D-ORM上所有处理器并行比较模式字符和正文字符。收集结果:如果第l个2D-MESH上的第i条行总线上所有处理器均比较成功，那么说明模式串Patl与正文子串T[i‥i+m’-1]产生匹配，1≤i≤n-m’+1，1≤l≤k。第十三页，共六十四页，2022年，8月28日

3D-ORM模型的多模式串并行匹配算法

//PR(i,j,l)中的行坐标i表示垂直方向、列坐标j表示水平方向，坐标l表示纵深方向，m’=max{|Patl|:1<=l<=k}，初始时正文保存在各2D-ORM的第1列处理器上，第l个模式存在第l个2D-ORM的第1行处理器对于ORM的每个2D-RMESH，动态地生成n条自左下方至右上方的对角线总线，这样n×m’×k的3D-ORM共生成k×n条对角线总线处理器阵列；(2)foralliandl,1≤i≤n，1≤l≤kdoinparallel

第1列的

PR(i,1,l)将保存在其存储器中的T[i]向其相应的对角线总线播送；(3)foralljandl,1≤j≤m’,1≤l≤kdoinparallel

第1行的PR(1,j,l)将其存储器中的Patl[j]向第j列总线处理器阵列播送；(4)foralli,jandl,1≤i≤n-m’+1，1≤j≤m’,1≤l≤kdoinparallelPR(i,j,l)比较T[i+j-1]和Patl[j]是否相等，若相等则设置开关状态{EW,S,N}连通东西开关端口，而断开南、北端口；否则设置开关状态{E,W,S,N}断开东、西、南、北4个端口；(5)foralliandl,1≤i≤n-m’+1，1≤l≤kdoinparallel

最后一列的PR(i,m’,l)从东到西向其所在的行总线处理器阵列发送“#”；(6)foralliandl,1≤i≤n-m’+1，1≤l≤kdoinparallel

第1列的PR(i,1,l)如果接收到符号“#”则输出匹配起始位置和模式串的下标l，即模式串Patl与起始位置为i的正文子串T[i‥i+

m’-1]产生匹配。第十四页，共六十四页，2022年，8月28日9.2.3ORM模型上多模式串并行匹配算法时间复杂度

对于ORM模型，因为并行播送数据、并行比较字符、并行播送特殊符号“#”等操作均可在常数时间内完成，所以有：定理

对于给定的k个模式串Patl，1≤l≤k，以及正文串T[1‥n]，3D-ORM模型上多模式串并行匹配可以在常数时间内完成。第十五页，共六十四页，2022年，8月28日9.3CREW-PRAM上允许k-差别的近似串匹配并行算法

钟诚，陈国良.软件学报,2004,15(2):159-169

编辑距离(Editdistances)与允许k-差别的近似串匹配(ApproximateStringmatchingwithk-differencecharacters)

定义1

任意给定两个串X和Y，那么串X和Y之间的编辑距离D(X,Y)定义为使用如下三种编辑操作将串X转换成串Y（或者将Y转换成X）所需的最少的编辑操作次数：①

从串X（Y）中删除一个符号（字符），②

向串X（Y）插入一个符号，③

用另一个符号替换串X（Y）中指定的某个符号。性质1两个串X和Y之间的编辑距离D(X,Y)具有如下性质：①

非负性：D(X,Y)≥0，D(X,Y)=0当且仅当X=Y；②

对称性：D(X,Y)=D(Y,X)；③三角不等式：设Z为另一个串，则D(X,Y)≤D(X,Z)+D(Z,Y)。定义2

对于任意给定的一个长度为n的串X[1‥n]，称X[i‥j]为串X的子串，特别地，子串

X[1‥i]称为串X的前缀，而子串X[j‥n]则称为串X的后缀，其中1≤i，j≤n。

定义3

所谓允许k-差别的近似串匹配是指：对于任意给定的一个长度为m的称为模式的串

Pat[1‥m]和一个长度为n的称为正文的串T[1‥n]，m<n，并给定一个在线输入的正整数k，0≤k<m

，寻找出编辑距离小于等于k的模式Pat在正文T中所有匹配出现的终止位置j，1≤j≤n。第十六页，共六十四页，2022年，8月28日9.3CREW-PRAM上允许k-差别的近似串匹配并行算法

9.3.2允许k-差别的近似串匹配的动态规划方法

对于任意给定的模式Pat[1‥m]和正文T[1‥n]，m<n，以及任意给定的正整数k，0≤k<m。动态规划方法的思想:构造一个规模为(m+1)×(n+1)的编辑距离矩阵D并通过计算D中元素的值来实现允许k-差别的近似串匹配问题的求解。编辑距离矩阵D的计算满足如下递推方程：

(1)

D[i,j]表示将模式前缀Pat[1‥i]转换成正文子串

T[l‥j]所需的编辑操作次数，1≤l≤j

。

D[m,j]表示将模式Pat[1‥m]转换成正文子串

T[l‥j]所需的编辑操作次数.

算法的时空复杂度分别为O(nm)。

第十七页，共六十四页，2022年，8月28日例：Pat=bataa，T=cabataabadaa和编辑距离阈值k=1时，通过计算编辑距离矩阵D的元素值来完成近似串匹配的过程。

第十八页，共六十四页，2022年，8月28日9.3CREW-PRAM模型上允许k-差别的近似串匹配并行算法

9.3.3波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法

0123

l-2l-1l

n-2n-1n

012m-1m

(m+1)个处理器并行计算第

l条“反对角线”上的编辑距离元素值

并行推进第十九页，共六十四页，2022年，8月28日Algorithm1ParallelApproximateStringMatchingAlgorithmonCREWPRAMBasedonParallelComputingEdit-DistanceMatrixinWave-FrontWay

输入：模式串Pat[1‥m]，正文T[1‥n]，编辑距离阈值k；

输出：编辑距离≤k的模式在正文中的近似匹配终止位置pos，1≤pos≤n(1)

fori=0tomdoinparallel

{PL[i]=0;PP[i]=0;L[i]=0}(2)

PL[0]=1;(3)

forl=2ton+mdo//s记当前正在计算的第l条“反对角线”上元素的数目

(3.1)ifl<=mthens=l-1elseifl<=nthens=melses=m-(l-n)+1;(3.2)ifl<=mthenL[0]=l;(3.3)fori=1tosdoinparallel//并行计算第l条“反对角线”上元素的值

(3.3.1)ifl<=mthen{ifPat[s-(i-1)]=T[i]thenc=0elsec=1;

L[i]=min{PL[i-1]+1,PL[i]+1,PP[i-1]+c}(3.3.2)elseifl=m+1then{ifPat[m-(i-1)]=T[i]thenc=0elsec=1;

L[i-1]=min{PL[i-1]+1,PL[i]+1,PP[i-1]+c}(3.3.3)else{ifPat[m-(i-1)]=T[l-m+i-1]thenc=0elsec=1;

L[i-1]=min{PL[i-1],PL[i]+1,PP[i]+c}(3.4)fori=0tomdoinparallel{PP[i]=PL[i];PL[i]=L[i]}(3.5)ifl>=mandL[0]<=kthen{pos=l-m;writeln(“matchedat:”,pos);}endfor

第二十页，共六十四页，2022年，8月28日9.3CREW-PRAM模型上允许k-差别的近似串匹配并行算法

波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法的复杂度

引理1编辑距离矩阵D的“反对角线”的数目为n+m+1。引理2编辑距离矩阵D中任一条“反对角线”上的元素数目最多为m+1。

因为对于CREWPRAM模型并发读可在常数时间内解决，所以由引理1和引理2有：

定理1对于(m+1)个处理器的CREWPRAM计算模型，采用波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法所需时间为O(n)，获得线性加速，执行代价O(nm)是最优的；空间复杂度为O(n+m)。

第二十一页，共六十四页，2022年，8月28日波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验（并行Multipascal编程实现）

(a)纵轴为执行时间，单位为微秒；横轴为正文规模，单位为字节；模式5个字符；处理器数6，k=1

测试目的：固定模式长度（处理器个数）、正文规模不断增大对运行时间的影响。

结论：无论是串行执行时间还是并行执行时间都随着正文规模n的增大而相应地增加。第二十二页，共六十四页，2022年，8月28日波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验

(b)坐标纵轴表示加速比；横轴为正文规模，单位为字节；模式5个字符；处理器数6，k=1

测试目的：固定模式长度（处理器个数）而正文规模不断增大对加速度的影响

结论：无论正文规模n如何，并行算法保持亚线性加速趋势且加速比相差不超过±0.11。

第二十三页，共六十四页，2022年，8月28日波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验

纵轴为执行时间，单位为微秒；横轴为模式长度（处理器数），正文规模固定为1MB，k=1

测试目的：固定正文规模，不断增大模式长度（处理器个数）对执行时间的影响结论：当增大模式长度（处理器数目）时，求解问题所需的时间也相应地减少。第二十四页，共六十四页，2022年，8月28日波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验

(d)纵轴为加速比，横轴为模式长度（处理器数），正文规模固定为1MB，k=1

测试目的：固定正文规模，不断增大模式长度（处理器个数）对加速度的影响结论：并行算法获得良好加速；并行算法更适合于输入规模（正文长度）充分大的问题的求解。第二十五页，共六十四页，2022年，8月28日波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验(e)纵轴表示执行时间，单位为微秒；横轴为k值，正文规模1MB，模式15个字符；处理器数16

测试目的：固定正文规模和模式长度（处理器数目），编辑距离阈值k变化对算法执行时间的影响.结论：无论是串行还是并行执行时间几乎与编辑距离值k无关.第二十六页，共六十四页，2022年，8月28日波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法实验

纵轴表示加速比，横轴为k值，正文规模1MB，模式15个字符；处理器数16

测试目的：固定正文规模和模式长度（处理器数目），编辑

距离阈值k变化对算法加速度的影响

结论：编辑距离值k值的大小对加速的影响非常有限。第二十七页，共六十四页，2022年，8月28日9.3CREW-PRAM模型上允许k-

差别的近似串匹配并行算法9.3.4基于水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法

思想：将正文分割成α个正文段，建立α个编辑距离子矩阵，水平和斜向双并行计算编辑距离。

目的：提高算法的并行度

编辑距离子矩阵D1编辑距离子矩阵D2……

编辑距离子矩阵Dα

|

水平方向并行计算α个编辑距离子矩阵

|波前式斜向并行波前式斜向并行波前式斜向并行第二十八页，共六十四页，2022年，8月28日Algorithm2Parallel

ApproximateStringMatchingwithk-DifferencesonCREWPRAMBasedonParallelComputingEdit-DistanceMatrixSimultaneouslyalongDiagonalandHorizontalDirections

输入：模式串Pat[1‥m]，正文T[1‥n]，编辑距离阈值k，处理器数α(m+1)

输出：编辑距离≤k的模式在正文中的近似匹配终止位置pos，1≤pos≤n

(1)forj=1toαdoinparallel(2)fori=0tomdoinparallel{PL[j,i]=0;PP[j,i]=0;L[j,i]=0}(3)PL[j,0]=1;(4)ifj<αthen{nl=n/α+m-1elsenl=n/α}

(5)forl[j]=2tonl+mdo(5.1)ifl[j]<=mthen//s[j]记当前正在计算Dj的第l[j]条“反对角线”上元素的数目

s[j]=l[j]-1elseifl[j]<=nlthens[j]=melses[j]=m-(l[j]-nl)+1;(5.2)ifl[j]<=mthenL[j,0]=l[j];(5.3)fori=1tos[j]doinparallel//并行计算Dj第l[j]条“反对角线”上元素的值

(5.3.1)ifl[j]<=mthen{ifPat[s[j]-(i-1)]=T[(j-1)*n/α+i]thenc=0elsec=1;

L[j,i]=min{PL[j,i-1]+1,PL[j,i]+1,PP[j,i-1]+c}}(5.3.2)elseifl[j]=m+1then

{ifPat[m-(i-1)]=T[(j-1)*n/α+i]thenc=0elsec=1;

L[j,i-1]=min{PL[j,i-1]+1,PL[j,i]+1,PP[j,i-1]+c}}(5.3.3)else{ifPat[m-(i-1)]=T[(j-1)*n/α+l[j]-m+i-1]thenc=0elsec=1;

L[j,i-1]=min{PL[j,i-1],PL[j,i]+1,PP[j,i]+c}}endfor(5.4)fori=0tomdoinparallelPP[j,i]=PL[j,i];PL[j,i]=L[j,i]endfor(5.5)ifl[j]>=mandL[j,0]<=kthen{pos=

(j-1)*n/α+l[j]-m;writeln(“Matchedat:”,pos);endforendfor

第二十九页，共六十四页，2022年，8月28日9.3CREW-PRAM模型上允许k-差别的近似串匹配并行算法

水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法的复杂度

并行系统共有α(m+1)≤n的处理器，并行地对α段规模为n/α的正文进行编辑距离计算和模式匹配比较的工作。

根据定理1，有：

定理2

对于α(m+1)个处理器的CREWPRAM模型，水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法的时间复杂度为O(n/α+m)，获得线性加速，所需的存储空间为O(n+m)，1≤α≤n/(m+1)。

第三十页，共六十四页，2022年，8月28日9.3CREW-PRAM模型上允许k-差别的近似串匹配并行算法

水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法实验丛轴为并行算法的执行时间，单位为微妙；横轴为处理器数目，正文长度固定为2MB，模式长11个字符，编辑距离阈值为1

测试目的：固定正文和模式规模，增加处理器规模对并行求解时间的影响。

结论：增加处理器可以显著地减少并行算法所需的执行时间。第三十一页，共六十四页，2022年，8月28日9.3CREW-PRAM模型上允许k-

差别的近似串匹配并行算法

水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法实验

(b)丛轴为并行算法的加速比，横轴为处理器数目，正文长度固定为2MB，模式长11个字符，编辑距离阈值为1

测试目的：固定正文和模式规模，增加处理器规模对并行算法加速的影响。结论：并行算法保持接近于线性的亚线性加速趋势。第三十二页，共六十四页，2022年，8月28日9.4LARPBS模型上允许k-误配的近似串匹配并行算法

钟诚，陈国良.软件学报,2004,15(2):159-169

汉明距离(Hammingdistances)与允许k-误配的近似串匹配

(Approximatestringmatchingwithk-mismatchcharacters)

定义4

对于任意的两个字符a,b∈∑，定义布尔函数fb()：

设串X=x1x2…xn，Y=y1y2…yn∈，定义X和Y的汉明距离ham(X,Y)：

ham(X,Y)=

定义5

设模式Pat=Pat[1‥m]，正文T=T[1‥n]，m<n，任意给定一个整数k，0≤k<m，所谓允许k-误配的近似串匹配问题是指在正文中寻找出所有满足条件ham(Pat,Ti)≤k的匹配起始位置i，其中正文子串Ti=T[i‥i+m-1]，1≤i≤n-m+1。

第三十三页，共六十四页，2022年，8月28日9.4LARPBS模型上允许k-误配的近似串匹配并行算法

LARPBS计算模型

LARPBS模型（LinearArrayswithReconfigurablePipelinedBusSystem）——可重构流水线总线系统线性阵列模型，它使用光总线连接处理器。

处理器光有向耦合器

特征：◆单向传输◆极强的通信能力◆

可以动态重构成l个独立的光总线子系统，2≤l≤n，这些光总线子系统可以独立进行不同的计算而相互不受干涉。

102N-1第三十四页，共六十四页，2022年，8月28日9.4LARPBS模型上允许k-误配的近似串匹配并行算法

LARPBS计算模型的基本数据移动操作及其复杂度

引理3光总线上每个处理器将1个数据项发送给另一个处理器的操作称为点对点通信，点对点通信可以在1个总线周期内完成。

引理4源处理器将其局部寄存器的数据值发送到光总线上所有n个处理器的操作称为广播，广播操作可以在1个总线周期内完成。

引理5源处理器将其局部寄存器的数据值发送到光总线上若干个处理器的操作称为一对多广播即多播。多播操作可以在1个总线周期完成。

引理6假设n个数据分布在光总线上的n个处理器中，每个处理器保存1个数据。并假设活跃的（active）数据元素为s个，1≤s≤n。所谓活跃元素依据其局部变量的值来标识。拥有活跃元素的处理器称为活跃处理器。将活跃元素移动到处理器PRn-s，…，PRn-1的操作称为压缩。压缩操作可以在O(1)总线周期内完成。

引理7对于具有n个处理器的LARPBS系统，每个处理器PRi保存1个二进制值vi，0≤i≤n-1。计算所有二进制值前缀和，0≤i≤n-1。计算二进制值前缀和的操作可以在O(1)总线周期内完成。

第三十五页，共六十四页，2022年，8月28日9.4.3

n个处理器的LARPBS系统上的允许k-误配的近似串匹配并行算法

设正文T[0‥n-1]存储在LARPBS系统的n个处理器中，处理器PRi存储正文字符T[i]，0≤i≤n-1。处理器PRi包含有用于存储汉明距离的数组元素S[i]和布尔数组元素TB[i]，0≤i≤n-1。初始时，将模式Pat[0‥m-1]存储在处理器PR0-PRm-1中，即PRj存储模式字符Pat[j]，0≤j≤m-1。

算法思想（1）数据对准：基于分组原理和重迭方法，将正文和模式串字符分布在总线系统上相应的处理器中。（2）并行匹配比较：并行比较模式串字符和正文子串字符。（3）并行计算正文子串和模式的汉明距离：灵活地采用拆分总线和合并子总线的方法动态重构光总线系统，并充分利用光总线常数时间的消息播送和并行计算前缀和技术，实现并行计算正文子串和模式之间的汉明距离。（4）并行输出：若这些汉明距离值（前缀和）≤错误阈值k，则输出匹配起始位置。

第三十六页，共六十四页，2022年，8月28日9.4LARPBS模型上允许k-误配的近似串匹配并行算法

n个处理器的LARPBS系统上允许k-误配的近似串匹配并行算法

输入：模式Pat[0‥m-1]，正文T[0‥n-1]和错误阈值k

输出：若ham(Pat,Ti)≤k则输出模式在正文中的近似匹配起始位置i，0≤i≤n-m

(1)l=0；处理器PR0将k广播到总线系统上各个处理器中。(2)长度为n的LARPBS总线系统并发地执行多播操作，其中处理器PRj将模式字符Pat[j]播送给处理器PR(i×m+j+l)modn，

i=1~(n/m-1)，j=0~m-1。(3)将长度为n的总线系统重构成n/m个长度为m的子总线系统LARPBS-i，i=1~n/m。(4)各子总线系统LARPBS-i上所有处理器并行比较其存储器中的正文字符T[(i-1)×m+j]和模式字符Pat[j]，若T[(i-1)×m+j]=Pat[j]，则置B[(i-1)×m+j]=0，否则置B[(i-1)×m+j]=1，j=0~m-1，i=1~n/m。(5)各子总线系统LARPBS-i并行计算其上m个二进制值B[(i-1)×m]

~B[(i-1)×m+m-1]的前缀和psumi，然后执行点-对-点通信操作将psumi发送到处理器PR(i-1)×m+l的S[(i-1)×m+l]中，i=1~n/m。(6)l=l+1，若l≤m-1，则重构长度为n的LARPBS总线系统，然后各处理器并行执行点对点通信操作，其中若(i+l)≤n-1则处理器PRi+l将其存储器中的T[i+l]发送至PRi的T[i]中，0≤i≤n-l-1，然后转步（3）；否则执行步（7）。(7)重构长度为n的LARPBS总线系统，处理器PRi比较S[i]和k的大小，若S[i]≤k，则输出匹配起始位置，0≤i≤n-1。定理3

n个处理器的LARPBS系统上允许k-误配的近似串匹配并行算法时间复杂度为O(m)。

第三十七页，共六十四页，2022年，8月28日9.4LARPBS模型上允许k-误配的近似串匹配并行算法

mn个处理器的LARPBS系统上允许k-误配的近似串匹配并行算法算法思想

①数据对准：动态拆分光总线系统，基于分组和重迭方法，将模式、正文以及正文起始下标值播送到总线系统相应的处理器中。

②并行比较：动态合并光总线子系统，LARPBS系统上所有处理器并行比较模式和正文子串字符，若它们相等则产生值0，否则产生值1。③并行计算模式串与正文子串的汉明距离：各个光总线子系统并行求二进制值的前缀和（模式与各个正文子串之间的汉明距离值）。

④并发播送汉明距离（前缀和）：若汉明距离值（前缀和）≤k，则输出相应的近似匹配起始位置。

第三十八页，共六十四页，2022年，8月28日

9.4LARPBS模型上允许k-误配的近似串匹配并行算法算法

m×n个处理器的LARPBS系统上允许k-误配的近似串匹配并行算法输入：模式Pat[0‥m-1]，正文T[0‥n-1]和错误阈值k。输出：若ham(Pat,Ti)≤k则输出模式在正文中的近似匹配起始位置i，0≤i≤n-m。begin(1)长度为n×m的总线系统LARPBS上各处理器PRi

执行操作S[i]←-1，0≤i≤n×m-1(2)长度为n×m的总线系统LARPBS执行广播操作将k播送给所有处理器(3)长度为n×m的总线系统LARPBS并发地执行多播操作，其中处理器PRi将正文字符T[i]播送给处理器PRj×n+i

的T[j×n+i]，0≤i≤n-1，0≤j≤m-1(4)长度为n×m的总线系统LARPBS并发地执行点对点通信操作，其中处理器PRj×(n+1)+i

将字符T[j×(n+1)+i]和正文起始位置(j+i)分别发送给处理器PRj×n+i的T[j×n+i]和S[j×n+i]，0≤i≤n-j-1，0≤j≤m-1(5)将长度为n×m的总线系统LARPBS重构为m个长度n的总线子系统LARPBS-j，0≤j≤m-1，m个总线子系统并发地执行多播操作，其中处理器PRj×n判断j

是否大于零，若等于零，那么PRj×n将特殊字符“#”发送给处理器PR(j+1)×n-j

~PR(j+1)×n-1对应的T[(j+1)×n-j]~T[(j+1)×n-1]；否则PRj×n执行空操作，0≤j≤m-1(6)重构一个长度为n×m的总线系统LARPBS，并发地执行多播操作，其中处理器PRj

将模式字符Pat[j]播送给处理器PRi×m+j的Pat[i×m+j]，0≤j≤m-1，0≤i≤n-1(7)将长度为n×m的总线系统重构成n个长度为m的总线子系统，分别记为LARPBS-i

，1≤i≤n。各总线子系统LARPBS-i上所有处理器并行比较其存储器中的正文字符T[(i-1)×m+j]和模式字符Pat[j]，若T[(i-1)×m+j]=Pat[j]则执行B[(i-1)×m+j]←0，否则执行B[(i-1)×m+j]←1，0≤j≤m-1，1≤i≤n(8)各总线子系统LARPBS-i并行计算其上m个二进制值B[(i-1)×m]~B[(i-1)×m+m-1]的前缀和psi，将psi保存在处理器PR(i-1)×m中，1≤i≤n(9)重构一个长度为n×m的总线系统，并发地执行点对点通信操作，其中处理器PRj×n+i×m将S[j×n+i×m]发送给处理器PRj+i×m的PO[j+i×m]，1≤j≤m-1，0≤i≤n/m-1(10)长度为n×m的总线系统并发执行点对点通信操作，其中处理器PR(i-1)×m将psi发送（压缩）给处理器PRi-1的p_si-1，1≤i≤n(11)激活长度为n×m的总线系统上n个处理器PRi-1，1≤i≤n；处理器PRi-1比较汉明距离p_si-1和k值，若p_si-1≤k则输出匹配起始位置PO[i-1]，1≤i≤nend第三十九页，共六十四页，2022年，8月28日9.4LARPBS模型上允许k-误配的近似串匹配并行算法

mn个处理器的LARPBS系统上允许k-误配的近似串匹配并行算法时间复杂度

算法中每一步的所有操作都可以在常数时间内完成，故有：

定理4n×m个处理器的LARPBS系统上允许k-误配的近似串匹配并行算法的时间复杂度为O(1)。第四十页，共六十四页，2022年，8月28日9.4LARPBS模型上允许k-误配的近似串匹配并行算法

mn个处理器的LARPBS系统上允许k-误配的近似串匹配并行算法例

正文T=abcdabceg，n=9，模式Pat=abh，m=3，错误阈值k=1

中间数组Ｓ用于保存正文位置，二进制数组Ｂ保存正文和模式字符比较结果，ps和p-s数组用于保存汉明距离值，ＰＯ数组保存可能的匹配起始位置；特殊字符“＃”不属于字典表。

PR01234567891011121314151617181920212223242526Tabcdabcegbcdabceg#cdabceg##PatabhabhabhabhabhabhabhabhabhS01234567812345678-12345678-1-1B001111111111001111111111111ps133313333p-s13331