Why Do Direct-Mapped Caches Miss on Cache-Sized Strides?
Direct-mapped caches experience frequent conflict misses when memory access strides match the cache size because every accessed address maps to the exact same cache line. Even though the rest of the cache remains empty, each new memory access evicts the previous block, forcing repeated trips to main memory. This article explains the address mapping mechanism behind this behavior, walks through a concrete example, and discusses how hardware and software strategies mitigate the problem.
How Direct-Mapped Cache Addressing Works
In a direct-mapped cache, each memory block can reside in only one specific cache line. The hardware determines this location by dividing the memory address into three fields: the block offset, the index, and the tag.
For a cache with \(N\) lines and a block size of \(B\) bytes, the total cache capacity is \(C = N \times B\) bytes. Given a byte address \(A\), the block address is:
\[\text{Block Address} = \left\lfloor \frac{A}{B} \right\rfloor\]
The cache index, which selects the specific cache line, is computed using modulo arithmetic:
\[\text{Index} = \left\lfloor \frac{A}{B} \right\rfloor \bmod N\]
Because \(N\) is almost always a power of two in classical computing, this modulo operation simply extracts the \(\log_2(N)\) bits immediately above the block offset bits.
Why a Cache-Sized Stride Causes Conflict Misses
Suppose a program accesses memory with a stride \(S\) equal to the cache size \(C = N \times B\). Starting from an initial address \(A_0\), the sequence of accessed addresses is:
\[A_k = A_0 + k \cdot C = A_0 + k \cdot N \cdot B\]
for \(k = 0, 1, 2, \dots\)
When we compute the cache index for any address \(A_k\) in this sequence, we get:
\[\text{Index}(A_k) = \left\lfloor \frac{A_0 + k \cdot N \cdot B}{B} \right\rfloor \bmod N = \left( \left\lfloor \frac{A_0}{B} \right\rfloor + k \cdot N \right) \bmod N\]
Since \(k \cdot N\) is an exact multiple of \(N\), the modulo operation eliminates it completely:
\[\text{Index}(A_k) = \left\lfloor \frac{A_0}{B} \right\rfloor \bmod N = \text{Index}(A_0)\]
Every single access in the stride lands on the exact same cache index. Because a direct-mapped cache has only one slot per index, each new access has a different tag and must evict the block currently stored there. If the program loops over these addresses, every access results in a conflict miss, a phenomenon known as cache thrashing.
A Concrete Example
Consider a small 4 KB direct-mapped cache (\(C = 4096\) bytes) with 64-byte blocks (\(B = 64\) bytes). This gives \(N = 64\) cache lines, indexed from \(0\) to \(63\).
If a program reads a 4-byte integer at byte addresses \(0\), \(4096\), \(8192\), and \(12288\), the stride is \(S = 4096\) bytes, matching the cache size:
- Address \(0\): Block \(0 \bmod 64 = \text{Index } 0\)
- Address \(4096\): Block \(64 \bmod 64 = \text{Index } 0\)
- Address \(8192\): Block \(128 \bmod 64 = \text{Index } 0\)
- Address \(12288\): Block \(192 \bmod 64 = \text{Index } 0\)
All four accesses compete for Index \(0\), while Indices \(1\) through \(63\) sit completely unused.
Mitigating Stride-Induced Conflict Misses
Both hardware architects and software developers use specific techniques to avoid this bottleneck:
- Set-associative caches: Allowing each index to hold \(W\) blocks (a \(W\)-way set-associative cache) lets up to \(W\) addresses with the same index coexist without eviction.
- Array padding: Programmers can pad data structures or matrix rows so that their dimensions are not powers of two, breaking the alignment with the cache size.
- Loop tiling (blocking): Restructuring loops to process smaller contiguous chunks of data ensures that spatial locality is exploited before moving to the next strided region.