並行嵌套循環與依賴關係

我的問題是關於如何最好地構造我的（C++）代碼來支持並行化耗時的計算。所討論的僞代碼具有以下結構：並行嵌套循環與依賴關係

for a_1(y_1) in A_1 
    for a_2(y_2) in A_2(a_1) 
     ... 
      for a_n(y_n) in A_n(a_1, ..., a_{n-1}) 
       y_n = f(a_1, ..., a_n) 
      y_{n-1} = g_n(Y_n) 
     ... 
    y_1 = g_2(Y_2) 
.

粗略地說，每一個循環迭代元件在一組A_i，連續元件，其都依賴於從以前的迭代反饋y_i。換句話說，要確定下一個a_i，我們必須完成當前的所有計算a_i。此外，內部集合取決於外部迭代。寫在一個遞歸形式：

Iterate(A_i, a_1, ..., a_{i-1}): 
    for a_i(h_i) in A_i 
     Y_i += Iterate(A_{i+1}, a_1, ..., a_i) 
    return g(Y_i) 

Iterate(any, a_1, ..., a_n): 
    return f(a_1, ..., a_n) 

Iterate(A_1)

假定F（...）是一個耗時的計算，並且該反饋函數G（...）是簡單的（快速）。現在，如果所有的集合都是「大」的，那麼這個問題是令人尷尬的可並行化的。目前，我有一個線程池，並將最內層循環的計算拋到池中。問題在於，最內層循環通常是對單例的迭代，所以線程池中只有一個正在運行的線程。我曾考慮過使用期貨將價值返回到外部循環，但這需要期貨期貨等，並且它非常混亂（我認爲）。

我意識到，我上面列出的結構是相當複雜的，所以有一些簡化的情況下，我也感興趣：

a_i(h_i) = a_i;獨立於h_i
A_i(a_1, ..., a_{i-1}) = A_i;獨立於a_1，... a_ {i-1}
g_i = 0;獨立於H_ {i + 1}
所有外部循環都是「大」的;這些集合中元素的數量遠遠大於核心數量。

現在，在實踐中，n < = 3，項目1適用於所有外循環，以及項2-4中的所有持有，所以這種情況下，特解是足夠的。但是因爲我在這裏困擾着提出這個問題，所以我有興趣在可能的情況下獲得關於如何處理更一般性問題的額外複雜性的想法。

編輯：

盪滌第一僞代碼塊，使其與其他一致。由於人們無法理解我的數學符號，這裏是一個更具體的簡單的例子：

#include <cmath> 
#include <iostream> 
#include <vector> 
using namespace std; 

double f(double a1, int a2, double a3){ // Very slow function 
    cout << a1 << ", " << a2 << ", " << a3 << endl; 
    return pow(a1*a3, a2) + a1 + a2 + a3; // just some contrived example 
} 

int g2(const vector<double> &Y3){ // average-ish 
    double sum = 0; 
    for(int i = 0; i < Y3.size(); ++i){ sum += Y3[i]; } 
    return int(sum/(Y3.size() + 1)); 
} 

double g1(const vector<int> &Y2){ // return 1/(min(Y2)+1.0) 
    int imin = 0; int minval = 0; 
    for(int i = 1; i < Y2.size(); ++i){ 
     if(Y2[i] < minval){ 
      imin = i; 
      minval = Y2[imin]; 
     } 
    } 
    return 1.0/double(minval+1.0); 
} 

int main(){ 
    for(double a1 = 0.0, h1 = 10.0; a1 < 1.0; a1 += h1){ // for a1 in A1 
     vector<int> Y2; 
     for(int a2 = 2, h2 = 1; a2 <= (int)(5*a1+10); a2 += h2){ // for a2 in A2(a1) 
      vector<double> Y3; 
      for(double a3 = 6.0, h3 = 1.0; a3 >= (a1+a2); a3 -= 0.5*h3){ // for a3 in A2(a1, a2) 
       h3 = f(a1, a2, a3); 
       Y3.push_back(h3); 
      } 
      h2 = g2(Y3); 
      Y2.push_back(h2); 
     } 
     h1 = g1(Y2); 
    } 

    return 0; 
}

我選擇了隨機值，而且事實證明f只計算了3次。請注意，上面的代碼是不可並行化的。 假設有可能查詢循環的增量是否依賴於較高的循環。

我應該澄清我以後也是如此。當我最初說結構時，我應該說是並行化方法或類似的東西。例如，我第一次嘗試並行化是將最內部的調用f放到線程池中，並在最內部循環的末尾加入。如上所述，當最內層循環僅迭代一個元素時，這不起作用。這實際上並不需要重新調整現有的代碼，如果可能的話，我希望避免它。

來源

2009-10-03 Victor Liu

您可以嘗試以地圖縮減問題（http://en.wikipedia.org/wiki/MapReduce）的形式表達您的問題，使每個層次都嵌套一張地圖縮小作業。 for循環將被轉換爲映射，並且g_i調用到reduce步驟。

你可以試着讓你的僞語言更清晰一點......也許用n = 3或n = 4來表示它爲python程序？你的「for」是一個普通的for循環嗎？如果是這樣，我不太瞭解第一對括號。

我不太確定您的問題是否可以以陳述的形式並行化。如果你說循環的變量取決於以前的迭代，那麼它看起來更像是一個順序問題。

來源

2009-10-03 01:17:06 liori

這正是我要做的。如果您可以安排它，以便每個步驟都可以使用消息語義來完成，它會讓您的生活更輕鬆。 – kyoryu 2009-10-03 01:26:45

如果循環的變量完全依賴於前一次迭代，那麼它是不可並行化的。但有時它只依賴3次迭代之前的值，或者完全不依賴。假設你能夠查詢這樣的依賴關係是否存在，是否有可能比純粹的順序做得更好？事情是，我不想特殊情況下，如果每個for循環是一個單身（或一個小集）或不。 – 2009-10-03 02:11:31

嘗試Haskell的元編譯器。無論代碼是什麼特殊情況，它都可能推導出迭代之間的數據依賴性，並且無需提示即可平行化代碼。然後，您（可能）不必爲每個案例從頭開始明確編寫並行代碼。 – liori 2009-10-03 17:17:05

說實話，你的符號很難乍一看（至少對我來說）。也許如果你可以更明確或可能使用C或C++代碼。你的並行化方法是什麼（pthreads，openmp等）？我懷疑有一個問題是您可以改善您的負載平衡。例如，您可能不想將工作分配給處理時尚卡的線程。

來源

2009-10-03 00:46:11 BobbyShaftoe

我目前使用pthreads。關於符號，是的，我知道。問題在於所有集合都包含不同類型的對象，所以將它們寫成類似C的對象需要很多額外的細節。迭代中的+ =應該意味着「添加到設置」。 – 2009-10-03 00:50:58

如果可能的話，加速這種深度嵌套調用的最佳方式就是不要有深度嵌套調用。

您通常可以重新組織數據或數據中的鏈接以獲取可能爲您節省循環級別的引用，或者您可以找到一種方法將循環依次排列，存儲中間值信息。有時甚至需要創建一個不同的對象結構。

我並不是說這總是有效，但即使刪除一個級別，也會比其他任何嘗試的時間縮短得多。

如果我能理解你的psuedocode，我可能會試試，但我猜你已經抽象出大部分結構，無論如何都需要一個有洞察力的設計。

來源

2009-10-03 00:58:59

並行嵌套循環與依賴關係

回答

相關問題