并行处理机的算法

发布时间：85年07月27日

Geoffrey Fox Steve Otto 编译叶长远

—旦采用少许一般性技术，许多小型计算机就能有效地同时运行，由此可以解决从空气动力学到天体物理各门学科中需要大量计算的问题。

由于计算机技术的发展，我们正在开始一场计算革命。超大规模集成电路的进展不仅导致更快的计算机，也导致更加便宜、更加小型化的计算机——由几片集成块组成的计算机。这些计算机的实用价值大得令人瞠目结舌，而且也使得制造“超大功能计算机”，或称之为“超计算机”成为现实可行，这即是由许许多多的小型计算机组成的并行处理机。

并行处理机看上去比很快的串行处理机更能成为实用的大功能计算机。事实上，我们可以预期由10，000至100，000个“节点”组成的计算机，每个节点就是一个小而完整、具有每秒几千万次浮点计算，或“兆次翻转”这一不算太大功能的单独计算机，这样的设计，至少在五至十年内可以实行，可望比现有超计算机的功能增加一千至一万倍。如果这种“系列产品中最为先进”的百万兆次翻转计算机研制成功；更小的并行处理机，比如说由100个单独的节点组成，也将会实现。其总功能为几千兆翻转，基本中央处理单元及存储系统的费用大约在二万美元左右。（我们忽略了诸如磁盘盘点的基本外围设备。）

计算机功能的增强将会对各个科学领域和工程中的计算方法带来革命。例如，人们可以期望解决天气预报和量子场论中的动力学等类似的难题。值得注意的是，这些问题以及另外一些计算量很大的问题的确正好需要我们所期望的，功能增加许多的最大的并行处理机，另外一些重要问题，如空气动力学及其他领域中的三维微分方程所导出的问题，仅需要在运算速度在千兆翻转范围内的计算就足够了。

使用并行处理机的主要障碍在于提出计算机的算法及相应的程序。的确，这致使某些人怀疑这种计算机的实用性。但我们确信并行处理机的操作是十分容易的，它也绝非特别的设备，而且它能对付绝大部分计昇量很大的问题。所以，我们这篇文章的目的就在于给出使用并行处理机的一般技术，并且以几个实例加以说明。我们主要限于科学和工程领域，以及例如人工智能。因为这些领域提供了已彻底弄清楚了的算法，这可能会使得并行处理机的有效性得以数量化。同时，我们也相信我们的考虑具有一般性，在其他领域也适用。

问题的一般特征

在开始讨论具体例子之前，值得我们首先注意需要计算的问题的一般性质。表1列出几个问题作为例子，同时也列出了用并行处理机求解时的一些主要特征。任何情况下，问题都须分解成许多部分，每个部分对应于一个节点。典型地，由于算法的复杂性只是在概念意义上的，因此问题一般都显得十分容易。更确切地说，我们必须把一种相当简便的方法（例如，在计算▽²中的偏微分）用于一个“世界”中的基本“单元”（例如，一种场），而该世界包含着许许多多这样的单元。在有限差分问题中，单元便成为三维世界中的一个格点；在研究宇宙进化时，单元为一个星系，而世界即为宇宙本身。

分解用并行处理机处理的问题的第一步是，把世界分成许多小区域，用处理机的各个节点负责一个区域。如下柜图便以二维问题中求解拉普拉斯（Laplace）方程▽^2φ=0为例说明这种方法。如果有N_n个节点以及总共D个单元——图中的格点——我们发现每个节点的邻近单元数n为D/N_n，这种分解成立的条件为：单元数至少与节点数相等。下面我们看到，事实上，单元数必须远远大于节点数。这个约束是容易满足的。如今，超过一百万单元的计算已是家常便饭了，在各个领域内，目前工艺水平上计算的自由度数目正在不断增加。

