multithreading - 并行化 "Reduce"中的 "MapReduce"

Question

我了解 Map 是如何轻松并行化的——每台计算机/CPU 只能在阵列的一小部分上运行。

Reduce/foldl 是否可并行化？似乎每个计算都依赖于前一个。它是否仅适用于某些类型的函数？

Answer 1

如果您的归约基础操作是关联的*，您可以使用操作顺序和局部性。因此，在“收集”阶段，您通常会具有树状结构，因此您可以在对数时间内通过多次传递来完成此操作:

a  +  b  +  c  +  d
 \   /       \   /
 (a+b)       (c+d)
     \       /
   ((a+b)+(c+d))

而不是 (((a+b)+c)+d)

如果您的操作是可交换的，则可以进一步优化，因为您可以按不同的顺序收集(例如，当这些操作是向量操作时，数据对齐可能很重要)

[*] 你真正想要的数学运算，当然不是像浮点数这样的有效类型的运算。