FOUNDATIONS

Cache Coherency and Memory Ordering

A visual course for understanding cache lines, coherence states, barriers, atomics, DMA, and multicore visibility.

Reviewed 2026-08-226,364 wordsFirmware, kernel, driver, and CPU designers who need a precise model of shared memory.

The stale-copy problem

Private caches improve latency but create multiple physical copies of the same memory location. Coherence protocols coordinate those copies at cache-line granularity. A correct mental model must track the address, line state, owner, sharers, pending transactions, and the exact event that makes new data visible. Thinking only in C variables hides the mechanism that causes many multicore failures.

Coherence is not memory ordering

Coherence answers whether processors eventually agree on one location. Memory ordering constrains how observations of different locations may be reordered. A system can be coherent while still producing outcomes that surprise code written with an overly sequential mental model. The course uses litmus-style traces to show why atomics and barriers are contracts, not timing delays.

Ownership beyond CPUs

DMA engines, accelerators, and peripherals may access memory without participating in the CPU coherence protocol. Software must define buffer ownership, clean dirty cache lines before device reads, invalidate stale lines before CPU reads, and order descriptor publication correctly. These steps are derived from the data-flow contract so learners can transfer the reasoning to different architectures and operating systems.

What you will be able to do

Separate coherence from consistency
Trace a cache line through common protocol states
Place barriers from ordering requirements instead of habit
Handle DMA ownership and cache maintenance safely

One memory, many fast private views

Each core may keep a local cache-line copy so it can avoid slow DRAM. Once more than one agent can cache the same physical address, the machine needs rules that decide who may read, who may write, and how an old copy stops being usable.

A cache is not a second source-code variable. It is a hardware-managed collection of copies, usually organized in fixed-size cache lines. A load may be answered by a private L1 cache in a few cycles while DRAM would take far longer. That speed gap is the reason the copies exist and also the reason coherence is necessary.

The identity that coherence tracks is normally a physical memory block, not a C variable and not necessarily a virtual address. Two different virtual addresses can alias the same physical line. Conversely, two nearby variables can occupy one line and become coupled even though the program treats them as unrelated.

Coherence is a contract among agents in a coherence domain. CPU cores are common agents, but GPUs, accelerators, and I/O masters may be inside, partly inside, or outside that domain. Never infer device coherence merely because CPU-to-CPU sharing works.

Vocabulary

agent: A component that can issue memory transactions.
cache line: The transfer and coherence unit, often larger than one variable.
private cache: A cache local to a core or cluster.
physical address: The system address coherence normally associates with a block.
coherence domain: The set of agents participating in one visibility contract.

Two readers

Memory contains x=7.
Core 0 loads x and caches its line.
Core 1 loads x and caches another copy.
Both reads can now hit locally.

Multiple clean readers are safe; the difficult case starts when one wants to write.

Common mistakes

A cache contains variables rather than lines.
Every bus master automatically participates in CPU coherence.
A cache hit always means the returned data is globally current without a coherence contract.

Next, define the cache line precisely because protocols move and invalidate whole lines, not individual fields.

Cache lines, tags, sets, and dirty data

A cache divides an address into line offset, set index, and tag. A valid entry holds one aligned block plus metadata; a dirty line contains a newer value than backing memory and therefore cannot simply disappear.

If a machine uses 64-byte lines, addresses 0x1000 through 0x103f belong to one coherence block. A four-byte integer is only part of that block. Fetch, ownership, invalidation, and write-back traffic operate at line granularity, which explains spatial locality as well as false sharing.

The index selects candidate entries, the tag proves which memory block an entry represents, and the offset selects bytes inside it. Associativity lets multiple tags occupy a set. Replacement is a local capacity decision; coherence state is separate metadata governing whether that copy may be read or written.

Write-back caches allow a dirty line to differ from DRAM. The current value may be supplied cache-to-cache or written back when another agent requests it. Therefore 'read memory' is not always the correct mental model: a coherent owner can be the authoritative source.

Vocabulary

tag: The address identity stored with a cache entry.
set: The indexed group of candidate cache entries.
offset: The byte position inside a line.
dirty: Modified relative to the next backing level.
write-back: Defer updating the backing level until required.

Line arithmetic

