并行算法與并行程序設(shè)計(jì)第02章 并行算法

第二章并行算法教師：彭四偉一、問(wèn)題的并行性把有唯一輸入向量和唯一輸出向量的一個(gè)程序段在某一環(huán)境下的一次執(zhí)行稱為一個(gè)進(jìn)程。設(shè)有一組程序段A1…An，若{Ai}在n個(gè)處理機(jī)上同時(shí)執(zhí)行的結(jié)果等同于{Ai}以任意順序執(zhí)行的結(jié)果，則稱{Ai}為可并行執(zhí)行的。一、問(wèn)題的并行性設(shè)兩個(gè)程序段A、B，如果

(IA∩OB)∪(OA∩IB)∪(OA∩OB)≠Φ，

則稱A和B數(shù)據(jù)相關(guān)，否則稱之為數(shù)據(jù)無(wú)關(guān)。設(shè)兩個(gè)語(yǔ)句L1和L2，如果

L1的執(zhí)行結(jié)果能夠決定L2是否執(zhí)行，

則稱L2控制相關(guān)于L1。一、問(wèn)題的并行性設(shè)兩個(gè)程序段A、B，且A先于B，若A與B數(shù)據(jù)相關(guān)或控制相關(guān)，則稱A是B的父進(jìn)程。父進(jìn)程關(guān)系可以傳遞，稱為祖先進(jìn)程。記α(A,B)為A是B的父進(jìn)程，αT即祖先進(jìn)程關(guān)系。設(shè)某一程序P中的進(jìn)程集合W，于是G=（W,α）可以構(gòu)成一張圖，稱為進(jìn)程流程圖。A1：x=1A2：y=2A3：s=2*x+yA4：t=x*x*yA5：u=3*s-tA6：v=cos(t)A7：z=u*v+1如下例所示：u,vzA7tvA6s,tuA5x,ytA4x,ysA3yA2xA1輸入輸出進(jìn)程輸入輸出表如下：A7A7A6A7A5A5，A6A4A5A3A3，A4A2A3，A4A1子進(jìn)程父進(jìn)程進(jìn)程關(guān)系表如下：BeginA1A2A3A4A5A6A7End進(jìn)程流程圖如下：二、并行算法的性能指標(biāo)對(duì)問(wèn)題規(guī)模n，所動(dòng)用的處理器的數(shù)目p(n)，運(yùn)行時(shí)間或最壞運(yùn)行時(shí)間tp(n)。粒度：并行單元的規(guī)模，通常將循環(huán)級(jí)及以下稱為小粒度，子程序級(jí)稱為大粒度。工作量Wp(n)：Wp(n)=tp(n)*p(n)，直觀上即模擬該并行算法的串行算法的計(jì)算量。工作量越小，算法的性能越好。如果對(duì)同一問(wèn)題，并行算法A與串行算法B的工作量同階，稱A對(duì)B工作量有效，若A對(duì)最壞情況下的最優(yōu)算法B工作量有效，稱A工作量有效。加速比Sp(n)：Sp(n)=ts(n)/tp(n)，其中ts(n)是解同一問(wèn)題在最壞情況下的最優(yōu)串行算法的運(yùn)行時(shí)間。加速比反映運(yùn)行時(shí)間的改進(jìn)倍數(shù)。由于并行算法可以用串行算法來(lái)模擬，模擬的串行算法的運(yùn)行時(shí)間不超過(guò)p(n)*tp(n)，所以有1≤Sp(n)≤p(n)。工作效率Ep(n)：Ep(n)=Sp(n)/p(n)，反映算法所占用的處理器的工作效率，即工作飽滿程度。工作效率越高，算法的性能越好。由1≤Sp(n)≤p(n)，有1/p(n)≤Ep(n)≤1。三、并行求和倍增法求和倍增法是并行分治的一種簡(jiǎn)化形式。其基本思想是將原問(wèn)題反復(fù)分解為等規(guī)模的兩個(gè)子問(wèn)題，在逐步分解的過(guò)程中，子問(wèn)題個(gè)數(shù)成倍增加。將各個(gè)子問(wèn)題恰當(dāng)?shù)赜成涞礁髋_(tái)處理機(jī)上，即可實(shí)現(xiàn)計(jì)算過(guò)程的并行化。intPSum(intL[],ints,intt){if(s==t)returnL[s];intk=(s+t)/2;returnPSum(L,s,k)+PSum(L,k+1,t);}三、并行求和倍增法求和計(jì)算序列L[0..n-1]的和，記為S(0,n-1)。S(0,7)S(0,3)S(4,7)S(0,1)S(2,3)S(4,5)S(6,7)三、并行求和倍減法求和計(jì)算序列L[0..n-1]的和，記為S(0,n-1)。設(shè)可用處理器為n/2個(gè)。intPSum(intL[],intn){ k=n/2; while(k>0) { forallPii=0..k-1do { L[i]+=L[i+k]; } k/=2; } returnL[0];}四、平衡樹(shù)法平衡樹(shù)法的基本思想用一棵平衡二叉樹(shù)組織并行計(jì)算，輸入元素存放在葉結(jié)點(diǎn)，然后逐層并行地計(jì)算一直到根結(jié)點(diǎn)。四、平衡樹(shù)法以求最大值問(wèn)題為例計(jì)算序列L[0..n-1]中的最大值。不失一般性，設(shè)n=2m，A是一個(gè)大小為2n-1的數(shù)組，采用完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，將序列分別存放到n個(gè)葉結(jié)點(diǎn)中，在樹(shù)的同一層各結(jié)點(diǎn)上作并行計(jì)算，逐層遞推，直到得到最終結(jié)果。fork=m-1to0doforallPii=0…2k-1doj2k-1+i;A[j]max(A[2*j+1],A[2*j+2]);四、平衡樹(shù)法平衡樹(shù)法的評(píng)估以平衡樹(shù)法求解最大值是一個(gè)EREW算法，計(jì)算時(shí)間tp(n)=O(logn)，運(yùn)用處理器最多為p(n)=n/2，工作量為O(nlogn)，不是工作量有效的算法。平衡樹(shù)方法的優(yōu)點(diǎn)是在樹(shù)中能快速存取信息，對(duì)數(shù)據(jù)的傳遞、壓縮、抽取和前綴計(jì)算均十分有用。五、向量法向量法的基本思想以向量方式描述計(jì)算過(guò)程；以并行方式執(zhí)行向量計(jì)算。五、向量法以矩陣計(jì)算為例對(duì)n階矩陣，串行加法的計(jì)算量為n2，若動(dòng)用n個(gè)（或n2個(gè)）處理器，分別處理每行（或列）的相加運(yùn)算，則可以得到計(jì)算量亦為n2，工作量有效。五、向量法以矩陣計(jì)算為例矩陣相乘：C=A*Bfori=1tondo forj=1tondo ci,j=0 fork=1tondo ci,j+=ai,k*bj,kfori=1tondo forallPjj=1tondo ci,j=0 //Ci.=0 fork=1tondo //Ci.=∑ai,k*Bk. forallPjj=1tondo ci,j+=ai,k*bk,j串行算法：并行算法：六、線性遞推問(wèn)題一般性線性遞推問(wèn)題對(duì)一個(gè)k階，N式的線性遞推式，

