[数学]高性能计算教案-第七讲-last.pptVIP

结构化通信 每个任务的通信模式是相同的； 下面是否存在一个相同通信模式？ 非结构化通信 没有一个统一的通信模式 例如：无结构化网格 静态通信vs.动态通信 静态 通信伙伴的身份不随时间改变 动态 通信伙伴的身份可能由运行时所计算的数据决定且是可变的 同步通信vs.异步通信 同步 双方知道何时进行通信，发送方显示的发给接收方 异步 不确定，接收的方明确地从发送者请求数据 通信判据 所有任务是否执行大致相当的通信? 是否尽可能的局部通信？ 通信操作是否能并行执行? 同步任务的计算能否并行执行？ 通信标准 所有任务是否执行大致同样多的通信。(可扩放性) 若否，则可扩放性可能不好 每个任务是否只与少许近邻通信 若否，则可能导致全局通信；应设法将全局通信结构化为局部通信结构 诸通信操作是否能并行执行 若否，则可能是低效的和不可扩放的 不同任务的计算能否并行执行 若否，则可能是低效的和不可扩放的 可重新安排通信/计算次序 第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通信 7.4 组合 7.5 映射 7.6 小结 方法描述 组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行； 合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程； 通过增加任务的粒度和重复计算，可以减少通信成本； 保持映射和扩展的灵活性，降低软件工程成本； 方法描述 （2） 增加粒度： 在划分阶段，致力于尽可能多的任务以增大并行执行的机会。但定义大量的细粒度任务不一定产生一个有效的算法，因为这有可能增加通信的代价和任务创建的代价 表面-容积效应：通信量比例于子域的表面积，而计算比例于容积； 通信/计算之比随任务的尺寸的增加而减少??增加粒度 重复计算(Replication Computation),也叫冗余计算，有时可用冗余计算来减少通信。 同时也要保持灵活性和减少软件成本、降低软件工程代价 表面-容积效应 通信量与任务子集的表面成正比，计算量与任务子集的体积成正比； 增加重复计算有可能减少通讯量； 重复计算 重复计算减少通讯量，但增加了计算量，应保持恰当的平衡； 重复计算的目标应减少算法的总运算时间； 示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。 二叉树上求和，共需2logN步 重复计算 重复计算 示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。 蝶式结构求和，使用了重复计算，共需logN步 组合判据 增加粒度是否减少了通信成本？ 重复计算是否已权衡了其得益？ 是否保持了灵活性和可扩放性？ 组合的任务数是否与问题尺寸成比例? 是否保持了类似的计算和通信？ 有没有减少并行执行的机会？ 组合的标准 组合造成的重复计算，是否平衡了其收益？ 造成重复数据，是否已证实不会因限制问题尺寸和处理机数目而影响可扩放性？ 组合产生的任务是否具有类似的计算、通信代价？ 任务数目是否仍与问题尺寸成比例？ 第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通信 7.4 组合 7.5 映射 7.6 小结 方法描述 每个任务要映射到具体的处理器，定位到运行机器上； 任务数大于处理器数时，存在负载平衡和任务调度问题； 映射的目标：减少算法的执行时间 并发的任务 ? 不同的处理器 任务之间存在高通讯的 ? 同一处理器 映射实际是一种权衡，属于NP完全问题； 负载平衡算法 静态的：事先确定； 概率的：随机确定； 动态的：执行期间动态负载； 基于域分解的： 递归对剖 局部算法 概率方法 循环映射 任务放在集中的或分散的任务池中，使用任务调度算法将池中的任务分配给特定的处理器。下面是两种常用调度模式： 经理/雇员模式 非集中模式 任务调度算法 映射判据 采用集中式负载平衡方案，是否存在通信瓶颈？ 采用动态负载平衡方案，调度策略的成本如何？ 小 结 划分 域分解和功能分解 通信 任务间的数据交换 组合 任务的合并使得算法更有效 映射 将任务分配到处理器，并保持负载平衡 并行计算 李 粤 liyue@scut.edu.cn */46 第七章 啥叫粒度（非并行计算版） 打个比方，100个学生要进行管理。 细粒度： 4个学生一个班25个班； 粗粒度： 50个学生一个班2个班。 大学寝室八个人中午吃饭 细粒度：每个人都要出寝室，去食堂打份饭回来。 粗粒度：派个代表，或者找个别的寝室的，把所有饭带回来。 程序也是一样，事情定下来的功能就那么多 细粒度： 定义了100个类； 粗粒度： 定义了2个类。 啥叫粒度（并行计算版） 粒度（gran