Cache mapping, associativity, and conflicts

Consider a hypothetical cache with line size L, S sets, and A ways per set. Under a simple modulo mapping, divide the byte address by L to obtain its line number, then take the remainder modulo S to choose a set. The remaining address identity acts as a tag. Each set has A places, but a line cannot use an empty place in some other set merely because that would avoid an eviction.

This arithmetic is a teaching contract, not a reverse-engineered description of a particular processor. Real designs can use physical or virtual address information at different stages, slice hashes, skewed mappings, and policies that vary across levels. Software should query documented geometry where possible and treat inferred mappings as hypotheses. Even with known geometry, replacement and concurrent traffic can make the actual residency sequence differ from an ideal least-recently-used trace.

The first touch of a line cannot hit in an initially empty cache: it is compulsory under that starting condition. Later misses may occur because too many live lines need storage, because their mapping overloads one set, or because coherence and other agents remove copies. The classic capacity-versus-conflict distinction uses a fully associative reference cache of the same total capacity and a specified replacement rule; classification depends on that comparison, not merely on a performance counter's name.

To isolate conflict behavior, repeat a short sequence whose total footprint is below total capacity but whose lines all map to one set. Under ideal LRU, cycling through A+1 distinct competing lines can miss on every access after warmup. Changing an address offset can spread the lines across sets without changing their useful values. A timing improvement is evidence worth investigating, but does not by itself prove that a documented cache level caused it.

Padding a matrix leading dimension can change which sets its rows compete for. The extra storage may help one access pattern while hurting another, increasing page count, or defeating vector-friendly alignment. Compare multiple nearby dimensions instead of tuning only a conveniently favorable size. Record the full layout contract so a later allocator change or architecture transition does not silently invalidate the explanation. An optimization should earn its complexity across the workloads that matter.

The probability lab is not a cache model. Its success probability p and integer trial count n define independent Bernoulli trials and exact binomial bars. Use it only as a contrasting model: predict that p=0 makes every success count zero, then explain why assigning a fixed independent hit probability cannot reproduce a deterministic repeated conflict trace. Cache outcomes depend on address history and replacement state; the lab's independent trials deliberately omit both mechanisms.