OpenMP-std::next_permutation

Question

我正在尝试使用 OpenMP 并行化我自己的旅行商问题的 C++ 实现。

我有一个函数可以计算道路 cost() 和向量 [0,1,2,...,N] 的成本，其中 N 是道路的节点数。

在main()，我正在寻找最佳道路：

do
{
    cost();
} while (std::next_permutation(permutation_base, permutation_base + operations_number));

我试图使用 #pragma omp parallel 来并行化该代码，但这只会让它更耗时。有什么方法可以并行化该代码吗？

Answer 1

绝对是。

并行化这些排列问题的最大问题是，为了很好地并行化，您需要 "index" 成任意排列。简而言之，您需要找到第 k 个排列。您可以利用一些很酷的数学属性，您会发现：

std::vector<int> kth_perm(long long k, std::vector<int> V) {
    long long int index;
    long long int next;
    std::vector<int> new_v;
    while(V.size()) {
        index = k / fact(V.size() - 1);
        new_v.push_back(V.at(index));
        next = k % fact(V.size() - 1);
        V.erase(V.begin() + index);
        k = next;
    }
    return new_v;
}

那么您的逻辑可能如下所示：

long long int start = (numperms*threadnum)/ numthreads;
long long int end = threadnum == numthreads-1 ? numperms : (numperms*(threadnum+1))/numthreads;

perm = kth_perm(start, perm); // perm is your list of permutations

for (int j = start; j < end; ++j){
    if (is_valid_tour(adj_list, perm, startingVertex, endingVertex)) {
        isValidTour=true;
        return perm;
    }
    std::next_permutation(perm.begin(),perm.end());
}

isValidTour = false;
return perm;

显然有很多代码，但是并行化它的想法可以从我发布的少量代码中得到体现。您可以像这样想象 "indexing"：

|--------------------------------|
^        ^                   ^
t1      t2        ...        tn

找到第i个排列，让一个线程调用std::next_permutation，直到找到下一个线程的起点。

请注意，您需要将包含底部代码的函数包装在 #pragma omp parallel

中

Answer 2

#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()));
}

OpenMP-std::next_permutation

OpenMP - std::next_permutation

c++

std

openmp

traveling-salesman