并行計算-習(xí)題及答案-例題習(xí)題講解.doc

例題習(xí)題講解例1 SIMD-SM上求最大值算法Begin for k=m-1 to 0 do for j=2k to 2k+1-1 par-do Aj=maxA2j, A2j+1 end for end for end 時間分析 t(n)=mO(1)=O(logn) p(n)=n/2 c(n)=O(nlogn) 非成本最優(yōu)例2 令n=2k(k=0)，求n個數(shù)和的并行算法 算法運行時間：t(n)=O(logn) 總運算量: W(n)=W(1)(n)+W(2)(n)+W(3)(n)=n+n/2h+1=O(n)由Brent定理知: t(n)=O(n/p+logn)例3 設(shè)A為矩陣，有如下串行程序段： for i=1 to n do for j=1 to n do a3i,2j = a3i-2,2j-1 endfor endfor 其相關(guān)方向向量為，可知行和列間同時存在數(shù)據(jù)相關(guān)。在此我們可以試用行劃分、列劃分和方塊劃分.在行劃分的情況下令m=n/p ,例1的串行程序段可以轉(zhuǎn)化為如下的并行程序段： for k=1 to P Par-do for i1=1 to m do for j=1 to n do a3(k-1)m+3i1,2j=a 3(k-1)m+3i1-2 ,2j-1 endfor endfor endfor 例4 設(shè)A為一個n階方陣，有如下串行程序段： for i=1 to n do for j=1 to n do ai,j = ai-1,j endfor endfor 分析矩陣A的元素下標(biāo)i和j，則i和j的相關(guān)方向向量為，各列之間數(shù)據(jù)無任何相關(guān)關(guān)系。因此對矩陣A可按列劃分。 串行程序段可轉(zhuǎn)化為如下并行程序段： for k=1 to P Par-do for j1=1 to m do for i=1 to n do ai,(k-1)m+j1=ai-1,(k-1)m+j1 endfor endfor endfor 例5 注：本例無鏈路競爭和死鎖現(xiàn)象例6 E立方選路 0110(S) 1101(D) 1011(R)例7 DNS乘法示例C00=1(-5)+27=9 C01=1(-6)+28=10 C10=3(-5)+47=13 C11=3(-6)+48=14例8 上三角方程組的回代解法并行化(1)SISD上的回代算法 Begin (1)for i=n downto 1 do (1.1)xi=bi/aii (1.2)for j=1 to i-1 do bj=bj-ajixi aji=0 endfor endfor End (2)SIMD-CREW上的并行回代算法 - 劃分: p個處理器行循環(huán)帶狀劃分 - 算法 Begin for i=n downto 1 do xi=bi/aii for all Pj, where 1jp do for k=j to i-1 step p do bk=bk-akixi aki=0 endfor endfor endfor End / p(n)=n, t(n)=n 例9 n=8的BF網(wǎng)絡(luò)表示Pr,i與上層Pr-1,i, Pr-1,j相連, 這里j與i僅在第r位不同例10 一個在MPI中創(chuàng)建新通信域的例子MPI_Comm MyWorld, SplitWorld; int my_rank,group_size, Color, Key; MPI_Init(&argc, &argv); MPI_Comm_dup(MPI_COMM_WORLD,&MyWorld); MPI_Comm_rank(MyWorld,&my_rank); MPI_Comm_size(MyWorld,&group_size); Color=my_rank%3; Key=my_rank/3; MPI_Comm_split(MyWorld,Color,Key,&SplitWorld);例11 考慮如下程序段：L1 : for I = 1 to 50 do . . . S : X(2*I) = . . . . . . T : . . . = . . . X(3*I + 1 ) . . . . . . endfor 這里： f1(I) = 2 * I ； g1(J) = 3 * J + 1 。依賴方程為： f1(I) - g1(J) = 0 2*I 3*J = 1 , 而依賴約束為： 1I50 ，1J50。該方程的解（I,J）對應(yīng)的數(shù)組變量會導(dǎo)致S和T之間的依賴。 例12 考查以下循環(huán)可向量化的情況.（1）for I = 2 to N 1 do for J = 2 to N 1 do S : A(I, J) = B( I-1, J ) + C T : B(I, J) = A(I, J+1) * 2 endfor endfor （a）存在依賴T df S, 方向為（1，0） （b）存在依賴T da S, 方向為（0, 1）（2） for I = 1 to N do fo