Performance considerations

Why performance tuning matters in OpenMP

Shared-memory parallel programming with OpenMP can give large speedups, but naïve parallelization often leaves most of the potential performance unused—or even slows programs down. Performance considerations are about:

• Getting useful speedup from additional threads (scalability)
• Avoiding performance pitfalls specific to multi-threaded execution
• Making parallel regions efficient relative to the work they do

This chapter focuses on practical issues that affect performance in OpenMP-style shared-memory programs.

Overheads of parallelism

Parallel region overheads

Creating and destroying threads costs time. In OpenMP, entering a parallel region involves:

• Waking or creating threads
• Distributing work
• Synchronizing at the end

If the amount of work inside the region is small compared to this overhead, performance will degrade.

Guidelines:

• Use fewer, larger parallel regions instead of many tiny ones.
• For simple loops, prefer #pragma omp parallel for over surrounding each loop with a separate parallel region.
• Consider using nowait on for or sections constructs when a barrier is not needed, to avoid unnecessary synchronization overhead.

Task and scheduling overheads

• Each OpenMP task has creation and scheduling overhead.
• Very fine-grained tasks (e.g., tiny loop bodies) can cost more than they save.
• Use tasks for irregular or coarse-grained work; keep task granularity reasonably large.

Load balance between threads

Static vs dynamic work distribution

Imbalanced workloads cause some threads to finish early and sit idle while others keep working.

In omp for loops:

• schedule(static) assigns a fixed chunk of iterations to each thread.
• Very cheap overhead.
• Can cause imbalance if iteration work is non-uniform.
• schedule(dynamic, chunk) assigns chunks to threads on demand.
• Better balance when work per iteration varies.
• More overhead due to runtime scheduling.
• schedule(guided) starts with large chunks, shrinking over time; often a compromise between overhead and balance.

Rule of thumb:

• Use static when work per iteration is uniform.
• Use dynamic or guided when iteration work varies significantly.

Chunk size choice

• Too small a chunk size → more scheduling overhead.
• Too large a chunk → poorer load balance.

Experiment with chunk sizes that:

• Are large enough to amortize scheduling overhead
• Still allow the runtime to redistribute work effectively

False sharing and cache behavior

What is false sharing (performance perspective)

False sharing happens when:

• Different threads write to different variables or array elements
• These variables happen to be on the same cache line
• The cache coherence protocol repeatedly invalidates and transfers that line

This causes large slowdowns even though threads are not logically sharing data.

Typical warning signs:

• A code with very little sharing still scales poorly
• Running with 2 threads is fine, but scaling degrades quickly beyond that
• Performance improves significantly after adding padding to data structures

Avoiding false sharing

Common patterns that cause false sharing:

• Arrays where each thread writes to adjacent elements:
• e.g., a[tid] in a small array where tid is the thread ID but elements are packed tightly
• Small per-thread struct fields laid out next to each other in memory

Mitigation strategies:

• Padding: ensure per-thread data are separated by at least one cache line.
• For example, for a double array used per thread, allocate something like local[omp_get_max_threads()][PAD] where PAD is chosen to exceed a cache line.
• Structure of arrays vs array of structures:
• Choose layouts that prevent different threads from updating neighbors in the same cache line.
• Use reduction clauses instead of manual shared-array reductions where possible; OpenMP runtimes usually implement these efficiently.

Cache-friendly data access

Even without false sharing, cache behavior matters:

• Prefer contiguous memory access (e.g., iterating arrays in the natural order).
• In multi-dimensional arrays, iterate with the fastest-varying index in the innermost loop (e.g., row-major vs column-major depending on language).
• Avoid strided or random access patterns inside parallel loops when possible; poor cache locality reduces the benefits of parallelism.

Synchronization costs and contention

Barriers

