False Sharing, Tasking, and Thread Safety

In shared-memory programming, achieving peak performance requires understanding the underlying hardware architecture—especially CPU cache lines.

In this chapter, we investigate cache coherence and false sharing, optimize thread reuse in odd-even sorting, master the dynamic OpenMP Tasking API, and examine thread-safety and reentrancy.

---

5.20 Caches, Cache Coherence, and False Sharing

Modern processors access CPU cache memory in sub-nanoseconds, whereas accessing main memory requires tens of nanoseconds. To leverage spatial and temporal locality, memory is transferred between main memory and caches in fixed chunks called cache lines (typically 64 bytes = 8 double values).

The Cache Coherence Problem

When multiple CPU cores cache the same memory location, hardware enforces cache coherence. If Core 0 writes to a cache line, that entire line is marked invalid in all other cores’ caches.

Table 5.6: Memory and Cache Access Sequence

Time	Main Memory	Thread 0 Register	Thread 0 Cache	Thread 1 Register	Thread 1 Cache
0	$x = 5$	Load $x$	—	Load $x$	—
1	$x = 5$	—	$x = 5$	—	$x = 5$
2	$x = 5$	Execute x++	$x = 5$	—	$x = 5$
3	Updated / Pending	—	$x = 6$	Read $x$	Invalidated! Must reload from memory

---

The False Sharing Phenomenon

Consider matrix-vector multiplication $\mathbf{y} = A\mathbf{x}$ parallelized across 4 threads:

#pragma omp parallel for num_threads(thread_count) \
    default(none) private(i, j) shared(A, x, y, m, n)
for (i = 0; i < m; i++) {
    y[i] = 0.0;
    for (j = 0; j < n; j++) {
        y[i] += A[i * n + j] * x[j];
    }
}

Now compare three different matrix dimensions, each requiring exactly 64,000,000 arithmetic operations:

Table 5.7: Run-times and Efficiencies of Matrix-Vector Multiplication

Threads	$8,000,000 \times 8$ (Time / Eff)	$8000 \times 8000$ (Time / Eff)	$8 \times 8,000,000$ (Time / Eff)
1	$0.322\,\text{s}$ • $1.000$	$0.264\,\text{s}$ • $1.000$	$0.333\,\text{s}$ • $1.000$
2	$0.219\,\text{s}$ • $0.735$	$0.189\,\text{s}$ • $0.698$	$0.300\,\text{s}$ • $0.555$
4	$0.141\,\text{s}$ • $0.571$	$0.119\,\text{s}$ • $0.555$	$0.303\,\text{s}$ • $0.275$

Why Did the $8 \times 8,000,000$ Matrix Experience Severe Degradation?

• The result vector $\mathbf{y}$ has only 8 elements.
• On a 64-byte cache line system, all 8 doubles of $\mathbf{y}$ fit into a single cache line ($8 \times 8 = 64$ bytes).
• Thread 0 updates y[0], Thread 1 updates y[1], etc. Even though each thread accesses a distinct array element, every write by Thread 0 invalidates the entire cache line in the caches of Threads 1, 2, and 3!
• The cache line constantly bounces between core caches, stalling processors on main memory reloads. This is false sharing.

flowchart TD
  subgraph FalseSharing["False Sharing on 64-Byte Cache Line"]
      direction TB
      subgraph Line["Single 64-Byte Cache Line"]
          Y0["y[0] (Thread 0)"]
          Y1["y[1] (Thread 1)"]
          Y2["y[2] (Thread 2)"]
          Y3["y[3] (Thread 3)"]
      end
      T0["Core 0 writes y[0]"] ==>|Invalidates Line| Line
      Line -.->|Forces Cache Miss| T1["Core 1 stalls reloading y[1]"]
      Line -.->|Forces Cache Miss| T2["Core 2 stalls reloading y[2]"]
      Line -.->|Forces Cache Miss| T3["Core 3 stalls reloading y[3]"]
  end

Mitigating False Sharing

1. Private Local Accumulators: Have each thread accumulate into a private local variable on its own stack, and write to y[i] once when the loop completes.
2. Padding: Pad arrays with dummy elements so variables accessed by different threads occupy separate cache lines.

---

5.21 Loop Parallelization vs. Thread Reuse: Odd-Even Sort

In odd-even transposition sort, compare-swaps alternate between even phases and odd phases:

Table 5.8: Serial Odd-Even Transposition Sort Trace

Phase	Array Index 0	Array Index 1	Array Index 2	Array Index 3
0 (Even)	$9 \leftrightarrow 7$	$7 \quad 9$	$8 \leftrightarrow 6$	$6 \quad 8$
1 (Odd)	$7$	$9 \leftrightarrow 6$	$6 \quad 9$	$8$
2 (Even)	$7 \leftrightarrow 6$	$6 \quad 7$	$9 \leftrightarrow 8$	$8 \quad 9$
3 (Odd)	$6$	$7 \leftrightarrow 8$	$7 \quad 8$	$9$

Implementation 1: Nested parallel for (Repeated Fork-Join)

/* Program 5.4: High Fork/Join Overhead */
for (phase = 0; phase < n; phase++) {
    if (phase % 2 == 0) {
        #pragma omp parallel for num_threads(thread_count) default(none) ...
        for (i = 1; i < n; i += 2) { /* compare-swap */ }
    } else {
        #pragma omp parallel for num_threads(thread_count) default(none) ...
        for (i = 1; i < n - 1; i += 2) { /* compare-swap */ }
    }
}

This forks and joins thread_count threads $n$ times, generating significant thread lifecycle overhead.

