1、第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略 6.1 6.1 串行算法的直接并行化串行算法的直接并行化 6.2 6.2 從問題描述開始設(shè)計并行算法從問題描述開始設(shè)計并行算法 6.36.3 借用已有算法求解新問題借用已有算法求解新問題 第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略6.16.1串行算法的直接并行化串行算法的直接并行化直接并行化的直接并行化的關(guān)鍵關(guān)鍵：分析分析數(shù)據(jù)執(zhí)行數(shù)據(jù)執(zhí)行的的相關(guān)性相關(guān)性檢測檢測算法算法結(jié)構(gòu)的結(jié)構(gòu)的固有串行性固有串行性T1T2T3任務(wù)圖任務(wù)圖任務(wù)任務(wù)T1T1和和T2T2可以并行可以并行T3T3則需要等待則需要等待T1, T2T1, T2執(zhí)行結(jié)束執(zhí)行結(jié)束后，才能

2、運(yùn)行后，才能運(yùn)行第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略32022-4-23 6 6.1.1.1.1設(shè)計方法的描述設(shè)計方法的描述 設(shè)計策略描述設(shè)計策略描述 發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法改造為并行算法。改造為并行算法。 注意注意 由串行算法直接并行化的方法是并行算法設(shè)計的最常用由串行算法直接并行化的方法是并行算法設(shè)計的最常用方法之一；方法之一； 不是所有的串行算法都可以直接并行化的；不是所有的串行算法都可以直接并行化的； 一個好的串行算法并不能并行化為一個好的并行算法一個好的串行算法并不能并行化為一個好的并行算法； 許多數(shù)

3、值串行算法可以并行化為有效的數(shù)值并行算法。許多數(shù)值串行算法可以并行化為有效的數(shù)值并行算法。第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略42022-4-235.1.2 快排序算法的并行化 算法算法5.2 PRAM-CRCW上的快排序二叉樹構(gòu)造算法上的快排序二叉樹構(gòu)造算法 輸入：序列輸入：序列(A1,An)和和n個處理器個處理器 輸出：供排序用的一棵二叉排序樹輸出：供排序用的一棵二叉排序樹 Begin (1)for each processor i do (2)repeat for each processor iroot do (1.1)root=i if (AiAfi)(Ai=Afiifi)

4、 then (1.2)fi=root (2.1)LCfi=i (1.3)LCi=RCi=n+1 (2.2)if i=LCfi then exit else fi=LCfi endif end for else (2.3)RCfi=i (2.4)if i=RCfi then exit else fi=RCfi endif endif end repeat End第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略52022-4-23P1 A1 4P2 A2 1P3 A3 3P4 A4 2P5 A5 5f1 LC1 RC11 6 6f2 LC2 RC21 6 6f3 LC3 RC31 6 6f4 LC4

5、 RC4 1 6 6f5 LC5 RC51 6 6A2Af2=A1LCf2= LC1 =2i=2=LCf2= 2exitA3Af3=A1LCf3= LC1 =3i=3LCf2= 2 f3 =LCf3 = LC1 =2A4Af5=A1RCf2=RC1 =5i=5=RCf5= 5exitf1 LC1 RC11 2 5f2 LC2 RC21 6 6f3 LC3 RC32 6 6f4 LC4 RC4 2 6 6f5 LC5 RC51 6 6A3Af3=A2RCf3=RC2 =3i=3=RCf3=3exitA4Af4=A2RCf4=RC2 =4i=4 RCf3=3f4 =RCf4 = RC2 =3f1

6、LC1 RC11 2 5f2 LC2 RC21 6 3f3 LC3 RC32 6 6f4 LC4 RC4 3 6 6f5 LC5 RC51 6 6A4Af4=A3LCf4= LC3 =4i=4=LCf4= 4 exitf1 LC1 RC11 2 5f2 LC2 RC21 6 3f3 LC3 RC32 4 6f4 LC4 RC4 3 6 6f5 LC5 RC51 6 6算法實例：算法實例：A=4A=4，1 1，3 3，2 2，55，設(shè)編號小的處理器寫優(yōu)先，設(shè)編號小的處理器寫優(yōu)先A14A21A55A33A42構(gòu)造的邏輯構(gòu)造的邏輯二叉樹二叉樹第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略62022-