如下所示：x1= b1x2= a21x1+b2x3= a31x1+a32x2+b3x4= a41x1+a42x2+a43x3+b4……xN= aN1x1+aN2x2+…+aN,N-1xN-1+bN展開(kāi)式如下：forallPkk=1…NdoS[k]=b[k];fori=2toN{ forallPkk=i…Ndo S[k]+=x[i-1]*a[k][i-1]; x[i]=S[i];}可得算法如下：六、線性遞推問(wèn)題一階線性遞推問(wèn)題有一階線性遞推式如下：x1= b1x2= a2b1+b2x3= a3a2b1+a3b2+b3x4= a4a3a2b1+a4a3b2+a3b3+b4x5= a5a4a3a2b1+a5a4a3b2+a5a4b3+a5b4+b5x6= a6a5a4a3a2b1+a6a5a4a3b2+a6a5a4b3+a6a5b4+a6b5+b6x7= a7a6a5a4a3a2b1+a7a6a5a4a3b2+a7a6a5a4b3+a7a6a5b4+a7a6b5+a7b6+b7x8= a8a7a6a5a4a3a2b1+a8a7a6a5a4a3b2+a8a7a6a5a4b3+a8a7a6a5b4+a8a7a6b5+a8a7b6+a8b7+b8展開(kāi)式如下：定義：則xi=Q(i,1)forallPkk=1…Ndo{ P[k]=a[k]; Q[k]=b[k];}for(L=1;L<N;L+=L){ forallPkk=1…Ndo if(k-L>=1) { C[k]=P[k]*Q[k-L]+Q[k]; Q[k]=C[k]; C[k]=P[k]*P[k-L]; P[k]=C[k]; }}可得并行算法如下：可推導(dǎo)得到：P(i,i-k+1)*Q(i-k,i-2k+1)+Q(i,i-k+1)=Q(i,i-2k+1)約定P(i,i+1)=1，aj=1(j≤1)，bj=0(j<1)設(shè)初始值：P[i]=P(i,i)=ai，Q[i]=Q(i,i)=bi設(shè)已知某一階線性遞推式的系數(shù)向量如下：a=(1,3,2,7,1,4,2,5)Tb=(2,1,9,3,2,4,6,3)T七、線性代數(shù)方程組高斯消去法for(k=1;i<N;i++){ for(j=k+1;j<=N+1;j++)A[k][j]/=A[k][k]; for(i=1;i<=N;i++) if(i!=k) for(j=k+1;j<=N+1;j++) A[i][j]-=A[i][k]*A[k][j];}串行求解算法：for(k=1;i<N;i++){ forallPjj=k…NdoA[k][j+1]/=A[k][k]; for(i=1;i<=N;i++) if(i!=k) forallPjj=k…Ndo A[i][j+1]-=A[i][k]*A[k][j+1];}并行求解算法：八、一元多項(xiàng)式的計(jì)算一元多項(xiàng)式的一般式八、一元多項(xiàng)式的計(jì)算一元多項(xiàng)式的串行最優(yōu)解法PN(x)=((…(aNx+aN-1)x+aN-2)x+…+a1)x+a0X0=1 P0=a0X1=X0*x P1=P0+a1*X1X2=X1*x P2=P1+a2*X2......XN=XN-1*x PN=PN-1＋aN*XN八、一元多項(xiàng)式的計(jì)算并行解法作推導(dǎo)如下：令a(1)i=(a2i+a2i+1x)，可將關(guān)于x的多項(xiàng)式看作關(guān)于x2的多項(xiàng)式：不失一般性，設(shè)N+1=2μ，反復(fù)利用上述方法，可得：其中：由此得到并行計(jì)算步驟：第1步：第2步：第3步：…………第μ步：在并行計(jì)算過(guò)程中同時(shí)計(jì)算八、一元多項(xiàng)式的計(jì)算一階線性遞推解法Y0= anY1= x*Y0+an-1Y2= x*Y1+an-2……Yi= x*Yi-1+an-i……Yn= x*Yn-1+a0PN(x)=((…(aNx+aN-1)x+aN-2)x+…+a1)x+a0令xai，aibn-i，即得一階線性遞推公式，代入一階線性遞推算法即可。九、指針跳越技術(shù)指針跳越技術(shù)是設(shè)計(jì)關(guān)于靜態(tài)鏈表快速操作并行算法的一個(gè)有力工具。012345678data-1925179861302215next5704832616117981519223025九、指針跳越技術(shù)表序問(wèn)題已知n個(gè)元素，構(gòu)成一個(gè)靜態(tài)單鏈表，要求計(jì)算每個(gè)元素到表尾的距離d[i]，即計(jì)算：6117981519223025voidD(slistL,intd[],inti){ if(L[i].next==0) d[i]=0; else { D(L,d,L[i].next); d[i]=d[L[i].next]+1; }}串行遞歸算法描述如下：voidD(slistL,intd[]){ StackS;InitStack(S); for(inti=0;L[i].next!=0;i=L[i].next) Push(S,L[i].next); Pop(S,i); d[i]=0; while(!EmptyStack(S)) { Pop(S,j); d[j]=d[i]+1; i=j; }}串行非遞歸算法描述如下：九、指針跳越技術(shù)表序問(wèn)題使用指針跳越技術(shù)，用n個(gè)處理器并行對(duì)n個(gè)元素進(jìn)行處理。012345678data-1925179861302215next570483261P1P2P3P4P5P6P7P8forallPii=1…ndo if(next[i]==0)d[i]=0;elsed[i]=1;while(存在next[i]!=0){ forallPii=1…ndo if(next[i]!=0) { d[i]+=d[next[i]]; next[i]=next[next[i]]; }}算法描述如下：611798151922302511111110611798151922302576543210第三趟跳越611798151922302544443210第二趟跳越611798151922302522222210第一趟跳越12345678data1925179861302215next70483261d1011111122122202dnextdata720418061522306198172519876543211次跳越42144403dnextdata200167001522306198172519876543212次跳越42175603dnextdata000000001522306198172519876543213次跳越九、指針跳越技術(shù)指針跳越操作將破壞原有的鏈結(jié)構(gòu)，因此在操作前應(yīng)復(fù)制原鏈結(jié)構(gòu)，在復(fù)制的鏈結(jié)構(gòu)上進(jìn)行跳越操作?？勺C明算法的正確性。在循環(huán)過(guò)程中，以每個(gè)元素為鏈頭的子表中的d值之和，恰好等于該元素到表尾的距離。在指針跳越過(guò)程中，將越過(guò)的元素的d值累積到被操作元素上，以保證上述性質(zhì)仍然成立。當(dāng)元素沒(méi)有后繼元素時(shí)，其d值即是到表尾的距離值。注意：在對(duì)多個(gè)next指針進(jìn)行更新時(shí)，要求讀寫操作保持同步，即讀取next值的操作要先于任何next的寫入操作。由于每次跳越將使一個(gè)子表被分裂成兩個(gè)子表，因此計(jì)算時(shí)間為O(logn)。九、指針跳越技術(shù)表前綴的并行計(jì)算表前綴計(jì)算問(wèn)題由一個(gè)二元可結(jié)合運(yùn)算⊕來(lái)定義，對(duì)一個(gè)輸入序列<x1…xn>，其輸出是序列<y1…yn>，滿足：y1=x1，且yk=yk-1⊕xk=x1⊕x2⊕…⊕xk,k=2,3,…,n即每一個(gè)yk是輸入序列的前k個(gè)元素的“累積”。表序計(jì)算可以看作表前綴的一個(gè)特例（須先將表顛倒）。為描述方便，定義如下符號(hào)：[i,j]=xi⊕xi+1⊕…⊕xj，1≤i≤j≤n則有：[k,k]=xk，[i,k]=[i,j]⊕[j+1,k]，yk=[1,k]forallPii=1…ndo y[i]=x[i];while(存在next[i]!=0){ forallPii=1…ndo { if(next[i]!=0) { y[next[i]]=y[i]⊕y[next[i]]; next[i]=next[next[i]]; } }}并行算法描述如下：611798151922302511111111611798151922302512345678第三趟跳越611798151922302512344444第二趟跳越611798151922302512222222第一趟跳越九、指針跳越技術(shù)前綴運(yùn)算中的循環(huán)終止條件的判斷對(duì)已知表長(zhǎng)n的情況下，循環(huán)步長(zhǎng)不超過(guò)logn。對(duì)未知表長(zhǎng)n的情況下，表頭元素的循環(huán)步數(shù)最多，通過(guò)判斷表頭元素的next是否已變?yōu)?來(lái)作為循環(huán)的終止條件?？梢酝ㄟ^(guò)O(1)的運(yùn)算找到表頭單元。forallPii=1…ndo{ h[i]=1; if(next[i]!=0)h[next[i]]=0; if(h[i]==1)head=I;}九、指針跳越技術(shù)應(yīng)用舉例中位元素定位查找鏈表中序號(hào)為K的元素。數(shù)組的前綴運(yùn)算yk=yk-1⊕xk=x1⊕x2⊕…⊕xk藍(lán)色鏈表問(wèn)題鏈表中有紅藍(lán)兩色的結(jié)點(diǎn)，將藍(lán)色結(jié)點(diǎn)挑出組成一個(gè)新的鏈表。循環(huán)鏈表的標(biāo)識(shí)問(wèn)題在循環(huán)鏈表上應(yīng)用指針跳越技術(shù)，如何標(biāo)識(shí)跳越的結(jié)束狀態(tài)。十、歐拉回路技術(shù)歐拉回路一個(gè)圖的歐拉回路是指經(jīng)過(guò)圖中每條弧恰好一次的一條回路。一個(gè)有向強(qiáng)連通圖有歐拉回路的充要條件是該圖中每個(gè)結(jié)點(diǎn)的出度等于入度。無(wú)向連通圖可以轉(zhuǎn)換為有歐拉回路的有向強(qiáng)連通圖。十、歐拉回路技術(shù)二叉樹(shù)的歐拉回路構(gòu)造構(gòu)造思路通過(guò)對(duì)二叉樹(shù)進(jìn)行變形，構(gòu)造歐拉回路；將每個(gè)結(jié)點(diǎn)分解為三個(gè)單鏈子結(jié)點(diǎn)A、B、C；令A(yù)為父結(jié)點(diǎn)入口，左子出口；令B為左子入口，右子出口；令C為右子入口，父結(jié)點(diǎn)出口；歐拉回路鏈的順序?yàn)椋篈——左子樹(shù)——B——右子樹(shù)——C十、歐拉回路技術(shù)二叉樹(shù)的歐拉回路構(gòu)造構(gòu)造規(guī)則若一個(gè)結(jié)點(diǎn)有左子，則令結(jié)點(diǎn)的A指向左子結(jié)點(diǎn)的A，否則令結(jié)點(diǎn)的A指向結(jié)點(diǎn)的B；若一個(gè)結(jié)點(diǎn)有右子，則令結(jié)點(diǎn)的B指向右子結(jié)點(diǎn)的A，否則令結(jié)點(diǎn)的B指向結(jié)點(diǎn)的C；若一個(gè)結(jié)點(diǎn)是父結(jié)點(diǎn)的左子，則令C指向父結(jié)點(diǎn)的B；若是父結(jié)點(diǎn)的右子，則令C指向父結(jié)點(diǎn)的C；根結(jié)點(diǎn)的C指向空；十、歐拉回路技術(shù)計(jì)算二叉樹(shù)各結(jié)點(diǎn)的層次定義根結(jié)點(diǎn)為0層；定義子結(jié)點(diǎn)的層數(shù)為父結(jié)點(diǎn)的層數(shù)加1；0層1層2層3層十、歐拉回路技術(shù)計(jì)算二叉樹(shù)各結(jié)點(diǎn)的層次利用歐拉回路計(jì)算先構(gòu)造二叉樹(shù)的歐拉回路；令各結(jié)點(diǎn)的A的初值為1，B的初值為0，C的初值為-1；對(duì)該鏈進(jìn)行前綴加和運(yùn)算；各結(jié)點(diǎn)C中所得到的結(jié)果即該結(jié)點(diǎn)的層次；A——左子樹(shù)——B——右子樹(shù)——C十、歐拉回路技術(shù)計(jì)算二叉樹(shù)遍歷序設(shè)A初值為1，B初值為0，C初值為0，