Choose a 64-byte line size.
Divide address 0x1034 by 64.
The aligned line base is 0x1000.
A store at 0x1038 touches the same coherence unit.

Variables at 0x1034 and 0x1038 can invalidate each other despite having different addresses.

Common mistakes

Dirty means corrupted.
Evict and invalidate are synonyms.
A store changes only the bytes relevant to coherence traffic.

With the unit established, we can state the two invariants every useful protocol protects.

The coherence contract: SWMR and data value

A useful model has two obligations: single-writer/multiple-reader permission for each line, and a data-value rule that makes a read observe the value of the appropriate serialized write. Coherence is per location; it does not by itself order different locations.

The single-writer/multiple-reader invariant says that at any logical time either one agent has write permission or one or more agents have only read permission. A writer cannot coexist with another valid reader. Protocol states encode permissions that preserve this rule through transient races.

The data-value invariant connects permissions to values: after a write becomes ordered for an address, later reads of that address must not indefinitely return an older value. Implementations serialize competing requests at an ordering point such as a bus, home node, or directory.

These are per-line guarantees. If Core 0 stores payload and then stores a separate ready flag, coherence can maintain each location while another core observes the flag before the payload under a weak consistency model. Ordering needs language atomics and architecture barriers.

Vocabulary

SWMR: Single writer or multiple readers.
serialization: A single accepted order for conflicting requests.
ownership: Permission to modify a line.
visibility: When another observer may see an effect.
consistency: Rules relating observations across multiple memory operations.

Permission handoff

Both cores hold Shared x=4.
Core 0 requests write permission.
The protocol invalidates Core 1's copy.
Only after acknowledgements may Core 0 modify x.

The writer becomes unique before it publishes a new value.

Common mistakes

Coherence makes every multithreaded program race-free.
Coherence totally orders all addresses.
Eventual visibility means an immediate wall-clock broadcast.

Now encode those permissions in the smallest teaching protocol: MSI.

MSI: the first complete state machine

MSI labels each local copy Modified, Shared, or Invalid. Processor reads and writes trigger coherence requests; snooped requests trigger state changes, data responses, write-backs, or invalidations.

Modified means this cache has the only valid copy and it differs from backing memory. Shared means the copy is clean and potentially replicated. Invalid means the entry cannot satisfy a processor access. These are permission states, not descriptions of the source-code object.

A read miss issues a shared-read request. A write to Invalid requests exclusive ownership, while a write to Shared sends an upgrade and waits for other sharers to invalidate. A read of another cache's Modified line forces that owner to supply or write back the newest data and downgrade.

Real protocols include transient states because requests and acknowledgements take time. A line waiting for invalidation acknowledgements is not yet safely Modified. Stable-state diagrams are the grammar; production controllers add message queues, retries, ordering rules, and race resolution.

Vocabulary

M: Unique dirty writable copy.
S: Clean read-only copy that may be replicated.
I: Unusable local entry.
BusRd: Teaching name for a shared-read request.
BusRdX: Teaching name for a read-for-ownership request.

Read then write

Core 0 reads an Invalid line and obtains Shared.
Core 1 reads and also obtains Shared.
Core 0 writes and sends an upgrade.
Core 1 acknowledges invalidation; Core 0 becomes Modified.

MSI preserves multiple readers, then creates a single writer.

Common mistakes

Invalid means the DRAM value is invalid.
Shared means another copy definitely exists.
A cache may write as soon as it sends invalidations.

MSI wastes a transaction when a lone reader later writes, so MESI adds proof of exclusivity.

MESI: silent writes from Exclusive

MESI adds Exclusive: a clean line held by exactly one cache. Because no other valid copy exists, that cache may change E to M on a processor write without broadcasting an upgrade.

An Exclusive line is clean like Shared but unique like Modified. The system grants E after a read miss only when the coherence mechanism establishes that no other cache holds the line. A later remote read downgrades E to S; a local write changes E to M silently.

E is an optimization, not a new correctness requirement. An MSI implementation can be coherent without it. MESI reduces traffic for common private-data behavior where a core reads a line and then updates it.

Protocol names are families rather than universal wire formats. Intel systems, Arm ACE/CHI systems, and teaching diagrams may use comparable permission ideas with different transactions, extra states, and implementation-specific optimizations. Do not turn a conceptual MESI diagram into a claim about every product.

