并行算法的一般設(shè)計(jì)方法

第四章

并行算法的一般設(shè)計(jì)方法4.1串行算法的直接并行化

4.2從問(wèn)題描述開(kāi)始設(shè)計(jì)并行算法

4.3借用已有算法求解新問(wèn)題

主要內(nèi)容設(shè)計(jì)并行算法的方法串行算法直接并行化：檢測(cè)串行算法中是否有可以并行執(zhí)行的部分，然后將其并行化從問(wèn)題本身出發(fā)，設(shè)計(jì)并行算法：從開(kāi)始分析問(wèn)題時(shí)，就考慮將其并行化借用已有算法求解新問(wèn)題：根據(jù)問(wèn)題的相似性，利用已有的并行算法來(lái)求解新問(wèn)題

4.1串行算法的直接并行化方法描述發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法改造為并行算法。

4.1串行算法的直接并行化說(shuō)明由串行算法直接并行化的方法是并行算法設(shè)計(jì)的最常用方法之一；不是所有的串行算法都可以直接并行化的；一個(gè)好的串行算法并不能并行化為一個(gè)好的并行算法；許多數(shù)值串行算法可以并行化為有效的數(shù)值并行算法。4.1.1快速排序及其串行算法基本思想：（1）將當(dāng)前無(wú)序序列(A[q],…,A[r])分成兩個(gè)非空子序列（A[q],…A[s])和(A[s+1],…A[r])，其中第一個(gè)子序列中的任意元素都小于等于后一個(gè)子序列中的任意元素（2）對(duì)劃分后的兩個(gè)子序列實(shí)行遞歸運(yùn)算（3）直到子序列中僅有兩個(gè)元素為止如何選定主元？如何將一個(gè)序列

劃分成兩個(gè)序列？4.1.1快速排序及其串行算法輸入：無(wú)序序列(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)}遞歸結(jié)束條件劃分后的第一個(gè)子序列劃分后的第二個(gè)子序列快速排序（最壞情況）712345688123457651234412312345678123456782134567831245678567867881234567Step1:2:3:4:5:6:7:8:4.1.2快速排序的并行化思想：并行地調(diào)用串行的快速排序算法，對(duì)兩個(gè)所

劃分的子序列進(jìn)行快速排序。4.1.2快速排序的并行化一、基于二叉樹(shù)的并行選主元PRAM——CRCW上的快速排序算法

（1）構(gòu)造一棵二叉排序樹(shù)，其中主元是根（2）小于等于主元的元素處于左子樹(shù)（3）大于等于主元的元素處于右子樹(shù)（4）其左、右子樹(shù)分別也是一棵二叉排序樹(shù)1586424213102026對(duì)二叉樹(shù)進(jìn)行中序遍歷可以得到排序序列4.1.2快速排序的并行化待排序序列（A1,A2

…An

）,分別存放到（P1,P2

…Pn

）,處理器Pi保存元素Ai排序樹(shù)的樹(shù)根為root（SM變量），左孩子為L(zhǎng)c[root]，右孩子為Rc[root]fi（局部變量）:存有主元的處理器號(hào)如果某處理器中的元素被選定為主元后，該處理器即可停止計(jì)算

