并行算法的设计与(9)

1、 第9章 串匹配并行算法 精确串匹配并行算法 多模式串匹配并行算法 允许k-差别的近似串匹配并行算法 允许k-误配的近似串匹配并行算法 异构机群系统上近似串匹配并行算法串匹配技术的应用串匹配技术的应用 1、Internet信息搜索 2、生物信息学 3、网络入侵检测 4、网络远程教学 5、电子商务 6、数据挖掘 7、模式识别 8、文本编辑 9、数据压缩 10、图象处理 11、信号检测与处理 12、其他 9.1 9.1 分布式存储系统的精确串匹配并行算法分布式存储系统的精确串匹配并行算法陈国良，林洁，顾乃杰.软件学报软件学报, ,2000, 11 (6) : 771- -7789.1.1 顺序的K

2、MP串匹配算法定义：精确串匹配问题是指, 给定一个长度为n 的正文串T 1n 和一个长度 为m 的模式串P1m, 字符Ti (1in) 和P j (1jm ) ( 为字符集) ，查找出P在T 中所有成功匹配的起始位置。 顺序的KM P (Knuth Morris Pratt)精确串匹配算法的时间复杂度为O (m+n)。 KM P 算法的关键是根据给定的模式串算法的关键是根据给定的模式串P1m 定义一个定义一个next 函数函数，next函数包含函数包含了模式串本身局部匹配的信息了模式串本身局部匹配的信息. KMP 算法的基本思想： 假设模式匹配进程正在执行T i和P j的匹配检查， 若Ti=

3、Pj, 则继续检查T i+1和Pj+1是否匹配。 若TiPj， 则分成两种情况： 若j=1, 则模式串“右移右移” 一位, 检查Ti+1和P1是否匹配; 若1jm , 则模式串“右移右移” j-next(j) 位, 检查T i和Pnext(j)是否匹配。 重复此过程，直到j=m 或i=n 结束。KMP算法结束时算法结束时, 模式串指针模式串指针j -1 的值就是正文串尾模式串最大前缀的长度的值就是正文串尾模式串最大前缀的长度。 9.1.2 改进的KMP 算法、计算next 函数和newnext 函数的算法算法1. 改进的KMP 串匹配算法 procedure KMP输入: 正文串T 1 n和模

4、式串P1 m 输出: 匹配结果match 1 nBegin i= 1；j= 1； while i= n do while ( j ! = 0 and P j! = T i ) do j=newnext j； if j=m then match i- (m-1)=1; j= nextm+1 ; i+; else j+; i+ +; max-prefix-len= j1; End在模式串字符重复多的情况下在模式串字符重复多的情况下, 利用利用newnext j使得改进的使得改进的KM P 算法更有效算法更有效.算法2. next函数和newnext 函数的计算算法 procedure NEXT输入

5、: 模式串P 1 m ; 输出: next 1 m+1和newnext 1 mBegin next1= newnext1= 0; j=2; / newnext j函数同时要求满足Pnextj!=Pj while j= m+1 do i= next j-1; while ( i! = 0 and P i! = P j-1) do i=nexti; next j= i+1; if j ! = m+1 then If P j! = Pi+1 then newnext j= i+1 else newnext j= newneti+1 j+; End9.1.3 分布式并行串匹配算法的思想（1） 将长为n

6、 的正文串T 均匀划分成互不重叠的p 段 分布存储于处理器0p-1中， 且使相邻的正文段分存储布在相邻处理器中，每个处理器中局部正文段的长度为n/p ( 最后一个处理器可在其段尾补上其他特殊字符， 使其长度为n/p )。（2） 将长为将长为m 的模式串的模式串P 和模式串的和模式串的newnext 函数播送到各处理器中。函数播送到各处理器中。 各处理器使用各处理器使用改进的改进的KM P 算法并行地对局部正文段进行匹配算法并行地对局部正文段进行匹配，以，以找到所有段内匹配位置找到所有段内匹配位置。（3） 每个局部正文段（第p-1段除外） 段尾m-1 字符中的匹配位置必须跨段才能找到。为此，每个

7、处理器(处理器p-1 除外) 将本局部段的段尾m-1 个字符传送给下一处理器, 下一个处理器接收前一处理器传来的m-1 个字符之后, 再结合本段的段首m-1 个字符构成一个长为2 (m-1) 的段间字符子串, 对此字符子串作匹配, 就能找到所有段间匹配位置。 但是, 当m较大时这样做通信量较大。 解决办法是每个处理器在其段尾解决办法是每个处理器在其段尾m-1个字符中找到模式串个字符中找到模式串P 的最长前缀子串的最长前缀子串。 因因每个处理器都有模式串每个处理器都有模式串P P 的信息的信息，故只需传送此前缀子串的长度故只需传送此前缀子串的长度Max-prefix-len 即即可可, 这样大大

