并行算法的設(shè)計與分析

并行算法的設(shè)計與分析第一頁，共六十四頁，2022年，8月28日第9章串匹配并行算法精確串匹配并行算法多模式串匹配并行算法允許k-差別的近似串匹配并行算法允許k-誤配的近似串匹配并行算法異構(gòu)機群系統(tǒng)上近似串匹配并行算法第二頁，共六十四頁，2022年，8月28日串匹配技術(shù)的應(yīng)用

1、Internet信息搜索2、生物信息學(xué)

3、網(wǎng)絡(luò)入侵檢測4、網(wǎng)絡(luò)遠程教學(xué)

5、電子商務(wù)6、數(shù)據(jù)挖掘

7、模式識別8、文本編輯

9、數(shù)據(jù)壓縮10、圖象處理

11、信號檢測與處理12、其他

第三頁，共六十四頁，2022年，8月28日9.1分布式存儲系統(tǒng)的精確串匹配并行算法

陳國良，林潔，顧乃杰.軟件學(xué)報,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)精確串匹配算法的時間復(fù)雜度為O(m+n)。

KMP算法的關(guān)鍵是根據(jù)給定的模式串P[1~m]定義一個next函數(shù)，next函數(shù)包含了模式串本身局部匹配的信息.

KMP算法的基本思想：

假設(shè)模式匹配進程正在執(zhí)行T[i]和P[j]的匹配檢查，若T[i]=P[j],則繼續(xù)檢查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)]是否匹配。重復(fù)此過程，直到j(luò)=m或i=n結(jié)束。KMP算法結(jié)束時,模式串指針j-1的值就是正文串尾模式串最大前綴的長度。

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

9.1.2改進的KMP算法、計算next函數(shù)和newnext函數(shù)的算法

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

n]和模式串P[1‥

m]輸出:匹配結(jié)果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在模式串字符重復(fù)多的情況下,利用newnext[j]使得改進的KMP算法更有效.算法2.next函數(shù)和newnext函數(shù)的計算算法procedureNEXT輸入:模式串P[1‥

m];輸出:next[1‥

m+1]和newnext[1‥

m]Beginnext[1]=newnext[1]=0;j=2;//newnext[j]函數(shù)同時要求滿足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函數(shù)播送到各處理器中。

各處理器使用改進的KMP算法并行地對局部正文段進行匹配，以找到所有段內(nèi)匹配位置。（3）每個局部正文段（第p-1段除外）段尾m-1字符中的匹配位置必須跨段才能找到。為此，每個處理器(處理器p-1除外)將本局部段的段尾m-1個字符傳送給下一處理器,下一個處理器接收前一處理器傳來的m-1個字符之后,再結(jié)合本段的段首m-1個字符構(gòu)成一個長為2(m-1)的段間字符子串,對此字符子串作匹配,就能找到所有段間匹配位置。但是,當(dāng)m較大時這樣做通信量較大。解決辦法是每個處理器在其段尾m-1個字符中找到模式串P的最長前綴子串。因每個處理器都有模式串P的信息，故只需傳送此前綴子串的長度Max-prefix-len即可,這樣大大降低了通信量。（4）進一步降低播送模式串和newnext函數(shù)的通信復(fù)雜度：利用模式串的周期性質(zhì),對模式串P預(yù)處理，獲得其最小周期長度|U|、最小周期個數(shù)s及后綴長度|V|

，其中

P=UsV

，只需播送U,s和|V|以及部分newnext函數(shù)即可，從而大大減少播送模式串和

newnext函數(shù)的通信量。第六頁，共六十四頁，2022年，8月28日

字符串的周期性分析

字符串的最小周期和next函數(shù)之間的關(guān)系存在著如下定理所述的規(guī)律,據(jù)此可設(shè)計出常數(shù)時間復(fù)雜度的串周期分析算法。定義：給定字符串P,如果存在字符串U以及正整數(shù)k≥2,使得串Uk是串P的前綴,則稱字符串U為串P的周期.在字符串P的所有周期中長度最短的周期稱為串P的最小周期。

