5. Shared-Memory Parallel Programming

Introduction and Context

Shared-memory parallel programming enables multiple threads or processing cores to work within one address space. It is central to high-performance computing because modern multicore CPUs can execute many instruction streams concurrently while sharing main memory and often several levels of cache. Scientific simulation, data analytics, machine learning, image processing, financial modelling, and database systems all use this model.

The apparent simplicity of shared memory is deceptive. Threads can access the same variables, but unsynchronised access may produce race conditions, inconsistent results, deadlocks, poor cache behaviour, and performance that is worse than serial execution. Effective parallel programming therefore requires more than creating threads. The programmer must identify parallel work, control interactions among threads, select suitable scheduling policies, preserve locality, and measure the resulting program.

This chapter develops a practical and analytical understanding of thread-based programming, OpenMP, synchronisation, memory locality, false sharing, and NUMA placement. It complements distributed-memory methods by focusing on parallel execution within a node.

Learning Objectives

After studying this chapter, the learner should be able to:

1. Explain the shared-memory programming model and the relationship among processes, threads, cores, caches, and memory.

2. Identify data, task, and loop parallelism in an application.

3. Develop thread-safe programs using threads and OpenMP.

4. Select appropriate scheduling and synchronisation mechanisms.

5. Diagnose race conditions, deadlocks, false sharing, and load imbalance.

6. Apply locality-aware and NUMA-aware techniques.

7. Evaluate the performance, scalability, and maintainability of shared-memory programs.

The Shared-Memory Execution Model

In a shared-memory system, a process owns an address space containing code, heap data, global variables, and stacks. Threads created by that process share code, heap data, and global variables, but normally have separate registers and stacks. A thread is therefore a unit of execution, whereas a process is primarily a unit of resource ownership and protection.

A multicore processor may execute several threads simultaneously. Each core usually has private registers and one or more cache levels; some caches may be shared by a group of cores. A cache line is the unit transferred between cache and memory, commonly several dozen bytes. When one thread writes data in a cache line, hardware coherence protocols may invalidate corresponding copies in other cores. Coherence preserves a consistent view of memory, but it does not make compound operations automatically atomic.

For example, the statement `counter++` usually involves reading the value, adding one, and writing the result. If two threads read the same old value before either writes, one update can be lost. This is a race condition. The language memory model determines which reorderings and visibility guarantees are valid; consequently, a program must use defined synchronisation rather than rely on timing or hardware behaviour.

Parallelism may be expressed at several levels. Data parallelism applies the same operation to different elements of a collection. Task parallelism executes different activities concurrently. Pipeline parallelism divides a workflow into stages, allowing different data items to occupy different stages simultaneously. Loop parallelism, a common form of data parallelism, assigns iterations to threads.

A useful first principle is that only independent work should be executed concurrently. Dependencies, shared state, input/output, and external library behaviour must be analysed before parallelisation.

Threads, OpenMP, and Programming Abstractions

A low-level thread library gives explicit control over thread creation, joining, attributes, locks, condition variables, and thread-local data. This control is valuable for irregular applications and runtime systems, but it also creates substantial programming responsibility. The programmer must divide work, communicate results, handle errors, and ensure that every synchronisation object is correctly managed.

OpenMP provides compiler directives, runtime functions, and environment variables for shared-memory parallelism in C, C++, and Fortran. A directive such as:

```c

#pragma omp parallel for

for (int i = 0; i < n; i++)

c[i] = a[i] + b[i];

```

creates a team of threads and distributes loop iterations. Variables declared outside the region are generally shared, while loop indices are private to iterations. The exact data-sharing attributes should be made explicit when clarity or correctness demands it:

```c

#pragma omp parallel for default(none) shared(a,b,c,n)

for (int i = 0; i < n; ++i)

c[i] = a[i] + b[i];

```

OpenMP constructs include `parallel`, `for` or `do`, `sections`, `single`, `task`, `simd`, and combined forms such as `parallel for`. Clauses control data scope, scheduling, reduction, and synchronisation. The `reduction` clause is especially important for safe accumulation:

```c

#pragma omp parallel for reduction(+:total)

for (int i = 0; i < n; ++i)

total += values[i];

```

Each thread receives a private partial value, and OpenMP combines the partial results. Floating-point reductions may produce slightly different rounding because addition is not mathematically associative in finite precision.

