Parallel & Multi-core Computing

Hyper-Threading (Intel SMT)

One physical core appears as 2 logical cores to the OS. The core has duplicate registers/state for 2 threads, sharing execution units. When one thread stalls (e.g., cache miss), the other runs.

A thread is the smallest unit of CPU execution. Multiple threads within one process share the same code, heap, and global data — but each has its own stack and registers.

Thread Lifecycle (State Machine)

A race condition occurs when the program output depends on the relative timing of threads. Classic example: two threads incrementing a shared counter.

int counter = 0;  // shared variable

// Thread A              // Thread B
read counter → 5         read counter → 5
add 1 → 6               add 1 → 6
write counter ← 6        write counter ← 6
// Both incremented but counter went 5→6, NOT 5→7 !

Error Diffusion Algorithm (Parallel)

Used in image processing (e.g., dithering). Quantization error of one pixel is diffused to neighbouring pixels. In parallel, threads handling adjacent rows can conflict — a classic parallel programming challenge.

Parallel Error Diffusion — Checkerboard Pattern

Instead of shared memory, threads/processes can communicate by sending messages. This eliminates race conditions but requires explicit send/receive calls.

#include <pthread.h>

void* worker(void* arg) {
int id = *(int*)arg;
printf(“Thread %d running\n”, id);
return NULL;
}

int main() {
pthread_t t1, t2;
int a=1, b=2;
pthread_create(&t1, NULL, worker, &a); // create thread
pthread_create(&t2, NULL, worker, &b);
pthread_join(t1, NULL);  // wait for t1 to finish
pthread_join(t2, NULL);
return 0;
}

HANDLE h = CreateThread(
NULL,           // default security
0,              // default stack size
ThreadFunc,     // function pointer
(LPVOID)&args,  // argument
0,              // run immediately
&threadId       // receives thread ID
);
WaitForSingleObject(h, INFINITE);
CloseHandle(h);

The #pragma omp task directive creates a task — a unit of work that can be executed by any thread in the team. Useful for irregular parallelism (e.g., tree traversal).

int fib(int n) {
    if (n < 2) return n;
    int x, y;
    #pragma omp task shared(x)
        x = fib(n - 1);
    #pragma omp task shared(y)
        y = fib(n - 2);
    #pragma omp taskwait  // wait for both tasks
    return x + y;
}

OpenMP Environment Variables

Compilation & Debugging

# GCC
```

gcc -fopenmp program.c -o program

# Intel ICC

icc -qopenmp program.c -o program

# Run with Valgrind DRD for race detection

valgrind –tool=drd ./program

# Intel Inspector for race conditions

inspxe-cl -collect=ti3 – ./program

Memory Consistency Models

Different architectures allow CPUs to reorder memory operations for performance. Programmers need to insert barriers to enforce ordering.

Cache-friendly Programming Tips

• Row-major access: In C, 2D arrays are stored row-by-row. Always iterate rows in outer loop.
• Struct of Arrays vs Array of Structs: For parallel access, SoA is more cache-friendly (SIMD-friendly).
• Prefetching: Use __builtin_prefetch(addr, rw, locality) in GCC to hint CPU to load data before needed.

// BAD — column-major: cache thrashes each row
```

for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += matrix[i][j];   // jumps N*4 bytes each step!

// GOOD — row-major: sequential cache line access
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += matrix[i][j];   // sequential 4-byte steps ✓

Non-blocking Algorithms & ABA Problem

x86-64 Architecture Essentials

Avoiding Pipeline Stalls

// Branchy — hard to predict
```

int max_val;
if (a > b) max_val = a;
else max_val = b;

// Branchless — no pipeline flush
int max_val = a ^ ((a ^ b) & -(a < b));
// or simply:
int max_val = (a > b) ? a : b;
// Most compilers emit CMOV (conditional move) — no branch!

Thread-safe Functions & Bandwidth

• Thread-safe functions can be called concurrently without data corruption. They either use no shared state (pure functions) or protect shared state with locks.
• Memory Bandwidth is often the bottleneck for parallel programs (not CPU speed). Use roofline model to determine if your code is compute-bound or memory-bound.
• Working with Cache: Keep hot data in <32KB (L1 per core). Use tiling/blocking to reuse cached data.