OpenMP：深度優先搜索的好策略

我正在編寫一個C++程序，它對關閉的Knight's tours執行蠻力搜索。代碼是here。OpenMP：深度優先搜索的好策略

我想使用OpenMP對其進行並行化。我的問題是要創建足夠的並行度。目前，我的代碼the relevant portion看起來像這樣

#pragma omp parallel for reduction(+:count) if (depth==4) 
    for (size_t i=0;i<g.neighbours[last].size();i++){ 
    auto n = g.neighbours[last][i]; 
    // See if n can be used to extend or complete the tour

的if (depth==4)是我的企圖，以確保不會有太多並行任務的創建，但是，從另一方面足夠的設置是爲了讓所有的處理器忙。設置depth==2不會更改程序的運行時間。

這似乎沒有工作。對於3x12的問題，在我的雙核處理器上，OpenMP版本消耗的CPU總時間大約爲130s，而沒有OpenMP的單線程版本需要大約40s的CPU時間。

我很感謝有關如何更好地使用OpenMP的建議或者爲何不適合解決此問題的原因。

更新：感謝@Zulan我有一個newer version使用OpenMP任務，具有更快的順序性能以及良好的並行化。

來源

2016-04-23 Jyotirmoy Bhattacharya

首先，讓我們來超快速瀏覽一下您的應用程序花費了時間，通過使用perf：

perf record ./knights_tour_omp 3 12 
perf report 

# Overhead Command   Shared Object  Symbol                       
# ........ ............... ................... ................................................................................................. 
# 
    53.29% knights_tour_om libc-2.19.so   [.] malloc                      
    23.16% knights_tour_om libc-2.19.so   [.] _int_free                      
    10.31% knights_tour_om libc-2.19.so   [.] _int_malloc                     
    4.78% knights_tour_om knights_tour_omp  [.] _Z13continue_tourIZ4mainEUlRKSt6vectorIiSaIiEEE_EmRK5GraphS4_RKS0_IcSaIcEEiiRT_.constprop.119 
    2.64% knights_tour_om libc-2.19.so   [.] __memmove_ssse3_back                   
    1.48% knights_tour_om libc-2.19.so   [.] malloc_consolidate

你的應用程序花費它所有的時間分配和釋放內存。雖然有一些報告顯示malloc is is not fully locked，但它似乎並不很好地並行。

它不需要太多進一步的調查，以找出這是由於每次迭代複製visited和path向量造成的。幸運的DFS有很好的屬性，你不一定要做到這一點，你可以重複使用的狀態，並恢復它：

visited[n] = 1; 
path.emplace_back(n); 
count += continue_tour(g, path, visited, depth+1,remain-1, cb); 
visited[n] = 0; 
path.pop_back();

然而，對於並行循環，你需要做的工作副本的每個線程，因此您需要爲原始行爲制定一個單獨的路徑。

這個小小的改變已經將串行運行時間從22秒降低到2.65秒。進一步2線程下降到2.0秒。有一個加速，但它不是很好 - 爲什麼？爲了說明這一點，我使用了4個線程（在一個足夠大的系統上）。以下是score-p中記錄的隨時間變化的應用程序的執行情況，如Vampir所示。

紅色是實際工作中，藍色是一種隱性障礙，這意味着線程空轉。似乎總是有3個或1個活動線程。原因很簡單：主板上的大部分位置都有4個或2個鄰居，但其中一個已經訪問過，所以此循環迭代即時完成。所以實際的工作是在循環的3次或1次迭代中。對於2個線程來說這是一個特別糟糕的匹配。使用3個線程，運行時間降至1.7秒

注意：所有在E5-2690 @ 2.90 GHz上使用gcc 5.3的時間都沒有turbo。沒有采取任何措施來彌補運行時間的差異。

考慮到單個循環暴露了非常糟糕的並行性，您可能會試圖嵌套並行循環。我鼓勵你嘗試一下，但我認爲這樣做不會奏效。我認爲在這種情況下任務可以很好地工作，因爲任務可以產生其他任務。因此，您可以將每個遞歸步驟產生爲任務，並讓OMP運行時找出一個好的調度。但請務必將其限制在某個depth，以便任務不會太短。

我想強調使用工具的重要性：試圖找出沒有性能分析工具的性能問題就像在沒有調試器的情況下計算出錯誤。 perf已經可以用於Linux，並且它的基本形式非常易於使用。然而它非常強大（儘管高級用法可能有一些缺陷）。

附加說明：藉助OpenMP，通常可以嘗試使用不同的編譯器。例如，對於（固定）任務代碼，gcc不會再擴展到超過4個線程，而intel編譯器/ omp運行時甚至可以提高24個線程的加速比。

來源

2016-04-23 13:51:24 Zulan

感謝您的詳細分析。我分離出了我複製路徑和訪問的並行級別以及突變它們的順序級別。現在OpenMP版本的CPU時間僅比非OpenMP版本略多。新代碼位於https://gist.github.com/jmoy/2151e6d7070a6ce18aa9298fbe050062 –

@JyotirmoyBhattacharya在遞歸之外移動'omp parallel' /'omp single'。我甚至不知道嵌套的task/parallel/single的語義是什麼。它確實混淆了任務運行時間。 – Zulan

順便說一句：雖然，與gcc它仍然不能擴展超過4個線程的小例子，intel編譯器/ omp運行時甚至可以擴展到24線程。 – Zulan

OpenMP：深度優先搜索的好策略

回答

相關問題