7、4-236.2 從問題描述開始設(shè)計并行算法 方法描述方法描述 從問題本身描述出發(fā)，不考慮相應(yīng)的串行算法，設(shè)從問題本身描述出發(fā)，不考慮相應(yīng)的串行算法，設(shè)計一個全新的并行算法。計一個全新的并行算法。 注意注意 挖掘問題的固有特性與并行的關(guān)系；挖掘問題的固有特性與并行的關(guān)系； 設(shè)計全新的并行算法是一個挑戰(zhàn)性和創(chuàng)造性的工作；設(shè)計全新的并行算法是一個挑戰(zhàn)性和創(chuàng)造性的工作； 利用串的周期性的利用串的周期性的PRAM-CRCW算法是一個很好的算法是一個很好的范例；范例；第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略6 6.2.1 .2.1 字符串匹配算法字符串匹配算法 給定一個長度為給定一個長度為n n的字

8、符串的字符串( (通常稱為通常稱為正文正文) )Text=Text=t t1 1t t2 2t tn n和一個和一個長度為長度為m m ( (m mn n) )的另一個字符串的另一個字符串( (通常稱為通常稱為模式模式) )Pattern=Pattern=p p1 1p p2 2p pm m， 要求查找出模式要求查找出模式P P在正文在正文T T中的中的首次出現(xiàn)首次出現(xiàn)或或所有出現(xiàn)所有出現(xiàn)的的起始位置起始位置（下（下標(biāo)）。標(biāo)）。 模式匹配的定義模式匹配的定義Pattern=arePattern=are示例示例1 3Text=how are you!Text=how are you!112n=1

9、2m=3首次出現(xiàn)的起始位置首次出現(xiàn)的起始位置= =5 5第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略82022-4-236 6.2.1 .2.1 字符串匹配算法字符串匹配算法 問題1.字符串匹配有哪些具體應(yīng)用？（舉例：一般計算機(jī)應(yīng)用中）2.字符串匹配在信息安全領(lǐng)域有哪些具體應(yīng)用？（舉例）第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略92022-4-23串行算法實例：串行算法實例： 簡單的字符串匹配算法簡單的字符串匹配算法轉(zhuǎn)化成以模式作為關(guān)鍵字的查找問題。它將長度轉(zhuǎn)化成以模式作為關(guān)鍵字的查找問題。它將長度n n為的正文為的正文T T劃分成劃分成n n- -m m+1+1個長度個長度為為m m的

10、子的子 串串, ,檢查比較每個這樣的子串是否與長度為檢查比較每個這樣的子串是否與長度為m m的模式相匹配。的模式相匹配。 1 1、算法思想、算法思想，Pattern=arePattern=areText=how are you!Text=how are you!n=12， m=3示例示例Text=how are you!Text=how are you!howhow ，ow ow ，w aw a ，arar ，areare ，re re ，e ye y ，yoyo ，ou!ou!第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略102022-4-23 算法算法 Simple-String-Matc