Vocabulary

E: Unique clean copy with silent-write permission.
silent upgrade: E→M without a coherence message.
snoop response: Information revealing whether another cache has a copy.
clean unique: Backing memory agrees and no peer copy exists.
protocol family: A conceptual state model with implementation variants.

Private counter

Core 0 reads a line no peer holds.
The response grants Exclusive.
Core 0 increments the counter.
E→M occurs without invalidation traffic.

MESI avoids the upgrade that MSI would require.

Common mistakes

Exclusive means locked against all future requests.
E contains newer data than memory.
All processors literally expose MESI states to software.

MOESI then avoids writing dirty data all the way to memory when it can remain owned and shared.

MOESI and owned dirty sharing

MOESI adds Owned so a dirty line can be shared without immediately updating memory. One cache remains responsible for the newest dirty value while other caches hold read-only shared copies.

In basic MESI teaching, a remote read of M causes the owner to provide data and make the backing level current before both copies become S. The Owned state permits the backing memory to remain stale: one cache carries responsibility for eventually writing back while multiple readers use the supplied value.

Owned is dirty and read-only from the local processor's permission perspective. A store still needs unique ownership and invalidation of sharers. The O state shifts where the authoritative value lives; it does not permit multiple writers.

Other protocols add Forward states or encode ownership in a directory rather than using exactly MOESI. The enduring questions are who has read permission, who has write permission, which component has the newest bytes, and who must respond or write back.

Vocabulary

O: Dirty shared owner responsible for the newest value.
forwarder: A designated responder among clean sharers in some protocols.
intervention: A cache supplies data in response to another request.
write-back responsibility: Obligation to preserve dirty data on eviction.
authoritative copy: The place holding the most recent value.

Dirty read sharing

Core 0 owns M with x=9; memory still has 4.
Core 1 reads x.
Core 0 supplies 9 and changes M→O.
Core 1 receives S while memory may remain 4.

Readers agree on 9 and the Owned cache remains responsible for eventual write-back.

Common mistakes

Owned grants write permission.
Memory always has the latest coherent value.
MOESI is automatically faster for every workload.

States need a communication organization; start with broadcast snooping.

Snooping and the shared ordering point

A snooping system makes relevant caches observe coherence requests, often through a broadcast medium or filtered interconnect. A shared ordering point serializes conflicts so controllers agree which request won.

On a simple bus, every cache snoops every coherent request and checks its tags. Broadcast naturally provides discovery and a common order, making it excellent for teaching and modest core counts.

Snoops consume tag bandwidth, interconnect bandwidth, and energy even when most probes miss. Duplicate tags, multiported structures, snoop queues, and filters reduce interference, but broadcast fanout becomes a scaling limit.

Atomicity of a state transition depends on the transaction protocol, not on messages teleporting instantly. A requester may wait for all required responses or invalidation acknowledgements before treating ownership as granted.

Vocabulary

snoop: A coherence lookup triggered by another agent's request.
broadcast: Send a request to all potential holders.
ordering point: The component that serializes conflicting transactions.
snoop filter: Metadata used to avoid probes to definite non-holders.
acknowledgement: Evidence that a required state change completed.

Two simultaneous writers

Core 0 and Core 1 request x exclusively.
The bus orders Core 0's request first.
Core 0 receives invalidation acknowledgements and writes.
Core 1's later request takes ownership from Core 0.

The requests serialize; both writers never own the line at once.

Common mistakes

All requests occur simultaneously because cores are parallel.
A snoop hit always returns data.
Sending an invalidate is equivalent to receiving all acknowledgements.

Large systems replace global broadcast with directories and targeted probes.

Directory coherence and scalable fabrics

A directory or home node records likely sharers and an owner for each block. Requests go to the home, which sends targeted probes and collects acknowledgements instead of broadcasting everywhere.

Directory metadata can be a full bit vector, a sparse list, coarse region information, or a compressed representation. Precision costs storage; approximation can cause harmless extra probes. The directory is about locating permissions, not necessarily storing the data itself.

A home node serializes requests for its address range. A read can be forwarded to a dirty owner; a write sends invalidations only to recorded sharers. Network messages may travel independently, so transient states and race handling become central.

