例1 SIMD-SM上求最大值算法 Begin for k=ml to o do 1 par-do A[j]=max{A[2j],A[2j+1]} end for 时间分析 t(n)=m×0(1)=0(logn) c(n)=0( nlogn)非成本最优 例2令n=2k(k>=0),求n个数和的并行算法 算法11①-SM并行求和算法(高层描述一不涉及处理器数目 B BikA+Wa(n)n (1) for i-1 to n par-do end for Wh)=/2 2) for h=1 to logn do for i=1 to n/2h pardo B[}=B[21-1H+B[2] B B21 Bn? end fc Bn-2 B 0()—→(3)S-E[]Wn)=1 end 算法运行时间:t(n)=0(logn) 总运算量:W(n)=W(n)+Wa(n)+W(n)=n+∑n/2+1=0(n) 由 Brent定理知:t(m)=0(m/p+logn) 例3设A为矩阵,有如下串行程序段: for i=l to n do for j=l to n do a[3i,2j=a[3i-2,2j-1] 其相关方向向量为,可知行和列间同时存在数据相关。在此我们可以试用行划分、列划分和 方块划分.在行划分的情况下令m=rn/p,例1的串行程序段可以转化为如下的并行程序
例 1 SIMD-SM 上求最大值算法 Begin for k=m-1 to 0 do for j=2k to 2k+1-1 par-do A[j]=max{A[2j], A[2j+1]} end for end for end 时间分析 t(n)=m×O(1)=O(logn) p(n)=n/2 c(n)=O(nlogn) 非成本最优 例 2 令 n=2k(k>=0)，求 n 个数和的并行算法 算法运行时间：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 设 A 为矩阵，有如下串行程序段： for i=1 to n do for j=1 to n do a[3i,,2j] = a[3i--2,,2j--1] endfor endfor 其相关方向向量为，可知行和列间同时存在数据相关。在此我们可以试用行划分、列划分和 方块划分..在行划分的情况下令 m=┌n/p┐ ,,例 1 的串行程序段可以转化为如下的并行程序
段 for k=l to p par-de for il=l to m de fc or J a[3(k-1)m+3i1,2j]l=a[3(k-1)m+3i1-2,2j-1] endf or 例4设A为一个n阶方阵,有如下串行程序段: for i=l to n do a[i, j]= a[i-1, j] endor endfor 分析矩阵A的元素下标i和j,则i和j的相关方向向量为,各列之间数据无任何相关 关系。因此对矩阵A可按列划分 串行程序段可转化为如下并行程序段 for k=l to P Par-do for i=l to n de a[i,(k-1)mtj1]=a[i-1,(k-1)m+j1 endfor endfor 例5
段： for k=1 to P Par--do for i1=1 to m do for j=1 to n do a[3(k--1)m+3i1,,2j]=a[ 3(k--1)m+3i1--2 ,,2j--1] endfor endfor endfor 例 4 设 A 为一个 n 阶方阵，有如下串行程序段： for i=1 to n do for j=1 to n do a[i,,j] = a[i--1,,j] endfor endfor 分析矩阵 A 的元素下标 i 和 j，则 i 和 j 的相关方向向量为，各列之间数据无任何相关 关系。因此对矩阵 A 可按列划分。 串行程序段可转化为如下并行程序段：： for k=1 to P Par--do for j1=1 to m do for i=1 to n do a[i,,(k--1)m+j1]=a[i--1,,(k--1)m+j1] endfor endfor endfor 例 5
77一77一77区7 .666区626 444.4小国44区4 0 0-3,04,0 4(源;日的)对:(2,1;7,6) (5,4;2,0) (0,7;4,2) (6,3:1,5) 注:本例无链路竞争和死锁现象 例6E立方选路 0110(S 1101①D) 1011(R
注：本例无链路竞争和死锁现象 例 6 E 立方选路 0110(S) 1101(D) 1011(R)
dim3 源:S=0110 目的:D=1101 路径 diml0110→0111→0101→1101 dime 0110 0l11 1110 0010 0011 1010 1011 0100 0101 1100 1101 0000 0001 1000 1001 例7DNS乘法示例 34 B 求C=AxB
例 7 DNS 乘法示例
0 0 0 0 6 8 6 3 18 10 14 图9.12 C00=1×(-5)+2×7=9 C01=1×(-6)+2×8=10 10°=3×(-5)+4×7=13 C113×(-6)+4×8=14 例8上三角方程组的回代解法并行化 (1)SISD上的回代算法 Begin 1)for i=n downto (1.1)xi=bi/ai (1. 2)for j=1 to i-1 do bi=bi-ajixi
C00=1×(-5)+2×7=9 C01=1×(-6)+2×8=10 C10=3×(-5)+4×7=13 C11=3×(-6)+4×8=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
endfor (2) SIMD-CREW上的并行回代算法 划分:p个处理器行循环带状划分 算法 Begi for i=n downto l do for all p;, where 1≤j≤pd for k=j to i-l step p do bk=bk-akix endfor endfor //p(n)=n, t(n)=n R J+p 例9n=8的BF网络表示 Pr,i与上层Pr-1,i,P1x-1,j相连,这里j与i仅在第r位不同
aji=0 endfor endfor End (2)SIMD-CREW 上的并行回代算法 - 划分: p 个处理器行循环带状划分 - 算法 Begin for i=n downto 1 do xi =bi /aii for all Pj , where 1≤j≤p 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 网络表示 Pr,i 与上层 Pr-1,i, Pr-1,j 相连, 这里 j 与 i 仅在第 r 位不同
行0 行10a 行 2 1a5 000001010011100101110111 列0列1列2列3列4列5列6列7 例10一个在MPI中创建新通信域的例子 MPI Comm My World, SplitWorld: int my rank, group size, Color, Key MPI Init(&argc, &argv) MPI Comm dup (MPI COMM WORLD, &My World): MPI Comm rank (MyWorld, &my rank) MPI Comm size(MyWorld, &group size) Colormy rank%3 Ke MPI Comm split(My World, Color, Key, &SplitWorld): 例11考虑如下程序段: LI for i=1 to 50 do S:X(2*D) T =,,.X(3*I+1),, endfor f1(1)=2*I;g()=3*J+1。依赖方程为:
例 10 一个在 MPI 中创建新通信域的例子 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(1)-g1()=02*I-3*J=1,而依赖约束为: 1≤I≤50,1≤J≤50。该方程的解(I,J)对应的数组变量会导致S和T之间的依赖。 例12考查以下循环可向量化的情况 (1) for I=2 to N-1 do for =2 to n-1 do (I,J)=B(I-1,J)+C B(I,J)=A(I,J+1)*2 endo (a)存在依赖Tdfs, 方向为(1,0) (b)存在依赖Tds, 方向为(0,1) (2) for i =1 ton do forj=1 to n do S D(L, D=A(I,J)+C T A(I+1,J+1)=B(I,J)*2 endfor endor 存在依赖Tdfs, 方向为(1,1)
f1 (I) -- g1 (J) = 0 è 2*I –– 3*J = 1 ,, 而依赖约束为： 1≤I≤50 ，1≤J≤50。该方程的解（I,,J）对应的数组变量会导致 S 和 T 之间的依赖。 例 12 考查以下循环可向量化的情况.. （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 d f S,, 方向为（1，0） （b）存在依赖 T d a S,, 方向为（0,, 1） （2） for I = 1 to N do for J = 1 to N do S :: D(I,, J) = A( I,, J ) + C T :: A(I+1,, J+1) = B(I,, J) * 2 endfor endfor 存在依赖 T d f S,, 方向为（1，1）