11、hing Begin i=1; while (i=n-m+1) do begin j=1; while (jm then writeln(Matched,position:,i); i=i+1; end; End.2 2、算法形式描述、算法形式描述第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略112022-4-23，Pattern=arePattern=areText=how are you!Text=how are you!n=12， m=33、示例、示例Text=how are you!Text=how are you!howhow ow ow w aw a arar areare re

12、re e ye y yoyo ou!ou!12 3 456 789101112i=1i=2i=3i=4i=5i=6i=7i=8i=9匹配匹配i=10 youyou第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略122022-4-23 算法算法 Simple-String-Matching Begin i=1; while (i=n-m+1) do begin j=1; while (jm then writeln(Matched,position:,i); i=i+1; end; End.4 4、算法復(fù)雜性分析、算法復(fù)雜性分析最壞情形復(fù)雜性分析最壞情形復(fù)雜性分析: : t(n)=m(n-m+1)

13、=O (mn)t(n)=m(n-m+1)=O (mn)問題：問題：1. 1.你所知道的字符串匹配你所知道的字符串匹配算法還有哪些？算法還有哪些？2.2.在何種情況下需要高性在何種情況下需要高性能字符串匹配算法？能字符串匹配算法？第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略132022-4-235 56 6.2.3 .2.3 并行串匹配算法的設(shè)計思路并行串匹配算法的設(shè)計思路研究串的研究串的數(shù)學(xué)性質(zhì)數(shù)學(xué)性質(zhì)是并行化的可能途徑是并行化的可能途徑周期性周期性第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略142022-4-23定義定義6 6.1 .1 給定兩個串給定兩個串w w和和u u，對于某一正常

14、數(shù)，對于某一正常數(shù)k k，如果，如果w = uw = uk ku u ，其中其中u uk k是是u u自身重復(fù)自身重復(fù)k k次，次，u u 是是u u的前綴，則稱的前綴，則稱u u是是w w的周的周期。期。 例例6 6.1 .1 令令w = ababababaw = ababababa，則，則u = ababu = abab是是w w的周期，因為的周期，因為w = uw = u2 2a a。w w還還有如下周期：有如下周期：abab，因為，因為w = uw = u4 4a aabababababab，因為，因為w = uw = u2 2a aabababab,abababab,因為因為w =

15、ua w = ua 。 第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略152022-4-23定義定義6 6.4.4 對于給定的對于給定的j(1j(1jm/2)jm/2)，如果，如果patj:m patj:m pat1:m pat1:mj+1j+1，則存在某個，則存在某個w(1wmw(1wmj+1)j+1)使得使得patw patw pats pats，其，其中中s = js = j1+w1+w，則記，則記WITj = wWITj = w。顯然。顯然WIT1 = 0WIT1 = 0。jm11mmj+1wsWITj = w 第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略162022-4-23例例6

16、.2 令令pat = abaababa(m = 8)，WIT1 = 0，WIT2 = 1，w=1,j=2,s=2-1+1=2 patw = a pats=bWIT3 = 2，w=1,j=3,s=3-1+1=3 patw = pats=a w=2,j=3,s=3-1+2=4 patw = b pats=aWIT4 = 4 w=1,j=4,s=4-1+1=4 patw = pats=a w=2,j=4,s=4-1+2=5 patw = pats=b w=3,j=4,s=4-1+3=6 patw = pats=a w=4,j=4,s=4-1+4=7 patw = a pats=bj:1jm/ /2,

17、 w:1wmj+1, s = j1+w , patw pats第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略172022-4-23根據(jù)根據(jù)WITjWITj的定義，按如下方式來區(qū)分的定義，按如下方式來區(qū)分非周期串和周期串非周期串和周期串： 對于所有對于所有22jm/2jm/2，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)WITj WITj 0 0時，則稱時，則稱patpat是是非周期的；非周期的； 對于所有對于所有22jm/2jm/2，若存在某個，若存在某個j j，使得，使得WITj = 0WITj = 0，則稱，則稱patpat是周期的。是周期的。 例例5.35.3 令pat1 = abcaabcabpat1 = ab

18、caabcab，因為對于所有，因為對于所有22jm/2jm/2，WITjWITj均不均不為零，所以為零，所以pat1pat1是非周期的；是非周期的；如令如令pat2 = abcabcabpat2 = abcabcab，則因為，則因為WIT4 = 0WIT4 = 0，所以，所以pat2pat2是周期是周期的的 第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略182022-4-23因為串匹配與模式串的周期性和非周期性有關(guān)，所以按照因為串匹配與模式串的周期性和非周期性有關(guān)，所以按照VishkinVishkin串匹配的算法，串匹配的算法，先要定義串的周期性和非周期性，而判定串的周期性要利用不匹先要定義串

19、的周期性和非周期性，而判定串的周期性要利用不匹配表配表WITWIT，所以求，所以求patpat的的WITWIT表表是算法最關(guān)鍵而且也是最困難的部是算法最關(guān)鍵而且也是最困難的部分。分。一旦求出了一旦求出了WITWIT表，就可分別研究非周期串的模式匹配和周期串表，就可分別研究非周期串的模式匹配和周期串的模式匹配算法了。的模式匹配算法了。第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略192022-4-23 SIMD-CREWSIMD-CREW模型上的非周期串的匹配算法模型上的非周期串的匹配算法 1 1、dualdual（p p，q q）的計算）的計算 為了以下的討論，我們再引入為了以下的討論，我們再

20、引入WITWIT ii，它是一個一維數(shù)組，其，它是一個一維數(shù)組，其中每個分量均是匹配的見證者。中每個分量均是匹配的見證者。即若即若patpat在在texttext的位置的位置i i不匹配，則定義不匹配，則定義WITWIT i i 0 0，否則，否則WITWIT i = 0(1ini = 0(1inm+1)m+1)。我們稱我們稱WITWIT i = 0i = 0的分量是匹配的見證者。起始的的分量是匹配的見證者。起始的WITWIT ii均均為零為零 第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略202022-4-23匹配算法的關(guān)鍵概念是正文中兩個位置匹配算法的關(guān)鍵概念是正文中兩個位置p p和和q

21、q之間的競爭之間的競爭dual(p,q)dual(p,q)，其中，其中，11p pqnqn = n = nm+1m+1，且，且q qp pm/2m/2。我們。我們稱，當(dāng)稱，當(dāng)patpat為非周期串時，為非周期串時，patpat不會同時出現(xiàn)在不會同時出現(xiàn)在texttext的位置的位置p p處和處和q q處。處。證明：令證明：令j = qj = qp+1p+1，因為，因為patpat是非周期的，所以是非周期的，所以WITj WITj 0 0，不妨假設(shè)不妨假設(shè)WITj = wWITj = w，則，則patw patw patj+w patj+w11。假定假定patpat在在texttext的的p p

22、位置出現(xiàn)，即位置出現(xiàn)，即pat = textp:p+mpat = textp:p+m11， pat1:m=textp:p+mpat1:m=textp:p+m1,1,則則patj+wpatj+w11=pat1+=pat1+j+wj+w2 2= = textp+ textp+ j+wj+w2 2=textp+=textp+q qp+1p+1+w+w2= 2= textq+wtextq+w11。由上。由上可知，可知，patw patw textq+w textq+w11，即，即patpat不會在不會在texttext的位置的位置q q處出處出現(xiàn)，此時可設(shè)置現(xiàn)，此時可設(shè)置WITWIT q = wq =

23、 w。同樣，假定同樣，假定patpat在特在特texttext的的q q位置出現(xiàn)，即位置出現(xiàn)，即patw = textq+wpatw = textq+w11，由此可知，由此可知textq+wtextq+w1 1 patj+w patj+w11，即，即patpat不會出現(xiàn)在不會出現(xiàn)在texttext的位置的位置p p，此時可設(shè)置，此時可設(shè)置WITWIT p = w+qp = w+qp p。第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略212022-4-23q可見可見dual(p,q)dual(p,q)的意義是很明確的：即當(dāng)?shù)囊饬x是很明確的：即當(dāng)patpat為非周期串時，為非周期串時，取取text

