6.1.3False-Sharing

False Sharing Cache Performance Issues in Parallel Programming

Introduction

Presentation by L. V. Kale, University of Illinois Urbana, 2018.

Problem Overview

The goal is to find the index of the largest value in an array. The initial code leads to performance issues due to constant access to a critical section, causing serialization:

curMax = MINUS_INFINITY;
maxIndex = -1;
#pragma omp parallel for
for(i=0; i<n; i++){
    #pragma omp critical {
        if (a[i] > curMax) {
            curMax = a[i];
            maxIndex = i;
        }
    }
}

Improved Maximum Index Strategy

Each loop iteration accesses the critical section. To reduce contention, only enter the critical section after the condition check, though this risks changes to curMax:

curMax = MINUS_INFINITY;
maxIndex = -1;
#pragma omp parallel for
for(i=0; i<n; i++){
    if (a[i] > curMax)
        #pragma omp critical {
            if (a[i] > curMax) {
                curMax = a[i];
                maxIndex = i;
            }
        }
}

Better Strategy with Privatization

Privatize maxIndex so each thread maintains its own copy using an array maxIndices[] indexed by thread ID:

int* maxIndices = new int[p]; // p is the number of threads
#pragma omp parallel {
    int id = omp_get_thread_num();
    maxIndices[id] = 0;
    #pragma omp for
    for(i=0; i<n; i++)
        if (a[i] > a[maxIndices[id]])
            maxIndices[id] = i;
}

After computation, find the global maxIndex:

maxIndex = maxIndices[0];
for(i=1; i<p; i++)
    if (a[maxIndices[i]] > a[maxIndex])
        maxIndex = a[maxIndices[i]];
curMax = a[maxIndex];

Problem: Cache Traffic Increase

Threads writing to the same cache line (e.g., maxIndices[i]) lead to excessive cache traffic, known as thrashing. This occurs despite threads writing to distinct variables.

Solution: Padding

Introduce padding to ensure each thread writes to its own cache line:

typedef struct{
    int index;
    char padding[28];
} PaddedIndex;

Update maxIndices[] to use the padded structure based on cache line size:

maxIndices[id].index;

Recap: False Sharing

• Definition: False sharing is when multiple threads write to distinct variables in the same cache line simultaneously.

• Impact: It increases cache traffic and degrades performance.

• Solution: Use padding to ensure data accessed by distinct threads resides in separate cache lines.