第23讲 并行算法设计方法

并行算法的一般设计过程

PCAM设计方法

1

PCAM设计方法学设计并行算法的四个阶段划分(Partitioning)通讯(Communication)组合(Agglomeration)映射(Mapping)划分：分解成小的任务，开拓并发性；通讯：确定诸任务间的数据交换，监测划分的合理性；组合：依据任务的局部性，组合成更大的任务；映射：将每个任务分配到处理器上，提高算法的性能。2

PCAM设计过程3划分

1方法描述

2域分解

3功能分解

4划分判据4划分方法描述充分开拓算法的并发性和可扩放性；先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)；使数据集和计算集互不相交；划分阶段忽略处理器数目和目标机器的体系结构；能分为两类划分：域分解(domaindecomposition)功能分解(functionaldecomposition)5域分解划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通讯；6域分解示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：实际上，分解沿X、Y、Z维及它们的任意组合都可以进行。开始时，应进行三维划分，因为该方法能提供最大灵活性。

7域分解不规则区域的分解示例：8功能分解划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解；划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠，意味着要重新进行域分解和功能分解；功能分解是一种更深层次的分解。9功能分解示例1：搜索树搜索树没有明显的可分解的数据结构，但易于进行细粒度的功能分解：开始时根生成一个任务，对其评价后，如果它不是一个解，就生成若干叶结点，这些叶结点可以分到各个处理器上并行地继续搜索。

示例2：气候模型10划分判据划分是否具有灵活性？(所划分的任务数是否高于目标机上处理器数目一个量级

?)划分是否避免了冗余计算和存储？(若不是，则产生的算法对大型问题可能不是可扩展的。

)划分任务尺寸是否大致相当？(若不是，则分配处理器时很难做到负载平衡。

)11划分判据任务数与问题尺寸是否成比例？(理想情况下，问题尺寸的增加应引起任务数的增加而不是任务尺寸的增加。若不是这样，算法可能不能求解更大的问题，尽管有更多的处理器。)功能分解是一种更深层次的分解，是否合理？(多考虑几种选择可以提高灵活性。同时既要考虑域分解又要考虑功能分解。)12通讯

方法描述

四种通讯模式

通讯判据

13通讯方法描述通讯是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通讯；功能分解确定了诸任务之间的数据流；诸任务是并发执行的，通讯则限制了这种并发性；14四种通讯模式局部/全局通讯结构化/非结构化通讯静态/动态通讯同步/异步通讯15局部通讯通讯限制在一个邻域内16局部通讯当一个任务仅要求与邻近的其它任务通信时，就呈现局部通信模式。例如在数值计算中的雅可比有限差分法。如果采用5点格式，迭代公式为:

17全局通讯通讯非局部的例如：AlltoAllMaster-Worker5372118全局通讯在全局通信中，有很多任务参与交换数据。这可能造成过多的通信，从而限制了并行执行的机会。例如我们希望计算

。为此，我们使用一个根进程S负责从各进程一次接收一个值（xi）并进行累加。这时就会出现全局通信的局面。

19全局通讯采用分治策略可以开拓求和的并行性：

上式右边的两个求和可以同时执行，并且每一个仍可按同样的方式进一步分解。求和的过程如下图所示，同一级上的求和可以并行执行。这样就可以避免全局通信，并提高算法的并行度。图中

表示处理器X至处理器Y上所有数据的和。

20全局通讯21结构化通讯每个任务的通讯模式是相同的；下面是否存在一个相同通讯模式？22非结构化通讯没有一个统一的通讯模式例如：无结构化网格23通讯判据所有任务是否执行大致相当的通讯?(若不是，所设计的算法的可扩展性可能会不好。)是否尽可能的局部通讯？(若不是，则可能导致全局通信。此时应设法将全局通信换成局部通信。)24通讯判据通讯操作是否能并行执行?(若不能，所设计的算法可能是低效的和不具可扩展性的。此时可试用分治策略来开发并行性。)同步任务的计算能否并行执行？(是否会因为等待数据而降低并行度？若不能并行执行，所设计的算法可能是低效的和不具可扩展性的。此时可考虑重新安排通信和计算的顺序以改善这种情况。

)25

方法描述

表面-容积效应

重复计算

组合判据

组合26方法描述组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通讯成本；保持映射和扩展的灵活性，降低软件工程成本；27增加粒度在划分阶段，为了尽可能地开发问题的并行性，可能产生了大量的细粒度任务。但是大量的任务可能会增加通信开销和任务创建开销。28表面-容积效应通讯量与任务子集的表面成正比，计算量与任务子集的体积成正比；增加重复计算有可能减少通讯量；29表面-容积效应因此一个计算单元的通信与计算之比随任务尺寸的增加而减小。例如在二维问题中，“表面积”即是数据域的周长，它正比于问题的尺寸，而“容积”指数据域的面积，它正比于问题尺寸的平方。