構(gòu)造出的二叉排序樹(shù)是不唯一的PRAM-CRCW上的快排序二叉樹(shù)構(gòu)造算法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實(shí)例給定待排序序列：33，21，13，54，82，33，44，72一種候選答案一種候選答案一種候選答案問(wèn)題描述：對(duì)a[1],a[2]…a[n]按照從小到大排序，排序后結(jié)果存入b[1],b[2]…b[n]思路：將a[1]與a[2]…a[n]比較，記錄比其小的元素的個(gè)數(shù)，令其為k，a[1]就存入數(shù)組b[k+1]中；將a[2]與a[1]…a[n]比較，記錄比其小的元素的個(gè)數(shù)，令其為k，a[2]就存入數(shù)組b[k+1]中；…4.1.3枚舉排序時(shí)間復(fù)雜度為O(n2)串行枚舉排序輸入：無(wú)序數(shù)組a[1],a[2]…a[n]輸出：有序數(shù)組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并行枚舉排序思想：一個(gè)長(zhǎng)為n的輸入序列，處理器個(gè)數(shù)為n每個(gè)處理器負(fù)責(zé)完成一個(gè)元素a[i]的定位處理器將所有的定位信息送到主進(jìn)程主進(jìn)程負(fù)責(zé)完成所有元素的最終排位并行枚舉排序輸入：無(wú)序數(shù)組a[1],a[2]…a[n]輸出：有序數(shù)組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）思想：均勻劃分局部排序正則采樣（抽取樣本）采樣排序選擇主元主元?jiǎng)澐秩纸粨Q歸并排序方法描述從問(wèn)題本身描述出發(fā)，不考慮相應(yīng)的串行算法，設(shè)計(jì)一個(gè)全新的并行算法評(píng)注挖掘問(wèn)題的固有特性與并行的關(guān)系設(shè)計(jì)全新的并行算法是一個(gè)挑戰(zhàn)性和創(chuàng)造性的工作利用串的周期性的PRAM-CRCW算法是一個(gè)很好的范例4.2從問(wèn)題描述開(kāi)始設(shè)計(jì)

并行算法4.2從問(wèn)題描述開(kāi)始設(shè)計(jì)

并行算法串匹配：計(jì)算機(jī)領(lǐng)域研究較為廣泛的問(wèn)題之一應(yīng)用領(lǐng)域文字編輯處理、圖像處理、文獻(xiàn)檢索、自然語(yǔ)言識(shí)別、生物學(xué)定義一種模式匹配問(wèn)題，在給定的文本串中找出與模式串匹配的子串的起始位置。串匹配串匹配常見(jiàn)問(wèn)題精確匹配：KMP隨機(jī)串匹配近似串匹配由兩個(gè)設(shè)計(jì)者的姓名命名4.2.1KMP串匹配算法例1：正文串T：abaabaabcac模式串P：abaabcac你的匹配算法是什么？4.2.1KMP串匹配算法例2：正文串T：abcdefabcdefabcdeg模式串P：abcdefabcdeg

i=12，j=12時(shí)，T[12]≠P[12]

關(guān)鍵問(wèn)題：如何移動(dòng)模式串，重新進(jìn)行P與T的比較？ij4.2.1KMP串匹配算法例2：正文串T：abcdefabcdefabcdeg模式串P：abcdefabcdeg當(dāng)T[12]≠P[12]時(shí)，比較T[12]與P[6]

ijnext[12]=6KMP思想文本串T[1,n]，模式串P[1,m]，執(zhí)行T[i]和P[j]的匹配情況：若T[i]=P[j]:若T[i]≠P[j]:繼續(xù)檢查T(mén)[i+1]和P[j+1]是否匹配模式串右移1位，檢查T(mén)[i+1]和P[1]是否匹配模式串右移j-next[j]位，檢查T(mén)[i]和P[next[j]]是否匹配j=11<j≤mnext函數(shù)如何構(gòu)造？不斷重復(fù)上述過(guò)程，直到i=n或j=m結(jié)束