当然，也存在不能如此分解而计算量又很大的问题。太阳系便为一例。在这个N体引力问题中，我们希望在一个很长的时间t上对10个方程进行积分。而这个大参数t却很难分解，所以，我们至多能用10个节点。另一方面，人们通常想考虑在各种不同初始条件下积分的结果，这样，问题也可以在积空间——粒子和初始条件——上分解，以便有效地利用大型并行处理机。

问题的处理方法

并行处理机以其节点和连接拓扑的不同而有各式各样的设计方案。我们这里考虑的硬件是加州理工学院（Caltech）的同事查理士 · 西兹（Charles Seitz）小组的系统及相似的机器。这种计算机由相同的节点组成，每个节点为一完整计算机，它可以有自己的算法单元和存储器。我们假定每个节点可以执行它自己的指令线，虽然这并不是在每次应用时都有此必要。这样的并行处理机就具有多指令、多数据（MIMO）的结构。计算机内部还可以具有另一水平上的并行性，例如“管线”（pipelining）节点不须连接成任何特定的形状，我们允许连接拓扑具有一般性；对每个问题，我们寻求其“自然”的连接方式，尤其特要的是所谓的超立方，或更精确地说，布尔（Boolean）超立方结构，即利用2^r个计算机，以r维空间中的立方体为其连接方式。例如，节点数N_n等于28时，8个计算机就犹如通常3维立方体的顶角的连接方式相同，每个点与其他三点相连。我们不需假定所有节点共有取存器，简单的分布存储结构就足以解决问题了。

通常以功能增加S（speed-up）表示并行处理机的有效性，其定义为：对同一问题，N_n节点的集合比单个节点快S倍。更进一步，定义效率ε为每节点的功能增加：S=εN_n。我们希望考察会导致并行计算机功能降低以及效率减少（完全理想情形下应为1）的因素。通常，具有线性功能增加的算法就相当令人满意了，这时，效率与节点数无关，其值也十分合适，例如，至少大于0.5。

在讨论效率时，有两个特别重要的因素。第一，节点之间的相互传递需要一定的时间，这一时间在如下条件下达到极小：算法所需的节点之间的传递必须通过“硬线”途径。系统中的传递可以视为邮电系统，这里信息可在两个任意节点之间通过中间节点得以传播。显然，“浪费的”传递时间在向前传播的信息量很小时达极小值。一般地、被分成一个个特殊问题的“世界”具有一定的拓扑以支配适当的硬件连接方式。超立方节点连接方式十分诱人，因为它包括圆环和许多网络拓扑作为子集，它也是快速Fourier变换的拓扑。更进一步，任意节点之间的距离只随节点总数的对数增长，这意味着对具有不规则结构的问题——例如，线路模拟和战争模拟——向前传播的时间最为适中。表2总了本文中讨论的问题中由于传递引起的效率减小。

“负荷平衡”是影响效率的第二个因素。必须保证每个节点基本上具有相同的计算负荷。典型情形下，效率的减小近似为每个节点上的平均计算负荷与节点上的最大负荷之比例因子。从框图可以晋到，相等负荷的实现是靠对各个节点分配相等的格点数目实现的。对这样的常规问题，这意味若每个节点在“世界”中占的面积相等。事实上，这个例子与完美的平衡还存在一较小的离差，各个节点包括的势场固定的点子（不再需要有关的计算）数目还是不同的。

对于均匀的问题，达到平衡一般比较容易。但在一些非均匀情况下，必须进行周密的考虑。考查一个引力进化问题，这里，每个节点处理相等数目的恒星式另外的天体。假如在双星形式存在的区域，我们必须使用缩小的时间步长。因而包含有双星的节点比其他的节点的负荷大。对这种情况，我们有两种方案。如果节点足够“大”，每个节点将具有相等数目的双星，这样负荷就会平衡——我们称之为分解的“中心极限定理”。这个例子便是“精细颗粒”的分解方式的反证。在表2中我们也看到，每个节点需保留适当数目的“单元”，以使传递所需的通常开支达到极小。一个更为复杂的解决方法机动地重新调节处理机的恒星分布，以使那些含有双星的处理机承担较少的其它计算任务。负荷平衡是一个重要的、实际的问题，但也并非不可克服的困难。

