将串行算法并行化

Question

大家好，

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

Queue<Element>;

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

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

每次迭代都依赖于之前的结果（有点儿这个意思）。无法确定此循环将执行多少次迭代。

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

谢谢任何帮助/评论。

- theintz

---

你不能基于原始队列来分配工作吗？比如说，排序很重要吗？原始队列非常短吗？最短和最长运行时间之间会有很大的差异吗？ - Edvard Pedersen

那么，如果按字母顺序添加元素，以 [a,b,c] 为初始列表，a 将评估 [b,c]，b 将评估 [b,c,d,e]（例如）等等？ calculateResultSet 可以使用不完整的数据开始处理吗（即，它可以处理队列直到下一个部分准备好）？我不确定它如何适应 MapReduce 范例，但似乎（也许）所有初始元素都可以开始处理其部分列表，直到 a 完成，然后处理 a 直到 b 完成，依此类推。 - Edvard Pedersen

根据我目前对该应用程序的了解，calculateResultSet() 需要整个集合准备就绪，因此没有办法从半成品集合开始。我需要的是一种将输入附加到 Map 操作的方法，但我不认为这是可能的。 - theintz

你能修改 calculateResultSet 吗？如果不能，并且第 N 次调用 calculateResultSet 需要完整的前 N-1 次调用的结果才能开始处理，那么你只能使用串行执行。如果你可以修改 calculateResultSet，你可以并行化它，或者处理数据直到可用队列的末尾并等待，在前面的执行产生数据时处理数据，并且只有在所有前 N-1 个输出被处理后才返回结果。 - Edvard Pedersen

我看到有两种可以并行化的方式，但它们都涉及将队列分成几个部分进行处理（例如将队列分成N个部分，并在并行运行它们）。但这依赖于队列的b部分能够在a完成之前处理c，因此如果a能够在b处理c之前修改c，那么可能某种形式的推测执行可以起作用，但是不知道calculateResultSet实际上做了什么很难说。 - Edvard Pedersen

Answer 1

也许您可以将calculateResultSet拆分成几个不同的函数，这些函数对整个集合进行操作。这样，您可以将整组数据提供给所有函数，并使每个函数执行单独的操作。一旦所有的函数都完成了，您就可以将所有的结果馈送到另一个函数中，以创建最终的输出。这样就可以使用分布式架构将数据发送到不同的节点，执行操作，最后收集结果。

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

- mchlstckl

Answer 2

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

您需要进行一些实验-有些问题即使有很多近似也很好，而其他问题则完全不行。

- nflacco