定理：字符串P的長度為m,記u=m+1-next(m+1),則u為串P的最小周期長度.

算法3

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

輸出:最小周期長度period-len,最小周期個數(shù)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串匹配的分布式并行算法及其復(fù)雜度分析

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

//PE0求模式串P的next函數(shù)和newnext函數(shù)

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

播送模式串最小周期長度,最小周期個數(shù),后綴長度

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

ifperiod-num=1thenBroadcastNewnext[1‥m]函數(shù)//播送模式串部分newnext函數(shù),若周期數(shù)為1,則播送整個newnext函數(shù)

else

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

callprocedureREBUILD;//由傳來的模式串周期和部分newnext函數(shù)并行重構(gòu)整個模式串和newnext函數(shù)

fori=0top-1doinparallelKMP(Ti,P,n,0,match);//各處理器調(diào)用過程KMP并行匹配局部段,并獲得局部段尾最大前綴串的長度(4)fori=0top-2doinparallel

PEisend

max-prefix-lentoPEi+1//PEi把max-prefix-len發(fā)送給處理器PEi+1fori=1top-1doinparallel

{PEi

receive

max-prefix-lenfromPEi-1//PEi接收PEi-1發(fā)送來的max-prefix-lenPEicallKMP(Ti

,P,m-1,max-prefix-len,match+m-1);}//調(diào)用KMP并行進行段間匹配算法的計算時間由步(1)中算法2的時間復(fù)雜度O(m)和算法3的時間復(fù)雜度O(1),步(3)和步(4)的改進的KMP算法的時間O(n/p)和O(m)構(gòu)成.所以,算法總的計算時間復(fù)雜度為O(n/p+m)。通信復(fù)雜度由步(2)播送模式串信息(最小周期串U及最小周期長度、周期個數(shù)和后綴長度3個整數(shù))和Newnxt函數(shù)(長度為2u的整數(shù)數(shù)組,u為串U的長度)以及步(4)傳送最大前綴串長度組成,采用二分樹通信技術(shù),所以總的通信復(fù)雜度為O(ulogp)。

第八頁，共六十四頁，2022年，8月28日9.1.4算法實驗性能

在大規(guī)模并行機曙光1000上測試了模式串長為128KB和周期串長為4KB,16KB,64KB的3組數(shù)據(jù),每組數(shù)據(jù)的處理器數(shù)分別為1,2,4,8,16和31,文本串長分別為28MB,56MB,112MB,224MB,448MB和868MB.利用曲線擬合分別擬合周期串長為4KB,16KB,64KB

的數(shù)據(jù),得到3個計算時間復(fù)雜度方程：

(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.

擬合結(jié)果和實驗測量數(shù)據(jù)吻合。這3個擬合公式與理論推導(dǎo)的計算時間O(n/p+m)一致(由于固定m,所以擬合公式中沒有出現(xiàn)m)。另外，上面3個擬合公式所對應(yīng)的系數(shù)相差非常小,這說明計算時間和模式周期長幾乎沒有關(guān)系。曲線擬合得到通信時間與模式周期和處理器數(shù)的關(guān)系式：

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

此擬合公式和理論推導(dǎo)的通信復(fù)雜度O(ulogp)吻合。分析和實驗結(jié)果表明算法的通信時間只和模式串的周期相關(guān),而與文本串、模式串長度無關(guān)。.因主要關(guān)注計算量、機器數(shù)目和效率之間的關(guān)系,故把模式串長和周期看成是常數(shù).從曲線擬合中得到計算時間和通信時間分別為：

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)

工作量（數(shù)據(jù)規(guī)模）n=(E/(1-0.63E))*(0.45uplnp-0.21p+2.41).

上述表明工作量n與p

lnp成比例,該算法是可擴放的，

但不是線性可擴放的。第九頁，共六十四頁，2022年，8月28日9.2可重構(gòu)光計算模型的多模式串并行匹配算法

鐘誠，中國科技大學(xué)博士學(xué)位論文，2003.5

