Threads competition problem

General OpenMP discussion

Threads competition problem

Postby mathmax » Sat Dec 02, 2017 9:47 pm

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];
                        }
                }
mathmax
 
Posts: 9
Joined: Mon Nov 27, 2017 8:47 pm

Re: Threads competition problem

Postby MarkB » Mon Dec 04, 2017 10:13 am

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 .
MarkB
 
Posts: 768
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Threads competition problem

Postby mathmax » Mon Dec 04, 2017 3:50 pm

Hi MArkB,

Thank you again very much.
It make sense.

I am working on it now.
mathmax
 
Posts: 9
Joined: Mon Nov 27, 2017 8:47 pm


Return to Using OpenMP

Who is online

Users browsing this forum: No registered users and 8 guests