parallel

**Parallel Stencil Computation** is **numerical computation applying local patterns (stencils) to grid points independently, combining neighboring values according to kernel coefficients, commonly used for solving PDEs via finite differences** — fundamental to scientific computing with excellent parallelism properties. Stencil algorithms expose massive data parallelism. **Stencil Patterns and Kernels** define finite difference coefficients combining neighbors—2D 5-point stencil (center, up, down, left, right), 2D 9-point stencil (8 neighbors), 3D 7-point, etc. Coefficients determine output: u_new[i,j] = c0*u[i,j] + c1*u[i+1,j] + c2*u[i-1,j] + ... **Domain Decomposition** partitions grid among processors: regular decomposition assigns rectangular regions. Interior points need only local data, boundary points need from neighbors. **Halo Exchange** before computation: interior processors send boundary rows/columns to neighbors, receive neighbors' boundaries (halos). Halo width depends on stencil radius. All-to-all exchange is bottleneck in weak scaling. **Memory Layout Optimization** stores data in cache-friendly order: row-major for typical stencils accessing neighbors in same row. Padding to cache line boundaries avoids false sharing. **Time Stepping** iterates stencil application: time step n uses values from n-1, producing n. Multiple time steps amortize communication overhead. Temporal blocking processes multiple time steps before new halo exchange. **GPU Implementation** threads process single grid point, block computes larger region with shared memory for halo elements. Block synchronization ensures halo data availability. **Overlapping Communication and Computation** send interior boundary regions immediately, compute interior while receiving halo, reducing communication latency. **Vectorization** via SIMD within each grid point dimension—stencil computation on multiple points in parallel (row or column vectors). **Stencil Chain Fusion** fuses multiple dependent stencil operations to reduce memory traffic. **Weak Scaling** with fixed problem size per processor maintains constant stencil computation despite increasing processors—limited by halo exchange latency which doesn't decrease. **Strong Scaling** with fixed total size faces diminishing returns when halo exchange dominates computation. **Fundamental limit: stencil communication-to-computation ratio determines scalability—small ratio (many stencil applications) scales well, large ratio (few applications) doesn't** requiring algorithmic or hardware improvements.