NUMA placement and directory placement interact. A remote home or owner adds hops even when DRAM is not accessed. Modern coherent meshes therefore require topology-aware performance reasoning rather than the simple phrase 'cache hit.'

Vocabulary

directory: Metadata tracking sharers and ownership.
home node: Ordering authority for an address region.
targeted probe: Snoop sent only to a possible holder.
sharer vector: Bits identifying caching agents.
transient state: Controller state while messages are outstanding.

Eight-core write

Directory records Core 1 and Core 6 as sharers.
Core 3 asks the home for ownership.
The home probes only Cores 1 and 6.
After both acknowledgements, Core 3 receives write permission.

Targeted invalidations replace an eight-way broadcast.

Common mistakes

Directory coherence means no snoops exist.
The directory always contains the newest data.
A directory entry can never be imprecise.

Now place protocol behavior inside a real multi-level hierarchy with inclusive and non-inclusive policies.

Coherence across L1, L2, LLC, and clusters

A hierarchy may maintain coherence at private-cache, cluster, and system levels. Inclusive, exclusive, and non-inclusive policies change where data may reside and how the system locates or invalidates inner copies.

In an inclusive hierarchy, an inner-cache line implies a representation at an outer level; evicting the outer line may require back-invalidating inner copies. Inclusion can simplify snoop filtering but consumes capacity with duplicated data.

An exclusive hierarchy tries to avoid duplication across levels, while non-inclusive policies make neither promise. These replacement policies are different from MESI's Exclusive permission state—one of the most damaging vocabulary collisions in cache discussions.

A cluster can hide private L1 activity behind a shared L2 and participate in system coherence through one interface. The exact point of coherence and whether instruction caches are automatically coherent with data writes are architecture-specific.

Vocabulary

inclusive: Inner contents are represented in an outer cache.
exclusive hierarchy: Data is preferentially held at only one cache level.
non-inclusive: No strict inclusion or exclusion guarantee.
back-invalidation: Outer eviction invalidates dependent inner copies.
point of coherence: Architecture-defined point where observers agree.

Inclusive LLC eviction

Core 0 holds line A in L1.
The inclusive LLC also tracks A.
LLC replacement selects A's entry.
The hierarchy invalidates Core 0's L1 copy before removing the LLC entry.

Replacement can cause coherence-visible invalidations even without another core writing.

Common mistakes

MESI Exclusive means an exclusive cache hierarchy.
Every L1 talks directly to every other L1.
Instruction and data caches are universally self-coherent.

With the hierarchy in place, separate coherence from the ordering rules software actually programs against.

Coherence is not memory consistency

Coherence constrains observations of one address; a memory consistency model constrains relationships among operations to different addresses. Compiler transformations, store buffers, speculation, and interconnect ordering mean correct synchronization must use language atomics and architecture-defined ordering.

Consider data=42 followed by ready=1 on one core. Another core reads ready and then data. Per-location coherence can be perfect while the second core observes ready=1 and stale data unless the programming model creates a happens-before relationship.

Compiler order and hardware order are separate layers. Volatile in C generally controls compiler access to an object but does not create inter-thread synchronization. C11/C++ atomics express both atomicity and ordering; the compiler maps them to instructions and barriers appropriate for the target.

Sequential consistency is an intuitive global interleaving, but many architectures and language operations permit weaker behavior for performance. Acquire/release is often enough for message passing: release publishes earlier writes and acquire prevents later reads from moving before observing the publication.

Vocabulary

memory model: Rules for values and order observable by concurrent agents.
happens-before: Language-level relation making effects visible in a defined order.
acquire: Ordering that keeps following operations after a synchronization read.
release: Ordering that keeps preceding operations before a synchronization write.
volatile: A language qualifier that is not a general thread-synchronization primitive.

Publish a payload

Producer writes payload fields normally.
Producer stores ready with release semantics.
Consumer loads ready with acquire semantics.
After observing ready, consumer may read the published payload.

Coherence moves each line; acquire/release supplies the cross-location ordering.

Common mistakes

Coherence implies sequential consistency.
Volatile makes a data race safe.
A fence flushes every cache to DRAM.

Atomics exploit exclusive ownership but must also satisfy the language memory model.

Atomics, locks, reservations, and barriers

