Page 1 of 1

Threads competition problem

PostPosted: Sat Dec 02, 2017 9:47 pm
by mathmax
Hi,
I am thinking use the Openmp to parallel the below code.

But notice that in the last line "neighbors[max_idx].dist = z[i];" each thread will share the same variable ,i.e.neighbors.
In that case if the openmp is used, at a given time several threads will write different value to the same location, which causes a competition.

So does that the below code cann't be using openmp parallel the code?

Any hint will be appreciated.

Code: Select all
for( i = 0 ; i < rec_count ; i++ ) {
                        float max_dist = -1;
                        int max_idx = 0;
                        for( j = 0 ; j < k ; j++ ) {
                                if( neighbors[j].dist > max_dist ) {
                                        max_dist = neighbors[j].dist;
                                        max_idx = j;
                                }
                        }
                        if( z[i] < neighbors[max_idx].dist ) {
                                strcpy(neighbors[max_idx].entry, sandbox +i*REC_LENGTH);
                                neighbors[max_idx].dist = z[i];
                        }
                }

Re: Threads competition problem

PostPosted: Mon Dec 04, 2017 10:13 am
by MarkB
Hi again!

mathmax wrote:But notice that in the last line "neighbors[max_idx].dist = z[i];" each thread will share the same variable ,i.e.neighbors.
In that case if the openmp is used, at a given time several threads will write different value to the same location, which causes a competition.


Yes, you are right, this would a race condition, so you cannot simply parallelise this loop.

Here's a sketch of possible parallel implementation:

  • Give each thread a temporary copy of the neighbours array by adding an extra dimension of size the number of threads (You can use omp_get_max_threads() to safely allocate sufficient memory before the parallel region starts).
  • Each thread executes the loop on part of the input array using its own neighbour list.
  • Copy all the points in the threads neighbour lists to a new input array of size (k * no. of threads) (can be done in parallel).
  • Run the loop again sequentially using the new input array

If you keep track of the i values along with the per-thread neighbour lists you can avoid doing the strcpys until the last stage.

This should give reasonable performance as long as the number of records is much larger than k .

Re: Threads competition problem

PostPosted: Mon Dec 04, 2017 3:50 pm
by mathmax
Hi MArkB,

Thank you again very much.
It make sense.

I am working on it now.