第四章并行算法的设计基础 习题例题: 1.试证明 Brent定理:令W(n)是某并行算法A在运行时间T(n)内所执行的运算数量,则 A使用p台处理器可在t(n)=O(Wn)/p+T(n)时间内执行完毕 2.假定P(1≤i≤n)开始时存有数据d,所谓累加求和指用∑d来代替P中的原始值 d i 算法 PRAM-EREY上累加求和算法 输入:P中保存有d,l≤i≤n 输出:P中的内容为∑d for j=0 to logn for i=2J+ I to n par-do (1)P1=d:(2^) (in)d;=d+d(2①) endo (1)试用n=8为例,按照上述算法逐步计算出累加和。 (2)分析算法时间复杂度。 3.在 APRAM模型上设计算法时,应尽量使各处理器内的局部计算时间和读写时间大致 与同步时间B相当。当在 APRAM上计算M个数的和时,可以借用B叉树求和的办法。 假定有j个处理器计算n个数的和,此时每个处理器上分配n个数,各处理器先 求出自身的局和;然后从共享存储器中读取它的B个孩子的局和,累加后置入指定的 共享存储单元SM中;最后根处理器所计算的和即为全和。算法如下: 算法 APRAM上求和算法 输入:n个待求和的数 输出:总和在共享存储单元SM中 (1)各处理器求np个数的局和,并将其写入SM中 (3)for k=[ logB(P(B-1)+1))-2 downto o de 3.1 for all P,0≤i≤p-1,do ifP1在第k级then P计算其B各孩子的局和并与其自身局和相加然后将结果 写入SM中
第四章 并行算法的设计基础 习题例题： 1. 试证明 Brent 定理：令 W (n)是某并行算法 A 在运行时间 T(n)内所执行的运算数量，则 A 使用 p 台处理器可在 t(n)＝O(W(n)／p+T(n))时间内执行完毕。 2. 假定 Pi（1≤i≤n）开始时存有数据 di , 所谓累加求和指用 1 i j j d = 来代替 Pi 中的原始值 di 。 算法 PRAM-EREW 上累加求和算法 输入： Pi 中保存有 di , l≤ i ≤ n 输出： Pi 中的内容为 i j j l d = begin for j = 0 to logn – 1 do for i = 2j + 1 to n par-do (i) Pi = di-(2^i) (ii) di = di + di-(2^j) endfor endfor end (1)试用 n=8 为例，按照上述算法逐步计算出累加和。 (2)分析算法时间复杂度。 3. 在 APRAM 模型上设计算法时，应尽量使各处理器内的局部计算时间和读写时间大致 与同步时间 B 相当。当在 APRAM 上计算 M 个数的和时，可以借用 B 叉树求和的办法。 假定有 j 个处理器计算 n 个数的和，此时每个处理器上分配 n/p 个数，各处理器先 求出自身的局和；然后从共享存储器中读取它的 B 个孩子的局和，累加后置入指定的 共享存储单元 SM 中；最后根处理器所计算的和即为全和。算法如下： 算法 APRAM 上求和算法 输入： n 个待求和的数 输出： 总和在共享存储单元 SM 中 Begin (1) 各处理器求 n/p 个数的局和,并将其写入 SM 中 (2) Barrier (3) for k = [ logB ( p(B – 1) + 1) ] – 2 downto 0 do 3.1 for all Pi , 0 ≤ i ≤ p – 1,do if Pi 在第 k 级 then Pi 计算其 B 各孩子的局和并与其自身局和相加,然后将结果 写入 SM 中 endif
barrier end ior (1)试用 APRAM模型之参数,写出算法的时间复杂度函数表达式。 (2)试解释 Barrier语句的作用 4.在给定时间t内,尽可能多的计算输入值的和也是一个求和问题,如果在logP模型上 求此问题时,要是t<L+2·0,则在一个单处理机上即可最快地完成:要是tL+2·0时, 则根处理器应在t-1时间完成局和的接收工作,然后用一个单位的时间完成加运算而得 最终的全和。而根的远程子节点应在(t-1)一(L+2·0)时刻开始发送数据,其兄妹 子节点应依次在(t-1)-(L+2·0+g),(t-1)-(L+2·0+2g),…·时刻开始发送数 据。图示出了t=28,p=8,L=5,o-=2,g=4的logP模型上的通信(即发送/接收)调度 树。试分析此通信调度树的工作原理和图中节点中的数值是如何计算的? 28)P P2 P 图1.50t=28,p=8,L=5,o=2,g=4的通信调度树 5.欲在8个处理器的BSP模型上,计算两个N阶向量内积: ①试画出各超级步的计算过程(假定N=8) ②并分析其时间复杂度
end for 3.2 barrier end for End (1)试用 APRAM 模型之参数，写出算法的时间复杂度函数表达式。 (2)试解释 Barrier 语句的作用。 4. 在给定时间 t 内，尽可能多的计算输入值的和也是一个求和问题，如果在 logP 模型上 求此问题时，要是 t<L+2·0，则在一个单处理机上即可最快地完成；要是 t>L+2·0 时， 则根处理器应在 t-1 时间完成局和的接收工作，然后用一个单位的时间完成加运算而得 最终的全和。而根的远程子节点应在（t－1）－ (L+2·0）时刻开始发送数据，其兄妹 子节点应依次在（t－1）－ (L+2·0+g)，（t－1）－ (L+2·0+2g)，···时刻开始发送数 据。图示出了 t=28，p=8，L=5，o=2，g=4 的 logP 模型上的通信（即发送/接收）调度 树。试分析此通信调度树的工作原理和图中节点中的数值是如何计算的？ 6 28 10 14 18 4 4 8 P0 P1 P2 P3 P4 P5 P6 P7 图 1.50 t=28，p=8，L=5，o=2， g=4 的通信调度树 5. 欲在 8 个处理器的 BSP 模型上，计算两个 N 阶向量内积： ①试画出各超级步的计算过程（假定 N=8）； ②并分析其时间复杂度