Atomic read-modify-write operations combine observation and update without an intervening writer. Coherence obtains exclusive line permission, while the ISA and language memory model define atomicity and ordering. Locks then build higher-level exclusion from those primitives.

Compare-exchange, fetch-add, and swap typically require the cache line in a writable ownership state. Heavy contention therefore makes ownership bounce among cores. The instruction is atomic, but its performance depends on the same coherence traffic studied in MESI.

Load-linked/store-conditional or reservation-based sequences may fail spuriously when another agent touches the reservation granule. Correct loops retry. Compare-exchange loops likewise handle failure and must choose success and failure memory orders correctly.

A barrier orders classes of memory operations; it is not a mutual-exclusion lock and does not repair a non-atomic data race. Prefer language-level atomics in application code, operating-system synchronization APIs in kernels, and documented DMA/MMIO primitives in drivers.

Vocabulary

RMW: Atomic read-modify-write operation.
CAS: Compare-and-swap/exchange primitive.
LL/SC: Reservation-based atomic update pair.
contention: Agents repeatedly competing for the same ownership.
fence: An ordering constraint, not a cache-wide write-back command.

Contended fetch-add

Core 0 obtains M and increments counter.
Core 1's atomic requests ownership.
Core 0 supplies/invalidates its copy.
Repeated alternation causes line ping-pong.

Every increment can be logically correct yet physically expensive.

Common mistakes

Atomic means one CPU instruction on every architecture.
A barrier makes a non-atomic increment atomic.
Lock-free means contention-free or wait-free.

The same line-granularity ownership transfer causes false sharing even when variables are logically independent.

True sharing, false sharing, and line ping-pong

False sharing occurs when threads modify different objects that occupy the same coherence line. There is no logical communication, but each store invalidates the other core's entire line, causing ownership ping-pong.

True sharing means threads intentionally communicate through the same data. False sharing means their distinct data merely shares a hardware line. Both can create contested-line traffic, so source code and measured addresses are needed to distinguish them.

Padding or alignment can place hot writable fields on separate lines, but blindly padding everything increases footprint, cache misses, and memory bandwidth. Better fixes often privatize counters, batch updates, partition ownership, or reduce write frequency.

Measurement matters. Hardware counters and profilers can identify cache-to-cache transfers or modified-line hits, but event names and interpretation are microarchitecture-specific. Confirm structure layout, allocation alignment, thread placement, and actual hot instructions.

Vocabulary

false sharing: Independent writable data sharing a coherence line.
true sharing: Intentional communication through shared data.
ping-pong: Repeated ownership migration between agents.
padding: Unused bytes inserted to separate objects.
privatization: Give each worker local data and combine later.

Two counters

Counters a and b are adjacent eight-byte fields.
Both land in one 64-byte line.
Core 0 repeatedly writes a; Core 1 repeatedly writes b.
Ownership moves despite no logical dependency.

Separating or privatizing the counters removes coherence contention, subject to measurement.

Common mistakes

Any shared cache line is false sharing.
Alignment alone guarantees two objects are on different lines.
Padding is free and universally best.

CPU caches are only part of the system; DMA introduces agents that may sit outside the coherent domain.

DMA, I/O coherence, and cache maintenance

Only if the platform and mapping place the device in the required coherence domain. Otherwise software must use the DMA API to transfer ownership and perform clean, invalidate, or synchronization operations in the correct direction.

A CPU may have dirty transmit data that has not reached memory, while a device reads memory directly. Conversely, a device can write receive data while the CPU retains a stale cache copy. On non-coherent systems, clean/write-back and invalidate operations bridge those views.

Linux distinguishes coherent DMA mappings from streaming mappings. Coherent mapping means CPU and device do not require explicit cache flushing for mutual visibility, but it does not remove the need for memory barriers that order descriptor fields before a valid bit or doorbell.

DMA direction and ownership are correctness information. The portable rule is to use the platform DMA API rather than inventing cache instructions from application code. Buffers should avoid sharing cache lines with unrelated CPU-written data when maintenance works at line granularity.

Vocabulary

DMA: A device accesses memory without CPU load/store copying.
clean: Write dirty cache data toward the point of coherence.
invalidate: Discard a cached copy so a later read refetches.
coherent mapping: Mapping whose visibility contract avoids explicit cache sync.
streaming mapping: Transfer-oriented mapping with explicit ownership synchronization.