多模式串匹配問題所謂多模式串匹配是指，對于一個給定的總長度為M的k個模式串所構(gòu)成的集合D={Pat1，Pat2，…，Patk}，Patj為第j個模式，1≤j≤k，M=

，在線輸入的一個長度為n的正文T，希望使用與M成線性關(guān)系的時間預(yù)處理集合D中的所有模式串，并盡可能在O(n+tocc)時間內(nèi)能夠檢查出那些模式在正文中匹配出現(xiàn)以及匹配出現(xiàn)的所有起始位置，其中tocc為集合D中所有模式串在正文中匹配出現(xiàn)的總次數(shù)。

多模式串匹配問題的特點：（1）集合D中的模式串事先知道，正文在線輸入。（2）每個模式串的長度｜Patj｜比n小得多，1≤j≤k，因k值通常較大，故M遠遠大于n。（3）預(yù)處理集合D中所有模式串所需的時間希望與M成線性關(guān)系，正文匹配檢查所需的時間應(yīng)與集合D中模式串的個數(shù)k和總長度M無關(guān)。

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

9.2.2可重構(gòu)光網(wǎng)孔模型ORM(OpticalReconfigurableMesh)

處理層處理器偏傳部件偏傳層

（1）ORM由偏轉(zhuǎn)層（Deflectionlayer）和處理層（Processinglayer）構(gòu)成。每個處理器擁有3個光轉(zhuǎn)發(fā)器和1個接收器。（2）偏轉(zhuǎn)層由n2個組織成n×n網(wǎng)格的偏轉(zhuǎn)部件（光可重構(gòu)鏡）構(gòu)成，每個偏轉(zhuǎn)部件用D(i,j)表示，1≤i,j≤n。

（3）處理層由n2個處理器組成。處理層上的n2個處理器通過總線互連成n×n可重構(gòu)網(wǎng)孔RMESH，并且利用偏轉(zhuǎn)層實現(xiàn)任意處理器之間單位時間的光通信。（4）每個處理器用PR(i,j)表示，1≤i,j≤n，它都有一個局部可控總線開關(guān)（處理器設(shè)置開關(guān)的連接方式為{E,W,S,N}），允許動態(tài)地將廣播總線劃分成若干子總線，提供規(guī)模較小的RMESH或者可重構(gòu)總線段。

第十一頁，共六十四頁，2022年，8月28日RMESH結(jié)構(gòu)

第十二頁，共六十四頁，2022年，8月28日9.2.2可重構(gòu)光網(wǎng)孔模型ORM(OpticalReconfigurableMesh)

定理對于可重構(gòu)光網(wǎng)孔模型ORM，任意n個處理器的并發(fā)讀和并發(fā)寫操作可以在O(1)時間內(nèi)完成。

9.2.33D-ORM模型的多模式串并行匹配算法算法思想數(shù)據(jù)對準:

動態(tài)構(gòu)造行總線、列總線、對角線總線處理器陣列將正文和模式字符播送到指定的位置（處理器）中，使得第l個2D-MESH上的各條行總線上的處理器存儲模式串Patl，同時第l個2D-MESH上的第i條行總線上的處理器存儲正文子串T[i‥i+m’-1]，1≤i≤n-m’+1，1≤l≤k。匹配比較:3D-ORM上所有處理器并行比較模式字符和正文字符。收集結(jié)果:如果第l個2D-MESH上的第i條行總線上所有處理器均比較成功，那么說明模式串Patl與正文子串T[i‥i+m’-1]產(chǎn)生匹配，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，動態(tài)地生成n條自左下方至右上方的對角線總線，這樣n×m’×k的3D-ORM共生成k×n條對角線總線處理器陣列；(2)foralliandl,1≤i≤n，1≤l≤kdoinparallel

第1列的

PR(i,1,l)將保存在其存儲器中的T[i]向其相應(yīng)的對角線總線播送；(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]是否相等，若相等則設(shè)置開關(guān)狀態(tài){EW,S,N}連通東西開關(guān)端口，而斷開南、北端口；否則設(shè)置開關(guān)狀態(tài){E,W,S,N}斷開東、西、南、北4個端口；(5)foralliandl,1≤i≤n-m’+1，1≤l≤kdoinparallel