8、降低了通信量这样大大降低了通信量。（4） 进一步降低播送模式串和newnext 函数的通信复杂度：利用模式串的周期性质, 对模式串P 预处理，获得其最小周期长度|U|、最小周期个数s 及后缀长度|V| ，其中 P = U s V ，只需播送U , s 和|V|以及部分newnext 函数即可，从而大大减少播送模式串和 newnext函数的通信量。字符串的周期性分析 字符串的最小周期和next 函数之间的关系存在着如下定理所述的规律, 据此可设计出常数时间复杂度的串周期分析算法。 定义定义： 给定字符串P , 如果存在字符串U 以及正整数k2, 使得串U k是串P的前缀, 则称字符串U 为串P

9、的周期. 在字符串P的所有周期中长度最短的周期称为串P 的最小周期。 定理： 字符串P的长度为m , 记u=m+1- next(m+1) , 则u 为串P的最小周期长度. 算法算法3 字符串周期性分析算法 输入: nextm+1 输出: 最小周期长度period-len, 最小周期个数period-num , 模式串后缀长度pattern-suffixlen Procrdure PERIOD-ANALYSIS begin period-len= m+1- next (m+1) ; period-num = (int)m/period-len; pattern-suffixlen= m mod

10、period-len; end9.1.3 KMP串匹配的分布式并行算法及其复杂度分析 输入:文本子串T i 1 n/p 分布存储于处理器PEi的( i= 0 p - 1)和模式串P 1m 存储于PE 0 ；输出: 匹配结果(1) PE0 call procedure NEX T / PE0求模式串P 的next 函数和newnext 函数 PE0 call procedure PERIOD-ANALYSIS / PE0对模式串P进行周期分析(2) PE0 broadcast period-len, period-num , period-suffix-len / 播送模式串最小周期长度, 最小

11、周期个数, 后缀长度 PE0 broadcast P 1 period-len / 播送模式串的最小周期 if period-num=1 then Broadcast Newnext 1 m 函数 / 播送模式串部分newnext函数, 若周期数为1, 则播送整个newnext 函数 else Broadcast newnext1 2* period-len / 否则, 播送两倍周期长度的newnext(3) for i=1 to p-1 do in parallel call procedure REBUILD; / 由传来的模式串周期和部分newnext函数并行重构整个模式串和newnex

12、t 函数 for i=0 to p-1 do in parallel KMP(Ti, P , n, 0, match); / 各处理器调用过程KMP并行匹配局部段, 并获得局部段尾最大前缀串的长度(4) for i= 0 to p-2 do in parallel PE i send max-prefix-len to PE i+1 / PE i 把max-prefix-len 发送给处理器PE i+1 for i=1 to p-1 do in parallel PE i receive max-prefix-len from PE i-1 / PE i接收PE i-1发送来的max-pref

13、ix-len PE i call KMP (T i , P , m-1, max-prefix-len, match+ m -1); / 调用KMP 并行进行段间匹配算法的计算时间由步算法的计算时间由步(1) 中算法中算法2 的时间复杂度的时间复杂度O (m ) 和算法和算法3 的时间复杂度的时间复杂度O (1) , 步步(3) 和步和步(4) 的改进的的改进的KM P 算法的时间算法的时间O (n/p ) 和和O (m ) 构成构成. 所以所以, 算法总的计算时间复杂度为算法总的计算时间复杂度为O (n/p + m )。 通信复杂度由步(2) 播送模式串信息(最小周期串U 及最小周期长度、周

14、期个数和后缀长度3 个整数) 和Newnxt 函数(长度为2u 的整数数组, u 为串U 的长度) 以及步(4) 传送最大前缀串长度组成, 采用二分树通信技术, 所以总的通信复杂度为O (u logp )。 9.1.4 算法实验性能 在大规模并行机曙光1000 上测试了模式串长为128KB 和周期串长为4KB, 16KB, 64KB 的3 组数据, 每组数据的处理器数分别为1, 2, 4, 8, 16 和31, 文本串长分别为28M B, 56MB , 112MB , 224MB , 448MB 和868MB.利用曲线拟合分别拟合周期串长为利用曲线拟合分别拟合周期串长为4KB, 16KB, 6

15、4KB 的数据的数据, 得到得到3 个计算时间复杂度方程个计算时间复杂度方程： (1) 周期长为4KB： t(n, p)=0.631076n/p+2.41241/p+12.440410- 6 n-0.2106. (2) 周期长为16KB：t(n, p)=0.63114n/p+2.41422/p+8.3227710- 6 n-0.214093. (3) 周期长为64KB：t(n, p)=0.631078n/p+2.42302/p+6.1421610- 6 n-0.228162. 拟合结果和实验测量数据吻合。这3 个拟合公式与理论推导的计算时间O (n/p + m ) 一致(由于固定m , 所以拟

16、合公式中没有出现m )。另外，上面3 个拟合公式所对应的系数相差非常小, 这说明计算时间和模式周期长几乎没有关系。曲线拟合得到通信时间与模式周期和处理器数的关系式曲线拟合得到通信时间与模式周期和处理器数的关系式： comm (u, p ) = 0.00452519u lnp+0.00479584lnp-0.000242529u-0.00156526 此拟合公式和理论推导的通信复杂度O (ulogp) 吻合。分析和实验结果表明算法的通信时间只和模式串的周期相关, 而与文本串、模式串长度无关。.因主要关注计算量、机器数目和效率之间的关系因主要关注计算量、机器数目和效率之间的关系, 故把模式串长和周

