High Performance computing (CS-802 (C)) Unit 4 Notes

How unit 4 is examined

This unit covers profiling an OpenMP program and the pitfalls that slow it down; Performance pitfalls carries all the marks (14 marks, May 2022), and the other four topics are short but must not be missing.

Program profiling

Not asked since 2022

Definition. Profiling is measuring where a program spends its time, so that optimisation effort goes to the few hot spots that dominate the run time.

Key points.

A flat profile lists the time spent in each function, and a call-graph profile also shows which caller triggered it.
Tools such as gprof (compile with -pg), perf, Intel VTune and the OpenMP timer omp_get_wtime() give the numbers.
Profile the serial code first, because a parallel version of a slow algorithm is still slow.
For OpenMP, also measure per-thread time, because a large gap between the fastest and slowest thread shows load imbalance.
By Amdahl's law, speedup is limited by the serial fraction $s$: $S(p)=\dfrac{1}{s+(1-s)/p}$, so profile to find $s$.

Performance pitfalls

Definition. OpenMP is a shared-memory model in which threads of one process share the same address space and communicate through shared variables; performance pitfalls are the programming errors and hidden costs of this model (races, false sharing, overhead, load imbalance, serialisation, poor memory placement) that make a parallel program slow or wrong.

Key points.

A data race occurs when two threads access the same variable without ordering and at least one writes, so the result changes from run to run; it is circumvented with critical, atomic, reduction or by making the variable private.
False sharing occurs when threads write different variables that lie on the same cache line, so the line bounces between cores through cache coherence; it is circumvented by padding, or by keeping per-thread data in private variables.
Overhead of thread creation, fork-join, barriers and scheduling is paid on every parallel region, so a very short loop can run slower in parallel; it is circumvented with the if clause, larger work per region, and one enclosing parallel region with several for constructs.
Load imbalance occurs when iterations take unequal time, so fast threads wait idle at the implicit barrier; it is circumvented with schedule(dynamic) or guided, a suitable chunk size, and nowait where the next step does not depend on the loop.
Excess synchronisation such as a critical section or lock inside a loop serialises the threads and kills speedup; it is circumvented with per-thread partial results combined by a reduction.
Poor memory placement and thread migration make threads read remote memory (NUMA); it is circumvented with thread affinity (pinning threads to cores) and first-touch initialisation by the thread that later uses the data.
Memory-bandwidth saturation means adding threads gives no gain for memory-bound loops; it is circumvented by improving data reuse and cache blocking.
The result of each pitfall is lower speedup or wrong output, so check correctness first, then profile and remove the largest cost.

Diagram. Cause and cure:

Problem	Cause	Circumvention
Race	Unordered shared writes	critical, atomic, reduction, private
False sharing	Same cache line, different data	Padding, private copies
Overhead	Small work per region	`if` clause, merge regions
Load imbalance	Unequal iteration cost	dynamic or guided schedule
Serialisation	Locks in the loop	Reduction, less locking
Remote memory	No affinity	Pinning, first touch

Example. A shared sum += a[i] in a parallel loop is a race and gives wrong totals; #pragma omp parallel for reduction(+:sum) gives each thread a private copy and adds them at the end, so it is correct and fast.

Answer frame. Open with "OpenMP threads share one address space, so poor sharing and scheduling reduce performance"; draw the cause-and-cure table; then develop race, false sharing, overhead, load imbalance, synchronisation and affinity in that order, each as problem, effect, remedy; close with "profile first, then fix the largest cost".

Asked: [14 marks] (May 2022) Discuss the performance problems that can be raised with OpenMP shared-memory programming, also discuss how they can be circumvented?

Pitfall: Listing problems without the circumvention for each loses half the marks, because the question asks for both.

Improving the impact of OpenMP work-sharing constructs

Definition. Work-sharing constructs (for, sections, single) divide the work of a parallel region among threads, and their efficiency depends on schedule, chunk size, barriers and region structure.

Key points.

Use schedule(static) for equal iterations because it has the least overhead, and dynamic or guided for uneven iterations.
Use nowait to remove the implicit barrier at the end of a construct when the next code does not depend on its result.
Put several loops inside one parallel region rather than opening a new region for each, so thread creation is paid once.
Use collapse(n) on nested loops to give more iterations to distribute when the outer loop is short.
Parallelise the outermost loop with enough work, and avoid dependencies between iterations.

Determining overheads for short loops

Definition. Loop overhead is the fixed time spent on starting the threads, scheduling and the final barrier, which does not shrink when the loop body is small.

Key points.

Measure it by timing the same loop serially and in parallel with omp_get_wtime(), or by timing an empty parallel region, repeated many times and averaged.
Overhead per region is roughly constant, so parallel time is $T_p \approx T_s/p + T_{ovh}$.
Parallelism pays only when $T_s/p + T_{ovh} < T_s$, that is, when the loop is long enough.
Cut the overhead with the if(n > threshold) clause, fewer parallel regions and static scheduling.
A barrier or reduction costs more as the number of threads grows.

Serialisation and false sharing

Definition. Serialisation is parallel code being forced to run one thread at a time, and false sharing is threads slowing each other by writing different variables that sit in the same cache line.

Key points.

Serialisation comes from critical sections, locks, ordered and atomic updates on one variable, so threads queue.
Cache coherence works on whole lines (typically 64 bytes), so a write by one core invalidates the line in the other cores.
A typical case is sum[tid] in a shared array, where neighbouring elements share a line and each write causes a coherence miss.
Remove it by padding each element to a full cache line, or by using a private variable and writing the result once at the end.
Reduce serialisation by using reduction instead of critical, and finer-grained locking.

Last-minute revision

Profiling finds hot spots; profile serial code first; gprof uses -pg; timing uses omp_get_wtime().
Amdahl: $S(p)=1/(s+(1-s)/p)$.
Main OpenMP pitfalls: race, false sharing, overhead, load imbalance, serialisation, remote memory.
Race fix: critical, atomic, reduction, private.
False sharing fix: pad to the cache line (about 64 bytes) or use private copies.
Short loop fix: if clause and one enclosing parallel region.
Load imbalance fix: schedule(dynamic) or guided.
nowait removes the implicit barrier of a work-sharing construct.
collapse(n) merges nested loops into one iteration space.
Affinity and first touch reduce NUMA remote access.

Memory hooks

"R-F-O-L": Race, False sharing, Overhead, Load imbalance, the four pitfalls the examiner expects.
"Pad, Private, Pin": cures for false sharing and remote memory.
"Static for equal, dynamic for uneven."
"Measure before you tune."

Coverage checklist

Program profiling: definition, tools, Amdahl.
Performance pitfalls: May 2022 14-mark question (problems and circumvention).
improving the impact of open MP work sharing constructs: schedule, nowait, collapse.
determining overheads for short loops: timing, break-even, if clause.
Serilisation and false sharing: cache line, padding, reduction.

Account

High Performance computing (CS-802 (C)) - Unit 4 Short Notes

How unit 4 is examined

Program profiling

Performance pitfalls

Improving the impact of OpenMP work-sharing constructs

Determining overheads for short loops

Serialisation and false sharing

Last-minute revision

Memory hooks

Coverage checklist