Parallelize Algorithm with OpenMP in C++

Question

my problem is this:

I want to solve TSP with the Ant Colony Optimization Algorithm in C++. Right now Ive implemented a algorithm that solve this problem iterative.

For example: I generate 500 ants - and they find their route one after the other. Each ant starts not until the previous ant finished.

Now I want to parallelize the whole thing - and I thought about using OpenMP.

So my first question is: Can I generate a large number of threads that work simultaneously (for the number of ants > 500)?

I already tried something out. So this is my code from my 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();
        }

    }

And this is the code in my Ant class that is "critical" because each Ant reads and writes into the same Matrix (pheromone-Matrix):

 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;
         }
     }

 }

So for some reasons the omp parallel for loop wont work on these range-based loops. So this is my second question - if you guys have any suggestions on the code how the get the range-based loops done im happy.

Thanks for your help

you don't need number of threads larger than your hardware parallelisation, which is number of logical CPU cores on your system — Andriy Tylychko

Zulan Zulan · Accepted Answer · 2018-10-28T09:18:27

So my first question is: Can I generate a large number of threads that work simultaneously (for the number of ants > 500)?

In OpenMP you typically shouldn't care how many threads are active, instead you make sure to expose enough parallel work through work-sharing constructs such as omp for or omp task. So while you may have a loop with 500 iterations, your program could be run with anything between one thread and 500 (or more, but they would just idle). This is a difference to other parallelization approaches such as pthreads where you have to manage all the threads and what they do.

Now your example uses ordered incorrectly. Ordered is only useful if you have a small part of your loop body that needs to be executed in-order. Even then it can be very problematic for performance. Also you need to declare a loop to be ordered if you want to use ordered inside. See also this excellent answer.

You should not use ordered. Instead make sure that the ants know there number beforehand, write the code such that they don't need a number, or at the very least that the order of numbers doesn't matter for ants. In the latter case you can use omp atomic capture.

As to the access to shared data. Try to avoid it as much as possible. Adding omp critical is a first step to get a correct parallel program, but often leads to performance problems. Measure your parallel efficiency, use parallel performance analysis tools to find out if this is the case for you. Then you can use atomic data access or reduction (each threads has their own data they work on and only after the main work is finished, data from all threads is merged).

Parallelize Algorithm with OpenMP in C++

1 Answers