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

How unit 3 is examined

This unit covers the kinds of parallelism, the laws and metrics that measure speedup, and the core OpenMP constructs; the 14-mark variants-of-parallelism question and the OpenMP question carry the marks.

Data and functional parallelism

High weight

Definition. Parallelism is the execution of many computations at the same time, by splitting a problem into parts that run simultaneously on multiple processing units, so that the total time falls.

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 424 338" width="424" height="338" role="img" aria-label="Variants of parallelism. P parallelism, D data, T task or functional, B bit-level, I instruction-level, F functional decomposition, M multiple independent tasks"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M57,160.5 L193.2,92.4" marker-end="url(#ah3)"/><path class="e" d="M57,177.5 L193.2,245.6" marker-end="url(#ah3)"/><path class="e" d="M230.4,78.4 L363.6,45.1" marker-end="url(#ah3)"/><path class="e" d="M230.4,87.6 L363.6,120.9" marker-end="url(#ah3)"/><path class="e" d="M230.4,250.4 L363.6,217.1" marker-end="url(#ah3)"/><path class="e" d="M230.4,259.6 L363.6,292.9" marker-end="url(#ah3)"/><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">P</text><circle class="n" cx="212" cy="83" r="18"/><text class="t" x="212" y="83" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="212" cy="255" r="18"/><text class="t" x="212" y="255" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">I</text><circle class="n" cx="384" cy="212" r="18"/><text class="t" x="384" y="212" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="384" cy="298" r="18"/><text class="t" x="384" y="298" dy=".35em" text-anchor="middle">M</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Variants of parallelism. P parallelism, D data, T task or functional, B bit-level, I instruction-level, F functional decomposition, M multiple independent tasks</figcaption></figure>

Key points.

Parallelism is needed in HPC because a single processor has hit limits of clock speed, power and heat, so more speed now comes from doing many operations at once on many cores.
Data parallelism splits the data into chunks and applies the same operation to every chunk on different processors (SIMD/SPMD style); example: adding two arrays, where each thread adds its own slice of a[i]+b[i].
Functional (task) parallelism runs different operations, functions or tasks at the same time on the same or different data (MIMD style); example: one thread reads input, another filters it and a third writes the output, like stages of a compiler.
Bit-level parallelism increases the word size so that one instruction handles more bits at once; example: a 32-bit processor adds two 32-bit numbers in one instruction, where an 8-bit processor needs four.
Instruction-level parallelism (ILP) overlaps independent instructions inside one processor using pipelining and superscalar issue; example: while one instruction executes, the next is decoded and a third is fetched.
Data parallelism scales with the data size and needs little communication, while functional parallelism is limited by the number of distinct tasks and their dependences.
Benefits and applications are shorter run time, solving larger problems, and use in weather forecasting, simulation, image processing and scientific computing.

Answer frame. Open with the definition and why HPC needs it; draw the variants tree; then develop data, task, bit-level and ILP in that order, each with its one example; close with benefits (speedup, larger problems) and applications.

Asked: [14 marks] (May 2022) What is Parallelism? Discuss the different variants of parallelism with the help of an example in each case.

Parallel scalability laws

Definition. Scalability is how well speedup grows as processors are added; Amdahl's law bounds speedup for a fixed problem size and Gustafson's law for a problem size that grows with the processors.

Key points.

Amdahl's law: with serial fraction $s$ and $p$ processors, $S(p)=\dfrac{1}{s+\frac{1-s}{p}}$, and the maximum speedup is $1/s$ however many processors are used.
Example: $s=0.1$, $p=8$ gives $S=1/(0.1+0.9/8)=1/0.2125=4.71$, and no number of processors can exceed 10.
Gustafson's law: $S(p)=p-s(p-1)$, which assumes the parallel work grows with $p$, so scaled speedup stays close to $p$.
Strong scaling fixes the problem size and adds processors (Amdahl); weak scaling grows the problem with the processors (Gustafson).

Metrics

Definition. Performance metrics measure how much a parallel program gains over the serial one: speedup, efficiency, and cost.

Key points.

Speedup $S=T_1/T_p$, where $T_1$ is the best serial time and $T_p$ the time on $p$ processors.
Efficiency $E=S/p$, the fraction of each processor's time that is used usefully; ideal value is 1.
Cost is $p\times T_p$; a parallel program is cost-optimal when its cost equals the serial time.
Example: $T_1=100$ s and $T_8=20$ s give $S=5$ and $E=5/8=0.625$.

Factors, efficiency and load imbalance

Definition. Load imbalance is the uneven division of work among processors, so some finish early and wait while the slowest one decides the total time.

Key points.

Efficiency falls because of serial sections, communication and synchronization overhead, and idle waiting.
Parallel time is set by the busiest processor, so $T_p=\max_i T_i$ and efficiency is $E=\dfrac{\text{average load}}{\text{maximum load}}$.
Load imbalance is reduced by dividing work in smaller equal pieces or by dynamic scheduling.
Other factors are memory contention, false sharing, and too small a problem for the number of processors.

Shared memory parallel programming with OpenMP

