OpenMP - std :: next_permutation

Question

Я пытаюсь распараллеливать собственную реализацию C++ для Traveling Salesman с использованием OpenMP.

У меня есть функция для расчета стоимости дороги cost() и вектора [0,1,2, ..., N], где N - количество узлов дороги.

В main(), я пытаюсь найти лучший путь:

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

Я пытался использовать #pragma omp parallel распараллелить этот код, но это только сделало его более трудоёмким. Есть ли способ распараллеливать этот код?

Answer 1

#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 и вычисляете затраты. Затем вы управляете permutation_base с помощью next_permutation. Вам действительно нужно дождаться окончательных вычислений затрат, прежде чем вам будет разрешено манипулировать массивом, потому что в противном случае вычисление стоимости будет неправильным. Таким образом, все это не будет работать на отдельных потоках.

Одним из возможных решений могло бы быть сохранение нескольких копий вашего массива 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()); 
} 

Answer 2

Определенно.

Большая проблема с распараллеливанием этих проблем перестановки заключается в том, что для того, чтобы правильно распараллелить, вам нужно «проиндексировать» произвольную перестановку. Короче говоря, вам нужно найти 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; 

Очевидно, что есть много кода, но идея распараллеливать его можно захватить небольшим кодом, который я опубликовал. Вы можете визуализировать «индексацию», как это:

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

Найти ю перестановку и пусть нить вызов std::next_permutation до тех пор, пока не найдет начальную точку следующего потока.

Обратите внимание, что вы хотите, чтобы обернуть функцию, которая содержит нижний код #pragma omp parallel