计算框架如何提升并行编程效能？

在计算密集型或者数据密集型的应用场景，多机并行处理是提升性能的常用方法。并行编程不仅仅是一个编程问题，它涉及到数据访问、多机通信和资源调度，应用开发人员不可能从头造轮子解决所有问题，借助于编程框架是不可避免的趋势。究竟框架如何提升并行处理的效能呢？本篇我们聊聊这个话题。

并行如何提升计算效率？

分而治之是王道

计算机算法中常常将一个大问题分解成若干个小问题来解决，这就是所谓的分治法(Divide-Conquer)。如果不同的小问题可以交由单台机器的N个CPU（泛指逻辑CPU，包括CPU、核或者超线程），或者更进一步交给多台机器的N个CPU，理想情况下期望的运行时间可能缩短到1/N。之所以说是理想，是因为实际运行时间由下面几个因素决定：

• 程序的串并行部分比率：程序不可能所有部分都能够并行执行，如果程序的必须串行部分的比例一定时，加速比是有上限的，即不管你堆叠多少CPU参与计算，都不能突破上限。这就是下面的Amdahl定律：

Amdahl定律:

加速比 = 优化前系统耗时 / 优化后系统耗时

所谓加速比就是优化前的耗时与优化后耗时的比值。加速比越高，表明优化效果越明显。

设 
    n 表示处理器个数;
    T 表示时间;
    T1 表示优化前耗时（也就是只有 1 个处理器时的耗时）;
    Tn 表示使用 n 个处理器优化后的耗时;
    F 是程序中只能串行执行的比例,

可以推导得到加速比的公式：

加速比 = 1 / (F + (1-F)/n)

由上述公式可知，如果系统中必须有50%的代码串行执行，那么系统的最大加速比为2。

• 交互代价：既然是分治，有分解（Divide)，必然有合并（Conquer）。合并意味着多个并行的子任务结束后需要交互，可能是汇总结果，也可能是重新分割数据。这中间有可能产生一部分串行，也有可能串行时间很短，但是通信代价很大，例如消息延迟或者大数据量传输。交互是严重影响性能的因素。很多类型的计算，规模增加到一定程度，性能不增反降，就是因为交互代价占了上风。

计算机体系提升并行的方式

分布式计算是从并行计算机的时代演化来的。我们花点时间介绍一下传统并行计算机的实现模式，以此为基础理解分布式并行计算会有帮助。笔者认为并行的基础是数据并行。这个数据指文件，也可以是内存或者寄存器的数据。如果没有数据并行，那意味着操作之间或者毫无关系（从而直接分解），或者必须严格串行。如果是后者，就不可能有并行可言。

在传统的计算机体系中，数据并行有两种实现路径：

• SIMD： 全称Single Instruction Multiple Data，即单指令流和多数据流，对于多数据流进行相同的操作。一个简单的例子就是向量的加减。SIMD矢量指令能够加速如C和Java语言的处理。矢量指令对多个数据元素进行并行操作，从而使主机能够快速处理大量数据。随着多媒体、大数据、人工智能等应用的兴起，为处理器赋予SIMD处理能力变得愈发重要，因为这些应用存在大量细粒度、同质、独立的数据操作，而SIMD天生就适合处理这些操作。SIMD对面临普通负载的系统程序员来说似乎没有太大的帮助。
• MIMD： 全称Multiple Instruction Multiple Data，即多指令流多数据流，体现为多发射、多线程（multi-thread）、多核心（multi-core），在当代设计的以处理能力为目标驱动的处理器中，均能看到它们的身影。

在分布式并行处理的场景中，我们会看到类似SIMD和MIMD的模式。

资源瓶颈驱动问题分解

基于多CPU和多线程的并行能够有效优化单机计算性能，而当一个问题的规模超过了单机算力才需要借助分布式并行。问题的关键在于资源瓶颈是什么？是CPU、内存，还是IO能力？如果问题是CPU受限的，需要借助多CPU加速，或者多台机器进一步加速。如果问题受限于内存或者数据，需要分解数据，让子问题的内存工作集和数据规模变小，然后再借助多机加速。

如果问题是CPU密集型的，即计算特别复杂耗时，但是处理的数据量不大，则只需要分解计算任务，将多个任务调度到多台机器上运行，然后汇总计算结果即可。传统的HPC大多属于这个类型，MPI（mpich 或者openmpi）常用于解决这一类问题。它主要解决算力的问题。

