爲什麼D中的這個並行代碼縮放非常糟糕？

這是我在C++和D中比較並行性的一個實驗。我使用相同的設計在兩種語言中實現了一種算法（用於網絡中社區檢測的並行標籤傳播方案）：並行迭代器獲取句柄函數（通常爲閉包）並將其應用於圖中的每個節點。爲什麼D中的這個並行代碼縮放非常糟糕？

下面是使用在d迭代器，實現從taskPoolstd.parallelism：

/** 
* Iterate in parallel over all nodes of the graph and call handler (lambda closure). 
*/ 
void parallelForNodes(F)(F handle) { 
    foreach (node v; taskPool.parallel(std.range.iota(z))) { 
     // call here 
     handle(v); 
    } 
}

這是被傳遞手柄功能：

auto propagateLabels = (node v){ 
     if (active[v] && (G.degree(v) > 0)) { 
      integer[label] labelCounts; 

      G.forNeighborsOf(v, (node w) { 
       label lw = labels[w]; 
       labelCounts[lw] += 1; // add weight of edge {v, w} 
      }); 

      // get dominant label 
      label dominant; 
      integer lcmax = 0; 
      foreach (label l, integer lc; labelCounts) { 
       if (lc > lcmax) { 
        dominant = l; 
        lcmax = lc; 
       } 
      } 

     if (labels[v] != dominant) { // UPDATE 
      labels[v] = dominant; 
      nUpdated += 1; // TODO: atomic update? 
      G.forNeighborsOf(v, (node u) { 
       active[u] = 1; 
      }); 
     } else { 
      active[v] = 0; 
     } 

     } 
    };

的C++ 11執行幾乎是相同但是使用OpenMP進行並行化。那麼縮放實驗顯示了什麼？

scaling

在這裏，我檢查弱縮放，加倍輸入圖形的尺寸，同時也增加一倍的線程的數目和測量的運行時間。理想將是一條直線，但當然有一些並行的開銷。我在主函數中使用defaultPoolThreads(nThreads)來設置D程序的線程數。 C++曲線看起來不錯，但D曲線看起來非常糟糕。我做錯了什麼嗎？ D並行性，還是這反映嚴重的並行D程序的可擴展性？

p.s.編譯器標記

爲d：rdmd -release -O -inline -noboundscheck

爲C++：-std=c++11 -fopenmp -O3 -DNDEBUG

PPS。東西一定是真的錯了，因爲d實現並行順序比慢：

enter image description here

購買力平價。對於好奇，這裏有水銀克隆網址，這兩種方案：

來源

2013-07-30 clstaudt

如果你沒有使用openmp，那麼性能會如何？ – greatwolf

從檢查它看起來不像dmd編譯器目前支持openmp。如果一個版本使用openmp，而另一個版本不使用，它看起來不像是一個蘋果對蘋果的比較。 – greatwolf

@greatwolf除非我誤解了你，否則我相信你錯過了這一點。 D沒有OpenMP，但它有'std.parallelism'庫，它提供了類似的並行結構。實際上，D程序在運行時使用了許多內核。 – clstaudt

這很難說，因爲我不完全理解你的算法是如何工作的，但它看起來像你的代碼不是線程安全的，這導致算法運行更多的迭代超過必要的。

我已將此添加的PLP.run末：

writeln(nIterations);

隨着1線程nIterations = 19
隨着10個線程nIterations = 34
隨着100個線程3210

因此，大家可以看到，它需要更長的時間不因爲std.parallelism有些問題，但只是因爲它正在做更多的工作。

爲什麼你的代碼不是線程安全的？

你並行運行的功能是propagateLabels，這已共享，非同步訪問labels，nUpdated，和active。誰知道這是什麼奇怪的行爲造成的，但它不可能是好的。

在開始分析之前，您需要修復算法以確保線程安全。

來源

2013-07-31 17:59:51

良好的觀察。對我而言，有趣的問題是：爲什麼這種行爲與D幾乎完全相同的C++實現有如此不同？我知道線程共享'labels'，'active'和'nUpdated'。這種情況對於C++/OpenMP實現來說是一樣的，它不是問題。 – clstaudt

不幸的是，我對OpenMP並不熟悉，但它從事作業的方式可能與std.parallelism不同，因此OpenMP解決方案可能「正常工作」並且與您正在運行的東西有關。 –

正如Peter Alexander指出的那樣，您的算法似乎是線程不安全的。爲了使其成爲線程安全的，您需要消除可能在不同線程中同時或以未定義順序發生的事件之間的所有數據依賴關係。一種方法是使用WorkerLocalStorage（在std.parallelism中提供）跨線程複製某些狀態，並可能在算法結束時以相對便宜的循環合併結果。

在某些情況下複製此狀態的過程中可以通過寫算法作爲還原和使用std.parallelism.reduce（可能與std.algorithm.map或std.parallelism.map組合），以做繁重自動化。

來源

2013-07-31 19:47:18 dsimcha

爲什麼D中的這個並行代碼縮放非常糟糕？

回答

相關問題