A parallel region has overhead: threads must be activated or scheduled, work must be distributed, and an implicit barrier may occur at its end. A small loop may therefore run more slowly in parallel. Combining work into sufficiently large regions and reusing a thread team can reduce overhead.

Scheduling and Load Balance

Scheduling determines how loop iterations are assigned to threads. `static` scheduling divides iterations predictably and has low overhead. It is effective when iterations have similar cost and often supports good locality. `dynamic` scheduling assigns chunks as threads become available, improving balance when iteration costs vary, but it introduces runtime overhead and may reduce locality. `guided` scheduling begins with larger chunks and gradually reduces their size, seeking a compromise between balance and scheduling cost. `runtime` allows the policy to be selected externally.

For example:

```c

#pragma omp parallel for schedule(static)

for (int i = 0; i < n; ++i) fixed_cost(i);

#pragma omp parallel for schedule(dynamic, 8)

for (int i = 0; i < n; ++i) variable_cost(i);

```

Chunk size is a performance parameter. Very small chunks can improve balance but increase scheduling overhead and cause threads to move across data regions. Very large chunks reduce overhead but may leave some threads idle. Scheduling should therefore be chosen from measurements and knowledge of iteration cost rather than habit.

Load imbalance is the difference between the amount of useful work assigned to workers. It can result from unequal input sizes, branches, irregular graph structures, or synchronisation. The ideal schedule minimises both idle time and coordination cost.

Correctness: Races, Atomicity, and Synchronisation

A data race occurs when two or more threads access the same memory location concurrently, at least one access is a write, and no valid ordering mechanism protects the access. Race-induced errors may be intermittent, input-dependent, and difficult to reproduce.

A critical section provides mutual exclusion: only one thread at a time executes a protected region. In OpenMP:

```c

#pragma omp critical

{

shared_list.push_back(item);

}

```

This is easy to use, but a single unnamed critical region can become a bottleneck. Named critical regions allow independent locks for unrelated resources.

An atomic operation protects a specific simple update and usually has lower overhead than a general critical section:

```c

#pragma omp atomic

counter++;

```

Atomic operations are not a universal replacement for locks. A multi-step invariant involving several variables may require a critical section or explicit lock.

A barrier causes threads to wait until all members of the team arrive. Barriers are appropriate when a later phase depends on completion of an earlier phase. They are harmful when inserted unnecessarily because the fastest threads wait for the slowest. Many OpenMP work-sharing constructs have an implicit barrier; the `nowait` clause can remove it when the next operation is independent.

Locks provide explicit mutual exclusion. Condition variables, often used with low-level thread libraries, allow a thread to sleep until a condition becomes true. Semaphores represent a count of available permits and can regulate access to a bounded resource. Thread-local storage avoids sharing when each thread can maintain an independent copy.

Correctness should be expressed through invariants. For example, if a queue has a `head`, `tail`, and buffer, all operations that must preserve their relationship should be protected by a consistent protocol. Protecting only one field is not sufficient.

Deadlock and Lock Discipline

Deadlock is a state in which threads wait indefinitely for resources held by one another. Four conditions commonly permit deadlock: mutual exclusion, hold and wait, no pre-emption, and circular wait. Consider thread A holding lock L1 while requesting L2, and thread B holding L2 while requesting L1. Neither can proceed.

Deadlocks can be prevented by imposing a global lock order and requiring every thread to acquire locks in that order. Other approaches include acquiring all required locks together, using timed or try-lock operations, reducing lock scope, and replacing shared mutable state with message passing or immutable data. Lock acquisition and release should be visible, limited, and exception-safe where applicable.

Livelock differs from deadlock: threads continue changing state but make no useful progress. Starvation occurs when a thread is repeatedly denied access to a resource. Fair scheduling, bounded waiting, and carefully designed lock policies help address these problems.

Locality, Cache Behaviour, and False Sharing

Performance depends strongly on locality. Temporal locality means recently used data is likely to be used again; spatial locality means nearby data is likely to be accessed soon. Row-major traversal of a matrix in C generally has better locality than column-wise traversal because adjacent elements in a row are contiguous.

A cache miss forces data to be fetched from a slower level of the memory hierarchy. In parallel programs, several threads may also compete for bandwidth and cache capacity. A program can be computationally parallel yet memory-bound, meaning that additional threads cannot improve performance because memory transfer is the limiting resource.

