parallel-processing - "reduce"函数能否在函数式编程中并行化？

Question

在函数式编程中，map 的一个好处功能是可以实现在中执行平行 .

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

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

好吧，现在让我们谈谈reduce功能。

Return the result of repeatedly calling combine with an accumulated value initialized to initial and each element of self, in turn, i.e. return combine(combine(...combine(combine(initial, self[0]), self[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 并行。

对于数学实数也是如此，but not for floating point numbers .在许多情况下，catastrophic cancellation不是预期的，因此最终结果将足够接近，值得大量的性能提升。对于 C/C++ 编译器，这是 -ffast-math 启用的优化之一。选项。 (只有 -fassociative-math 的这一部分有一个 -ffast-math 选项，没有关于缺少无穷大和 NaN 的假设。)

如果一个宽负载不能获取多个有用的值，就很难获得很多 SIMD 加速。 Intel的AVX2增加了“聚集”的负载，但是开销非常高。使用 Haswell，通常只使用标量代码会更快，但后来的微体系结构确实有更快的收集。所以 SIMD 减少是 在阵列上更有效 ，或其他连续存储的数据。

现代 SIMD 硬件通过加载 2 来工作连续 double 浮点到向量寄存器中(例如，使用 16B 向量，如 x86 的 sse )。有一个packed-FP-add指令将两个向量的相应元素相加。所谓的“垂直”向量操作(在两个向量中的相应元素之间发生相同的操作)比“水平”操作(将一个向量中的两个 double 彼此相加)便宜得多。

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

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

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

举个具体的例子，here's how gcc 5.3 auto-vectorizes a FP sum reduction .它只使用一个累加器，因此它错过了 Skylake 8 倍的吞吐量。 clang 更聪明一点，而且 uses two accumulators, but not as many as the loop unroll factor获得 Skylake 最大吞吐量的 1/4。注意如果取出-ffast-math从编译选项来看，FP 循环使用 addss (添加标量单)而不是 addps (添加打包单)。整数循环仍然自动矢量化，因为整数数学是关联的。

在实践中，大多数情况下，内存带宽是限制因素。 Haswell 和更高版本的 Intel CPU 可以从 L1 缓存中维持每个周期的两个 32B 负载。 In theory, they could sustain that from L2 cache .共享 L3 缓存是另一回事:它比主内存快得多，但其带宽由所有内核共享。这使得 L1 或 L2 的缓存阻塞(又名 loop tiling)成为非常重要的优化，因为它可以廉价地完成，并且处理超过 256k 的数据。与其生成然后减少 10MiB 的数据，不如生成 128k 块并在它们仍在 L2 缓存中时减少它们，而不是生产者必须将它们推送到主内存，而 reducer 必须将它们带回来。高级语言，您最好的选择可能是希望实现为您做到这一点。不过，就 CPU 的实际作用而言，这正是您理想中想要发生的事情。

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

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

我不会尝试从添加到其他操作进行概括。 IDK 函数式编程人员可以通过减少来解决什么样的问题，但是加法或比较(查找最小值/最大值，计数匹配)是用作 SIMD 优化示例的那些。