下载掌阅APP，畅读海量书库
立即打开
如何设计软件和算法，使得程序可以在多核或集群上并行运行？早在1995年，Ian Foster在其书中提出了PCAM方法 [1] ，这种方法的思想可以用来指导并行算法的设计。PCAM主要包括4个步骤：切分（Partition）、通信（Communicate）、聚集（Agglomerate）和分发（Mapping）。图1.8展示了这4个步骤。
图1.8 PCAM方法
● 切分：将整个问题切分为多个子问题或子任务，包括计算部分和数据部分。
● 通信：定义不同子任务之间的通信方式，包括通信的数据结构和通信算法。
● 聚集：根据当前的硬件性能和编程难度，将前两步进一步整合，将细粒度的任务整合成更高效的任务。
● 分发：将整合好的任务分发给多个处理器。
例如，对于一个超大矩阵，它的大小为 M × M ，这个矩阵大到无法放在单个计算节点上计算。现在想得到这个矩阵的最大值，可以考虑如下的并行算法设计：
● 将矩阵切分成若干子矩阵，每个子矩阵的大小为 m × m ，并在每个计算节点上执行max()函数以求得子矩阵的最大值。
● 将每个子矩阵的最大值汇集到一个计算节点，并在该节点上再次执行max()函数以求得整个矩阵的最大值。
● 子矩阵大小为 m × m 的max()函数可以在单个计算节点上运行。
● 将上述计算任务分发到多个计算节点上进行处理。
设计并行程序中，最困难、最关键的部分是如何进行切分。常见的切分方式如下：
● 任务并行：一个复杂的程序通常包含多个任务，将不同的任务分配给不同的Worker。如果任务之间没有太多复杂的依赖关系，这种方式可以有效地并发执行。
● 几何分解：将所处理的数据结构化，例如根据一维或多维划分矩阵，并将它们分配给不同的Worker。刚才提到的对矩阵求最大值就是一个例子。
Google在2004年提出了MapReduce [2] ，这是一种典型的大数据并行计算范式。图1.9展示了使用MapReduce进行词频统计的处理方式。
图1.9 MapReduce进行词频统计
MapReduce主要涉及以下4个阶段。
● 切分（Split）：将大数据切分成多个小数据块，每份小数据可以在单个Worker上计算。
● 映射（Map）：对每个小数据执行Map操作。Map是一个函数映射，程序员需要自定义Map函数。Map函数输出一个键-值对（Key-Value Pair）。在词频统计的例子中，每出现一个词就计1次，Key是词，Value是1，表示该词出现了1次。
● 交换（Shuffle）：将具有相同Key的数据归集到相同的Worker上。这一步涉及数据的交换。在词频统计的例子中，将相同的词汇发送到同一个Worker上。
● 聚合（Reduce）：对所有相同的Key进行聚合操作，程序员需要自定义Reduce函数。在词频统计的例子中，Shuffle阶段已经将相同的Key归集到一起，现在只需要将所有词频求和。
MapReduce的编程范式深刻影响了Apache Hadoop、Apache Spark、Dask等开源项目。