17、期看成是常数故把模式串长和周期看成是常数. 从曲线拟合中得到计从曲线拟合中得到计算时间和通信时间分别为算时间和通信时间分别为： 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. 45up lnp - 0.21p+2.41). 上述表明工作量上述表明工作量n与与p lnp

18、 成比例成比例, 该算法是可扩放的，该算法是可扩放的， 但不是线性可扩放的但不是线性可扩放的。9.2 可重构光计算模型的多模式串并行匹配算法钟诚，中国科技大学博士学位论文，2003.59.2.1 多模式串匹配问题 所谓多模式串匹配是指，对于一个给定的总长度为M 的k个模式串所构成的集合D=Pat1，Pat2，Patk，Patj为第j个模式，1 j k，M = ，在线输入的一个长度为n的正文T，希望使用与M成线性关系的时间预处理集合D中的所有模式串，并尽可能在O(n+tocc)时间内能够检查出那些模式在正文中匹配出现以及匹配出现的所有起始位置，其中tocc为集合D中所有模式串在正文中匹配出现的总

19、次数。 多模式串匹配问题的特点： （1）集合D中的模式串事先知道，正文在线输入。 （2）每个模式串的长度Patj比n小得多，1 j k，因k值通常较大，故 M 远远大于n。 （3）预处理集合D中所有模式串所需的时间希望与M 成线性关系，正 文匹配检查所需的时间应与集合D中模式串的个数k和总长度M无关。 kjjPat1| 9.2.2 可重构光网孔模型可重构光网孔模型ORM (Optical Reconfigurable Mesh) 处理层 处理器 偏传部件 偏传层 （1）ORM由偏转层（由偏转层（Deflection layer）和处理层（）和处理层（Processing layer）构成。）构

20、成。每个处理器拥每个处理器拥有有3个光转发器和个光转发器和1个接收器个接收器 。 （2）偏转层由n2个组织成nn网格的偏转部件（光可重构镜） 构成，每个偏转部件用D(i, j) 表示，1i, jn。 （3） 处理层由处理层由n2个处理器组成。处理层上的个处理器组成。处理层上的n2个处理器通过总线互连成个处理器通过总线互连成nn可重构网孔可重构网孔RMESH，并且利用偏转层实现任意处理器之间单位时间的光通信，并且利用偏转层实现任意处理器之间单位时间的光通信。 （4）每个处理器用PR(i, j)表示，1i, jn，它都有一个局部可控总线开关（处理器设置开关的连接方式为E,W,S,N ），允许动态地

21、将广播总线划分成若干子总 线，提供规模较小的RMESH或者可重构总线段。 RMESH结构9.2.2 可重构光网孔模型可重构光网孔模型ORM (Optical Reconfigurable Mesh)定理定理 对于可重构光网孔模型ORM，任意n个处理器的并发读和 并发写操作可以在O(1)时间内完成。 9.2.3 3D-ORM模型的多模式串并行匹配算法 算法思想 数据对准数据对准: 动态构造行总线、列总线、对角线总线处理器阵列将正文和模式字符播送到指定的位置（处理器）中，使得第l个2D-MESH上的各条行总线上的处理器存储模式串Patl，同时第l个2D-MESH上的第i条行总线上的处理器存储正文子

22、串Tii+m-1，1in- m+1，1lk。 匹配比较匹配比较: 3D-ORM上所有处理器并行比较模式字符和正文字符。 收集结果收集结果:如果第l个2D-MESH上的第i条行总线上所有处理器均比较成功，那么说明模式串Patl与正文子串Tii+m-1产生匹配，1in- m+1，1lk。9.2.3 3D-ORM模型的多模式串并行匹配算法模型的多模式串并行匹配算法 / PR(i, j , l)中的行坐标i 表示垂直方向、列坐标j 表示水平方向， 坐标 l 表示纵深方向， m=max| Patl |: 1= l =k，初始时正文保存在各2D-ORM的第1列处理器上，第l 个模式存在第l 个2D-ORM

23、的第1行处理器对于ORM的每个2D-RMESH，动态地生成 n 条自左下方至右上方的对角线 总线， 这样nmk的3D-ORM共生成 kn 条对角线总线处理器阵列；(2) for all i and l , 1in，1lk do in parallel 第1列的 PR(i,1, l)将保存在其存储器中的Ti 向其相应的对角线总线播送；(3) for all j and l , 1jm, 1lk do in parallel 第1行 的PR(1, j, l)将其存储器中的Patl j向第 j 列总线处理器阵列播送；(4) for all i , j and l , 1in- m+1，1jm, 1l