如果问题是IO受限的，即处理的数据量很大（至少PB级），但是计算本身并不复杂，类似于传统并行计算的SIMD模式，则需要进行数据分解。互联网数据的统计计算即属于这一类，例如统计所有网页的词频率，相互引用率等等。Google的MapReduce系统，和其开源实现Hadoop常用于解决这类问题。它的核心功能在于有效分解数据，利用多机算力并行处理。匹配IO吞吐量与CPU算力是这类框架的要解决的问题。

另有一类问题，它的内存（或者GPU显存）占用大小超过了单机限制，计算本身具备一定的复杂性，不能简单的归为SIMD，可能接近于MIMD。这类问题访问的数据可能很大，但是没有达到PB级。很多机器学习类型的计算例如大语言模型的训练等属于这一类。这类问题通常没有高效的通用解决方案。图计算框架，AI框架如Tensorflow、Pytorch等，都给出了自己的解决方案。也有很多用户使用MPI直接开发。

问题合并引发性能损失

将大问题分解成小问题并行计算提升了性能，但是将小问题的计算结果合并引起的同步则会造成性能瓶颈。最终的性能是这对矛盾综合后的结果。对很多计算来说，性能取决于如何高效的解决子问题的合并。典型的例子是Hadoop和Spark的MapReduce类计算。Map阶段相当于SIMD，多台机器可以完全并行，但是Reduce阶段需要重新分布数据（shuffle），需要所有机器交换数据，代价很高。这个阶段的瓶颈不再是CPU，而是硬盘IO或者网络IO，很多时候CPU未到瓶颈，网络已达瓶颈。例如Tensorflow的跨机器send/recv操作也属于这种情况。

所以加机器并不一定意味着性能提升。感兴趣的同志可以去看看Jeff Dean早期的深度学习的论文，并行规模都不是很大。规模达到一定程度，性能不升反降。这在实际中可能是常态。

分布式计算不仅仅解决计算问题

从单机多CPU并行到多机多CPU的分布式计算，用户编程方式发生了本质变化。单机并行是基于共享内存的计算（例如多线程），而多机并行是基于消息传递的计算，因为程序不再直接共享内存地址空间。即便MPI和Tensorflow框架等使用Infiniband硬件实现基于RDMA的高速数据传输，在性能上等价于直接写对方机器的内存，从用户编程角度讲依然是消息传递。

另外，如果程序的目标是处理大量数据，还需要解决多台机器之间的数据共享问题。通常有两种架构：

• 不共享存储（share nothing）：每个机器有自己的内存和硬盘，完全通过消息传递同步计算任务和交换中间数据。这种情况适用于处理数据规模不太大或者交互数据量较少的场景。
• 共享存储（share storage）：是多个计算机器之间共享一个分布式文件系统，用于数据输入、输出或中间数据的共享。在这种场景下并行的性能不仅仅取决于CPU，还受到IO带宽的限制。

所以说，从单机到多机，计算和编程的难度发生了质变。用户不仅仅是解决一个编程问题，需要一个平台帮助解决从硬件、存储到资源调度等的系统级问题。这正是计算平台或计算框架可能提供给用户的价值。我们常常听说的MPI、Hadoop、Spark、Flink、Tensorflow等都可以理解为计算框架。计算框架有胖有瘦，根据自身的设计目标，为用户解决计算中相对通用的问题。

框架解决的问题是什么？

框架本质上是一个抽象层，将不同用户或者不同场景的共同机制抽出来，封装成编程库或者通用服务，作为黑盒子给上层调用。不同框架因为设计目标不一样，编程模型也不一样。所有的编程模型背后都隐藏了解决某些通用问题的细节。了解这些通用问题的处理方法，不但是使用框架的基础，也是选择框架的前提。

资源聚合和调度

多机并行的目标是聚合多台机器的物理资源（CPU、GPU、内存、网络等等）解决一个大问题。事实上多个机器的资源并不能真的聚合成一个虚拟的机器，而是将多个程序副本或者程序的不同部分运行在多个机器上。这就涉及到如何在多个机器上调度程序的问题。很多传统的调度软件例如SGE、PBS、Slurm等的一个核心功能是帮助用户投递一个计算程序到特定的机器上运行，并监控和管理这些远程任务的状态。分布式计算框架也需要在某种程度上解决这个问题。但是不同的框架在调度上介入的深度不一样。

