"reduce" 函数可以在函数式编程中并行化吗？
Could the "reduce" function be parallelized in Functional Programming?
在函数式编程中，map函数的一个好处是它可以在并行中执行.
因此在 4 核硬件上，此代码和 map 的并行实现将允许同时 处理 4 个值。
let numbers = [0,1,2,3]
let increasedNumbers = numbers.map { [=11=] + 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) { [=12=] + }
最常见的归约之一是所有元素的总和。
((a+b) + c) + d == (a + b) + (c+d) # associative
a+b == b+a # commutative
这种等式适用于整数，因此您可以将操作顺序从一个长依赖链更改为多个较短的依赖链，从而允许多线程和 SIMD 并行。
对于数学实数也是如此，but not for floating point numbers. In many cases, catastrophic cancellation 不是预期的，因此最终结果将足够接近，值得大量的性能提升。对于 C/C++ 编译器，这是 -ffast-math 选项启用的优化之一。 （只有 -ffast-math 的这一部分有一个 -fassociative-math 选项，没有关于缺少无穷大和 NaN 的假设。）
如果一个宽负载不能获得多个有用的值，则很难获得很大的 SIMD 加速。 Intel 的 AVX2 添加了 "gathered" 负载，但是开销非常高。使用 Haswell，通常只使用标量代码会更快，但后来的微体系结构确实具有更快的收集速度。因此，减少 SIMD 对数组 或其他连续存储的数据更有效。
现代 SIMD 硬件通过将 2 个连续 双精度浮点数加载到向量寄存器中来工作（例如，使用像 x86's sse 这样的 16B 向量）。有一个 packed-FP-add 指令将两个向量的相应元素相加。所谓的 "vertical" 向量运算（相同的运算发生在两个向量中的对应元素之间）比 "horizontal" 运算（将一个向量中的两个 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 数学饱和单位。每个操作可以是一个由八个单精度浮点数、四个双精度浮点数、一个 16B 向量或一个标量组成的 32B 向量。（保持多个操作在运行中也可以加快标量的速度，但是如果有任何数据-级并行可用，您可以对其进行矢量化以及使用多个累加器。）请参阅 http://agner.org/optimize/ 了解 x86 指令时序、流水线描述和 asm 优化内容。但请注意，此处的所有内容都适用于 ARM NEON、PPC Altivec 和其他 SIMD 架构。它们都有向量寄存器和类似的向量指令。
举个具体的例子，here's how gcc 5.3 auto-vectorizes a FP sum reduction. It only uses a single accumulator, so it's missing out on a factor of 8 throughput for Skylake. clang is a bit more clever, and uses two accumulators, but not as many as the loop unroll factor 获得 Skylake 最大吞吐量的 1/4。请注意，如果您从编译选项中取出 -ffast-math，FP 循环将使用 addss（添加标量单个）而不是 addps（添加打包单个）。整数循环仍然自动矢量化，因为整数数学是关联的。
实际上，内存带宽在大多数情况下是限制因素。 Haswell 和后来的 Intel CPUs 可以从 L1 缓存中承受每个周期两个 32B 负载。 In theory, they could sustain that from L2 cache. The shared L3 cache is another story: it's a lot faster than main memory, but its bandwidth is shared by all cores. This makes cache-blocking (aka loop tiling) 对于 L1 或 L2 来说，当处理超过 256k 的数据时，它可以很便宜地完成，这是一个非常重要的优化。与其生成然后减少 10MiB 的数据，不如生成 128k 块并在它们仍在 L2 缓存中时减少它们，而不是生产者必须将它们推送到主内存，而缩减器必须将它们带回。在工作时更高级别的语言，你最好的选择可能是希望实现为你做这件事。不过，就 CPU 的实际作用而言，这是您理想中希望发生的事情。
请注意，所有 SIMD 加速的东西都适用于在连续内存块上运行的单个线程。 您（或您的函数式语言的编译器！）可以而且应该使用这两种技术，让多个线程各自饱和它们 运行 所在核心上的执行单元。
很抱歉此答案中缺少函数式编程。你可能已经猜到我看到这个问题是因为 SIMD 标签。 :P
我不会尝试将加法概括为其他操作。 IDK 函数式编程人员通过缩减处理了什么样的东西，但是加法或比较（查找 min/max，计算匹配）是用作 SIMD 优化示例的东西。
有一些函数式编程语言的编译器可以并行化 reduce 和 map 函数。这是来自 Futhark 编程语言的示例，它编译成并行的 CUDA 和 OpenCL 源代码：
let main (x: []i32) (y: []i32): i32 =
reduce (+) 0 (map2 (*) x y)
也许可以编写一个编译器将 Haskell 的一个子集翻译成 Futhark，尽管这还没有完成。 Futhark 语言不允许递归函数，但它们可能会在该语言的未来版本中实现。
在函数式编程中，map函数的一个好处是它可以在并行中执行.
因此在 4 核硬件上，此代码和 map 的并行实现将允许同时 处理 4 个值。
let numbers = [0,1,2,3]
let increasedNumbers = numbers.map { [=11=] + 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) { [=12=] + }
最常见的归约之一是所有元素的总和。
((a+b) + c) + d == (a + b) + (c+d) # associative
a+b == b+a # commutative
这种等式适用于整数，因此您可以将操作顺序从一个长依赖链更改为多个较短的依赖链，从而允许多线程和 SIMD 并行。
对于数学实数也是如此，but not for floating point numbers. In many cases, catastrophic cancellation 不是预期的，因此最终结果将足够接近，值得大量的性能提升。对于 C/C++ 编译器，这是 -ffast-math 选项启用的优化之一。 （只有 -ffast-math 的这一部分有一个 -fassociative-math 选项，没有关于缺少无穷大和 NaN 的假设。）
如果一个宽负载不能获得多个有用的值，则很难获得很大的 SIMD 加速。 Intel 的 AVX2 添加了 "gathered" 负载，但是开销非常高。使用 Haswell，通常只使用标量代码会更快，但后来的微体系结构确实具有更快的收集速度。因此，减少 SIMD 对数组 或其他连续存储的数据更有效。
现代 SIMD 硬件通过将 2 个连续 双精度浮点数加载到向量寄存器中来工作（例如，使用像 x86's sse 这样的 16B 向量）。有一个 packed-FP-add 指令将两个向量的相应元素相加。所谓的 "vertical" 向量运算（相同的运算发生在两个向量中的对应元素之间）比 "horizontal" 运算（将一个向量中的两个 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 数学饱和单位。每个操作可以是一个由八个单精度浮点数、四个双精度浮点数、一个 16B 向量或一个标量组成的 32B 向量。（保持多个操作在运行中也可以加快标量的速度，但是如果有任何数据-级并行可用，您可以对其进行矢量化以及使用多个累加器。）请参阅 http://agner.org/optimize/ 了解 x86 指令时序、流水线描述和 asm 优化内容。但请注意，此处的所有内容都适用于 ARM NEON、PPC Altivec 和其他 SIMD 架构。它们都有向量寄存器和类似的向量指令。
举个具体的例子，here's how gcc 5.3 auto-vectorizes a FP sum reduction. It only uses a single accumulator, so it's missing out on a factor of 8 throughput for Skylake. clang is a bit more clever, and uses two accumulators, but not as many as the loop unroll factor 获得 Skylake 最大吞吐量的 1/4。请注意，如果您从编译选项中取出 -ffast-math，FP 循环将使用 addss（添加标量单个）而不是 addps（添加打包单个）。整数循环仍然自动矢量化，因为整数数学是关联的。
实际上，内存带宽在大多数情况下是限制因素。 Haswell 和后来的 Intel CPUs 可以从 L1 缓存中承受每个周期两个 32B 负载。 In theory, they could sustain that from L2 cache. The shared L3 cache is another story: it's a lot faster than main memory, but its bandwidth is shared by all cores. This makes cache-blocking (aka loop tiling) 对于 L1 或 L2 来说，当处理超过 256k 的数据时，它可以很便宜地完成，这是一个非常重要的优化。与其生成然后减少 10MiB 的数据，不如生成 128k 块并在它们仍在 L2 缓存中时减少它们，而不是生产者必须将它们推送到主内存，而缩减器必须将它们带回。在工作时更高级别的语言，你最好的选择可能是希望实现为你做这件事。不过，就 CPU 的实际作用而言，这是您理想中希望发生的事情。
请注意，所有 SIMD 加速的东西都适用于在连续内存块上运行的单个线程。 您（或您的函数式语言的编译器！）可以而且应该使用这两种技术，让多个线程各自饱和它们 运行 所在核心上的执行单元。
很抱歉此答案中缺少函数式编程。你可能已经猜到我看到这个问题是因为 SIMD 标签。 :P
我不会尝试将加法概括为其他操作。 IDK 函数式编程人员通过缩减处理了什么样的东西，但是加法或比较（查找 min/max，计算匹配）是用作 SIMD 优化示例的东西。
有一些函数式编程语言的编译器可以并行化 reduce 和 map 函数。这是来自 Futhark 编程语言的示例，它编译成并行的 CUDA 和 OpenCL 源代码：
let main (x: []i32) (y: []i32): i32 =
reduce (+) 0 (map2 (*) x y)
也许可以编写一个编译器将 Haskell 的一个子集翻译成 Futhark，尽管这还没有完成。 Futhark 语言不允许递归函数，但它们可能会在该语言的未来版本中实现。