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

Question

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

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

其中 key 表示其中包含的向量的 size。

一开始，映射只有一个键（例如[3]），其中包含输入向量（例如{1, 3, 5}和{2, 4, 6}）。

我的函数使用存储在 map 的 最大键 中的 vectors 和 将它们分解为元素较少的所有可能的组合并将它们存储在对应于key的大小新向量（例如 [2] = {1,3} {1,5} {3,5} {2,4} {2,6} {4,6} and [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"）允许安全地访问数据结构，同时允许所有其他操作运行并行。代码工作几乎完美，几乎...因为它在最终结果中遗漏了一些（非常少的）子向量（如果禁用 omp 则成功生成）。

有没有"OMP expert"可以帮我解决这个问题？提前谢谢你。

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

更新

Minimal Complete Verifiable Example

Answer 1

我不确定我是否理解你算法的所有细节，因此我不能完全确定我的分析。该免责声明说，这是我认为会发生的事情：

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

所以，请再次记住我最初的免责声明，但我认为你的算法本质上是错误的，原因有很多，它只是偶然地给出了接近你期望的东西。

最后，我正要向您推荐我的算法，但由于您的代码片段中缺少很多部分，所以我不能。如果你post一个合适的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++;
    }
}

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

OMP and parallel operations on a std::set<...>::iterator

c++

stdmap

openmp

clique-problem