前綴計(jì)算后，A中即為前序的編號(hào)；設(shè)A初值為0，B初值為1，C初值為0，

前綴計(jì)算后，B中即為中序的編號(hào)；設(shè)A初值為0，B初值為0，C初值為1，

前綴計(jì)算后，C中即為后序的編號(hào)；根據(jù)歐拉回路鏈序：A——左子樹(shù)——B——右子樹(shù)——C十、歐拉回路技術(shù)計(jì)算二叉樹(shù)上各結(jié)點(diǎn)為根的子樹(shù)的規(guī)模根據(jù)歐拉回路鏈序：A——左子樹(shù)——B——右子樹(shù)——C在前序遍歷序計(jì)算中，每個(gè)結(jié)點(diǎn)的C-A+1即子樹(shù)規(guī)模；在中序和后序遍歷序計(jì)算中，每個(gè)結(jié)點(diǎn)的C-A的值即子樹(shù)規(guī)模；十、歐拉回路技術(shù)二叉樹(shù)的藍(lán)色鏈表問(wèn)題設(shè)在一棵有n個(gè)結(jié)點(diǎn)的二叉樹(shù)T中，某些結(jié)點(diǎn)標(biāo)記為藍(lán)色結(jié)點(diǎn)，將二叉樹(shù)T中的所有沒(méi)有藍(lán)色祖先的藍(lán)色結(jié)點(diǎn)連成一個(gè)鏈表。對(duì)藍(lán)色元素初始化為A=1，B=0，C=-1；對(duì)紅色元素初始化為：A=0，B=0，C=0；構(gòu)造歐拉回路，進(jìn)行前綴計(jì)算后，結(jié)點(diǎn)的C中為“藍(lán)深度”，即藍(lán)色祖先結(jié)點(diǎn)的個(gè)數(shù)。將所有有藍(lán)色祖先的結(jié)點(diǎn)的顏色全改為紅色，用鏈表的藍(lán)色鏈算法剔除其中的無(wú)藍(lán)色祖先的結(jié)點(diǎn)。十、歐拉回路技術(shù)多叉有序樹(shù)的歐拉回路十一、MIMD算法算術(shù)表達(dá)式的同步MIMD算法例：(A+B(C+D*E*F))+G變形為：A+G+B*C+B*D*E*FP1P2P3P4a1=A+GP(r1)a1+=a2P(r3)a1+=a3a2=B*CV(r1)a3=B*DP(r2)a3*=a4V(r3)a4=E*FV(r2)十一、MIMD算法區(qū)間分割法解代數(shù)方程的根求單調(diào)連續(xù)函數(shù)f(x)=0的根。設(shè)已知兩端l~u，對(duì)區(qū)間進(jìn)行n+1等分，令y[0]=f(l)，y[n+1]=f(u)。lu…………十一、MIMD算法同步牛頓迭代法解代數(shù)方程的根迭代公式：P0P1while未達(dá)到精度{ y=f(x); wait(y’) x=x–y/y’;}while未達(dá)到精度{ wait(x) y’=f’(x);}并行進(jìn)程如下：P0P1y0=f(x0)y0’=f’(x0)x1=x0–y0/y0’y1=f(x1)y1’=f’(x1)x2=x1-y1/y1’…………并行計(jì)算過(guò)程如下：十一、MIMD算法異步牛頓迭代法解代數(shù)方程的根P1P2While未達(dá)到精度{ y=f(x); x=x–y/y’;}While未達(dá)到精度{ y’=f’(x);}十二、MIMD算法異步枚舉排序算法用n個(gè)進(jìn)程并行計(jì)算各元素在排序后序列中的位置。i01234567X1593233819214T4891519213233十二、MIMI算法異步快速排序算法在快速排序過(guò)程中，每一步劃分完成后，所得到的兩個(gè)待排序子序列是相互獨(dú)立的，可以創(chuàng)建兩個(gè)并行進(jìn)程分別對(duì)這兩個(gè)子序列進(jìn)行遞歸快速排序。intQSort(L,s,t){ if(s>=t)return0; k=Partition(L,s,t); QSort(L,s,k-1); QSort(L,k+1,t); return1;}十二、并行分治分治通過(guò)將一個(gè)問(wèn)題分解成若干個(gè)性質(zhì)相同的子問(wèn)題，并遞歸地對(duì)子問(wèn)題進(jìn)行求解，然后將各子問(wèn)題的解加以合并構(gòu)造出原問(wèn)題的解。分治步驟將問(wèn)題的輸入進(jìn)行均勻劃分，構(gòu)成規(guī)模大致相等的若干個(gè)同類的子問(wèn)題；遞歸求解各子問(wèn)題；將各子問(wèn)題的解歸并成為原問(wèn)題的解；十二、并行分治并行分治F(I){ if輸入足夠小then OAnswer(I); else {

分解輸入：I1,…Ik；

forallPii=1…kdo Oi

F(Ii,Oi); OCombine(O1,…Ok); }}十二、并行分治最近點(diǎn)對(duì)問(wèn)題d1d2d2d十三、劃分法劃分法與分治法相似，劃分原理也是將原問(wèn)題進(jìn)行分解，分別求解，再歸并子問(wèn)題的解。所不同的是，分治法采用簡(jiǎn)單的分解方法，因此設(shè)計(jì)的難點(diǎn)在于如何歸并子問(wèn)題的解，而劃分方法則講究分解的方法，以獲得簡(jiǎn)單的歸并策略。十三、劃分法有序序列歸并設(shè)A=(a1,a2,…,an)，

