2/3/26: Intro & Matrix Multiplication

Why Performance Engineering?

Performance is not the only goal, but it enables others.

• Correctness, modularity, maintainability, portability, usability, security
• Performance can often be traded for these properties

Why performance no longer comes for free

• Moore's Law: transistor count $\approx 2\times$ every $\sim$2 years
• 1990s--early 2000s: “free” speedups from
  • higher clock rates
  • smaller transistors $\Rightarrow$ lower voltage/energy per operation (Dennard scaling)
• Around 2004: power/thermal limits $\Rightarrow$ clock rates stopped scaling quickly
  • single-thread speedups became much slower
  • extra transistors went into more cores + wider datapaths + bigger caches
• Modern performance gains typically require software to exploit:
  • parallelism: use many cores effectively (avoid overhead, load imbalance)
  • memory hierarchy: optimize locality to reduce cache misses / bandwidth limits
  • SIMD/vectorization: do multiple ops per instruction (often needed to approach peak)

Case Study: Matrix Multiplication

Compute $C = AB$, where $A,B,C \in \mathbb{R}^{n \times n}$.

Assume row-major layout.

Peak Performance Model

Machine parameters (example):

• 2.9 GHz CPU
• 2 sockets, 9 cores/socket
• 16 FLOPs / cycle (FMA)

Implementation Ladder

Why?

• Python is interpreted.
• C is compiled directly to machine code.
• Java is compiled to byte-code, which is then interpreted and just-in-time (JIT) compiled to machine code.

JIT compilation can recover some performance lost to interpretation:

• Code starts out interpreted.
• The runtime profiles execution (tracks which functions/loops are “hot”).
• Hot code is compiled to machine code during execution.
• Later executions reuse the compiled version (faster than interpreting).

Loop Ordering and Locality

Same math, wildly different runtime due to memory behavior (row-major arrays).

Spatial locality: accessing nearby addresses so a fetched cache line is reused.

• CPU loads memory in cache lines (blocks). If you access with unit stride, each line gives many useful elements.
• Unit-stride (good): inner loop walks across a row (contiguous).
• Strided access (bad): inner loop jumps by $\approx n$ elements (e.g., walking down a column in row-major).

Matrix multiply: $C[i][j] \mathrel{+}= A[i][k] \cdot B[k][j]$

• If inner loop is $k$ (order $i,j,k$):
  • $A[i][k]$ is unit-stride (good)
  • $B[k][j]$ is strided (bad) $\Rightarrow$ many cache misses
• If inner loop is $j$ (order $i,k,j$):
  • $B[k][j]$ becomes unit-stride (good)
  • $C[i][j]$ updates are unit-stride (good)

Compiler Optimizations

Clang provides a collection of optimization switches. You can specify a switch to the compiler to ask it to optimize.

• -O0: no optimization
• -O1/-O2: major gains
• -O3: diminishing returns

Also -Os, which aims to limit code size, and -Og, for debugging purposes.

Multicore Parallelism

cilk_for loop enables all iterations of the loop to execute in parallel

• Parallelize outer loops (coarse-grained)
• Avoid fine-grained parallelism (high overhead)

Cache-Oblivious Algorithms

• Recursively split matrices into submatrices.
• Subproblems operate on contiguous blocks $\Rightarrow$ good cache locality.
• Independent subproblems can run in parallel.

Vectorization (SIMD)

• SIMD: single instruction operates on multiple data elements.
• Compilers can auto-vectorize simple loops (-O2 or higher).
• Auto-vectorization is conservative for portability.
• Intrinsics allow explicit use of vector instructions for higher performance.

Final Takeaways

• Measure performance empirically
• Optimize memory access before compute
• Use compiler optimizations
• Add parallelism carefully
• SIMD is required to approach peak

2/5/26: Bit Hacks

Bitwise ops + shifts

• Operators: $\&$ AND, $\mid$ OR, ^ XOR, $\sim$ NOT, $\ll$ left shift, $\gg$ right shift
• Shifts drop bits that fall off the edge
• Hex is compact since 1 hex digit = 4 bits

Binary representation + two's complement

• Unsigned: value is $\sum_{i=0}^{w-1} x_i2^i$
• Signed: value is $-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2} x_i2^i$
• $x + \sim x = -1$
• All 0s = $0$, all 1s = $1$.
• This makes signed add/sub work the same way as unsigned in hardware

Core patterns

Single-bit masking Let mask $m = (1 \ll k)$.

• Set bit: $x \mid = m$
• Clear bit: $x \&= \sim m$
• Toggle bit: $x $^$=m$

Bit fields

• Extract field (mask + shift):

  \[\texttt{\text{field} = (x \& \text{mask}) $\gg$ \text{shift}}\]

• Set field (clear then insert $y$):
  \[\texttt{x $\leftarrow$ (x \& \text{mask}) $\sim$ ((y $\ll$ \text{shift}) \& \text{mask})}\]

  Must mask else higher bits of $y$ can spill.

A circular buffer is a fixed-size array that you treat like its ends are connected in a loop. FIFO.

• We can do modulo: $\texttt{x = (x+1) \% (1 $\ll$ k)}$
• For a mask, we can do

  \[\texttt{x = (x+1) \& ((1 $\ll$ k)-1)}\]

Powers of 2

Least-Significant 1: compute mask of the least-significant $1$ in word $x$.

How do we find the index of the bit lg r, or $\log_2{r}$?

Is an Integer a Power of 2?

Count Trailing Zeros: compute lg r.

A deBruijn sequence $s$ of length $2^k$ is a cyclic 0 - 1 sequence such that each of the $2^k$ 0 - 1 strings of length $k$ occurs exactly once as a substring of $s$.

To calculate ctz (hardware __builtin_ctz(int x)):

• Isolate lowest set bit: \[ \texttt{b = x \& (-x)} \]

  so $b = 2^i$ where $i = \texttt{ctz}(x)$.

• Multiply by a deBruijn constant $C$ (bits of $C$ form a deBruijn cycle):
  \[ y = b \cdot C \]

  Since $b$ is a power of two, this is just a shift of $C$.

• Extract a $k$-bit index from the top bits:
  \[ \texttt{idx} = y \gg (w-k) \]

  where $w$ is the word size in bits.

• Lookup table maps the unique index back to the bit position:

  \[ \texttt{ctz}(x) = \texttt{convert[idx]} \]

Round Up to a Power of 2 or __builtin_clz(int x):

• $n \leftarrow n-1$ to avoid rounding up when $n$ is already a power of 2.
• Bit-smear (propagate MSB downward): \[ n \mathrel{|}= n \gg 1;\; n \mathrel{|}= n \gg 2;\; n \mathrel{|}= n \gg 4;\;\dots \]

  After this, $n$ is all 1s below its top 1-bit.

• $n \leftarrow n+1$ to carry into the next power of 2.

Swapping

No-Temp Swap

Note that x = (x ^ y) ^ y. However, this is poor at exploiting instruction-level parallelism (ILP), or simultaneous execution of a sequence of instructions. There is instruction dependence.

Branches and predictability

• Data-dependent branches are hard to predict, and any mispredict will flush the pipeline.
• Loop-control branches are usually predictable.

Minimum of Two Integers without Branching

• if $xy ^(x ^ y) = $x$.
• Else, we get y ^((x ^ y) & 0) = y.

Merging Two Sorted Arrays

Branches still depend on data, which is often unpredictable. There exist a branchless approach but is often slower as compiler optimizes branching version too.

Branchless Approach: Replace the inside of first while loop with:

Modular Addition Can reduce to one compare/sub, assuming $0 \le x,y < n$.

• $z = x+y$
• $r = z$ if $z < n$, else $r = z-n$.

Popcount (numbers of 1s)

Methods

• Repeated clear LS1: x &= (x-1) until $x = 0$
• Table lookup by bytes (memory-latency sensitive). Example is table size of $256$, shift $8$ each time.
• Parallel divide-and-conquer (mask-and-add). $\Theta(\text{lg} w)$ time.
• or just use __builtin_popcount(int x)

Queens Problem: number of ways to place $n$ queens on an $n \times n$ board, such that no two are attacking each other.

A solution is using backtracking. How should the board be represented to facilitate Queen placement?

State as bitvectors: track blocked columns for next row using

• down: occupied columns
• left: blocked by diagonals shifting left
• right: blocked by diagonals shifting right

Let mask be $n$ low bits set (limits us to board width). Then available positions:

aka no conflicts.

Iterate placement using LS1:

• \text{place = possible & $\sim$ possible}
• \text{possible & = $\sim$ place}

Update for recursion:

• down' = down $\mid$ place
• left' = ((left $\mid$ place) $\ll$ 1) & mask
• right' = ((right $\mid$ place) $\gg$ 1)

2/10/26: Bentley Rules for Optimizing Work

Work and Why We Care

• Less work $\neq$ faster code.
• Reducing the work doesn't automatically reduce running time.
• It does serve as a good heuristic for reducing overall running time.

Bentley Rules: Overview

Checklist of low-level performance optimizations.

Data Structures

• Packing: store more than one data value in a single machine word.
• Encoding: convert data values into a representation that requries fewer bits
• An example where we pack dates (requiring more than 2 64-bit words) into just 22 bits (assuming between 4096 BCE and 4096 CE)
  
• Augmentation: add extra information to a data structure to make it more efficient to use.
  • An example would be adding a tail pointer to a linked list
• Caching: store frequently accessed data in a faster memory location.
• Precomputation: perform calculations in advance to avoid doing them at critical times (aka lookup tables)
  • An example would be precomputing the Fibonacci sequence up to a certain number
• Compile-time initialization: store values of constants during compilation
  • create large static tables by meta-programming or multi-stage programming
  • it is about when the table gets materialized
• Sparsity: avoid storing and computing values that are zero
  

  Here, they store a matrix using just $O(n+nnz)$ space, instead of $O(n^2)$ space. Number of scalar multiplications is $nnz$.

  

  All neighbor vertex IDs are concatenated back-to-back.

Logic & Functions

• Constant folding & propagation: evaluate constant expressions and substitute result into further expressions, so that they are evaluated during compile time.
• Common-Subexpression Elimination: identify and reuse identical subexpressions.
• Algebraic identities: replace expensive algebraic expressions with algebraic equivalents that require less work.
  
• Creating a fast path: handle the common case with a minimal code path, fall back to slow path for rare cases.
• Short-circuiting: evaluate logical expressions from left to right, stopping when the result is determined.
  
• Ordering tests: put the cheapest or most-likely-to-fail checks to exit early.
• Inlining: replace function call with function body. Can start function definition with inline keyword.
• Tail-recursion elimination: Remove overhead of recursive call by using a loop when possible.
• Coarsening recursion: Reduce recursion depth by doing bigger chunks per call.

Loops

• Loop unrolling: do multiple iterations of the loop at once. Will result in fewer branches/loop counter ops and more ILP. However, it results in poor use of instruction cache.
• Hoisting: move loop-invariant computations outside the loop.
• Sentinels: special dummy values placed in data structure to simplify logic of boundary conditions.
  
• Loop fusion/jamming: combine multiple loops over same index range into a single loop body.
• Eliminating Wasted Iterations: modify loop bounds to avoid executing loop iterations that are not needed.

2/12/26: Assembly Language and Computer Architecture

Why this is in Performance Engineering

Performance engineering is a jack-of-all-trades: once you can’t reduce work further, the next lever is reducing cycles per unit work by making the machine execute that work more efficiently.

From C to Running Program

• Four compilation stages: preprocess -> compile to assembly -> assemble to object -> link into an executable
  
• Assembly is the human-readable view of machine code. Lets you verify what the compiler actually did
  • Debug work at -O0 but breaks at -O3 style issues, cause sometimes the compiler is the source of the bug
