並行化串行算法

我上移植從單核文本挖掘/自然語言應用到地圖，減少風格系統的工作。其中一個步驟涉及一個類似於此的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

並行化串行算法

回答

相關問題