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

How unit 1 is examined

This unit covers processor architecture (cache, pipelining, superscalar, SIMD, multicore, vector) and serial optimization; the marks sit in Moore's law (with the scalability, bandwidth-model and virtual-topology options), the cache block diagram, the multicore/multithreaded/vector comparison, scalar profiling and C++ optimizations.

General Purpose cache based architecture

<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">Low weight</span>

Definition. A cache-based microprocessor keeps small, fast on-chip memories (L1, L2, L3) between the CPU core and slow main memory, so that most accesses are served quickly and memory latency is hidden.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 596 217.6" width="596" height="217.6" role="img" aria-label="CPU core, L1 (split I/D), L2, L3 cache, MMU (address translation), bus interface unit (BIU) with address/data/control buses to main memory"><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" 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="ahh1" 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="M61,40 L148,40" marker-end="url(#ah1)" marker-start="url(#ah1)"/><path class="e" d="M190,40 L277,40" marker-end="url(#ah1)" marker-start="url(#ah1)"/><path class="e" d="M319,40 L406,40" marker-end="url(#ah1)" marker-start="url(#ah1)"/><path class="e" d="M53,53.9 L154.6,162.3" marker-end="url(#ah1)"/><path class="e" d="M427,61 L427,156.6" marker-end="url(#ah1)" marker-start="url(#ah1)"/><path class="e" d="M445.5,167.7 L537.5,118.7" marker-end="url(#ah1)" marker-start="url(#ah1)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">CPU</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">L1</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">L2</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">L3</text><circle class="n" cx="169" cy="177.6" r="18"/><text class="t" x="169" y="177.6" dy=".35em" text-anchor="middle">MMU</text><circle class="n" cx="427" cy="177.6" r="18"/><text class="t" x="427" y="177.6" dy=".35em" text-anchor="middle">BIU</text><circle class="n" cx="556" cy="108.8" r="18"/><text class="t" x="556" y="108.8" dy=".35em" text-anchor="middle">MEM</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">CPU core, L1 (split I/D), L2, L3 cache, MMU (address translation), bus interface unit (BIU) with address/data/control buses to main memory</figcaption></figure>

Key points.

The CPU core (registers, ALU, control) works at the highest speed, so it is fed by the L1 cache, split into instruction and data caches.
L2 and L3 are progressively larger and slower, and L3 is often shared between cores.
The MMU translates virtual addresses to physical ones and protects memory.
The bus interface unit connects the last cache level to main memory over address, data and control buses.
Caches work because of temporal and spatial locality; data moves in cache lines.

Asked: [7 marks] (May 2022) Draw the block diagram of a typical cache-based microprocessor.

performance metric and bench marks

Definition. A performance metric measures how fast a program runs; a benchmark is a standard program used to compare machines fairly.

Key points.

Common metrics are execution time, FLOPS (floating-point operations per second), MIPS, speedup and efficiency.
Speedup is $S = T_{serial}/T_{parallel}$.
LINPACK (used for the Top500 list), SPEC CPU and STREAM (memory bandwidth) are standard benchmarks.
Peak performance is a theoretical limit; sustained benchmark performance is always lower.

Moors Law

Definition. <mark>Moore's law states that the number of transistors on an integrated circuit doubles roughly every two years, so processing capability grows exponentially at falling cost.</mark>

Key points (a: Moore's law).

Gordon Moore observed in 1965 that the transistor count doubled every year and revised it in 1975 to every two years.
More transistors gave more cache, deeper pipelines, superscalar units and wider SIMD, so performance rose steadily.
Clock speed stopped rising around 2005 because power and heat grow steeply with frequency (the power wall).
The extra transistors are therefore spent on multiple cores, so HPC now needs parallel programs to gain speed.
It is an empirical trend, not a physical law, and it is slowing as feature sizes reach atomic limits.

Scalability laws (b). Amdahl's law for serial fraction $s$ on $N$ processors gives $S = \dfrac{1}{s + (1-s)/N}$, which is bounded by $1/s$. Gustafson's law for a scaled problem gives $S = N - s(N-1)$. Efficiency is $E = S/N$.

Bandwidth-based performance modelling (c). Many loops are limited by memory, not the ALU. With code balance $B_c$ (bytes moved per flop) and memory bandwidth $b_S$, performance is $P = \min(P_{peak},\; b_S/B_c)$.

Virtual topologies (d). MPI can arrange processes as a logical Cartesian grid or graph (MPI_Cart_create), independent of the physical network, so neighbours map naturally to the problem and communication is simpler and can be faster.

Answer frame. Open with the definition; state 1965/1975 doubling; develop points 1-5 in order; for the second option add one of (b), (c) or (d) with its formula; close with: Moore's law now delivers cores, not clock speed, so parallel programming is essential.

Asked: [14 marks] (May 2022) Short note (any two): a) Moore's law b) Scalability laws c) Bandwidth-based performance modelling d) Virtual topologies

