并行化串行算法

Question

Hej 伙计们，

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

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

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

有没有办法并行化像这样的串行算法？我试图想出一种能够提供自己的输入的反馈机制，但是如何并行化它呢？

感谢您的任何帮助/评论

Answer 1

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

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

Answer 2

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

你需要做一些实验 - 有些问题往往很好，即使有很多近似值，有些则根本不好。