Definition. OpenMP is an API of compiler directives, library routines and environment variables for shared-memory parallel programming in C, C++ and Fortran.

Key points.

Threads share one address space and are created with directives such as #pragma omp parallel.
The programmer adds pragmas to serial code, so the program still runs serially if the compiler ignores them.
For the exam question, write the definition and then the three concepts as answered in the sections on data scoping, work sharing using loops and loop scheduling below.

Asked: [7 marks] (May 2022) What is OpenMP? Explain the concepts of data scoping, work-sharing for loops and loop scheduling.

Parallel execution

Definition. OpenMP uses the fork-join model: a master thread forks a team of threads at a parallel region and they join back into the master at its end.

Key points.

#pragma omp parallel creates a team; every thread runs the block.
Code outside the region runs on the master thread only.
There is an implicit barrier at the end of the region, after which only the master continues.
Team size is set by omp_set_num_threads(), num_threads(n) or OMP_NUM_THREADS.

Data scoping

Definition. Data scoping decides for each variable in a parallel region whether all threads share one copy or each thread has its own private copy.

Key points.

shared(x): one copy, seen by all threads; concurrent writes need protection.
private(x): each thread gets its own uninitialised copy, discarded after the region.
firstprivate(x) starts each private copy with the original value; lastprivate(x) copies the last iteration's value out.
default(none) forces every variable to be scoped explicitly; the loop index of a parallel for is private by default.

Work sharing using loops

Definition. A work-sharing loop, #pragma omp for, divides the iterations of a loop among the threads of the team so each executes a different part.

Key points.

#pragma omp parallel for combines region creation and loop sharing.
Iterations must be independent, with no loop-carried dependence.
There is an implicit barrier at the end of the loop unless nowait is given.
Example: #pragma omp parallel for over c[i]=a[i]+b[i] gives each thread a block of i values.

Synchronization

Definition. Synchronization coordinates threads so that shared data is accessed safely and in the right order.

Key points.

barrier makes all threads wait until every thread has reached it.
critical lets only one thread at a time execute a block; atomic protects a single memory update more cheaply.
master and single run a block by one thread only; ordered keeps loop iterations in sequence.
Without it, a race condition arises, where the result depends on thread timing.

Reductions

Definition. A reduction combines a per-thread partial result from all threads into one value using an operator, such as a sum.

Key points.

Syntax: reduction(+:sum); each thread gets a private copy initialised to the identity (0 for +, 1 for *).
At the end, the private copies are combined into the shared variable.
Operators include + * - & | ^ && || max min.
It avoids a race on sum without the cost of critical.

double sum = 0;
#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < n; i++) sum += a[i];

Loop scheduling and tasking

Definition. Loop scheduling, set by schedule(kind, chunk), decides how iterations are handed to threads; tasks are independent units of work queued for any free thread.

Key points.

static: iterations are split into fixed chunks in advance; lowest overhead, best when iterations cost the same.
dynamic: threads take a chunk when free; balances uneven work but has more overhead.
guided: chunk size starts large and shrinks as work runs out.
#pragma omp task creates a task for irregular work such as recursion or linked lists, and taskwait waits for child tasks.

Last-minute revision

Parallelism is many computations at once; variants are data, task/functional, bit-level and instruction-level.
Data parallelism: same operation on different data; task parallelism: different operations at once.
Speedup $S=T_1/T_p$; efficiency $E=S/p$; cost $=pT_p$.
Amdahl: $S=1/(s+(1-s)/p)$, upper bound $1/s$; Gustafson: $S=p-s(p-1)$.
OpenMP is a shared-memory API of pragmas, library routines and environment variables.
Fork-join: master forks a team and joins at the implicit barrier.
Scoping: shared, private, firstprivate, lastprivate, default(none).
parallel for divides independent iterations; reduction(+:sum) avoids races.
Schedules: static, dynamic, guided; tasks handle irregular work.

Memory hooks

D-T-B-I: Data, Task, Bit, Instruction, the four variants.
S-E-C: Speedup, Efficiency, Cost.
Amdahl = fixed size, Gustafson = growing size.
SDG: Static, Dynamic, Guided.
Fork, Work, Join: the OpenMP life cycle.

Coverage checklist

data and functional parallelism: May 2022 14-mark parallelism variants.
parallel scalability- laws: Amdahl and Gustafson.
metrics: speedup, efficiency, cost.
factors, efficiency and load imbalance: overheads and imbalance.
Shared memory parallel programming with Open MP: May 2022 7-mark OpenMP question.
Parallel execution: fork-join.
data scoping: covered for the OpenMP question.
work sharing using loops: covered for the OpenMP question.
synchronization: barrier, critical, atomic.
Reductions: reduction clause.
loop scheduling and Tasking: covered for the OpenMP question.

Account

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

How unit 3 is examined

Data and functional parallelism

Parallel scalability laws

Metrics

Factors, efficiency and load imbalance

Shared memory parallel programming with OpenMP

Parallel execution

Data scoping

Work sharing using loops

Synchronization

Reductions

Loop scheduling and tasking

Last-minute revision

Memory hooks

Coverage checklist