我正在尝试使用 OpenMP 并行化我自己的旅行商问题的 C++ 实现。
我有一个函数来计算道路成本 cost()
和 vector [0,1,2,...,N],其中 N 是道路的节点数。
在 main()
中,我试图找到最佳路径:
do
{
cost();
} while (std::next_permutation(permutation_base, permutation_base + operations_number));
我试图使用 #pragma omp parallel
来并行化该代码,但这只会让它更耗时。
有什么方法可以并行化该代码吗?
最佳答案
#pragma omp parallel
不会自动将计算分配到单独的线程上。如果你想划分计算,你需要额外使用#pragma omp for
,否则空洞计算会进行多次,每个线程一次。例如下面的代码打印“Hello World!”在我的笔记本电脑上四次,因为它有 4 个内核。
int main(int argc, char* argv[]){
#pragma omp parallel
cout << "Hello World!\n";
}
如果您简单地编写#pragma omp parallel
,您的代码也会发生同样的事情。您的代码被执行多次,每个线程执行一次。因此你的程序不会更快。如果你想将工作分配给线程(每个线程做不同的事情),你必须使用类似 #pragma omp parallel for
的东西。
现在我们可以查看您的代码。它不适合并行化。让我们看看为什么。您从数组 permutation_base
开始并计算成本。然后用 next_permutation
操作 permutation_base
。在允许操作数组之前,您实际上必须等待完成的成本计算,否则成本计算将是错误的。所以整个事情不会在单独的线程上工作。
一个可能的解决方案是,保留数组 permutation_base
的多个拷贝,并且每个可能的排列基数仅运行所有排列的一部分。例如:
vector<int> permutation_base{1, 2, 3, 4};
int n = permutation_base.size();
#pragma omp parallel for
for (int i = 0; i < n; ++i) {
// Make a copy of permutation_base
auto perm = permutation_base;
// rotate the i'th element to the front
// keep the other elements sorted
std::rotate(perm.begin(), perm.begin() + i, perm.begin() + i + 1);
// Now go through all permutations of the last `n-1` elements.
// Keep the first element fixed.
do {
cost()
}
while (std::next_permutation(perm.begin() + 1, perm.end()));
}
关于c++ - OpenMP - std::next_permutation,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33595236/