False sharing is a particularly important multicore problem. It occurs when independent variables used by different threads occupy the same cache line. Although the threads do not logically share data, writes cause repeated cache-line invalidations. Padding or alignment can separate frequently written per-thread variables:

```c

struct Counter {

long value;

char padding[56];

};

```

The exact padding depends on cache-line size and data layout, so measurement is essential. A better design may use thread-local partial results followed by a reduction, avoiding frequent writes to a common location.

Data layout matters in arrays, structures, and object-oriented applications. Structure-of-arrays layouts can improve vectorisation and memory throughput when processing one field across many records. Blocking or tiling divides a large computation into subproblems that fit better in cache, as in tiled matrix multiplication.

NUMA Placement and Affinity

In a non-uniform memory access system, memory is physically distributed among sockets or nodes. A core accesses its local memory faster and with greater bandwidth than remote memory. The operating system and runtime may use first-touch placement: a page is physically allocated near the thread that first writes it. If one thread initialises all data and many other sockets later process it, remote access can become a bottleneck.

NUMA-aware programming distributes data initialisation and computation consistently. Parallel first-touch initialisation, thread affinity, and placement policies can keep threads near the data they use. Affinity binds threads to selected cores or places them within a socket. Excessive binding may be counterproductive if it prevents the operating system from responding to workload changes, so affinity should be tested with the actual machine and workload.

NUMA effects are especially important for large arrays, databases, graph analytics, and memory-bandwidth-intensive scientific codes. A scalable design considers not only the number of threads but also socket boundaries, memory channels, and data ownership.

A Method for Developing Reliable Parallel Programs

A disciplined workflow begins with a correct serial baseline. Profile it to identify dominant computation and memory behaviour. Parallelise a region with substantial work and limited dependencies, then verify correctness before pursuing optimisation.

The following questions provide a useful design sequence:

• What work can proceed independently?
• Which variables are read-only, privately writable, or genuinely shared?
• What ordering constraints are required?
• Can reductions or ownership eliminate shared updates?
• Which scheduling policy matches the cost distribution?
• Will the data fit in cache, and where is it allocated on a NUMA machine?
• What measurement will distinguish computation, memory, synchronisation, and scheduling costs?

Test with small deterministic inputs, boundary cases, repeated executions, and sanitising or race-detection tools where available. Compare parallel output with a trusted serial result, allowing for legitimate floating-point variation. Benchmark using warm-up runs, representative data, multiple thread counts, and repeated trials.

Important metrics include speedup, efficiency, throughput, latency, scalability, and parallel overhead. Speedup is `T1/Tp`, where `T1` is serial time and `Tp` is time using `p` threads. Efficiency is speedup divided by `p`. Amdahl’s law shows that a serial fraction limits strong scaling: if a fraction `s` cannot be parallelised, the maximum speedup is approximately `1/(s + (1-s)/p)`. Memory bandwidth, synchronisation, and load imbalance impose additional practical limits.

Applied Case: Parallel Risk Aggregation in a Financial Analytics Service

Background

Consider an illustrative financial analytics service that evaluates thousands of portfolios under many market scenarios. Each scenario applies instrument-specific calculations and contributes to portfolio-level risk measures. The original implementation processes scenarios serially and fails to meet the overnight reporting deadline.

Situation and Problem

A first OpenMP implementation parallelises the scenario loop but updates a shared portfolio accumulator inside a critical section. It produces correct results, yet speedup stops after four threads. Profiling shows high time in lock contention and substantial memory traffic.

Analysis

The scenario calculations are mostly independent. The shared accumulator is the main serialisation point. In addition, all threads access a large instrument table, and one initialisation thread places its pages on a single NUMA node. On a two-socket server, remote memory accesses increase as thread count grows.

Approach and Solution

Each thread receives a private accumulator. Scenario iterations are scheduled statically because their costs are similar and the schedule preserves locality. At the end of the parallel region, private accumulators are combined using a reduction-like merge. The instrument table is read-only and is initialised in parallel using the same broad partitioning used by the computation. Threads are bound appropriately within sockets, and measurements are collected separately for one-socket and two-socket execution.

