Unit 1.1 · about 4 h
230 / 324Instruction pipelines, branches and SIMD
Assume Programming's layout-alignment-locality and profiling-benchmarking units. Here the mechanism is instruction execution: dependencies, speculation and SIMD determine which work can overlap before the kernel or storage enters the picture.
- explain
You can now
- Explain pipeline overlap, instruction dependencies and branch recovery without equating clock cycles with instructions.
- Identify SIMD lanes, loop tails and a loop-carried dependency in compiler output.
- Separate a compiler's vectorization decision from evidence of a runtime speedup.
Covers
- Instructions, dependencies, pipelines and branch behavior vocabulary
- SIMD lanes, scalar work and vectorization limits
Study, in this order
4 steps
- Throughput processors: superscalar, speculation and SIMDMIT 6.S894 Accelerated Computing - Throughput Processors
Lecture 2, Throughput Processors (slides; the recording is linked from the Lectures page): slides 4 to 10, a processor as an instruction interpreter, superscalar issue, out-of-order execution and speculation; slides 25 to 28, SIMD execution and why it needs coherent control
Depth · Stop at slide 29. Multicore scaling, latency hiding by interleaving and the GPU walkthrough return in the GPU track.
- Pipeline hazards and the cost of branchingAlgorithmica - Algorithms for Modern Hardware
Instruction-Level Parallelism: Instruction Pipelining; Pipeline Hazards; The Cost of Branching: An Experiment, Branch Prediction and Pattern Detection; Branchless Programming: Predication and When Predication Is Beneficial
Depth · The cycle counts are the author's, on a Zen 2 laptop at a fixed 2 GHz. Use them as a model of the effect, not as numbers for your CPU. Skip Hinting Likeliness of Branches and Larger Examples.
- SIMD and the limits of auto-vectorizationAlgorithmica - Algorithms for Modern Hardware
SIMD Parallelism (chapter introduction); Auto-Vectorization and SPMD: Potential Problems
Depth · Its timings and flags are GCC on Zen 2, while the Reproduce uses Clang. Skip the intrinsics, shuffle and SPMD material.
- Clang vectorization remarksAuto-Vectorization in LLVM
The Loop Vectorizer: Usage and Diagnostics, for the
-Rpass=loop-vectorize,-Rpass-missed=loop-vectorizeand-Rpass-analysis=loop-vectorizeremarksDepth · Use it as the reference for the Reproduce flags. The Features list is optional.
Focus on
- Pipeline overlap improves throughput, not necessarily the latency of one instruction. Dependencies limit overlap; a wrong branch prediction discards speculative work.
- Instruction count, CPI and clock period all enter execution time. Out-of-order execution schedules ready work but must preserve architectural behavior.
- SIMD widens independent operations. Tails, alias checks, calls and recurrences constrain the generated loop; unrolling is not itself SIMD.
- If conversion can replace branches. Inspect the executable before calling an input-order timing difference a branch-prediction effect.
Reproduce closed-book
noinline bump(uint32_t *a, unsigned n) with a[i] += 1u for \(i = 0, \dots, n-1\), and noinline chain with a[i] += a[i-1] for \(i = 1, \dots, n-1\). In main set a[i] = i for 1031 elements, call bump, sum into uint64_t and print it, then call chain and print a[1030]. Compile with clang -O3 -march=x86-64-v3 -Rpass=loop-vectorize -Rpass-missed=loop-vectorize, and again with -fno-vectorize -fno-slp-vectorize. Run both with taskset -c 2. Both print 531996 twice. On Clang 21.1.8, bump vectorizes with eight uint32_t lanes and chain does not; confirm packed additions and the scalar tail with objdump -d. This is a correctness and instruction observation, not a timing claim.Traps
- Counting SIMD lanes as a promised speedup. Loads, stores, dependencies and loop overhead still consume resources.
- Using signed overflow or floating-point reassociation as an exact correctness oracle. Use unsigned arithmetic here; floating-point reductions need a stated error criterion.
- Timing a loop the compiler folded away, or attributing branch misses to source-level
ifstatements that became branchless code.
Practice
The section mini-project covers this: a correctness-checked scalar/vectorized kernel, dependency and branch variants, saved assembly, and pinned repeated measurements with compiler flags and warm-up state.
Self-test
-
In Algorithmica's experiment, summing the elements below 50 of a random array costs about 14 cycles per element, and a little over 4 once the same array is sorted. What changed?
Only the order. Sorted input makes the branch predictable, so speculative work is rarely discarded; random input mispredicts about half the time, and each miss refills the pipeline (19 stages on the author's Zen 2). The figures are the author's, not a prediction for your CPU. -
Why does
chainnot have the same independent lanes asbump?Iteration \(i\) needs the value written by iteration \(i-1\). A simple widening would read the wrong predecessor; a different algorithm such as a parallel scan is needed. -
Does a vectorization remark prove the vector loop ran for a particular call?
No. A small length, tail or runtime alias check can select a scalar path. Inspect the call's inputs and generated control flow. -
Can a predictable branch be cheaper than computing both arms?
Yes. Prediction can avoid unnecessary work. Which version wins depends on the generated code and workload and must be measured.
Completion criterion
Stop when
Both builds agree on the checksum and recurrence endpoint, and you can mark the vector lanes, scalar tail and dependency in the executable without promising a speedup.
Mark passed, then open 1.2 Only mark this when you can do it without notes.Leads to
- 1.2 Caches, working sets, bandwidth and NUMA Explain why wider arithmetic still has to wait for data.
Comes after
- 1.10 Binary logic and machine language with Nand2TetrisReturn to instruction dependencies once register and memory effects are concrete.
Resources for this unit
- Algorithmica - Algorithms for Modern Hardware Use the Instruction-Level Parallelism, SIMD Parallelism and RAM & CPU Caches chapters for measured pipeline, branch, vectorization, bandwidth, latency and cache-line effects. The figures are the author's Zen 2 measurements at a fixed 2 GHz: predict and measure your own.
- MIT 6.S894 Accelerated Computing - Throughput Processors Use Lecture 2 for the processor model behind this section: superscalar issue, out-of-order execution, speculation and SIMD's need for coherent control. The labs run on the course's remote machines and target AVX-512 and NVIDIA GPUs, so they belong to the GPU track.
- Auto-Vectorization in LLVM Use The Loop Vectorizer Usage and Diagnostics sections for the Clang remarks the pipelines unit asks for; the Features list is optional depth.
Also in this section
- Operating Systems: Three Easy Pieces - selected foundations Read Chapters 4-7, 13-15, 18-21, 36, 39-40, 42 and 45. Work from process state to address translation, devices, files, journaling and integrity. For every chapter, draw the owned state and one failure boundary instead of collecting summaries.
- MIT 6.1810 - selected xv6 process and memory labs Use Fall 2025 Lectures 1, 3-6, 8 and 10-11. Complete the util lab, one syscall task, and the page-table inspection plus ugetpid task from pgtbl. Add cow only if copy-on-write remains unclear. Keep all work in your own course checkout and stop before the full xv6 sequence.
- OSTEP homework - process, paging, disk and integrity simulators Solve process-run.py, paging-linear-translate.py, paging-policy.py, disk.py, fsck.py and checksum.py for at least two seeds each before using the answer flag. Then reproduce one prediction using strace, /proc or a small local program.
- AlgoMaster Operating Systems - selected observation route After OSTEP, use the matching lessons as a second explanation and recall check: fork, exec, wait, and exit; Zombies and Orphans; Signals; Context Switching; The Process Address Space; Paging; The TLB: Hits, Misses, and Invalidation; Page Faults; Copy-on-Write; mmap and Memory-Mapped Files; How malloc Works; VSZ, RSS, PSS, and What They Mean; File Descriptors; The Page Cache and Write-Back; Durability and fsync; Crash Consistency; Linux Namespaces; Control Groups; PID 1 and Signal Handling; Container Resource Failures; and the Investigating lessons. Treat quizzes as recall checks and keep your own traces as evidence.
- Linux proc and strace references Use proc(5), getrusage(2), mmap(2), fsync(2), rename(2), wait(2) and signal(7) while tracing a parent-child pipe, page faults, file publication and a resource-limit failure. Record exact commands and raw observations.
- Nand2Tetris - Projects 1 and 4 only Use Project 1 for Boolean logic and Project 4 for machine-language execution only if the binary or instruction-level entry check fails. Do not take the full course as a second systems curriculum.
- AlgoMaster: hardware and container storage companions Use Memory Ordering, Barriers, and False Sharing (coherence and false-sharing headings only); Huge Pages, NUMA, and ASLR (NUMA headings only); Storage Hardware; RAID Fundamentals (comparison and backup boundaries); and Container File Systems. These fill hardware and image-layer gaps outside the pool's selected OS revision lessons.