24、k do in parallel PR(i, j, l)比较Ti+j-1和Patl j是否相等，若相等则设置开关状态 EW,S,N连 通东西开关端口，而断开南、北端口；否则设置开关状态E,W,S,N断开东、 西、南、北4个端口；(5) for all i and l , 1in- m+1，1lk do in parallel 最后一列的PR(i, m,l )从东到西向其所在的行总线处理器阵列发送 “#”；(6) for all i and l , 1in- m+1，1lk do in parallel 第1列的PR(i,1, l )如果接收到符号“#”则输出匹配起始位置和模式串的下标 l ，

25、即模式串Patl 与起始位置为i 的正文子串Tii+ m-1产生匹配。9.2.3 ORM模型上多模式串并行匹配算法时间复杂度模型上多模式串并行匹配算法时间复杂度 对于ORM模型， 因为并行播送数据、并行比较字符、并行播送特殊符号“#”等操作均可在常数时间内完成，所以有： 定理定理 对于给定的k个模式串Patl，1lk，以及正文串T1n，3D-ORM模型上多模式串并行匹配可以在常数时间内完成。9.3 CREW-PRAM上允许上允许k- 差别的近似串匹配并行算法差别的近似串匹配并行算法钟诚，陈国良.软件学报,2004, 15(2):159-169 9.3.1 编辑距离(Edit distances

26、)与允许k-差别的近似串匹配(Approximate String matching with k-difference characters) 定义定义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,

27、X)； 三角不等式：设Z为另一个串，则D(X, Y)D(X, Z)+D( Z, Y)。定义定义2 对于任意给定的一个长度为n的串X1n，称Xij为串X的子串，特别地，子串 X1i称为串X的前缀，而子串Xjn则称为串X的后缀，其中1i，jn。 定义定义3 所谓允许k-差别的近似串匹配是指：对于任意给定的一个长度为m的称为模式的串 Pat1m和一个长度为n的称为正文的串T1n，mn，并给定一个在线输入的正 整数k，0km ，寻找出编辑距离小于等于k 的模式Pat在正文T中所有匹配出现的终 止位置j，1jn。 9.3 CREW-PRAM上允许上允许k- 差别的近似串匹配并行算法差别的近似串匹配并行算

28、法 9.3.2 允许允许k- 差别的近似串匹配的动态规划方法差别的近似串匹配的动态规划方法 对于任意给定的模式Pat1m和正文T1n，mn，以及任意给定的正整数k，0km。动态规划方法的思想: 构造一个规模为(m+1)(n+1)的编辑距离矩阵D并通过计算D中元素的值来实现允许k-差别的近似串匹配问题的求解。编辑距离矩阵D的计算满足如下递推方程： (1) Di, j表示将模式前缀Pat1i转换成正文子串 Tlj 所需的编辑操作次数， 1lj 。 Dm, j表示将模式表示将模式Pat1m转换成正文子串转换成正文子串 Tlj 所需的编辑操作次数所需的编辑操作次数. 算法的时空复杂度分别为O(nm)。

29、 否则若其中, 1, 0, 1, 1, 1, 1, 1 1,min0,0, 0,jTipatccjiDjiDjiDjiijiD例：Pat=bataa，T=cabataabadaa和编辑距离阈值k=1时，通过计算编辑距离矩阵D的元素值来完成近似串匹配的过程。 c a b a t a a b a d a a 0 1 2 3 4 5 6 7 8 9 10 11 12 0 b 1 a 2 t 3 a 4 a 5 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 0 1 1 2 2 1 1 0 1 1 1 1 0 1 0 1 3 3 2 2 1 0 1 2 2

30、1 1 1 1 4 4 3 3 2 1 0 1 2 2 2 1 1 5 5 4 4 3 2 1 0 1 2 3 2 1 9.3 CREW-PRAM模型上允许模型上允许k- 差别差别的近似串匹配并行算法的近似串匹配并行算法 9.3.3 波前式并行计算编辑距离矩阵波前式并行计算编辑距离矩阵D的允许的允许k-差别的近似串匹配并行算法差别的近似串匹配并行算法 0 1 2 3 l-2 l-1 l n-2 n-1 n 012m-1m (m+1)个处理器并行计算第个处理器并行计算第 l 条条“反对角线反对角线”上的编辑距离元素值上的编辑距离元素值 并并行行推推进进Algorithm 1 Parallel A

31、pproximate String Matching Algorithm on CREW PRAM Based on Parallel Computing Edit-Distance Matrix in Wave-Front Way输入：模式串Pat1m，正文T1n，编辑距离阈值k；输出：编辑距离k的模式在正文中的近似匹配终止位置pos ，1posn(1) for i=0 to m do in parallel PLi=0; PPi=0; Li=0 (2) PL0=1; (3) for l=2 to n+m do / s记当前正在计算的第l条“反对角线”上元素的数目 (3.1) if l=m

