Quiz 2 Cheat Sheet

Memory-Level Parallelism / Bandwidth

MLP: number of outstanding memory requests.

Patterns:

• n=A[n]: pointer chasing; next address depends on loaded value; MLP \(\approx 1\).
• n=2*n mod p: address independent of loaded value; OoO can issue many misses.
• sequential/stride: stream/stride prefetchers help.
• random access: prefetchers mostly fail.
• L1 LFBs handle demand misses; L2 stream prefetcher can expose more MLP.
• MLP enablers: out-of-order execution, hardware prefetching, branch prediction.

Amdahl with memory cap:

Cache Model / Address Bits

Ideal cache: size \(\mathcal M\), line \(\mathcal B\), fully associative, optimal/LRU replacement. For real cache size \(C\), associativity \(A\), line size \(B\), address width \(w\):

Miss types:

• Cold: first access to block.
• Capacity: working set too large.
• Conflict: set collision.
• True sharing: same data.
• False sharing: different data same line.

Segment lemma: contiguous segments total \(N<\mathcal M/3\), average segment size \(\ge\mathcal B\):

Tall cache:

Submatrix lemma: \(n\times n\) row-major submatrix fitting tall cache:

If whole working set fits:

Cache-Efficient Algorithms

Naive matrix multiply:

Bad row-major access \(B[k][j]\):

Tiled matrix multiply:

Cache-oblivious D&C matrix multiply:

Generic cache-recursive rectangle:

Loop rule: if inner array is too large and reloaded every outer iteration:

Cache-Oblivious Stencils

Heat update:

Even-odd trick: keep only \(u[t\bmod 2][x]\). Looping 1D stencil with \(N>\mathcal M\):

Naive 2D stencil with \(n^2>\mathcal M\):

Trapezoid recursion:

• if width \(\ge 2h\), space cut
• if width \(<2h\), time cut
• base case: \(h=1\)

If leaf width \(w=\Theta(\mathcal M)\):

Parallel stencil: time cuts cannot parallelize. Space cuts can parallelize.

Determinism / Races / Locks

Deterministic: every memory location sees same sequence of updates every execution.

Determinacy race: logically parallel instructions access same location and at least one writes.

Data race: logically parallel strands hold no common lock, access same location, and at least one writes.

Atomic = system never observes sequence partially executed. Critical section = shared-data code requiring mutual exclusion.

Locks:

• spinning burns cycles
• yielding gives CPU to OS
• reentrant lets owner relock
• nonreentrant owner relock deadlocks
• fair = FIFO-ish
• unfair = any waiter can acquire

Contention: repeated xchg invalidates everyone else's line. Test-and-spin reads until free, then atomically exchanges. Backoff waits after failure.

until contention or bandwidth dominates. Performance ranking:

Deadlock / Convoys

Deadlock needs:

Global lock order:

Valid all-lock acquisition rules must impose one global order over all locks. Random start/order can deadlock. Rules:

• do not hold mutex across sync/join
• keep locks inside cilk_scope
• use try_lock to avoid convoys

Lock convoy: many threads repeatedly block on same lock.

Allocators / Garbage Collection

Bitmap allocator:

• good for tiny objects: less internal fragmentation
• compact metadata can reduce pages/TLB misses
• may have higher allocation latency due to scanning

Free list:

• fast allocation/free via pointer pop/push
• pointer/index metadata hurts tiny objects

Local ownership allocator:

• each block marked with owner thread
• owner eventually frees block
• can be resilient to false sharing
• remote frees can require synchronization
• can suffer blowup/drift under imbalance

Stop-and-copy GC:

• compacts live objects
• improves external fragmentation
• must update pointers
• not necessarily asymptotically faster

Mark-and-sweep: does not move objects; can leave external fragmentation.

Memory Models / TSO

Sequential consistency: all operations appear in one global total order preserving each processor's program order; load reads latest previous store to that address.

Store-buffering:

Under SC:

x86-64 TSO:

• loads not reordered with loads
• stores not reordered with stores
• stores not reordered with prior loads
• load may bypass prior store to different address
• load cannot bypass prior store to same address
• locked instructions globally ordered

Store buffer: stores wait before globally visible; later loads to other addresses can bypass. Fence prevents later memory ops from bypassing earlier ones. Loads check own store buffer for same address.

Peterson / Atomics / CAS

Peterson:

A_wants = true;
turn = B;
fence;
while (B_wants && turn == B);
critical_section();
A_wants = false;

Under SC: mutual exclusion, deadlock freedom, starvation freedom. Proof idea: if both enter, WLOG Bob wrote turn last; Bob sees A_wants=true and turn=A, so Bob spins.

On TSO, fence must be after writing turn, before the while loop. If fence moved before turn:

Fences can also act as compiler barriers. Volatile alone is not a full synchronization primitive.

Use _Atomic, atomic_load, atomic_store, atomic_thread_fence().

CAS: atomically replace if memory still equals expected value.

CAS update:

do {
    old = *addr;
    new = f(old);
} while (!CAS(addr, old, new));

Lock-free push:

do {
    old = head;
    node->next = old;
} while (!CAS(&head, old, node));

ABA: head changes \(A\to B\to A\), CAS succeeds although structure changed. Fix: version/tag pointer or delayed reclamation/hazard pointers.

Speculative Parallelism / Alpha-Beta

Speculative parallelism: spawn work serial projection may never do; trades extra work for parallelism.

Game tree:

• MAX takes max child
• MIN takes min child
• leaf uses static eval

Full depth-\(d\) tree:

Alpha-beta:

search(x, alpha, beta, d):
    if d==0 or leaf: return eval(x)
    for child c:
        s = -search(c, -beta, -alpha, d-1)
        alpha = max(alpha, s)
        if alpha >= beta: return alpha
    return alpha

If \(\alpha\ge\beta\), opponent avoids this line.

Best-ordered alpha-beta:

nodes; square-roots work/branching factor and roughly doubles depth.

Changes searched nodes:

• move ordering: yes
• leaf eval: yes
• transposition table: yes
• board representation: usually no
• -O3: usually no

Young Brothers Wait: search first child serially; if no cutoff, search rest in parallel.

Zero-window/scout: checks above/below threshold; returns bound, not exact score; full-window needed if move may improve best.

Sparse / Structured Data

Arrays are fast: contiguous, no pointer chasing, cache/prefetch/vector friendly. Dense row-major:

Formats:

• CSR: pos=row starts, crd=column indices, vals=values.
• CSC: pos=column starts, crd=row indices, vals=values.
• COO: rows, columns, values.
• RLE: runs of repeated values; row-major vs column-major matters.

Recognition:

Sparse iteration:

• dense-sparse: sparse leads, dense follows with \(O(1)\) lookup.
• sparse multiplication \(a_i=b_i c_i\): coordinate intersection.
• sparse addition \(a_i=b_i+c_i\): coordinate union.

Two-finger merge:

while (i < nnzA && j < nnzB) {
    a = A_crd[i];
    b = B_crd[j];
    m = min(a,b);
    if (a == m && b == m) compute;
    if (a == m) i++;
    if (b == m) j++;
}

SpMV:

SpMM: row work imbalanced; block compressed storage, not coordinates.

SDDMM / compound sparse expression:

If \(B_{ij}=0\), skip; fuse kernels; do not materialize dense intermediate.

Graphs

Graph storage: adjacency matrix simple/dense; adjacency list or CSR sparse/traversal-friendly.

Parallel BFS push:

• process frontier in parallel
• CAS depth[u] from \(-1\) to new depth
• successful CAS discovers vertex

Pull BFS: unvisited vertices check whether any incoming neighbor is in frontier; better when frontier large.

PageRank locality:

• push: random writes/atomics into new_ranks
• pull: reads neighbors, avoids atomics
• partition/reorder graph; BCSR improves locality

GPUs

Warp \(=32\) threads executing together. Block = one or more warps. Grid = one or more blocks. Bad patterns:

Less bad:

Coalescing matters most for global DRAM accesses. Hardware tradeoff:

Compiler Optimizations

Pipeline:

Passes run in heuristic order, may run multiple times, one pass enables another, order not globally optimal.

Optimizations:

• constant folding/propagation: compute/substitute constants
• CSE: reuse repeated expression
• inlining: replace call with body
• hoisting: move loop-invariant work out
• loop unswitching: move loop-invariant branch out
• combining tests: selects / lookup tables
• strength reduction: shifts, LEA, magic multiply
• Mem2Reg: stack locals \(\to\) SSA registers
• SROA: struct/aggregate \(\to\) scalar fields

At -O0: lots of alloca, store, load; locals live in stack slots.

Compiler likely:

If constants are hard-coded and function is inlined:

Compiler limitations:

• must be correct for all legal inputs
• limited hot-path/input knowledge
• imperfect hardware cost model
• analyses may be hard/undecidable
• usually cannot invent algorithmic symmetry

Example compiler likely cannot discover:

Quiz 2: Big Things To Know First

1. Identify the bottleneck

Ask: is this limited by work, span, cache misses, bandwidth, memory latency, lock contention, or nondeterminism?

If memory-bound:

Pointer chasing gives MLP \(\approx 1\). Independent addresses, OoO, branch prediction, and prefetching expose MLP.

2. Cache-analysis recipe

If whole working set fits:

If inner data is too large and reloaded each outer iteration:

For recursive cache-oblivious algorithms:

Use tall-cache/submatrix lemmas when row-major submatrices fit.

3. Races and determinism

No determinacy races \(\Rightarrow\) deterministic. Locks remove some data races but introduce nondeterministic order, contention, convoys, and deadlock risk.

4. Locking / deadlock / contention

Deadlock needs mutual exclusion, nonpreemption, and circular wait.

One hot lock serializes. With \(k\) locks:

until contention/cache-line bouncing/BW dominates.

5. Memory model / Peterson

SC: one global total order preserving each thread's program order. TSO: stores sit in store buffers; later loads to different addresses may bypass earlier stores. Fence after writing turn is the important Peterson placement:

Volatile is not a full synchronization primitive; atomics/fences are the real tool.

6. Allocators / GC

Bitmap: tiny objects, low internal fragmentation, compact metadata, maybe slower scan. Free list: fast pop/push, but pointer/index metadata hurts tiny objects. Global heap: no drift but lock contention. Local ownership: fast local alloc, resilient to false sharing, but remote frees/synchronization and drift/blowup possible. Mark-sweep: does not move objects, can leave external fragmentation. Stop-copy: moves/copies live objects, compacts, updates pointers, improves external fragmentation.

7. Alpha-beta / speculation

Full game tree:

Best-ordered alpha-beta:

nodes. It does not miss the best move; it prunes only when a branch is proven irrelevant. Speculative parallelism creates work the serial projection might not do.

8. Sparse / structure

Dense arrays are fast because contiguous. Sparse saves work only if structure is used.

Multiply sparse coordinates by intersection; add by union. RLE is for repeated runs.