next函數(shù)next函數(shù)：根據(jù)模式串本身的信息構(gòu)造的。函數(shù)作用：當(dāng)模式串中第j個(gè)字符與正文串的第i個(gè)字符匹配失敗后，需要通過(guò)next函數(shù)將模式串進(jìn)行右移。next函數(shù)定義方法：模式串有局部相同的子串next函數(shù)例：求模式串P=abaabcac的next函數(shù)j12345678模式串a(chǎn)baabcacnext[j]01122312next[j]=k:k為模式串中重新與T[i]字符比較的位置next函數(shù)T：ababaabcacP：T[4]≠P[4]，而next[4]=2所以比較T[4]與P[2]，模式串右移j-next[j]ijabaabcacnext函數(shù)課堂練習(xí)：P1=aaabcaabaP2=abcabcacbP3=babbabab01231123101112345101122343next函數(shù)的算法輸入：模式串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函數(shù)，KMP算法便可以實(shí)現(xiàn)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串匹配算法的并行化設(shè)計(jì)并行算法的出發(fā)點(diǎn)：正文串與模式串是否匹配，與串的自身前綴有關(guān)，這種前綴特性，就是串的周期性。如何判斷串的周期性？WIT函數(shù)WIT函數(shù)定義：對(duì)于給定的j（1<j≤m/2），如果P[j:m]≠p[1:m-j+1]，則存在某個(gè)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）串的周期性非周期串：對(duì)于所有2≤j≤m/2，當(dāng)且僅當(dāng)WIT[j]≠0周期串：

對(duì)于所有2≤j≤m/2，當(dāng)存在某個(gè)j，使得WIT[j]=0串的周期性例：P1=abaababaP2=baabaabaWIT[1]=0WIT[2]=1WIT[3]=2WIT[4]=4WIT[1]=0WIT[2]=1WIT[3]=1WIT[4]=0非周期串周期串主要研究非周期串的并行串匹配算法非周期串的匹配思想：

根據(jù)WIT函數(shù)來(lái)計(jì)算模式串在正文串中的匹配位置，為了減少P和T的比較次數(shù)，引入競(jìng)爭(zhēng)函數(shù)duel()。duel()函數(shù)：

若duel(p,q)=p，則表示當(dāng)模式串在正文的位置p處匹配時(shí)，那么在另一個(gè)位置q處一定不匹配。當(dāng)模式串P為非周期串時(shí)，模式串P不會(huì)同時(shí)在正文串的p處和q處匹配。

采用淘汰機(jī)制，從而減少P和T的比較次數(shù)duel()函數(shù)計(jì)算duel(p,q)過(guò)程：j=q-p+1w=WIT[j]判斷T[q+w-1]與P[w]的關(guān)系：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()函數(shù)令text=abaababaababaaba，p=abaababa，計(jì)算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并行思路各個(gè)處理器并行執(zhí)行duel(1,2)，duel(3,4)…找出勝者各個(gè)處理器在上一輪的勝者之間執(zhí)行duel函數(shù)最后經(jīng)過(guò)log2n輪競(jìng)爭(zhēng)后，有若干可能匹配的位置，然后再一一進(jìn)行驗(yàn)證4.3借用已有算法求解新問(wèn)題方法描述找出求解問(wèn)題和某個(gè)已解決問(wèn)題之間的聯(lián)系改造或利用已知算法應(yīng)用到求解問(wèn)題上評(píng)注使用矩陣乘法算法求解所有點(diǎn)對(duì)間最短路徑是一個(gè)很好的范例

1.利用矩陣乘法求所有點(diǎn)對(duì)間最短路徑問(wèn)題說(shuō)明

有向圖G=(V,E)，邊權(quán)矩陣W=(wij)n×n，求最短路徑長(zhǎng)度矩陣D=(dij)n×n，dij為vi到vj的最短路徑長(zhǎng)度。假定圖中無(wú)負(fù)權(quán)有向回路，記d(k)ij為vi到vj至多有k-1個(gè)中間結(jié)點(diǎn)的最短路徑長(zhǎng)，Dk=(d(k)ij)n×n利用矩陣乘法求所有點(diǎn)對(duì)間最短路徑計(jì)算原理(1)d(1)ij=wij

當(dāng)<i,j>E，則wij=∞d(1)ij=0當(dāng)i=j

(2)

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

視：”+”“×”，“min”“∑”，則上式變?yōu)閐(k)ij=∑1≤l≤n{d(k/2)il×d(k/2)lj}

(4)應(yīng)用矩陣乘法：D1D2D4…D2logn(=Dn)頂點(diǎn)間最短路徑算法讀入矩陣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.利用布爾矩陣求