将一个向量过滤到另一个并行向量上

Question

我正试图将一个向量过滤成另一个并行向量。我目前的设置产生太多的开销，所以它甚至比串行更慢。具体:

#pragma omp parallel for collapse(2)
for(int i = 0 ; i < a.size() ; i++){
for(int j = 0 ; j < a.size() ; j++){
if(meetsConditions(a[i], a[j])){
std::vector<int> tmp = {i, j};
#pragma omp critical
b.push_back(tmp);
}
}
}

我保存索引，因为我想以后在满足条件的每一对上运行一个单独的串行函数:

for(auto element : b){
doSmth(a[element[0]], a[element[1]]);
}

我尝试用一个新的空向量，将其大小调整为a.size()*a.size()，使用原子子句中的第三个索引分配元素，当它被增加时，但这会导致数据竞争(除非我看到它错误)。我该如何着手解决这个问题呢?也许使用列表能让它更简单?或者直接存储指向这些元素的指针会更容易?我对c++很陌生，所以我不太确定我怎么才能让它工作。

Answer 1

假设a.size()足够大，我将只并行化第一个循环(不崩溃)，对每个线程使用本地b_local，并在最后将所有b_local连接到共享的b。

#pragma omp parallel
{
std::vector<std::vector<int>> b_local;
#pragma omp for
for (int i = 0 ; i < a.size() ; i++){
for(int j = 0 ; j < a.size() ; j++){
if(meetsConditions(a[i], a[j])){
std::vector<int> tmp = {i, j};
b_local.push_back(tmp);
}
}
}
#pragma omp critical
b.insert(b.end(),b_local.begin(),b_local.end()); 
}

这应该更有效，因为critical节现在在循环之外，每个线程只遇到一次。b_local对每个线程都是私有的，所以更新时不需要critical。

但实际上我不确定是否值得并行化它，除非meetsConditions()有很多计算。

Answer 2

我希望这段代码运行得更慢，因为你有一个临界段，它将强制b.p push_back(tmp)在单个线程中运行。

也许想要删除临界区，而直接将结果写入已经适当大小的b，例如:

vector<std::vector<int>> b;
b.resize(a.size() * a.size());
#pragma omp parallel for collapse(2)
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < a.size(); j++) {
if (meetsConditions(a[i], a[j])) {
std::vector<int> tmp = { i, j };
b.at((i*a.size())+j) = tmp;
}
}
}