例 1 SIMD-SM 上求最大值算法
Begin
for k=m-1 to 0 do
for j=2
k
to 2
k+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=2
k
(k>=0)，求 n 个数和的并行算法
算法运行时间：t(n)=O(logn)
总运算量: W(n)=W
(1)
(n)+W
(2)
(n)+W
(3)
(n)=n+∑n/2
h
+1=O(n)
由 Brent 定理知: t(n)=O(n/p+logn)
例
例
3
3
设
设
A
A
为矩阵，有如下串行程序段：
为矩阵，有如下串行程序段：
for i=1 to n do
for i=1 to n do
for j=1 to n do
for j=1 to n do
a[3i,2j] = a[3i-2,2j-1]
a[3i,2j] = a[3i-2,2j-1]
endfor
endfor
endfor
endfor
其相关方向向量为，可知行和列间同时存在数据相关。在此我们可以试用行划分、列划分
其相关方向向量为，可知行和列间同时存在数据相关。在此我们可以试用行划分、列划分
剩余7页未读，继续阅读
资源评论
