第四章并行算法的设计基础 习题例题: 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