---

Implementation 2: Single parallel Block with Worksharing for Directives

/* Program 5.5: Optimized Thread Reuse */
#pragma omp parallel num_threads(thread_count) \
    default(none) shared(a, n) private(i, tmp, phase)
for (phase = 0; phase < n; phase++) {
    if (phase % 2 == 0) {
        #pragma omp for
        for (i = 1; i < n; i += 2) {
            if (a[i - 1] > a[i]) {
                tmp = a[i - 1]; a[i - 1] = a[i]; a[i] = tmp;
            }
        }
    } else {
        #pragma omp for
        for (i = 1; i < n - 1; i += 2) {
            if (a[i] > a[i + 1]) {
                tmp = a[i + 1]; a[i + 1] = a[i]; a[i] = tmp;
            }
        }
    }
}

#pragma omp for does not fork new threads; it partitions the iterations among the already existing team of threads.

Table 5.9: Odd-Even Sort Performance Comparison (20,000 elements, seconds)

Implementation	1 Thread	2 Threads	3 Threads	4 Threads
Two parallel for directives	$0.770\,\text{s}$	$0.453\,\text{s}$	$0.358\,\text{s}$	$0.305\,\text{s}$
Reusing threads with #pragma omp for	$0.732\,\text{s}$	$0.376\,\text{s}$	$0.294\,\text{s}$	$0.239\,\text{s}$ (17%+ faster)

---

5.22 Dynamic Workloads and the Tasking API

Loops with variable bounds, unbounded while loops, and recursive functions cannot be parallelized with parallel for. OpenMP 3.0 introduced Tasking to handle dynamic, irregular parallelism.

The Tasking Model

#pragma omp task [clause ...]
    structured-block

When a thread reaches a #pragma omp task directive, it creates a new independent unit of work that is queued and scheduled across available threads in the team.

#pragma omp parallel
#pragma omp single
{
    /* Single master generates tasks into the thread pool */
    #pragma omp task
    Process_item(A);

    #pragma omp task
    Process_item(B);
}

The #pragma omp single directive ensures tasks are submitted only once by a single thread, while the remaining threads in the team execute tasks from the pool.

---

Parallel Recursive Fibonacci

/* Program 5.6: Fibonacci with Tasks */
int fib(int n) {
    int i = 0, j = 0;

    if (n <= 1) return n;

    #pragma omp task shared(i)
    i = fib(n - 1);

    #pragma omp task shared(j)
    j = fib(n - 2);

    #pragma omp taskwait /* Barrier: wait for subtasks to finish */
    return i + j;
}

• Variable Scoping: Task variables default to firstprivate. Marking shared(i) and shared(j) ensures the parent task reads the computed results.
• Synchronization: #pragma omp taskwait acts as a barrier, pausing the parent task until both child tasks complete.

Preventing Task Creation Overhead

Creating billions of tiny tasks degrades performance. We use the if clause to establish a cutoff threshold:

#pragma omp task shared(i) if(n > 20)
i = fib(n - 1);

When $n \le 20$, the task executes sequentially without runtime task management overhead, cutting runtime in half.

---

5.23 Thread-Safety and Reentrancy

A function is thread-safe if it can be called simultaneously by multiple threads without producing incorrect behavior or data corruption.

Case Study: String Tokenization with strtok()

Consider parsing lines of text with standard C strtok():

/* Program 5.7: Buggy Multi-Threaded Tokenizer */
my_token = strtok(lines[i], " \t\n");
while (my_token != NULL) {
    printf("Thread %d > token = %s\n", my_rank, my_token);
    my_token = strtok(NULL, " \t\n");
}

When run with multiple threads, this randomly corrupts token streams or drops lines.

Why strtok() Fails:

strtok() retains its position in the string using an internal static variable. Because static memory is shared across all threads, Thread 1’s call overwrites Thread 0’s parsing state.

The Thread-Safe Solution: strtok_r()

POSIX provides the reentrant version strtok_r(), which accepts an explicit pointer (char** saveptr) to track state on the thread’s private stack:

char* saveptr;
my_token = strtok_r(lines[i], " \t\n", &saveptr);
while (my_token != NULL) {
    printf("Thread %d > token = %s\n", my_rank, my_token);
    my_token = strtok_r(NULL, " \t\n", &saveptr);
}

Nondeterministic Success

A buggy multithreaded program may execute correctly 99% of the time and fail only under specific thread interleavings. Never assume a parallel program is correct simply because test runs produce expected output.

---

5.24 Chapter Summary

• Directives & Pragmas: OpenMP uses #pragma omp to enable high-level, incremental parallelization of shared-memory C programs.
• Fork-Join Execution: Teams of threads are spawned by #pragma omp parallel and joined at implicit barriers.
• Mutual Exclusion:
  • #pragma omp critical: General software critical section.
  • #pragma omp atomic: Hardware-accelerated memory updates for single statements.
  • omp_lock_t: Dynamic, fine-grained object-level locking.
• Loop Worksharing: #pragma omp parallel for automatically divides iterations. Requires canonical loops with no loop-carried dependences.
• Scheduling: Controlled via schedule(static | dynamic | guided [, chunk]) or schedule(runtime).
• Hardware Awareness: Prevent false sharing by ensuring concurrent writes do not target different variables residing in the same 64-byte cache line.
• Tasking API: Parallelizes recursive and irregular algorithms using #pragma omp task and #pragma omp taskwait.
• Thread-Safety: Always verify that third-party and standard library functions are reentrant before calling them inside parallel regions.