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

How unit 2 is examined

This unit covers balance and light speed estimates, storage order, algorithm classes, and the parallel machine types; the marks sit in the sparse matrix-vector case study (blocking and rolling) and the distributed-memory Jacobi flowchart.

Balance analysis and light speed estimates

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Balance analysis compares how many bytes (or words) a loop must move per floating-point operation with how many the machine can supply per operation; the light speed estimate is the best performance this ratio allows.

Key points.

Machine balance is $B_m = b_{max}/P_{max}$, the memory bandwidth divided by the peak floating-point rate, in words per flop.
Code balance is $B_c$ = words transferred to and from memory divided by flops executed by the loop.
The light speed is $l = \min(1, B_m/B_c)$, and the attainable performance is $l \cdot P_{max}$.
If $B_c > B_m$ the loop is memory bound, so optimizing arithmetic will not help; only reducing data traffic will.
Example: the vector triad $A_i = B_i + C_i \cdot D_i$ moves 4 words for 2 flops, so $B_c = 2$ W/F; with $B_m = 0.125$ W/F, $l = 0.125/2 \approx 6\%$ of peak.

Storage order

Definition. Storage order is the way a multidimensional array is laid out in linear memory, either row-major (C) or column-major (Fortran).

Key points.

In row-major order the element $a[i][j]$ of an $M \times N$ array sits at offset $i \cdot N + j$, so the last index is contiguous.
In column-major order the offset is $j \cdot M + i$, so the first index is contiguous.
The innermost loop should run over the contiguous index (stride 1), so that every cache line loaded is fully used.
A wrong loop order gives strided access, wastes cache-line bandwidth and can be several times slower.
Loop interchange, array padding and transposing data are the standard fixes.

Algorithm classifications and assess optimizations

Definition. Algorithms are classified by how their work and data grow with problem size $N$, and this decides which data access optimization can help.

Key points.

Classify by ratio: O(N) work on O(N) data (vector triad, SpMV) is bandwidth bound, with almost no reuse.
O(N log N) work on O(N) data (FFT) has moderate reuse that can be raised by blocking.
O(N^3) work on O(N^2) data (dense matrix multiply) has high reuse and can approach peak after cache blocking.
Optimizations are assessed by comparing measured performance with the light speed estimate; a large gap means the loop can still be improved.
If performance already sits at the light speed, only a better algorithm or data format can help.

Case studies for data access optimizations

Definition. Sparse matrix-vector multiplication (SpMV) computes $y = A x$ where $A$ is stored as only its non-zero entries, so that each non-zero causes one indirect access into $x$.

Storage (CRS). Arrays val (non-zeros), col_idx (their columns) and row_ptr (start of each row).

for (i = 0; i < N; i++)
    for (k = row_ptr[i]; k < row_ptr[i+1]; k++)
        y[i] += val[k] * x[col_idx[k]];   // 2 flops per non-zero

Key points.

The memory problem is that val and col_idx are streamed once with no reuse, while x[col_idx[k]] is an irregular gather that misses the cache when the columns are scattered.
Code balance is about $(8+4)/2 = 6$ bytes per flop even when $x$ stays in cache, far above machine balance, so SpMV is bandwidth bound.
Blocking splits the matrix into row and column blocks small enough that the matching part of $x$ (and $y$) fits in cache, so each loaded $x$ element is reused by many non-zeros before eviction.
Register blocking (BCSR) stores dense $r \times c$ sub-blocks, keeps the $x$ and $y$ pieces in registers, and needs only one column index per block instead of one per non-zero.
Rolling (strip-mining) processes the rows in strips and slides the working window of $x$ along the matrix diagonal, so the part of $x$ just used is still in cache for the next strip, and old data is discarded as the window rolls.
Rolling works best for banded matrices whose non-zeros stay near the diagonal, while blocking also helps matrices with scattered structure.
Both cut traffic on $x$ and $y$, raising the cache hit rate; they cannot remove the traffic on val, so the gain is bounded by the light speed of the matrix stream.
Comparison: blocking gives reuse in space (a fixed tile), rolling gives reuse in time (a moving window); both trade extra loop code (and zero fill for BCSR) for locality.

Example. Blocking a loop with block size $B$ (cache-sized strip of columns):

for (jb = 0; jb < N; jb += B)          // column block: x[jb..jb+B) stays in cache
    for (i = 0; i < N; i++)
        for (k = start[i][jb]; k < start[i][jb+1]; k++)
            y[i] += val[k] * x[col_idx[k]];

Answer frame. Open with "SpMV multiplies a sparse matrix stored in CRS with a vector; its indirect access to $x$ gives poor cache reuse"; draw the CRS arrays for a small matrix; then develop points 1-2 (problem), 3-4 (blocking with the code), 5-6 (rolling), and 7-8 (benefit and comparison table); close with "blocking and rolling raise locality of $x$ and $y$, moving SpMV closer to its bandwidth light speed".

Asked: [14 marks] (May 2022) Explain the blocking and rolling strategies with the help of multiplication of a sparse matrix with a vector.

Shared memory computers

Definition. A shared memory computer has several processors that access one common address space, so they communicate by reading and writing shared variables.

Key points.

In UMA (SMP) all processors reach memory with equal latency over a bus or crossbar, and the shared bus limits how far it scales.
In ccNUMA memory is split into locality domains, each attached to a processor, and remote access is slower, so data placement matters (first touch).
Each processor has private caches, so a cache-coherence protocol must keep copies consistent, and false sharing can hurt performance.
Programming uses threads (OpenMP), and access to shared data needs synchronization.