pipelining

Definition. Pipelining splits an instruction into stages (fetch, decode, execute, memory, write-back) so that different instructions occupy different stages at the same time.

Key points.

In steady state one instruction completes per cycle, though each still takes $k$ cycles.
For $n$ instructions and $k$ stages, time is $(k+n-1)$ cycles instead of $nk$.
Speedup approaches $k$ for large $n$; hazards (data, control, structural) and branch mispredictions cause stalls.

super clarity

Definition. This topic is superscalar execution: a processor with several functional units issues more than one instruction per cycle.

Key points.

Hardware finds independent instructions at run time (instruction-level parallelism) and issues them together.
Out-of-order execution and branch prediction keep the units busy.
Peak rate equals issue width times clock frequency, e.g. 4 flops per cycle at 3 GHz gives 12 GFlops.

SIMD

Definition. SIMD (Single Instruction, Multiple Data) applies one instruction to several data elements held in a wide register.

Key points.

Examples are SSE (128-bit), AVX (256-bit) and AVX-512; AVX holds 4 doubles per register.
It gives data parallelism inside one core, and compilers vectorise loops automatically.
Data must be contiguous and aligned, and loops need no dependences, for full speed.

Memory Hierarchies

Definition. A memory hierarchy is a layered set of memories: registers, L1, L2, L3, main memory and disk, from fastest and smallest to slowest and largest.

Key points.

It exploits temporal and spatial locality to give the illusion of a large, fast memory.
Latency and size grow, and cost per byte falls, at each level down.
Average access time is $t_{avg} = h\,t_{cache} + (1-h)\,t_{mem}$, where $h$ is the hit ratio.
Blocks are moved as cache lines, and misses are compulsory, capacity or conflict.

Multi core processors

Definition. A multi-core processor places two or more independent cores on one chip, sharing the caches and memory interface.

Key points.

Each core runs its own thread, giving true thread-level parallelism.
Cores gain performance without higher clock speed, so power stays manageable.
Software must be parallel (OpenMP, threads) to benefit.

Feature	Multi-core	Multithreaded	Vector
Idea	Many full cores on one chip	Many threads share one core's units	One instruction on long vectors of data
Execution model	MIMD, one thread per core	Switch or interleave threads to hide stalls	SIMD
Parallelism	Thread-level, real	Thread-level, resource shared	Data-level
Hardware added	Duplicate cores	Duplicate register sets and PC	Vector registers and pipelined units
Best for	General parallel programs	Latency-bound code	Regular array loops
Example	Intel Core i7	Intel Hyper-Threading	NEC SX, Cray-1

Asked: [7 marks] (May 2022) Differentiate Multi-core, Multithreaded and Vector processors.

Multi threaded processors

Definition. A multithreaded processor keeps the state of several threads on one core and switches between them so that stalls of one thread are hidden by another.

Key points.

Kinds are coarse-grained, fine-grained and simultaneous multithreading (SMT, Intel Hyper-Threading).
SMT issues instructions from several threads in the same cycle.
It improves utilisation of functional units at small hardware cost, but threads share cache and units.

Vector processors- Design principle

Definition. A vector processor has instructions that operate on whole vectors of data, using vector registers and deeply pipelined functional units.

Key points.

One vector instruction replaces a whole loop, so fetch and decode overhead falls.
Vector registers hold, say, 64 elements, and results stream out one per cycle after the pipeline fills.
High-bandwidth interleaved memory feeds the pipes, and chaining forwards results between units.
Performance is good for long, regular, independent loops.

Max performance estimates

Definition. Maximum (peak) performance is the theoretical flop rate of a processor.

Formula. $P_{peak} = \text{cores} \times \text{clock} \times \text{flops per cycle}$.

Key points.

Example: 8 cores, 2.5 GHz, 16 flops per cycle gives $8 \times 2.5 \times 16 = 320$ GFlops.
Real code reaches only a fraction because of memory limits, dependences and poor vectorisation.
The bandwidth bound $b_S/B_c$ gives a tighter limit for memory-bound loops.

programming for vector architecture

Definition. Programming for vector architecture means writing loops so the compiler can turn them into vector instructions.

Key points.