表1中有一列表示某些算法是否自然实现负荷平衡，另一些列表示传递的范围及算法所需的拓扑。

短程和长程力

也许，用并行处理机解决局域性问题是最为明确的。标准的例子即偏微分方程组的有限差分法。方程的局域性的基本点在于：场变量的变化仅与其附近（在物理空间中）变量有关。所以，算法可以简单分解成：经每个节点一定的物理空间中的部分体积，并且让变量只能在这个体积中变化。每个节点的算法完全与一个序列计算机相似。唯一的差别在于部分体积中的变量在稍微复杂的“边界条件”下变化——当计算遇到部分体积的边界时，就向另外的节点传递。这种问题中，我们的确需要节点之间的连接拓扑以匹配物理空间，这就是说，在问题中物理空间相近的点子同时也需要在并行处理机中相邻——相隔没有几个传递步长——二维和三维网眼和超立方即为这种拓扑的例子。

局域性问题绝非并行处理机算法相当有效的唯—例子。作为例证，我们讨论完全非局域相互作用的极端情况：N体牛顿引力问题。系统进化的直接计算方法中，只需简单地计算各种可能成对的二体作用力：

计算这些力后，可以利用通常的时间步长步骤计算粒子如何运动。作用力的计算是主要的。因为它按质点数的平方增加，而时间步长仅为线性的。虽然这是N体问题中的较慢算法，但也经常被人采用，因为此法最为精确。

要在N_n个节点的计算机上完成这一计算，我们首先必须把问题进行分解。相关的“空间”并非粒子的坐标空间——长程作用说明把坐标空间的特别区域与计算节点相对应是毫无益处的。相反，我们把粒子数进行分解，以使每个节点都负责相等数目n个粒子的演化。此处n即为N/N_n，粒子数与节点数之比。我们可以随机地给各个节点分配粒子，因为每个节点在整个演化过程中都跟踪一群给定的粒子，在任意给定时间步长中，一个节点上的粒子将会杂乱地分布在坐标空间的位置上。

现在假定节点连接拓扑包含一个环，这种拓扑的例子为环本身，或超立方体及周期性网眼。算法的第一步，每个节点记下其中一个粒子的质量和坐标，并把该信息传递给前一个节点。每个节点就开始计算进来的粒子与其中的所有另外粒子之间的作用力。完成后，“流动”粒子沿环传到另一节点，重复进行至环上每个节点都已通过时为止，然后，这种完整的循环又对另一个粒子进行，如此继续，直到每个粒子都到过每个节点。

这种算法对处理长程力是相当有效的，只要节点之间传递粒子的时间远小于计算粒子与节点中所有粒子间的作用力的时间就行了。这个条件在实际例子中是容易实现的——即使每个节点只有几个粒子，由此产生高度平行性，方法仍然十分有效。实际上，长程力算法是我们所知的最为有效的算法之一。如表2所示，传递的通常开支与成正比。然而，别的算法中，通常开支随n减小得较慢。一般认为，传递量并不造成麻烦，麻烦的倒是传递上的计算量。

在过去，并行进行的算法有点像是深奥难懂的追求，只有少数的计算机科学家才了解。而且主要是理论工作，原因很简单，现存的计算机太少。超大规模集成技术正在迅速改变这种情形，不久的将来，建造非常高的处理能力的机器将会十分便宜。我们相信在这种鼓舞下，科学家将会去学习已经被人理解的并行处理算法。毫无疑问，更好的算法也会产生。这不仅能描绘出分解的基本原理，而且有助于工具的发展，如语言和汇编器，使并行处理机与序列机同样容易使用。