• Each implicit or explicit barrier (#pragma omp barrier, end of parallel regions, some work-sharing constructs) forces all threads to wait for the slowest.
• Too many barriers reduce scalability.

Strategies:

• Remove unnecessary barriers.
• Use nowait where correctness allows it (e.g., #pragma omp for nowait).
• Restructure algorithms to reduce global synchronization points.

Locks and critical sections

• #pragma omp critical and explicit locks serialize access.
• Heavy contention (many threads frequently entering the same critical region) can destroy performance.

Guidelines:

• Minimize the time spent inside critical regions.
• Reduce frequency of entering critical/locked sections:
• Aggregate updates per thread, then combine once in a reduction step.
• Use atomic operations for simple operations on single variables.

Atomics

• #pragma omp atomic is typically cheaper than a critical section when updating a single value (e.g., sum += x).
• Overuse of atomics can still cause contention, especially with many threads updating the same variable.

Consider:

• Reductions instead of atomics when you can:
• #pragma omp parallel for reduction(+:sum) is often faster than many atomics on sum.
• Private or thread-local accumulation followed by a merge step.

NUMA and memory placement

On many modern multi-socket systems, memory is organized as NUMA (Non-Uniform Memory Access): memory attached to one socket is slower to access from another.

Performance implications:

• A thread accessing memory attached to a remote socket experiences higher latency and lower bandwidth.
• Poor memory placement can significantly reduce scaling beyond a single socket.

Practical measures:

• First-touch policy: many systems allocate physical memory when it is first written.
• Initialize data in parallel, such that each thread touches (initializes) the data it will use; this tends to place memory close to the thread’s core.
• Avoid unnecessary migration of threads between sockets while a computation is running (see thread affinity below).

Thread affinity and core binding

Thread affinity determines how threads are mapped to cores.

Performance effects:

• If many threads are scheduled on the same core or share resources unevenly, performance suffers.
• If threads frequently migrate between cores/sockets, cache locality and NUMA locality are lost.

Using affinity (conceptually):

• Bind threads to specific cores or at least to specific sockets.
• Ensure the number of threads does not exceed the number of physical cores intended for use (unless hyper-threading is specifically beneficial for the workload).

OpenMP usually provides environment variables (e.g., OMP_PROC_BIND, OMP_PLACES) or runtime options to control binding; exact usage belongs in hands-on sections, but you should be aware that:

• Consistent thread placement is crucial for reproducible performance.
• Affinity settings often interact with job schedulers on clusters; cluster documentation usually recommends specific settings.

Choosing the number of threads

More threads do not always mean better performance. Factors:

• Problem size: too small a problem cannot amortize overheads of many threads.
• Memory bandwidth: some codes are memory-bound; after a certain number of threads, memory bandwidth saturates and speedup flattens.
• NUMA boundaries: using more sockets may add remote memory traffic and overhead.

Guidelines:

• Perform simple experiments:
• Measure runtime for different thread counts (e.g., 1, 2, 4, 8, …).
• Identify where speedup saturates or decreases.
• Use that empirical optimal or near-optimal thread count on the target system.

Granularity of parallel work

Granularity is the amount of work handled per thread or per unit of scheduling (e.g., chunk, task).

• Too fine-grained:
• High overhead: thread management, scheduling, synchronization dominate.
• Typical with very small loops or very small tasks.
• Too coarse-grained:
• Potential load imbalance if tasks differ in cost.
• Harder to adapt to variability in runtime behavior.

Aim for:

• Each parallel chunk or task performing enough work (e.g., many operations or iterations) to amortize overhead.
• Adjust granularity according to:
• Cost per iteration
• Number of threads
• Scheduling strategy (static vs dynamic)

Reductions and accumulation patterns

Reductions (sum, max, min, etc.) are common in parallel programs.

Bad pattern (performance-wise):

• All threads repeatedly updating a single shared accumulator (using critical or atomic).

Better strategies:

• Use OpenMP reduction clauses where possible:
• They create private accumulators per thread and combine them efficiently at the end.
• If using custom data types:
• Consider per-thread accumulators stored in a padded array or vector (to avoid false sharing), followed by a sequential or parallel merge.
• Reduce the frequency of updates:
• Accumulate locally over many iterations before updating shared data.

Interaction with vectorization and the memory hierarchy

Thread-level parallelism (OpenMP) and instruction-level parallelism (vectorization) can interact in ways that affect performance.

Consider:

• Don’t disable compiler vectorization accidentally with OpenMP pragmas.
• Use collapse (collapse(n)) on nested loops when appropriate to:
• Expose more iterations to both thread parallelism and vectorization.
• Ensure that inner loops remain vectorizable:
• Avoid unnecessary dependencies or complex control flow within innermost loops.

Memory hierarchy aspects:

• More threads increase memory traffic; ensure your algorithm uses:
• Good locality of reference
• Blocking/tiling strategies if appropriate (especially for large arrays/matrices)
• Excessive parallelism on a memory-bound kernel may offer little benefit.

Measuring and tuning performance

Performance considerations are empirical: you must measure.

Basic workflow:

1. Establish a serial or baseline version.
2. Parallelize with OpenMP using only the necessary constructs.
3. Measure:
• Runtime for different thread counts
• Scaling efficiency (speedup / number of threads)
4. Investigate:
• If scaling is poor, check:
• Load balance (e.g., using different schedules)
• Synchronization hotspots (critical, locks, barriers)
• False sharing (try padding per-thread data)
• NUMA and affinity settings
5. Iterate:
• Modify code or runtime settings.
• Re-measure to confirm improvement.

Use your environment’s profiling and performance tools (covered elsewhere) to locate hotspots and bottlenecks; then apply the shared-memory specific ideas in this chapter to address them.

Summary checklist

When evaluating performance of an OpenMP shared-memory program, check:

• Are parallel regions coarse-grained enough to amortize overhead?
• Is work well-balanced across threads (scheduling strategy, chunk sizes)?
• Are there unnecessary barriers or synchronization points?
• Are critical regions and locks minimized and contention reduced?
• Are reductions implemented efficiently (prefer reduction over atomics/critical)?
• Could false sharing be affecting performance (consider padding per-thread data)?
• Is thread affinity set appropriately for the hardware and job scheduler?
• Does memory placement respect NUMA locality (first-touch initialization)?
• Is the number of threads appropriate for the problem size and hardware limits?
• Do data access patterns maintain good cache locality and remain vectorizable?

Addressing these points systematically is key to obtaining high performance from shared-memory parallel programs.