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.