《并行计算_中国科学技术大学.》由会员分享，可在线阅读，更多相关《并行计算_中国科学技术大学.（46页珍藏版）》请在金锄头文库上搜索。
1、并行计算 中国科学技术大学计算机科学与技术系国家高性能计算中心 合肥 2004年12月 第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程 第六章并行算法的基本设计技术6 1划分设计技术6 2分治设计技术6 3平衡树设计技术6 4倍增设计技术6 5流水线设计技术 6 1划分设计技术6 1 1均匀划分技术6 1 2方根划分技术6 1 3对数划分技术6 1 4功能划分技术 国家高性能计算中心 合肥 5 2020 1 27 均匀划分技术 划分方法n个元素A 1 n 分成p组 每组A i 1 n p 1 in p i 1 p
2、示例 MIMD SM模型上的PSRS排序begin 1 均匀划分 将n个元素A 1 n 均匀划分成p段 每个pi处理A i 1 n p 1 in p 2 局部排序 pi调用串行排序算法对A i 1 n p 1 in p 排序 3 选取样本 pi从其有序子序列A i 1 n p 1 in p 中选取p个样本元素 4 样本排序 用一台处理器对p2个样本元素进行串行排序 5 选择主元 用一台处理器从排好序的样本序列中选取p 1个主元 并播送给其他pi 6 主元划分 pi按主元将有序段A i 1 n p 1 in p 划分成p段 7 全局交换 各处理器将其有序段按段号交换到对应的处理器中 8 归并排序
3、 各处理器对接收到的元素进行归并排序end 国家高性能计算中心 合肥 6 2020 1 27 均匀划分技术 例6 1PSRS排序过程 N 27 p 3 PSRS排序如下 6 1划分设计技术6 1 1均匀划分技术6 1 2方根划分技术6 1 3对数划分技术6 1 4功能划分技术 国家高性能计算中心 合肥 8 2020 1 27 方根划分技术 划分方法n个元素A 1 n 分成A i 1 n 1 2 1 in 1 2 i 1 n 1 2 示例 SIMD CREW模型上的Valiant归并 1975年发表 有序组A 1 p B 1 q 假设p q 处理器数begin 1 方根划分 A B分别按 2 段
4、间比较 A划分元与B划分元比较 至多对 确定A划分元应插入B中的区段 3 段内比较 A划分元与B相应段内元素进行比较 并插入适当的位置 4 递归归并 B按插入的A划分元重新分段 与A相应段 A除去原划分元 构成了成对的段组 对每对段组递归执行 1 3 直至A组为0时 递归结束 各组仍按分配处理器 end 国家高性能计算中心 合肥 9 2020 1 27 方根划分技术 国家高性能计算中心 合肥 10 2020 1 27 方根划分技术 6 1划分设计技术6 1 1均匀划分技术6 1 2方根划分技术6 1 3对数划分技术6 1 4功能划分技术 国家高性能计算中心 合肥 12 2020 1 27 对数
5、划分技术 划分方法n个元素A 1 n 分成A i 1 logn 1 ilogn i 1 n logn示例 PRAM CREW上的对数划分并行归并排序 1 归并过程 设有序组A 1 n 和B 1 m j i rank bilogm A 为bilogm在A中的位序 即A中小于等于bilogm的元素个数 2 例 A 4 6 7 10 12 15 18 20 B 3 9 16 21 n 8 m 4 logm log4 2 j 1 rank blogm A rank b2 A rank 9 A 3 j 2 8B0 3 9B1 16 21A0 4 6 7A1 10 12 15 18 20A和B归并化为 A
6、0 B0 和 A1 B1 的归并 6 1划分设计技术6 1 1均匀划分技术6 1 2方根划分技术6 1 3对数划分技术6 1 4功能划分技术 国家高性能计算中心 合肥 14 2020 1 27 功能划分技术 划分方法n个元素A 1 n 分成等长的p组 每组满足某种特性 示例 m n 选择问题 求出n个元素中前m个最小者 功能划分 要求每组元素个数必须大于m 算法 p148算法6 4输入 A a1 an 输出 前m个最小者 Begin 1 功能划分 将A划分成g n m组 每组含m个元素 2 局部排序 使用Batcher排序网络将各组并行进行排序 3 两两比较 将所排序的各组两两进行比较 从而形
7、成MIN序列 4 排序 比较 对各个MIN序列 重复执行第 2 和第 3 步 直至选出m个最小者 End 国家高性能计算中心 合肥 15 2020 1 27 功能划分技术 第六章并行算法的基本设计技术6 1划分设计技术6 2分治设计技术6 3平衡树设计技术6 4倍增设计技术6 5流水线设计技术 6 2分治设计技术6 2 1并行分治设计步骤6 2 2双调归并网络 国家高性能计算中心 合肥 18 2020 1 27 并行分治设计步骤 将输入划分成若干个规模相等的子问题 同时 并行地 递归求解这些子问题 并行地归并子问题的解 直至得到原问题的解 6 2分治设计技术6 2 1并行分治设计步骤6 2 2
8、双调归并网络 国家高性能计算中心 合肥 20 2020 1 27 双调归并网络 双调序列 p149定义6 2 1 3 5 7 8 6 4 2 0 8 7 6 4 2 0 1 3 5 1 2 3 4 5 6 7 8 以上都是双调序列Batcher定理给定双调序列 x0 x1 xn 1 对于si min xi xi n 2 和li max xi xi n 2 则小序列 s0 s1 sn 1 和大序列 l0 l1 ln 1 仍是双调序列 国家高性能计算中心 合肥 21 2020 1 27 双调归并网络 4 4 双调归并网络 国家高性能计算中心 合肥 22 2020 1 27 双调归并网络 Batch
9、er双调归并算法输入 双调序列X x0 x1 xn 1 输出 非降有序序列Y y0 y1 yn 1 ProcedureBITONIC MERG x Begin 1 fori 0ton 2 1par do 1 1 si min xi xi n 2 1 2 li max xi xi n 2 endfor 2 RecursiveCall 2 1 BITONIC MERG MIN s0 sn 2 1 2 2 BITONIC MERG MIN l0 ln 2 1 3 outputsequenceMINfollowedbysequenceMAXEnd 第六章并行算法的基本设计技术6 1划分设计技术6 2分
10、治设计技术6 3平衡树设计技术6 4倍增设计技术6 5流水线设计技术 6 3平衡树设计技术6 3 1设计思想6 3 2求最大值6 3 3计算前缀和 国家高性能计算中心 合肥 25 2020 1 27 平衡树设计技术 设计思想以树的叶结点为输入 中间结点为处理结点 由叶向根或由根向叶逐层进行并行处理 示例求最大值计算前缀和 6 3平衡树设计技术6 3 1设计思想6 3 2求最大值6 3 3计算前缀和 国家高性能计算中心 合肥 27 2020 1 27 求最大值 算法6 8 SIMD TC SM 上求最大值算法Beginfork m 1to0doforj 2kto2k 1 1par doA j m
11、ax A 2j A 2j 1 endforendforend图示时间分析t n m O 1 O logn p n n 2 6 3平衡树设计技术6 3 1设计思想6 3 2求最大值6 3 3计算前缀和 国家高性能计算中心 合肥 29 2020 1 27 计算前缀和 问题定义n个元素 x1 x2 xn 前缀和是n个部分和 Si x1 x2 xi 1 i n这里 可以是 或 串行算法 Si Si 1 xi计算时间为O n 并行算法 p154算法6 9SIMD TC上非递归算法令A i xi i 1 n B h j 和C h j 为辅助数组 h 0 logn j 1 n 2h 数组B记录由叶到根正向遍
12、历树中各结点的信息 求和 数组C记录由根到叶反向遍历树中各结点的信息 播送前缀和 国家高性能计算中心 合肥 30 2020 1 27 计算前缀和 例 n 8 p 8 C01 C08为前缀和 第六章并行算法的基本设计技术6 1划分设计技术6 2分治设计技术6 3平衡树设计技术6 4倍增设计技术6 5流水线设计技术 6 4倍增设计技术6 4 1设计思想6 4 2表序问题6 4 3求森林的根 国家高性能计算中心 合肥 33 2020 1 27 倍增设计技术 设计思想又称指针跳跃 pointerjumping 技术 特别适合于处理链表或有向树之类的数据结构 当递归调用时 所要处理数据之间的距离逐步加倍
13、 经过k步后即可完成距离为2k的所有数据的计算 示例表序问题求森林的根 6 4倍增设计技术6 4 1设计思想6 4 2表序问题6 4 3求森林的根 国家高性能计算中心 合肥 35 2020 1 27 表序问题 问题描述n个元素的列表L 求出每个元素在L中的次第号 秩或位序或rank k rank k 可视为元素k至表尾的距离 示例 n 7 1 p a b p b c p c d p d e p e f p f g p g gr a r b r c r d r e r f 1 r g 0 2 p a c p b d p c e p d f p e p f p g gr a r b r c r d
14、 r e 2 r f 1 r g 0 3 p a e p b f p c p d p e p f p g gr a 4 r b 4 r c 4 r d 3 r e 2 r f 1 r g 0 4 p a p b p c p d p e p f p g gr a 6 r b 5 r c 4 r d 3 r e 2 r f 1 r g 0 国家高性能计算中心 合肥 36 2020 1 27 表序问题 算法 P155算法6 10 1 并行做 初始化p k 和distance k O 1 2 执行次 O logn 2 1 对k并行地做 O 1 如果k的后继不等于k的后继之后继 则 i distance
15、 k distance k distance p k ii p k p p k 2 2 对k并行地做rank k distance k O 1 运行时间 t n O logn p n n 6 4倍增设计技术6 4 1设计思想6 4 2表序问题6 4 3求森林的根 国家高性能计算中心 合肥 38 2020 1 27 求森林的根 问题描述一组有向树F中 如果是F中的一条弧 则p i j 即j是i的双亲 若i为根 则p i i 求每个结点j j 1 n 的树根s j 示例初始时P 1 p 2 5p 3 p 4 p 5 6P 6 p 7 8p 8 8P 9 10p 10 11p 11 12p 12 1
16、3p 13 13s i p i 国家高性能计算中心 合肥 39 2020 1 27 求森林的根 示例第一次迭代后第二次迭代后算法 P157算法6 11运行时间 t n O logn W n O nlogn 第六章并行算法的基本设计技术6 1划分设计技术6 2分治设计技术6 3平衡树设计技术6 4倍增设计技术6 5流水线设计技术 6 5流水线设计技术6 5 1设计思想6 5 25 pointDFT的计算 国家高性能计算中心 合肥 42 2020 1 27 流水线设计技术 设计思想将算法流程划分成p个前后衔接的任务片断 每个任务片断的输出作为下一个任务片断的输入 所有任务片断按同样的速率产生出结果 评注流水线技术是一种广泛应用在并行处理中的技术 脉动算法 Systolicalgorithm 是其中一种流水线技术 6 5流水线设计技术6 5 1设计思想6 5 25 pointDFT的计算 国家高性能计算中心 合肥 44 2020 1 27 5 pointDFT的计算 问题描述5 pointDFT的计算 应用秦九韶 Horner 法则 国家高性能计算中心 合肥 45 2020 1 27 5 p
