并行程序设计讲并行算法.pdf

并行算法的设计

高性能应用问题中，计算开销通常集中于其中少数几个循环计算，它们的计算效率决定

了整个问题的求解效率。这样的一个循环计算称为高性能应用的一个“计算热点”(hotspot)。

每个计算热点的执行过程中，将一个或者多个数据集(dataset)，各次迭代分别数据

集的不同元素。一个计算热点的执行结果可以是一个数据集，循环的每次迭成、或者更

新其中的一个元素；也可以是一个标量，由循环的各次迭代的计算结果规约而成。按照计算

热点所涉及数据集的表示，可以分为数组计算(arraycomputing)和图计算(graphcomputing)

两类。

数组计算。在循环计算中，每次迭代所的数据集元素可以表示为迭代变量的规则表

达式。即使有迭代变量的规则表达式，可以确定每次迭代所元素的下标。

图计算(graphcomputing)。在循环计算的每次迭代中，一些被的元素可以表示为迭

代变量的规则表达式，还有一些元素则需要通过这些元素所关联的“边”来确定。

为高性能应用问题开发并行程序时，关键在于发现其中的计算热点、并为每个计算热点

设计合适的并行算法。一个计算热点的并行算法设计包括任务的分解、并行计算区的划分、

超级计算步的划分、超级计算步上的任务分配以及异地任务之间的数据交换。将一个计算热

点的数据处理分解成松耦合的任务后，单向松耦合的任务将分别由不同的并行计算区执行。

在并行计算区，不同的任务通常是数据并行的。当一个并行计算区的各个任务之间存在

规约操作时，则利用规约操作的交换律和结合律特征，将该并行计算区划分成多个超级计算

步，使得超级计算步内的任务之间无数据。

4.1典型的数组计算问题

1.Laplace变换

Laplace变换是对数组的一种变换模式，即：使用变换规则数组A每个元素

A变换成另一个数组B的对应元素B，变换规则A及其周围邻居的函数。二维热

传导问题就是一个简单的Laplace变换实例。Laplace变换广泛用于空气动力场、热场、磁场

等“场”计算问题的求解。计算机解决这类问题时通常采用模拟方法，用有限元法将场空间

离散化成数组，模拟物体表面受力与其状态变化的交互作用过程、能量从源点向周围空

1

间扩散的过程。每次变换就是从当前数组出发，运用变换规则产生一个新的数组。

在应用问题中，“场”空间的全部变换构成一个计算热点，而每次变换则是该计算热点的一

1

分配时，可以将数组划分成等大小的数组片段，下标相邻的元素划分到同一个片段中，

每个片段的计算分配给一颗处理器。在不同超级计算步上，同一颗处理器所计算数值元素的

下标范围一致，以此减少每个任务的异地数据量。

例如电子设计中，就要考虑热量的扩散问题，通过合理的晶体管功能分布和散

热设计确保电子即使满负荷工作时也不至于温度过高而发生故障。令T时刻场空间的温

1

度分布为，根据场空间的温度规律计算，其中A表示T时刻位置(上的温度，

变换规则示场空间中各介质的热传导特性。在热源点,和场空间的边界上的温度分别

00

保持为常量和，其他点(在T+1时刻的温度则使用由该点及其周围其他点在T时

01

刻的温度进行计算。又比如在飞行器设计中，为了利于高速中产生的空气摩擦力实现某

些特定的性能(比如空中暂时静止)，需要通过空气动力学计算选择合适的材料、外形设

计和速度。

2.2DFFT

3.1DFFT

4.N-Body

5.矩阵乘法

6.(GaussElimination)消元法

a)Jacobi迭代法

b)