c++ - OMP 和 std::set<...>::iterator 上的并行操作

Question

给定一个基于如下所示的 map 的数据结构:

std::map<int, std::set<std::vector<int>>> cliques;

key 表示其中包含的 vector 的大小。

一开始， map 只有一个键(例如[3])，它包含输入 vector (例如 {1, 3, 5} 和 {2, 4, 6})。

我的函数获取存储在映射的最大键中的 vector 并将它们分解到所有具有较少元素的可能组合并将它们存储在与新 vector 的大小相对应的键中(例如[2] = {1,3} {1, 5} {3,5} {2,4} {2,6} {4,6} 和 [1] = {1} {3} {5} {2} {4} {6}) .

我不知道我的解决方案是否最有效，但效果很好。但是由于我的项目旨在处理大量数据，因此我需要并行化我的代码，这导致我进行了以下实现:

/// Declare data structure
std::map<int, std::set<std::vector<int>>> cliques;

/// insert "input" vectors
cliques[5] = {{1, 3, 5, 7, 9}};
cliques[4] = {{1, 2, 3, 4}};

/// set boundaries
int kMax = 5;
int kMin = 1;

/// enable/disable parallel execution
bool parallelExec = true;

/// "decompose" source vectors:
for (int k = kMax; k > kMin; k--)
{
  std::set<std::vector<int>>::iterator it = cliques[k].begin();
  #pragma omp parallel num_threads(max_threads) if(parallelExec)
  {
    for(int s = 0; s < cliques[k].size(); ++s)
    {
      std::vector<int> clique;
      /// maybe should be "omp critical"?
      /// maybe "clique" should be private? (or is it already??) 
      #pragma omp single
      { 
        clique = *it;
      }
      for (int v = 0; v < clique.size(); ++v)
      {
        int& vertex = clique[v];
        std::vector<int> new_clique;
        std::copy_if(clique.begin(), clique.end(), std::back_inserter(new_clique), [vertex](const int& elem) { return elem != vertex; });
        int kNew = k - 1;
        #pragma omp critical
        { 
          cliques[kNew].insert(new_clique);
        }
      }
      #pragma omp single
      {
        it++;
      }
    }
  }
}

/// Display results
for(int i = cliques.size(); i > 0 ; i--)
{
    auto kSet = cliques[i];
    std::cout << "[" << i << "]: ";  
    for(auto& vec : kSet)
    {
        std::cout << "{";
        for(auto& elem : vec)
        {
            std::cout << elem << " ";  
        }
        std::cout << "} ";
    }
    std::cout << std::endl;
}

“omp parallel” 和“omp single”(而不是“omp for”)的使用允许安全地访问数据结构，同时允许所有其他操作并行运行。该代码几乎完美地工作，几乎......因为它在最终结果中遗漏了一些(非常少的)子 vector (如果禁用 omp 则成功生成)。

有没有“OMP专家”能帮我解决这个问题？提前谢谢你。

----------------

更新

Minimal Complete Verifiable Example

Answer 1

我不确定我是否理解您算法的所有细微之处，因此我不能完全确定我的分析。该免责声明说，这是我认为会发生的情况:

1. 您没有并行化处理:您没有跨线程分配工作，您只是在所有线程上复制相同的工作，这些线程互相踩着脚趾将结果写回同一位置。
2. 即使这样也没有正确完成，因为迭代器的增量是通过 omp single nowait 完成的，允许线程在上一次迭代中工作，因为 的值没有同步>it 在此阶段执行。 (注意:没有 nowait 的 omp single 在退出时保护迭代器的增量有一个隐式的 barrier 确保这个线程的一致性 View 值，所以差异只能在当前迭代和前一个迭代之间)
3. 这个 cliques[kNew].insert(new_clique); 确实是所有内容都可能爆炸的地方，因为对同一位置的访问是并发的，这是标准容器不支持的。 (就我的理解而言，这是错误的)

再次重申，请牢记我最初的免责声明，但我认为您的算法本质上是错误的，原因有很多，而且它给出的结果与您的预期相近只是偶然。

最后，我正要向您推荐我的算法，但由于您的代码片段中缺少太多部分，我无法做到。如果您发布适当的 mcve ，那么也许我会。

更新根据您的代码，这是一个可能的并行版本:

for (int k = kMax; k > kMin; k--)
{
    std::set<std::vector<int>>::iterator it = cliques[k].begin();
    for(int s = 0; s < cliques[k].size(); ++s)
    {
        std::vector<int> clique = *it;
        #pragma omp parallel for num_threads(max_threads)
        for (int v = 0; v < clique.size(); ++v)
        {
            int& vertex = clique[v];
            std::vector<int> new_clique;
            std::copy_if(clique.begin(), clique.end(), std::back_inserter(new_clique), [vertex](const int& elem) { return elem != vertex; });
            int kNew = k - 1;
            #pragma omp critical
            cliques[kNew].insert(new_clique);
        }
        it++;
    }
}