最后一列的PR(i,m’,l)從東到西向其所在的行總線處理器陣列發(fā)送“#”；(6)foralliandl,1≤i≤n-m’+1，1≤l≤kdoinparallel

第1列的PR(i,1,l)如果接收到符號“#”則輸出匹配起始位置和模式串的下標l，即模式串Patl與起始位置為i的正文子串T[i‥i+

m’-1]產(chǎn)生匹配。第十四頁，共六十四頁，2022年，8月28日9.2.3ORM模型上多模式串并行匹配算法時間復(fù)雜度

對于ORM模型，因為并行播送數(shù)據(jù)、并行比較字符、并行播送特殊符號“#”等操作均可在常數(shù)時間內(nèi)完成，所以有：定理

對于給定的k個模式串Patl，1≤l≤k，以及正文串T[1‥n]，3D-ORM模型上多模式串并行匹配可以在常數(shù)時間內(nèi)完成。第十五頁，共六十四頁，2022年，8月28日9.3CREW-PRAM上允許k-差別的近似串匹配并行算法

鐘誠，陳國良.軟件學(xué)報,2004,15(2):159-169

編輯距離(Editdistances)與允許k-差別的近似串匹配(ApproximateStringmatchingwithk-differencecharacters)

定義1

任意給定兩個串X和Y，那么串X和Y之間的編輯距離D(X,Y)定義為使用如下三種編輯操作將串X轉(zhuǎn)換成串Y（或者將Y轉(zhuǎn)換成X）所需的最少的編輯操作次數(shù)：①

從串X（Y）中刪除一個符號（字符），②

向串X（Y）插入一個符號，③

用另一個符號替換串X（Y）中指定的某個符號。性質(zhì)1兩個串X和Y之間的編輯距離D(X,Y)具有如下性質(zhì)：①

非負性：D(X,Y)≥0，D(X,Y)=0當(dāng)且僅當(dāng)X=Y；②

對稱性：D(X,Y)=D(Y,X)；③三角不等式：設(shè)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，并給定一個在線輸入的正整數(shù)k，0≤k<m

，尋找出編輯距離小于等于k的模式Pat在正文T中所有匹配出現(xiàn)的終止位置j，1≤j≤n。第十六頁，共六十四頁，2022年，8月28日9.3CREW-PRAM上允許k-差別的近似串匹配并行算法

9.3.2允許k-差別的近似串匹配的動態(tài)規(guī)劃方法

對于任意給定的模式Pat[1‥m]和正文T[1‥n]，m<n，以及任意給定的正整數(shù)k，0≤k<m。動態(tài)規(guī)劃方法的思想:構(gòu)造一個規(guī)模為(m+1)×(n+1)的編輯距離矩陣D并通過計算D中元素的值來實現(xiàn)允許k-差別的近似串匹配問題的求解。編輯距離矩陣D的計算滿足如下遞推方程：

(1)

D[i,j]表示將模式前綴Pat[1‥i]轉(zhuǎn)換成正文子串

T[l‥j]所需的編輯操作次數(shù)，1≤l≤j

。

D[m,j]表示將模式Pat[1‥m]轉(zhuǎn)換成正文子串

T[l‥j]所需的編輯操作次數(shù).

算法的時空復(fù)雜度分別為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記當(dāng)前正在計算的第l條“反對角線”上元素的數(shù)目

