Where a cache line can live

Prerequisites: Addresses, cache lines, and the memory hierarchy.

Learning objectives

• Decompose an address into tag, index, and offset.
• Trace conflicts under stated replacement assumptions.
• Explain false sharing separately from data races.

Placement is a calculation

A cache stores aligned blocks called lines. Consider a deliberately small byte-addressed cache with 64 bytes of data capacity, 16-byte lines, and direct mapping. It has four slots. An address divides into a four-bit byte offset, a two-bit slot index, and a remaining tag. For an integer address a, the block number is a // 16, the index is that block number modulo four, and the tag is the block number divided by four with truncation.

Addresses 0 and 64 have different block numbers but both map to index zero. Starting empty, the access sequence 0, 64, 0, 64 misses every time because each line evicts the other. The working set is only 32 bytes, smaller than total capacity. These are placement conflicts, not evidence that every byte of the cache is occupied.

A two-way cache of the same capacity has two sets, each containing two slots. Both blocks still map to the same set, but they can coexist. For this sequence, the first accesses miss and the later accesses hit. If a third conflicting block appears, the replacement policy becomes relevant. Always state the associativity, line size, capacity, and initial contents before reporting a miss count.

A write changes more than one copy

With multiple cores, private caches may hold copies of the same physical line. A coherence protocol coordinates permissions and values for those copies. A simplified invalidation protocol lets several caches read a shared line, but a writer must obtain exclusive permission and invalidate other copies before making its write visible according to the protocol.

Suppose two threads update different eight-byte counters located in the same 64-byte line. Their accesses do not necessarily form a language-level data race because they touch different objects. Yet the cache line can repeatedly move between cores as each requests write ownership. This is false sharing: the coherence granularity is larger than the logical data being shared. Padding or reorganizing data may help, but increases footprint and can harm locality elsewhere.

Separate the guarantees

Coherence describes coordination for an individual location or line. A memory consistency model constrains ordering across operations, potentially at several addresses. A coherent cache does not by itself make an unsynchronized program correct. Similarly, a cache hit can still wait for permission, an outstanding miss, or a resource conflict. Use placement arithmetic to predict a specific access pattern, then measure a representative workload before attributing its total runtime to cache capacity alone.

Primary reading

• Caches and the Memory Hierarchy (MIT OpenCourseWare, Computation Structures).
• Parallel Processing (MIT OpenCourseWare, Computation Structures).

Practice problem

For a direct-mapped cache with eight 32-byte lines, compute the block number and index for byte addresses 0, 256, and 288. Starting empty, count misses for 0, 256, 0, 288, 256. Explain whether doubling the number of ways while preserving total capacity necessarily removes every possible conflict.

Worked solution

The cache has 256 bytes of data capacity. Address 0 is block 0 at index 0. Address 256 is block 8 at index 0. Address 288 is block 9 at index 1. The first access to 0 misses; 256 misses and evicts it; the next 0 misses and evicts 256; 288 misses in index 1; and the final 256 misses in index 0. There are five misses. A two-way organization can keep two competing blocks in one set, but preserves only eight total lines and reduces the number of sets to four. Three or more blocks mapping to the same set can still conflict. Associativity changes placement freedom; it does not provide unlimited storage or eliminate replacement decisions.

Check your understanding

Why can a 32-byte working set repeatedly miss in the 64-byte direct-mapped example?

• Every cache line holds only one bit.
• The two blocks require the same slot.
• Capacity misses require a full cache.
• The addresses are always invalid.

Explanation

Direct mapping permits only one destination for each block, so conflicts can occur below total capacity.

Two cores update separate counters in one cache line. What can padding improve?

• It proves all synchronization correct.
• It can reduce false-sharing ownership transfers.
• It guarantees every memory access is a hit.
• It changes virtual addresses into physical addresses.

Explanation

Separating counters into different lines can reduce coherence contention, without replacing synchronization requirements.

Primary reading

• Caches and the Memory Hierarchy: MIT OpenCourseWare, Computation Structures
• Parallel Processing: MIT OpenCourseWare, Computation Structures

Open the study and save your work →