并行計(jì)算作業(yè)參考解答

單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,,*,《,并行計(jì)算,》,作業(yè)參考解答,,,,,5.10,對(duì)圖,5.3,所示的單位權(quán)有向圖，試用布爾鄰接矩陣乘法求出其傳遞閉包。,,A+I=,,,,A,+,=((A+I),2,),2,=(A+I),4,=,,,,A,是一個(gè)大小為,n,的布爾數(shù)組，欲求出最小的下標(biāo),i,且,A[i,],為真，試設(shè)計(jì)一個(gè)常數(shù)時(shí)間的,PRAM-CRCW,并行算法。如果使用,PRAM-CREW,模型，運(yùn)行時(shí)間如何？,,,,n,2,個(gè)處理器,1. copy A[1..n] to B[1..n],//O(1),,2. for i=1 to n par-do  if,B[i,]=true then//O(1),,for j=i+1 to n par-do,B[j,]=false //O(1),endfor,,,endif,,,endfor,,3. for i=1 to n par-do,,if,B[i,]=true then //O(1) return i,,,endif,,,endfor,PRAM-CRCW,下的時(shí)間復(fù)雜度為,:O(4),,PRAM-CREW,下第,2,步,B[i,]=false,不能同時(shí)寫(xiě)，需要,O(n,),的時(shí)間來(lái)寫(xiě),,,,,試用分治策略或劃分技術(shù)設(shè)計(jì)一個(gè)算法求數(shù)組,A[1..n],的最小元素，要求用,O(n/logn,),個(gè)處理器，時(shí)間復(fù)雜度為,O(logn,),。,,1.,采用均勻劃分，每個(gè)處理器分配,logn,個(gè)元素，求出本處理器中的最小元素時(shí)間為：,log(log,n),。共得到,n/logn,個(gè)局部最小元素。,,2.,對(duì),n/logn,個(gè)局部最小元素用平衡二叉樹(shù)的算法求最小值（類(lèi)似算法,6.8,）。時(shí)間為：,log(n,/log n)=log n -,log(log,n),,3.,總的時(shí)間為,log(log,n) +,log(n,/log n) =,log(n,),,題目,11.7,,(a)A,[0],j,=a,0,+a,2,w,n/2,j,+a,4,w,n/2,j·2,+…+a,n-2,w,n/2,j·(n/2-1),A,[1],j,=a,1,+a,3,w,n/2,j,+a,5,w,n/2,j·2,+…+a,n-1,w,n/2,j·(n/2-1),其中,(w,n/2,),n/2,,= 1,B,j,=a,0,+a,1,w,n,j,+a,2,w,n,j·2,+…+a,n-1,w,n,j·(n-1),其中,(,w,n,,),n,,= 1,利用,w,n/2,j,=,,w,n,j·2,,,,w,n,j·(n/2),= -1,可得：,,B,j,=A,[0],j,+w,n,j,A,[1],j,B,j+n/2,=A,[0],j,+w,n,j+n/2,A,[1],j,=A,[0],j,-w,n,j,A,[1],j,,(b) 1.,遞歸策略不同,2.,參數(shù)傳遞,vs,,返回值,3.,步驟（,7,）中的迭代為算法,11.2,的一 半,,(c),,,,謝謝大家！,,課堂練習(xí),,1.,試畫(huà)出基于,Batcher,比較器的雙調(diào)序列（,8,，,6,，,4,，,2,，,0,，,1,，,3,，,5,）的雙調(diào)歸并排序網(wǎng)絡(luò)，并標(biāo)出每個(gè),Batcher,比較器的輸入和輸出數(shù)據(jù)。,,2.,給出矩陣,A,和,B,的,Cannon,矩陣乘法的具體計(jì)算過(guò)程。,,,A= B=,,,,