Transmit descriptor

CPU fills address and length fields.
A DMA write barrier orders those stores.
CPU sets the ownership/valid field.
CPU rings the device doorbell using the platform I/O primitive.

Cache visibility and operation ordering are both satisfied; neither substitutes for the other.

Common mistakes

PCIe guarantees every device is cache coherent.
Coherent DMA memory needs no barriers.
Flush always means invalidate and write-back together.

Heterogeneous and NUMA systems enlarge both the coherence domain and the cost topology.

NUMA, chiplets, GPUs, and coherent accelerators

No. Coherence provides a functional visibility contract, while NUMA topology determines latency, bandwidth, hop count, and contention. A remote coherent cache-to-cache transfer can be far slower than a local hit.

In a multi-socket or chiplet system, an address has a home and memory placement. Thread migration can turn local accesses into remote ones, and a dirty owner on another node can add further interconnect hops. First-touch allocation and affinity therefore affect coherence performance.

CPU–GPU and accelerator systems offer different levels: non-coherent sharing, I/O coherence, full hardware coherence, and sometimes shared virtual addressing. These capabilities are independent; sharing an address space does not automatically make caches coherent.

Coherent interconnect standards and on-chip fabrics reduce explicit copying, but fine-grained shared writes may still be a poor algorithm because line migration and synchronization dominate. Partitioning and bulk handoff remain valuable.

Vocabulary

NUMA: Memory access cost depends on topology and placement.
home: Node responsible for ordering/address metadata.
affinity: Constraint keeping work on selected processors.
I/O coherence: Limited device participation in system coherence.
shared virtual memory: Agents use compatible virtual-address mappings; not itself coherence.

Remote ownership

Thread allocates a counter on socket 0.
Scheduler runs its writer on socket 1.
A reader remains on socket 0.
The line and synchronization traffic cross the socket link repeatedly.

The program is coherent and correct but topology makes it slow.

Common mistakes

Coherent memory is uniform memory.
Shared virtual addresses imply shared coherent caches.
A cache hit has one universal latency.

Performance engineering needs evidence that distinguishes capacity misses, contention, and protocol traffic.

Measure before fixing: counters and experiments

Use controlled experiments, source/layout inspection, affinity, and platform-specific performance counters. Compare throughput and tail latency while changing sharing, placement, and padding one variable at a time.

A high cache-miss count does not uniquely mean coherence trouble. Capacity, conflict, compulsory, TLB, prefetch, and coherence misses overlap in symptoms. Events such as cache-to-cache transfers or modified-line responses are stronger clues but require the processor's performance-monitoring documentation.

Build a hypothesis: identify a line, writers, expected ownership movement, and predicted counter change. Pin threads, warm up, run long enough, report variance, and preserve compiler optimization. Then alter layout or ownership and see whether both performance and relevant events move as predicted.

Tail latency can reveal bursts hidden by averages. Also measure the cost of the cure: padding increases working set, batching increases delay, locks can convoy, and thread affinity can harm load balance.

Vocabulary

PMU: Hardware performance monitoring unit.
HITM: Intel-family term/event concept for a hit involving a modified peer copy; exact events vary.
affinity: Controlled processor placement for reproducible topology.
baseline: Unmodified measurement used for comparison.
tail latency: Slow-percentile behavior such as p99.

Evidence chain

Measure two adjacent counters with pinned threads.
Record throughput and platform-specific contested-line events.
Separate counters by a verified line boundary.
Repeat and compare confidence intervals and event deltas.

A matching speedup and traffic reduction support the false-sharing diagnosis.

Common mistakes

One benchmark run is evidence.
LLC misses prove false sharing.
A profiler event name has identical meaning on every CPU.

The final step is protocol verification: prove invariants across races, not just friendly traces.

Verification, transient races, and system design

Designers state invariants, model stable and transient states, generate concurrent message interleavings, assert safety and progress, and verify at unit, fabric, and software-litmus levels. Passing ordinary workloads is not proof.

Safety properties include never granting two writable copies, never losing the latest value, and never letting incompatible aliases coexist. Liveness asks whether requests eventually complete under fair service rather than deadlocking, livelocking, or starving.