32、then s=l-1 else if l=n then s=m else s=m-(l-n)+1 ; (3.2) if l=m then L0=l; (3.3) for i=1 to s do in parallel / 并行计算第l条“反对角线”上元素的值 (3.3.1) if l=m and L0=k then pos= l-m; writeln(“matched at:”, pos); endfor 9.3 CREW-PRAM模型上允许模型上允许k- 差别差别的近似串匹配并行算法的近似串匹配并行算法 波前式并行计算编辑距离矩阵波前式并行计算编辑距离矩阵D的允许的允许k-差别的近似串匹配差

33、别的近似串匹配并行算法的复杂度并行算法的复杂度 引理引理1 编辑距离矩阵D的“反对角线”的数目为n+m+1。 引理引理2 编辑距离矩阵D中任一条“反对角线”上的元素数目 最多为m+1。 因为对于CREW PRAM模型并发读可在常数时间内解决，所以由引理1和引理2有： 定理定理1 对于(m+1)个处理器 的CREW PRAM计算模型，采用波前式并行计算编辑距离矩阵D的允许k-差别的近似串匹配并行算法所需时间为O(n)，获得线性加速，执行代价O(nm)是最优的；空间复杂度为O(n+m)。 波前式并行计算编辑距离矩阵波前式并行计算编辑距离矩阵D的允许的允许k-差别的近似串匹配并差别的近似串匹配并行算

34、法实验（并行行算法实验（并行Multipascal编程实现）编程实现） (a) 纵轴为执行时间，单位为微秒；横轴为正文规模，单位为字节； 模式5个字符；处理器数6，k=1 测试目的：固定模式长度（处理器个数）、正文规模不 断增大对运行时间的影响。 结 论：无论是串行执行时间还是并行执行时间都随着 正文规模n 的增大而相应地增加。02000000004000000006000000008000000001000000000120000000014000000001600000000100K500K800K1M5M8M10M15M20M串行执行时间并行执行时间波前式并行计算编辑距离矩阵D的允许k-

35、差别的近似串匹配并行算法实验 (b) 坐标纵轴表示加速比；横轴为正文规模，单位为字节； 模式5个字符；处理器数6 ，k=1 测试目的：固定模式长度（处理器个数）而正文规模不断增大对加速度的影响 结论：无论正文规模n如何，并行算法保持亚线性加速趋势且加速比相差不超过0.11。 4.604.654.704.754.80100K500K800K1M5M8M10M15M20M加速比波前式并行计算编辑距离矩阵波前式并行计算编辑距离矩阵D的允许的允许k-差别的近似串匹差别的近似串匹配并行算法实验配并行算法实验 纵轴为执行时间，单位为微秒；横轴为模式长度（处理器数），正文规模固定为1MB，k=1 测试目的：

36、固定正文规模，不断增大模式长度（处理器个数） 对执行时间 的影响结论：当增大模式长度（处理器数目）时，求解问题所需的时间也相应地 减少。0 01000000010000000200000002000000030000000300000004000000040000000500000005000000060000000600000007000000070000000800000008000000090000000900000003(4)3(4)5(6)5(6)7(8)7(8)11(12)11(12)17(18)17(18)23(24)23(24)31(32)31(32)37(38)37(38)串

37、行执行时间串行执行时间并行执行时间并行执行时间波前式并行计算编辑距离矩阵波前式并行计算编辑距离矩阵D的允许的允许k-差别的近似串匹差别的近似串匹配并行算法实验配并行算法实验 (d) 纵轴为加速比，横轴为模式长度（处理器数），正文规模固定为1MB，k=1 测试目的：固定正文规模，不断增大模式长度（处理器个数） 对加速度 的影响 结论：并行算法获得良好加速；并行算法更适合于输入规模（正文长度） 充分大的问题的求解。051015203(4)5(6)7(8)11(12)17(18)23(24)31(32)37(38)加速比波前式并行计算编辑距离矩阵波前式并行计算编辑距离矩阵D的允许的允许k-差别的近似

38、串匹差别的近似串匹配并行算法实验配并行算法实验 (e) 纵轴表示执行时间，单位为微秒；横轴为k值，正文规模1MB， 模式15个字符；处理器数16 测试目的：固定正文规模和模式长度（处理器数目），编辑 距离阈值 k 变化对算法执行时间的影响.结论：无论是串行还是并行执行时间几乎与编辑距离值k无关. 0 01000000010000000200000002000000030000000300000004000000040000000500000005000000060000000600000007000000070000000800000008000000090000000900000000 02

