Example A.15.13 data race

[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.

[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.