文档介绍：并行算法的设计基础
习题例题:
试证明Brent定理:令W (n)是某并行算法A在运行时间T(n)内所执行的运算数量,则A使用p台处理器可在t(n)=O(W(n)/p+T(n))时间内执行完毕。
假定Pi(1≤i≤n)开始时存有数据di , 所谓累加求和指用来代替Pi中的原始值di 。
算法 PRAM-EREW上累加求和算法
输入: Pi中保存有di , l≤ i ≤ n
输出: Pi中的内容为
begin
for j = 0 to logn – 1 do
for i = 2j + 1 to n par-do
Pi = di-(2^i)
di = di + di-(2^j)
endfor
endfor
end
(1)试用n=8为例,按照上述算法逐步计算出累加和。
(2)分析算法时间复杂度。
在APRAM模型上设计算法时,应尽量使各处理器内的局部计算时间和读写时间大致与同步时间B相当。当在APRAM上计算M个数的和时,可以借用B叉树求和的办法。
假定有j个处理器计算n个数的和,此时每个处理器上分配n/p个数,各处理器先求出自身的局和;然后从共享存储器中读取它的B个孩子的局和,累加后置入指定的共享存储单元SM中;最后根处理器所计算的和即为全和。算法如下:
算法 APRAM上求和算法
输入: n个待求和的数
输出: 总和在共享存储单元SM中
Begin
各处理器求n/p个数的局和,并将其写入SM中
Barrier
for k = [ logB ( p(B – 1) + 1) ] – 2 downto 0 do
for all Pi , 0 ≤ i ≤ p – 1,do
if Pi 在第k级 then
Pi计算其B各孩子的局和并与其自身局和相加,然后将结果写入SM中
endif
end for
barrier
end for
End
(1)试用APRAM模型之参数,写出算法的时间复杂度函数表达式。
(2)试解释Barrier语句的作用。
在给定时间t内,尽可能多的计算