39、 24 46 68 8101012121414串行执行时间串行执行时间并行执行时间并行执行时间波前式并行计算编辑距离矩阵波前式并行计算编辑距离矩阵D的允许的允许k-差别的近似串匹差别的近似串匹配并行算法实验配并行算法实验 纵轴表示加速比，横轴为k值，正文规模1MB，模式15个字符；处理器数16 测试目的：固定正文规模和模式长度（处理器数目），编辑 距离阈值 k 变化对算法加速度的影响 结论：编辑距离值 k 值的大小对加速的影响非常有限。11.2411.2411.2611.2611.2811.2811.311.311.3211.3211.3411.3411.3611.3611.3811.3811

40、.411.40 01 12 23 34 45 56 67 78 89 91010 1111 1212 1313 1414加速加速9.3 CREW-PRAM模型上允许模型上允许k- 差别差别的近似串匹配并行算法的近似串匹配并行算法9.3.4 基于水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法 思想：将正文分割成个正文段，建立个编辑距离子矩阵， 水平和斜向双并行计算编辑距离。 目的：提高算法的并行度 编辑距离子矩阵D1 编辑距离子矩阵D2 编辑距离子矩阵D | 水平方向并行计算水平方向并行计算个编辑距离子矩阵个编辑距离子矩阵 |波波 前前 式式 斜斜 向向 并并 行行波波 前前 式

41、式 斜斜 向向 并并 行行波波 前前 式式 斜斜 向向 并并 行行Algorithm 2 Parallel Approximate String Matching with k-Differences on CREW PRAM Based on Parallel Computing Edit-Distance Matrix Simultaneously along Diagonal and Horizontal Directions 输入：模式串Pat1m，正文T1n，编辑距离阈值k，处理器数(m+1) 输出：编辑距离k的模式在正文中的近似匹配终止位置pos ，1posn (1) for j=

42、1 to do in parallel(2) for i=0 to m do in parallel PLj,i=0; PPj,i=0; Lj,i=0 (3) PLj,0=1; (4) if j then nl=n/+m-1 else nl=n/ (5) for lj=2 to nl+m do(5.1) if lj=m then / sj记当前正在计算Dj的第lj条“反对角线”上元素的数目 sj= lj-1 else if lj=nl then sj=m else sj=m-( lj-nl)+1;(5.2) if lj=m then Lj,0= lj; (5.3) for i=1 to sj

43、do in parallel / 并行计算Dj第lj条“反对角线”上元素的值 (5.3.1) if lj=m and Lj,0=k then pos= (j-1)* n/+lj-m; writeln(“Matched at:”, pos); endfor endfor 9.3 CREW-PRAM模型上允许模型上允许k- 差别差别的近似串匹配并行算法的近似串匹配并行算法 水平和斜向双并行计算编辑距离的允许水平和斜向双并行计算编辑距离的允许k-差别的近似串匹差别的近似串匹配并行算法的复杂度配并行算法的复杂度 并行系统共有(m+1) n的处理器，并行地对段规模为n/的正文进行编辑距离计算和模式匹配比

44、较的工作。 根据定理1，有： 定理定理2 对于(m+1)个处理器的CREW PRAM模型，水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法的时间复杂度为O(n/+m)，获得线性加速，所需的存储空间为O(n+m) ，1 n/(m+1)。 9.3 CREW-PRAM模型上允许模型上允许k- 差别差别的近似串匹配并行算法的近似串匹配并行算法 水平和斜向双并行计算编辑距离的允许水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法实验差别的近似串匹配并行算法实验丛轴为并行算法的执行时间，单位为微妙；横轴为处理器数目，正文长度固定为2MB，模式长11个字符，编辑距离阈值为1 测试目

45、的：固定正文和模式规模，增加处理器规模对并行求解时间的影响。 结论：增加处理器可以显著地减少并行算法所需的执行时间。 0 0200000020000004000000400000060000006000000800000080000001000000010000000120000001200000014000000140000001600000016000000180000001800000012122424363648486060727284849696并行执行时间并行执行时间9.3 CREW-PRAM模型上允许模型上允许k- 差别差别的近似串匹配并行算法的近似串匹配并行算法 水平和斜向双并

46、行计算编辑距离的允许水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法实验差别的近似串匹配并行算法实验 (b) 丛轴为并行算法的加速比，横轴为处理器数目，正文长度固定为2MB， 模式长11个字符，编辑距离阈值为1 测试目的：固定正文和模式规模，增加处理器规模对并行算法加速的影响。 结论：并行算法保持接近于线性的亚线性加速趋势。0 01010202030304040505060607070808012122424363648486060727284849696加速比加速比9.4 LARPBS模型上允许模型上允许k- 误配误配的近似串匹配并行算法的近似串匹配并行算法钟诚，陈国良.软件学

