OpenMP - Concurrently sorting the rows of a 2d array

Question

I'm trying to parallelize the Heinritz-Hsiao algorithm for finding good solutions to travelling salesman problem. During each step of the algorithm the salesman is on some city i with i=0,1,...,N and he visits the city j closest to i. My approach so far is as follows:

I have a 2d array distances[N][N] which is a lookup table for finding the distance between 2 cities. In a second 2d array i'm trying to sort the cities according to their distance from some reference city i.

#define N 10
float distances[N][N];
int* optimalDestinations[N];

for(int i=0; i<N; i++){
    optimalDestinations[i] = (int *) malloc(N * sizeof(int));

    for(int j=0; j<N; j++){
        optimalDestinations[i][j] = j;
    }
}

//--------------------------------------------------------------

int reference;

//define comparator function for usage in sort
int comparator(const void *p1, const void *p2){
    float d1 = distances[reference][*(int *)p1];
    float d2 = distances[reference][*(int *)p2];

    return d1 - d2;
}

//sorting the row of the optimal destinations matrix concurrently
#pragma omp parallel for private(reference)
for(int i=0; i<N; i++){
    reference = i;
    qsort(&optimalDestinations[i][0], N, sizeof(int), comparator);
}

So in the row i of optimalDestinations the first element should be i because the distance from a city to itself is 0, and then the rest of the cities in ascending order of their distance from city i. I tried a small example N=10 to confirm correctness, however they all appear to be in the same order:

         wrong                       correct
---distances from city 0--- | ---distances from city 9---
9 -- 889.117981             | 9 -- 0.000000
2 -- 177.912125             | 2 -- 711.281982
5 -- 595.591553             | 5 -- 746.731689
3 -- 711.891724             | 3 -- 748.628479
1 -- 462.097321             | 1 -- 758.993103
6 -- 121.480255             | 6 -- 767.745117
8 -- 204.375336             | 8 -- 864.327087
0 -- 0.000000               | 0 -- 889.117981
7 -- 557.984436             | 7 -- 909.726929
4 -- 184.023422             | 4 -- 1000.247253

What am I missing here?

Answer 1

As stated by @jim-cownie, each thread is modifying concurrently the shared global reference variable. In order to avoid data race, you must make it thread private.

You can achieve it with the threadprivate clause:

int reference;
#pragma omp threadprivate(reference)