Распараллелить алгоритм с OpenMP в C ++ - PullRequest
Новая
       12

Распараллелить алгоритм с OpenMP в C ++

0 голосов
/ 27 октября 2018

Моя проблема заключается в следующем:

Я хочу решить TSP с помощью алгоритма Ant Colony Optimization в C ++.Прямо сейчас я реализовал алгоритм, который решает эту проблему итеративно.

Например: я генерирую 500 муравьев - и они находят свой маршрут один за другим.Каждый муравей запускается до тех пор, пока не закончится предыдущий муравей.

Теперь я хочу распараллелить все это - и я подумал об использовании OpenMP.

Итак, мой первый вопрос: могу ли я сгенерироватьбольшое количество потоков, которые работают одновременно (для числа муравьев> 500)?

Я уже что-то пробовал.Итак, это мой код из моего main.cpp: 

 #pragma omp parallel for       
    for (auto ant = antarmy.begin(); ant != antarmy.end(); ++ant) {
        #pragma omp ordered
        if (ant->getIterations() < ITERATIONSMAX) {
            ant->setNumber(currentAntNumber);
            currentAntNumber++;
            ant->antRoute();
        }

    }

И этот код в моем классе Ant является «критическим», потому что каждый Ant читает и записывает в одну и ту же матрицу (феромон-матрица):

 void Ant::antRoute()
 {
     this->route.setCity(0, this->getStartIndex());
     int nextCity = this->getNextCity(this->getStartIndex());
     this->routedistance += this->data->distanceMatrix[this->getStartIndex()][nextCity];
     int tempCity;
     int i = 2;
     this->setProbability(nextCity);
     this->setVisited(nextCity);
     this->route.setCity(1, nextCity);
     updatePheromone(this->getStartIndex(), nextCity, routedistance, 0);

     while (this->getVisitedCount() < datacitycount) {
         tempCity = nextCity;
         nextCity = this->getNextCity(nextCity);
         this->setProbability(nextCity);
         this->setVisited(nextCity);
         this->route.setCity(i, nextCity);
         this->routedistance += this->data->distanceMatrix[tempCity][nextCity];
         updatePheromone(tempCity, nextCity, routedistance, 0);
         i++;
     }

     this->routedistance += this->data->distanceMatrix[nextCity][this->getStartIndex()];
     // updatePheromone(-1, -1, -1, 1);
     ShortestDistance(this->routedistance);
     this->iterationsshortestpath++;
}

void Ant::updatePheromone(int i, int j, double distance, bool reduce)
{

     #pragma omp critical(pheromone) 

     if (reduce == 1) {
        for (int x = 0; x < datacitycount; x++) {
             for (int y = 0; y < datacitycount; y++) {
                 if (REDUCE * this->data->pheromoneMatrix[x][y] < 0)
                     this->data->pheromoneMatrix[x][y] = 0.0;
                 else
                    this->data->pheromoneMatrix[x][y] -= REDUCE * this->data->pheromoneMatrix[x][y];
             }
         }
     }
     else {

         double currentpheromone = this->data->pheromoneMatrix[i][j];
         double updatedpheromone = (1 - PHEROMONEREDUCTION)*currentpheromone + (PHEROMONEDEPOSIT / distance);

         if (updatedpheromone < 0.0) {
            this->data->pheromoneMatrix[i][j] = 0;
            this->data->pheromoneMatrix[j][i] = 0;
         }
          else {
             this->data->pheromoneMatrix[i][j] = updatedpheromone;
             this->data->pheromoneMatrix[j][i] = updatedpheromone;
         }
     }

 }

Так что по некоторым причинам параллельная omp для цикла не будет работать на этих основанных на диапазоне циклах. Итак, это мой второй вопрос - если у вас, ребята, есть какие-то предложения по коду, как сделать циклы на основе диапазона Я счастлив.

Спасибо за вашу помощь

1 Ответ

0 голосов
/ 28 октября 2018

Итак, мой первый вопрос: могу ли я создать большое количество потоков, которые работают одновременно (для числа муравьев> 500)?

В OpenMP вам, как правило, не важно, сколько потоков активно, вместо этого вы обеспечиваете достаточную параллельную работу с помощью таких структур разделения работы, как omp for или omp task. Таким образом, в то время как у вас может быть цикл с 500 итерациями, ваша программа может быть запущена с любым количеством между одним потоком и 500 (или более, но они будут просто простаивать). В этом отличие от других подходов распараллеливания, таких как pthreads, где вы должны управлять всеми потоками и тем, что они делают.

Теперь ваш пример использует ordered неправильно. Упорядочивание полезно только в том случае, если у вас есть небольшая часть тела цикла, которую нужно выполнить по порядку. Даже тогда это может быть очень проблематичным для производительности. Также вам нужно объявить цикл равным ordered, если вы хотите использовать ordered внутри. Смотри также этот отличный ответ .

Вы не должны использовать заказанный. Вместо этого убедитесь, что муравьи знают об этом number заранее, напишите код так, чтобы им не требовалось число или, по крайней мере, порядок чисел для муравьев не имеет значения. В последнем случае вы можете использовать omp atomic capture.

Что касается доступа к общим данным. Старайтесь избегать этого как можно больше. Добавление omp critical является первым шагом для получения правильной параллельной программы, но часто приводит к проблемам с производительностью. Измерьте свою параллельную эффективность, используйте инструменты параллельного анализа производительности, чтобы выяснить, так ли это для вас. Затем вы можете использовать атомарный доступ к данным или их сокращение (каждый поток имеет свои собственные данные, с которыми он работает, и только после завершения основной работы данные всех потоков объединяются).

...