47、报,2004, 15(2):159-169 9.4.1 汉明距离(Hamming distances)与允许k-误配的近似串匹配 (Approximate string matching with k-mismatch characters) 定义定义4 对于任意的两个字符a,b，定义布尔函数fb()： 设串X=x1x2xn ，Y=y1y2yn ，定义X和Y的汉明距离ham(X, Y)： ham(X, Y)= 定义定义5 设模式Pat=Pat 1m，正文T=T 1n，mn，任意给定一个整数k，0km，所谓允许k-误配的近似串匹配问题是指在正文中寻找出所有满足条件ham(Pat, Ti)k的匹配

48、起始位置i，其中正文子串Ti= T ii+m-1，1in-m+1。 ，否则，若01),(babafb ),(1iniiyxfb n 9.4 LARPBS模型上允许模型上允许k- 误配误配的近似串匹配并行算法的近似串匹配并行算法 9.4.2 LARPBS计算模型计算模型 LARPBS 模型（Linear Arrays with Reconfigurable Pipelined Bus System ）可重构流水线总线系统线性阵列模型，它使用光总线连接处理器 。 处理器 光有向耦合器 特征：特征： 单向传输 极强的通信能力 可以动态重构成 l 个独立的光总线子系统，2ln，这些光总线子系统可以独立

49、进行不同的计算而相互不受干涉。 102N-19.4 LARPBS模型上允许模型上允许k- 误配误配的近似串匹配并行算法的近似串匹配并行算法 LARPBS计算模型的基本数据移动操作及其复杂度计算模型的基本数据移动操作及其复杂度 引理引理3 光总线上每个处理器将1个数据项发送给另一个处理器的操作称为点对点通信，点对点通信可以在点对点通信可以在 1个总线周期内完成个总线周期内完成。 引理引理4 源处理器将其局部寄存器的数据值发送到光总线上所有n个处理器的操作称为广播，广播操作可以在广播操作可以在 1个总线周期内完成个总线周期内完成。 引理引理5 源处理器将其局部寄存器的数据值发送到光总线上若干个处理

50、器的操作称为一对多广播即多播。多播操作可以在多播操作可以在1个总线周期完成。个总线周期完成。 引理引理6 假设n个数据分布在光总线上的n个处理器中，每个处理器保存1个数据。并假设活跃的（active）数据元素为s个，1sn。所谓活跃元素依据其局部变量的值来标识。拥有活跃元素的处理器称为活跃处理器。将活跃元素移动到处理器PRn-s，PRn-1的操作称为压缩。压缩操作可以在压缩操作可以在O(1)总线周期内完成总线周期内完成。 引理引理7 对于具有n个处理器的LARPBS系统，每个处理器PRi保存1个二进制值vi，0in-1。计算所有二进制值前缀和，0in-1。计算二进制值前缀和的操作可计算二进制值

51、前缀和的操作可以在以在O(1)总线周期内完成。总线周期内完成。 9.4.3 n个处理器的LARPBS系统上的允许k-误配的近似串匹配并行算法 设正文T0n-1存储在LARPBS系统的n个处理器中，处理器PRi存储正文字符Ti，0in-1。处理器PRi包含有用于存储汉明距离的数组元素Si和布尔数组元素TBi，0in-1。初始时，将模式Pat0m-1存储在处理器PR0-PRm-1中，即PRj存储模式字符Patj，0jm-1。 算法思想 （1）数据对准：数据对准：基于分组原理和重迭方法，将正文和模式串字符分布在总线系统上相应的处理器中。 （2）并行匹配比较并行匹配比较：并行比较模式串字符和正文子串字

52、符。 （3）并行计算正文子串和模式的汉明距离：并行计算正文子串和模式的汉明距离：灵活地采用拆分总线和合并子总线的方法动态重构光总线系统，并充分利用光总线常数时间的消息播送和并行计算前缀和技术，实现并行计算正文子串和模式之间的汉明距离。 （4）并行输出并行输出：若这些汉明距离值（前缀和）错误阈值k，则输出匹配起始位置。 9.4 LARPBS模型上允许模型上允许k- 误配误配的近似串匹配并行算法的近似串匹配并行算法 9.4.3 n个处理器的个处理器的LARPBS系统上允许系统上允许k-误配的近似串匹配并行算法误配的近似串匹配并行算法 输入：模式Pat0m-1，正文T0n-1和错误阈值k 输出：若h

53、am(Pat, Ti)k则输出模式在正文中的近似匹配起始位置i，0in-m (1) l=0；处理器；处理器PR0将将 k 广播到总线系统上各个处理器中。广播到总线系统上各个处理器中。(2) 长度为长度为n的的LARPBS总线系统并发地执行多播操作，其中处理器总线系统并发地执行多播操作，其中处理器PRj将模式字符将模式字符Patj播送给播送给处理器处理器PR(im+j+l) mod n， i=1(n/m-1)，j=0m-1。(3) 将长度为将长度为n的总线系统重构成的总线系统重构成n/m个长度为个长度为m的子总线系统的子总线系统LARPBS-i，i=1n/m。(4) 各子总线系统各子总线系统LA

54、RPBS-i上所有处理器并行比较其存储器中的正文字符上所有处理器并行比较其存储器中的正文字符T(i-1)m+j和模式和模式字符字符Patj，若，若T(i-1)m+j= Patj，则置，则置B(i-1)m+j=0，否则置，否则置B(i-1)m+j=1，j=0m-1，i=1n/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=1n/m。(6)

55、l=l+1，若，若lm-1，则重构长度为，则重构长度为n的的LARPBS总线系统，然后各处理器并行执行点对点通信总线系统，然后各处理器并行执行点对点通信操作，其中若操作，其中若(i+l)n-1则处理器则处理器PRi+l将其存储器中的将其存储器中的Ti+l发送至发送至PRi的的Ti中，中，0in-l-1，然后转步（然后转步（3）；否则执行步（）；否则执行步（7）。）。(7) 重构长度为重构长度为n的的LARPBS总线系统，处理器总线系统，处理器PRi比较比较Si和和k的大小，若的大小，若Sik，则输出匹配，则输出匹配起始位置，起始位置，0in-1。定理定理3 n个处理器的个处理器的LARPBS系

56、统上允许系统上允许k-误配的近似串匹配并行算法时间复杂度为误配的近似串匹配并行算法时间复杂度为O(m)。 9.4 LARPBS模型上允许模型上允许k- 误配的误配的近似串匹配并行算法近似串匹配并行算法 9.4.4 mn个处理器的个处理器的LARPBS系统上允许系统上允许k-误配的近似串匹配并行算法误配的近似串匹配并行算法 算法思想算法思想 数据对准数据对准：动态拆分光总线系统，基于分组和重迭方法，将模式、正文以及正文起始下标值播送到总线系统相应的处理器中。 并行比较并行比较：动态合并光总线子系统， LARPBS系统上所有处理器并行比较模式和正文子串字符，若它们相等则产生值0，否则产生值1。 并

57、行计算模式串与正文子串的汉明距离：并行计算模式串与正文子串的汉明距离：各个光总线子系统并行求二进制值的前缀和（模式与各个正文子串之间的汉明距离值）。 并发播送汉明距离（前缀和）：并发播送汉明距离（前缀和）：若汉明距离值（前缀和）k ，则输出相应的近似匹配起始位置。 9.4 LARPBS模型上允许模型上允许k- 误配误配的近似串匹配并行算法的近似串匹配并行算法算法算法 9.4.4 mn个处理器的个处理器的LARPBS系统上允许系统上允许k-误配的近似串匹配并行算法误配的近似串匹配并行算法输入：模式Pat0m-1，正文T0n-1和错误阈值k。输出：若ham(Pat, Ti )k则输出模式在正文中的

58、近似匹配起始位置i，0in-m。begin(1) 长度为长度为nm的总线系统的总线系统LARPBS上各处理器上各处理器PRi 执行操作执行操作Si-1，0inm-1(2) 长度为长度为nm的总线系统的总线系统LARPBS执行广播操作将执行广播操作将k播送给所有处理器播送给所有处理器(3) 长度为长度为nm的总线系统的总线系统LARPBS并发地执行多播操作，其中处理器并发地执行多播操作，其中处理器PRi 将正文字符将正文字符Ti播送给处理器播送给处理器PRjn+i 的的Tjn+i，0in-1，0jm-1(4) 长度为长度为nm的总线系统的总线系统LARPBS并发地执行点对点通信操作，其中处理器并

59、发地执行点对点通信操作，其中处理器PRj(n+1)+i 将字符将字符Tj(n+1)+i和和正文起始位置正文起始位置(j+i)分别发送给处理器分别发送给处理器PRjn+i的的Tjn+i和和Sjn+i，0in-j-1，0jm-1(5) 将长度为将长度为nm的总线系统的总线系统LARPBS重构为重构为m个长度个长度n的总线子系统的总线子系统LARPBS-j，0jm-1，m个总线子系统并个总线子系统并发地执行多播操作，其中处理器发地执行多播操作，其中处理器PRjn判断判断 j 是否大于零，若等于零，那么是否大于零，若等于零，那么PRjn将特殊字符将特殊字符“#”发送给处发送给处理器理器PR(j+1)n

60、-j PR(j+1)n-1对应的对应的T(j+1)n-jT(j+1)n-1；否则；否则PRjn执行空操作，执行空操作，0jm-1(6) 重构一个长度为重构一个长度为nm的总线系统的总线系统LARPBS，并发地执行多播操作，其中处理器，并发地执行多播操作，其中处理器PRj 将模式字符将模式字符Patj播送给播送给处理器处理器PRim+j的的Patim +j，0jm-1，0in-1(7) 将长度为将长度为nm的总线系统重构成的总线系统重构成n个长度为个长度为m的总线子系统，分别记为的总线子系统，分别记为LARPBS-i ，1in。各总线子系统。各总线子系统LARPBS-i上所有处理器并行比较其存储