B=(b1,b2,…,bm)，

是U上的單調(diào)增序列，且A∩B=Ф。

將A和B歸并到：

C=(c1,c2,…,cm+n)。十三、劃分法有序序列歸并定義：對(duì)U上的有序序列列X=(x1,x2,…,xt)，x∈U，x在X上的位序rank(x:X)為X中小于等于x的元素個(gè)數(shù)。歸并問(wèn)題即求rank(x:A∪B)，x∈A∪B。分別求出rank(ai:B)和rank(bj:A)，即可得到rank(x:A∪B)=rank(x:A)+rank(x:B)。這樣就可以在O(logn)時(shí)間內(nèi)用O(nlogn)工作量完成合并的任務(wù)。但這樣的解法不是一個(gè)工作量有效的算法。通過(guò)進(jìn)一步劃分，可以得到工作量有效的解法。十三、劃分法有序序列歸并可以在O(logn)的時(shí)間內(nèi)將A和B劃分成p對(duì)子序列(Ai,Bi)，i=0,1,…,p-1，

使得Ai和Bi中的每一個(gè)元素均大于Ai-1和Bi-1中的元素。

經(jīng)過(guò)這樣劃分，合并問(wèn)題就轉(zhuǎn)化為子序列對(duì)（Ai,Bi）的合并問(wèn)題了。Aa1…aj[1]aj[1]+1…aj[2]aj[2]+1…aj[3]……anBb1…bLbL+1…b2Lb2L+1…b3L……bmCPartition(A,B,n,m){ lm/p; j[0]0; j[p]n; forallPii=1…p-1do j[i]rank(bi*l:A); forallPii=0…p-1do { Bi

(bi*l+1,…,b(i+1)*l); Ai

(aj[i]+1,…,aj[i+1]); }}十四、流水線技術(shù)基本思想將一個(gè)計(jì)算任務(wù)t分成一系列連續(xù)子任務(wù)t1,t2,…,tm，使得一旦完成了子任務(wù)ti，其后繼的子任務(wù)ti+1就可以立即開(kāi)始，并以同樣的速率進(jìn)行計(jì)算。十四、流水線技術(shù)歸并排序設(shè)輸入長(zhǎng)度為n=2r，用p(n)=r+1個(gè)處理器并行完全合并排序的任務(wù)。設(shè)處理器編號(hào)從1到r+1，其中首處理器有一個(gè)輸入，尾處理器有一個(gè)輸出，其他處理器各有兩個(gè)輸入和兩個(gè)輸出。各處理器同步運(yùn)行，在一個(gè)時(shí)間步內(nèi)，P1從原始輸入序列中讀取一個(gè)數(shù)并將其作為結(jié)果輸出，Pi(i=2…r+1)接收從Pi-1輸出的兩個(gè)長(zhǎng)度為2i-2的子序列，并將其合并為一個(gè)長(zhǎng)度為2i-1的子序列。從P1到Pr，每一個(gè)處理器交替地在上面和下面兩條輸出線上產(chǎn)生合并子序列。除P1外，每個(gè)處理器Pi當(dāng)其前一個(gè)處理器的一條輸出線上已經(jīng)產(chǎn)生了長(zhǎng)為2i-2的子序列，另一條輸出線上出現(xiàn)了第一個(gè)元素時(shí)，就可以開(kāi)始?xì)w并了。設(shè)Pi和Pi+1之間通過(guò)的隊(duì)列為q2i和q2i+1，即q2i和q2i+1是Pi的輸出序列，Pi+1的輸入序列。如下圖所示：設(shè)n=2r，p(n)=r+1，算法描述如下：P1:j2;fork=1tondo{ xkq1; qjxk; j=5-j;}Pi:i=2…rj0;k1;whilek<=ndo{ ifq2(i-1)+j已裝滿2i-2個(gè)元素and q2(i-1)+(1-j)已出現(xiàn)1個(gè)元素then { form=1to2i-1do q2i+jmin(q2(i-1)+j,q2(i-1)+(1-j)); j1-j; kk+2i-1; }}Pr+1:ifq2r已裝滿2r-1個(gè)元素，且q2r+1已出現(xiàn)1個(gè)元素then{ form=1to2rdo q2(r+1)min(q2r,q2r+1);}十四、流水線技術(shù)排序問(wèn)題每個(gè)進(jìn)程一次從前一個(gè)進(jìn)程接收待排序序列中的一個(gè)數(shù)，保存當(dāng)前接受到的最大的數(shù)字，把比這個(gè)數(shù)小的其他數(shù)傳給下一個(gè)進(jìn)程。第一個(gè)進(jìn)程P0直接從待排序序列接收數(shù)據(jù)。P0P1P2P3P44|3|1|2|512345P0P1P2P3P4-----4|3|1|2|55----4|3|1|25----4|3|1252---4|3152---431531--42542--315431-254321十四、流水線技術(shù)質(zhì)數(shù)生成問(wèn)題生成從2~n的所有質(zhì)數(shù)。埃拉托色尼篩選法從2開(kāi)始，依次刪除2的所有倍數(shù)；對(duì)余下的每個(gè)數(shù)字重復(fù)這個(gè)過(guò)程；只須考察從2到n1/2的數(shù)即可；對(duì)被考察數(shù)i，只須測(cè)試i2~n的所有數(shù)即可；2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,202,3,5,7,9,11,13,15,17,192,3,5,7,11,13,17,19十四、流水線技術(shù)質(zhì)數(shù)生成問(wèn)題順序解法for(i=2;i<=n;i++) prime[i]=1;for(i=0;i<=sqrt_n;i++) if(prime[i]==1) for(j=i*i;j<=n;j+=i) prime[j]=0;十四、流水線技術(shù)質(zhì)數(shù)生成問(wèn)題流水線解法第一個(gè)流水線級(jí)輸入一系列連續(xù)的數(shù)，然后剔出所有2的倍數(shù)，并把余下的數(shù)傳遞給第二級(jí)流水線；第二級(jí)剔出所有3的倍數(shù)并把余下的數(shù)傳遞給第三級(jí)流水線；以此類推；流水線的個(gè)數(shù)與質(zhì)數(shù)的個(gè)數(shù)的方根相同；P0P1P2xn-1,...,x1,x0數(shù)序列倍數(shù)比較第1個(gè)質(zhì)數(shù)第2個(gè)質(zhì)數(shù)第3個(gè)質(zhì)數(shù)進(jìn)行埃拉托色尼篩選的流水線：P0:x0