24、text中位置中位置p p和和q(1pq(1pqnqn ) )且且q qp pm/2m/2，則，則patpat不會在不會在p p和和q q處同時出現(xiàn)。因此可排除其中的一個位置，而剩下一個位置處同時出現(xiàn)。因此可排除其中的一個位置，而剩下一個位置作為可能發(fā)生匹配的候選者，令其為作為可能發(fā)生匹配的候選者，令其為r r，且置，且置WITWIT r = 0r = 0。 例例5.4 5.4 令令text = abaababaababaababaababatext = abaababaababaababaababa，pat = abaababapat = abaababa。我們有我們有WIT1=0WIT1=

25、0，WIT2=1WIT2=1，WIT3 =2WIT3 =2，WIT4 =4WIT4 =4。試考慮。試考慮p p =6=6，q =9q =9。令。令j =qj =qp+1 =4p+1 =4，我們有，我們有WIT4 = w =4WIT4 = w =4。在本例中，。在本例中，textq+wtextq+w1 =text9+41 =text9+41 = b 1 = b patw = pat4 = a patw = pat4 = a，因，因此可設(shè)置此可設(shè)置WITWIT 9 =49 =4。所以。所以p p和和q q競爭的結(jié)果，競爭的結(jié)果，p p獲勝，即獲勝，即dual(6,9) dual(6,9) =6=6

