并行计算机的应用基础.ppt

1第第2 2章章 并行计算机的应用基础并行计算机的应用基础 2本章学习要求：§掌握：如何提高并行计算机高性能的概念§掌握：并行计算机访存模型§了解：并行计算机存储层次及其一致性问题 §掌握：并行计算模型§掌握：并行程序设计模型 §了解：同步、通信§了解：并行化技术与程序调试 3§2.1 如何提高高性能使用并行机的目的就是获取高性能但现实高性能的并行算法或并行程序是一个不断调整和改进的过程 一般说来，它们的设计过程可以划分为4步，即:l任务划分（Partitioning）、l通信（Communication）分析、l任务组合（Agglomeration）、l处理器映射（Mapping）简称为PCAM设计过程 4这是一种设计方法学，是实际设计并行算法或程序的自然过程，其基本要点是：首先尽量开拓算法的并发性和满足算法的可扩放性；然后着重优化算法的通信成本和全局执行时间并行计算的PCAM设计方法中的任务划分和通信分析阶段主要考虑如并发性和可扩放性等与机器无关的特 性，寻求开发出具有这些特性的并行算法，基本上与底 层体系结构和编程模型无关；而到任务组合和处理器映 射阶段才开始将注意力转移到局部性和别的与性能有关 的问题上。

5图2.1 算法的PCAM设计过程6如图2.1所示，PCAM设计方法的四个阶段可以简述 如下：l①划分：将整个计算分解为一些小的任务，其 目的是尽量开拓并行执行的机会；l②通信：确定诸任务执行中所需交换的数据和 协调诸任务的执行，由此可检测上述划分的合理性 ；l③组合：按性能要求和实现的代价来考察前两 阶段的结果，必要时可将一些小的任务组合成更大 的任务以提高性能或减少通信开销；l④映射：将每个任务分配到一个处理器上，其 目的是最小化全局执行时间和通信成本以及最大化 处理器的利用率7§2.1.1 任务划分所谓划分，就是使用域分解的方法将原计算问题分割成一些小的计算任务，以充分开拓算法的并发性和 可扩放性其方法是先集中数据的分解（域分解），然 后是计算功能的分解（功能分解），两者互为补充划 分的要点是力图避免数据和计算的复制，应使数据集和 计算集互不相交8§1.域分解域分解（Domain Decomposition）也叫数据划分所要划分的对象是些数据，这些数据可以是算法（或程 序）的输入数据、计算的输出数据、或者算法所产生的 中间结果域分解的步骤是：首先分解与问题相关的数 据，如果可能的话，应使这些小的数据片尽可能大致相 等；其次再将每个计算关联到它所操作的数据上。

由此 划分将会产生一系列的任务，每个任务包括一些数据及 其上的操作当一个操作可能需要别的任务中的数据时 ，就会产生通信要求9域分解的经验方法是，优先集中在最大数据的划 分；或者那些经常被访问的数据结构上在计算的不同 阶段，可能要对不同的数据结构进行操作，或者需要对 同一数据结构进行不同的分解图2.2示出了一个三维网 格的域分解方法，在各格点上计算都是重复执行的，分 解在X、Y和Z维都是可以的开始时，应集中在能提供最 大灵活性的三维（即3-D）分解上，即每一个格点定义一 个计算任务，每个任务维护与其格点有关的各种数据， 并负责计算以修改状态循环无疑是并行程序中最丰富的并行资源，如何 将大的串行循环并行化是并行编译技术的研究重点，已 经提出大量的判定循环可否并行的定理和各种循环变换 技术10图2.2 三维网格问题的域分解法(各图中的阴影部分代表一个任务)11§2.功能分解除了数据并行，应用程序本身也存在着功能并行的机会功能分界（Functional Decomposition）也被称为 任务分解或计算划分l它首先关注于被执行的计算上，而不是计算所 需的数据上；l然后，如果所作的计算划分是成功的，再继续 研究计算所需的数据，如果这些数据基本上不相交 ，就意味着划分的成功；l如果这些数据有相当的重叠，就意味着必然带 来大量的通信，这暗示着应该考虑数据分解。