例如MPI相对较“瘦”。它依赖一个外部调度器（例如SGE、PBS等）投递任务。原始的Hadoop平台则比较“胖”，具备复杂的资源管理和调度功能。Hadoop2.0之后，分离出YARN作为独立的资源管理平台，Hadoop和Spark等成为了应用框架，仅包含应用级别的调度功能。这是参考Google架构演化的二级调度思路。让应用级别调度与资源管理分离，实质上解决了异构框架共享物理资源的问题。随着计算集群规模扩大，峰值算力提高，平均资源利用率必然下降。二级调度使得不同类型的计算充分共享资源，是用多租客共享经济的方式提升了整体资源利用率。极道Achelous平台更进一步实现了动态实时共享，可以进一步提升资源利用率和计算吞吐量。

扩展性（scalability）

在并行处理的场景下，性能问题部分转化为规模扩展问题，即运算时间能否随着集群规模扩大降低。如果增加算力不能提升性能，说明问题或者算法存在瓶颈，或者框架没有挖掘出足够的并行性。不同的计算框架，因为实现的并行粒度不一样，在扩展性上的表现也会不一样。

用户通过mpiexec或者mpirun启动MPI程序的时候需要指定规模大小。调度器启动指定数量的程序，协商形成固定拓扑的集群（例如给每个程序副本分配一个序号rank）。因此增加新的计算节点并不能增加并行度，所以MPI在运行期间做不到实时扩展。Hadoop和Spark等数据处理框架，它们并行的粒度是小的mapper或reducer的程序闭包（closure）。当集群可用资源规模增加时，容易利用更多的计算资源提升处理的并行度，缩短计算时间。一般来讲，并行粒度越细，调度的动态性越强，越能够利用集群资源提升吞吐量。

数据分解与聚合

很多框架（例如Hadoop、Spark）设计的目标是帮助用户解决大规模数据处理和分析的难题。这些框架不但要解决计算资源的调度问题，还需要匹配数据与算力。例如Hadoop或者Spark在Map阶段完全并行，不同计算节点上运行的Mapper程序需要处理不同的文件，或者同一个文件的不同部分。框架需要解决数据的分割问题。Hadoop这类框架都提供默认的数据分割方式，也支持用户的分割程序（例如InputFormat类等）。框架自动完成数据和Mapper的匹配，既调度算力，也调度数据。

复杂的并行处理中数据有分割也有合并，甚至会多次分割和合并。这些数据处理过程，即便最后的结果集不大，中间数据也可能达到很大规模。框架需要解决中间数据的存储、索引和分发。例如Hadoop程序的reduce阶段和Spark的shuffle都需要将中间数据重新分布，交给下一个阶段处理。这个过程涉及到大规模数据并行传输，由计算框架解决，向用户屏蔽复杂性。这个阶段往往是性能瓶颈所在。

挖掘并行性

我们基于框架实现并行处理，那么框架怎么才能最大程度挖掘应用的并行性呢？答案是数据流编程，即所谓的data flow。相对于我们平常C、C++编程使用的控制流方式，数据流更容易挖掘数据并行性，在框架层面自动并行，最大化性能。

最典型的是Spark框架。它采用RDD作为数据集抽象，在RDD上应用操作形成新的RDD，最后这些RDD根据依赖关系形成输入输出的有向无环图。Spark分析有向无环图，从结果开始触发计算依赖。已经完成的依赖无需再计算，没有依赖关系的数据集则可以并行处理。这样在框架层面保证了最大化并行性。它将如何并行的决策从程序猿下放到系统，提升了"平均程序猿"的并行水平。除了Spark，很多AI框架例如Tensorflow采用的都是数据流编程模式。所以说捕获数据的依赖关系是实现系统级优化的前提。

自动容错

我们知道，系统的故障率随着规模扩大增加。当计算规模达到一定程度，例如大规模的MapReduce集群，错误基本不可避免。框架可以为应用程序提供通用的容错机制，这样避免所有程序猿自己去处理错误和恢复，很大程度上了编程的复杂性。

结束语

本篇从原理上介绍了计算框架如何帮助用户简化并行编程。在计算的闭环中人永远是最慢的，框架的可贵之处在于它不仅仅优化程序性能，还提升开发人员的效率。博尔特一身飞起纵然突破了人类极限，但高铁纵横改变了普通人跨越地域的时间才是时代的进步。后续我们就用放大镜挨个看看这些具体的框架是怎么工作的。