Transient races dominate verification: an eviction crosses an incoming probe, two requesters race, a response is retried, or a dirty owner changes while a forward is in flight. Controllers need transaction identifiers, dependency rules, bounded resources, and recovery behavior.

Litmus tests explore allowed software observations under a memory model; they complement but do not replace protocol assertions. End-to-end validation spans compiler mappings, ISA ordering, cache controllers, coherent interconnect, memory controller, IOMMU, and devices.

Vocabulary

safety: A bad state is never reached.
liveness: A requested action eventually makes progress.
litmus test: Small concurrent program probing allowed observations.
model checking: Systematic state/interleaving exploration.
deadlock: A dependency cycle prevents progress.

Race audit

Core 0 evicts a Modified line.
Core 1 concurrently requests ownership.
Model both message orders and delayed acknowledgements.
Assert one newest value survives and exactly one writer emerges.

The transient protocol, not merely the MESI picture, determines correctness.

Common mistakes

Random benchmarks prove protocol correctness.
Stable states describe every controller cycle.
Coherence verification alone proves the language memory model implementation.

You can now move from a source-level shared variable to lines, states, messages, topology, ordering, devices, measurement, and proof.

Walkthrough: MESI: two cores, one line

One cache line chased by two cores: cold read, silent E→M upgrade, snoop downgrade with flush, BusUpgr from Shared, and a write-back on evict. This is the canonical interview trace.

Walkthrough: MOESI: dirty sharing

The Owned state lets a dirty line be read-shared without writing memory. Watch memory stay stale while readers get correct data straight from the owner.

Walkthrough: MESI: false sharing ping-pong

Two unrelated variables, one 64-byte line. Cores alternate writes to different words and still invalidate each other every time — coherence works on lines, not variables.

The mental model

Cache address mapping is division by powers of two. The low log2(line size) bits of an address pick the byte inside a cache line, the next log2(set count) bits pick which set the block lands in, and the remaining top bits are the tag that identifies which memory block actually lives there.

Tag/set/offset problems are a staple of architecture exams and interviews, and the same slicing shows up in real firmware when you reason about cache maintenance (clean/invalidate by address), DMA buffer alignment, and why two buffers that map to the same set evict each other.

Core rules

Offset bits come from the line size

offset = log2(line size in bytes). A 64-byte line needs 6 offset bits, because 2^6 = 64 bytes must be addressable inside one line.

Sets divide lines by ways

sets = cache size / (line size x ways). Lines per way = cache / line; the associativity splits those lines into groups of 'ways' slots each. Forgetting the ways is the most common exam error.

Set bits come from the set count

set bits = log2(sets). Direct mapped is just ways = 1, so sets = cache / line.

The tag is whatever is left

tag bits = address bits - set bits - offset bits. The three fields are disjoint slices that must sum to the address width.

All sizes must be powers of two

Cache size, line size, and ways must be powers of two for the address to slice cleanly. If a problem gives a non-power-of-two size, the binary slicing breaks down.

Workflow

Write down address bits, cache size, line size, and ways.
Compute offset bits = log2(line size).
Compute lines = cache size / line size, then sets = lines / ways.
Compute set bits = log2(sets).
Compute tag bits = address bits - set bits - offset bits.
For a concrete address: block = floor(address / line), set = block mod sets, tag = floor(block / sets).

Worked example

16 KiB, 64 B lines, 4-way, 32-bit addresses

offset bits = log2(64)          = 6
lines       = 16384 / 64       = 256
sets        = 256 / 4 ways     = 64
set bits    = log2(64)         = 6
tag bits    = 32 - 6 - 6       = 20

// address 0x00003E84
// block = 0x3E84 / 64 = 250
// set   = 250 % 64    = 58
// tag   = 250 / 64    = 3

Each field width is a log2 of a count, and the fields must add back to 32 bits: 20 + 6 + 6 = 32. The tag value, not the address, is what gets compared against the tags stored in the set.

Vocabulary

cache line: The fixed-size block (e.g. 64 B) moved between memory and cache as one unit.
set: A group of 'ways' line slots; an address maps to exactly one set.
tag: The high address bits stored with each line to identify which memory block it holds.
associativity: How many line slots each set has; 1 way is direct mapped.
block number: floor(address / line size) - which memory block the address belongs to.