12一个并行程序通常同时存在数据和功能并行的机会但 功能并行的并行度通常比较有限，并且不会随着问题规 模的的扩大而增加；不同的函数所涉及的数据集的大小 可能差异很大，因此也难于实现负载平衡而数据并行 则一般具有较好的可扩放性，也易于实现负载的平衡 现有的绝大多数大规模的并行程序属于数据并行应用， 但功能分解有时能提示问题的内在结构展示出优化的机 遇，而对数据单独进行研究却往往难以做到这一点搜 索树是功能分解的最好例子，此时并无明显的可分解的 数据结构，但却易于进行细粒度的功能分解：开始时根 生成一个任务，对其评价后，如果它不是一个解，就生 成一棵搜索子树，整个搜索过程自根以波前（Wavefront ）形式逐级向树叶推进13§2.1.2 通信分析由划分所产生的诸并行执行的任务，一般而言不可能完全并行执行，一个任务中的计算可能需要用到另一 个任务中的数据，从而就产生了通信要求在域分解中，通常难以确定通信要求，因为将数 据划分成不相交的子集并未充分考虑在数据上执行操作 时可能产生的数据交换；在功能分解时，通常容易确定 通信要求，因为并行算法中诸任务之间的数据流就相应于通信要求 14§通信大致可以分为以下四种模式：l①局部/全局通信：局部通信时,每个任务只和 较少的几个近邻通信；全局通信中，每个任务与很 多别的任务通信。

l②结构化/非结构化通信：结构化通信时，一 个任务和其近邻形成规整结构（如树、网格等）； 非结构化通信中，通信网则可能是任意图l③静态/动态通信：静态通信，通信伙伴的身 份不随时间改变；动态通信中，通信伙伴的身份则 可能由运行时所计算的数据决定且是可变的l④同步/异步通信：同步通信时，接收方和发 送方协同操作；异步通信中，接收方获取数据无需 与发送方协同 15§2.1.3 任务组合在任务划分和通信阶段，得到的算法是抽象的，并未考虑在具体并行机上的执行效率，在组合阶段将重 新考察在划分和通信阶段所作的抉择，力图得到一个在 某一类并行机上能有效执行的并行算法组合的目的就 是通过合并小尺寸的任务来减少任务数，但它仍可能多 于处理器数，理想的情况是任务数和处理器数目一致从 而得到一个SPMD程序用增加计算和通信粒度的方法可 以减少通信成本，组合时要在保持足够的灵活性的同时 减少软件工程代价这几个相互矛盾的准则在组合阶段 要仔细权衡16§1.增加粒度在设计的划分阶段，致力于定义尽可能多的任务以增大并行执行的机会但是定义大量的细粒度任务不 一定能产生一个有效的并行算法，因为大量细粒度任务 有可能增加通信代价和任务创建代价。

重复计算（Replication Computation）也称冗余计算有时可采用不必要的多余计算来减少通信要求和执行时间 17如果每个任务的通信伙伴较少，增加划分粒度通常可以减少通信次数，同时还可以减少总通信量：一个任 务通信需求比例于它所操作的子域的表面积，而计算需 求却比例于子域的容积，这就是所谓的表-容效应（ Surface-Volume Effect）在一个二维问题中，“表面 积”比例于问题的尺寸，而“容积”比例于问题尺寸的 平方，因此一个计算单元的通信/计算之比随问题（任务 ）尺寸的增加而减少所以，在其它条件等同的情况下 ，高维分解一般更为有效因为相对一个给定的容积（ 计算）它减少了表面积（通信）因此从效率的角度， 增加粒度的最好办法是在所有的维组合任务18§2.保持灵活性组合的主要目的是提高效率和减少通信成本，但也要注意保持足够的灵活性和降低软件工程代价在组 合时，易于作出对算法的可扩放性带来不必要限制的决 定，要维持一个程序的可移植性和可扩放性，创建可变 数目的任务是很关键的，而组合时往往会使问题的任务 数的变化范围受到限制为了易于在映射时平衡负载， 组合后的任务数，按照经验，至少应比处理器的数目多 一个数量级。