(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-差別的近似串匹配并行算法的復(fù)雜度

引理1編輯距離矩陣D的“反對角線”的數(shù)目為n+m+1。引理2編輯距離矩陣D中任一條“反對角線”上的元素數(shù)目最多為m+1。

因為對于CREWPRAM模型并發(fā)讀可在常數(shù)時間內(nèi)解決，所以由引理1和引理2有：

定理1對于(m+1)個處理器的CREWPRAM計算模型，采用波前式并行計算編輯距離矩陣D的允許k-差別的近似串匹配并行算法所需時間為O(n)，獲得線性加速，執(zhí)行代價O(nm)是最優(yōu)的；空間復(fù)雜度為O(n+m)。

第二十一頁，共六十四頁，2022年，8月28日波前式并行計算編輯距離矩陣D的允許k-差別的近似串匹配并行算法實驗（并行Multipascal編程實現(xiàn)）

(a)縱軸為執(zhí)行時間，單位為微秒；橫軸為正文規(guī)模，單位為字節(jié)；模式5個字符；處理器數(shù)6，k=1

測試目的：固定模式長度（處理器個數(shù)）、正文規(guī)模不斷增大對運行時間的影響。

結(jié)論：無論是串行執(zhí)行時間還是并行執(zhí)行時間都隨著正文規(guī)模n的增大而相應(yīng)地增加。第二十二頁，共六十四頁，2022年，8月28日波前式并行計算編輯距離矩陣D的允許k-差別的近似串匹配并行算法實驗

(b)坐標縱軸表示加速比；橫軸為正文規(guī)模，單位為字節(jié)；模式5個字符；處理器數(shù)6，k=1

測試目的：固定模式長度（處理器個數(shù)）而正文規(guī)模不斷增大對加速度的影響

結(jié)論：無論正文規(guī)模n如何，并行算法保持亞線性加速趨勢且加速比相差不超過±0.11。

第二十三頁，共六十四頁，2022年，8月28日波前式并行計算編輯距離矩陣D的允許k-差別的近似串匹配并行算法實驗

縱軸為執(zhí)行時間，單位為微秒；橫軸為模式長度（處理器數(shù)），正文規(guī)模固定為1MB，k=1

測試目的：固定正文規(guī)模，不斷增大模式長度（處理器個數(shù)）對執(zhí)行時間的影響結(jié)論：當(dāng)增大模式長度（處理器數(shù)目）時，求解問題所需的時間也相應(yīng)地減少。第二十四頁，共六十四頁，2022年，8月28日波前式并行計算編輯距離矩陣D的允許k-差別的近似串匹配并行算法實驗

(d)縱軸為加速比，橫軸為模式長度（處理器數(shù)），正文規(guī)模固定為1MB，k=1

測試目的：固定正文規(guī)模，不斷增大模式長度（處理器個數(shù)）對加速度的影響結(jié)論：并行算法獲得良好加速；并行算法更適合于輸入規(guī)模（正文長度）充分大的問題的求解。第二十五頁，共六十四頁，2022年，8月28日波前式并行計算編輯距離矩陣D的允許k-差別的近似串匹配并行算法實驗(e)縱軸表示執(zhí)行時間，單位為微秒；橫軸為k值，正文規(guī)模1MB，模式15個字符；處理器數(shù)16

測試目的：固定正文規(guī)模和模式長度（處理器數(shù)目），編輯距離閾值k變化對算法執(zhí)行時間的影響.結(jié)論：無論是串行還是并行執(zhí)行時間幾乎與編輯距離值k無關(guān).第二十六頁，共六十四頁，2022年，8月28日波前式并行計算編輯距離矩陣D的允許k-差別的近似串匹配并行算法實驗

縱軸表示加速比，橫軸為k值，正文規(guī)模1MB，模式15個字符；處理器數(shù)16

測試目的：固定正文規(guī)模和模式長度（處理器數(shù)目），編輯

距離閾值k變化對算法加速度的影響

結(jié)論：編輯距離值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，處理器數(shù)α(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]記當(dāng)前正在計算Dj的第l[j]條“反對角線”上元素的數(shù)目

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-差別的近似串匹配并行算法的復(fù)雜度

并行系統(tǒng)共有α(m+1)≤n的處理器，并行地對α段規(guī)模為n/α的正文進行編輯距離計算和模式匹配比較的工作。

根據(jù)定理1，有：

定理2

對于α(m+1)個處理器的CREWPRAM模型，水平和斜向雙并行計算編輯距離的允許k-差別的近似串匹配并行算法的時間復(fù)雜度為O(n/α+m)，獲得線性加速，所需的存儲空間為O(n+m)，1≤α≤n/(m+1)。

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

水平和斜向雙并行計算編輯距離的允許k-差別的近似串匹配并行算法實驗叢軸為并行算法的執(zhí)行時間，單位為微妙；橫軸為處理器數(shù)目，正文長度固定為2MB，模式長11個字符，編輯距離閾值為1

測試目的：固定正文和模式規(guī)模，增加處理器規(guī)模對并行求解時間的影響。

結(jié)論：增加處理器可以顯著地減少并行算法所需的執(zhí)行時間。第三十一頁，共六十四頁，2022年，8月28日9.3CREW-PRAM模型上允許k-

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

水平和斜向雙并行計算編輯距離的允許k-差別的近似串匹配并行算法實驗

(b)叢軸為并行算法的加速比，橫軸為處理器數(shù)目，正文長度固定為2MB，模式長11個字符，編輯距離閾值為1

測試目的：固定正文和模式規(guī)模，增加處理器規(guī)模對并行算法加速的影響。結(jié)論：并行算法保持接近于線性的亞線性加速趨勢。第三十二頁，共六十四頁，2022年，8月28日9.4LARPBS模型上允許k-誤配的近似串匹配并行算法

鐘誠，陳國良.軟件學(xué)報,2004,15(2):159-169

漢明距離(Hammingdistances)與允許k-誤配的近似串匹配

(Approximatestringmatchingwithk-mismatchcharacters)

定義4

對于任意的兩個字符a,b∈∑，定義布爾函數(shù)fb()：

設(shè)串X=x1x2…xn，Y=y1y2…yn∈，定義X和Y的漢明距離ham(X,Y)：

ham(X,Y)=

定義5

設(shè)模式Pat=Pat[1‥m]，正文T=T[1‥n]，m<n，任意給定一個整數(shù)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）——可重構(gòu)流水線總線系統(tǒng)線性陣列模型，它使用光總線連接處理器。

處理器光有向耦合器

特征：◆單向傳輸◆極強的通信能力◆

可以動態(tài)重構(gòu)成l個獨立的光總線子系統(tǒng)，2≤l≤n，這些光總線子系統(tǒng)可以獨立進行不同的計算而相互不受干涉。

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

LARPBS計算模型的基本數(shù)據(jù)移動操作及其復(fù)雜度

引理3光總線上每個處理器將1個數(shù)據(jù)項發(fā)送給另一個處理器的操作稱為點對點通信，點對點通信可以在1個總線周期內(nèi)完成。

引理4源處理器將其局部寄存器的數(shù)據(jù)值發(fā)送到光總線上所有n個處理器的操作稱為廣播，廣播操作可以在1個總線周期內(nèi)完成。

引理5源處理器將其局部寄存器的數(shù)據(jù)值發(fā)送到光總線上若干個處理器的操作稱為一對多廣播即多播。多播操作可以在1個總線周期完成。

引理6假設(shè)n個數(shù)據(jù)分布在光總線上的n個處理器中，每個處理器保存1個數(shù)據(jù)。并假設(shè)活躍的（active）數(shù)據(jù)元素為s個，1≤s≤n。所謂活躍元素依據(jù)其局部變量的值來標識。擁有活躍元素的處理器稱為活躍處理器。將活躍元素移動到處理器PRn-s，…，PRn-1的操作稱為壓縮。壓縮操作可以在O(1)總線周期內(nèi)完成。

引理7對于具有n個處理器的LARPBS系統(tǒng)，每個處理器PRi保存1個二進制值vi，0≤i≤n-1。計算所有二進制值前綴和，0≤i≤n-1。計算二進制值前綴和的操作可以在O(1)總線周期內(nèi)完成。

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

n個處理器的LARPBS系統(tǒng)上的允許k-誤配的近似串匹配并行算法

設(shè)正文T[0‥n-1]存儲在LARPBS系統(tǒng)的n個處理器中，處理器PRi存儲正文字符T[i]，0≤i≤n-1。處理器PRi包含有用于存儲漢明距離的數(shù)組元素S[i]和布爾數(shù)組元素TB[i]，0≤i≤n-1。初始時，將模式Pat[0‥m-1]存儲在處理器PR0-PRm-1中，即PRj存儲模式字符Pat[j]，0≤j≤m-1。

算法思想（1）數(shù)據(jù)對準：基于分組原理和重迭方法，將正文和模式串字符分布在總線系統(tǒng)上相應(yīng)的處理器中。（2）并行匹配比較：并行比較模式串字符和正文子串字符。（3）并行計算正文子串和模式的漢明距離：靈活地采用拆分總線和合并子總線的方法動態(tài)重構(gòu)光總線系統(tǒng)，并充分利用光總線常數(shù)時間的消息播送和并行計算前綴和技術(shù)，實現(xiàn)并行計算正文子串和模式之間的漢明距離。（4）并行輸出：若這些漢明距離值（前綴和）≤錯誤閾值k，則輸出匹配起始位置。

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

n個處理器的LARPBS系統(tǒng)上允許k-誤配的近似串匹配并行算法

輸入：模式Pat[0‥m-1]，正文T[0‥n-1]和錯誤閾值k

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

(1)l=0；處理器PR0將k廣播到總線系統(tǒng)上各個處理器中。(2)長度為n的LARPBS總線系統(tǒng)并發(fā)地執(zhí)行多播操作，其中處理器PRj將模式字符Pat[j]播送給處理器PR(i×m+j+l)modn，

i=1~(n/m-1)，j=0~m-1。(3)將長度為n的總線系統(tǒng)重構(gòu)成n/m個長度為m的子總線系統(tǒng)LARPBS-i，i=1~n/m。(4)各子總線系統(tǒng)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)各子總線系統(tǒng)LARPBS-i并行計算其上m個二進制值B[(i-1)×m]

