设时刻i(1iT(n))并行算法A做的工作量为Wi(即在(i-

o4 3 证明 设时刻 i 1 i T n 并行算法 A 做的工作量为 Wi 即在 i 1 i 时段内的工作量 用 p 台处理器去完成并行算法 A 的第 i 时刻工作量 需时间 p Wi 用 p 台处理器模拟并行算法 A 的总时间为 1 1 1 1 1 nT p W p W p W P W n nT i i nT i i nT i i 4 6 答案 分别对 1 2 3 进行时间复杂度进行计算 1 p dn p n 1 2 B 3 1 1 1 log BdBBdBp B 总的时间复杂度 可考虑 APRAM 假定的参数关系 pBd 2 1 2 3 log pBd p dn O B Barrier 语句的作用同步多个处理器的操作 以便进行下一步操作 4 7 答案 方法一 相应代入如下变量 1 0 1 0 s i i s i iBSP sLhgwT 总的计算时间 1 0 1 1 1 log s i di ddp p n w 每个进程总的发送信包数 1 0 1 1 log s i di ddph 路障同步时间 L 超级计算步个数 题目中的 B 应该为 d 1 1 log dpS d 时间复杂度为 1 1 log dpLgd p n OT dBSP 方法二 可以直接对每一步的时间复杂度进行计算 类似 4 6 过程略 d 的取值要保证 d 叉树的节点数要少于或等于处理器个数 p 否则存在树中节点无法 对应处理器 进一步对时间复杂度进行求导 确定 d 的值使得总的时间复杂度尽量少 12 9 总的并行执行时间 T clockcsncs tTnT 使用 n 个处理器加速比 clockcsncs csncs tTnT TTn S 故当 n 最够大且时 可被忽略 clockcs csncs n tT TT S lim csclock Tt clock t 12 10 相并行 id process id p number of process C id 0 for i id i N i i p C id A i B i Barrier sum 0 for i id i N i i p sum C i 分治并行 保证父进程将任务分配给子进程即可 主从并行 pragma omp for for i 0 i N i C i A i B i lock S sum C i unlock S 流水线 NUM THREADS 2 for i 0 i N i pragma omp parallel id omp get thread num if id 0 sum C i 1 else C i A i B i 工作池 k 0 j 0 sum 0 id omp get thread num if id 0 for i 0 i N i while k 0 sum c k 0 else lock s while k 0 c A j B j k 1 unlock s 第三次作业 1 A 是一个大小为 n 的布尔数组 欲求出最小的下标 i 且 A i 为真 试设计一个常数时间 的 PRAM CRCW 并行算法 如果使用 PRAM CREW 模型 运行时间如何 答案 1 COPY A 1 n to B 1 n 2 for i 1 to n par do if B i ture then for j i 1 to n par do B j false endfor endif endfor 3 for i 1 to n par do if B i true then return i endif endfor PRAM CRCW 中 1 使用 O n 个处理器可在 O 1 时间内完成 2 中使用 O n2 个处理器可在 O 1 时间内完成 3 使用 O n 个处理器可在 O 1 时间内完 成 如果使用 PRAM CREW 模型 2 中 B j false 这一行存在写冲突 仍然使用 O n2 个处理器 但是完成的时间最坏情况下会达到 O n 2 试用分治策略或划分技术设计一个算法求数组 A 1 n 的最小元素 要求用 O n log n 个处理器 时间复杂度为 O log n 答案 算法思想 a 将 n 个元素分给 n log n 个处理器 每个处理器获得 log n 个元素 每个处理器 需要 log n 的时间来挑选出最小的元素 问题转化为求 n log n 个元素中的最小 元素 b 以 n log n 个元素为叶子节点构造二叉树 树高为 O log n log n 将叶子 节点上的元素两两比较 较小的元素转移到上一层 因为可以试用的处理器的 节点数等于叶子节点数 故此次操作的时间复杂度 O 1 共需操作 O log n