Use simple countable loops with unit-stride access and no loop-carried dependences.
Avoid function calls, branches and pointer aliasing inside the loop; use restrict or pragmas such as #pragma omp simd.
Align data, use long vector lengths, and read the compiler vectorisation report.

Scalar profiling

Definition. Scalar profiling measures where a serial program spends its time, so that optimization targets the real hotspots.

Key points.

Function-based profiling (e.g. gprof) records, for each function, time spent, number of calls and the call graph.
Line-based profiling records time per source line or loop, showing the exact statement that is slow.
It is done by sampling or instrumentation, and hardware counters can add cache misses and flops.
Always profile before optimizing, and re-profile after.

Asked: [7 marks] (May 2022) What do you mean by scalar profiling? Explain function and line-based profiling.

common sense optimizations

Definition. Common sense optimizations are simple serial changes that avoid useless work, before any advanced tuning.

Key points.

Do less work: hoist loop-invariant code and avoid repeated computation.
Replace expensive operations, such as division by multiplication with a reciprocal and pow by multiplication.
Avoid small functions and branches in inner loops, and access memory in contiguous order.

Simple measures and their impacts

Definition. These are easy measures such as compiler flags, correct data layout and a good algorithm, with the speedup they give.

Key points.

Turning on -O2/-O3 often gives a several-fold gain over -O0.
Choosing a better algorithm beats micro-tuning.
Contiguous access and blocking reduce cache misses and can give large speedups.

role of compilers

Definition. The compiler translates source code to machine code and, with optimization on, restructures it to run faster.

Key points.

It performs inlining, loop unrolling, common-subexpression elimination, register allocation and instruction scheduling.
It vectorises loops and can prefetch data.
Flags such as -O3, -march=native and -ffast-math control it, but aliasing and dependences limit it.

C++ optimizations

Definition. C++ optimizations are techniques that remove the overhead of abstraction so that C++ code runs as fast as plain C.

Key points.

Enable compiler optimizations (-O3, -march=native) and use inline to remove call overhead, with loop unrolling for inner loops.
Avoid temporary objects: pass by const reference, use move semantics and reserve container capacity.
Prefer contiguous containers (std::vector) and structure-of-arrays for cache efficiency.
Avoid virtual calls and dynamic allocation in hot loops; use templates for static polymorphism.

Asked: [7 marks] (May 2022) Discuss C++ optimizations.

Last-minute revision

Moore's law: transistors double about every 2 years (1965 yearly, 1975 revised).
Clock speed stalled near 2005 (power wall), so chips gained cores.
Amdahl: $S = 1/(s + (1-s)/N)$; Gustafson: $S = N - s(N-1)$; $E = S/N$.
Bandwidth model: $P = \min(P_{peak}, b_S/B_c)$.
Cache hierarchy: L1 fastest and smallest, then L2, L3, main memory.
Pipeline of $k$ stages, $n$ instructions: $k+n-1$ cycles.
$P_{peak}$ = cores x clock x flops per cycle.
SIMD: one instruction, many data; AVX has 4 doubles.
Multi-core = many cores; multithreaded = many threads per core; vector = long data vectors.
Profiling: function-based (gprof) versus line-based; profile first.

Memory hooks

Moore = More transistors, not more GHz.
Cache levels: L1 Little and fast, L3 Large and slow.
Multi-core = many brains; multithreaded = one brain juggling; vector = one order, many items.
Profile, then polish.

Coverage checklist

General Purpose cache based architecture: cache block diagram question.
performance metric and bench marks: no past question.
Moors Law: Moore's law, scalability laws, bandwidth modelling, virtual topologies short note.
pipelining: no past question.
super clarity: no past question.
SIMD: no past question.
Memory Hierarchies: no past question.
Multi core processors: multi-core, multithreaded, vector differentiation.
Multi threaded processors: covered in the comparison table.
Vector processors- Design principle: covered in the comparison table.
Max performance estimates: no past question.
programming for vector architecture: no past question.
Scalar profiling: function and line-based profiling.
common sense optimizations: no past question.
Simple measures and their impacts: no past question.
role of compilers: no past question.
C++ optimizations: discuss C++ optimizations.

Account

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

How unit 1 is examined

General Purpose cache based architecture

performance metric and bench marks

Moors Law

pipelining

super clarity

SIMD

Memory Hierarchies

Multi core processors

Multi threaded processors

Vector processors- Design principle

Max performance estimates

programming for vector architecture

Scalar profiling

common sense optimizations

Simple measures and their impacts

role of compilers

C++ optimizations

Last-minute revision

Memory hooks

Coverage checklist