并行算法的设计基础 习题例题： 试证明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内，尽可能多的计算输入值的和也是一个求和问题，如果在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模型上的通信（即发送/接收）调度树。试分析此通信调度树的工作原理和图中节点中的数值是如何计算的？  图1.50 t=28，p=8，L=5，o=2， g=4的通信调度树 欲在8个处理器的BSP模型上，计算两个N阶向量内积： ①试画出各超级步的计算过程（假定N=8）； ②并分析其时间复杂度。