OpenMP: Introduction to OpenMP (Part 6)

Eliminating False Sharing in OpenMP

In parallel programming, false sharing refers to a situation where multiple threads unintentionally access different variables that happen to reside on the same cache line. This can cause unnecessary cache invalidations and inter-thread communication, leading to performance degradation. OpenMP provides techniques to mitigate false sharing, such as introducing padding to separate variables that should not share a cache line.

Example:

    
#include 
static long num_steps = 100000;
double step;
#define PAD 8 // assume 64-byte L1 cache line size
#define NUM_THREADS 2

int main() {
  int i, nthreads;
  double pi, sum[NUM_THREADS][PAD];
  step = 1.0 / (double)num_steps;
  omp_set_num_threads(NUM_THREADS);

  #pragma omp parallel
  {
    int i, id, nthrds;
    double x;

    id = omp_get_thread_num();
    nthrds = omp_get_num_threads();

    if (id == 0)
      nthreads = nthrds;

    for (i = id, sum[id][0] = 0.0; i < num_steps; i = i + nthrds) {
      x = (i + 0.5) * step;
      sum[id][0] += 4.0 / (1.0 + x * x);
    }

    for (i = 0, pi = 0.0; i < nthreads; i++)
      pi += sum[i][0] * step;
  }
    
  

In the provided example, padding is introduced by adding an array sum[NUM_THREADS][PAD]. The PAD constant represents the assumed cache line size (e.g., 64 bytes). By separating the elements of the sum array by the size of a cache line, false sharing is minimized. Each thread operates on its own padded element, reducing cache conflicts and unnecessary synchronization.

False sharing can negatively impact performance, but by employing padding techniques, you can eliminate false sharing and improve the scalability and efficiency of your OpenMP programs.

References:

• "Using OpenMP: Portable Shared Memory Parallel Programming" by Barbara Chapman, Gabriele Jost, and Ruud van der Pas
• OpenMP official website: https://www.openmp.org