receive(X);while(!EOF(X)){ xreceive(X); if(x%x0!=0)send(P1,x);}Pi:xi

receive(Pi-1);while(!EOF(X)){ xreceive(Pi-1); if(x%xi!=0)send(Pi+1,x);}十五、接力技術(shù)基本思想讓兩種算法接力，產(chǎn)生一個(gè)求解該問(wèn)題的新算法，使得既有耗時(shí)少的特性又有工作量有效性較高的特性。先用需要較少時(shí)間（速度較快）的算法求解給定的問(wèn)題，直到問(wèn)題的規(guī)模減到某一個(gè)閾值為止；再用工作量有效性較高的算法，繼續(xù)求解，直到獲得最終的解答。十五、接力技術(shù)求解最大值的常數(shù)時(shí)間算法對(duì)n個(gè)元素的數(shù)組，可以動(dòng)用n2個(gè)處理器，在O(1)的時(shí)間內(nèi)求解出最大值。A1A2A3mA1?F?FA2TTTTA3?F?FforallPii=1…ndo m[i]true;forallPi,ji=1…n,j=1…ndo if(A[i]<A[j])m[i]false;forallPii=1…ndo if(m[i]==true)maxA[i];十五、接力技術(shù)求解最大值的重對(duì)數(shù)時(shí)間算法設(shè)n個(gè)元素的序列，定義一棵以n個(gè)元素為葉結(jié)點(diǎn)的重對(duì)數(shù)深度平衡樹(shù)如下：