组合还应尽量减少软件工程代价，尽量减 少代码的巨大变化以减少软件开发开销19§2.1.4 处理器映射（Mapping） §1.处理器映射策略指定任务到哪个处理器上去执行就是映射，其主 要目标是减少算法的总执行时间，策略有二：l一是把那些可并发执行的任务放在不同的处理器上 以增强并行度；l二是把那些需频繁通信的任务置于同一个处理器上 以提高局部性这两个策略有时会冲突，需要权衡对于两个处 理器而言，映射问题有最佳解；当处理器数目大于等于3 时，此问题是NP完全问题，但仍可以利用关于特定策略 的知识，用启发式算法来获得有效的解20§2.负载平衡简单地说，负载平衡(Load-balancing)就是使得所有处理器完成等量的任务，这要求挖掘足够的并行性 负载平衡不是任务简单的平均划分，更重要的是所有 处理器应该在大致相等的时间内完成所分配的任务，因 此必须减少同步等待的时间，这包括等待其它进程结束 运行的时间和串行执行的代码部分（包括临界区代码和 因数据相关造成的串行执行）21基于域分解技术的算法有很多专用的和通用的负载平衡技术，它们都是试图将划分阶段产生的细粒度任务 组合成每一个处理器一个粗粒度的任务。

代表性的方法 包括递归对剖(Recursive Bisection)、局部算法、概率 方法、循环映射(Cyclic Mapping)等递归对剖法需全 局知识，性能好但代价高；局部算法代价小，但当负载 变化大时调整较慢；概率方法代价低，可扩放性好，但 通信代价可能较大，且只适用于任务数远多于处理器的 情形；循环映射技术实际上是概率映射的一种形式，而 概率方法比其它技术可能会使负载失衡和牺牲了局部性 ，从而带来相当的通信22§2.1.5 任务的分配与调度负载平衡与任务分配/调度密切相关，任务分配通常有静态的和动态的两种方法静态分配一般是任务到 进程的算术映射静态分配的优点是没有运行时任务管 理的开销，但为了实现负载平衡，要求不同任务的工作 量和处理器的性能是可以预测的并且拥有足够的可供分 配的任务动态分配就相对灵活，可以运行时在不同处 理器间动态地进行负载的调整23静态调度（Static Scheduling）任务调度通常也有静态和动态两种静态调度方案一般是静态地为 每个处理器分配[N/p]个连续的循环迭代，其中N为迭代 次数，p是处理器数除了在所有的循环迭代计算时间和 每个处理器的计算能力都相同的同构情况下外，这种静 态调度的方案总会引起负载的不平衡。

另一方面，静态 调度方案也可以采用轮转(Round-robin)的方式来给处理 器分配任务，即将第i个循环迭代分配给第i mod p个处 理器这种方案可以部分地解决应用程序本身负载不平 衡的情况，如LU分解的执行时间随着循环变量i的增长而 减少然而，采用轮转方式可能会导致高速缓存命中率 降低24§1.基本自调度(SS) 基本自调度的基本原理是每个处理器在空闲时就 从全局任务队列中取走一个循环迭代，由此可以看出， 无论在独占还是在元计算环境下，SS总可以获得一个较 好的负载平衡各处理器间的差距最多不超过一次循环 迭代的时间然而，由于调度的开销和迭代次数成正比 ，所以这种形式的负载平衡并不意味着一定会得到最好 的性能对于那些细粒度的应用来说，任务调度的开销 比实际计算的时间还要大另外，任务队列的频繁互斥 访问将会导致严重的竞争从而影响性能SS可能适合那 些循环的迭代次数不是太多，但计算时间比循环分配时 间要长一些的应用程序25§2.块自调度(BSS)为了减少SS方案中花费在循环任务分配的开销，块自调度方案每次取来K个循环迭代这样在SS方案 中的K个任务分配的开销就被BSS中的K个循环迭代的计算 时间所掩盖。

当K=1时，BSS就演变为SS而当 ，BSS和静态调度任务看起来很象，其实它们之间存在着 很大的不同，这将在后面看出BSS的主要缺点是对块大 小的依赖很大而且针对一个应用很难事先确定块的大小 块太大会导致负载不平衡，块太小会引起过多的循环 。