30表面-容积效应以二维平面上的雅可比有限差分法5点格式为例。假设需要计算的数据是4×4矩阵。如果把计算每个元素算作一个任务，则有16个任务。每轮迭代中，每个任务都需要与其上下左右的任务通信，共需48次通信（当然这些通信中许多可以并行进行）。如下图（a）所示，每个箭头表示一次通信。

31表面-容积效应如果将相邻的四个元素的计算作为一个任务则只需8次通信，如上图（b）所示。虽然每次通信要传递两个数据，但是相对于图（a），通信的次数和通信量都大大减少了。可见，当小任务组合为大任务后，原来的某些数据传递被“包含”在大任务里面了，它们不再表现为通信，实际计算时，这些数据交换可以通过直接读取内存完成。这正是增加粒度可以减少通信的原因。

32重复计算重复计算减少通讯量，但增加了计算量，应保持恰当的平衡；重复计算的目标应减少算法的总运算时间；33重复计算假定在二叉树上求N个数的和，且要求最终在每个处理器上都有该结果。一种方法是先自叶向根求和，得到结果后再自根向叶播送，共需2

步。如下图所示。

34重复计算以上述方式求和，处理器的利用率是逐级减半的。如果在每一级每个处理器均接收两个数据，求和后再发送给上一级的两个处理器，那么经过

步后，每个处理器中就都得到了N个数的全和。计算过程如下图所示。

35组合判据增加粒度是否减少了通讯成本？（若不是，能否换用别的组合策略以减少通信开销？）重复计算是否已权衡了其得益？是否保持了灵活性和可扩放性？36组合判据组合的任务数是否与问题尺寸成比例?（若不是，算法是不可扩展的。）是否保持了类似的计算和通讯？有没有减少并行执行的机会？（是否已证实现在的并发性仍能适应目前和将来的并行机？）37

方法描述

负载平衡算法

任务调度算法

映射判据映射38方法描述每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间并发的任务

不同的处理器任务之间存在高通讯的

同一处理器映射实际是一种权衡，属于NP完全问题；39负载平衡算法静态的：事先确定；概率的：随机确定；动态的：执行期间动态负载；基于域分解的：递归对剖局部算法概率方法循环映射40负载平衡算法

局部算法局部负载平衡算法的思想是通过从近邻迁入任务和向近邻迁出任务来达到负载平衡。比如，每个处理器周期性地与邻居比较负载的轻重。如果差异超过了某个阈值，就进行负载迁移。如果自己的负载轻且有邻居负载重，则从该邻居迁入一些任务。反之，如果自己的负载重，而别的邻居较空闲，则把自己的一部分负载迁给它。局部算法的优点是这个方案只利用局部的负载信息。同时，迁移任务时往往通信量很大，而此方案只在局部迁移，有利于提高效率。

41负载平衡算法

概率方法（ProbabilisticMethod）此法的思想是将任务随机地分配给处理器，如果任务足够多，则每个处理器预计能分到大致等量的任务。此法的优点是低价和可扩展性好；缺点是要求跨处理器进行通信，并且只有当任务数远远多于处理器数时才能达到预期的效果。

循环映射（CyclicMapping）此法又称为循环指派法，即轮流地给处理器分配计算任务。它实际上是概率方法的一种形式。此法适用于各计算任务呈明显的空间局部性的情况。

总之，局部算法代价小，但当负载变化大时调整很慢；概率方法代价小，可扩展性好，但通信代价可能较大，且只适用于任务数远多于处理器数的情况；循环映射技术是概率映射的一种形式，而概率方法比其它技术易于导致可观的通信。

42负载平衡算法43任务调度算法任务放在集中的或分散的任务池中，使用任务调度算法将池中的任务分配给特定的处理器。下面是两种常用调度模式：经理/雇员模式

经理/雇员模式：

在此模式中，有一个进程（经理）负责分配任务，每个雇员向经理请求任务，得到任务后执行任务。使用预取方法（以使计算和通信重叠）可以提高效率。

层次经理/雇员模式：在此模式中，雇员被分成不相交的集合，每个集合有一个小经理。雇员们从小经理那里领取任务，小经理从经理处领取任务。经理/雇员模式的缺点是经理进程容易成为系统的瓶颈。44任务调度算法非集中模式它就是无中心管理者的分布式调度法。

45映射判据如果采用集中式负载平衡方案，是否检查了中央管理者不会成为瓶颈？如果采用动态负载平衡方案，是否衡量过不同策略的成本？