樹(shù)中每一個(gè)非葉子結(jié)點(diǎn)u的子結(jié)點(diǎn)的個(gè)數(shù)為以u(píng)為根的子樹(shù)上的葉結(jié)點(diǎn)的個(gè)數(shù)的平方根。則第0層為樹(shù)根，有一個(gè)結(jié)點(diǎn)，第1層為n1/2個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)為根的子樹(shù)上有n/n1/2=n1/2個(gè)葉子，所以每個(gè)結(jié)點(diǎn)有n1/4個(gè)子結(jié)點(diǎn)，可以證明，以第i層上每一個(gè)結(jié)點(diǎn)為根的子樹(shù)上有個(gè)葉子結(jié)點(diǎn)，第i層上共有個(gè)結(jié)點(diǎn)，可知這樣一棵樹(shù)的高度為loglogn+1，因此稱為重對(duì)數(shù)深度平衡樹(shù)。在重對(duì)數(shù)深度平衡樹(shù)上，除第0層外，對(duì)每一層按父結(jié)點(diǎn)分組，對(duì)每一組用常數(shù)時(shí)間算法求解最大值，結(jié)果放在其父結(jié)點(diǎn)中?？勺C明，共須n個(gè)處理器，經(jīng)過(guò)loglogn+1個(gè)并行步完成計(jì)算，時(shí)間復(fù)雜度為O(loglogn)。216個(gè)葉子根28個(gè)結(jié)點(diǎn)，每個(gè)分28個(gè)葉結(jié)點(diǎn)28*24個(gè)結(jié)點(diǎn)，每個(gè)分24個(gè)葉結(jié)點(diǎn)28*24*22個(gè)結(jié)點(diǎn)，每個(gè)分22個(gè)葉結(jié)點(diǎn)28*24*22*2個(gè)結(jié)點(diǎn)，每個(gè)分2個(gè)葉結(jié)點(diǎn)十五、接力技術(shù)對(duì)數(shù)深度樹(shù)和重對(duì)數(shù)深度樹(shù)算法接力第一步，利用對(duì)數(shù)深度平衡樹(shù)方法向上逐層進(jìn)行計(jì)算，經(jīng)過(guò)logloglogn層的選拔后停下來(lái)。第二步，以第一步選拔出的最大值候選結(jié)點(diǎn)為葉結(jié)點(diǎn)，按重對(duì)數(shù)時(shí)間算法進(jìn)行繼續(xù)計(jì)算，直到所求的解。第一步所需時(shí)間為O(logloglogn)，工作量為O(nlogloglogn)，在第一步結(jié)束時(shí)，剩下的結(jié)點(diǎn)數(shù)為：n’=n/2logloglogn=n/loglogn。則第二步需要的時(shí)間為O(loglogn’)=O(loglogn)，工作量為O(n’loglogn)=O(n)。從而進(jìn)一步提高了工作量的有效性。十六、遞歸的并行隨機(jī)消元法基本思想運(yùn)用遞歸，且在遞歸的每一階段用最短的時(shí)間，并隨機(jī)地消去盡量多的元素，以迅速地壓縮問(wèn)題的規(guī)模，直到規(guī)模為0，遞歸不再深入，再返回并逐步拼接原問(wèn)題的解。以前綴計(jì)算為例。十六、遞歸的并行隨機(jī)消元法遞歸消元可以通過(guò)O(1)時(shí)間的操作將一個(gè)單鏈表改造成為一個(gè)雙向鏈表。對(duì)于規(guī)模為n的雙向鏈表，擬使用p個(gè)處理器，每個(gè)處理器負(fù)責(zé)處理鏈中的n/p個(gè)元素。先將n個(gè)元素任意地分配給各處理器，一經(jīng)分配，歸屬關(guān)系在遞歸過(guò)程中不再改變。十六、遞歸的并行隨機(jī)消元法遞歸消元第一步：消元各處理器按如下兩條原則并行地消去表中的一些元素：

