"reduce"函数可以在函数式编程中并行化吗？

Question

在功能编程中,该map功能的一个好处是它可以实现为并行执行.

因此,在4核硬件上,此代码和并行实现map将允许同时处理 4个值.

let numbers = [0,1,2,3]
let increasedNumbers = numbers.map { $0 + 1 }

好的,现在让我们谈谈这个reduce功能.

返回结果重复调用与初始化为初始化的自身的累积值和自身的每个元素,即返回组合(组合(...组合(组合(初始,自[0]),自[1]), ... self [count-2]),self [count-1]).

我的问题:是否reduce可以实现该功能以便并行执行？或者,根据定义,它只能按顺序执行？

例:

let sum = numbers.reduce(0) { $0 + $1 }

Answer 1

最常见的归约之一是所有元素的总和。

((a+b) + c) + d == (a + b) + (c+d)  # associative
a+b == b+a                          # commutative

这种相等性适用于整数，因此您可以将操作顺序从一个长依赖链更改为多个较短依赖链，从而允许多线程和 SIMD 并行性。

对于数学实数也是如此，但对于浮点数则不然。在许多情况下，灾难性的取消是不会发生的，因此最终的结果将足够接近，值得巨大的性能提升。对于 C/C++ 编译器，这是该选项启用的优化之一-ffast-math。-fassociative-math（对于 的这一部分有一个选项-ffast-math，无需假设缺少无穷大和 NaN。）

如果一个宽负载无法获取多个有用值，则很难获得很大的 SIMD 加速。Intel的AVX2增加了“聚集”负载，但开销非常高。对于 Haswell，仅使用标量代码通常会更快，但后来的微架构确实具有更快的收集速度。所以 SIMD 减少是对于数组或其他连续存储的数据更为有效。

现代 SIMD 硬件的工作原理是将 2 个连续的双精度浮点数加载到向量寄存器中（例如，使用x86的sse等 16B 向量）。有一个 Packed-FP-add 指令，用于将两个向量的相应元素相加。所谓的“垂直”向量运算（相同的运算发生在两个向量中的相应元素之间）比“水平”运算（将两个向量相加）便宜得多double一个向量中的两个 s 彼此相加）便宜得多。

因此，在 asm 级别，您有一个循环，将所有偶数元素求和到向量累加器的一半，并将所有奇数元素求和到另一半。然后最后的一个水平操作将它们结合起来。因此，即使没有多线程，使用 SIMD 也需要关联操作（或者至少足够接近关联，就像通常的浮点一样）。如果您的输入中有一个近似模式，例如 +1.001、-0.999，则将一个大正数与一个大负数相加所产生的取消错误可能比每次取消单独发生时要严重得多。

对于更宽的向量或更窄的元素，向量累加器将容纳更多元素，从而增加 SIMD 的优势。

现代硬件具有流水线执行单元，每个时钟可以维持一个（或有时两个）FP 向量加法，但每个加法的结果在 5 个周期内还没有准备好。使硬件的吞吐量能力饱和需要在循环中使用多个累加器，因此存在 5 或 10 个独立的循环承载依赖链。（具体来说，英特尔 Skylake 进行矢量 FP 乘法、加法或 FMA（融合乘加），延迟为 4c，每 0.5c 吞吐量一次。4c/0.5c = 一次进行 8 个 FP 加法，以使 Skylake 的 FP 数学饱和每个操作可以是一个由八个单精度浮点、四个双精度浮点组成的 32B 向量、一个 16B 向量或一个标量。（在运行中保持多个操作也可以加快标量的速度，但如果有任何数据 -级别并行性可用，您可以对其进行矢量化并使用多个累加器。）请参阅http://agner.org/optimize/了解 x86 指令时序、管道描述和 asm 优化内容。但请注意，这里的所有内容都适用于 ARM NEON、PPC Altivec 和其他 SIMD 架构。它们都有向量寄存器和类似的向量指令。

举一个具体的例子，下面是 gcc 5.3 如何自动向量化 FP 总和缩减。它仅使用单个累加器，因此它错过了 Skylake 8 倍的吞吐量。clang 更聪明一点，它使用两个累加器，但没有循环展开因子那么多，以获得 Skylake 最大吞吐量的 1/4。-ffast-math请注意，如果从编译选项中取出，FP 循环将使用addss(add scalar single) 而不是addps(add Packed single)。整数循环仍然自动向量化，因为整数数学是关联的。

在实践中，内存带宽大多数时候是限制因素。 Haswell 和更高版本的 Intel CPU 可以在每个周期从 L1 缓存维持两个 32B 负载。 理论上，他们可以通过二级缓存来维持这一点。共享 L3 缓存则是另一个故事：它比主内存快得多，但其带宽由所有内核共享。当处理超过 256k 的数据时，这使得 L1 或 L2 的缓存阻塞（又名循环平铺）成为非常重要的优化，因为它可以廉价地完成。不要生成然后减少 10MiB 的数据，而是生成 128k 块并在它们仍在 L2 缓存中时减少它们，而不是生产者必须将它们推送到主内存，而减少器必须将它们带回。更高级别的语言，您最好的选择可能是希望实现为您做到这一点。不过，就 CPU 实际执行的操作而言，这正是您理想希望发生的情况。

请注意，所有 SIMD 加速内容都适用于在连续内存块上运行的单个线程。 您（或您的函数式语言的编译器！）可以而且应该使用这两种技术，让多个线程每个线程都使它们正在运行的核心上的执行单元饱和。

很抱歉这个答案中缺乏函数式编程。您可能已经猜到我看到这个问题是因为 SIMD 标签。：P

我不会尝试将加法推广到其他操作。我不知道你们这些函数式编程人员会用归约来做什么，但加法或比较（查找最小值/最大值、计算匹配项）才是用作 SIMD 优化示例的内容。