26、，也就是位置，也就是位置6 6是幸存者。是幸存者。第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略222022-4-23function dual(p,q) / /* * WITqp+1 0 * */ /begin if p = null then dualq else if q = null then dualp else begin jqp+1 wWITj if textq+w1 patw then (i) WIT qw (ii) dualp else (i) WIT pqp+w (ii) dualq end if end end if end if End第六章第六章 并行算法設(shè)計策略并行

27、算法設(shè)計策略232022-4-23非周期串的匹配算法非周期串的匹配算法假定假定m m和和n n 均是均是2 2的方冪，的方冪，(1)(1)首先將首先將texttext的的1 1，2 2，n n 劃分成不相交的大小為劃分成不相交的大小為2 2k k的若干的若干個個k-k-塊（塊（k = 0k = 0，1 1，log mlog m1 1），其中第），其中第k k個劃分為個劃分為1:21:2k k22k k+1:2+1:2* *2 2k k ii* *2 2k k+1:(i+1)+1:(i+1)* *2 2k k 在這樣劃分的在這樣劃分的k-k-塊中，塊中，任取兩個位置任取兩個位置p p和和q q總

28、滿足總滿足q qp pm/2m/2。(2)(2)開始時，開始時，k = 0k = 0，對每個，對每個i i，WITi =0WITi =0，在每個，在每個k-k-塊中，只塊中，只有一個候選者有一個候選者r r，置，置WITWIT r =0r =0；(3)(3)設(shè)置設(shè)置k = k+1k = k+1，然后在每個，然后在每個k-k-塊中，必有兩個候選，記之為塊中，必有兩個候選，記之為p p和和q q，并行地執(zhí)行，并行地執(zhí)行dual(p,q)dual(p,q)，競選的結(jié)果，僅剩下一個候選者，競選的結(jié)果，僅剩下一個候選者r r，置置WITWIT r =0r =0；(4)(4)重復(fù)上述過程重復(fù)上述過程log

29、 mlog m1 1次，得到所有可能發(fā)生匹配的候選位次，得到所有可能發(fā)生匹配的候選位置；最后對上述候選位置施行匹配檢查。整個計算過程形成一棵置；最后對上述候選位置施行匹配檢查。整個計算過程形成一棵樹樹 第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略242022-4-23算法算法6.5 SIMD-CREW模型上的非周期串匹配算法模型上的非周期串匹配算法輸入：輸入：Test，WIT，pat輸出：輸出：WIT procedure APERIOD-MATCHING MARK SPARSE(text，k)begin for k = 1 to log m1 do MORE SPARSE(text，k) e

30、nd forendprocedure MORE SPARSE(text，k)begin for all k-block par-do 令令p和和q是本塊的候選者是本塊的候選者 / /* * WIT 為為0 * */ / 候選者候選者dual(p，q) end forend 第六章第六章 并行算法設(shè)計策略并行算法設(shè)計策略252022-4-23例6.5 令text = abaababaababaababaababa，n =23；pat = abaababa，m =8。假定已計算出：WIT1 = 0， WIT2 = 1，WIT3 = 2， WIT4 = 4。a b a a b a b a a b a b a a b a b a a b a b a k=1 1 4 6 8 9 11 14 1