• Disassembly: if you only have a binary/library, you can still inspect assembly to understand behavior (aka reverse-engineering)

x86-64 ISA primer

Mental model: assembly lines are opcode + operands, where operands can be registers, immediates, or (at most one) memory operand.

Registers

x86-64 has 16 general purpose registers, each has multiple names for subparts. There are also vector registers (xmm/ymm/zmm) used for SIMD.

• general-purpose registers are aliased: each has multiple names, referring to overlapping bytes in register.
  
• format: <opcode> <operand\_list>
  • <opcode> is short mnemonic identifying the type of instruction
  • <operand\_list> is 0,1,2, or (rarely) 3 operands, separated by commas

Opcode

• Common categories: data movement, arithmetic, logic, control-flow
• suffixes like q/l/w/b indicate operand width, and there's a C <-> assembly type mapping
  
• Branches depend on flags (RFLAGS): cmp/test set flags, jcc checks a condition code (je, jne, jge)
  

jcc: jump if condition code

• ZF: zero flag
• SF: sign flag
• CF: carry flag
• OF: overflow flag

Operands

Operands of an instruction specify values using a variety of addressing modes. direct addressing modes

• Immediate: use the specified value
• Register: use the value in the specified register
• Direct memory: use the value at the specified memory address

indirect addressing modes

• Register indirect: the address is stored in the specified register
• Register indexed: the address is a constant offset of the value in the specified register
• Instruction-pointer relative: the address is a constant offset of the instruction pointer
• Base indexed scale displacement: refer to address Base + Index * Scale + Displacement

use godbolt to visualize assembly

Modern Computer Architecture

Simple 5-Stage Processor

Intel Haswell

What changed to get to a modern architecture like the Haswell?

Pipeline + Stalls

• Pipelining increases throughput by overlapping stages
• Real pipelines stall due to three hazards: structural (resource conflict), control (branches), and data (dependencies).

Dealing with structural hazards

More functional units + superscalar front-end

• Real CPUs split work across multiple functional units/ports; ops might have multi-cycle latency
• use separate functional units for complex operations, like floating-point arithmetic
  
• Superscalar means fetching/decoding/issuing multiple micro-ops per cycle to keep units busy

x86 instructions are often decoded into micro-ops.

Dealing with control hazards

Speculation and branch prediction

• To handle a control hazard, processor either stalls at the branch or speculatively executes past it. It must roll back on mispredict, but they are expensive.
• Modern processors use branch predictors to increase effectiveness of speculative execution (accurate about $95\%$ of time)
• Simple predictor model: per-branch 2-bit saturating counter
  

Dealing with data hazards

Bypassing and Out-of-Order and Renaming

Types of data hazards

• True dependence (RAW): instructon writes to a location that instruction right after reads
• Anti-dependence (WAR): instruction reads a location that an instruction later on writes
• Output-dependence (WAW): multiple instructions write to the same location

• Bypassing/forward: use a computed value before it's written back to register file to reduce stalls
• Out-of-order execution: issue instructions as soon as their true (RAW) inputs are ready, don't wait for program order.
• Register renaming: eliminate fake name dependencies (WAR/WAW)by mapping architectural regs to many physical regs

2/13/26: Recitation 2

Tips for Bit Manipulation

• If manipulating bits, generally want to use unsigned ints, else use signed int.
  • Underflow in unsigned numbers (such as $N \rightarrow 0$ for loop) doesn’t work nicely
• Use the appropriate literals
• Never shift by more than the number of bits in the number, could result in undefined behavior.
• Never shift by a negative amount.

Shifting Columns

Problem: Input: N x N matrix of bits, stored in row-major order.

Goal: Circularly rotate ith column of bits up i rows.

Solution:

Rounding

Problem: Given a floating point number $x$, round it to the nearest integer.

Solution:

2/19/26: Autovectorization

Historical Motivation

Multimedia instructions are

• SIMD: Single Instruction Multiple Data
• Integrated into the processor
• Short and fast
• No startup overhead

SIMD

Scalar Hardware: big instruction decode logic with small ALU. They process one "word" per instruction.

Vector Hardware: multiple lanes, each lane has its own ALU, one instruction controls all lanes. All vector lanes operate in lockstep, meaning they all execute the same instruction at the same time.

for AVX2:

• 256 bit registers
• FP32: 8 floats per instructions
• FP64: 4 doubles per instructions

Notes about SIMD:

• SIMD operate in elementwise fashion (so ith element of one vector register only takes part in operations with ith element of another vector register)
• all lane perform the same operation at the same time
• vector memory operands might need to be aligned to the vector size (address is multiple of vector size)
• SIMD expanded to support cross-lane operations, such as permuting the vector, scatter, or gather operations.
  • permuting the vector: permute the elements of the vector according to a mask
  • scatter: scatter the elements of the vector to different memory locations
  • gather: gather the elements of the vector from different memory locations

Vector Register Alias:

Floating Point

Floating point operations are not associative. Vector operations do not add the values in the same order as a scalar loop.

Multi-Media Instructions

Note that: Single-precision (32-bit) vs double-precision (64-bit).

• Arithmetic Logic: add, sub, mul, div, and, or, andnot, xor
• Compare: "normal" comparisons (sets lanes to ones if true), AVX-512 comparisons sets mask registers.
• Load/Store: aligned (vmovaps), unaligned (vmovups), streaming (vmovntps)
• Shuffle: _mm_blendv_ps (two sources), _mm_shuffle_epi8 (within a source), unpackhi, unpacklo
• Non-SIMD: dot product instructions (_mm_maddubs_epi16), addsub (dependent on index of 64-bit element)

Types of Vectorization

Loop Vectorization: vectorize a loop by processing multiple iterations at once. Requires no cross-iteration dependencise, and parallelizable loop body.

SLP (Superword Level Parallelism): unrolls the loop, group individual scalar ops, packs them into vectors

Vectorization vary heavily between compilers: VeGen does the best here.

Why Compilers Fail to Vectorize

1. Unknown Trip Count: dynamic bounds makes cost modeling harder. Third function is best vectorized.
   
2. Cannot Prove Independence.
   

   Solution is restrict keyword.

3. Loop-Carried Dependencies: A[i] += A[i-1]. Prefix sums requires special treatment.
4. Reductions: sum += A[i]. A scalar accumulator, so compiler must create vector accumulator and reduce horizontally
   
   

   We must shuffle here because vectorization must be done in the same lane as before.

5. Control Flow: branches inside loops. Vectorization requires masked operations.
6. Non-Contiguous Data: gather instructions is much slower than contiguous load.
7. Cost Model Failures: compiler might know how to vectorize but doesn't since its not profitable.
   

   Clang v13 doesn't whereas Clang v14 does, making it $30\%$ slower.

8. Vectorization of Function Calls: only some built-in functions are vectorized.
9. Different Hardware Version: different Intel chips have different vectorization capabilities.

Vectorizing Dot Product

_mm512_dpbusd_epi32 essentially is a specialized intrinsic for dot-product of unsigned bits with signed bits into 32-bit integers.

AMX

Note AMX (Advanced Matrix Extensions): Intel's vectorized matrix operations. Use TMM registers to scale from vectors to matrices.

2/20/26: Recitation 3

Vector Register Sizes: xmm: 128 bits, ymm: 256 bits, zmm: 512 bits.

To vectorize codes that eal with two arrays, we need to know they don't overlap This can be done by marking them with restrict keyword.

What can a compiler auto-vectorize?

• "Pure" loop iterations
• Reductions (sum or product of contiguous memory)
• Inductions (A[i] = i)
• If statements
• Stride
• When restrict isn't known

Floating point additions are not associative. Vector operations do not add the values in the same order as a scalar loop.

Useful Intrinsics:

• __builtin_assume_aligned(const void *arg, size_t align): returns first argument and allows compiler to assume that the returned pointer is at least align bytes aligned
• __pext_64(uint64_t s1, uint64_t mask): transfer either contiguous or non-contiguous bits in the first source operand to contiguous low order bit positions in the destination according to the mask values

2/24/26: Multicore Programming

Historical Software Scaling:

Why Multicore?

Transistor counts kept rising, but clock speed flattened, so single-thread performance stopped scaling.

Hardware progress moved to multiple cores on one chip, and for more speed, parallelism in software is needed. Unfortunately, this is not so easy.

Shared-memory Multicore Architecture + Cache Coherence

Baseline: several processors/cores with private caches connected through an on-chip “network” to memory/I/O.

This motivates cache coherence, because if multiple caches can hold copies of the sample memory location, a store on one core can make other cores' copies stale.

Examples of cocurrency platforms:

• Pthreads (and WinAPI threads)
• Threading Building Blocks
• OpenMP
• Cilk

MSI Protocol:

• M: cache block has been modified. No other caches contain this block in M or S states.
• S: other caches may be sharing this block, matches memory.
• I: cache block is invalid.

Concurrency Platforms

Programming directly on cores is painful and error-prone.

A concurrency platform abstracts processor cores, handles synchronization and communication protocols, and performs load balancing.

A key example is Fibonacci, as fib(n-1) and fib(n-2) are independent and can be executed simultaneously without mutual interference.

Pthreads

Standard API for threading specified by ANSI C. Known as a "do-it-yourself" concurrency platform, with library functions full of special non-C semantics.

• Each thread implements an abstraction of a processor, which are multiplexed onto machine resources.
• Threads communicate though shared memory.
• Library functions mask the protocols involved in inter-thread coordination.

Key Pthread Functions:

pthread_create creates a new thread. Provide the function pointer and a argument and returns a thread handle to refer to later.

pthread_join waits for a thread to finish, and lets you collect its return value.

Fibonacci Example:

• struct for thread arguments
• thread_func: function called whent thread is created.
• (n<30) to avoid creating threads when there isn't enough work to do.
• args.input as Marshal input argument to thread
• pthread_create: create a new thread.
• Main program executes fib(n-2) in parallel.
• pthread_join: wait for the thread to finish and collect the return value. We block until the thread finishes.

Issues of Pthreads:

• Overhead: thread creation cost.
• Scalability: this fib gets only  1.5× on 2 cores; needs rewrite for more cores.
• Modularity: fib logic no longer encapsulated cleanly.
• Simplicity: manual argument marshaling + error-prone load balancing.

Threading Building Blocks

C++ library on top of native threads, where you specify tasks not threads. Runtime does work-stealing load balancing (inspired by Cilk research at MIT).

• Work-stealing is where each worker thread keeps its own deque of tasks. A worker normally pops tasks from its own deque; if it runs out of work, it becomes a “thief” and steals a task from another worker’s deque

• FibTask is computation organized as explicit tasks.
• FibTask has input n and output parameter sum.
• execute() performs computation when task is started and uses allocate_child() to recursively create child tasks.
• set_ref_count sets the number of tasks to wait for
• spawn(b) starts task b.
• spawn_and_wait_for_all(a) starts task a and waits for all tasks to finish.
• task::spawn_root_and_wait(a) creates the root task.

This generally gives better scaling than manual thread mgmt.

OpenMP

OpenMP is a industry consortium spec, compiler pragmas for C/C++/Fortran, and supports loop/task/pipeline parallelism. Provides a higher level of abstraction than Pthreads.

• Loop (omp parallel for): divide loop iterations across threads.
• Task (omp task): create independent work units dynamically; runtime schedules them.
• Pipeline: split into ordered stages; different items run in different stages at the same time.

• #pragma omp parallel is a compiler directive to parallelize the following code.
• task is a statement to create an independent task.
• sharing of memory is managed explicitly.
• taskwait waits for the two tasks to complete before continuing

Use parallel for for loop parallelism and reduction for data aggregation. OpenMP also supports synchronization constructs, like barriers, atomic updates, and mutex locks.

