并行算法简介.pptVIP

* 设计一个高效的并行算法并非易事,过程很复杂,往往要几经反复方能达到要求 我们从给定问题的描述出发,通过一系列步骤,最终设计出一个能展示并发性,可扩放性,局部性和模块性的并行算法 * 考虑与机器特性无关的特性:并行性和可扩放性,寻求具有 这些特性的算法 考虑与机器相关的特性:局部性等与性能有关的问题 任务划分 将整个计算分解为一些小任务,其目的是尽量开拓并行执行的机会 通信 确定诸任务执行中所需要交换的数据和协调诸任务的执行,由此检测上述划分的合理性 任务组合 按性能要求和实现的代价来考察前两阶段的结果,必要时可将一些小任务组合成更大的任务以提高性能和减少通信开销 处理器映射 将每个任务分配到一个处理器上,其目的是最小化全局执行时间和通信成本以及最大化处理器的利用率 * 若否,后继的设计步骤缺少灵活性 若否,则产生的算法对大型问题可能是不可扩放的 若否,分配处理器时很难做到工作量均衡 理想情况下,问题尺寸的增加应引起任务数的增加而不是任务尺寸的增加 * 局部：只与较少的几个近邻通信；全局：与很多任务交换数据 结构化:一个任务与其近邻形成规整的结构(如:树,网格等) 非结构化:通信网可能是任意图 静态:通信伙伴的身份不随时间改变 动态：通信伙伴的身份可能由运行时所计算的数据决定且是可变的 同步：双方知道何时进行通信，发送方显示的发给接收 方； 异步：不确定，接收方明确地从发送者请求数据 * 若否,则可扩放性可能不好 若否,则可能导致全局通信,应设法将全局通信结构化为局部通信结构 若否,则可能是低效的和不可扩放的 若否,则可能是低效的和不可扩放的,可重新安排通信/计算次序 * 并行算法的基本设计技术 从上至下是分解过程,从下至上是求部分和的过程,是一个简单的有分有治的过程 并行算法的基本设计技术 同步和异步并行算法 同步并行算法需要在某一时刻需要与其它的处理机进行数 据交换,然后才能继续进行.异步并行算法进行数据交换不 需要严格确定在某一时刻,每个处理机按照预定的计算任 务持续执行,但通常需要在一定的时候必须进行一次数据 交换,以保证算法的正确性 例: 并行算法的一般设计过程 PCAM设计方法学 首先尽量开拓算法的并发性和满足算法的可扩放性(与算法相关的特性) 然后着重优化算法的通信成本和全局执行时间(与机器相关的特性) 同时通过必要的整个过程的反复回溯,以期望达到一个满意的设计选择 PCAM方法设计 PCAM分为四步 1) 任务的划分 2) 通信 3) 任务组合 4) 处理器映射 并行算法的一般设计过程:划分 使用域分解或者功能分解将整个计算分解成一些小的任务，以便充分利用其潜在的并行性和可扩放性。 先集中数据的分解（域分解），然后是计算功能的分解（功能分解），两者互为补充。 要点：计算集、数据集互补相交，以避免数据和计算的复制 并行算法的一般设计过程:划分 划分标准 任务数，是否至少高于目标机上处理器数的一个量级。（灵活性） 是否避免了冗于的计算和存储要求。（扩放） 划分的任务是否尺寸大致相当。（均衡） 任务数是否与问题尺寸成比例。 是否采用了几种不同的划分法，多考虑几种选择可提高灵活性，同时既考虑域分解，又要考虑功能分解。 并行算法的一般设计过程:通信 四种模式 局部通信vs.全局通信 结构化通信vs.非结构化通信 静态通信vs.动态通信 同步通信vs.异步通信 并行算法的一般设计过程:通信 通信标准 所有任务是否执行大致同样多的通信。(可扩放性) 每个任务是否只与少许近邻通信 诸通信操作是否能并行执行 不同任务的计算能否并行执行 并行算法的一般设计过程:组合 目的：合并小尺寸的任务以减少任务数，理想情况每个处理器一个任务，得到SPMD程序。 增加粒度： 在划分阶段,致力于尽可能多的任务以增大并行执行的机会.但定义大量的细粒度任务不一定产生一个有效的算法,因为这有可能增加通信的代价和任务创建的代价 表面-容积效应：通信量比例于子域的表面积，计算比例于容积，通信/计算之比随任务的尺寸的增加而减少-增加粒度 重复计算（Replication Computation）,也叫冗余计算，有时可用冗余计算来减少通信。 同时也要保持灵活性和减少软件成本,降低软件工程代价 并行算法的一般设计过程:组合 组合标准 组合造成的重复计算，是否平衡了其收益？ 造成重复数据，是否已证实不会因限制问题尺寸和处理机数目而影响可扩放性？ 组合产生的任务是否具有类似的计算、通信代价？ 任务数目是否仍与问题尺寸成比例？ 并行算法的一般设计过程:映射 指定每个任务到哪里执行，目的，减少算法的总的执行时间 策略 1)可并发执行的任务放在不同的处理器上，增强并行度 2)需要频