9.4MIMD共享存儲(chǔ)模型的并行算法(一)異步枚舉排序算法枚舉排序(EnumerationSort)是一種最簡單的排序算法，通常也稱為秩排序(RankSort)。對于基于枚舉比較原理的異步排序算法，為了排序n個(gè)數(shù)的序列S=(x1,x2，...,xn)，算法要生成n個(gè)進(jìn)程。進(jìn)程i(IWiWn)將xi與S中其余元素進(jìn)行比較，并且使用局部變量k及下所有小于xi的元素的數(shù)目。當(dāng)所有的比較都完成時(shí)，就將xi置入排序序列中的k+1的位置上，，因此每個(gè)進(jìn)程都可能彼此獨(dú)立地執(zhí)行，而無通信的要求。令X是存在共享存儲(chǔ)器中長度為n的數(shù)組，開始時(shí)放入被排序的序列，當(dāng)算法結(jié)束時(shí)，結(jié)果置于共享存儲(chǔ)器中的T數(shù)組內(nèi)，變量i,j,k是算法生成的每個(gè)進(jìn)程的局部變量［1。。7］。該并行算法的描述如下：算法9.4.1MIMD-CREW模型上的異步枚舉排序算法輸入：S=(x1,x2,.,xn)置于共享存儲(chǔ)器的X數(shù)組中輸出：已排序的序列置于共享存儲(chǔ)器的T數(shù)組中ENUERSORTTOC\o"1-5"\h\z{for(i=1;i<=n;i++){CreateProcessi;}Processi:k=0;for(j=1;j<=n;j++){if(X(i)>X(j)){k^k+1;}elseif((X(i)==X(j)&&i>j)){k^k+1;}}T(k+1)=X(i);} 在該并行算法中有，由于每個(gè)處理器至多確定數(shù)組X中的「n/p］個(gè)元素的位置，而每確定一個(gè)元素的位置需O(n)時(shí)間，因此對X進(jìn)行排序需「n/p】XO(n)時(shí)間。例9_8設(shè)S=(8,6,6,9,7)，p(n)=2。創(chuàng)建進(jìn)程的過程中，假定由P1生成5個(gè)進(jìn)程，此后所有的進(jìn)程均等待開始。假定使用“先進(jìn)先出”的調(diào)度策略。進(jìn)程1和2分別由P1和P2執(zhí)行，它們同時(shí)計(jì)算元素8和6的次第，然后將其分別置于T數(shù)組的相應(yīng)位置上，如圖9_19(a)所示。欲知下一進(jìn)程有哪一個(gè)處理器啟動(dòng)執(zhí)行，需研究進(jìn)程1和2的執(zhí)行時(shí)間。假定比較操作和賦值操作大致用相同的時(shí)間，當(dāng)執(zhí)行

