Example A.15.13 data race

Discuss the OpenMP 3.1 API Specifications with the OpenMP Arch. Review Board. (Read Only)
Forum rules
The OpenMP Forums are now closed to new posts. Please visit Stack Overflow if you are in need of help: https://stackoverflow.com/questions/tagged/openmp
Locked
nathanweeks
Posts: 41
Joined: Sun May 17, 2009 6:19 am
Location: Iowa State University
Contact:

Example A.15.13 data race

Post by nathanweeks »

There's a data race in Examples A.15.13c and A.15.13f from the OpenMP 3.1 spec.

Consider the following program that implements bin_search() from Example A_15_13.c, where, to more easily illustrate the problem, the LIMIT macro has been modified so that all generated tasks are final tasks:

Code: Select all

// A_15_13.c
#include <stdio.h>
#include <string.h>
#include <omp.h>
#define LIMIT  -1 /* arbitrary limit on recursion depth */
#define NSTATES 2
void check_solution(char *);
void bin_search (int pos, int n, char *state)
{
   if ( pos == n ) {
      check_solution(state);
      return;
   }
   #pragma omp task final( pos > LIMIT ) mergeable
   {
      char new_state[n];
      if (!omp_in_final() ) {
         memcpy(new_state, state, pos );
         state = new_state;
      }
      state[pos] = 0;
      bin_search(pos+1, n, state );
   }
   #pragma omp task final( pos > LIMIT ) mergeable
   {
      char new_state[n];
      if (! omp_in_final() ) {
          memcpy(new_state, state, pos );
          state = new_state;
      }
      state[pos] = 1;
      bin_search(pos+1, n, state );
   }
   #pragma omp taskwait
}

void check_solution(char *state) {
   #pragma omp critical
   {
      printf("%i: ", omp_get_thread_num());
      for (int i = 0; i < NSTATES; i++)
         printf("%i", state[i]);
      printf("\n");
   }
}
    
int main(void) {
   char state[NSTATES];

   #pragma omp parallel
   #pragma omp master
       bin_search(0, NSTATES, state);

   return 0;
}
When compiled with gcc 4.7.1 and run with two threads, the following differences between executions with one and two threads were observed:
  • $ gcc -std=c99 -fopenmp A_15_13.c
    $ OMP_NUM_THREADS=1 ./a.out
    0: 10
    0: 11
    0: 00
    0: 01
    $ OMP_NUM_THREADS=2 ./a.out
    0: 10
    1: 11
    0: 11
    1: 11
The "final" tasks encountered during the first level of recursion are not included tasks, and in this case were executed concurrently by separate threads accessing the same memory block through different firstprivate "state" pointers.
--
Nathan Weeks
Iowa State University HPC Group
http://weeks.public.iastate.edu/

MarkB
Posts: 808
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Example A.15.13 data race

Post by MarkB »

Hi Nathan,

Many thanks for pointing this out: this had been noted by the OpenMP Language Committee for fixing in the upcoming version of the spec.

Mark.

Locked