The implementation also changes the data layout so frequently accessed instrument attributes are stored in contiguous arrays. A small number of expensive, irregular scenarios are assigned with a dynamic schedule in a separate phase rather than making the entire workload dynamic.

Outcome

The redesigned program removes lock contention, improves locality, and reduces remote memory traffic. Its scaling is not perfectly linear because memory bandwidth and the final merge remain limiting factors, but it achieves substantially better throughput and more predictable execution time. The improvement comes primarily from changing ownership and data movement, not merely from increasing the thread count.

Learning Points

The case illustrates four general principles: private partial results are often preferable to synchronised global updates; scheduling should reflect workload regularity; NUMA placement must be considered for large data; and performance analysis should identify the actual bottleneck before selecting an optimisation.

Common Errors, Risks, and Professional Considerations

The most frequent error is assuming that a parallel loop is safe simply because each iteration appears independent. Hidden shared state in library calls, static variables, random-number generators, logging, and memory allocators can invalidate that assumption. Another error is placing a large amount of work inside a critical section, thereby converting a parallel program into a serial one.

Creating too many threads causes context-switching and scheduling overhead. Nested parallelism may oversubscribe the machine if each outer thread creates a full inner team. Oversubscription also occurs when several applications or libraries independently create threads. Thread counts and affinity should be coordinated across the software stack.

Parallel floating-point calculations may not be bitwise reproducible because operation order changes. In regulated finance, scientific validation, and safety-related systems, the required reproducibility level must be documented. Random-number generation requires independent, correctly seeded streams rather than concurrent use of an unsafe global generator.

Data privacy and security also matter. Shared memory can expose sensitive intermediate data to threads that should not access it, and improper cleanup may leave confidential values in reusable buffers. Production systems should apply least-privilege design, controlled logging, code review, testing, and documented performance assumptions.

Current Directions and Best Practices

Modern shared-memory programming increasingly combines OpenMP with SIMD vectorisation, task-based runtimes, accelerator offload, and performance-portable frameworks. OpenMP task constructs are useful for irregular dependency graphs, while task dependences express ordering without imposing a global barrier. Performance tools increasingly expose cache misses, branch behaviour, memory bandwidth, NUMA traffic, and thread states.

Best practice is to:

1. Establish a correct and measured serial baseline.

2. Prefer ownership, private data, reductions, and immutable structures over frequent locking.

3. Make data-sharing attributes explicit.

4. Choose schedules according to iteration cost, locality, and overhead.

5. Minimise synchronisation scope and avoid unnecessary barriers.

6. Use consistent lock ordering and document invariants.

7. Inspect cache-line placement and NUMA affinity for memory-intensive workloads.

8. Validate results under different thread counts and schedules.

9. Measure with representative workloads rather than relying on intuition.

10. Treat maintainability and reproducibility as performance requirements, not afterthoughts.

Chapter Summary

Shared-memory parallel programming allows threads to cooperate through a common address space, but shared access introduces correctness and performance challenges. Thread safety depends on identifying races, defining ownership, and using appropriate mechanisms such as atomics, critical sections, barriers, locks, reductions, and thread-local storage. Scheduling policies balance overhead, locality, and irregular workload costs.

Cache and NUMA behaviour strongly influence scalability. Locality-aware data layout, avoidance of false sharing, parallel first-touch initialisation, and thread affinity can be as important as algorithmic parallelism. A reliable development process combines serial baselines, profiling, correctness testing, controlled benchmarking, and analysis of speedup and efficiency. Professional parallel programs are designed around limited sharing, explicit dependencies, measured choices, and documented assumptions.

Key Terms

Thread: An independently schedulable execution flow within a process.

Shared-memory model: A model in which cooperating threads access a common address space.

Data race: Conflicting unsynchronised concurrent accesses to the same memory location.

Atomic operation: An indivisible operation that prevents intermediate states from being observed.

Critical section: A region that permits only one thread at a time.

Barrier: A synchronisation point at which threads wait for one another.

Reduction: A structured combination of private partial results into one result.

Static scheduling: Predetermined assignment of loop iterations to threads.

Dynamic scheduling: Runtime assignment of work as threads become available.

Load imbalance: Unequal distribution of useful work among threads.

Cache coherence: Hardware consistency of cached copies of memory.

Cache line: The unit of data transferred between cache and memory.