~B[(i-1)×m+m-1]的前綴和psumi，然后執(zhí)行點-對-點通信操作將psumi發(fā)送到處理器PR(i-1)×m+l的S[(i-1)×m+l]中，i=1~n/m。(6)l=l+1，若l≤m-1，則重構(gòu)長度為n的LARPBS總線系統(tǒng)，然后各處理器并行執(zhí)行點對點通信操作，其中若(i+l)≤n-1則處理器PRi+l將其存儲器中的T[i+l]發(fā)送至PRi的T[i]中，0≤i≤n-l-1，然后轉(zhuǎn)步（3）；否則執(zhí)行步（7）。(7)重構(gòu)長度為n的LARPBS總線系統(tǒng)，處理器PRi比較S[i]和k的大小，若S[i]≤k，則輸出匹配起始位置，0≤i≤n-1。定理3

n個處理器的LARPBS系統(tǒng)上允許k-誤配的近似串匹配并行算法時間復(fù)雜度為O(m)。

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

mn個處理器的LARPBS系統(tǒng)上允許k-誤配的近似串匹配并行算法算法思想

①數(shù)據(jù)對準：動態(tài)拆分光總線系統(tǒng)，基于分組和重迭方法，將模式、正文以及正文起始下標值播送到總線系統(tǒng)相應(yīng)的處理器中。

