Barrier Synchronization

How a barrier works

Imagine eight runners on a track. They are told: run one lap, then wait at the finish line until everyone has finished. When the last runner crosses, all eight start lap two together. That's a barrier — a meeting point where every participant pauses until the slowest catches up.

In code, a barrier is initialized with a participant count N and exposes one operation:

barrier_wait(b):
    atomic_inc(b.count)
    if b.count < N:
        block_until_released()
    else:
        b.count = 0
        release_all()

The Nth arriving thread doesn't block — it triggers the release. Threads 1 through N-1 wake from their wait, and all N proceed to the next phase concurrently.

The bulk-synchronous parallel (BSP) model formalizes this: a computation is a sequence of supersteps, each consisting of local compute, then communication, then a global barrier. Every parallel framework that follows BSP — OpenMP parallel for, MapReduce shuffles, Pregel graph iterations, MPI collective communication — uses barriers as its fundamental phase separator.

Centralized vs tree vs dissemination

Variant	Latency	Memory traffic	Best for
Centralized counter	O(N)	O(N) on one cache line	N ≤ 8 threads
Sense-reversing	O(N)	O(N) on one cache line	Reusable, small N
Tree barrier	O(log N)	O(N) distributed	16 - 256 threads
Dissemination	O(log N)	O(N log N) total	Lowest latency, no atomics
Tournament	O(log N)	O(N) distributed	Wakeup-fairness sensitive
Hardware barrier (BlueGene)	O(1)	Wired	HPC supercomputers
GPU __syncthreads	~1 cycle	Hardware	Within a thread block

The centralized counter on a hot cache line is fine until thread count rises. At 8 threads, the cache line bounces 8 times — maybe 300 ns total. At 64 threads, contention serializes: 64 × ~100 ns RMW = 6 µs, and the wake is bottlenecked by the kernel's futex implementation. Tree barriers split arrivals into log₂N rounds where each thread only contends with one partner, so the cache traffic stays bounded.

The sense-reversing trick

A naive barrier resets the counter to N on release, then expects the next phase to count up from zero again. But what if a fast thread races into the next barrier before slow threads have finished waking up? It increments a counter that should still be in "reset" state, and the next barrier's arrival logic is off-by-one. Reuse breaks.

Sense reversal solves this without resetting. The barrier maintains a global sense bit (initially 0); each thread maintains a local sense bit (also 0). On wait, the last arrival toggles the global sense — all waiters see global ≠ local and wake. Each thread then flips its local sense for the next round. There is no "reset" phase — the bit flip itself is the release signal, and it cannot be undone by a confused early-arriver.

// Sense-reversing barrier (each thread has a local_sense)
barrier_wait(b, local_sense):
    local_sense = !local_sense
    if atomic_dec(b.count) == 0:
        b.count = N             // safe — no waiter cares yet
        b.sense = local_sense   // release: triggers wake on all waiters
    else:
        while b.sense != local_sense:
            cpu_relax()
    return local_sense

When to reach for a barrier

• BSP-style parallel loops. Iterate over a grid in parallel; barrier; iterate again with updated neighbor data. Stencil computations, cellular automata, finite-element solvers all live here.
• GPU thread-block coordination. __syncthreads() (CUDA), barrier() (OpenCL) — ensures all threads in a block have written shared memory before others read it.
• MPI applications. MPI_Barrier synchronizes processes across nodes — often used for timing fairness rather than correctness, since most collectives already imply ordering.
• Phased benchmarks. All threads start the measurement window simultaneously. Without a barrier, the first thread's warm-up bias dominates the result.
• Pipeline-stage synchronization. Producers finish stage K, all wait, consumers start stage K — a barrier between stages keeps the data fresh.

Pseudo-code

// Centralized barrier — simple but contended.
struct Barrier:
    count: atomic int = N
    generation: atomic int = 0

barrier_wait(b):
    local_gen = b.generation
    if atomic_dec(b.count) == 0:
        // Last to arrive — release everyone
        b.count = N
        atomic_inc(b.generation)        // wake all waiters
        return
    // Wait for generation to change
    while b.generation == local_gen:
        cpu_pause()