Cilk

Cilk is introduced as an MIT-developed multithreading language with:

• small extensions for fork-join parallelism (computation forks into parallel subcomputations and joins them later)
• provably efficient work-stealing scheduler
• reducers linguistic interface for parallizing code
• ecosystem: race detector (to find race conditions) + scalability analyzer (to analyze scalability)

Cilk keywords cilk_spawn and cilk_sync grant permission to run code in parallel. They don't command parallel execution.

Serial Semantics: replace Cilk keywords with plain serial constructs and you get a legal interpretation of the program.

To run serial projection:

#define cilk_for for
#define cilk_spawn
#define cilk_scope

Hence Cilk concurrency allows programmer to express logical parallelism in an application.

Reducers (Cilk Hyperobjects)

• Core idea: avoid races by giving each strand a private reducer view.
• During parallel execution, multiple views may exist simultaneously.
• After cilk_sync (or end of a cilk_scope), runtime merges all views into one.
• Reducers preserve serial semantics: result matches a legal serial execution order.

Algebraic model (monoid).

• Value domain $T$, associative merge operator $\oplus$, identity element $e$.
• Associativity lets runtime regroup merges without changing final answer.

If serial updates are $x_1,\dots,x_7$ on initial value $x_0$, one serial form is:

A parallel execution can use multiple views, e.g.:

and still produce the same final value.

• Reducers also work for noncommutative operations (e.g., matrix multiply), because Cilk preserves left/right merge order.
• Practical upside: no locks for this pattern, deterministic result (given correct reducer definition), and low synchronization overhead.

2/26/26: C to Assembly

It's not clear how the compiler translates C to Assembly. To understand this mapping, we need to see how the Clang/LLVM compiler reasons about the code.

Organization of LLVM IR

Example of LLVM IR:

LLVM is similar to assembly

• Instruction format: [destination operand] = [opcode] [source operands]
• Control flow is implemented using conditional and unconditional branches.

However, it is simpler with

• C-like functions
• smaller instruction set
• Infinite LLVM IR registers
• No implicit FLAGS register or condition codes
• No stack or frame pointer

Note that code containing no conditionals or loops becomes a sequence of LLVM IR instructions. Here, intermediate results are stored in registers

LLVM IR maintains static single assignment (SSA) form, where a register is defined by at most one instruction in a function. This makes it easier for the compiler to reason about the program’s behavior.

The body of a function definition is partitioned into basic blocks. A straight-line sequence of instructions with one entry point and one exit point.

LLVM splits the C fib into basic blocks with explicit branches, and the phi in the merge block picks the return value based on which predecessor block control came from (base case returns $\%0$/n, recursive case returns $\%8$).

Control-Flow Graph (CFG): graph formed from basic blocks and their control-flow edges.

Conditionals in LLVM IR

A conditional in C is translated to conditional branch instruction, br, in LLVM IR.

• The comparison is done with an icmp instruction

Predicate determines which branch to take, first branch is taken if true, else second branch is taken.

If br just has one operand, it is an unconditional branch to the operand block. So it will jump to the block specified by the operand.

These C conditions create a diamond control flow in the LLVM IR.

Static Single Assignment Form

How does LLVM represent a variable whose value depends on control flow?

phi instruction specifies the value of a register depending on control flow. It specifies, for each predecessor P of a basic block B, the value of the destination register if control enters B via P.

LLVM IR to Assembly

LLVM IR is structurally similar to assembly. The compiler must perform three main tasks to translate LLVM IR into assembly.

• Select assembly instructions to implement LLVM IR instructions.
• Allocate assembly registers to hold values in LLVM IR registers.
• Coordinate function calls.

LINUX X86-64 Calling Convention

Program executes, virtual memory is organized into segments.

• A process gets a virtual address space split into regions: text (code, read/execute), data (initialized globals/statics), bss (uninitialized globals/statics, zeroed), heap (malloc/new, grows upward), and stack (call frames/locals, grows downward). The OS maps these virtual regions to physical memory pages and enforces permissions; the gap between heap and stack lets them grow without immediately colliding.

The stack is used to manage function calls, which stores return addresses of function calls, register state, so different functions can use the same registers, and function arguments and local variables that don't fit in registers.

How do functions in different object files coordinate their use of the stack and of the registers?

Functions abide by a calling convention.

Linux x86-64 organizes the stack into frames, where each function instantiation gets its own frame.

• The base pointer (or frame pointer), $\%$rbp, points to the top of the current stack frame.
• The stack pointer, $\%$rsp, points to the bottom of the current stack frame.

The stack segment grows down, towards lower virtual memory addresses.

The call and ret instructions manage return addresses using the stack and the instruction pointer, $\%$rip.

• A call instruction pushes $\%$rip onto the stack and jumps to the specified function.
• A ret instruction pops the return address from the stack and jumps to it.

Who’s responsible for preserving the register state across a function call and return? Both don't want to waste work saving register state that the other won't use.

For x86-64,

• Callee-saved registers: $\%$rbx, $\%$rbp, $\%$r12-$\%$r15. So if the callee uses these registers, it must save and restore them.
• All other registers are caller-saved.

$\%$xmm0-$\%$xmm7 registers are used for floating point arguments

Linux C Subroutine Linkage

Function B was called from function A and is about to call function C.

• The linkage block contains nonregister arguments from A for B. These are positive offsets from $\%$rbp (above the frame pointer)
• Function B accesses local variables with negative offsets from $\%$rbp (below the frame pointer)
• Before function B calls C, B places the nonregister arguments for Cinto the reserved linkage block
• Function B executes call instruction to push the return address onto the stack and give control to C.
  
• When function C begins, it executes a function prologue to set up stack frame.
  • $\texttt{push \%rbp}$: Push $\%$rbp, B’s base pointer, onto the stack, so that B can restore its frame pointer when it returns. B's base pointer is right before its local variables.
  • $\texttt{mov \%rsp, \%rbp}$: Set $\%$rbp = $\%$rsp, so the base pointer points to the top of the stack frame. This makes a stable anchor for this function’s frame
  • Advance $\%$rsp to allocate space for C’s local variables and linkage block. This reserves stack space for C’s locals and linkage block.
  
  NOTE Optimization: if the compiler can guarantee the stack pointer stays a fixed offset from the frame base for the whole function, then you don’t need a dedicated frame pointer.

  • indexing can be done off $\%$rsp, and $\%$rbp can be used as an ordinary callee-saved register

Compiling LLVM IR To Assembly

    .globl  _fib
    .p2align 4, 0x90
_fib:                          ## @fib
    pushq   %rbp
    movq    %rsp, %rbp
    pushq   %r14
    pushq   %rbx
    movq    %rdi, %rbx
    cmpq    $2, %rdi
    jl      LBB0_2
    leaq    -1(%rbx), %rdi
    callq   _fib
    movq    %rax, %r14
    addq    $-2, %rbx
    movq    %rbx, %rdi
    callq   _fib
    movq    %rax, %rbx
    addq    %r14, %rbx
LBB0_2:
    movq    %rbx, %rax
    popq    %rbx
    popq    %r14
    popq    %rbp
    retq

Overview

Reason through the mapping from C code to assembly in two steps: C to LLVM IR and then LLVM IR to assembly.

• LLVM IR organizes a C function into a control-flow graph.
• Assembly implements the LLVM IR code using ISA registers and the stack, according to a calling convention.

Handing LLVM IR Manually

Use clang *.ll -S to compile the LLVM IR to assembly.

2/27/26: Recitation 4

LLVM IR Overview

LLVM IR stores values in registers.

• Syntax: $\%[\text{name}]$
• LLVM supports an infinite number of registers, each distinguished by name.
• Register names are local to each LLVM IR function

LLVM-IR code is organized into instructions.

• Syntax for instructions that produce a value: $[\text{name}] = [\text{opcode}] [\text{flags}] [\text{operands}]$
• Syntax for other instructions: $[\text{opcode}] [\text{operands}]$

LLVM IR Data Types

• Integers: i<number>
  • Example: A 64-bit integer: i64
  • Example: A 1-bit integer: i1
• Floating-point values: double, float
• Arrays: [<number> x <type>]
  • Example: An array of 5 int’s: [5 x i32]
• Structs: { <type>, $\dots$ }
• Vectors: $<<$number$>$ x $<$type$>>$
• Pointers: $<$type$>*$
• Example: A pointer to an 8-bit integer: $<$i8$*>$
• Labels (i.e., basic blocks): label

LLVM IR Loops

The loop control for a C loop consists of a loop induction variable, an initialization, a condition, and an increment.

LLVM IR Memory

A memory access in LLVM IR typically involves computing an address followed by reading or writing memory.

• getelementptr instruction computes a memory address from a pointer and a list of indices. Computes i32* $\%0 + \%1$

LLVM IR Attributes

Attribute describing the alignment of the read from memory.

• Some attributes are derived from the source code
• Other attributes are determined by compiler analysis.

Section directives refer to and operate on sections of assembly.

3/3/26: Races and Parallelism

Cactus Stack: supports multiple views

Determinacy Races

Determinacy race occurs when two logically parallel instructions access the same memory location and at least one of the instructions performs a write.

We denote two sections of code to be independent if they have no determinacy races between them.

Avoid races by:

• Iteration of cilk_for should be inependent
• after cilk_sync, code executed by spawned task should be independent of subsequent code executed by parents
• Races in packed data structures:
  

Cilksan Tool

Cilksan Tool: –fsanitize=cilk. Will guarantees to report and localize the offending race. It is used via regression-test methodology (programmer provides input) and it will check for races across all files.

• The runtime overhead isnearly constant compared with a serial execution.
• ASCII art:
  • * = racing instructions
  • + = stack frames (call/spawn)
  • |/ = common calling context
  • ⎵ = allocation context

Parallelism

Trace:

• Trace is a DAG $G = (V, E)$
• Each vertex $v \in V$ is a strand, or a sequence of instructions that isn't a spawn, sync, or return from spawn
• An edge $e \in E$ is a spawn, call, return, continue edge

$T_P$ is exeution time on $P$ processors. Then $T_\infty$ will be our span or critical-path length.

• Work Law: $T_P \ge T_1/P$
• Span Law: $T_P \ge T_\infty$

Composition:

• $T_P$, both $T_P$ and $T_\infty$, are additive when in series.
• In parallel, $T_1$ is the sum whereas $T_\infty$ is the maximum.

Speedup: $S_P = T_1/T_P$

• $T_1 = 17$
• $T_\infty = 8$
• $S_P = 2.125$ or more than $2$ processors yield only marginal gains.

Cilkscale Scalability Analyzer

Visualizer:

It plots burdened parallelism, which indicates whether the program might incur scheduling overhead.

3/5/26: Scheduling Theory and Parallel Loops

Recall maximum possible speedup via Span Law is $ T_1/T_\infty$.

• Work Law: $T_P \ge T_1/P$
• Span Law: $T_P \ge T_\infty$

Scheduling Theory

Cilk allows programmers to express potential parallelism in an application by mapping strands onto processors dynamically at runtime.

Greedy Scheduling

Suppose we are working with $P$ processors. A strand is ready if all its predecessors have executed.

Complete step: when $\ge P$ strands are ready. Run any $P$.

Incomplete Step: when less than $P$ strands are ready. Run all of them.

We define parallel slackness as $(T_1/T_\infty)/P$. It is the ratio of available parallelism in an application to the number of processors.

Cilk's Work-Stealing Scheduler

Cilk's work-stealing scheduler achieves:

• $T_P = T_1/P + O(T_\infty)$ expected time (provably)
• $T_P \approx T_1/P + T_\infty$ time (empirically)