如果采用概率或循环指派法，是否有足够多的任务？一般地，任务数应不少于处理器数的10倍。46并行算法的复杂性度量串行算法的复杂性度量最坏情况下的复杂度(Worst-CASEComplexity)期望复杂度(ExpectedComplexity)并行算法的几个复杂性度量指标运行时间t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。处理器数p(n)并行算法成本c(n):c(n)=t(n)p(n)总运算量W(n):并行算法求解问题时所完成的总的操作步数。

47Brent定理令W(n)是某并行算法A在运行时间T(n)内所执行的运算量，则A使用p台处理器可在t(n)=O(W(n)/p+T(n))时间内执行完毕。W(n)和c(n)密切相关P=O(W(n)/T(n))时，W(n)和c(n)两者是渐进一致的对于任意的p，c(n)›W(n)并行算法的复杂性度量48算法级性能评测加速比性能定律并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。Amdahl定律Gustafson定律SunNi定律可扩放性评测标准等效率度量标准等速度度量标准平均延迟度量标准49Amdahl定律P：处理器数；W：问题规模（计算负载、工作负载，给定问题的总计算量）；Ws：应用程序中的串行分量，f是串行分量比例（f=Ws/W，Ws=W1）；WP：应用程序中可并行化部分，1-f为并行分量比例；Ws+Wp=W；Ts：串行执行时间，Tp：并行执行时间；S：加速比，E：效率；出发点：固定不变的计算负载；固定的计算负载分布在多个处理器上的，增加处理器加快执行速度，从而达到了加速的目的。50固定负载的加速公式：

Ws+Wp可相应地表示为f+（1-f）

p→∞时，上式极限为：S=1/fWo为额外开销

Amdahl定律51Amdahl定律52Gustafson定律出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。

Gustafson加速定律:并行开销Wo：53Gustafson定律54Sun和Ni定律基本思想：只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之，此时工作负载W=fW+（1-f）W。在p个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到pM。令因子G（p）反应存储容量增加到p倍时并行工作负载的增加量，所以扩大后的工作负载W=fW+（1-f）G（p）W。存储受限的加速公式：并行开销Wo:55Sun和Ni定律G（p）=1时就是Amdahl加速定律；

G（p）=p变为f+p（1-f），就是Gustafson加速定律G（p）>p时，相应于计算机负载比存储要求增加得快，此时Sun和Ni加速均比Amdahl加速和Gustafson加速为高。

56加速比讨论参考的加速经验公式：p/logp≤S≤P线性加速比：很少通信开销的矩阵相加、内积运算等p/logp的加速比：分治类的应用问题通信密集类的应用问题：S=1/C（p）超线性加速绝对加速：最佳并行算法与串行算法相对加速：同一算法在单机和并行机的运行时间57可扩放性评测标准并行计算的可扩放性（Scalability）也是主要性能指标可扩放性最简朴的含意是在确定的应用背景下，计算机系统（或算法或程序等）性能随处理器数的增加而按比例提高的能力影响加速比的因素：处理器数与问题规模求解问题中的串行分量并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等）加大的处理器数超过了算法中的并发程度增加问题的规模有利于提高加速的因素：较大的问题规模可提供较高的并发度；额外开销的增加可能慢于有效计算的增加；算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题规模的增大而缩小）。增加处理器数会增大额外开销和降低处理器利用率，所以对于一个特定的并行系统（算法或程序），它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。

58可扩放性:调整什么和按什么比例调整并行计算要调整的是处理数p和问题规模W，两者可按不同比例进行调整，此比例关系（可能是线性的，多项式的或指数的等）就反映了可扩放的程度。并行算法和体系结构可扩放性研究的主要目的：确定解决某类问题用何种并行算法与何种并行体系结构的组合，可以有效地利用大量的处理器；对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能；对固定的问题规模，确定在某类并行机上最优的处理器数与可获得的最大的加速比；用于指导改进并行算法和并行机体系结构，以使并行算法尽可能地充分利用可扩充的大量处理器目前无一个公认的、标准的和被普遍接受的严格定义和评判它的标准可扩放性评测标准59等速度度量标准p表示处理器个数，W表示要求解问题的工作量或称问题规模（在此可指浮点操作个数），T为并行执行时间，定义并行计算的速度V为工作量W除以并行时间Tp个处理器的并行系统的平均速度定义为并行速度V除以处理器个数p：W是使用p个处理器时算法的工作量，令W’表示当处理数从p增大到p’时，为了保持整个系统的平均速度不变所需执行的工作量，则可得到处理器数从p到p’时平均速度可扩放度量标准公式60等速度度量标准优点：直观地使用易测量的机器性能速度指标来度量缺点：某些非浮点运算可能造成性能的变化61并行数值算法

三角形方程组的求解

62基本术语线性方程组的定义和符号

a1,1x1+a1,2x2+…+a1,nxn=b1a2,1x1+a2,1x2+…+a2