JavaScript (Atomics-based barrier)

// Shared barrier across Web Workers.
const sab = new SharedArrayBuffer(8);
const state = new Int32Array(sab);
// state[0] = count remaining; state[1] = generation

const N = 4;
Atomics.store(state, 0, N);

function barrierWait() {
  const myGen = Atomics.load(state, 1);
  const remaining = Atomics.sub(state, 0, 1) - 1;
  if (remaining === 0) {
    // Last arrival: reset count, bump generation, wake everyone
    Atomics.store(state, 0, N);
    Atomics.add(state, 1, 1);
    Atomics.notify(state, 1, +Infinity);
  } else {
    // Wait until generation changes
    while (Atomics.load(state, 1) === myGen) {
      Atomics.wait(state, 1, myGen);
    }
  }
}

// Each worker:
for (let phase = 0; phase < numPhases; phase++) {
  computePhase(phase);
  barrierWait();
}

C with pthreads

#include <pthread.h>

#define N 8
pthread_barrier_t barrier;

void *worker(void *arg) {
    for (int phase = 0; phase < NUM_PHASES; phase++) {
        compute(phase);
        // All N threads wait; last to arrive releases all.
        int rc = pthread_barrier_wait(&barrier);
        // rc == PTHREAD_BARRIER_SERIAL_THREAD for exactly one thread —
        // the rest get 0. Useful for "have one thread reset shared state."
        if (rc == PTHREAD_BARRIER_SERIAL_THREAD) {
            update_global_data();
        }
        pthread_barrier_wait(&barrier);  // wait for the resetter
    }
    return NULL;
}

int main() {
    pthread_barrier_init(&barrier, NULL, N);
    pthread_t threads[N];
    for (int i = 0; i < N; i++)
        pthread_create(&threads[i], NULL, worker, NULL);
    for (int i = 0; i < N; i++) pthread_join(threads[i], NULL);
    pthread_barrier_destroy(&barrier);
}

Common pitfalls

• Wrong N. Initialize the barrier with N=8 but spawn 7 workers — every barrier call blocks forever waiting for the 8th. Always tie the count to the actual thread set, and verify with assertions.
• Reusing a non-reusable barrier. Some implementations support only one wait per init. POSIX pthread_barrier is reusable; ad-hoc counter-based barriers usually are not unless sense-reversed.
• Destroying with arrivals in flight. Calling pthread_barrier_destroy while threads are still inside their wait call is undefined. Join all participants before destroy.
• Forgetting that ALL threads must call wait. If even one worker exits early without participating, the rest deadlock. Either reduce N, or have the exiting thread call wait one last time before leaving.
• Calling barrier_wait from inside a critical section. The barrier blocks; the mutex stays held; other threads can't make progress to arrive at the barrier. Classic deadlock.
• Assuming exit order. Threads release simultaneously, but scheduler chaos means actual run order is arbitrary. Don't write code that depends on which thread "wakes first."

Performance: who waits for whom

The defining performance property of a barrier: the slowest thread sets the pace. If 7 threads finish a phase in 10 ms and one straggler takes 30 ms, the barrier holds everyone for 30 ms. With many phases, this imbalance compounds:

• Load imbalance of 10% over 1000 phases → 10× total slowdown in pathological cases
• OS jitter (a kernel timer fires on one core) → that core's thread arrives late every time
• NUMA effects — cross-socket cache misses make some threads slower than others on the same task

The solution is rarely a faster barrier — barriers themselves are cheap (microseconds at worst). The solution is load balancing: dynamic work-stealing, fine-grained tasks, oversubscription so OS jitter is absorbed by spare threads. Or eliminating the barrier altogether — task graphs (Cilk, TBB, Taskflow) express dependencies without global synchronization, letting fast threads start the next phase immediately.

For micro-benchmarks: 8-thread pthread_barrier_wait on a desktop CPU is ~500 ns. 64-thread on a server CPU is ~5 µs centralized, ~1 µs with a tree barrier. GPU __syncthreads is effectively free — about one instruction issue cycle. The hardware barriers on BlueGene/Q ran in under 100 ns globally across 100K cores.