Midterm Cheat Sheet

Work / Optimization Principles

• Work: total number of operations executed.
• First reduce work, then reduce cycles per unit work.
• On a single core, parallelism / work-stealing do not help.
• Helpful single-core optimizations:
  • loop unrolling
  • hoisting
  • short-circuiting
  • common-subexpression elimination
  • vectorization
  • inlining
• Inlining removes call overhead but can hurt i-cache locality.

Bit Hacks

Core identities

Single-bit mask with \(m = (1 \ll k)\):

• set bit:

  x |= m

• clear bit:

  x &=  m

• toggle bit:

  x ^= m

Core idioms:

• least-significant 1 bit:

  x & (-x)

• clear least-significant 1 bit:

  x & (x-1)

• power of 2:

  x > 0 && (x & (x-1)) == 0

• circular buffer of size \(2^k\):

  x = (x+1) & ((1<<k)-1)

• branchless minimum:

  min(x,y) = y ^ ((x ^ y) & -(x < y))

• branchless maximum:

  max(x,y) = x ^ ((x ^ y) & -(x < y))

No-temp XOR swap:

x ^= y;
y ^= x;
x ^= y;

Builtins to know:

• __builtin_ctzll(x)
• __builtin_clzll(x)
• __builtin_popcountll(x)
• __builtin_assume_aligned(ptr, align)

Hailstone Optimization

Instead of repeatedly dividing by 2 in a loop, compress all trailing factors of 2 at once:

int z = __builtin_ctzll((unsigned long long)n);
n >>= z;
iterations += z;

Why faster:

• fewer instructions
• fewer unpredictable branches

N-Queens Bitmask Recurrence

State:

• down: occupied columns
• left: blocked by left diagonals
• right: blocked by right diagonals
• mask: low \(n\) bits set

Core recurrence:

possible =  (down | left | right) & mask;
place = possible & (-possible);
possible &=  place;

Updates:

down'  = down | place;
left'  = ((left | place) << 1) & mask;
right' = (right | place) >> 1;

Base case:

down == mask

Locality / Caches / Memory Hierarchy

• Spatial locality: nearby addresses likely reused soon.
• Temporal locality: same address likely reused soon.
• Cache moves data in cache lines, not individual words.
• Unit-stride access is much better than strided / irregular access.
• Loop order matters for locality.

Cache miss types:

• Cold miss: first access to a block
• Capacity miss: working set too large for cache
• Conflict miss: mapping collisions in set-associative / direct-mapped cache
• True sharing: cores communicate via same cache line
• False sharing: unrelated variables share one line, causing coherence traffic

MSI / Cache Coherence

• M: modified, exclusive dirty copy
• S: shared, clean copy
• I: invalid
• Before writing a shared line, hardware must invalidate other copies.
• Shared \(\to\) Invalid transition is possible.
• Set-associative caches reduce conflict misses relative to direct-mapped caches.

x86-64 Essentials

• Course uses AT&T syntax: destination is the last operand.
• Suffixes:

  \[ \texttt{b}=8\text{-bit},\quad \texttt{w}=16\text{-bit},\quad \texttt{l}=32\text{-bit},\quad \texttt{q}=64\text{-bit} \]

• cmp/test set flags, jcc reads them.
• Important flags: ZF, SF, CF, OF.
• Addressing mode:

  \[ \texttt{disp(base,index,scale)} = \texttt{base + index*scale + disp} \]

• lea computes addresses without dereferencing memory.

Calling Convention / Stack

Integer / pointer args:

Floating-point args:

Callee-saved:

Caller-saved: everything else.

Standard prologue:

pushq %rbp
movq  %rsp, %rbp

• stack grows downward
• call pushes return address
• ret pops return address

LLVM IR Essentials

• SSA: each register written at most once.
• icmp: compare
• br: conditional / unconditional branch
• phi: select value based on predecessor block
• getelementptr: address computation

Autovectorization

For AVX2:

• 256-bit vector registers
• FP32: 8 lanes
• FP64: 4 lanes

Why compilers fail to vectorize:

• unknown trip count
• cannot prove independence / aliasing
• loop-carried dependence
• reductions
• control flow
• non-contiguous memory / gather
• cost model says not profitable

Important facts:

• floating-point addition is not associative
• restrict helps prove no aliasing
• -ffast-math may be needed for floating-point vectorization

Multicore / Cilk / Reducers

• cilk_spawn and cilk_sync grant permission for parallel execution.
• They do not force parallel execution.
• cilk_for requires independent iterations.

Serial semantics:

#define cilk_for for
#define cilk_spawn
#define cilk_scope

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

Bad example:

int answer = A[0];
cilk_for (int i = 0; i < n; i++) {
    answer = min(answer, A[i]);
}

Use a reducer instead.

Parallelism / Work / Span

Amdahl's Law:

Greedy scheduling theorem:

Near-linear speedup when:

Parallel slackness:

Parallel Loop Formulas

Nested independent \(n \times n\) parallel loops:

Coarsened loop with grainsize \(G\), iteration cost \(I\), and scheduling overhead \(S\):

Want:

but not so large that parallelism collapses.

Alternative coarse-grained span model:

Best balance:

Master Method / Common Recurrences

Useful ones:

Measurement / Timing

• Best raw statistic for runtime: minimum
• For multiplicative benchmark ratios, use geometric mean
• Major noise sources:
  • other processes
  • interrupts
  • DVFS / Turbo Boost
  • hyperthreading
  • cache / page alignment

Tools:

• /usr/bin/time: whole-program timing
• clock_gettime(CLOCK_MONOTONIC): region timing
• rdtsc(): cycle count, but tricky across cores / DVFS
• perf stat: hardware counters

Quiescing tips:

• run on quiet system
• pin with taskset
• avoid core 0 for serial benchmarks
• warm cache vs cold cache matters

Virtual Memory / TLB / Allocators

• page size usually \(4\text{ KiB}\)
• page faults are extremely expensive
• TLB caches virtual-to-physical translations
• TLB miss does not imply cache miss
• L1 lookup can overlap with translation using page-offset bits

Allocator metrics:

where

• \(M\): user footprint
• \(H\): allocator footprint

Fragmentation types:

• internal fragmentation: block larger than requested
• external fragmentation: enough total free space exists, but not contiguously

NUMA / first-touch:

• page goes to the socket of the first thread that touches it
• pinning threads alone does not control memory placement

Memory-Level Parallelism

Little's Law:

Interpretation for memory:

• \(W\): latency
• \(\lambda\): throughput
• \(L\): memory-level parallelism

• pointer chasing often gives MLP \(= 1\)
• independent address generation allows multiple outstanding misses
• hardware prefetchers help for regular patterns
• software prefetch can help when future accesses are predictable enough