例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