資源描述:
《共享存儲(chǔ)模型的并行算法.doc》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、9.2SIMD共享存儲(chǔ)模型的并行算法(一)播送算法基本思想:為解決N個(gè)處理器同時(shí)讀取共享存儲(chǔ)器中的數(shù)據(jù)m在SIMD-EREW機(jī)上引起的讀沖突,可以使用一個(gè)長(zhǎng)度為N的共享數(shù)組B(開始時(shí)為空,且用B(i)表示B的第i個(gè)位置),每個(gè)處理器在讀取數(shù)據(jù)m的同時(shí)向B的后繼單元寫入,通過(guò)延長(zhǎng)B來(lái)增加下次讀取的并行度,當(dāng)算法結(jié)束時(shí)所有的N個(gè)處理器都接受到了數(shù)據(jù)m。具體步驟:(1)由處理器P1把m寫入B[1];(2)由處理器P1把B[1]寫入B[2];由P1,P2把B[1],B[2]并行寫入B[3],B[4]中;…;由P1,P2,…,Pi把B[1],B[2],…,B[i]并行
2、寫入B[i+1],B[i+2],…,B[2i]中;…;由P1,P2,…,PN/2把B[1],B[2],…,B[N/2]并行寫入B[N/2+1],B[N/2+2],…,B[N]中;(3)處理器Pi(i=1,…,N)從B[i]中并行讀取數(shù)據(jù)m。并行算法:12345678910算法9.2.1播送算法輸入:共享存儲(chǔ)器中數(shù)據(jù)m,N個(gè)處理器,共享數(shù)組B輸出:所有的N個(gè)處理器都接受到數(shù)據(jù)mBROADCAST(m,N,B){處理器P1將m復(fù)制到存儲(chǔ)器中;處理器P1將m寫入B[1];for(i=0;i<=logN-1;i++)parfor(j=1;j<=2i;j++){處理器
3、Pj將B[j]復(fù)制到自己的存儲(chǔ)器中;處理器Pj將B[j]寫入B[2i+j];}}算法分析:在該并行算法中,并行寫入數(shù)組的時(shí)間復(fù)雜度為O(logN),并行讀取數(shù)據(jù)m的時(shí)間復(fù)雜度為O(1),因此該算法的時(shí)間復(fù)雜度為O(logN)。(二)求和算法求和是指處理器Pi(1≤i≤N)中含有數(shù)據(jù)Si,用和來(lái)代替Pi中的Si。求和算法的基本思想是充分利用上次累加結(jié)果來(lái)作下次并行累和。第j次累加(0≤j≤logN-1)為:2j<i≤N顯然對(duì)于i≤2j+1有[1004]:具體步驟:第1步處理器Pi(2≤i≤N)計(jì)算Si?Si+Si-1;第2步處理器Pi(3≤i≤N)計(jì)算Si?S
4、i+Si-2;第3步處理器Pi(5≤i≤N)計(jì)算Si?Si+Si-4;……第j步處理器Pi(2j+1≤i≤N)計(jì)算Si?Si+,其中j=logN-1。并行算法:12345678算法9.2.2求和算法輸入:S1,S2,…,SN輸出:Pi中的Si為和,i=1,2,…,NALLSUMS(S1,S2,…,SN){for(j=0;j<=logN-1;j++)parfor(i=2j+1;i<=N;i++){處理器Pi經(jīng)共享存儲(chǔ)器獲得;Si?Si+;}}該并行算法的時(shí)間復(fù)雜度為O(logN)。例9_1當(dāng)N=7時(shí)并行求和的執(zhí)行過(guò)程如圖9.12所示。++++++第一步S1S2
5、S3S4S5S6S7+++++第二步S1S2S3S4S5S6S7第三步S1S2S3S4S5S6S7圖9_12N=7時(shí)并行求和執(zhí)行過(guò)程(三)并行k-選擇算法并行k-選擇算法,假定輸入序列S=(x1,…,xn),且系統(tǒng)中有N=n1-ε(0<ε<1)個(gè)處理器可用,欲求S中第k個(gè)最小者(1≤k≤n)。算法思想:(1)先將S分成若干個(gè)段,每段指派給一個(gè)處理器;(2)各段同時(shí)并行求取各自的中值(可使用任意的順序選擇算法);(3)求各中值之中值,將其播送到各個(gè)處理器中;(4)以其為準(zhǔn),將S劃分成分別小于、等于、大于該值的三個(gè)子序列;(5)以一定的規(guī)則判斷各子序列長(zhǎng)度與k值
6、的大小關(guān)系,以確定k值,或繼續(xù)在相應(yīng)子序列中重復(fù)上述過(guò)程,直到找到第k個(gè)最小者為止。并行算法:1234567891011121314151617算法9.2.3并行k-選擇算法輸入:S=(x1,…,xn),
7、S
8、=n輸出:S中第k個(gè)最小者(1≤k≤n)PARALLELSELECT(k,S){if(
9、S
10、<3){使用一個(gè)處理器return(k);}else{將S分成長(zhǎng)度各為nε的n1-ε個(gè)序列,每個(gè)各指派一個(gè)處理器;}parfor(i=1;i<=n1-ε;i++){Pi使用順序選擇算法找其所轄子序列的中值mi(即第個(gè)最小者);Pi將mi寫入共享存儲(chǔ)器中數(shù)組M的第
11、i個(gè)單元M(i);}調(diào)用PARALLELSELECT(,M)找M之中值m(即第個(gè)最小者);將S分成三個(gè)子序列S1,S2,S3,其中元素分別小于,等于,大于m;if(
12、S1
13、≥k){PARALLELSELECT(k,S1);}else{if(
14、S1
15、+
16、S2
17、≥k){return(m);}else{PARALLELSELECT(k-
18、S1
19、-
20、S2
21、,S3);}}}并行k-選擇算法中,播送時(shí)間為O(logn1-ε),每個(gè)處理器使用順序選擇算法求中值時(shí)間為O(nε),使用歸并劃分法將S劃分為S1,S2,S3的時(shí)間為O(nε),該算法的時(shí)間復(fù)雜度為O(nε)。例9
22、_2對(duì)于S=(18,35,21,24,29,13,3