例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 的串行程序段可以转化为如下的并行程序