高阶并行程序设计

每当我向学生或咖啡馆的咖啡师解释并行函数式编程时，我必须解决的一件事是人们以前使用并行编程的经验。这些体验通常是低级多线程编程的，充满了竞争条件和其他危险。他们的经验是并行编程是困难和令人沮丧的。谁又能怪他们呢？共享状态多线程编程肯定是我所知道的最困难的编程形式之一。然而，这种编程风格对于并行性既不是必要的，也不是充分的。毕竟，并发编程在只有一个处理器的情况下是有用的。

但是，当我必须解释我们在Futhark这样的语言中支持的并行编程类型时，这种先入为主的观念仍然是一个障碍。我的策略已经转向将Python数组库NumPy作为广泛使用的并行编程模型的一个示例；该模型已经表明高级并行编程可以与顺序编程一样可访问。在这篇文章中，我将详细阐述这一主题，并展示NumPy的一阶模型与Futhark的高阶模型相比的局限性。

NumPy是一个Python库，它提供数组类型，以及各种用于操作此类数组的函数和运算符。其主要特点是大多数操作都被隐式提升以对整个数组进行操作，而不是一次对单个元素进行操作。例如，如果x是NumPy数组，则x+1会生成一个与x大小和类型相同的数组，但每个元素加1。类似地，如果x和y是数组，则x+y产生它们的成对和，如果x和y是一维的，则对应于向量相加，如果它们是二维的，则对应于矩阵相加，依此类推。好的NumPy编程基于这些在整个数组上操作的批量操作，而不是基于单独操作元素。

NumPy的主要优势是这些原语操作是用高效的语言(如C或Fortran)实现的，这些语言的运行速度将比相应的Python循环快得多。但其优势远不止于此：数组加法x+y可能是并行的。在不了解程序中发生的其他事情的情况下，我们知道可以安全地以并行方式执行此加法，例如，对结果中的每个元素使用一个线程。当然，从字面上来说，每个元素启动一个线程效率不高，因为单独添加一个线程的工作量太少，无法摊销创建线程的成本。但请注意，我们已经在讨论如何使并行高效，而不是首先讨论并行是否安全或正确！

现在，尽管存在这种潜在的并行性，据我所知，股票NumPy不会在多个线程中执行任何操作。但是，NumPy API的其他实现，如Numba或CuPy，却做到了！一旦我们开始使用并行编程模型，实际上利用并行执行就变成了一个触手可及的工程问题。

使NumPy作为并行编程模型工作的原因是强调在整个数组上操作的批量操作。只要我们对这些操作之间的数据有一个顺序一致的视图，NumPy实现就可以在这些操作中执行它希望的任何并行技巧。我们两全其美：顺序的、完全确定的、一次一行的语义，但是(潜在的)高效并行执行。作为人类程序员，我们必须用批量操作来表达我们的代码，但我们永远不必担心争用条件或不确定性。

尽管NumPy模型具有所有优点，但它也有与所有类似的数组编程模型(如历史悠久的APL)相同的缺点。最终，在这些模型中，您作为程序员可以使用的只是一大组内置数组操作。如果您希望自己的代码高效，则in必须是可用这些原语表示的。在某些情况下，它们不够灵活。特别是，定义需要每个元素控制流的批量操作是很棘手的。

作为一个有点做作的示例，考虑将以下Python函数应用于NumPy数组的每个元素的问题：

现在，虽然NumPy确实提供了映射函数，但是使用它并不是一个好主意。因为我们应用于每个元素的函数是任意的Python函数，所以NumPy不再能够分派给一些高度调优的本机实现。更糟糕的是，通过提供任意函数，不再保证并行化是安全的，因为该函数可能会修改全局数据！为了利用高效的原语操作，我们最终必须将控制流编码为数据：

这不太好。特别是原来的函数f完全没有了，所以没有任何代码重用。此外，这些索引的并行化相当复杂，所以我们可能需要一个更糟糕的公式(它的运行速度几乎是原来的两倍，甚至是按顺序运行)：

肮脏的东西。NumPy有一些用于“掩蔽执行”的特别机制，但它并没有改变一个基本事实，即这可能不是我们喜欢的算法思考方式。而且，情况变得更糟了。让我们考虑一下计算Mandelbrot分形的任务，其本质上归结为将以下函数应用于一组独立的复数：

那么，我们如何将该函数应用于NumPy数组的每个元素呢？在上一个示例中，处理if已经够糟糕的了。处理WHILE循环更糟糕：

虽然这个程序肯定是从并行批量操作的角度来表达的，但它并没有带来欢乐。控制流是模糊的，它总是运行d次迭代，并且它会导致大量的内存流量，因为中间输出和z数组必须在内存中显示。与最初的发散函数相比，原来的发散函数只涉及一堆标量，原则上可以完全存储在寄存器中！

问题是NumPy(实际上)是一阶编程模型，因为它的操作是由值(数组和标量)参数化的，而不是函数。简而言之，NumPy缺乏有效的地图。

现在我将展示Futhark如何允许我们以一种自然的方式公开具有嵌套控制流的并行性。这并不是要批评NumPy-高阶并行编程是一件非常棘手的高效实现的事情，而且在很大程度上它仍然是一个活跃的研究领域，实现没有NumPy那么健壮。从比喻的意义上说，福塔克是在刀刃上保持平衡，承诺的东西超过了编译器所能提供的。

但它确实能送到这里。对于平方根问题，我们只定义任意标量函数，在Futhark中如下所示：

它很管用，而且跑得也很快。那曼德尔布洛特呢？同样简单：

为简单起见，我没有使用复杂的数库，因此事情看起来比实际情况要尴尬一些。完整的代码可以在这里找到。

性能怎么样？我提到过，NumPy风格的Mandelbrot由于内存流量过大而效率低下，但它到底有多糟糕？将GPU加速的Futhark与顺序NumPy进行比较并不公平，但我可以在Futhark中实现NumPy方法：

这实际上比最初的NumPy公式更有效率，因为我避免了一些昂贵的过滤器。它看起来确实很脏，但是它有多快呢？在我的AMD Vega64GPU上，对于300x300阵列，numpy_mandelbrot运行时间为7846微秒，而mandelbrot运行时间为110微秒。这比以前快了两个数量级！这完全归功于mandelbrot能够将其所有中间结果保存在寄存器中，而GPU的速度快得离谱，因为它们永远不需要触及内存。相比之下，numpy_mandelbrot必须不断地在相对较慢的内存总线(350GiB/s)上传送数据，更不用说很多额外的同步了，因为涉及到更多的离散GPU内核。

总而言之，高阶并行编程与一阶并行编程一样简单，因为它仍然是无竞争且完全确定的。但它不仅允许我们使用更强大的抽象方法，而且还可能提供更好的性能。