1

给定一个基于如下图的数据结构：

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

其中键表示其上包含的向量的大小。

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

我的函数获取存储在地图最大键中的向量，并将它们分解为具有较少元素的所有可能组合，并将它们存储在与新向量的大小相对应的键中（例如）。[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 专家”能够帮助我解决这个问题？先感谢您。

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

更新

最小完整可验证示例

4

1 回答 1

1

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

  1. 您没有并行化处理：您没有跨线程分配工作，您只在所有线程上复制相同的工作，这些线程相互踩踏以将结果写回相同的位置。
  2. 即使这样也没有正确完成，因为迭代器的增量是用 an 完成的，因为在这个阶段omp single nowait没有对 的值执行同步，所以线程可以在前一次迭代上工作。it（注意：omp single没有nowait在退出时保护迭代器的增量具有隐式barrier确保该值的线程一致视图，因此差异只能在当前迭代和前一个迭代之间）
  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++;
    }
}
于 2018-04-10T07:49:54.270 回答