②并行比較：動態(tài)合并光總線子系統(tǒng)，LARPBS系統(tǒng)上所有處理器并行比較模式和正文子串字符，若它們相等則產(chǎn)生值0，否則產(chǎn)生值1。③并行計算模式串與正文子串的漢明距離：各個光總線子系統(tǒng)并行求二進制值的前綴和（模式與各個正文子串之間的漢明距離值）。

④并發(fā)播送漢明距離（前綴和）：若漢明距離值（前綴和）≤k，則輸出相應(yīng)的近似匹配起始位置。

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

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

m×n個處理器的LARPBS系統(tǒng)上允許k-誤配的近似串匹配并行算法輸入：模式Pat[0‥m-1]，正文T[0‥n-1]和錯誤閾值k。輸出：若ham(Pat,Ti)≤k則輸出模式在正文中的近似匹配起始位置i，0≤i≤n-m。begin(1)長度為n×m的總線系統(tǒng)LARPBS上各處理器PRi

執(zhí)行操作S[i]←-1，0≤i≤n×m-1(2)長度為n×m的總線系統(tǒng)LARPBS執(zhí)行廣播操作將k播送給所有處理器(3)長度為n×m的總線系統(tǒng)LARPBS并發(fā)地執(zhí)行多播操作，其中處理器PRi將正文字符T[i]播送給處理器PRj×n+i

