Accessing a single vector from multiple threads

General OpenMP discussion

Accessing a single vector from multiple threads

Postby ausairman » Sun Aug 05, 2012 5:40 pm

I have a piece of code that executes over several threads in OpenMP. Basically I have to optimise a number of "species" that are stored in a vector called vector<Species*> species_vec_shuffled. The size of this vector exceeds the number of threads.

If any threads are left waiting once all available species have been allocated to other threads, I want the thread to simply keep working on the current species rather than just waiting. Here is how I have tried to achieve this (simplified for demonstration sake):

Code: Select all
void Trainer<Scheme>::Epoch() {

   /*
    * species_optimisation_started_vec / species_optimisation_ended_vec:
    * Vectors which store a list of booleans indicating whether
    * a given OpenMP thread has begun and ended running optimisation
    * generations on a species, whose index in each vector corresponds
    * to the index in species_vec_shuffled.
    */
   vector<bool> species_optimisation_started_vec(p_world->species_vec_shuffled.size(),false);
   vector<bool> species_optimisation_ended_vec(p_world->species_vec_shuffled.size(),false);

#pragma omp parallel for schedule(dynamic,1)
   for (int l = 0; l < static_cast<int>(p_world->species_vec_shuffled.size()); l++) {
      species_optimisation_started_vec[l] = true; // flag the current species optimisation as started

      // run optimisation until some convergence criterion is met...

      species_optimisation_ended_vec[l] = true; // flag the current species optimisation as ended

      /*
       * At this point optimisation has ended. Check to see if all other
       * species have already been started, but not all have finished.
       * If this is the case, just run generations until it is no longer
       * the case (we have spare time on this thread, so might as well use
       * it)
       */
      while (
         find(species_optimisation_started_vec.begin(),species_optimisation_started_vec.end(),false) == species_optimisation_started_vec.end() && // all generations have started, but...
         find(species_optimisation_ended_vec.begin(),species_optimisation_ended_vec.end(),false) != species_optimisation_ended_vec.end()) // ... not all generations have finished
      {
         // continue running steps (these are very short)
      }
   }
}


This code runs fine, but stalls after a couple of seconds. I suspect it might be getting stuck in the while loop at the bottom but I don't understand how this is logically possible. Maybe someone with experience in parallel threads could help with you this might happen and how I can avoid it? How is it possible that all threads get stuck in the while loop?
ausairman
 
Posts: 12
Joined: Mon Jul 11, 2011 5:40 am

Re: Accessing a single vector from multiple threads

Postby MarkB » Mon Aug 06, 2012 3:43 am

Hi there,

It's hard to say what in practise is actually going wrong, but this is not correct OpenMP for a couple of reasons:

Firstly, there are race conditions, since threads can be reading and writing elements of the boolean vector at the same time: the outcome of these is unspecified.

Secondly, there are no flush operations (memory fences) to guarantee that writes to elements of the vector become visible to other threads before the barrier at the end of the parallel loop.

You could try implementing this using counters which are protected by OpenMP synchronisation constructs. As a first try, you could do something like this:

Code: Select all
void Trainer<Scheme>::Epoch() {

       boolean do_extra;
       int num_started = 0;
       int num_finished = 0; 
       int num_iters = static_cast<int>(p_world->species_vec_shuffled.size());

    #pragma omp parallel for schedule(dynamic,1) private(do_extra)
       for (int l = 0; l < num_iters; l++) {

#pragma omp critical
           num_started++;

          // run optimisation until some convergence criterion is met...

#pragma omp critical
           num_finished++;

          /*
           * At this point optimisation has ended. Check to see if all other
           * species have already been started, but not all have finished.
           * If this is the case, just run generations until it is no longer
           * the case (we have spare time on this thread, so might as well use
           * it)
           */
#pragma omp critical
          do_extra = ( ( num_started == num_iters) && (num_finished < num_iters) );

          while (do_extra)
          {
             // continue running steps (these are very short)
#pragma omp critical
          do_extra = ( ( num_started == num_iters) && (num_finished < num_iters) );
          }

       }
    }


(with apologies for any syntax errors and abuses of C++ conventions!).

If this works, then it may be possible to optimise it further by using OpenMP atomic reads and increments (if your compiler supports OpenMP 3.1), and by running more than one iteration of the the while loop between testing the exit condition.
MarkB
 
Posts: 432
Joined: Thu Jan 08, 2009 10:12 am


Return to Using OpenMP

Who is online

Users browsing this forum: No registered users and 6 guests