3

嘿，伙计们，

我正在将文本挖掘/自然语言应用程序从单核移植到 Map-Reduce 样式系统。其中一个步骤涉及类似于以下的 while 循环：

Queue<Element>;

while (!queue.empty()) {
    Element e = queue.next();
    Set<Element> result = calculateResultSet(e);

    if (!result.empty()) {
        queue.addAll(result);
    }
}

每次迭代都取决于前一次的结果（种类）。无法确定此循环必须执行的迭代次数。

有没有一种方法可以并行化像这样的串行算法？我正在尝试考虑一种反馈机制，它能够提供自己的输入，但是如何将它并行化呢？

感谢您的任何帮助/评论

4

2 回答 2

2

也许你可以分成calculateResultSet几个不同的函数来操作整个集合。这样，您可以为所有函数提供整个集合，并让每个函数执行单独的操作。所有函数完成后，您可以将所有结果提供给另一个函数以创建最终输出。这将允许您将数据发送到不同的节点，执行操作，最后使用分布式架构收集结果。

您还可以研究共享的概念。一个经典的例子是斐波那契数列，其中 xn 取决于 xn-1 和 xn-2。以下是使用 OpenMP 的并行化版本示例：http: //myxman.org/dp/node/182

于 2012-05-15T14:57:32.163 回答
1

Mstoeckli 的建议是一个很好的建议。或者，如果您的数据真的很大，也许可以分割数据集并对集合的各个部分进行循环，然后以预定的迭代次数（或在某种停止标准之后）重新组合数据.

您需要进行一些实验——即使有很多近似值，有些问题往往会很好，有些则根本不行。

于 2012-05-31T22:37:54.067 回答