线程使用OpenMP任务争夺类中的全局变量

Question

我目前正试图使用OpenMP来找出无向图中是否存在大小为k的集团，以使代码运行得更快。

这是我试图并行的代码：

bool Graf::doesCliqueSizeKExistParallel(int k) {
if (k > n) return false;
clique_parallel.resize(k);
bool foundClique = false;
#pragma omp parallel
#pragma omp single
for (int i = 0; i < n; i++) {
if (degree[i] >= k - 1) {
clique_parallel[0] = i;
#pragma omp task
doesCliqueSizeKExistParallelRecursive(i + 1, 1, k, foundClique);
}
}
return foundClique;
}
void Graf::doesCliqueSizeKExistParallelRecursive(int node, int currentLength, int k, bool & foundClique) {
for (int j(node); j < n; j++) {
if (degree[j] >= k - 1) {
clique_parallel[currentLength - 1] = j;
bool isClique=true;
for(int i(0);i<currentLength;i++){
for(int l(i+1);l<currentLength;l++){
if(!neighbors[clique_parallel[i]][clique_parallel[l]]){isClique=false; break;}
}
if(!isClique) break;
}
if (isClique) {
if (currentLength < k)
doesCliqueSizeKExistParallelRecursive(j + 1, currentLength + 1, k, foundClique);
else {
foundClique= true;
return;
}
}
}
}
}

这里的问题可能是，变量degree、neighbors、clique_parallel都是全局的，当某个线程试图写入其中一个变量时，另一个线程会来写入该变量，而不是正确的线程。我尝试的唯一解决方案是传递这三个变量作为函数的副本，这样每个线程都有自己的变量，但它不起作用。我尽量不使用#pragma omp taskwait，因为这只是顺序算法，不会有任何加速。目前我迷失了方向，不知道如何解决这个问题(如果这是一个问题的话(，也不知道还应该尝试什么，或者如何避免在线程之间共享这些变量。

这是类别Graf:

class Graf {
int n; // number of nodes
vector<vector<int>> neighbors; //matrix adjacency
vector<int> degree; //number of nodes each node is adjacent to
vector<int> clique_parallel;
bool directGraph;
void doesCliqueSizeKExistParallelRecursive(int node, int currentLength, int k, bool & foundClique);
public:
Graf(int n, bool directGraph = false);
void addEdge(int i, int j);
void printGraf();
bool doesCliqueSizeKExistParallel(int k);
};

所以我的问题是，在这段代码中，线程正在为全局变量而斗争，或者可能是其他问题？任何帮助都是有用的，如果您对代码有任何问题，我会回答。

Answer 1

您观察到omp task wait将其转化为顺序算法是正确的。事实上更糟糕的是：它将深度优先搜索算法有效地变成了广度优先，它将遍历整个空间。

好的。首先使用task group，它在生成任务的for循环结束时有一个隐含的任务等待。

接下来，让您的任务返回false，或者返回找到的某个集团的值。

现在，关键是：一旦一个任务找到了解决方案，就调用omp cancel task group，这将使您离开for循环，您可以保留找到的值！这种取消将杀死该级别的所有其他任务(以及它们递归派生的任务(。现在，递归的魔力开始发挥，所有的组都被取消了。

我曾经为另一个递归搜索问题解决过这个问题，但我相信你可以将其转化为你的问题：https://pages.tacc.utexas.edu/~eijkhout/pcse/html/omp-examples.html#Treetraversal