False sharing: Performance degradation caused by independent variables sharing a cache line.

Locality: The tendency to reuse nearby or recently accessed data.

NUMA: Non-uniform memory access with different costs for local and remote memory.

Thread affinity: Binding threads to particular processors or processor groups.

Deadlock: Indefinite waiting caused by circular resource dependencies.

Oversubscription: Running more active software threads than hardware can efficiently support.

Speedup: The ratio of serial execution time to parallel execution time.

Efficiency: Speedup divided by the number of processing units used.

Review Questions

Short Answer Questions

1. Distinguish between a process and a thread in a shared-memory system.

2. What conditions produce a data race?

3. Why can a reduction be preferable to a critical section?

4. Differentiate static and dynamic loop scheduling.

5. What is false sharing, and why does it reduce performance?

Long Answer Questions

1. Explain the OpenMP shared-memory programming model, including parallel regions, data scope, scheduling, and reductions.

2. Discuss the causes of deadlock and present practical techniques for preventing it.

3. Explain how cache locality, cache coherence, and memory bandwidth influence parallel performance.

4. Describe NUMA placement, first-touch allocation, and thread affinity in a multisocket system.

5. Develop a systematic workflow for designing, testing, and benchmarking a thread-safe parallel program.

Analytical / Application Questions

1. A loop has highly variable iteration costs and each iteration writes to a separate array element. Which scheduling policy would you test first, and what performance trade-offs would you examine?

2. Two threads update separate counters, but profiling shows heavy cache invalidation. Explain the likely cause and propose two remedies.

3. A parallel financial aggregation program is correct but stops scaling beyond one socket. Using the case study, identify likely causes and design an investigation plan.

22. Multiple Choice Questions with Answers

Question 1

Two threads execute counter++ on the same shared variable without synchronisation. What is the primary risk?

A. Deadlock

B. A data race and lost updates

C. Improved cache locality

D. Guaranteed atomic execution

Correct Answer: B. A data race and lost updates

Question 2

Which OpenMP mechanism is most appropriate for combining independent per-thread partial sums?

A. reduction

B. barrier

C. single

D. sections

Correct Answer: A. reduction

Question 3

A loop has nearly equal-cost iterations and contiguous array access. Which schedule usually has the lowest scheduling overhead and good locality?

A. dynamic with chunk size 1

B. guided with chunk size 1

C. static

D. runtime with random assignment

Correct Answer: C. static

Question 4

What distinguishes false sharing from ordinary data sharing?

A. False sharing occurs only between processes

B. False sharing involves independent variables on the same cache line

C. False sharing always causes incorrect numerical results

D. False sharing is prevented by using a critical section

Correct Answer: B. False sharing involves independent variables on the same cache line

Question 5

Which situation can create deadlock?

A. All threads acquire locks in the same global order

B. Each thread uses private variables

C. Two threads acquire two locks in opposite orders

D. A reduction combines private results

Correct Answer: C. Two threads acquire two locks in opposite orders

Question 6

Why might parallel first-touch initialisation improve a NUMA program?

A. It eliminates all cache misses

B. It places pages nearer to threads that will use them

C. It makes every operation atomic

D. It prevents load imbalance in every loop

Correct Answer: B. It places pages nearer to threads that will use them

Question 7

A critical section around every update causes poor scaling. Which redesign most directly addresses the bottleneck?

A. Increase the number of barriers

B. Use private accumulators followed by a merge

C. Use smaller cache lines

D. Create one additional process per iteration

Correct Answer: B. Use private accumulators followed by a merge

Question 8

What does speedup T1/Tp measure?

A. Memory capacity

B. The fraction of serial code

C. The performance improvement from parallel execution

D. The number of cache lines used

Correct Answer: C. The performance improvement from parallel execution

Question 9

Which condition most strongly supports dynamic scheduling?

A. All iterations have identical cost

B. Iteration costs vary substantially

C. The loop has no iterations

D. All data is read-only and already local

Correct Answer: B. Iteration costs vary substantially

Question 10

Why may floating-point reduction results differ slightly between serial and parallel executions?

A. Parallel processors cannot perform addition

B. The order of additions may change rounding behaviour

C. Reduction always discards negative values

D. Threads convert all values to integers

Correct Answer: B. The order of additions may change rounding behaviour