并行类型
- 11 分钟
开发分布式程序的另一个注意事项是指定并行类型（数据并行或图形并行）。 数据并行设计强调数据的分布式性质，并将其分布在多台计算机上。 同时，计算任务可以在所有节点中保持不变，并应用于不同的数据。 另外，不同计算机上的任务可以执行不同的计算任务。 当任务完全相同时，我们将分布式程序归类为单程序多数据 (SPMD)；否则，我们将其归类为多程序多数据 (MPMD)。
数据并行的基本思路很简单：通过将一个大型文件分布在多台计算机上，可以并行访问和处理文件的不同部分。 如前面的模块中所述，用于分配数据的一种常用方法是文件条带化，即，跨多个服务器对单个文件进行分区和分配。 另一种形式的数据并行是跨计算机分配整个文件（不进行分区），尤其是在文件较小并且所含数据表现出非常不规则的结构时。 我们发现，可以使用消息传递在分布式任务之间显式分配数据，或使用共享内存在分布式任务之间隐式分配数据（假设基础分布式系统支持共享内存）。
图 9：使用共享内存编程模型的 SPMD 分布式程序。
当每个节点对不同的分布式数据片段运行一个或多个任务时，就实现了数据并行。 作为一个具体示例，假设在分布式共享内存系统中的三台计算机之间共享数组 A。 再假设有一个分布式程序，该程序可将数组 A 的所有元素简单相加。可以命令计算机 1、2 和 3 运行相加任务，每台计算机负责处理数组 A 三分之一的元素（即 50 个元素），如图 9 所示。 可以使用共享内存编程模型跨任务分配数据，这需要使用同步机制。 很显然，这种程序是 SPMD。 相反，也可以通过（主）任务在三台计算机（包括主任务所在的计算机）之间平均分配（使用消息传递）数组 A，如图 10 所示。 每台计算机将独立运行相加任务；尽管如此，求和结果必须最终在主任务中聚合，才能生成总和。 在这种情况下，每个任务在某种意义上都是相似的，即，对数组 A 的不同部分执行相同的加法运算。不过，主任务还会将数据分发给所有任务并聚合求和结果，这使得它与其他两个任务略有不同。 很显然，这种程序是 MPMD。 如后面有关 MapReduce 的单元中所述，MapReduce 使用 MPMD 程序的数据并行。
图 10：使用消息传递编程模型的 MPMD 分布式程序
另一方面，图形并行专注于分配计算任务而不是数据。 实际上，大多数分布式程序采用的是介于这两种形式之间的某种统一形式。 图形并行已广泛应用于许多领域，例如机器学习、数据挖掘、物理学和电子电路设计。 这些领域中的许多问题都可以建模为图形，其中顶点表示计算任务，边表示数据依赖关系或通信。 回忆一下，图形 $G$ 是一对 ($(V, E)$)，其中 $V$ 是顶点的有限集合，$E$ 是成对关系（$E \subset (V \times V)$，称为边）的有限集合。 可以将权重与顶点和边关联，以指示每个顶点的工作量以及每条边上的通信数据。
以电路设计中的一个经典问题为例：其共同目标是通过将多个元件的某些引脚连接在一起，使其保持电力均衡。 如果我们假设有 $n$ 个引脚，则可以采用以下布置方式：使用 $(n - 1)$ 根电线，每根电线连接两个引脚。 在这类电路布置中，所需电线数量最少的布置通常就是最理想的布置。 显然，该布线问题可以建模为图形问题。 具体而言，每个引脚可以表示为一个顶点，一对引脚 ($(u, v)$) 之间的每个互连可以表示为一条边。 可以在 $u$ 和 $v$ 之间设置权重 $w(u, v)$，来表示连接 $u$ 和 $v$ 所需的成本（所需的电线数量）。 问题变成了如何找到连接所有顶点 $V$ 的边 $E$ 的非循环子集 $S$，其总权重
$$ w（S） = \Sigma_{（u， v）\in S} w（u， v） $$
是最小的。
因为 $S$ 是非循环且完全连接的，所以它一定会生成一颗称为最小生成树的树。 因此，解决布线问题就变成了解决最小生成树问题，这是一个可以使用 Kruskal's 和 Prim's 等算法来解决的经典问题。
图 11：使用边割度量进行分区的图形
一旦建模为图形，就可以使用图形分区技术将程序分布在分布式系统中的计算机上，该技术涉及在分布式节点上分配工作（顶点）以进行有效的分布式计算。 与数据并行一样，其基本思路很简单：通过将一个大型图形分布在多台计算机上，可以并行处理图形的不同部分，从而实现图形并行设计。 图形分区的标准目标是在 p 个处理器上均匀地分配工作，方法是将顶点划分为 p 个等权重的分区，同时最大程度减少各边表示的节点间通信量。 这样的目标通常称为标准边割度量。 虽然图形分区问题是一个 NP 难题，但启发法可以实现近乎最佳的解决方案。 作为一个具体示例，图 11 演示了 $P_{1}$、$P_{2}$ 和 $P_{3}$ 三个分区，这些分区使用边割度量划分顶点 $ \lbrace v_{1}, \cdots, v_{8} \rbrace $。 每条边的权重为 2，对应于在每个方向上传递的一个数据单元。 因此，所示边割法的总权重为 10。 其他边割法将产生更多通信流量。 显然，对于通信密集型应用程序，图形分区至关重要，它可以在决定整体应用程序性能方面发挥巨大作用。 Pregel 和 GraphLab 都采用图形分区，我们将在以后的单元中进一步讨论它们。
引用
- T. H. 科门， C. E. 莱森， R. L. 里夫斯特， 和 C. 斯坦 （2009 年 7 月 31 日）。 算法简介 MIT Press， Third Edition
- B. 亨德里克森和T.G.科尔达（2000年）。 并行计算的图形分区模型 并行计算
- M. R. Garey， D. S. Johnson， and L. Stockmeyer （1976 年） 。 一些简化的 NP-Complete 图形问题 理论计算机科学
- B. 亨德里克森和莱兰（1995年）。 The Chaco User's Guide Version 2.0 Technical Report SAND95-2344, Sandia National Laboratories
- G. 卡里皮斯和库马尔（1998年）。 用于分区不规则图形的快速高质量多层方案 SIAM 科学计算杂志