OpenMP: Atomic, Critical, Locks, and Barriers

Module 15

The Pthreads tools, OpenMP style

So far, OpenMP has mostly let us avoid synchronization. reduction combined private results, and the implicit barriers at the ends of parallel and for kept phases in order. Not every problem fits those patterns. Sometimes threads really must update the same data, or wait for each other in the middle of a region.

We built these tools ourselves with Pthreads: mutexes in Module 9 and barriers in Module 11. Today we meet OpenMP’s versions, following §5.8 of Pacheco and Malensek. The book builds them up with a long message-passing program. We will use three shorter ones:

  • omp_counter.c — Count to ten million on one shared counter, five ways.
  • omp_phases.c — Module 11’s barrier example, rewritten with # pragma omp barrier.
  • omp_buckets.c — Sort values into ten buckets, with one critical section or a lock per bucket.

First program: five ways to count

Every thread adds 1 to the same count, ten million times in all. Here are the four ways of protecting that update, side by side:

/* critical: one thread at a time runs the next statement */
#   pragma omp critical
count++;

/* atomic: one indivisible update of one memory location */
#   pragma omp atomic
count++;

/* lock: we set and unset it ourselves, like a mutex */
omp_set_lock(&count_lock);
count++;
omp_unset_lock(&count_lock);

/* reduction: no sharing at all until the end */
#   pragma omp parallel for num_threads(thread_count) reduction(+: count)

The first three each sit inside the same parallel for loop. In omp_counter.c, each method has its own short function, along with a fifth that leaves count++ unprotected. main runs all five and prints a table.

The new pieces

atomic (§5.8.7) protects a single update of one variable. It allows only statements of a few simple forms:

x++;   ++x;   x--;   --x;   x <op>= <expression>;

Here <op> is one of + * - / & ^ | << >>, and the expression must not use x. Many processors have a special instruction that loads, changes, and stores a value in one step. atomic can use that instruction instead of a lock, which is why it has the potential to be fast. Only the update of x is protected. In x += y++;, the change to y is not.

OpenMP locks (§5.8.8) work like a Pthreads mutex:

Pthreads OpenMP
pthread_mutex_t m; omp_lock_t lock;
pthread_mutex_init(&m, NULL) omp_init_lock(&lock)
pthread_mutex_lock(&m) omp_set_lock(&lock)
pthread_mutex_unlock(&m) omp_unset_lock(&lock)
pthread_mutex_destroy(&m) omp_destroy_lock(&lock)

As with a mutex, one thread initializes the lock before the threads use it and destroys it after they are done.

Build and run

Predict before you run: Which method will be fastest? Which will be slowest? Will the unprotected count be correct?

Compile this program with -O0, no optimization, instead of the -O2 we usually use:

gcc -Wall -O0 -fopenmp -o omp_counter omp_counter.c
./omp_counter 1
./omp_counter 4

We turn optimization off here so that each count++ really reads and writes memory, as the source code says. The reason is part of today’s lesson, and we will come back to it below.

Record your 4-thread results:

Method Count Correct? Time (s)
unprotected
critical
atomic
lock
reduction

The unprotected count should be far below ten million. Two threads read the same value, both add 1, and both write it back, so one update is lost. This is the shared-total race from Module 9, now losing millions of updates.

Discuss:

  • Why can critical and the lock take longer with four threads than with one?
  • On my test machine, atomic was roughly eight times faster than critical with four threads. Why might it be faster?
  • reduction beats all three. What does it do differently?

With one shared counter, only one thread can do useful work at a time. The others wait, and handing the lock or critical section from thread to thread costs time. Four threads take turns more slowly than one thread working alone.

atomic can often use a single hardware instruction for the whole update, with no separate lock to acquire and release. It is still one shared location, so the threads still contend for it, but each turn is much cheaper.

reduction does not share the counter during the loop. Each thread counts privately and combines once at the end. When a reduction fits, it is the right tool. Synchronization is for updates that cannot wait until the end.

Try it: turn optimization back on

Recompile with -O2 and run again:

gcc -Wall -O2 -fopenmp -o omp_counter omp_counter.c
./omp_counter 4

Is the unprotected count still wrong? It may now look correct, and fast.

At -O2, the compiler is allowed to assume that no other thread changes count without synchronization. So it may keep each thread’s count in a register and write it to memory only at the end of the loop. The program is just as wrong as before: it is still a data race, and C gives it no defined behavior. The compiler just happened to turn it into something that looks right here. A correct answer is not proof of a correct program. This is also why synchronization must be visible to the compiler, through atomic, critical, a lock, or reduction, and not just “probably fine” timing.

Second program: an explicit barrier

The implicit barriers we have used come at the end of a construct. Sometimes threads need to wait for each other in the middle of a parallel region (§5.8.6):

#   pragma omp barrier

No thread continues past it until every thread in the team has reached it. Here is the core of omp_phases.c, Module 11’s neighbor-sum example in OpenMP:

#   pragma omp parallel num_threads(THREAD_COUNT)
{
    int id = omp_get_thread_num();
    values[id] = id + 1;

#   pragma omp barrier

    int neighbor = (id + 1) % THREAD_COUNT;
    neighbor_sums[id] = values[id] + values[neighbor];
}

Compare it with the Pthreads version from Module 11, pth_phases.c. The OpenMP version has no thread function, no ID array, no pthread_barrier_init with a participant count, and no destroy. The team is the set of participants.

