网站 错误代码,wordpress问答社区,大连三大网络推广网站,本地建设网站怎么查看后台账号文章目录 并行与分布式计算 第9章 算法设计9.1 设计过程9.1.1 PCAM设计过程9.1.2 划分9.1.3 通信9.1.4 组合9.1.5 映射 8.2 设计方法8.2.1 划分技术9.2.2 分治9.2.3 平衡树技术9.2.4倍增技术9.2.5 流水线技术9.2.6 破对称技术 并行与分布式计算 第9章 算法设计
9.1 设计过程
… 文章目录 并行与分布式计算 第9章 算法设计9.1 设计过程9.1.1 PCAM设计过程9.1.2 划分9.1.3 通信9.1.4 组合9.1.5 映射 8.2 设计方法8.2.1 划分技术9.2.2 分治9.2.3 平衡树技术9.2.4倍增技术9.2.5 流水线技术9.2.6 破对称技术 并行与分布式计算 第9章 算法设计
9.1 设计过程
9.1.1 PCAM设计过程
并行算法设计过程的四个阶段 • 划分(Partitioning)将大任务分解成小任务尽量开拓并发性 • 通讯(Communication) 确定诸任务间的数据交换监测任务划分的合理性 • 组合(Agglomeration) 依据任务的局部性优化通信成本或提高性能必要时将一些小任务组合成更大的任务 • 映射(Mapping) 将每个任务分配到处理器上执行监测其执行性能以备下一轮迭代优化。 9.1.2 划分
任务的划分 • 就是将原始计算问题分割成一些小的计算任务以充分开拓算法中存在的并行性 • 先进行数据分解(域分解domain decomposition)再进行计算功能的分解(功能分解functional decomposition) • 划分的要点是力图避免数据复制和计算复制使数据集和计算集互不相交 • 划分阶段忽略处理器数目和目标机器的体系结构
域分解
划分的对象是数据可以是算法的输入数据、中间处理数据和输出数据
• 1优先集中划分最大的数据将数据分解成大致相等的小数据片 • 2划分时考虑数据上的相应计算操作在计算的不同阶段可能需要对不同的数据结构进行操作或者需要对同一数据结构做不同的分解 • 3如果一个任务需要别的任务中的数据则会产生任务间的通讯 • 4 划分的主要原理是时空局部性原理注意时空窗口的粒度
功能分解
• 划分的对象是计算将所有计算过程划分为不同的任务 • 划分后如果不同任务所需的数据不相交的则划分是成功的
9.1.3 通信
任务的通信 • 通信就是为了实现并行计算诸任务之间所进行的数据传输。 • 划分产生的诸任务一般不能完全独立执行需要在任务间进行数据交流从而产生了通信 • 通信通常是数据从“生产者”向“消费者”的流动“生产”和“消费”都是操作而且具有时序关系因而通信操作的划分无法通过域分解来确定只能通过功能分解来确定 • 诸任务本是并发执行的通讯则限制了这种并发性
通信模式 • 局部/全局通讯空间局部性 • 结构化/非结构化通讯拓扑 • 静态/动态通讯身份和角色 • 同步/异步通讯是否阻塞
通信判据 • 所有任务是否执行大致相当的通信量? • 是否尽可能的将全局通信化成局部通信 • 各个通信操作是否能并行执行? • 通信操作与同步点的距离是否合适便于异步并行执行
9.1.4 组合
任务的组合 • 组合是由抽象到具体的过程使将组合的任务能在一类并行机上有效的执行 • 合并小尺寸任务减少任务数。如果任务数恰好等于处理器数则也完成了映射过程 • 通过增加任务的粒度和重复计算可以减少通信成本 • 保持映射和扩展的灵活性降低软件工程成本注意负载均衡
粒度控制 • 大量细粒度的任务未必能产生有效的并行算法可能反而增加通信代价和任务调度代价。 • 表面-容积效应一个任务的通信需求与它所操作的数据子域的表面积成正比而这个任务的计算需求与它所操作的体积数据子域表面积*计算操作的深度成正比 • 体积不变的前提下增加计算操作深度又称重复计算或者冗余计算能够减少子域表面积进而减少通信量
T总T计算T通信
组合判据 • 通过组合增加粒度是否减少了通讯成本 • 用重复计算换取通信代价是否已权衡了其得益 • 组合后是否保持了灵活性和可扩放性 • 组合的任务数是否与问题尺寸成比例? • 组合后的各个任务是否保持了类似的计算和通讯代价 • 有没有减少并行执行的机会
9.1.5 映射
任务的映射 • 映射的目标每个任务要映射到具体的处理器减少算法的执行时间映射实际是一种权衡属于NP完全问题 • 任务数大于处理器数时域分解引入负载平衡问题功能分解引入任务调度问题 • 并发的任务放在不同的处理器频繁通信的任务放在同一处理器
负载平衡算法
负载平衡分类 • 静态的事先确定 • 概率的随机确定 • 动态的动态确定基于域分解的 • 递归对剖多维空间上递归的选一维进行对剖 • 局部算法与邻居比较决定是否把任务迁给邻居 • 概率方法满足某概率条件的随机数发生器进行投放 • 循环映射等概率的特例
8.2 设计方法
8.2.1 划分技术
• 1.1 均匀划分法
• 1.2 平方根划分
• 1.3 功能划分
9.2.2 分治
分治策略是一种问题求解的方法学其思想是将原来的大问题分解成若干个特性相同的子问题分而治之。若得到的子问题仍然偏大可以反复使用分治策略直到很容易求解的子问题为止。使用分治技术时分解后的子问题通常和原来问题的类型相同则很容易使用递归过程求解
分治v.s.划分 • 侧重点不同划分是面向求解问题的需要或过程而进行的分治是面向求解问题的简单规范化而进行的。 • 难点不同划分的难点是划分点的确定问题分治的难点是问题间的同步通信和递归结果的合并问题。 • 子问题规模不同划分是根据求解需要进行的结果不一定是等分分治一般是以1/k进行的等分
并行分治法的步骤 •1将输入划分成若干个规模相等的子问题 •2同时(并行地)递归求解这些子问题 •3并行地合并子问题的解直至得到原问题的解。
9.2.3 平衡树技术
平衡树Balanced Tree方法是将输入元素作为叶节点构筑一棵平衡二叉树中间结点为处理结点由叶向根或由根向叶逐层往返遍历在树的同一深度上各节点并行计算。平衡二叉树可以推广到平衡多叉树。
9.2.4倍增技术
倍增Doubling技术又称指针跳跃(pointer jumping)技术当递归调用时所要处理数据之间的距离逐步加倍经过k步后即可完成距离为2^k的所有数据的计算。特别适合于处理链表或有向树之类的数据结构 9.2.5 流水线技术
流水线Pipelining通过时间上重叠和空间上并行的方式将一个计算任务T分成n个前后衔接的子任务T[1:n]使得tk的输出作为t(k1)的输入且tk完成后t(k1)就可立即开始并以同样的速度进行计算。 9.2.6 破对称技术
• 破对称Symmetry Breaking就是要打破某些问题的对称性常用于图论和随机算法问题。