的T[j×n+i]，0≤i≤n-1，0≤j≤m-1(4)長度為n×m的總線系統(tǒng)LARPBS并發(fā)地執(zhí)行點對點通信操作，其中處理器PRj×(n+1)+i

將字符T[j×(n+1)+i]和正文起始位置(j+i)分別發(fā)送給處理器PRj×n+i的T[j×n+i]和S[j×n+i]，0≤i≤n-j-1，0≤j≤m-1(5)將長度為n×m的總線系統(tǒng)LARPBS重構(gòu)為m個長度n的總線子系統(tǒng)LARPBS-j，0≤j≤m-1，m個總線子系統(tǒng)并發(fā)地執(zhí)行多播操作，其中處理器PRj×n判斷j

是否大于零，若等于零，那么PRj×n將特殊字符“#”發(fā)送給處理器PR(j+1)×n-j

~PR(j+1)×n-1對應(yīng)的T[(j+1)×n-j]~T[(j+1)×n-1]；否則PRj×n執(zhí)行空操作，0≤j≤m-1(6)重構(gòu)一個長度為n×m的總線系統(tǒng)LARPBS，并發(fā)地執(zhí)行多播操作，其中處理器PRj

將模式字符Pat[j]播送給處理器PRi×m+j的Pat[i×m+j]，0≤j≤m-1，0≤i≤n-1(7)將長度為n×m的總線系統(tǒng)重構(gòu)成n個長度為m的總線子系統(tǒng)，分別記為LARPBS-i

，1≤i≤n。各總線子系統(tǒng)LARPBS-i上所有處理器并行比較其存儲器中的正文字符T[(i-1)×m+j]和模式字符Pat[j]，若T[(i-1)×m+j]=Pat[j]則執(zhí)行B[(i-1)×m+j]←0，否則執(zhí)行B[(i-1)×m+j]←1，0≤j≤m-1，1≤i≤n(8)各總線子系統(tǒng)LARPBS-i并行計算其上m個二進制值B[(i-1)×m]~B[(i-1)×m+m-1]的前綴和psi，將psi保存在處理器PR(i-1)×m中，1≤i≤n(9)重構(gòu)一個長度為n×m的總線系統(tǒng)，并發(fā)地執(zhí)行點對點通信操作，其中處理器PRj×n+i×m將S[j×n+i×m]發(fā)送給處理器PRj+i×m的PO[j+i×m]，1≤j≤m-1，0≤i≤n/m-1(10)長度為n×m的總線系統(tǒng)并發(fā)執(zhí)行點對點通信操作，其中處理器PR(i-1)×m將psi發(fā)送（壓縮）給處理器PRi-1的p_si-1，1≤i≤n(11)激活長度為n×m的總線系統(tǒng)上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系統(tǒng)上允許k-誤配的近似串匹配并行算法時間復(fù)雜度

算法中每一步的所有操作都可以在常數(shù)時間內(nèi)完成，故有：

定理4n×m個處理器的LARPBS系統(tǒng)上允許k-誤配的近似串匹配并行算法的時間復(fù)雜度為O(1)。第四十頁，共六十四頁，2022年，8月28日9.4LARPBS模型上允許k-誤配的近似串匹配并行算法

mn個處理器的LARPBS系統(tǒng)上允許k-誤配的近似串匹配并行算法例

正文T=abcdabceg，n=9，模式Pat=abh，m=3，錯誤閾值k=1

中間數(shù)組Ｓ用于保存正文位置，二進制數(shù)組Ｂ保存正文和模式字符比較結(jié)果，ps和p-s數(shù)組用于保存漢明距離值，ＰＯ數(shù)組保存可能的匹配起始位置；特殊字符“?！辈粚儆谧值浔?。

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