1.2 探索设计空间

在思考如何实现并行运行时系统之前，你必须先想想并行编程模型应该是什么样的。当然，这是对于完全从零开始的情况而言。如果你的任务是实现已有的编程模型，那你的选择就比较有限了，因为虽然实现的内部细节有调整空间，但模型中面向程序员的那些部分都已经定义好了。

并行编程模型实现者面临的一个主要问题是：编程模型应该以作为提供应用程序接口（Application Programming Interface，API）的库的方式实现，还是以作为编程语言自身的一部分（或者是对它的扩展）的方式实现。更复杂的是，你还能考虑一种混合模型，模型的一部分用语言表达，另一部分由API例程涵盖。图1.2展示了三种并行编程模型类别和几个知名的示例。图1.3展示了依据编程模型所针对的并行架构而进行的不同分类。

每种设计都具有某些优势，但同时也要付出一些代价——每种设计相较于其他并行编程模型实现都有一些缺点。现在，我们探讨两种主要的设计选择及其优缺点。

1.2.1 作为库的并行

通过库引入并行，似乎是显而易见的选择。因为大多数编程语言都支持库，所以你基本上能使用任何编程语言完成并行编程。POSIX线程库pthreads就是绝佳的例子。在POSIX兼容系统，例如GNU/Linux操作系统上，pthreads为C语言和其他语言带来了多线程。另一个例子是Intel线程构建模块（Threading Building Block，TBB）[151]，它为C++语言增添了基于任务的并行。

那么，这种想法有什么问题呢？仅用API来提供并行的主要问题是：编译器通常无法意识到用来创建并行的库调用的特殊含义，因此编译器只能将API例程视为内容不可见的黑盒。在过去，该问题因C语言没有定义内存模型（关于内存模型的讨论，请参见3.2.2节）而暴露出来。编译器会假定只有一个线程在执行代码。如果pthreads再创建一个线程，则新线程会被视为程序中唯一的线程，即使此时明显存在多个线程。使用volatile类型能缓解该问题。然而，volatile类型更适合处理内存映像设备，而不是编写并行代码。3.2.2.2节展示了编译器的这种假定会如何破坏用户意图。虽然各种语言的现代版本提供了缓解问题的工具，但你需要对这些问题有所警觉，并且在代码中运用缓解措施。

清单1.1展示了一段很短的使用Intel TBB的代码示例。它将一个非常简单的循环并行化，该循环将两个数组的对应元素相加。Intel TBB负责将循环分割成更小的块，以这种方式在可用线程之间分配负载，但编译器对这个以并行方式执行的循环一无所知，因此编译器难以确定是否还有进一步并行化的机会，例如，在支持单指令多数据（Single Instruction Multiple Data，SIMD）指令的机器上使用向量化。之所以会这样是因为：for循环从循环块的起始迭代至其结尾，而编译器必须对这种按序循环进行分析，才能进一步并行化。

库方法的主要优点是，并行编程模型不会与编程语言紧密耦合，这使得库方法比编译器方法更灵活，我们将在1.2.2节中介绍编译器方法。我们可以独立地开发库，并添加新的并行编程特性，而调用库的基础语言可以保持不变。因此，不需要修改编译器。这通常会简化推出新特性的过程。只需添加额外的库调用，或是添加对已有的库调用的扩展，然后发布库的新版本，就可以引入新特性。

在过去，通过库添加新特性的优势很明显。在高性能计算（High-Performance Computing，HPC）领域，“消息传递接口”（Message Passing Interface，MPI）[90]是构建使用多台联网机器的高度并行代码的标准方式，而“高性能Fortran”（High Performance Fortran，HPF）[109]现在已沦为边缘化的历史旁注般的存在，即使HPF曾比MPI功能强大。作为编程语言的一组扩展，HPF面临着需要有编译器供应商采用的重大问题，而任何人均能以库的形式实现MPI（实际上，当初制定MPI标准时，有一个原型MPI库实现，以便在完成标准制定之前，能发现设计中存在的问题）。MPI也证明了使用来自多种编程语言的库接口是可能的，这些语言都位于底层实现之上。因此，MPI既能用于编译型语言，例如C、C++、Fortran等，也能用于解释型语言，例如Python[148]和R[106]，还能用于即时（Just-In-Time，JIT）编译语言，例如Julia[13]。

关于库方法的最后一件事是，并行编程库与内部的运行时库的分界线并不总是清晰明了的。在现实中，这是一个软件设计问题，它定义了并行编程库能够依赖于哪些基础特性，以及如何从上层特性中抽象出实现的底层细节。

1.2.2 作为语言的并行

另一种方法是在编程语言内部实现并行编程模型，即扩展现有编程语言的语法和语义，甚至重新设计一种并行编程语言。也许你已经猜到了，因为我们现在处于另一个极端，所以该方法将库方法的缺点转变为优点，优点转变为缺点。

我们先从缺点谈起，优点稍后再谈。如果我们想为编程语言扩展新特性，则必须修改编译器，使其支持新的语法和语义。虽然这件事一开始听起来微不足道，但在大多数情况下，它很快就变得举足轻重。想象一下，假设你正在使用你最爱的编程语言的闭源编译器，而你想扩展它。除非你能直接修改编译器的源代码，否则，唯一的选择就是亲自实现该语言的编译器。这可是一项非常艰巨的任务！

重新设计一款并行语言并不会让情况好转很多。库能够利用已有生态，例如C++，但设计一款新的编程语言意味着必须先为新编程语言搭建生态，才能使其有用。结果就是，人们依然使用n种已有语言，而你只是创造了第n+1种语言。如图1.4所示，来自xkcd. com的漫画（请参见文献［93］）生动地总结了该现象。

但是，使用编译器支持的并行编程模型有一个重要优势：编译器知晓并行性，所以能在分析代码时利用这些额外信息。然后，它能利用这些从编程模型中获得的额外上下文信息来转换和优化代码。编译器不必像在库方法中那样，通过分析（按序执行的）代码来推断优化方法。

现在，我们来看看清单1.2中的Fortran示例。Fortran能对数组进行元素级操作。在该示例中，数组a的每一个元素与数组b的对应元素相加，结果存储在数组c的对应位置中。如你所见，不需要编写显式循环。编译器能自动生成处理二维数组的代码。因为对每个数组元素的操作都能独立于彼此，所以编译器知道它们能同时执行，而且编译器能利用该信息来进行并行化，例如，生成SIMD代码，或使用多线程。