Barrier Synchronization

Barrier Synchronization — a synchronization pattern where all threads/processes must reach a designated point before any can proceed past it.

How It Works

Thread 0: compute phase 1 → BARRIER → compute phase 2
Thread 1: compute phase 1 → BARRIER → compute phase 2
Thread 2: compute phase 1 → BARRIER → compute phase 2
(all must finish phase 1 before any starts phase 2)

Use Cases

• Iterative Algorithms: Each iteration depends on previous results from all threads (stencil computations, simulations)
• Phase-Based Programs: All workers must complete one phase before starting next
• Data Exchange: After computing partial results, threads need to see each other's results

Implementations

• Centralized Counter: Atomic counter; last thread to arrive signals all others. Simple but doesn't scale
• Tree Barrier: Hierarchical — threads synchronize in pairs, then pairs synchronize. $O(\log n)$ latency
• Butterfly Barrier: Each thread exchanges with partner at each level. Scales well
• OpenMP: `#pragma omp barrier`
• CUDA: `__syncthreads()` (within thread block), cooperative groups for grid-level sync
• MPI: `MPI_Barrier(communicator)`

Performance Impact

• Barriers serialize execution → reduce parallelism
• Minimize the number of barriers and reduce work imbalance between them

Barriers are necessary for correctness but each one is a potential bottleneck — use sparingly and balance the work between them.