gcc -Wall -O2 -fopenmp -o omp_phases omp_phases.c
./omp_phases

The sums should be 3, 5, 7, 5, as in Module 11. Try it: Comment out the barrier, recompile, and run several times. Some runs will show a thread that read its neighbor’s value before the neighbor wrote it.

Every thread in the team must reach the same barriers. A barrier inside an if that only some threads take would leave the others waiting forever.

Third program: when one critical section is too many

omp_buckets.c sorts two million values from 0 to 999 into ten buckets: values 0–99 go in bucket 0, values 100–199 in bucket 1, and so on. Adding a value to a bucket takes two steps:

void append(bucket_t *b, int v) {
    b->items[b->count] = v;
    b->count++;
}

Why can’t we use atomic here? Two threads could both store at the same position before either increases count. Both statements must happen together, and atomic can only protect one simple update.

Version 1: one critical section

The easy fix is a critical section:

#   pragma omp parallel for num_threads(thread_count)
for (int i = 0; i < n; i++) {
    int v = value(i);
#   pragma omp critical
    append(&buckets[v / 100], v);
}

This is correct, but think about what it protects. Thread 0 adding to bucket 3 has nothing to do with thread 1 adding to bucket 7, yet the critical section makes them take turns.

It is worse than that. All unnamed critical sections in a program share one lock. If another part of the program also used # pragma omp critical for something unrelated, it would block this one too. You can give a critical section a name, such as # pragma omp critical(buckets), and differently named sections can run at the same time. But names are fixed when the program is compiled. We cannot write ten names for ten buckets, or a thousand names for a thousand buckets, and pick one while the program runs.

Version 2: a lock per bucket

Locks solve that. A lock is data, so each bucket can carry its own (§5.8.9):

typedef struct {
    int count;
    int items[MAX_N];
    omp_lock_t lock;
} bucket_t;
#   pragma omp parallel for num_threads(thread_count)
for (int i = 0; i < n; i++) {
    int v = value(i);
    bucket_t *b = &buckets[v / 100];
    omp_set_lock(&b->lock);
    append(b, v);
    omp_unset_lock(&b->lock);
}

Now two threads wait for each other only if they want the same bucket. Main initializes all ten locks before the loops and destroys them at the end. The program checks each version against a serial calculation, comparing every bucket’s count and the sum of its values.

gcc -Wall -O2 -fopenmp -o omp_buckets omp_buckets.c
./omp_buckets 1
./omp_buckets 2
./omp_buckets 4

Both versions should print correct. Record the times:

Threads One critical section (s) A lock per bucket (s)
1
2
4

Discuss: Why might the lock version be a little slower with one thread? Why does it pull ahead with more threads? What would happen to the lock version if almost every value fell in the same bucket?

Which one should you use?

Section 5.8.10 suggests this order:

  1. If a reduction fits, use it. No synchronization is needed during the loop.
  2. If the update is one simple statement on one variable, use atomic. It is likely the fastest form of mutual exclusion.
  3. If you protect a block of code, use critical. It is easy to use, and it is often about as fast as a lock. Give it a name if unrelated critical sections should not block each other.
  4. If you need to protect pieces of data chosen while the program runs, such as one bucket, one queue, or one bank account, use locks.

Caveats

Section 5.8.11 warns about three mistakes:

  • Do not mix kinds of protection for the same variable. An atomic update of x in one place and a critical update of x in another do not exclude each other.
  • Do not nest critical sections carelessly. If a function containing # pragma omp critical is called from inside another unnamed critical section, the thread waits for a lock it already holds, forever. That is a deadlock.
  • Take locks in the same order everywhere. If thread A holds lock 1 and waits for lock 2, while thread B holds lock 2 and waits for lock 1, both wait forever. Named critical sections have the same problem.

Also, no construct guarantees fairness. A waiting thread is not promised a turn in any particular order.

Check your understanding

  1. Which of these can be protected with atomic? (a) sum += x * y; (b) x = x * 2 + 1; (c) count += 1; (d) a[i] = a[i] + a[j];
  2. Why did the unprotected count look correct at -O2? Does that make it correct?
  3. Why did reduction beat atomic, even though both are correct?
  4. What do the OpenMP lock functions correspond to in Pthreads?
  5. Why can’t named critical sections give each bucket its own protection?
  6. What happens if only some threads of a team reach a # pragma omp barrier?
  7. Two unrelated parts of a program each use an unnamed # pragma omp critical. What problem might that cause, and how do you fix it?
    1. Yes, x <op>= expression, where the expression does not use sum. (b) No: it is not one of the allowed forms. (c) Yes. (d) Yes, as a[i] += a[j];, provided j is not i. Only the update of a[i] is protected.
  2. The compiler kept each thread’s count in a register and stored it once, so fewer updates collided. It is still a data race with undefined behavior. The answer looked right by luck.
  3. With atomic, every one of ten million updates touches the same shared location. With reduction, each thread counts privately and the copies are combined only once per thread.
  4. omp_lock_t and omp_init_lock, omp_set_lock, omp_unset_lock, and omp_destroy_lock correspond to pthread_mutex_t and its init, lock, unlock, and destroy functions.
  5. Names are fixed at compile time. The bucket a thread needs is only known while the program runs.
  6. The threads that arrive wait forever for the rest.
  7. They share one lock, so a thread in one section blocks threads that want the other, even though the sections are unrelated. Give them different names, or use locks.
Back to top