并行类型
- 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 科学计算杂志