①每一個(gè)處理器每次最多消去它所管轄的一個(gè)元素；

②不同時(shí)消去當(dāng)前表中相鄰的兩個(gè)元素。

在消去當(dāng)前表中它所轄的一個(gè)元素之前，都要取出該元素及其下一個(gè)元素的前綴當(dāng)前值作⊕運(yùn)算，并用運(yùn)算的結(jié)果更新下一個(gè)元素的前綴當(dāng)前值，除非是表尾元素。十六、遞歸的并行隨機(jī)消元法遞歸消元第二步：遞歸當(dāng)?shù)谝徊降玫降男骆湵淼拈L(zhǎng)度不為0時(shí)，遞歸消元。第三步：回收各處理器并行地收回在第一步被自己消去的元素，接入遞歸返回的鏈表，然后取出該元素與其前一個(gè)元素的前綴當(dāng)前值作⊕運(yùn)算，并用運(yùn)算的結(jié)果更新該元素的前綴當(dāng)前值，除非是表首元素。PiNovnextP114[4,4]621[1,1]332[2,2]5P247[7,7]853[3,3]165[5,5]9P379[9,9]088[8,8]796[6,6]4[1,1][2,2][3,3][4,4][5,5][6,6][7,7][8,8][9,9][1,1][2,2][3,3][4,5][6,6][7,8][1,2][3,5][6,6][1,5]空表[1,5][1,2][1,5][1,6][1,1][1,2][1,3][1,5][1,6][1,8][1,1][1,2][1,3][1,4][1,5][1,6][1,7][1,8][1,9]P1P1P2P1P2P3P2P3P3十六、遞歸的并行隨機(jī)消元法遞歸消元可見(jiàn)，在遞歸消元過(guò)程中，被消去元的前綴值累積到了后面的元素上；在遞歸返回時(shí)，回收的元素從前面的元素中獲得了尚未被累積的前綴值。因此保證了在遞歸結(jié)束時(shí)，每個(gè)元素都獲得了其前面的所有元素的前綴累積值。并行消元時(shí)的兩條原則保證了消元過(guò)程中不會(huì)出現(xiàn)沖突，且消元和回收都可以在O(1)時(shí)間內(nèi)完成。十六、遞歸的并行隨機(jī)消元法選擇待消元的方法在兩條消元原則下，消去盡量多的元素，且耗費(fèi)時(shí)間盡量少，最好是O(1)。因此可以采用隨機(jī)消元法。方法如下：(1) 各處理器從所分管的元素中挑選一個(gè)未消去的元素作為候選元素；(2) 隨機(jī)地（拋硬幣）決定是否給該元素打一個(gè)標(biāo)記；(3) 如果元素被標(biāo)記，而元素next未標(biāo)記，則消去該元素，否則不消去該元素；十六、遞歸的并行隨機(jī)消元法算法分析在每一個(gè)遞歸步中，每個(gè)處理器以至少1/4的概率消去一個(gè)元素，對(duì)p個(gè)處理器，每個(gè)處理器分管n/p個(gè)元素，因此在高概率下，消元的期望時(shí)間為O(n/p)。則總工作量為O(n)。十七、確定性破對(duì)稱技術(shù)基本概念破對(duì)稱：打破并行操作的對(duì)稱性，即避免兩個(gè)處理器同時(shí)被分派對(duì)同一個(gè)單元進(jìn)行處理或同時(shí)不被分派進(jìn)行處理。前面的隨機(jī)消元中的拋硬幣方法就是一種不確定的破對(duì)稱技術(shù)。確定性破對(duì)稱技術(shù)：利用處理器的編號(hào)來(lái)打破對(duì)稱性。例如前面的例子中，通過(guò)讓下標(biāo)較小的處理器先訪問(wèn)來(lái)打破對(duì)稱性。十七、確定性破對(duì)稱技術(shù)確定性破對(duì)稱算法要求從靜態(tài)鏈表中選出一部分元素，這部分元素在鏈表中兩兩不相鄰，且數(shù)目是鏈表中元素總數(shù)的常分?jǐn)?shù)倍。n個(gè)處理器和O(log*n)的計(jì)算時(shí)間，其中l(wèi)og*n定義為：log*x=min{i|log(i)x<=1,i>=0};log(i)x定義為：對(duì)1≤n≤265536，有0≤log*n≤5，因此對(duì)一般的實(shí)際應(yīng)用，log*n是一個(gè)小常數(shù)。十七、確定性破對(duì)稱技術(shù)確定性破對(duì)稱算法確定性破對(duì)稱算法分為兩個(gè)部分：第一部分：在O(log*n)時(shí)間內(nèi)給出鏈表的“6-著色”。第二部分：將6-著色轉(zhuǎn)化為表的一個(gè)“極大獨(dú)立集”，該極大獨(dú)立集將至少包含鏈表中的n/3個(gè)元素，且這些元素中任何兩個(gè)元素在鏈表中不相鄰。十七、確定性破對(duì)稱技術(shù)無(wú)向圖著色與極大獨(dú)立集無(wú)向圖G=(V,E)的一個(gè)著色是一個(gè)映射Ｃ：ＶＮ，使得對(duì)所有u,v∈Ｖ，如果Ｃ(u)=C(v)，則(u,v)不屬于Ｅ，即相鄰點(diǎn)不同色。在鏈表上進(jìn)行６-著色，可用的顏色號(hào)為{0,1,2,3,4,5}，且相鄰元素不同色。雖然可以用O(logn)的時(shí)間并行地對(duì)鏈表進(jìn)行2-著色，將奇、偶元素分別著以不同的顏色，但通常只要有一種O(1)的著色就可以了。下面的算法在O(log*n)的時(shí)間對(duì)n個(gè)元素的鏈表進(jìn)行6-著色。十七、確定性破對(duì)稱技術(shù)無(wú)向圖著色與極大獨(dú)立集G=(V,E)的一個(gè)獨(dú)立集是其頂點(diǎn)集V的一個(gè)子集V’，使得E中的每條邊最多只與V’中的一個(gè)頂點(diǎn)相關(guān)聯(lián)。極大獨(dú)立集是一個(gè)不能再并入其他任何頂點(diǎn)的獨(dú)立集。最大獨(dú)立集是圖G的一個(gè)規(guī)模最大的獨(dú)立集。求極大獨(dú)立集是一個(gè)易解的問(wèn)題，求最大獨(dú)立集卻是一個(gè)NP-完全問(wèn)題。雖然對(duì)一個(gè)鏈表可以通過(guò)O(logn)時(shí)間分別標(biāo)出奇偶點(diǎn)，從而得到兩個(gè)最大獨(dú)立集，但速度不夠快。而只要我們能求得鏈表的極大獨(dú)立集，則可知極大獨(dú)立集中的元素個(gè)數(shù)不小于n/3（每三個(gè)元素中，至少有一個(gè)元素屬于極大獨(dú)立集）。十七、確定性破對(duì)稱技術(shù)鏈表6-著色算法思想對(duì)鏈表中的每一個(gè)元素迭代地計(jì)算出一個(gè)著色序列C0[x],C1[x],…,Cm[x]。鏈表的初始著色C0是一個(gè)n-著色，每一次迭代產(chǎn)生一種新的著色，最后的著色Cm是一個(gè)6-著色?？梢宰C明，m=log*n。初始著色C0可以定義為C0[x]=P(x)。每一種顏色的編號(hào)可通過(guò)logn個(gè)bit位來(lái)描述。十七、確定性破對(duì)稱技術(shù)鏈表6-著色迭代規(guī)則設(shè)Ck用了r位表示每一種顏色，通過(guò)查看每個(gè)元素的相鄰元素next[x]來(lái)確定新的顏色。設(shè)Ck[x]=a=<ar-1ar-2…a1a0>，

Ck[next[x]]=b=<br-1br-1…b1b0>，Ck[x]≠Ck[next[x]]，

因此必存在一個(gè)最小下標(biāo)i，使得ai≠bi，0≤i≤r-1，

則i可以用logr個(gè)bit位表示。x的新顏色值定義為i與ai的連接，

令Ck+1[x]=<i,ai>=<ilogr-1ilogr-2…i0ai>，若x是表尾，則定義Ck+1[x]=<0,…0a0>。這樣一來(lái)，新顏色的位數(shù)最多為logr+1位。ck[x]:01101101ck[next[x]]:10011001ck+1[x]:0101十七、確定性破對(duì)稱技術(shù)鏈表6-著色迭代規(guī)則證明可以證明，Ck+1仍是一個(gè)合法的著色。對(duì)非表尾元素x，Ck[x]≠Ck[next[x]]，按Ck+1[x]的定義，設(shè)Ck+1[x]=<i,ai>，

Ck+1[next[x]]=<j,bj>，

若i≠j，則Ck+1[x]≠Ck+1[next[x]]；

若i=j，則必有ai≠bj，所以Ck+1[x]≠Ck+1[next[x]]。ck[x]:01101101ck[n