10

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

减少/折叠是否可并行化？似乎每个计算都取决于前一个。对于某些类型的函数，它只是可并行化的吗？

4

6 回答 6

14

如果您的归约基础操作是关联的*，您可以使用操作顺序和位置。因此，您通常在“收集”阶段具有树状结构，因此您可以在对数时间内分多次完成：

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

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

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

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

于 2008-11-30T22:01:04.647 回答
6

是的，如果运算符是关联的。例如，您可以并行求和一个数字列表：

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)，即执行加法的顺序无关紧要。

于 2008-11-30T22:25:24.330 回答
3

查看 Hadoop 中的合并阶段

http://wiki.apache.org/hadoop/HadoopMapReduce

于 2008-11-30T23:00:52.637 回答
1

不确定您在考虑什么平台/语言，但您可以并行化 reduce 运算符，如下所示：

// Original
result = null;
foreach(item in map) {
    result += item;
}

// Parallel
resultArray = array();
mapParts = map.split(numThreads);
foreach(thread) {
    result = null;
    foreach(item in mapParts[thread]) {
        result += item;
    }
    resultArray += result;    // Lock this!
}
waitForThreads();
reduce(resultArray);

如您所见，并行实现很容易递归。您将映射拆分，在其自己的线程中对每个部分进行操作，然后在这些线程完成后执行另一个 reduce 以将各个部分组合在一起。

（这是Piotr Lesnick 的答案背后的程序化推理。）

于 2008-11-30T22:00:17.190 回答
1

从技术上讲，reduce 与 foldl（左折叠）不同，后者也可以描述为累积。

Jules 给出的例子很好地说明了 reduce 操作：

step 1: 1 + 2 + 3 + 4 
step 2:   3   +   7   
step 3:       10

请注意，在每一步，结果都是一个数组，包括最终结果，它是一个包含一项的数组。

fold-left 如下所示：

step 0: a = 0
step 1: a = a + 1 
step 2: a = a + 2 
step 3: a = a + 3
step 4: a = a + 4
step 5: a

现在显然这些都产生相同的结果，但是当给定非关联运算符（如减法）时 foldl 具有明确定义的结果，而 reduce 运算符则没有。

于 2010-02-09T02:10:23.303 回答
0

这取决于您的减少步骤。在 MapReduce 的 Hadoop 风格实现中，您的 Reducer每个键被调用一次，所有行都与该键相关。

因此，例如，您的 Mapper 可能会接收大量无序的 Web 服务器日志，添加一些元数据（例如，地理编码），并发出以 cookie ID 作为键的 [key, record] 对。然后，每个 cookie ID 将调用您的 Reducer 一次，并为该 cookie 提供所有数据，并可以计算聚合信息，例如访问频率或每次访问查看的平均页面。或者您可以键入地理编码数据，并根据地理位置收集汇总统计数据。

即使你没有进行每个键的聚合分析——事实上，即使你在整个集合上计算一些东西——也有可能将你的计算分成块，每个块都可以输入到 Reducer。

于 2009-01-08T18:43:21.140 回答