OpenMP/__ gnu_parallel for unordered_map

在我的代碼中的某個位置，我必須對unordered_map中的所有元素進行操作。爲了加速這個過程中，我想使用OpenMP的，但天真的方法是行不通的：OpenMP/__ gnu_parallel for unordered_map

std::unordered_map<size_t, double> hastTable; 

#pragma omp for 
for(auto it = hastTable.begin(); 
    it != hastTable.end(); 
    it ++){ 
//do something 
}

這樣做的原因是，一個unordered_map的迭代是沒有隨機訪問迭代器。作爲替代方法，我嘗試了for_each上的__gnu_parallel指令。但是，下面的代碼

#include <parallel/algorithm> 
#include <omp.h> 

__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item) 
         { 
          //do something with item.secon 
         });

編譯器（gcc 4.8.2）

g++ -fopenmp -march=native -std=c++11

不平行。使用矢量切換unordered_map並使用相同的__gnu_parallel指令並行運行。

爲什麼在無序映射的情況下不能並行運行？有解決方法嗎？

在下面我給你一些簡單的代碼，這再現了我的問題。

#include <unordered_map> 
#include <parallel/algorithm> 
#include <omp.h> 

int main(){ 

//unordered_map                                  
std::unordered_map<size_t, double> hashTable; 
double val = 1.; 
for(size_t i = 0; i<100000000; i++){ 
    hashTable.emplace(i, val); 
    val += 1.; 
} 
__gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair<const size_t, double> & item) 
         { 
          item.second *= 2.; 
         }); 

//vector                                    
std::vector<double> simpleVector; 
val = 1.; 
for(size_t i = 0; i<100000000; i++){ 
    simpleVector.push_back(val); 
    val += 1.; 
} 
__gnu_parallel::for_each (simpleVector.begin(), simpleVector.end(),[](double & item) 
         { 
          item *= 2.; 
         }); 

}

我期待着您的回答。

來源

2014-09-25 Christian

您可以在存儲區索引範圍內分割一個循環，然後創建一個內部存儲區迭代器來處理元素。 unordered_map具有.bucket_count()和特定於存儲桶的迭代器 - 產生begin(bucket_number)，end(bucket_number)，允許這樣做。假設你沒有修改默認的max_load_factor()從1.0開始，並且具有合理的散列函數，那麼你將每個桶1個元素平均值，不應該在空桶上浪費太多時間。

來源

2014-09-25 09:30:41

謝謝，這可以解決！我猜空桶的主要問題是，處理大量空桶的線程比其他線程快得多，因此會花費一些空閒時間。還是還有其他顧慮？儘管您的想法有效，但我仍然對以上方法對unordered_maps不起作用感興趣。 – Christian 2014-09-25 11:54:57

「......大量空桶會快得多......」 - 對，空桶或過度碰撞桶的集羣，但有一個合理的散列應該平均。至於「爲什麼」 - 就像你在你的問題中所說的那樣，「unordered_map」迭代器不是隨機訪問......這是一個可信的解釋，因爲並行化例程可能假設迭代開銷比每個數據元素有意義處理，所以當迭代進行到幾乎同時完成時，需要一些未知量的偏差來創建連續較小的批次。 – 2014-09-25 15:35:12

當然，如果您知道每個元素的處理時間占主導地位，您可以先將指向該元素的指針複製到一個向量中，然後對其進行並行處理。 – 2014-09-25 15:36:06

與不支持隨機迭代器容器中的典型方法是使用顯式OpenMP任務：

std::unordered_map<size_t, double> hastTable; 

#pragma omp parallel 
{ 
    #pragma omp single 
    { 
     for(auto it = hastTable.begin(); it != hastTable.end(); it++) { 
     #pragma omp task 
     { 
      //do something 
     } 
     } 
    } 
}

這將爲每個迭代一個單獨的任務帶來一些開銷，因此唯一有意義的時候//do something實際上意味着//do quite a bit of work。

來源

2014-09-25 12:07:45

OpenMP/__ gnu_parallel for unordered_map

回答

相關問題