Resolving Data Races

There are a number of ways to resolve a race condition:

Fix a bug in your program
Use local variables instead of global variables
Restructure your code
Change your algorithm
Use reducers
Use a lock

Fix a bug in your program

A race condition can be caused by a bug in the program logic. For instance, a race can occur if a recursive sort calls use an overlapping region, and, therefore, references the same memory location in parallel. The solution is to fix the application.

Use local variables instead of global variables

Consider the following program:

#include <cilk/cilk.h>
#include <iostream>
const int IMAX=5;
const int JMAX=5;
int a[IMAX * JMAX];

int main()
{
   int idx;

   cilk_for (int i=0; i<IMAX; ++i)
   {
     for (int j=0; j<JMAX; ++j)
     {
        idx = i*JMAX + j; // This is a race.
        a[idx] = i+j;
      }
   }
   for (int i=0; i<IMAX*JMAX; ++i)
     std::cout << i << " " << a[i] <<std::endl;
   return 0;
}

This program has a race on the idx variable, because it is accessed in parallel in the cilk_for loop. Because idx is only used inside the loop, it is easy to resolve the race by making idx local within the loop:

int main()
{
// int idx;                  // Remove global
   cilk_for (int i=0; i<IMAX; ++i)
   {
     for (int j=0; j<JMAX; ++j)
     {
       int idx = i*JMAX + j; // Declare idx locally
       a[idx] = i+j;
     }
    }
...
}

Restructure your code

In some cases, you can eliminate the race by a simple rewrite. Here is another way to resolve the race in the previous program:

int main()
{
// int idx;                // Remove global
   cilk_for (int i=0; i<IMAX; ++i)
   {
     for (int j=0; j<JMAX; ++j)
     {
//     idx = i*JMAX + j;    // Don't use idx
       a[i*JMAX + j] = i+j; // Instead,
                           // calculate as needed
      }
    }
...
}

Change your algorithm

One of the best solutions, although not always easy or even possible, is to find an algorithm that partitions your problem such that the parallelism is restricted to calculations that cannot race.

Use reducers

Reducers are designed to be race-free objects that can be safely used in parallel. See Reducers for more information.

Use locks

Locks can be used to resolve data race conditions. The drawbacks to this approach are described in Considerations for Using Locks. There are several kinds of locks, including:

tbb::mutex objects from the Intel® Threading Building Blocks library
system locks on Windows* or Linux* operating systems
atomic instructions that are effectively short-lived locks that protect a read-modify-write sequence of instructions

The following program contains a race on sum, because the statement sum=sum+i both reads and writes sum:

#include <cilk/cilk.h>

int main()
{
   int sum = 0;
   cilk_for (int i=0; i<10; ++i)
   {
      sum = sum + i;  // THERE IS A RACE ON SUM
    }
}

Using a lock to resolve the race:

#include <cilk/cilk.h>
#include <mutex.h>
#include <iostream>

int main()
{
   tbb::mutex mut;
   int sum = 0;
   cilk_for (int i=0; i<10; ++i)
   {
     mut.lock();
     sum = sum + i; // PROTECTED WITH LOCK
     mut.unlock();
   }
   std::cout << "Sum is " << sum << std::endl;

return 0;
}

This example is for illustration only. A reducer is typically a better way to solve this kind of race.