c++ - 在 OpenMP for 循环中更新 HashMap

Question

我正在尝试将 openmp 用于 for 循环，我试图在其中插入/更新 HashMap (std::unordered_map)

Hash map和key实际上是一个类的成员，所以我分配了指针来表示它们的地址。Key也是一个全局函数返回的hash值。

以下似乎是执行此操作的最简单方法，但 HashMap 未正确更新。有些事情是错误的，但我不确定如何解决。提前致谢。

void MyClass::ProcessBuffer(void)
{
    omp_set_num_threads(4);
    std::unordered_map<unsigned long long,unsigned int>* hashptr=&m_sequencehash;
    std::vector<std::string>* bufferptr=&m_buffer;
    unsigned int sizevec=m_kmer_size;
    size_t i;
    #pragma omp parallel for
    for (i=0; i<READSTR_BUF_SIZE;++i)
    {
        ++(*hashptr)[_hash((*bufferptr)[i],sizevec)];
    }

}

Answer 1

解决此问题的最简单方法是为每个线程创建一个新映射，然后按顺序将它们缩减为单个映射。这是一个经典的 map-reduce 场景。

int s = omp_get_num_threads();
std::unordered_map<unsigned long long,unsigned int> res[s];

// Map step
#pragma omp parallel for
for (i=0; i<READSTR_BUF_SIZE;++i)
{
    int t = omp_get_thread_num();
    res[t][_hash((*bufferptr)[i],sizevec)]++;
}

// Reduce step
for (int i=0; i < s; i++) {
    for (auto r : res[s]) {
        (*hashptr)[r.first] += r.second;
    }
}

同时执行缩减可能很危险，因为您仍然必须同时访问同一个 map 。如果您不知道 map 的实现，就无法确定这是安全的。

或者，您可以通过将不同的散列区间放入不同的桶中来划分不同映射之间的散列值。这将防止不同的线程在 reduce 步骤中访问相同的哈希值。然而，在一个小数据集上，很难找到具有少量桶的良好分区函数。与串行方法相比，使用过多的桶可能会产生显着的开销。