並行迭代器

Question

我正在爲並行代碼（使用OpenMP）設計一個C++數據結構（用於圖）。

假設我想有一個方法可以遍歷所有元素（節點）。當然，這個迭代將被並行化。

爲此可以使用迭代器嗎？迭代器應該如何看起來像啓用並行訪問？你會建議在這種情況下使用迭代器還是反對？

Answer 1

OpenMP並行循環不能很好地與迭代器一起玩。你需要在你的圖表類上實現一個索引機制（operator[]）。

如果您確實想使用OpenMP 3.0迭代器支持，請確保您有隨機訪問迭代器。將它作爲指向節點或邊的指針是最簡單的選擇。

Answer 2

這是讀寫器問題的變體。

這取決於該結構是否可變。如果沒有，那就離開你，儘可能多地並行閱讀。

但是，如果它是可變的，那麼迭代器可能會與對結構所做的更改發生衝突。例如，迭代器可能會到達正在被刪除的元素。一種解決方法是爲每個迭代器創建一個只讀，不可變的結構副本，但是那個迭代器在迭代器創建後不會註冊對結構所做的任何更改。第二種解決方案是製作寫時複製實現，這將導致對結構的所有寫入操作都會創建一個新對象，並且當前正在運行的迭代器在舊操作上運行。

您需要決定寫入該結構對程序的意義，算法明智，然後適當地實現讀取/寫入鎖定。

Answer 3

讓我展開我的評論。除非您的目標是跨平臺兼容性，並且您希望代碼也可以編譯並使用MS Visual C++，否則您可以通過使用顯式OpenMP任務來抵消爲圖對象提供「線性」迭代器的複雜性。 OpenMP 3.0中引入了顯式任務（因此即使在2012年，它也不受MSVC的支持，它只符合更早的規範）。任務是可以並行執行的代碼塊。它們由task結構創建：

... other code ... 
#pragma omp task 
{ 
    ... task code ... 
} 
... other code ... 

每當執行流程達到顯着的區域，創建一個新的任務對象，並放入任務隊列。然後，在某些時間點，空閒線程從隊列中抓取一個任務並開始執行。任務與OpenMP章節非常相似，因爲它們繼承了它們的環境，並且它們可以按不同於序列版本代碼的順序運行。

使用任務可以實現遞歸算法，也可以輕鬆使用不提供隨機迭代器的C++容器。對於二叉樹的例子遍歷可以這樣用任務來執行：

// Helper routine to traverse a tree and create one task for each node 
void traverse_and_make_tasks(tree_node *tn) 
{ 
    if (tn == NULL) 
     return; 

    // Create a task to process the node 
    #pragma omp task 
    { 
     very_long_computation(tn->value); 
    } 

    traverse_and_make_tasks(tn->left); 
    traverse_and_make_tasks(tn->right); 
} 

... main code ... 

// Disable dynamic teams 
omp_set_dynamic(0); 

#pragma omp parallel 
{ 
    #pragma omp single nowait 
    { 
     traverse_and_make_tasks(tree->root_node); 
    } 
} 

（禁用動態團隊是必要的，以防止OpenMP的運行時間從太聰明，執行parallel區域的單螺紋）

這是一個非常常見的任務模式，稱爲單個/系列生產商。只要執行進入parallel區域，一個線程就會執行single構造中的代碼。它將這三個根節點稱爲traverse_and_make_tasks。 traverse_and_make_tasks步行三個併爲每個節點創建一個任務。 task構造僅在parallel區域（靜態範圍）內使用或在從parallel區域（動態範圍）內部調用（直接或間接）代碼中使用時才起作用。當traverse_and_make_tasks行走樹時，它會產生排隊的任務。在parallel區域末尾有一個隱式任務調度點，這大致意味着執行不會在區域末尾恢復，直到所有任務都已執行完畢。也可以使用#pragma omp taskwait在並行區域內顯示明確的點。它的工作方式與barrier類似 - 執行「阻止」，直到處理完所有任務。

另一種常見模式是並行生產者其中並行生成任務。示例代碼上面可以很容易地轉變成由一個簡單的變形例的平行生產上traverse_and_make_tasks：

void traverse_and_make_tasks(tree_node *tn) 
{ 
    if (tn == NULL) 
     return; 

    #pragma omp task 
    traverse_and_make_tasks(tn->left); 
    #pragma omp task 
    traverse_and_make_tasks(tn->right); 

    // Create a task to process the node 
    very_long_computation(tn->value); 
} 

這的代碼版本在每個節點生成兩個任務 - 一個用於處理所述左後代，一個用於處理所述右後裔。如果這是串行代碼，它會從下往上遍歷樹。然而，在並行的情況下，任務排隊會導致或多或少的從上到下的遍歷。

使用任務還有很多其他可能的情況。你也可以用它們在非遞歸的情況下，處理容器沒有提供隨機迭代器，由工作共享需要構建for：

typedef container_type::iterator citer; 

container_type container; 
... push some values in the container ... 

#pragma omp parallel 
{ 
    #pragma omp single nowait 
    { 
     for (citer it = container.begin(); it != container.end(); it++) 
     #pragma omp task 
     process(*it); 
    } 

    #pragma omp taskwait 

    // process more 
    #pragma omp single nowait 
    { 
     for (citer it = container.begin(); it != container.end(); it++) 
     #pragma omp task 
     process_more(*it); 
    } 
} 

這個例子也說明了parallel區域內使用明確的任務同步。

Answer 4

如果它們是樹木，那麼你可能會想要在歐拉巡迴遍歷​​上比「迭代器」更多地考慮掃描。 http://en.wikipedia.org/wiki/Euler_tour_technique

我希望我有斯捷潘諾夫的書在我面前。我記得他簡短地觸及它。

Answer 5

我在Java中遇到了完全相同的問題。我已經實現的解決方案使用了hashmaps的hashmap。我還是不明白，爲什麼在標準庫，不要讓我們做多線程的迭代器...... 你可以閱讀我的問題，我的回答（用鏈接的Java代碼）一起在這裏：

Scalable way to access every element of ConcurrentHashMap<Element, Boolean> exactly once