X(i)>X(j),X(i)=X(j)和i>j以及k=0,k=k+1和T(k+1)=X(i)時(shí)，進(jìn)程1和2分別需要14和17各時(shí)間步，如圖9_19(b)所示。所以進(jìn)程3應(yīng)由P1啟動(dòng)執(zhí)行，之后3個(gè)時(shí)間步P2啟動(dòng)執(zhí)行進(jìn)程4。這兩個(gè)進(jìn)程負(fù)責(zé)將元素6和9分別置于數(shù)組T的相應(yīng)位置上，此時(shí)進(jìn)程3需要18個(gè)時(shí)間步，進(jìn)程4需要13個(gè)時(shí)間步，所以進(jìn)程4比進(jìn)程3早結(jié)束。下一進(jìn)程5由P2啟動(dòng)。之后當(dāng)進(jìn)程3執(zhí)行完后，因無等待的進(jìn)程，所以P1變?yōu)榭臻e。當(dāng)進(jìn)程5執(zhí)行15個(gè)時(shí)間步后，元素7便放到數(shù)組T的相應(yīng)位置上。算法總共需要45個(gè)時(shí)間步。Pi進(jìn)程1 進(jìn)程Pi進(jìn)程1 進(jìn)程3□ 14 32P2進(jìn)程2講程4進(jìn)程50 17 30 45(b)進(jìn)度調(diào)度(a)數(shù)組T(b)進(jìn)度調(diào)度圖9_19異步枚舉排序數(shù)組變化及進(jìn)程調(diào)度(二)單源點(diǎn)最短路徑并行算法假設(shè)一有向圖各邊賦于非負(fù)整數(shù)，某條路徑的長度就是沿該路徑所有邊權(quán)之和。最短路徑問題，就是對每一點(diǎn)對i和j，丘照期間任何最短長度的路徑。單源點(diǎn)最短路徑，即在一個(gè)圖中尋找從一個(gè)指定頂點(diǎn)到所有其他定點(diǎn)的最短路徑。(a)單處理機(jī)上的Moore算法。在Moore算法中，設(shè)源點(diǎn)為s^V。從s到其他各頂點(diǎn)的最短路徑長度用一維數(shù)組dist存儲(chǔ)。首先置dist(s)=0,dist(v)=8，其中v*，且vEV。算法使用了一個(gè)隊(duì)列queue。開始執(zhí)行時(shí)隊(duì)列中僅含有源點(diǎn)s；以后每次只要隊(duì)列非空，就將排頭頂點(diǎn)u從隊(duì)列中移去，令其作為本次搜索的頂點(diǎn)，然后檢查u的所有射出邊(u,v)EE：若dist(u)+w(u,v)<dist(v)，則此時(shí)就找到了一條從s到v的更短路徑，置dist(v)=dist(u)+w(u,v)；若v不再搜索隊(duì)列中，則把v加到隊(duì)尾。如此重復(fù)進(jìn)行，直到整個(gè)待搜索隊(duì)列空時(shí)，算法就終止。算法9?4?2_1SISD機(jī)器上的單源點(diǎn)最短路徑算法輸入：有向加權(quán)圖G(V,E)的權(quán)矩陣輸出：從源s到其余頂點(diǎn)i(i/s)的最短路徑dist(i),iEVSISDSHORTESTPATH{(1)for(i=1;i<=n;i++)/*初始化*/3{INITIALIZE(i);}(2)將s插入隊(duì)列queue中；(3)while(隊(duì)列非空){SEARCH;}8}StatusSEARCH{(3.1)dequeuevertexu;/*從隊(duì)列中刪去頂點(diǎn)u*/(3.2)for(eachedge(u,v)EE)TOC\o"1-5"\h\z{new_dist6dist(u)+w(u,v);if(new_dist<dist(v)){dist(v)6new_dist;}if(visnotinthequeue){enqueuevertexv;}}}StatusINITIALIZE{(1.1)dist(s)60;(1.2)dist(v)。8;(v#s,vEV)(1.3)queue60;}(b)Moore算法的并行化Deo等人基于MIMD緊耦合共享存儲(chǔ)模型實(shí)現(xiàn)了Moore算法的并行化。直觀上講，算法9.4.2_1有兩處可并行化的地方：一是SEARCH的第(3.2)步；二是主算法的第(3)步。前者，任何一個(gè)頂點(diǎn)均可能有多條射出邊，它們都可并行地被檢查；后者，在任何時(shí)候都可能有多個(gè)頂點(diǎn)在隊(duì)列中，因此有可能每次檢查多個(gè)頂點(diǎn)的射出邊。由于后者可產(chǎn)生較大的加速，而且當(dāng)G是個(gè)稀疏圖時(shí)，并行度受定點(diǎn)射出變得影響，所以選用后者。首先，隊(duì)列用源點(diǎn)初始化。然后創(chuàng)建了許多異步進(jìn)程，每個(gè)進(jìn)程都從隊(duì)列中刪除一個(gè)頂點(diǎn)，檢查其射出邊，將已發(fā)現(xiàn)有更短路徑的頂點(diǎn)加入到隊(duì)列。算法的第(1)步采用預(yù)調(diào)度方法很容易并行化。而第(3)步的while循環(huán)需作適當(dāng)?shù)男薷模阅芊从巢?zhí)行SEARCH過程時(shí)一些異步進(jìn)程的存在。顯然，當(dāng)一個(gè)進(jìn)程發(fā)現(xiàn)隊(duì)列為空時(shí)，就停止執(zhí)行是不合適的。因而必須采用兩個(gè)變量聯(lián)合使用的辦法，以決定什么時(shí)候無工作可做：第一個(gè)是數(shù)組變量waiting，它記住哪一個(gè)進(jìn)程正處于等待狀態(tài)；第二個(gè)是布爾變量halt，僅當(dāng)隊(duì)列為空和所有進(jìn)程處于等待狀態(tài)時(shí)為真。INITIALIZE過程置數(shù)組waiting中的第一個(gè)元素為假。SEARCH過程也必須作適當(dāng)?shù)男薷摹Ｒ驗(yàn)殛?duì)列的插入、刪除操作不是原子操作，所以執(zhí)行上述操作時(shí)必須給隊(duì)列上鎖：其次，在一個(gè)進(jìn)程將剛找到的v路徑new_dist與當(dāng)前的最短路徑dist(v)比較之前，變量dist(v)也必須上鎖，否則兩個(gè)進(jìn)程有可能同時(shí)修改它；最后，若一個(gè)進(jìn)程發(fā)現(xiàn)隊(duì)列為空時(shí)，則Swaiting中的相應(yīng)元素為真。若進(jìn)程1處于等待狀態(tài)，則它要檢查每個(gè)進(jìn)程是否都處在等待狀態(tài)，如果是，則halt置為真，而進(jìn)程1檢查每個(gè)進(jìn)程是否處于等待狀態(tài)時(shí)，隊(duì)列也必須上鎖。該并行算法的描述如下：算法9.4.2MIMD-SM模型上單源點(diǎn)最短路徑算法

1234567891011121314151617181920212223242526272829303132333435363738394041輸入：有向加權(quán)圖G的權(quán)矩陣W輸出：從源s到其余頂點(diǎn)i(iNs)的最短路徑dist(i),iEVMIMDSHORTESTPATH{parfor(i=1;i<=p;i++)/*p為進(jìn)程數(shù)*/{for(j=i;j<=n;j=j+p)/*初始化*/{INITIALIZE(j);}}enqueues;/*s入隊(duì)*/halt=FALSE;parfor(i=1;i<=p;i++){while(nothalt){SEARCH(i);}}}StatusSEARCH(i){lockthequeue;/*隊(duì)列上鎖*/if(queueisempty)/*隊(duì)列空時(shí)，等待進(jìn)程為真*/{waiting(i)6TRUE;if(i==1)/*進(jìn)程1等待時(shí)，其它進(jìn)程均須等待*/{halt=waiting(2)八waiting(3)八???八waiting(p);}unlockthequeue;/*隊(duì)列開鎖*/}else{dequeueu;/*從隊(duì)列中刪除u*/waiting(i)6FALSE;unlockthequeue;/*隊(duì)列開鎖*/for(everyedge(u,v)inGraph)/*檢查每條射出邊*/{new_dist。dist(u)+w(u,v);lock(dist(v))/*dist(v)上鎖*/if(new_dist<dist(v)){

42dist(v)6new_dist;/*更新new_dist*/43unlock(dist(v));/*dist(v)開鎖*/44if(v史queue)45{46lockthequeue;/*隊(duì)列上鎖*/47enqueuev;/*v入隊(duì)*/48unlockthequeue;/*隊(duì)列開鎖*/49}50}51else{unlock(dist(v));}/*dist(v)開鎖*/52}53 }54}(二)最小生成樹并行算法一個(gè)無向連通圖G的生成樹是指滿足如下條件的G的子圖T：G和T具有相同的頂點(diǎn)數(shù)；在T中有足夠的邊能連接G所有的頂點(diǎn)，但不出現(xiàn)回路。最小生成樹，即最小代價(jià)生成樹(MinimumCostSpanningTree)，它是加權(quán)連通無向圖的所有生成樹中權(quán)值最小的生成樹。(a)Sollin順序求MST算法算法開始時(shí)，圖的n個(gè)孤立頂點(diǎn)視為一片森林，而每個(gè)頂點(diǎn)均視為一棵樹；算法共迭代logn次，每次迭代時(shí)，森林中的每棵樹，同時(shí)決定其最小的鄰邊，并將它們加入到森林中(即合并各棵樹)；此過程重復(fù)到森林中只剩下一棵樹。因?yàn)樯种袠涞臄?shù)目，每次都以2的倍數(shù)減少，所以迭代至多需要hogn】次就可找到MST；而每次迭代時(shí)，找頂點(diǎn)的最小鄰邊至多執(zhí)行O(n2)次比較。因此Sollin的順序算法的復(fù)雜度為O(n2logn)。函數(shù)FIND(v)找頂點(diǎn)v所在的樹的名字，UNION(v,u)合并包括頂點(diǎn)v和u的兩棵樹。算法9?4?3_1SISD機(jī)器上的SollinMST算法輸入：無向圖G的加權(quán)矩陣W輸出：G的最小生成樹T(樹以邊的形式存儲(chǔ))SOLLIN-MSTTOC\o"1-5"\h\z{(1)for(i=1;i<=n;i++)/*初始化*/{vertexiisinitiallyinseti;}(2)T60;/*T就是MST*/

7(3)while(|T|<n-1)8{9(3.1)for(eachtreei)/*每棵樹i找不在同一樹中的最小邊權(quán)*/10{11closest(i)<8;12}13(3.2)for(each(v,u)EE)14{15if(FIND(v)^FIND(u))/*v和u屬于不同的連通片*/16{17if(w(v,u)<closest(FIND(v)))18{19closest(FIND(v))6w(v,u);20edge(FIND(v))<(v,u);21}22}23}24(3.3)for(eachtreei)25{26(3.3.1)(v,u)^edge(i);27(3.3.2)if(FIND(v)豐FIND(u))28{29(3.3.2.1)T6TU{(v,u)};/*加入新的樹邊*/30(3.3.2.2)UNION(v,u);/*合并成較大的樹*/31}32}33}34}(b)Quinn的并行化算法在共享存儲(chǔ)的MIMD機(jī)系統(tǒng)上，Sollin算法可按如下思路并行化：首先，應(yīng)設(shè)法對第(3)步while循環(huán)進(jìn)行并行化，但遺憾的是因循環(huán)之間存在著先后制約關(guān)系，即在第k+1次循環(huán)之前，第k次循環(huán)的子樹必須同一個(gè)有最小權(quán)值的邊關(guān)聯(lián)的另一棵子樹歸并，所以while語句的并行化是有限的。其次，考慮循環(huán)體內(nèi)的并行化。算法的第(3.1)步通過適當(dāng)?shù)念A(yù)調(diào)度可以使其并行化，設(shè)第t次循環(huán)時(shí)已有nt棵子樹:若nt>p，則把nt棵子樹較均勻的分配到p個(gè)處理器中，每個(gè)處理器約有［nt/p〕棵子樹；否則，這nt棵子樹就分配給nt個(gè)處理器。算法的第(3.2)步并行化的最有效做法是：首先，每個(gè)處理器檢查它內(nèi)部的頂點(diǎn)的邊，然后再檢查不在同一處理器上樹之間的邊。算法的第(3.3)步并行化稍微復(fù)雜些。圖9_20示出了此情況，假定一個(gè)處理器企圖將樹B與其最近的樹A進(jìn)行歸并，變量edge(A)有一條權(quán)值為k的邊(vA,uA)，變量edge(B)也有一條權(quán)值為k的邊(vB,uB)。然而假定兩處理器都在實(shí)行UNION之前執(zhí)行了第(ii)步的測試，則(vA,uA)和(vB,uB)都將加入到樹T中，結(jié)果形成一個(gè)環(huán)，顯然這是錯(cuò)的。因此，欲使第3.3)步并行化，必須在執(zhí)行第(3.3.2)步之前上鎖，執(zhí)行完第(3.3.2.2)步后再開鎖。每次僅允許一個(gè)處理器進(jìn)入臨界區(qū)。為了避免死鎖的產(chǎn)生，當(dāng)有多個(gè)請求上鎖的進(jìn)程申請臨界區(qū)時(shí)，僅僅讓標(biāo)號最小的子樹上鎖。在MIMD-SM模型上，所法所需的時(shí)間為~匚 l.n算法9?4?4MIMD-CREW模型上的算法9?4?4MIMD-CREW模型上的Gauss-Seidel算法輸入：AnXn，向量b，初值x0(i=1,...,n)，精度c(0<c<1)輸出：滿足精度要求的x的近似解GUASS-SEIDEL { for(i=1;i<=n;i++)3{O(logn(一+—+n+p))，處理器數(shù)為O(p)[ioo7]。PP樹A 樹B圖9_20并行化Sollin算法所引起的復(fù)雜情況i.Gauss-Seidel算法Gauss-Seidel算法是求解Ax=b的一種算法。先將系數(shù)矩陣A分解為A=E+D+F，其中D、E和F均為nXn的矩陣，它們的元素分別定義如下：d」％,eW卜jf<jij[0,否則，j[0,否則j[0,否則這樣，Ax=(D+E+F)x=b，從而Dx=b-Ex-Fx。給定初始值x0，則第k次迭代為Dxk=b-Exk-Fxk-1對于某一k和給定的誤差允許值c，如果下式成立，則認(rèn)為迭代時(shí)收斂的。/|xk+1一Xk|<Ci=1Gauss-Seidel異步并行算法，設(shè)有N個(gè)處理器(NWn)，算法生成n個(gè)進(jìn)程，每一個(gè)進(jìn)程計(jì)算x的一個(gè)分量。這些進(jìn)程由N個(gè)處理器異步的執(zhí)行。令x0代表初值，Iold；代表舊值，new；代表當(dāng)前值，c為精度[1007]。該并行算法的描述如下：old￡xo；7CreateProcessi;/*生成i個(gè)進(jìn)程*/8}9Processi:10do11{old.<new.;ii12睥可￡嘗歸外"d)f(⑶k=1 k=i+113}while(!(81new-old.\<c))14=115xi^newi;}6new￡氣。;xoldk))?例9_9使用算法9.4.4求解下述方程：|2x1+x2=3"1+2x2=4設(shè)有2個(gè)處理器(N=2)，取初值x0=1/2,x0=3/2,c=0.02。設(shè)置old]=1/2,neW]=1/2，生成進(jìn)程processl；設(shè)置old2=3/2,new2=3/2，生成進(jìn)程process2。process1：設(shè)置old1=1/2；計(jì)算new1=(1/2)(3-3/2)=3/4；process2：設(shè)置old2=3/2；計(jì)算new2=(1/2)(4-1/2)=7/4o重復(fù)計(jì)算如下：new1=5/8, new2=13/8；new1=11/16,new2=27/16；new1=21/32,new2=53/32；new1=43/64,new2=107/64；new1=85/128,new2=213/128o因?yàn)閨43/64-85/128|+|107/64-213/128|<0.02,所以迭代結(jié)束。牛頓求根并行算法牛頓求根法，設(shè)f(x)在(a,b)上連續(xù)，且f’(x)N0,f”(x)N0,f(a)?f(b)<0,則方程f(x)=0的根z的近似值可用如下迭代公式計(jì)算，直到誤差|xn+1-xn|<c，其中c為給定的精度： nxn+1=xn-f(xn)/f’(xn)并取初始值如下：枷,當(dāng)廣3)<0X=< 0lb,當(dāng)廣⑴>0牛頓方法的幾何解釋如圖9_21所示(假定f”(x)>0)。下一次迭代值xn+1就是曲線f(x)在xn處的切線與x軸的交點(diǎn)。MIMD機(jī)器上的牛頓求根算法，將包含f(x)的零點(diǎn)z的區(qū)間(a,b)(設(shè)a<b)劃分成N+1等分(NN2)。各分點(diǎn)取為z的近似值。計(jì)算由N個(gè)進(jìn)程組成，每一進(jìn)程開始用各分點(diǎn)值進(jìn)行牛頓法求根。各進(jìn)程并發(fā)異步的執(zhí)行。一旦某一進(jìn)程收斂，它就向共享存儲(chǔ)單元ROOT寫它所求得的值。開始時(shí)根ROOT被置成8,一旦ROOT值被某一進(jìn)程修改，所有進(jìn)程將隨之結(jié)束。如果兩個(gè)進(jìn)程同時(shí)收斂，就會(huì)造成寫沖突，于是按最小號碼的進(jìn)程優(yōu)先的策略來裁決，其它進(jìn)程都被拒絕。如果在預(yù)定的迭代數(shù)目r之內(nèi)某一進(jìn)程不收斂，則它就被掛起［1007］。該并行算法的描述如下: 算法9.4.5MIMD-CREW模型上的牛頓求根算法輸入：f(x)，f’(x)，(a,b)，精度c，最大容許迭代次數(shù)r輸出：返回答案在ROOT中ROOTs((b-a)/(N+1);for(k=1;k<=N;k++){createprocessk;/*生成進(jìn)程*/}ROOT。8;Processk:xold(a+ks;iteration。0;while(iteration<r&&ROOT==8){iteration++;xnew。xoldfgl/政1xnew-xold3{17ROOT。x;new18}19x,,6x ;old new20}21}在牛頓求根并行算法中，令N為可用處理器數(shù)，如果N足夠大，則有一個(gè)起始點(diǎn)可充分接近z。如果f(x),f’(x),f”(x)在區(qū)間(a,b)內(nèi)連續(xù)有界，那么其中有一個(gè)處理器將會(huì)在O(logm)時(shí)間內(nèi)收斂，其中m為所希望的精度的位數(shù)。例9_10令f(x)=x3-4x-5。因此f’(x)=3x2-4。在區(qū)間(-3,3)存在著f(x)的零點(diǎn)，令N=5,區(qū)間被6等分，各分點(diǎn)的值依次為-2,-1,0,1,2。算法生成5個(gè)進(jìn)程，令e=9-10，假定5個(gè)處理器同時(shí)執(zhí)行5個(gè)進(jìn)程。在此情況下，進(jìn)程5最先收斂到根，其值ROOT=2.456678。b)MIMD異步通信模型的并行算法i.快速排序并行算法快速排序(QuickSort)是一種最基本的排序算法，它的基本思想是，在當(dāng)前無序序列R[1,n]中取一個(gè)記錄作為比較的基準(zhǔn)，用此基準(zhǔn)將當(dāng)前的無序序列R[1,n]劃分成兩個(gè)無序序列R[1,i-1]和R[i,n](1WiWn)，且R[1,i-1]中記錄的所有關(guān)鍵字均小于等于基準(zhǔn)的關(guān)鍵字，R[i,n]中記錄的所有關(guān)鍵字均大于等于基準(zhǔn)的關(guān)鍵字；當(dāng)R[1,i-1]和R[i,n]非空時(shí)，分別對他們重復(fù)上述的劃分過程。對每次劃分過后所得到的兩個(gè)序列分別使用兩個(gè)處理器完成遞歸排序。例如對一個(gè)長為n的序列，首先劃分得到兩個(gè)長為n/2的序列，將其交給兩個(gè)處理器分別處理；而后進(jìn)一步劃分得到4個(gè)長為n/4的序列，在分別交給4個(gè)處理器處理；如此遞歸下去最終得到排序號的序列[1001]。該并行算法的描述如下: 算法9?5?1快速排序并行算法輸入：無序數(shù)組data[1,n]，使用的處理器個(gè)數(shù)2m輸出：有序數(shù)組data[1,n]SORT{para_quicksort(data,1,n,m,0);}para_quicksort(data,i,j,m,id)4{5 if((j-i)Wk||m==0)6{Pid:quicksort(data,i,j);8}else{Pid:r=partition(data,i,j);Pidsenddata[r+q,m-1]toPid+2m-1para_quicksort(data,I,r-1,m-1,id);paraquicksort(data,r+1,j,m-1,id+2m-1);P，d+2m-Senddata[r+1,m-1]toP，d；} 算法9?5?算法9?5?2矩陣轉(zhuǎn)置并行算法輸入：矩陣A*nxn輸出：矩陣Anxn的轉(zhuǎn)置矩陣ATnxnTRANSPOSEDMATRIX {/*對所有處理器my_rank(my_rank=0,...,p-1)*/v(my_rank/sqrt(p);/*計(jì)算子塊的行號*/u(my_rankmodsqrt(p);/*計(jì)算子塊的列號*/if(u<v)/*對存放下三角塊的處理器*/6{send所存的子塊to其對角塊所在的處理器；receive其對角塊所在的處理器中發(fā)來的子塊；}}在最優(yōu)的情況下該并行算法形成一個(gè)高度為logn的排序樹，其計(jì)算復(fù)雜度為O(n),通信復(fù)雜度為O(n)；在最壞情況下其計(jì)算復(fù)雜度降為O(n2)；正常情況下該算法的計(jì)算復(fù)雜度為O(n)。ii. 二維網(wǎng)孔上的矩陣轉(zhuǎn)置并行算法網(wǎng)孔上的矩陣轉(zhuǎn)置并行算法思路是，實(shí)現(xiàn)矩陣轉(zhuǎn)置時(shí)，若處理器個(gè)數(shù)為p,且它們的編號依次是0,1,...,p-1,則將n階矩陣A分成p個(gè)大小為mXm的子塊，m=「n/p〕。p個(gè)字塊組成一個(gè).￡FXv-7的子塊陣列。記其中第i行第j列的子塊為Aj它含有A的第(i-1)m+1至第im行中的第(j-1)m+1至第jm列的所有元素。對每一處理器按行主方式賦以二維下標(biāo)，記編號為i的處理器的而為下標(biāo)為(v,u)，其中v=￡jp」u=imodjp，將A的子塊存入下標(biāo)為(v,u)表示的對應(yīng)處理器中。這樣，轉(zhuǎn)置過程分兩步進(jìn)行：第一步，子塊轉(zhuǎn)置，具體過程如圖9_22所示；第二步，處理器內(nèi)部局部轉(zhuǎn)置。圖9_22子塊轉(zhuǎn)置為了避免對應(yīng)子塊交換數(shù)據(jù)時(shí)處理器發(fā)生死鎖，可令下三角子塊先向與之對應(yīng)的上三角子塊發(fā)送數(shù)據(jù)，然后從上三角子塊接收數(shù)據(jù)；上三角子塊先將數(shù)據(jù)存放在緩沖區(qū)buffer中，然后從與之對應(yīng)的下三角子塊接收數(shù)據(jù)；最后再將緩沖區(qū)中的數(shù)據(jù)發(fā)送給下三角子塊[1001]。該并行算法的描述如下：else/*對存放上三角塊的處理器*/TOC\o"1-5"\h\z{將所存的子塊在緩沖區(qū)buffer中做備份；receive其對角塊所在的處理器中發(fā)來的子塊；sendbuffer中所存子塊to其對角塊所在的處理器；}for(i=1;i<=m;i++) /*處理器內(nèi)部局部轉(zhuǎn)置*/{for(j=1;j<=i;j++){交換a[i,j]和a[j,i];}}}若記ts為發(fā)送啟動(dòng)時(shí)間，tw為單位數(shù)據(jù)傳輸時(shí)間，th為處理器間的延遲時(shí)間，則第一步由于每個(gè)子塊有n2/p"個(gè)元素，又由于通信過程中為了避免死鎖，錯(cuò)開下三角子塊與上三角子塊的發(fā)送順序，因此子塊的交換時(shí)間為n2 n22-+2tA；P+n2 n22-+2tA；P+2八丁+《\：p。2p p部轉(zhuǎn)置時(shí)間為n2/2p。因此所需的并行計(jì)算時(shí)間7p=矩陣并行分塊乘法算法矩陣并行分塊乘法的基本思想：將矩陣A按行劃分為p塊(p為處理器個(gè)數(shù))，設(shè)u=「m/p】，每塊含有連續(xù)的u行向量，這些行塊依次記為A。,％...▲-]，分別存放在標(biāo)號為0,1,...,p-1的處理器中。對矩陣B按列劃分為p塊，記v=k/p，每塊含有連續(xù)的v列向量，這些列塊依次記為B0,B],...,Bp1，分別存放在標(biāo)號為0,1,...,p-1的處理器中。將結(jié)果矩陣C也相應(yīng)的同時(shí)進(jìn)行行、列劃分，得到pXp個(gè)大小為uXv的子矩陣，記第i行第j列的子矩陣為C”則有C^AiXBj，其中Ai大小為uXn，Bj大小為nXv。開始，各處理器的存儲(chǔ)內(nèi)容如圖9_23(a)所示。此時(shí)各處理器并行計(jì)算C廠A|XB|，其中i,j=0,1,...,p-1，此后第i號處理器將所存儲(chǔ)的B的列塊送至第i-1號處理器(第0號處理器將B的列塊送至第p-1號處理器中，形成循環(huán)傳送)，各處理器中存儲(chǔ)內(nèi)容如圖9_23(b)所示。它們再次并行計(jì)算Cij.=AiXBj，這里j=(i+1)modp。B的列塊在處理器中以這樣的方式循環(huán)傳送p-1次，并做p次子矩陣相乘運(yùn)算，就生成了矩陣C的所有子矩陣。編號為i的處理器的內(nèi)部存儲(chǔ)器存有子矩陣Ci0,Ci1,.,Ci(p1)O為了避免在通信過程中發(fā)生死鎖，奇數(shù)號及偶數(shù)號處理器的收發(fā)順序被錯(cuò)開，使偶數(shù)號處理器先發(fā)送后接收；而奇數(shù)號處理器先將B的列塊存于緩沖區(qū)buffer中，然后接受編號在其后面的處理器所發(fā)送的B的列塊，最后再將緩沖區(qū)的原矩陣B的列塊發(fā)送給編號在其前面的處理器"01】。該并行算法的描述如下：——處理器編號 存儲(chǔ)器內(nèi)容處理器編號 存儲(chǔ)器內(nèi)容121F12345678910111213141516171819202122232425262728(a) (b)圖9_23矩陣相乘并行算法中的數(shù)據(jù)交換算法9?5?3矩陣并行分塊乘法算法輸入：矩陣AZBnXk輸出：矩陣C燈mXkBLOCK-MATRIXMUTIPLICATION{/*對所有處理器my_rank(my_rank=0,…,p-1)*/K(i+my_rank)%p;/*計(jì)算C的子塊號*/for(z=0;z<=u-1;z++){c[l,z,j](0；for(j=0;j<=v-1;j++){c[l,z,j](c[l,z,j]+a[z,s]*b[s,j];}}mm1((p+my_rank-1)%p;/*計(jì)算左鄰處理器的標(biāo)號*/mm1((my_rank+1)%p;/*計(jì)算右鄰處理器的標(biāo)號*/if(iJp-1){if(my_rank%2==0)/*編號為偶數(shù)的處理器*/{將所存的B的子塊發(fā)送到其左鄰處理器中接收其右鄰處理器中發(fā)來的B的子塊}if(my_rank%2/0)/*編號為奇數(shù)的處理器*/{將所存的B子塊在緩沖區(qū)buffer中做備份；receive其右鄰處理器中發(fā)來的B的子塊；sendbuffer中所存的B的子塊to其左鄰處理器;}}}矩陣并行分塊乘法中，設(shè)一次乘法和加法運(yùn)算時(shí)間為一個(gè)單位時(shí)間，由于每個(gè)處理器計(jì)算p個(gè)uXn與nXv階的子矩陣相乘，因此計(jì)算時(shí)間為uXnXvXp；所有處理器交換數(shù)據(jù)p-1次，每次的通信量為vXn，通信過程中為了避免死鎖，錯(cuò)開奇數(shù)號及偶數(shù)號處理器的收發(fā)順序，通信時(shí)間為2(p-1)(ts+nvtw)=O(nk)，所以并

行計(jì)算時(shí)間T=uvnp+2(p-1)(t+nvt)=mnk/p+2(p-1)(t+nvt)。PJ. '?A /'e wt^ A '?A /'e wt^sw sw分布式矩陣求逆的并行算法矩陣求逆的并行算法的基本思想：在矩陣求逆的過程中，一次利用主行i(i=0,1,...,n-1)對其余各行j(j^i)作初等變換，由于各行計(jì)算之間沒有數(shù)據(jù)相關(guān)關(guān)系，因此對矩陣A按行劃分來實(shí)現(xiàn)并行計(jì)算。考慮到在計(jì)算過程中處理器之間的負(fù)載均衡，對A采用行交叉劃分:設(shè)處理器個(gè)數(shù)為p,矩陣A的階數(shù)為n,m=「n/p】，對矩陣A行交叉劃分后，編號為i(i=0,1,...,p-1)的處理器存有A的第i,i+p,...,i+(m-1)p行。在計(jì)算中，依次將第0,1,...,n-1行作為主行，將其廣播給所有處理器，這實(shí)際上是各處理器輪流選出主行并廣播。發(fā)送主行數(shù)據(jù)的處理器利用主行對其主行之外的m-1行行向量做行變換，其余處理器則利用主行對其m行行向量做行變換［1001］。該并行算法的描述如下：算法9?5?4矩陣求逆并行算法輸入：矩陣A*nxn輸出：矩陣A-1nxnINVERSEMATRIX1{2/*對所有處理器my_rank(my_rank=0,...,p-1)*/3for(i=0;i<=m-1;i++)4{5for(j=0;j<=p-1;j++)6{7if(my_rank=j)/*主兀素在本處理器中*/89{v6i*p+j;/*v為王兀素的行號*/10a[i,v]61/a[i,v];11for(k=0;k<=n-1;k++)12{13if(k^v)14{15a[i,k]6a[i,k]*a[i,v];16}17}18for(k=0;k<=n-1;k++)19{20f[k]6a[i,k];21}2223broadcast變換后的主彳丁兀素(存于數(shù)組f中)to所有處理器:■ 3、?-1-7-^ J..LI-rmRDr-l-r“/else/*主兀素不在本處理器中*/2425{v6i*p+j;/*v為主兀素行號*/26reveive主彳丁兀素存于數(shù)組中；27}

282930313233343536373839404142434445464748495051525354555657585960616263646566676869 }70 }if(my_rank勺)/*主行元素不在本處理器中*/{for(k=0;k<=m-1;k++)/*處理非主行、非主列元素*/{for(w=0;w<=n-1;w++){if(w^v){a[k,w]<a[k,w]-f[w]*a[k,v];}}}for(k=0;k<=m-1;k++)/*處理主行元素*/{a[k,v]<-f[v]*a[k,v];}}else/*處理主行所在處理器中的其它元素*/{for(k=0;k<=m-1;k++){if(k^i){for(w=0;w<=n-1;w++){if(w^v){a[k,w]<a[k,w]-f[w]*a[k,v];}}}}for(k=0;k<=m-1;k++){if(k^i){a[k,v]6-f[v]*a[k,v];}}}}矩陣求逆的并行算法中，若一次乘法和加法運(yùn)算或一次除法運(yùn)算時(shí)間為一個(gè)單

位時(shí)間，則所需的計(jì)算時(shí)間為mn2；又由于共有n行數(shù)據(jù)依次作為主行被廣播，其通信時(shí)間為n(t+nt)logp，所以該算法并行計(jì)算時(shí)間為T=mn2+n(t+nt)logp。SW p sw分布式高斯消去并行算法高斯消去法是利用主行i對其余各行j(j>i)，作初等變換，各行計(jì)算之間沒有數(shù)據(jù)相關(guān)關(guān)系，因此可以對矩陣A按行劃分。考慮到在計(jì)算過程中處理器之間的負(fù)載均衡，對A采用行交叉劃分。設(shè)處理器個(gè)數(shù)為p，矩陣A的階數(shù)為n,m=「n/p】，對矩陣A行交叉劃分后，編號為i(i=0,1,...,p-1)的處理器含有A的第i,i+p,...,i+(m-1)p行和向量B的第i,i+p,...,i+(m-1)p一共m個(gè)元素。消去過程的并行是依次以第0,1,...n-1行為主行進(jìn)行消去計(jì)算，由于對行的交叉劃分與分布，這實(shí)際上是由各處理器輪流選出主行。在每次消去計(jì)算前，各處理器并行求其局部存儲(chǔ)器中右下角子陣的最大元。若以編號為my_rank的處理器的第i行作為主行，則編號在my_rank后面的處理器(包括my_rank本身)求其局部存儲(chǔ)器中第i行至第m-1行元素的最大元，并記錄其行號、列號及所在處理器編號；編號在my_rank前面的處理器求其局部存儲(chǔ)器中第i+1行至第m-1行元素的最大元，并記錄其行號、列號及所在處理器編號。然后通過擴(kuò)展收集操作，將局部存儲(chǔ)器中最大元按處理器編號連接起來，并廣播給所有處理器，各處理器以此求得整個(gè)矩陣右下角階子陣的最大元maxvalue及其所在行號、列號和處理器編號。若maxvalue的列號不是原主元素akk的列號，則交換第k列與maxvalue所在列的兩列數(shù)據(jù)；若maxvalue的處理器編號不是原主元素a^的處理器編號，則在處理期間的進(jìn)行行交換;若maxvalue的處理器編號是原主元素a^的處理器編號，但行號不是原主元素a^的行號，則在處理其內(nèi)部進(jìn)行行交換。在消去計(jì)算中，首先對主行元素作歸一化 操作akj=akj/akk，然后將主行廣播給所有處理器，各處理器利用接收到的主行元素對其部分行向量做行變換。若以編號為my_rank的處理器的第i行作為主行，并將它播送給所有的處理器。則編號在my_rank前面的處理器(包括my_rank)本身利用主行對其第i+1,...,m-1行數(shù)據(jù)和子向量B做行變換。編號在my_rank后面的處理器利用主行對其第i,...,m-1行數(shù)據(jù)和子向量B做行變換。回代過程的并行是按xn,xn-1,.x1的順序由各處理器依次計(jì)算x(i*p+myrank)，一旦x(i*p+myrank)被計(jì)算出來就立即廣播給所有處理器，用于與對應(yīng)項(xiàng)相乘并作求和計(jì)算I*：。該并行算法的描述如下：算法9?5?5全主元高斯消去法過程的并行算法輸入：系數(shù)矩陣Anxn，常數(shù)向量bnx1輸出：解向量xnx1GAUSSELIMINATIONTOC\o"1-5"\h\z{/*對所有處理器my_rank(my_rank=0,...,p-1)*//*消去過程*/for(i=0;i<=m-1;i++){for(j=0;j<=p-1;j++){if(my_rank<j)/*對于主行后面的塊*/{vi*p+j;/*v為主元素的行號*/

1112131415161718192021222324252627282930313233343536373839404142434445464748495051525354/*確定本處理器所存未消元部分的最大元及其位置，存于數(shù)組lmax中*/lmax[0]6a[i+1,v];for(k=i+1;k<=m-1;k++){for(t=v;t<=n-1;t++){if(|a[k,t]|>lmax[0]){lmax[0]6a[k,t];lmax[1]6k;lmax⑵6t;lmax[3]6my_rank;}}}}if(my_rankNj)/*對于主行后面的塊*/{v6i*p+j;/*v為主元素的行號*//*確定本處理器所存未消元部分的最大元及其位置，存于數(shù)組lmax中*/lmax[0]6a[i,v];for(k=i;k<=m-1;k++){for(t=v;t<=n-1;t++){if(|a[k,t]|>lmax[0]){lmax[0]6a[k,t];lmax[1]6k;lmax⑵6t;lmax[3]6my_ran;}}}}broadcast處理器中的lmax元素to其他所有處理器；/*確定最大元及其位置*/maxvalue6getpivort(max);maxrow6getrow(max);maxcolumn6getcolumn(max);maxrank6getrank(max);/*列交換*/

if(maxcolumn#v){for(t=0;t<=m;t++){交換a[t,v]與a[t,maxcolumn];}交換shift[v]與shift[maxcolumn];}/*行交換*/if(my_rank=j){if(maxcolumn#a[i,v]){if((maxrank==j)&&(i#maxrow)){innerexchangerow();/*處理器內(nèi)部換行*/}if(maxrank#j){outerexchangerow();/*處理器之間換行*/}}}if(maxrank#j)/*主行所在的處理器*//*對主行作歸一化運(yùn)算*/{for(k=v+1;k<=n-1;k++){a[i,k]6a[i,k]/a[i,v];}b[i]6b[i]/a[i,v];a[i,v]J;/*將主行元素賦于數(shù)組f*/for(k=v+1;k<=n-1;k++){f[k]6a[i,k];}f[n]6b[i];broadcast主行to所有處理器；}else/*非主行所在的處理器*/{receive主行元素存于數(shù)組f中；5556575859606162636465666768697071727374757677787980818283848586878889909192939495969798}99100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142if(my_rankWj){for(k=i+1;k<=m-1;k++){for(w=v+1;w<=n-1;w++){a[k,w]<a[k,w]-f[w]*a[k,v];}b[k]<b[k]-f[n]*a[k,v];}}if(my_rank>j){f