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.