openMp：並行化std :: map迭代

有一些關於這個問題的文章，但他們都不滿足我。我沒有openMp 3.0支持，我需要在地圖上並行化迭代。我想知道，如果這個解決方案將工作或沒有：openMp：並行化std :: map迭代

auto element = myMap.begin(); 

#pragma omp parallel for shared(element) 
for(int i = 0 ; i < myMap.size() ; ++i){ 
MyKeyObject * current_first = nullptr; 
MyValueObject * current_second = nullptr; 
#pragma omp critical 
{ 
    current_first = element->first; 
    current_second = element->second; 
    ++element; 
} 

// Here I can use 'current' as in a usual loop 
}

所以我使用的for循環，以確保公正的線程將處理同樣相同數量的地圖元素。這是一個正確的猜測還是會失敗？

PS：我上的Visual Studio 2012的工作，所以如果你有一個關於如何使我的編譯器支持的OpenMP 3.0的提示，這也將解決我的問題..

來源

2015-05-29 Arcyno

OpenMP 3.0有什麼好處呢？如果你想在Visual Studio中使用OpenMP 3.0，那麼你需要一個集成到Visual Studio中的新編譯器（例如英特爾編譯器）。 –

@Zboson，OpenMP 3.0具有明確的任務，並允許在地圖上進行迭代並行執行，如show [here]（http://stackoverflow.com/a/22936165/1374437）。 –

@HristoIliev，謝謝你，我認爲任務可能是正確的方法，因爲它是（std :: map）作爲二叉樹實現，據我瞭解。是時候學習OpenMP中的任務了。 –

由於您在關鍵部分訪問並迭代了共享對象element，因此您的方法可以正常工作。不管這對於性能是否有利，您都必須進行測試。以下是您可能需要考慮的另一種方法。讓我稱之爲「快進」方法。

讓我們假設你想通過myMap.size() iteartors使用OpenMP 2.0

#pragma omp parallel 
{ 
    size_t cnt = 0; 
    int ithread = omp_get_thread_num(); 
    int nthreads = omp_get_num_threads(); 
    for(auto element = myMap.begin(); element !=myMap.end(); ++element, cnt++) { 
     if(cnt%nthreads != ithread) continue; 
     foo(element->first, element->second); 
    } 
}

每個線程運行，以做到這一點並行

for(auto element = myMap.begin(); element !=myMap.end(); ++element) { 
    foo(element->first, element->second); 
}

你可以做到這一點。但是，每個線程只能調用foomyMap.size()/num_threads。您的方法只能通過myMap.size()/num_threads迭代器運行。但是，它需要在每次迭代中使用關鍵部分。

快進的方法是有效的，只要時間到「快進」，通過來確定nthreads itererators要少得多，則時間foo，即：

nthreads*time(++elements) << time(foo)

然而，如果該時間foo是在迭代的時間，而foo是讀/寫內存，foo可能是內存帶寬的限制，並且不會隨着線程的數量擴展。

來源

2015-06-01 08:41:02

好辦法！（但沒有人回答我的解決方案..是否好？） – Arcyno

爲什麼這不起作用？我在通常的循環中使用'omp parallel for' – Arcyno

@Arcyno，我把它拿回來，'omp parallel for'可以工作，但如果它是好的（性能明智）或者不好，你將不得不測試。將您的方法與我的「快進」方法進行比較將會很有趣。 –

你的做法是行不通的 - 因爲這是一個概念性問題和一些錯誤的混合體。

[bug]你總是會錯過第一個元素，因爲你做的第一件事是增加元素迭代器。
[bug]所有線程都會迭代整個地圖，因爲元素迭代器不共享。順便說一句，目前還不清楚你的代碼中共享變量'part'是什麼。
如果您讓元素共享，那麼訪問它的代碼（在關鍵部分之外）將看到它當前指向的任何內容，而不管線程是什麼。你最終會不止一次地處理一些元素，有些則完全沒有。

因爲地圖迭代器不是隨機訪問，所以沒有簡單的方法使用迭代器並行訪問地圖。您可能想要手動分割鍵，然後使用不同線程上的鍵集的不同部分。

來源

2015-05-29 13:46:08

你是對的，但是我對這篇文章所做的修改呢？ – Arcyno

您的更改只解決了我提到的第一個問題。他們仍然不會給你並行迭代。事實上，關鍵部分甚至不是必需的，因爲你的元素迭代器每個線程都是唯一的，所以沒有爭用。 –

再一次你是對的！現在，與共享元素？ – Arcyno

這不是對您的問題的直接回答，但我會盡力爲您節省一些未來的「OpenMP with Visual Studio」經驗。

Microsoft C/C++編譯器僅支持OpenMP 2.0。由於OpenMP內置於編譯器內核中，因此無法支持OpenMP 3.0或更高版本，並且不是附加軟件包（除非有人提出了外部源到源轉換引擎），而且Microsoft似乎不適用有興趣在推動他們自己的解決方案時提供進一步的OpenMP支持（見下文）。因此，您應該獲得與Visual Studio集成的英特爾C/C++編譯器或獨立編譯器（如GCC或PGI C/C++編譯器）。

如果您正在爲Windows專門開發，那麼您可能需要放棄OpenMP並使用Concurrency Runtime，特別是使用PPL。 PPL附帶Visual Studio 2012及更新版本，併爲STL中的一些算法提供數據和任務並行等價物。你感興趣的是concurrency::parallel_for_each()，這是std::for_each()的並行版本。它可以與前向迭代器一起工作，但不像隨機迭代器那樣有效。但是你必須確保處理地圖的一個元素需要至少一千條指令，否則並行化將不會有好處。

如果您的目標是跨平臺兼容，那麼Intel Threading Building Blocks（簡稱Intel TBB）是PPL的替代品。它提供了tbb::parallel_do()算法，該算法專門設計用於使用正向迭代器。關於每個貼圖元素的工作量的警告同樣適用。

來源

2015-05-29 14:51:35

openMp：並行化std :: map迭代

回答

相關問題