unordered_map에 대한 OpenMP/__ gnu_parallel

Question

내 코드의 일부 지점에서 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도의 반복자는 더 랜덤 액세스 반복자 없다는 것을 :이 과정 내가 OpenMP를 사용하려는하지만 순진 접근 방식은 작동하지 않습니다을 가속화하기 위해. 대신에 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.; 
         }); 

} 

나는 당신의 답변을 기다리고 있습니다.

Answer 1

버킷 인덱스 범위에 걸쳐 루프를 분할 한 다음 요소를 처리하기위한 인트라 버킷 반복기를 만들 수 있습니다. unordered_map은 .bucket_count()이고 버킷 특정 반복자는 begin(bucket_number), end(bucket_number)을 허용합니다. 기본값 max_load_factor()을 1.0에서 수정하지 않고 합리적인 해시 함수를 사용한다고 가정하면 평균 버킷 당 요소 1 개이며 빈 버킷에 너무 많은 시간을 낭비해서는 안됩니다.

Answer 2

임의 반복자를 지원하지 않는 용기와 정식 방법은 명시 적으로 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.