Cache Mapping: Why the Same Loop Can Be Ten Times Slower

A cache holds a small subset of memory close to the processor, and where a given address is allowed to sit inside it is the mapping. That choice - direct-mapped, set-associative or fully associative - decides which access patterns are fast and which collide. The reason it matters to a programmer is that two loops with identical instruction counts can differ by an order of magnitude purely because one keeps hitting the same set.

How it is built

An address is split into three fields: an offset within the line, an index selecting the set, and a tag stored alongside the data to confirm which address is actually present.
Direct-mapped gives each address exactly one possible location. It is the simplest and fastest to look up, and two hot addresses mapping to the same line evict each other repeatedly - conflict misses.
Set-associative gives each address a set of N possible locations. Higher associativity reduces conflicts at the cost of comparing N tags per access, and four or eight ways is the usual compromise.
Fully associative allows any address anywhere, so conflict misses vanish and every line's tag must be compared. It is only practical for small structures such as a TLB.
Misses come in three kinds: compulsory on first touch, capacity when the working set exceeds the cache, and conflict when the mapping collides despite space being free. Only the third is fixed by changing associativity or layout.
A cache line is the unit of transfer, typically 32 or 64 bytes. Touching one byte fetches the whole line, which is why sequential access is fast and why a stride equal to the line size wastes almost all of the bandwidth.

Design procedure

Find the cache's size, line length and associativity for the target part. Everything else follows from those three numbers.
Compute the stride that maps to the same set: cache size divided by associativity. Any array traversal with that stride collides on every access.
Traverse arrays in the order they are stored - row-major in C - so each fetched line is fully used before the next is needed.
Watch for power-of-two strides in two-dimensional data, which is exactly the pattern that maps everything to one set. Padding the row length by one element breaks the alignment and can transform the runtime.
Group fields used together into the same structure so one line fetch serves them, rather than spreading them across several objects.
Measure rather than assume. A profiler's cache-miss counters distinguish a capacity problem from a conflict problem, and the fixes are different.

Key terms

Cache line: The unit of transfer, typically 32 or 64 bytes. One byte fetches all of it.
Tag / index / offset: The three fields an address is split into for lookup.
Direct-mapped: One possible location per address. Fast, and prone to conflict misses.
N-way set associative: N possible locations. Fewer conflicts, N tag comparisons.
Compulsory miss: First touch of a line. Unavoidable.
Capacity miss: Working set larger than the cache.
Conflict miss: Collision despite free space. The only kind layout can fix.
Critical stride: Cache size divided by associativity. The stride that collides every time.

Worked example

Summing a 1024x1024 array of 32-bit values column by column on a 32 kB 4-way cache with 64-byte lines: the critical stride is 8 kB, and a column step is 4 kB, so every few accesses map to the same set. Each fetches a 64-byte line and uses four bytes of it before eviction. Traversing row by row instead uses all sixteen values in every line - the same instruction count, one sixteenth of the memory traffic, and typically ten times faster. Nothing about the arithmetic changed.

Common pitfalls

More in Foundations

PointersComplete visual pointer laboratory: addresses, dereferencing, pointer arithmetic, arrays and decay, double pointers, dynamic memory, function pointers, const/volatile, MMIO, lifetime bugs — with a step-through memory simulator, 100+ interview questions and a mastery exam.
Computer Systems 0 → 100A beginner-first path from what a computer is through bits, CPUs, addresses, memory hierarchy, SRAM, DRAM, ROM, flash, SSDs, buses, PCIe, SATA, AHCI, NVMe, M.2, boot and performance—with comparisons and interview practice.
From Power-On to main()What runs before main(): the Cortex-M reset sequence that gives C the machine it assumes, the linker script that decides where every section lives and why .data has two addresses, the four build stages and which one your error came from, and the order to work through a debug probe that will not connect.
Number RepresentationBases and why hex is the one you read, two's complement and the asymmetry that makes abs(INT_MIN) undefined, the bit-manipulation idioms with the edge case in each, and byte order - which matters in exactly three places and in none of the arithmetic.
FoundationsComputer systems from first principles—memory, storage and interconnects through cache coherence, ordering, atomics and DMA—then the firmware foundations of numbers, linking, interrupts and pointers.