并行化"MapReduce"中的"Reduce"

Question

我理解Map如何易于并行化 - 每台计算机/ CPU只能在阵列的一小部分上运行.

Reduce/foldl可并行化吗？似乎每个计算都取决于前一个计算.它是否可以与某些类型的函数并行化？

Answer 1

如果您的简化基础操作是关联*,您可以使用操作和地点的顺序.因此,在"聚集"阶段,您通常会有一个树状结构,因此您可以在对数时间内以几个通道执行此操作:

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

代替(((a + b)+ c)+ d)

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

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

Answer 2

是的,如果运营商是关联的.例如,您可以并行汇总数字列表:

step 1: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
step 2:   3   +   7   +   11  +   15
step 3:       10      +       26
step 4:               36

这是有效的,因为(a + b)+ c = a +(b + c),即执行相加的顺序无关紧要.