Distributed memory computers

Definition. A distributed memory computer is a set of processors each with its own private memory, which exchange data only by explicit message passing (MPI send and receive) over a network.

Key points.

The problem is decomposed by domain, and each process stores and updates only its own sub-domain.
For Jacobi, each process needs the boundary rows of its neighbours, kept in ghost (halo) cells that are refreshed every iteration by send and receive.
After the update, the local errors are combined with a reduction (MPI_Allreduce) to test convergence.

Diagram. Flowchart of Jacobi on each process (Init = decompose domain and initialise; Halo = send/receive boundary rows with neighbours; Upd = update interior points; Err = compute local error and Allreduce; Done? = error below tolerance or maximum iterations reached).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 467 209" width="467" height="209" role="img" aria-label="Jacobi on distributed memory: loop until converged or max iterations, then stop"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" 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="ahh2" 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="M59,40 L148,40" marker-end="url(#ah2)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah2)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah2)"/><path class="e" d="M427,59 L427,148" marker-end="url(#ah2)"/><path class="e" d="M408,169 L319,169" marker-end="url(#ah2)"/><path class="e" d="M298,150 L298,61" marker-end="url(#ah2)"/><path class="e" d="M279,169 L190,169" marker-end="url(#ah2)"/><g class="wl"><rect x="284.8" y="95.5" width="26.4" height="18" rx="9"/><text class="t" x="298" y="104.5" dy=".35em" text-anchor="middle">no</text></g><g class="wl"><rect x="216.7" y="160" width="33.6" height="18" rx="9"/><text class="t" x="233.5" y="169" dy=".35em" text-anchor="middle">yes</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">Ini</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Hal</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">Upd</text><circle class="n" cx="427" cy="169" r="18"/><text class="t" x="427" y="169" dy=".35em" text-anchor="middle">Err</text><circle class="n" cx="298" cy="169" r="18"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">Dn</text><circle class="n" cx="169" cy="169" r="18"/><text class="t" x="169" y="169" dy=".35em" text-anchor="middle">E</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Jacobi on distributed memory: loop until converged or max iterations, then stop</figcaption></figure>

Answer frame. Recall that Jacobi replaces each point by the average of its neighbours; draw the flowchart above with "send/receive halo" written in the Halo box and "converged or max iterations?" in the decision; close by noting each process communicates only with its neighbours.

Asked: [7 marks] (May 2022) Draw the flowchart for distributed-memory parallelization of the Jacobi algorithm.

Hybrid systems

Definition. A hybrid system is a cluster of shared-memory nodes joined by a network, combining shared memory inside a node with distributed memory between nodes.

Key points.

Each node has several cores sharing memory, often as ccNUMA, and nodes talk by message passing.
The usual model is hybrid MPI+OpenMP: one MPI process per node or socket with OpenMP threads inside.
This reduces the number of messages and the memory duplicated for halo data, but needs careful thread placement.
Most modern supercomputers are of this type.

Network computers

Definition. Network computers (clusters) are independent computers connected by an interconnect and used together as one parallel machine.

Key points.

Communication cost is modelled as latency plus message size divided by bandwidth: $T = \lambda + n/\beta$.
Topology (bus, ring, mesh, torus, fat tree) fixes the number of hops, the bisection bandwidth and the contention.
High-speed interconnects such as InfiniBand give much lower latency than Ethernet.
Fewer, larger messages are preferred because the latency is paid per message.

Last-minute revision

Machine balance $B_m = b_{max}/P_{max}$; code balance $B_c$ = words per flop; light speed $l = \min(1, B_m/B_c)$.
Vector triad: 4 words for 2 flops, $B_c = 2$ W/F.
Row-major offset is $iN + j$; column-major offset is $jM + i$; keep the innermost loop on the contiguous index.
CRS uses val, col_idx, row_ptr; 2 flops per non-zero; about 6 B/flop.
Blocking = fixed tile of $x$ in cache; rolling = sliding window over strips.
Register blocking (BCSR) keeps dense $r \times c$ blocks and saves index storage.
Shared memory: UMA or ccNUMA, threads, coherence; distributed memory: private memory, MPI messages.
Jacobi on distributed memory: halo exchange, update, Allreduce error, convergence test.
Hybrid = MPI between nodes plus OpenMP inside a node.
Message time $T = \lambda + n/\beta$.

Memory hooks

Balance: "Bandwidth over flops beats compute": if $B_c > B_m$, memory is the limit.
Row-major C: "Right index runs fastest."
CRS = Value, Column, Row-pointer (VCR).
Blocking = Box (tile); Rolling = Roll (window slides).
Jacobi loop = Halo, Update, Reduce, Check.

Coverage checklist

balance analysis and light speed estimates: balance, light speed, triad example.
storage order: row and column-major, stride.
Algorithm classifications and assess optimizations: classes by reuse, gap to light speed.
case studies for data access optimizations: SpMV blocking and rolling (May 2022, 14 marks).
Shared memory computers: UMA, ccNUMA, coherence.
Distributed memory computers: Jacobi flowchart (May 2022, 7 marks).
hybrid systems: MPI+OpenMP.
Network computers: latency-bandwidth model, topology.

Account

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

How unit 2 is examined

Balance analysis and light speed estimates

Storage order

Algorithm classifications and assess optimizations

Case studies for data access optimizations

Shared memory computers

Distributed memory computers

Hybrid systems

Network computers

Last-minute revision

Memory hooks

Coverage checklist