Near perfect linear speedup whenever $T_1/T_\infty \gg P$. Instrumentation in Cilkscale allows you to measure $T_1$ and $T_\infty$.

Parallel Loops

Implementation of parallel loops for transposing a matrix:

• cilk_for loop control implemented in if statement. It is the internal nodes of the trace DAG.
• bottom for loop is the lifted loop body. It is the leafs of the trace DAG.

• The total work $T_1(n) = \Theta(n^2)$.
• The total span $T_\infty(n) = \Theta(n+\log n) = \Theta(n)$.
• Parallelism $T_1(n)/T_\infty(n) = \Theta(n^2/n) = \Theta(n)$.

Analysis of Nested Parallel Loops

• Span of outer loop control is $\Theta(\log n)$.
• Span of inner loop control is $\Theta(\log n)$.
• Span of body is $\Theta(1)$.

So,

• The total work $T_1(n) = \Theta(n^2)$.
• The total span $T_\infty(n) = \Theta(\log n + \log n + 1) = \Theta(\log n)$.
• Parallelism $T_1(n)/T_\infty(n) = \Theta(n^2/\log n) = \Theta(n^2/\log n)$.

Overhead of Parallel Loops

Coarsening parallel loops:

#pragma cilk grainsize G
cilk_ for (int i=0; i‹n; ++i)
{
    A[i] += B[i];
}

• Let I be the time for one iteration of the loop body.
• Let S be the time to perform a level of the recursion.

Then,

• The total work $T_1(n) = n \cdot I + (n/G -1) \cdot S$
• The total span $T_{\infty}(n) = G \cdot I + \log(n/G) \cdot S$

We want $G \gg S/I$ but $G$ small to maximize parallelism.

We define parallelism here $T_1(n)/T_\infty(n) \approx \Theta(n/\log(n))/(S/I)$.

Another implementation:

Assuming $G$ coarse-grained, we get:

• The total work $T_1(n) = \Theta(n)$.
• The total span $T_\infty(n) = \Theta(G + n/G)$

We maximize parallelism by setting $G = \sqrt{n}$.

3/10/26: Task Parallel Algorithms II

Divide and Conquer for Matrix Multiplication

• Work: $O(n^3)$
• Span: $O(n)$
• Parallelism: $O(n^2)$

This has 8 multiplications and 1 addition.image.png

Divide and conquer uses cache more efficiently.

Representation of submatrices:

• Row Major: (i,j) of $A$ is $A[i*n+j]$

Divide and Conquer Matrices:

Code

• Assume input matrices are not aliased. Row sizes of the underlying matrices.
• Assert $n$ is a power of 2
• Coarsen leaves of recursion to lower overhead
• Allocate a temporary nxn array D, assert it is not null
• token-pasting operator macro to compute indices of submatrices
• Perform 8 multiplications of (n/2)x(n/2) matrices. First 4 are stored to $C$, last 4 are stored to temporary $D$
• Add temporary matrix $D$ to $C$ and free $D$

Analysis of Divide and Conquer Matrix Multiplication

Master Method:

Check http://tinyurl.com/mm-cheat for cheatsheet.

Analysis of Matrix Addition

• Work: $O(n^2)$
• Span: $O(\log n)$
• Parallelism: $O(n^2/\log n)$

Work of Matrix Multiplication:

By Master Method, $M_1(n) = O(n^3)$.

Span of Matrix Multiplication:

By Master Method, $M_\infty(n) = O(\log^2 n)$.

Parallelism:

Temporaries

This is expensive:

Since minimizing storage tends to yield higher performance, trade off some of the ample parallelism for less storage.

No-Temp Matrix Multiplication

We avoid races as writing to same sections of $C$ are not done at the same time.

Work:

By Master Method, $M_1(n) = O(n^3)$.

Span:

By Master Method, $M_\infty(n) = O(n)$.

Parallelism:

Parallel Merge Sort

Asymptotically optimal running time for a comparison sort: $\Theta(n \log n)$

Merge Two Sorted Arrays:

Time to execute is $\Theta(n)$.

Parallel Merge Sort Code

Work:

By Master Method, $T_1(n) = O(n \log n)$.

Span:

By Master Method, $T_\infty(n) = O(n)$.

Parallelism:

Parallel Merge

We assume $A$ has more elements than $B$. Find median of $A$ and binary search for it in $B$. If the total amount to merge in the two arrays is $n$, then the total number of elements in the larger of the two recursive merges is at most $3n/4$.

Work Efficiency:

• $T_S(n)$ is the running time of best serial algorithm.
• $T_1(n)$ is work of a parallel program on same input (using 1 processor).
• Work overhead $\lambda(n) = T_1(n)/T_S(n)$. We say it is work efficient if $\lambda(n) \sim 1$.
• We say it is asymptotically work efficient if $\lambda(n)=\Theta(1)$.

Hence Work Law says that $T_P \ge \lambda \cdot T_S/P$.

So if $\lambda$ is large, we cannot get near-perfect linear speedup over good serial code no matter how many processors we run on.

We must minimize work first, ahead of maximizing parallelism, if we want efficiency.

3/12/26: Measurement and Timing

If you can't mesaure performance reliably, it is hard to make many small changes that add up.

Measuring using time.h:

However, we get:

Potentially causes:

• Cache hierarchy, where working set crosses a cache boundary causing runtime to jump
• even if algorithm and memory behavior is fixed, the CPU itself may change its clock speed and voltage while you are measuring
  • This technique is known as DVFS (Dynamic Voltage and Frequency Scaling), where it dynamically trade power for performance by adjusting clock frequency and supply voltage to transistors.
  • Turbo Boost increases frequency if the chip is cool.

What Statistics and Metrics to Measure?

We evaluate two programs, A and A' statistically. Consider null hypothesis that A beats A', and calculate the P-value. If the P-value is low, we can reject that A beats A'.

Best statistic to represent raw performance of the software is the minimum, as it does best at noise rejection.

