并行化串行算法

我上移植从单核文本挖掘/自然语言应用到地图，减少风格系统的工作。其中一个步骤涉及一个类似于此的while循环：

Queue<Element>; 

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

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

每次迭代都取决于之前（种类）的结果。没有办法确定这个循环必须执行的迭代次数。

有没有一种方法来并行化一个串行算法，比如这个？我试图想到一个反馈机制，它可以提供自己的输入，但是如何去平行化呢？

感谢所有帮助/附注

来源

2012-05-02 t.heintz

是否有任何理由不能根据原始队列对工作进行分区？例如。排序很重要，原始队列很短，在最短和最长的运行时间之间会有很大的差异吗？ –

Edvard，函数calculateResultSet（）查看整个输入集，在此步骤开始之前需要完整计算。 –

所以，按照字母顺序添加元素，并用'[a，b，c]'初始列表，'a'将评估'[b，c]'，'b'评估'[b，c，d ，e]'（例如）等？ 'calculateResultSet'可以用不完整的数据开始处理（即它可以处理队列直到下一个部分准备好）？我不确定它如何适合MapReduce范例，但似乎所有初始元素都可以开始处理它们的部分列表，直到'a'结束，然后处理'a'直到'b'结束，等等。 –

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

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

来源

2012-05-15 14:57:32 mchlstckl

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

你需要尝试一点 - 即使有很多近似值，一些问题也可能没有问题，其他问题根本就没有问题。

来源

2012-05-31 22:37:54 nflacco

并行化串行算法

回答

相关问题