• When comparing two programs across multiple benchmarks, ratios such as $\frac{A}{A'}$ are multiplicative quantities, so they should not be summarized with the arithmetic mean.
• Example: if the ratios $\frac{A}{A'}$ are \[ 8,\;4,\;1,\;5, \]

  then the arithmetic mean is

  \[ \frac{8+4+1+5}{4}=4.5. \]

  It is tempting to conclude that $A'$ is $4.5\times$ better than $A$, but this is misleading.

• If we flip the comparison, the ratios become
  \[ \frac{A'}{A}=\frac18,\;\frac14,\;1,\;\frac15, \]

  whose arithmetic mean is

  \[ \frac{\frac18+\frac14+1+\frac15}{4}\approx 0.39. \]

  But

  \[ \frac{1}{4.5}\approx 0.22 \neq 0.39. \]

• Therefore,
  \[ \text{mean}\!\left(\frac{A'}{A}\right) \neq \frac{1}{\text{mean}\!\left(\frac{A}{A'}\right)}. \]

  The arithmetic mean does not preserve inversion, so it is the wrong summary for normalized performance ratios.

• The right summary statistic is the geometric mean:

  \[ \left(\prod_{i=1}^{n} a_i\right)^{1/n}. \]

• For the ratios $8,4,1,5$, the geometric mean is

  \[ (8\cdot 4\cdot 1\cdot 5)^{1/4}=160^{1/4}\approx 3.56. \]

• If all ratios are inverted, the geometric mean also inverts:

  \[ \text{GM}\!\left(\frac{A'}{A}\right)=\frac{1}{\text{GM}\!\left(\frac{A}{A'}\right)}. \]

• More broadly, the choice of summary statistic depends on the actual system goal:
  • for servers, throughput, cost per request, and tail latency may matter
  • for mobile devices, energy, battery life, and thermals may matter
  • for SLA-driven systems, multiple metrics such as average latency, p99 latency, and error rate may all be needed
  • for memory-constrained systems, maximum memory usage may matter as much as runtime

Tools to Measure Software Performance

Measure the whole program:

/usr/bin/time: time command can measure elapsed time, user time, and system time.

• real: wall-clock time
• user: amount of processor time spent in user-mode code
• sys: amount of processor time spent in the kernel within the process

Measure just part of theprogram:

clock_gettime(CLOCK_MONOTONIC): about two orders of magnitude faster than an ordinary system call.

rdtsc(): a time-stamp counter in hardware. Gives "clock cycles since boot":

Not all cycles take the same amount of time, so converting clock cycles to seconds can be tricky.

hardware counters: keep track of performance-related events, such as cache accesses and misses.

• libpfm4 virtualizes all hardware counters
• perf stat uses this library to measure all provided hardware event counters
• However, you cannot measure more than 4 to 5 counters at a time without paying penalty in performance/accuracy.

Create a profile of the program:

instrumenting the program: add code to the program to measure performance-related events.

However, the probe effect can occur where it alters the program's behavior unintendedly.

• pmprof, gprof, perf record, and gperftools are tools that provide profile information for all functions
• This approach isn't accurate if it doesn't obtain enough samples

Poor Man's Profiler: Use gdb and type control-C, but at random intervals.

What to measure as a surrogate for time?

• Work: use hardware counters or program instrumentation
• Processor cycles: use rdtsc()
• Memory accesses: hardware counters or /texttt{cachegrind}
• Span: use Cilkscale.

Simulations like cachegrind can deliver accurate and repeatable performance numbers. For deterministic programs, you only need to run simulator once. However, they run much slower than real time.

Quiescing Systems

Sources of variability:

Hyperthreading: enables a single physical CPU core act as two logical virtual cores

Use /proc/cpuinfo for information about a system's CPU. It tells you the "hardware thread" (like hyperthread), socket (physical chip), which core on the chip.

Quiescing lets the system become quiet and stable before measurements so leftover activity doesn't contaminate the timing. Performance tends to have less variance.

It does this by shuting down daemons and cron jobs, and minimizing the number of other jobs running.

• For serial jobs, don't run on core 0, as many interrupt handlers are usually run there.
• Use Linux CPU frequency governor to control DVFS and TurboBoost
• Use taskset to pin Cilk workers to cores and avoid hyperthreading.

Performance can also vary due to changes in cache alignment and page alignment. LLVM tends to cache-align functions, but we can asso control allignment:

Tips

If the function runs too fast, measure via a for loop.

First time called, the data may not be in the cache (warm cache vs cold cache).

Threads can go to sleep and get rescheduled (and change cores). This affects performance as data will be in caches of the old core. Use taskset to limit the cores a thread can be in.

Your thread may be running on one CPU socket, while the memory pages it uses live on another socket’s DRAM. Then every load becomes a remote memory access, which is slower. taskset is not enough as it only controls where the thread runs, not where the memory pages were allcoated.

• First-touch policy: the first thread to access a page allocates it on its socket's DRAM. This is so that the first thread to access a page will have it in its cache.

3/17/26: Storage Allocation

Memory-Allocation Primitives

Machine has physical memory and a physical disk, it must be shared across multiple processes. Each process would like to oblivious to one another.

Each virtual page (blocks per process)can be backed by either RAM (physical memory) or disk. mmap() gives a virtual address range to map a file to.

mmap() system call is used to allocate virtual memory by memory mapping:

The Linux kernel finds a contiguous, unused region in the address space of the application large enough to hold size bytes, modifies page table, and creates necessary virtual-memory management within OS to make user's access to this area legal to prevent segfaults.

mmap() can also map the contents of a file into physical memory, but different processes can't share memory. However, they can access the same files.

• You can "overlay" a circular queue on the file and use it as a shared-memory queue/buffer.
  

page fault occurs when virtual-memory access cannot be satisfied immediately from current mapping so OS must intervene. OS will map the offending page to physical memory (taking around 1 million cycles).

When the OS needs to reclaim a page, it will write the contents to disk and unmaps the page.

If virtual page doesn't reside in physical memory, this rseults in a page fault.

Page Table Structure ($2^9$-ary tree):

Since page-table lookups are costly, hardware contains a translation lookaside buffer (TLB) to cache recent page-table lookups.

L1 Cache

We use caches to speed up memory accesses, or reduce average cost to access data from main memory.

Set-associative cache where the cache is divided into sets, where each set contains several ways.

Page offset is 12 bits -> page size is 4 KiB. L1 caches usually have 64 sets or 6 bits for finding idx in cache set. Cache line is 64B or 6 bits for choosing addr in cache line.

So to make lookup for L1 cache,

• use virtual page-offset bits immediate to choose L1 set
• in parallel, use virtual page number in TLB to get physical frame number
• Combine physical frame number and offset to form physical address.
• Compare the physical tag against the tags of the lines in that set.

TLB Access: every memory access translates the virtual address through a prefix of this structure.

Storage Allocation

Two kinds of storage management: stack and heap.

Stacks

LIFO (Last In First Out): last item pushed is the first item popped.

Allocate x bytes:

    sp +=x;
    return sp-x;

Free x bytes:

    sp -= x;

Limited applicability, as it cannot handle freeing in arbitrary order.

Process's virtual address space:

So stack grows downward, mainly used for local variables and function calls.

Heaps

Allocation:

void* malloc(size_t size);

Free: p is a pointer to block of memory returned by malloc() or memalign().

free(void *p);

Aligned allocation: allocate and return a pointer to a block of memory containing at least s bytes, aligned to a multiple of a (a power of 2).

void* memalign(size_t a, size_t s);

Difference between malloc() and mmap():

• malloc()/free() are the user-level heap allocation interface, while mmap() is a lower-level kernel mechanism for obtaining virtual memory
• malloc() manages and reuses heap space internally, and only calls mmap() or related syscalls when it needs more memory from the OS

Garbage Collection:

• this storage does not need to be freed explicitly
• available in many high-level languages (python, java, julia)
• it looks for storage that the program no longer access and reclaims it
• garbage collector pause the executing program, run in real time, or operate concurrently
• usually slower than malloc() and free()

Properties of Storage Allocators

Allocator Speed: number of allocations and deallocations per second that the allocator can sustain.

Fragmentation

• user footprint: maximum over time of the number of bytes, $M$, in use by the user program
• allocator footprint: maximum over time of the number of bytes, $H$, provided to the allocator by the OS

Fragmentation: $F = H/M$. Space utilization: $U = M/H$.

Space overhead: space used by allocator for bookkeeping

Internal fragmentation: waste due to allocating larger blocks than the user requests

External fragmentation: waste due to inability to use storage because it is not contiguous

Blowup: additional spacae beyond what a serial allocator would require for a parallel allocator.

Cache locality: program accesses relatively small portion of address space often (temporal and spatial locality).

Fixed-size Heap Allocation

Use a bitmap to keep track of which blocks are free and used. We can choose lowest set bit on allocation (bitmap & (-bitmap)).

Free list: keep track of free blocks using a linked list, with a pointer to the next unused block.

• Allocate:

  
  x = free;
  free = free->next;
  return x;
  

• Free object x:

  
      x->next = free;
      free = x;
  

Allocating and freeing take $\Theta(1)$ time. Poor spatial locality due to external fragmentation, which can increase the size of the page table and cause disk thrashing. TLB can also become a problem.

Arranging heap allocation:

Probaility that $2$ random accesses hit the same page is $0.82$ vs $0.5$. This is better locality, and fewer distinct pages needs to be resident.

Variable-size Heap Allocation

Binned Free Lists leverage the efficiency of free lists. Accept a bounded amount of internal fragmentation.

bin $i$ has blocks of size $2^i$. We denote bin as a list of available blocks, being empty if no free blocks.

Allocating: if bin $k = \lceil \log_2(x) \rceil$ is nonempty, return a block. Otherwise find block in the next larger nonempty bin $k' > k$, split it up into blocks of sizes $2^{k'-1}$, $2^{k'-2}$, ..., $2^k$, $2^k$, and distribute the pieces.

How Virtual is Virtual Memory?

Storage Allocators is to use as little virtual memory as possible and keep used portions relatively compact.

Coalescing: binned free lists can sometimes be heuristically improved by splicing together adjacent small blocks into a larger block. Buddy system is a more sophisticated approach. Seems to reduce fragmentation in practice, because heap storage often obeys a stack discipline.

Parallel Heap Allocation Strategies

Global Heap: all threads share a singple heap. Prevents blowup but is really slow (essentially a L3-cache access).

Ideally as number of threads (processors) increase, the time to perform an allocation or deallocation should not increase. Most common reason for loss of scalability is lock contention.

Local Heap: each thread allocates its own heap. Faster than global heap, but suffers from memory drift: where blocks allocated by one thread are freed on another. This leads to unbounded blowup.

• Blowup $\le P$, the number of processors.

Resilience to false sharing, where threads access different variables but they happen to sit on the same cache line.

• Program can induce false sharing by having different threads process nearby objects.
  NOTE Can mitigate this problem by aligning the object on a cache-line boundary and padding out the object to thet size of a cache.
• Allocator can induce false sharing in two ways:
  • Actively, when allocator satisfies memory requests from different threads using same cache block
  • Passively, when program passes objects lying on the same cache line to different threads, and allocator reuses the objects' storage after the objects are freed to satisfy requests from those threads

Hoard Allocator: $P$ local heaps, $1$ global heap. Memory is organized into large superblocks of size $S$. Only superblocks are moved between local heaps and global heap.

Hoard allocation:

We take fullest nonfull superblock in heap so we prevent fragmentation.

Hoard deallocation: Let $m_i$ be the in-use storage in heap $i$, and let $h_i$ be the storage owned by heap $i$. Hoard maintains the following invariant for all heaps $i$:

where $S$ is the superblock size.

free(x) where $x$ is owned by thread $i$:

jemalloc is a popular choice for parallel systems due to performance and robustness.

Garbage Collection by Reference Counting

Free the programmer from freeing objects, where garbage collector identifies and recycles objects programs don't access.

• Roots are objects directly accessible by the program (globals, stack, etc)
• Live objects are reachable from the roots by following pointers
• Dead objects are inaccessible and can be recyled

Reference counting is when you keep a count of number of pointers referencing each object. If count drops to $0$, free the dead object.

Mark-and-Sweep Garbage Collection

Graph Abstraction using $G=(V,E)$. Use breadth-first search to find the live objects. Live objects are reachable from the roots. Use BFS to find the live objects.

Using BFS, we can find and extract all garbage objects.

Mark-and-Sweep occurs where mark stage BFS all live objects, and sweep stage free unmarked objects.

Stop-And-Copy Garbage Collection

All live vertices are placed in contiguous storage in the BFS order.

Pauses the program, copies all live objects from one memory region to another, and resumes with copied region as new active heap.

Treat FROM-space as “full” after the program has allocated an additional amount of heap equal to the currently used live data; then a copying GC costs work proportional to that new allocation, giving amortized $O(1)$ overhead per allocation.

Overview

Generational Garbage Collection

Most objects die young, so strategy is collect nursery often and collect old generation rarely.

Run stop-and-copy on nursery only, so cost is proportional to nursery size not total heap size.

Old-to-young pointers are pointers from old generation to nursery. They are updated when objects are copied to nursery.

Promoting surviving objects to old generation:

Other Dynamic Storage Allocation Strategies

[TODO: look through them]

• buddy system
• variants of mark-and-sweep,
• real-time garbage collection,
• multithreaded storage allocation,
• parallel garbage collection

3/19/26: Memory Level Parallelism

Cache Architecture

Intel's Cascade Lake is the test system for MicroBenchmarks.

Temporal Locality: if an item is referenced, it will tend to be referenced again Spatial Locality: if an item is referenced, items whose addresses are close tend to be referenced soon

Cache Misses: when a requested item is not in cache.

• Cold Miss: the first time the data is accessed
• Capacity Miss: previous access has been evicted, "working set" too large
• Conflict Miss: multiple items mapped to the same location, evicted even before cache is full

MSI/MESI Misses:

• True Sharing Miss: thread in another processor wanted data, it got moved to the other cache
• False Sharing Miss: other processor used different data in same cache line, so line got moved

MicroBenchmark

Cycle Microbenchmark: initialize an array $A$ with cycle: $A[n]=2n \mod p$, for all $n \in \{1, \dots, p-1\}$. $p$ is a prime such that $2$ is a primitive root of $GF(p)$.

ReadNext

uint64_t cycleWithReadNext(uint64_t *A, int p, int iterations) {
    uint64_t sum = 0;
    int n = 1;
    for (int i = 0; i < iterations; i++) {
        sum += A[n];
        n = A[n];
    }
    return sum;
}

Blowup in per access time as there is a loop-carried dependence that goes through memory (n = A[n]).

OoO (Out-of-Order) Execution utilizes cores to exploit ILP by executing independent instructions in the dynamically unfolding DAG of instructions.

So with larger array size, we must utilize slower cache lines to avoid conflict misses, causing slower performance.

Performance Counters

Examples include:

• Cycles
• Cycles spent stalled waiting for memory
• Cycles stalled waiting for instruction cache
• Number of loads outstanding
• Cache misses at each cache level
• TLB misses
• Branch mispredictions

These are helpful for interpretating performance:

CalculateNext

uint64_t cycleWithCalcNext(uint64_t *A, int p, int iterations) {
    uint64_t sum = 0;
    int n = 1;
    for (int i = 0; i < iterations; i++) {
        sum += A[n];
        n = 2 * n;
        n = n > p ? n - p : n;
    }
    return sum;
}

There still is a loop-carried dependence that goes through memory, but address calculation is independent of the contents of the array. Hence, indices for several iterations can be calculated in quick succession.

Memory-Level Parallelism

Rewriting, we get $\lambda^{-1} = \frac{W}{L}$, where $W$ is average latency (ns), $\lambda^{-1}$ is average throughput, and $L$ is Memory-Level Parallelism.

It still does real memory accesses in parallel, but we can exploit this to improve performance.

SequentialWithReadNext

uint64_t sequentialWithReadNext(uint64_t *A, int p, int iterations) {
    uint64_t sum = 0;
    int n = 1;
    for (int i = 0; i < iterations; i++) {
        sum += A[n];
        n = A[n];
    }
    return sum;
}

If we cheat with $A$ initialized to a sequential cycle, it can fully drop latency (as indices are calculated in advance).

L2 Stream Prefetcher

Stream Prefetcher finds L1 miss streams that are approximately sequential and prefetches ahead.

It is trying to prevent future demand loads from becoming expensive L1 misses by fetching the corresponding cache lines ahead of time from lower levels of the hierarchy.

• Using larger set of Line Fill Buffers at L2 level, the core's max MLP will increase

Loop Unrolling

Loop unrolling/blocking reduces control overhead, but if memory dependence still exist, it will not help. If we are issued a stream of known addresses, it helps keep the memory system busy and reduce latency.

uint64_t sequentialCalcBlocked(uint64_t *A, int p, int iterations) {
    uint64_t sum = 0;
    int n = 1;
    for (int i = 0; i < (iterations >> 4; i++)) {
        for (int j = 0; j < (1 << 4); j++) {
            sum += A[n];
            n = 2 * n;
            n = n > p ? n - p : n;
        }
    }
    return sum;
}

This helps as we only get 1 TLB miss every 4KB, or 512 accesses.

Sequential Strides

Testing different strides can isolate different bottlenecks.

• n = n+8: walk one cache line at a time
• n = n+512: walk one page at a time

Stride Prefetcher

Stide Prefetcher finds load instructions that load addresses at a constant stride and prefetches ahead in that stride. Lands in L1 and consume an L1 LFB.

Sweep Phase

Software Prefetch __builtint_prefetch(void *addr, int rw, int locality)

This allows us to hide some memory latency. We are allowed to do this as the sweep has enough forward structure to make future accesses predictable, but not regular enough for hardware streaming alone.

Mark Phase

When you enqueue a node, you can issue a prefetch for it as it will likely be processed soon in BFS order.

Bulk Prefetch

Pointer-chasing leads to MLP=1, which is bad.

Segmented Allcoation where we can group related allocations into contiguous tagged regions so runtime can prefetch and make irregular accesses behave more like a cache-friendly stream.

Now when we perform work on segment 2 for example, we can prefetch the entire allocated range. This makes us less sensitive to pointer chasing as we are jumping to a place that is probably within a small nearby prefetched region.

4/2/26: Cache-Efficient Algorithms

Cache Hardware

Multicore Cache Hierarchy, where each level of cache is larger and cheaper per bit than the previous level, but also slower.

Intel Xeon Platinum 8280L (Cascade Lake)

• April 2019 release for 17906, now 13k
• 2.7GHz clock, Turbo Boost up to 4 GHz
• 28 cores/chip + 2-way hyperthreading
• 2190 GFLOPS
• 64B cache lines/blocks
• 8-way multiprocessing

CACHE REVIEW

Fully Associative Cache where there is only one set, and that set contains all cache lines. Must check tags.

When the cache becomes full, a replacement policy determines which block to evict to make room for a new block.

Direct-Mapped Cache where each memory block maps to a cache line, and compare the stored tag with the tag of the memory block.

Set-Associative Cache where there are multiple sets, and each set contains a certain number of cache lines. The number of cache lines in a set will need to be searched.

Types of Cache Misses

• Cold miss: first time cache block is accessed
• Capacity miss: cache is full and must evict a block (even if fully associative)
• Conflict miss: multiple blocks map to the same set. If fully associative and other sets are empty, block would not be evicted.
• Sharing miss: another processor acquired exclusive access to cache block
  • True-sharing miss: two processors access same data on cache block
  • False-sharing miss: two processors access different data on cache block

If conflict misses for submatrices, copy into temporary smaller matrices or pad rows.

Ideal-Cache Model

Parameters:

• Two-level hierarchy
• cache size of $M$ bytes
• cache-line length of $B$ bits
• fully associative
• optimal, omniscient replacement

Essentially, LRU with twice the space keeps everything recently used. If it still misses, the working set has been large enough that OPT with half the space must also have missed often nearby.

Tall Caches Assumption: $\mathcal{B}^2 < c \mathcal{M}$ for some sufficiently small $c \le 1$

Issue with short caches is that an $n \times n$ submatrix stored in row-major order may not fit in short cache even if $n^2 < c \mathcal{M}$.

• Submatrix will touch $n$ cache lines, and cache only has $\mathcal{M}/\mathcal{B}$ so trouble will start occuring when $n > \mathcal{M}/\mathcal{B}$.

Now using Submatrix Caching Lemma, if $n \times n$ submatrix $A$ is stored into a tall cache with $\mathcal{B}^2 < c \mathcal{M}$ with $c < 1/3$ and $c\mathcal{M} \le n^2 < \mathcal{M}/3$, then $A$ fits into cache. This makes the number of misses at most $3n^2/\mathcal{B}$.

Cache Analysis of Matrix Multiplication

Total work: $O(n^3)$. Assume row major and tall cache.

Analyze matrix $B$ assuming LRU:

• $n \ge \mathcal{M}/\mathcal{B}$ (number of cache lines): $Q(n) = \Theta(n^3)$ as matrix $B$ misses on each access.
• $\mathcal{M}^{1/2} \le n < \mathcal{M}/\mathcal{B}$ (full column worth of cache lines can fit in cache): $Q(n) = n \cdot \Theta(n^2/\mathcal{B})=\Theta(n^3/\mathcal{B})$, as matrix $B$ can exploit spatial locality.
• $n < c \mathcal{M}^{1/2}, c < 1/3$: $Q(n) = \Theta(n^2/\mathcal{B})$, by submatrix caching lemma.

Tiling

Total work: $O((n/s)^3 (s^3)) = O(n^3)$.

If you tune $s$ so that $s = \Theta(\mathcal{M}^{1/2})$, submatrix caching lemme implies $\Theta(s^2/\mathcal{B})$.

Can further extend to Two Level Cache and Multi-Level Cache, but they get much harder to tune (easy to mistune).

code

Divide-and-Conquer

code

This gives

Cache Oblivious Algorithms

We aim for cache oblivious algorithms, where the algorithm can passively autotune to different configurations.

Essentially in a parallel Cilk computation with private caches, total caches equal serial cache misses plus small overhead (proportional to # steals times cache size).

4/7/26: Cache Oblivious Algorithms

Heat Diffusion

Finite-Difference Method: approximating derivatives and solving differential equations without a clean closed-form solution.

Assuming $\delta(t)=1$ and $\delta(x)=1$, we get:

So finite-difference method becomes a stencil computation after discretization. (stencil is a fixed pattern)

To save memory, we can use the even-odd trick:

Cache-Oblivious Stencil Computations

Recall performance measures are done via: work $T_1$ and cache misses $Q$.

$Q=\Theta(NT/\mathcal{B})$.

As a 3-point stencil, we can recurse these regions as:

We recurse as such:

• If width $\ge 2 \cdot$ height, cut trapezoid with line of slope $-1$ through center. Traverse trapzeoid on left first, then the right.
• If width $<$ 2 $\cdot$ height, cut trapezoid with horizontal line through the center. Traverse bottom trapezoid first, then top one.
• Base case is height $=$ 1, so just compute all space-time points.

code

work and cache analysis

Essentially work stays the same at $\Theta(TN)$ but cache misses drop to $\Theta(TN/\mathcal{B}\mathcal{M})$.

Despite fewer cache misses, advantage is negligible, due to a good memory architecture and prefetching.

Parallelizing Cache-Oblivious Stencil Computation

Note that time cuts can't be parallelized, as time depends on the previous time. Similarly with a space cut, we must traverse trapezoid on left before traverse the right.

We utilize a parallel space cut to produce two trapezoids that can be executed in parallel and third "inverted" trapezoid that executes after the two completions.

Parallelizing with Cilk now addresses insufficient parallelism and scheduling overhead. To address lack of memory bandwidth, we run $P$ identical copies of serial projection in parallel (given enough memory).

Cache-Oblivious Sorting (*)

c-o algorithms

c-o data structures

[TODO: look at these]

Takeaways

• Cache-oblivious algorithms can use cache as well as cache-aware algorithms without resorting to vodoo parameters
• Cache-efficiency matters more for parallel code
• Base case of DnC algorithms must be engineered to account for hardware acceleration (prefetching) along fast-moving index of array
• DnC cache-oblivious algorithms over looping algorithms diminish as number of dimensions increase.

Merging Algorithms

Merge two sorted arrays:

Merge Sort:

code

• Work $W(n) = 2W(n/2) + O(n) = \Theta(n\log n)$
• With caching, \[Q(n) = \begin{cases} \Theta(n/\mathcal{B}) & \text{if } n^2 < c \mathcal{M} \\ 2Q(n/2) + \Theta(n/\mathcal{B}) & \text{otherwise} \end{cases}\]

  This gives $Q(n) = \Theta((n / \mathcal{B})\log (n / \mathcal{M}))$.

  asymptotic analysis

  $n >> M$: $W(n)/Q(n) \approx \Theta(\mathcal{B})$

  $n \approx M$: $W(n)/Q(n) \approx \Theta(\mathcal{B} \log n)$

Multiway Merging: merge $R < n$ sorted subarrays with a tournament

This gives $W(n) = \Theta(n \log n)$.

This gives $Q(n) = \Theta((n / \mathcal{B})\log_R (n / \mathcal{M}))$.

We get $W(n)/Q(n) \approx \Theta(\mathcal{B} \log \mathcal{M})$.

cool diagram of funnel

4/9/26: Nondeterministic Parallel Programming

Deterministic program on a given input is if every memory location is updated with the same sequence of values in every execution.

• Program always behaves the same way
• Two different memory locations may be updated in different orders, but each location sees same sequence of updates.

Atomicity and Mutual Exclusion

Concurrent Hash Table:

A sequence of instructions is atomic if the rest of the system never views them as partially executed. At any moment, either no instruction in sequence have executed or all of them are executed.

A critical section is a piece of code taht accesses shared data structure which must not be accessed by two or more strands at the same time (mutual exclusion).

A mutex is an object with lock() and unlock() functions. If a strand tries to lock an already locked mutex, it will cause that strand to block (or just wait) until mutex is unlocked.

Dealing with concurrent hash tables:

• Introduce mutex and lock and unlock around critical section.
  

  This is very slow though.

• Make each slot a struct with mutex and pointer head to slot contents
  
  THIS FAILS DETERMINISM

  Whichever thread acquires the lock second becomes the new head. Being serialized in an arbitrary order make the final linked-list order depend on which thread acquires lock last.

  

Types of Races

• Determinacy race occurs when two logically parallel instructions access same memory location and at least one instruction performs a write.
  note

  A program execution with no determinacy races means that the program is deterministic on that input. If determinacy race exists in a program w/o mutexes, Cilksan will guarantee to find such a race.
• Data race occurs when two logically parallel strands holding no locks in common access same memory location and at least one strand performs a write.
  note

  data-race-free programs can still be nondeterministic as acquiring a lock can cause a determinacy race with another lock acquisition.
  no data race != no bugs

  

  Since you unlock in between, a thread can slip in after first line and before second. This causes stale next pointers, causing lost nodes.

Implementation of Mutexes

Properties

• A yielding mutex returns control to the operating system when it blocks.
  yielding mutex

  

  A spinning mutex consumes processor cycles whiile blocked.

  spinning mutex

  

  xchg is an atomic exchange operation

• A reentrant mutex allows a thread that is already holding a lock to acquire it again. A nonreentrant mutex deadlocks if the thread attempts to reacquire a mutex it already holds. [TODO: review]
• An unfair mutex lets any blocked thread go next. A fair mutex type allows the thread that has been waiting longest to go next (FIFO queue).

Locking Anomaly: Contention

Use a spinning or yield mutex for the result accumulate? [TODO: review]

spinning mutex

Essentially sequential.

test + spin mutex

simple spin mutex

As $P$ grows, more threads are contending for the same lock. Essentially, simple spin makes everyone collide on the lock, test-and-spin reduces collisions, and green is the unattainable best-case floor.

The main problems:

• Everyone misses: reads satisfied sequentially
• Everyone does XCHG: invalidates others' caches
• eventually quiesces after lock acquired. Quiescence time can increase linearly with the number of processors.
  

To do better we can try:

backoff mutex

If the lock looks free but I fail to get it, there must be contention. So its best to back off than to collide again.

Ideas include exponential backoff, but that does double expected wait for each failure.

Deadlock

Holding more than one lock at a time can be dangerous.

Conditions for Deadlock

• Mutual Exclusion: each thread claims exclusive control over the resources it holds
• Nonpreemption: each thread does not release the resources it holds until it completes its use of them
• Circular waiting: a cycle of threads exist in which each thread is blocked waiting for resources held by the next thread in cycle
  NOTE related to dining philosophers problem

deadlock with 1 lock (mutex across join)

main waits on foo, foo waits on L, and L is held by main.

Tips:

• Don't hold mutexes across joins
• Hold mutexes only within cilk_scope
• try to avoid nondeterministic programming

Convoy

A lock convoy occurs when multiple threads of equal priority contend repeatedly for the same lock.

example

Solution is to use nonblocking function try_lock instead of lock.

• try_lock returns true if the lock is acquired, false otherwise (doesn't block)

In Cilk Plus, when it fails, it tries to steal again at random.

4/14/26: Synchronization without Locks

Sequential Consistency

Memory Model: defines how loads/stores behave across processors.

Question: can $r_0=r_1=0$?

Sequential Consistency: pretend all processors’ instructions were merged into one single global order, while keeping each processor’s own program order unchanged.

Guarantees $\%$eax = $\%$ebx = 0 never happens.

A program execution is sequentially consistent iff you can place all instructions into one total “happens-before” order that preserves each processor’s program order and makes every LOAD read the most recent earlier STORE to that address.

Mutual Exclusion

Critical sections is a piece of code that needs mutual exclusion (no two threads can execute it at the same time).

Computer hardware provides atomic read-modify-write instructions to build locks safely.

Theorem. [Peterson's Algorithm]

Alice and Bob each sets whether they want in, then gives other person priority with turn and wait only if the other also wants in and it's their turn.

A correct lock needs mutual exclusion so no two critical sections overlap. Deadlock freedom so the system keeps making progress, and starvation freedom so any thread trying to enter eventually gets in.

proof of peterson's algorithm guarantees mutual exclusion

mutual exclusion

FTSOC both Alice and Bob execute critical section concurrently. Consider the most-recent time that each of them execute code before entering the critical section.

WLOG Bob was last to write to turn.

Alice and Bob's program starts with:

It goes Alice's program order to the WLOG statement to Bob's program order

We assume Bob would get in, but ordering forces Bob to read both A_want = True and turn = A, so he should spin.

deadlock freedom

starvation freedom

If Alice is waiting, Bob may enter once, but then Bob eventually exits and sets B_wants = false, so Alice’s wait condition becomes false and Alice enters.

Relaxed Memory Consistency

No modern-day processor implements sequential consistency, but some relaxed form.

We can reorder as long as a and b isn't in the same memory location. And there is not concurrency.

Hardware Reordering: A processor may put stores in a store buffer and let later loads to different addresses bypass them, so execution can look like a later load happened before an earlier store.

This hides store latency. All other combinations of store orders are preserved.

BUT: this breaks sequential consistency. The LOAD'S of B wants and A wants can be reordered before the STORE'S of A wants and B_wants,respectively.

Memory fence/Memory barrier: do not let later loads/stores bypass earlier loads/stores across this line

Real machines need atomics/fences so the machine actually behaves like the proof assumes.

Must declare variables with _Atomic and use atomic_load and atomic_store instead of load and store.

Real locks need real hardware atomics because plain reads/writes are too weak/expensive to scale.

Compare-and-Swap

Compare-and-Swap an atomic read-modify-write instruction that checks whether a memory location still has an expected old value, and if so replaces it with a new value, all as one indivisible step.

code

proof

false = unlocked/free, true = locked/taken.

Ways to prevent cilk race:

using mutex

using CAS

Rereads result until CAS succeeds.

Lock-Free Algorithms

lock-free Push

lock-free Pop

Efficient lock-free algorithms still can cause a thread to starve. Transactional memory offers one way to revolutionize this area by allowing a block of code to be atomic.

ABA Problem

A thread sees head = A, pauses, another thread changes head to $B$, and pushes back to old $A$ node (same memory, but A shouldn't overwrite it)

Solutions: versioning (version number of each pointer) which increments each time pointer is changed, though it could get very large. Also, reclamation which prevents node reuse while pending requests exist.

4/16/26: Project 4 Code Walkthrough

--

4/21/26: Speculative Parallelism

Computer Chess

Min-max tree: We define value of leaf to be $1$ if white wins, $0$ if black wins, and $0.5$ if draw.

• value of White's internal node is the maximum of children's values, and value of Black's internal node is the minimum of children's values
• the principal variation is the sequence of moves in which each of Black and White play optimally

Searching game tree for chess is impossible. Compromise heuristic is to search to some fixed depth $d$. Use a static evaluation at the leaves to estimate expected value of the leaf (no longer just 0/0.5/1).

However, a depth-d search is still exponential $\approx b^d$ where $b$ is the branching factor

We define a move transposition to cause the game tree to reconverge (two different paths to the same position)

Alpha-Beta Search

game tree represents all move from current position given a search ply/depth. At leaves apply static evaluation to get value.

• MAX chooses maximum score among its children
• MIN chooses minimum score among its children

If MAX discovers a move so good that MIN would never allow that position, MAX's other children need not to be search (beta cutoff).

Once it sees a score higher than 6, all other children after don't need to be searched.

code

every node maximizes from the current player’s perspective, recursion flips signs and swaps the window, and if alpha >= beta, the branch is cut off because the opponent would never allow it.

alpha is the best score found so far for the current player, beta is the cutoff threshold from opponent (will avoid if better)

The root max has a better value of $5$, so if right purple min node is $4$, we need not search the rest of the right most branch.

Analysis of Alpha-Beta Search

Number of nodes in a game tree with branchinb $b>1$ and $d>=0$ is

Hence as a result, alpha-beta effectively doubles search depth, square-roots the work, square-roots branching factor.

Speculative Parallelism

Bentley rule: short-circuit optimization (aka quit loop early if found the element). How do we parallelize it?

Parallel Alpha-Beta Search

If the first child fails to generate a beta-cutoff (if does, we can skip other children), speculate the node is maximal, and search the remaining children in parallel. Bet you won't waste any work.

We know from above that $T_1 = 2b^{d/2}$ (work). When we do Child 1 and all other child in parallel, its just like the work of searching a tree with branching factor $2$. Hence $T_\infty = 2\cdot 2^{d/2}$ (span).

The parallelism is $(b/2)^{d/2}$.

But what if game trees is not best-ordered?

Wasted work on the right tree since middle min node is not known yet. Propagating information scores up is tricky to setup and efficiency relies on lucky scheduling.

In general, speculation in parallel alpha-beta search will always waste some work.

Scout Search

Zero-window search just checks if a score is less than or greater than $\alpha$ or $\beta$.

It is fast for pruning some earlier trees but once a move might be better, it must do a full window search.

[TODO: read about]

• Late-Move Reductions
• Futility Pruning
• Null Move Margin Pruning

4/23/26: Structure and Unstructured Data

Performance engineering is not just choosing better algorithms or optimizing code. Choosing the right data representation can give both asymptotic wins and low-level speed wins.

Most data in the world is in Arrays, and they are fast since modern hardware and compilers optimize for contiguous, predictable memory access, allow caches, prefetching, vectorization, tiling, and parallelization to work well.

FORTRAN: first data structure in a programming language

We represent arrays through tensors, and it is advatangeous as it is simple to use, no pointer chasing, and works well with modern cache and prefetches.

Einsum is a compact way to describe tensor/array computations.

Types of structure:

• Repeated data values: values or patterns that appear many times in a dataset, so we can store them more compactly using compression instead of repeating every copy.
• Sparse data values: datasets where most entries are the default value, usually zero, so we store and compute only on the nonzero entries.
  threshold

  
• Symmetric data values: datasets where one part determines another part, e.g. $A_{ij} = A_{ji}$, so we only need to store one triangle/side instead of the full structure.

Storing and Accessing Sparse Data

Compressed Sparse Rows Format (CSR): COO/CSR store only existing entries: rows and cols tell where each stored value lives in the original matrix.

view

Computing with Sparse Data

code

A lot less data and a lot less computation. (NM >> NNZ)

Note that A_pos chooses the row’s slice; A_crd gives each entry’s column; A_vals gives the actual stored value.

However, restricted iterations as we only get $O(1)$ acccess for the next element (not all elements like dense)

• Dense-sparse iteration: iterate over the sparse structure's nonzero coordinates, then use those coordinates to perform $O(1)$ lookups into the dense array.
• Leader-follower algorithm: the sparse array is the leader because it chooses which coordinates matter, and the dense array follows by providing values at those coordinates.
• Sparse-sparse iteration: compute only coordinates where both sparse inputs have nonzeros, usually by intersecting their coordinate lists.
• Two-finger merge: keep one pointer into each sorted sparse coordinate list, advance the pointer with the smaller coordinate, and compute only when both pointers point to the same coordinate.

Beyond two-finger merge will make code pretty complicated, but requires a good model of the problem and translation into code.

example

$$a_i = b_i + c_i + d_i$$

An edge label like c means “advance/lose c because its coordinate is not part of the next overlap case.

Matrix Multiply

Sparse Matrix Matrix Multiply (SpMM)

Per square on output matrix, we get per row's nonzero columns and multiple with retrieved value from C.

Parallel SpMM

Load Balancing Parallel SpMM

Block compressed storage, not geometric rows, because sparse rows can have wildly different amounts of work.

We will need extra metadata or row-recovery logic

[TODO: this is important]

SpMSpM

LOOP ORDER CHANGES ASYMPTOTIC BEHAVIOR

Optimizing Compound Expression: SDDMM

We have C and D as dense, A and B as sparse.

code

THIS IS FASTER because we don't have to multiply if B is zero! So a kernel combined is faster than two separate kernels.

Repeated Values May Not Be All Zeros

Run Length Encoding (RLE): extension to CSR Format, last value is fill value

We slice the run arrays by row (pos), and slice column (coord) with values (val).

math

This will be 62.

Graphs

We can represent graphs via adjacency matrix. Note we can have sparse matrix when not all vertices are connected, and symmetric matrix when undirected.

BFS

Serially,

• Initialize $\texttt{depth[source]}=0$, all others $-1$, and queue the source.
• Pop $v$ from the queue; for each unvisited neighbor $u$, set $\texttt{depth[u]}=\texttt{depth[v]}+1$ and enqueue $u$.
• First visit gives shortest unweighted distance.

Parallel,

visual

• Maintain current frontier $\texttt{frontier\_in}$ and next frontier $\texttt{frontier\_out}$.
• Process all $v \in \texttt{frontier\_in}$ in parallel and add newly discovered neighbors to $\texttt{frontier\_out}$.
• Use CAS on $\texttt{depth[u]}$ to avoid races when multiple vertices discover the same $u$.
• Swap frontiers and increment depth.

code

• Push BFS is wasteful when frontier is large: many outgoing edges point to already-visited vertices.
  graph

  
• In that case, switch to pull BFS: unvisited vertices check whether any incoming neighbor is in the frontier.

PUSH + PULL CODE

at pull: each unvisited vertex checks its incoming neighbors to see whether any are in the current frontier.

Page Rank

Problem: assign a score to each vertex based on score of neighbors

This has poor cache performance. (every write is a random access in the new_ranks array)

Improve locality:

• Partition/reorder the graph so edges in the same block update nearby vertices.
• This makes writes to new_ranks more cache-friendly instead of random.
• Blocking also lets each worker handle a region with less cross-thread contention.
• The preprocessing cost is worth it because PageRank runs many iterations.

Convert the data layout from CSR to BCSR (Blocked CSR). Can be combined with PULL traversal to avoid atomics (reads from others not write to others)

Inserting to Sparse

Adding a data item in middle of an array is $O(n)$ for sparse array, but $O(1)$ for dense array.

4/28/26: What Compilers Can and Cannot Do

Recall compiler pipeline:

Now we aim to optimize and transform our LLVM IR to make code even faster:

Useful for plenty of architectures:

We study compilers because they can automatically produce fast code from readable code, but they are conservative/finicky, so understanding their choices helps you write code they can optimize and debug when they fail.

Overview of Compiler Optimizations

Don’t hand-optimize blindly; first know what the compiler already does and where it needs help.

Simple Examples

• Inlining: replace a small function call with the function body, removing call overhead and exposing more optimization opportunities.

  Example: square(A[i]) becomes A[i] * A[i] inside the loop.

• Hoisting: move loop-invariant work outside the loop when the compiler can prove it does not change.

  Example: exp(sqrt(M_PI/2)) is constant, so the compiler precomputes it and multiplies by a constant inside the loop.

  NOTE if the expression involves function calls like sqrt(M_PI/N) and the compiler cannot prove enough, it may only partially hoist.
• Combining tests: simplify nested conditionals into fewer branches, selects, or lookup tables.

  Example: a full-adder's many if cases can become table lookups indexed by bits of a,b,c.

  lookup table

  
• Loop unswitching: if a condition inside a loop is loop-invariant, split the loop into two versions with the condition outside.

  Example: instead of checking debug every iteration, create one debug loop and one non-debug loop.

  visual

  
• Arithmetic strength reduction: replace expensive arithmetic with cheaper equivalent instructions when valid.

  Example: n * 8 becomes a shift/LEA; division by a constant can become multiplication by a magic number plus a shift.

  optimized assembly

  

  Division is slow: multiply by magic number and shift right

How the Compiler Works

An optimizing compiler runs a sequence of transformation passes over LLVM IR, which each pass (which can run multiple times) analyzes and edits code to optimize performance. These passes are predetermined in order.

One pass can enable later passes, but the order is not always globally optimal.

Why doesn't the compiler always optimize?

• Must be correct for all legal inputs.
• Has limited knowledge of program inputs and hot paths.
• May not see the whole program.
• Uses an imperfect cost model of the hardware.
• Some analyses are undecidable, NP-hard, or too expensive.
• Compiler passes are heuristic and can miss cases.

inlining vs hoisting

After inlining, the compiler may struggle to hoist loop-invariant work out of the loop.

Optimizing Scalar Arithmetic

At -O0, LLVM is very conservative and keeps local variables in stack slots.

For

the unoptimized IR does:

• allocate stack storage with alloca
• store arguments into local memory
• load them back
• multiply
• return result

Mem2Reg: compiler pass that promotes stack-allocated variables into registers.

mem2reg

Replace loaded values with original registers, then remove dead stack loads/stores.

Optimizing a Structure

Structs are harder to optimize because code operates on individual fields through addresses.

Example:

At -O0, LLVM computes addresses for each field:

• compute address of a.x, b.x, c.x
• load a.x, load b.x
• add them
• store into c.x
• repeat for y

code

Scalar Representation of Aggregates (SROA): bust a struct into individual scalar fields and optimize those fields separately.

SROA

Treat fields like:

\[ \texttt{cx = ax + bx} \] \[ \texttt{cy = ay + by} \]

instead of repeatedly loading/storing the whole struct. They are treated as independent values.

Optimizing Function Calls

Inlining replaces a function call with the body of the called function.

code

math

\[ \texttt{vec\_add(pos, vec\_scale(vel, dt))} \]

can become scalar arithmetic:

\[ \texttt{new\_x = pos.x + vel.x * dt} \] \[ \texttt{new\_y = pos.y + vel.y * dt} \]

LLVM IR

• Small helper functions like vec_add and vec_scale can be copied into the call site.
• The compiler then removes the call/return overhead.
• After inlining, useless pack/unpack instructions can be eliminated.

Compiler Reports (*)

    clang -O3 file.c -Rpass=.* -Rpass-missed=.* -Rpass-analysis=.*
    

Optimizing a Loop

Example: normalize a vector.

Naively, norm(X,n) appears inside every loop iteration.

• Hoisting: since norm(X,n) is loop-invariant, compute it once before the loop.
• Strength reduction: replace division inside the loop with multiplication by reciprocal.

The compiler is able to implement many loop optimizations including algebraic identities.

Something the Compiler Can't Do

The compiler is unlikely to discover high-level mathematical structure.

Example: in an $n$-body simulation,

so one force computation could update both bodies. But the compiler is unlikely to automatically exploit this symmetry.

Summary

• Compilers transform code through many IR passes.
• One optimization can enable later optimizations.
• Compilers must be conservative when correctness is uncertain.
• IMPORTANT: Help the compiler with simple code, restrict, const, flags, and compiler reports.

Case Studies (*)

Link-Time Optimization

Normally, the compiler optimizes each source file separately.

Problem:

• The compiler only sees one compilation unit at a time.
• If a function is defined in another file, the compiler usually cannot inline it.
• This blocks later optimizations that depend on inlining.

Link-Time Optimization (LTO): keep LLVM IR/bitcode until link time, then optimize after all files are linked together.

• Compile each source file into LLVM bitcode instead of final assembly.
• Link the bitcode files together.
• Rerun LLVM optimizer with visibility across files.
• Enables cross-file inlining and whole-program optimization.

clang -O3 -flto file1.c file2.c -o program

5/12/26: GPUs & Accelerated Computing

Introduction

Instead of x86 CPUs, we will look at hardware beyond the CPU.

Hardware progress is real and extreme.

• Modern hardware delivers orders of magnitude more compute and energy efficiency than historical systems
• Contrast:
  • First supercomputer: Cray 1 (1975).  160 MegaFLOPS, 8MB RAM, costed $\$7.9$M (56M today)
  • Modern SoC/GPU: Tera-PetaFLOPs at comparable power
• Energy efficiency improved by  1e9x over these past 50 years.

Matrix Multiplication on Apple M2:

• Python: 10 MegaFLOPS or  $0.00005\%$ of SoC peak
• JavaScript: 500 MegaFLOPS, or $~0.0025\%$ of SoC peak
• C: 1 GigaFLOPS, $~0.005\%$ of SoC peak
• Optimized C (look reorder, vectorization, parallel cores):  $0.1-1\%$ of SoC peak
• C & Assembly (quantized to bf16, matrix units): 1.5 TeraFLOPS, $7.5\%$ of SoC peak
• GPU (metal compute shaders): 3.2 TeraFLOPS, $15\%$ of SoC peak
• Neural Processor Unit (int16 quantized, proprietary),  $80\%$ of SoC peak

Extreme programming effort & specialization of code. Requires

• data layout control
• vectorization
• parallelism
• specialized hardware (tensor units / NPUs)
• thousands of lines of low-level code

Hardware is amazing, but there is a mismatch between programming models and hardware reality.

• Programming models still assume
  • sequential, scalar execution
  • uniform global memory
  • abstractions via pointers, calls, virtual memory
• Hardware however is
  • deeply parallel
  • hierarchical (registers $\rightarrow$ caches $\rightarrow$ DRAM)
  • throughput-oriented

Modern systems are still basically PDP-11s, at the programming model level. CUDA doesn't fix this, but it exposes more of the hardware.

Pipeline for CPU performance model

• Fetch
• Decode
• Operand fetch
• Execute
• Writeback

CPU optimizations include:

• Higher clock speed (limited by power, leakage)
• Superscalar execution (multiple instructions/cycle)
• Out-of-order execution (avoid stalls via speculation like for branches, memory pre-fetchers)

We most need performance when processing lots of stuff. So we aim to optimize aggregate rate of processing many items, or a throughput-oriented view on performance.

Efficiency is programmer's problem.

There is diminishing returns with single-core scaling, as power and area efficiency collapse. When doubling silicon area, we see diminishing returns for a big core vs just replicating into multiple simpler cores.

Goal is to better understand hardware, program it explicitly for performance, and reason from first principles.

GPUs hide latency mainly by issuing other warps when one warp is waiting (warp-level multithreading).

Throughput Processors

Processor is a programmable computer that runs a sequence of instructions over time including control flow, computation & state updates.

• modern CPUs are still conceptually similar to early designs (PDP-11)
• now on silicon chips

Traditional CPU Performance Optimizations (Latency-Oriented)

• Increase the clock speed
  • Higher voltage $\rightarrow$ quadratic power cost
  • Deeper pipelines $\rightarrow$ lower IPC
  • Faster transistors $\rightarrow$ higher leakage
• Superscalar execution
  • Multiple instructions per cycle
  • Requires, multiple ALUs, out-of-order execution, complex scheduling logic
  • Complex scheduling logic
• ILP + speculation
  • Branch predictors, prefetchers, OoO buffers
  • Works well only with single thread, hard-to-parallel workloads

However, modern workloads have abundant data parallelism, meaning they need aggregate throughput.

Throughput is driven via:

1. Total work
2. Available hardware resources
3. Efficiency of using them

To do such, idea is to simplify cores, add parallelism.

Idea 1: Remove latency-oriented hardware

• OoO execution
• Branch predictions
• Huge caches
• speculation

Use the saved area for many simpler cores, and explicit parallelism.

Idea 2: amortize control overhead with SIMD execution

• One instruction stream but many ALUs execute it on different data
• Benefits:
  • Control logic shared
  • High ALU utilization per unit area
• Costs:
  • Requires coherent control
    
  • Branch divergence wastes ALU lanes
• SIMD exists as:
  • Explicit ISA (AVX, NEON)
  • Implicit hardware (GPUs)

Scaling beyond SIMD: Multicore

• SIMD width saturates (typically 8-64 lanes)
• Further scaling requires replicating cores
• Throughput processors use many small cores, not wide superscalar ones

Idea 3: Interleave parallel tasks to hide latency

Memory latency: hundreds of cycles

• cache miss
• off-chip DRAM

Hence, we can interleave independent tasks, where when one stalls, we run another. (aka how we interleave warps)

This is hardware multithreading, which requires extra register/state storage. We trade per-thread state area for latency hiding.

A throughput-oriented processor exploits abundant parallelism for efficiency:

• Scales via multicore, not ILP
• Uses SIMD to amortize control
• Hides latency via many concurrent threads
• Avoids speculation
• Accepts higher single-thread latency for better total throughput

Idea 4: amortize instruction overheads with more complex instructions

GPU (RTX 4000 Ada):

One core (warp scheduler) of GPU

• 32x32-bit ALUs/vector lanes (exec units)
• 512x32x32-bit registers
• 1 warp instruction/clock (32 lanes)
• Up to 12 live threads (independent warps)

One SM is a cluster of 4 warp schedulers. The whole GPU has 48 SMs, or 192 cores. This is 6144 exec units which hits 26.7 TFLOPs. Limit of 192x12 = 2304 threads. 12 MB of registers. 48MB L2 cache.

CPU(AMD Zen 4):

One core of CPU

• Huge, complex control logic
• Two 256-bit vector ALUs = 16x32-bit exec. units
• 192 vector registers
• 1 MB cache
• 2 hyperthreads

Whole CPU has 8 cores x 16 = 128 exec units, which hits 1.4 TFLOPs. 8x2 = 16 threads, 24 KB registers. 40MB L2+L3 cache.

A throughput processor is still a processor, but software must expose explicit parallelism across data and instruction streams.

Data Movement

The overhead of datamovement is 100x vs compute. Data supply dwarfs computation for primitive ALU operations. 32-bit IADD overhead is $99\%$ of total execution time.

Amortize data-supply with more complex instructions

• RISC to CISC
• Essentially getting to ASIC-in-an-instruction
• Texture mapping (compute many address, load, and compute a blend) is implemented as a single instruction
• Matrix block multiply accumulate is becoming a single instruction too

MMA instructions amortize energy overhead of data-supply (drop from $75\%$ (serial) to $12\%$ (int8)-$19\%$ (fp16)). Any instruction not using MMA leaves 90+$\%$ of peak energy efficiency.

Matmul has high arithmetic intensity (work / data) which is what allows it to amortize the data-supply overhead.

Optimizations for GPUs

Changing the programming model:

• Multicore over ILP
• Amortize control with SIMD
• Hide latency with threads
• Minimize precision
• Amortize data suply with complex instructions
• Seek arithmetic intensity

Class Info

This class was taught by Saman Amarasinghe, Charles E. Leiserson, and Nir Shavit.