--- title: Cache Memories and Direct Mapping module: The Memory Hierarchy moduleNumber: 6 lessonNumber: 3 order: 603 summary: > A cache is fast SRAM that holds copies of recently-used blocks of main memory. We fix its organization — S sets, E lines per set, B bytes per block — and the way it dissects an address into tag, set index, and block offset, worked bit by bit on a concrete 16-byte cache. Then we run the direct-mapped (E=1) access algorithm end to end on a seven-access trace: index to a set, compare the tag, hit or miss, evict. Cold and conflict misses fall out of the structure, and a two-array ping-pong shows conflict thrashing and its padding fix. topics: [The Memory Hierarchy] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §6 The Memory Hierarchy" - book: Bistriceanu ref: "Computer Architecture Notes — §7–9 The Memory Hierarchy / The Cache / Main Memory" --- A **cache** is the hardware that turns [locality](/computer-architecture/memory-hierarchy/locality) into speed. It is a small, fast SRAM memory sitting between the processor and main memory, holding copies of **blocks** of DRAM that the program has used recently. On each memory reference the processor checks the cache first; if the data is there — a **hit** — it comes back in a cycle or two, and the slow DRAM is never touched. The work is entirely in the bookkeeping: given an address, **where in the cache could this block be, and is it actually there?** This lesson answers both questions for the simplest organization, the **direct-mapped** cache, and the answer is a precise slicing of the address. ## Cache geometry: S, E, B A cache is organized as a two-dimensional array of **cache lines**. The lines are grouped into **sets**, and the parameters are fixed by powers of two. - There are $S = 2^s$ **sets**. - Each set holds $E$ **lines** (also called ways). - Each line stores one **block** of $B = 2^b$ contiguous bytes of memory, plus a **valid bit** (is this line holding real data?) and a **tag** (which block of memory is it?). The total data capacity is the product of the three: $$ C = S \times E \times B = 2^s \cdot E \cdot 2^b. $$ Each line carries overhead the capacity figure ignores: the valid bit and the tag are needed to identify and validate the block, but they do not count toward $C$. > **Definition (Cache line / block / set).** A **block** is a fixed run of $B$ > contiguous bytes — the unit of transfer between cache and memory. A **line** is a > cache slot that holds one block together with a valid bit and a tag. A **set** is > a group of $E$ lines among which a given block is allowed to reside. ## Slicing the address Now the central idea. Because $B = 2^b$ and $S = 2^s$ are powers of two, the bits of a memory address split cleanly into three contiguous fields, read from the **low-order** end up: - The low $b$ bits are the **block offset**: which byte _within_ the block. With $B = 2^b$ bytes per block, $b = \log_2 B$ bits name a byte inside it. - The next $s$ bits are the **set index**: which set the block maps to. With $S = 2^s$ sets, $s = \log_2 S$ bits choose one. - The remaining high bits are the **tag**: they identify which of the many memory blocks that map to this set is actually stored. If the address is $m$ bits wide, the tag is $t = m - s - b$ bits. $$ % caption: An m-bit address splits into three fields: the high t = m - s - b tag % caption: bits, then s = log2(S) set-index bits, then the low b = log2(B) block- % caption: offset bits. The offset picks a byte; the index picks a set; the tag % caption: identifies the block. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} % three f\/ield boxes, widths ref\/lect bit counts \node[draw, fill=acc!8, minimum width=46mm, minimum height=8mm, inner sep=0pt] (tag) at (0,0) {tag}; \node[draw, minimum width=26mm, minimum height=8mm, inner sep=0pt, anchor=west] (idx) at (tag.east) {set index}; \node[draw, minimum width=22mm, minimum height=8mm, inner sep=0pt, anchor=west] (off) at (idx.east) {block of\/fset}; % bit positions: high bit at far left, bit 0 at far right \node[anchor=south east] at (tag.north west) {bit m-1}; \node[anchor=south west] at (off.south east |- off.north) {}; \node[anchor=south west] at (off.north east) {bit $0$}; % width brackets below \draw[<->] (tag.south west) ++(0,-0.25) -- ($(tag.south east)+(0,-0.25)$) node[midway,below] {$t$ bits}; \draw[<->] (idx.south west) ++(0,-0.25) -- ($(idx.south east)+(0,-0.25)$) node[midway,below] {$s$ bits}; \draw[<->] (off.south west) ++(0,-0.25) -- ($(off.south east)+(0,-0.25)$) node[midway,below] {$b$ bits}; \end{tikzpicture} $$ Stated plainly: **the offset locates a byte in a block, the index locates a set, and the tag disambiguates which block is in that set.** Adjacent addresses share a tag and set index and differ only in offset, and that is why a single block captures spatial locality — a stride-1 walk stays inside one block until the offset overflows. Why _these_ bits and not some other slicing? The choice is deliberate, and it is what makes spatial locality land in one place. The low bits change fastest as you walk memory, so putting the **offset** there means consecutive addresses stay in one block — the whole point of a block. The **index** sits just above the offset, so consecutive _blocks_ fall into consecutive sets and spread across the cache instead of piling into one. If the index were taken from the high bits instead, a stride-1 sweep would hammer a single set while the rest of the cache sat empty. The address split is the mechanism that maps the program's locality onto the cache's geometry. ### A concrete geometry, worked Fix one tiny cache for the rest of this lesson: $S = 4$ sets, $E = 1$ line per set, $B = 4$ bytes per block, on 6-bit addresses (a 64-byte memory). Then $b = 2$, $s = 2$, and $t = 6 - 2 - 2 = 2$: the low two bits pick a byte, the middle two pick a set, and the top two are the tag. The cache holds $C = 4 \times 1 \times 4 = 16$ bytes. Take the address `0x2C` $= 44 = \mathtt{101100}_2$ and read the fields off: $$ % caption: The address 0x2C = 101100 on the worked geometry (S = 4, B = 4, 6-bit % caption: addresses): the drawn strokes separate the fields. Tag = 10 (block group 2), % caption: set index = 11 (set 3), block offset = 00 (byte 0 of the block). \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.75,0) {0x2C =}; % bit cells \foreach \i/\bit in {0/1,1/0,2/1,3/1,4/0,5/0} \node[draw, minimum size=7.5mm, inner sep=0pt] at (\i*0.75,0) {\bit}; % bit indices above \foreach \i/\n in {0/5,1/4,2/3,3/2,4/1,5/0} \node[anchor=south,black] at (\i*0.75,0.42) {\n}; % drawn f\/ield separator strokes \draw[acc, very thick] (1.125,-0.62) -- (1.125,0.62); \draw[acc, very thick] (2.625,-0.62) -- (2.625,0.62); % f\/ield brackets and decoded values below \draw[<->] (-0.32,-0.62) -- (1.05,-0.62); \node[anchor=north] at (0.37,-0.72) {tag = 2}; \draw[<->] (1.2,-0.62) -- (2.55,-0.62); \node[anchor=north] at (1.87,-0.72) {set = 3}; \draw[<->] (2.7,-0.62) -- (4.07,-0.62); \node[anchor=north] at (3.38,-0.72) {byte = 0}; \end{tikzpicture} $$ So address `0x2C` refers to byte 0 of the block that lives (if present) in set 3, and that block is legitimate only if set 3's stored tag equals 2. The 64-byte memory holds 16 blocks; with 4 sets, exactly $2^t = 4$ of them map to each set, one per tag value, and the tag is what tells them apart. One more example. Take `0x17` $= 23 = \mathtt{010111}_2$. The low two bits `11` are offset 3; the middle two `01` are set 1; the top two `01` are tag 1. So byte 23 is byte 3 of the block occupying set 1 with tag 1 — and indeed block number $\lfloor 23/4 \rfloor = 5$, whose four bytes are 20–23, all sharing set 1 and tag 1. The arithmetic guarantees that because the set index is the _middle_ bits, the sixteen memory blocks fan out across the four sets in a strict repeating cycle — blocks 0, 4, 8, 12 to set 0; blocks 1, 5, 9, 13 to set 1; and so on. Every fourth block collides in the same set — the collision pattern the trace below will exploit. $$ % caption: Which of the 16 memory blocks map to each of the 4 sets in the worked % caption: geometry. The set index is the middle address bits, so blocks fan out % caption: round-robin: set i holds blocks i, i+4, i+8, i+12 — the four that share % caption: a set and are told apart only by their tag. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} \foreach \set/\y in {0/0, 1/-0.75, 2/-1.5, 3/-2.25} { \node[anchor=east] at (-0.3,\y+0.275) {set \set}; \foreach \k/\col in {0/0,1/1,2/2,3/3} { \pgfmathtruncatemacro{\blk}{\set + 4*\k} \node[draw, fill=acc!8, minimum width=13mm, minimum height=6mm, inner sep=0pt, anchor=west] at (\k*1.55,\y) {block \blk}; } } \node[anchor=south,black] at (3.1,0.6) {four memory blocks per set (one per tag)}; \end{tikzpicture} $$ ## Direct-mapped access A **direct-mapped** cache is the special case $E = 1$: exactly **one line per set**. Each memory block therefore has a single legal home, the set its index bits name, and no choice of placement remains. That makes the lookup mechanical. To service an address the cache does three steps. 1. **Set selection.** Extract the $s$ index bits and use them to select set number $\textit{index}$. There is no search across sets: the index _is_ the set number. 2. **Line matching.** The selected set has one line. It is a **hit** if and only if that line's **valid bit is 1** _and_ its stored **tag equals** the address's tag. If either fails, it is a **miss**. 3. **Byte selection.** On a hit, use the $b$ offset bits to pick the requested byte (or word) out of the block and return it. $$ % caption: Direct-mapped access. The set-index bits select one set (set 2 here); that % caption: set's single line is a hit when its valid bit is set and its stored tag % caption: equals the address tag; the offset then selects the byte. Any mismatch is a % caption: miss that fetches the block from memory. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} % address f\/ields across the top \node[draw, fill=acc!8, minimum width=18mm, minimum height=7mm] (atag) at (0,3.4) {tag}; \node[draw, minimum width=14mm, minimum height=7mm, anchor=west] (aidx) at (atag.east) {index}; \node[draw, minimum width=14mm, minimum height=7mm, anchor=west] (aoff) at (aidx.east) {of\/fset}; % the cache: four sets, each one line drawn as three sub-boxes (v, tag, block) \foreach \i/\y in {0/1.4, 1/0.5, 2/-0.4, 3/-1.3} { \ifnum\i=2 \node[draw, fill=acc!8, minimum width=7mm, minimum height=7mm, anchor=west, inner sep=0pt] (v\i) at (0,\y) {v}; \node[draw, fill=acc!8, minimum width=13mm, minimum height=7mm, anchor=west, inner sep=0pt] (t\i) at (0.7,\y) {tag}; \node[draw, fill=acc!8, minimum width=34mm, minimum height=7mm, anchor=west, inner sep=0pt] (b\i) at (2.0,\y) {block ($B$ bytes)}; \else \node[draw, minimum width=7mm, minimum height=7mm, anchor=west, inner sep=0pt] (v\i) at (0,\y) {v}; \node[draw, minimum width=13mm, minimum height=7mm, anchor=west, inner sep=0pt] (t\i) at (0.7,\y) {tag}; \node[draw, minimum width=34mm, minimum height=7mm, anchor=west, inner sep=0pt] (b\i) at (2.0,\y) {block ($B$ bytes)}; \fi } \node[anchor=north,black] at (2.7,-1.85) {$S$ sets, one line per set}; % index selects a set: down the left channel into the highlighted line \draw[->,acc] (aidx.south) -- (aidx.south |- 0,2.5) -| (-0.7,-0.4) -- (v2.west); % address tag to the comparator, routed above everything \node[draw, circle, minimum size=8mm, inner sep=0pt] (cmp) at (7.2,2.0) {$=$}; \draw[->] (atag.north) -- (atag.north |- 0,4.3) -| (cmp.north); % stored tag of the selected line, routed right then up into the comparator \draw[->] (b2.east) -- (6.0,-0.4) -- (6.0,1.2) -- (7.2,1.2) -- (cmp.south); \draw[->] (cmp.east) -- ++(0.9,0) node[anchor=west,text=acc] {hit / miss}; % byte-select stage fed by the block and the of\/fset \node[draw, minimum width=14mm, minimum height=8mm, align=center] (bsel) at (7.6,-0.4) {byte\\select}; \draw[->] (b2.east) -- (bsel.west); \draw[->,acc] (aoff.east) -- (10.4,3.4) -- (10.4,-0.4) -- (bsel.east); \draw[->] (bsel.south) -- ++(0,-0.75) node[anchor=north,text=acc] {byte}; \end{tikzpicture} $$ When step 2 reports a miss, the cache **fetches** the entire $B$-byte block from the next level down, installs it in the (single) line of that set, overwriting whatever was there, sets the valid bit, records the tag, and then completes the access as a hit. Because the home is forced, installing the new block **evicts** the old one unconditionally. ## A trace, end to end Run the worked cache ($S = 4$, $B = 4$, 6-bit addresses, initially empty) on seven reads. Each row splits the address into tag / set / offset and applies the three-step algorithm. | # | Address | Bits (tag, set, off) | Set | Result | | --- | --- | --- | --- | --- | | 1 | 0 | `00 00 00` | 0 | miss (cold): install block 0–3, tag 0 | | 2 | 1 | `00 00 01` | 0 | **hit**: same block, offset 1 | | 3 | 8 | `00 10 00` | 2 | miss (cold): install block 8–11, tag 0 | | 4 | 20 | `01 01 00` | 1 | miss (cold): install block 20–23, tag 1 | | 5 | 32 | `10 00 00` | 0 | miss (cold): **evicts** block 0–3 (tags 2 vs 0) | | 6 | 0 | `00 00 00` | 0 | miss (**conflict**): evicts block 32–35 right back | | 7 | 9 | `00 10 01` | 2 | **hit**: block 8–11 still resident | $$ % caption: The seven-access trace on the worked direct-mapped cache. Filled boxes are % caption: misses, outlined boxes are hits; beneath each access is the set it indexes. % caption: Addresses 0 and 32 share set 0 with dif\/ferent tags, so access 5 evicts % caption: address 0's block and access 6 pays a conf\/lict miss to bring it back. \begin{tikzpicture}[font=\footnotesize,>=stealth] \definecolor{acc}{HTML}{2348F2} \foreach \i/\addr/\res/\set/\m in { 0/0/miss/0/1, 1/1/hit/0/0, 2/8/miss/2/1, 3/20/miss/1/1, 4/32/miss/0/1, 5/0/miss/0/1, 6/9/hit/2/0} { \pgfmathsetmacro{\x}{\i*1.55} \ifnum\m=1 \node[draw, fill=acc!25, minimum width=11mm, minimum height=7mm] at (\x,0) {\addr}; \else \node[draw=acc, very thick, minimum width=11mm, minimum height=7mm, text=acc] at (\x,0) {\addr}; \fi \node[anchor=north] at (\x,-0.5) {\res}; \node[anchor=north,black] at (\x,-1.0) {set \set}; } \node[anchor=north,text=acc] at (6.2,-1.5) {evicts 0}; \node[anchor=north,text=acc] at (7.75,-1.5) {conf\/lict}; \end{tikzpicture} $$ The trace exhibits every behavior the structure allows. Access 2 is spatial locality at work: byte 1 hits in the block that byte 0 fetched. Accesses 5 and 6 are the direct-mapped pathology: addresses 0 and 32 differ by 32, a multiple of $S \cdot B = 16$, so they share set 0 while carrying different tags, and each install evicts the other. Access 7 hits because set 2 was never disturbed. ## Why misses happen The structure itself explains the kinds of misses a cache can suffer. > **Definition (Cold, conflict, and capacity misses).** A **cold** (compulsory) > miss is the first reference to a block — the cache starts empty, so the very > first touch of any block must miss. A **conflict** miss happens when the cache > has room overall but several actively-used blocks map to the **same set** and > keep evicting one another. A **capacity** miss happens when the program's active > working set is simply larger than the cache, so blocks are evicted before reuse > no matter how they are placed. Direct-mapped caches, with one line per set, are > especially prone to conflict misses. Cold misses are unavoidable and mostly harmless: every block pays one. Capacity misses mean the working set is too large; to address them, restructure the computation (the [last lesson](/computer-architecture/memory-hierarchy/cache-performance-and-cache-friendly-code) of this module does exactly that). Conflict misses are an artifact of rigid placement, and they can be severe. ### Thrashing: the two-array ping-pong Conflict misses turn pathological when a loop alternates between two blocks that share a set. Reuse the worked capacity, reorganized as $S = 2$ sets of $B = 8$ bytes (two `int`s per block, still 16 bytes of cache), and take a dot product: ```c [dotprod.c] int dotprod(int x[4], int y[4]) { int sum = 0; for (int i = 0; i < 4; i++) sum += x[i] * y[i]; return sum; } ``` Suppose the linker places `x` at address 0 and `y` right behind it at address 16. Then `x[0..1]` occupy the block at 0 (set 0), `x[2..3]` the block at 8 (set 1), `y[0..1]` the block at 16 (and $16 / 8 = 2$ is even, so it maps to **set 0 again**), and `y[2..3]` the block at 24, set 1. Every `x` block shares a set with the `y` block the loop uses _at the same time_: - `x[0]` misses and installs `x`'s first block in set 0. - `y[0]` misses and **evicts it**, installing `y`'s first block. - `x[1]` would have been a hit, the block was just here, but it was evicted: miss, evict `y`'s block. - `y[1]` misses, evicts `x`'s block. And so on through both sets. Eight accesses, eight misses. The spatial locality is real (two `int`s per block) but the cache never gets to use it, because the two arrays **thrash**: they ping-pong in and out of the same sets. The fix is simple: move `y`. Pad `x` by one block (`int x[6];` costs 8 bytes) so `y` starts at 24, which maps to set 1. Now the pairs the loop touches together live in different sets, the ping-pong stops, and the trace collapses to the four cold misses spatial locality predicts: a miss rate of $1/2$ instead of $1$. $$ % caption: Conf\/lict thrashing and the padding fix. Left: with y at address 16, each % caption: y block maps to the same set as the x block the loop is using, and every % caption: access evicts the block the next access needs. Right: padding x by one block % caption: shifts y to address 24, the concurrent pairs land in dif\/ferent sets, and % caption: the misses drop from 8 of 8 to the 4 cold misses. \begin{tikzpicture}[font=\footnotesize,>=stealth, blk/.style={draw, minimum width=24mm, minimum height=7mm, inner sep=0pt}, setbox/.style={draw, minimum width=16mm, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % LEFT PANEL: collision \node[blk, fill=acc!8] (xa) at (0,1.1) {x[0..1] at 0}; \node[blk] (ya) at (0,0) {y[0..1] at 16}; \node[setbox, fill=acc!8] (s0a) at (4.4,1.1) {set 0}; \node[setbox] (s1a) at (4.4,0) {set 1}; \draw[->,acc,thick] (xa.east) -- (s0a.west); \draw[->,acc,thick] (ya.east) -- (s0a.south west); \node[anchor=north,text=acc] at (2.2,-0.6) {both map to set 0: thrash}; % RIGHT PANEL: padded \begin{scope}[xshift=7.9cm] \node[blk, fill=acc!8] (xb) at (0,1.1) {x[0..1] at 0}; \node[blk] (yb) at (0,0) {y[0..1] at 24}; \node[setbox, fill=acc!8] (s0b) at (4.4,1.1) {set 0}; \node[setbox] (s1b) at (4.4,0) {set 1}; \draw[->,acc,thick] (xb.east) -- (s0b.west); \draw[->,acc,thick] (yb.east) -- (s1b.west); \node[anchor=north,text=acc] at (2.2,-0.6) {disjoint sets: no thrash}; \end{scope} \end{tikzpicture} $$ Thrashing of this shape is common in practice: arrays whose sizes are powers of two land on it constantly, because power-of-two dimensions make different rows and different arrays differ by exact multiples of $S \cdot B$. That is why performance folklore says to avoid power-of-two leading dimensions, and why a byte of padding can be worth a 2x speedup. ## The case for and against direct mapping Direct mapping looks weak — one home per block, conflict misses by construction — yet it survived in real designs for a precise reason. **The direct-mapped hit is the fastest possible.** Hennessy and Patterson make the argument sharply: a direct-mapped cache reads out the one candidate line and checks its tag _in parallel_, so the data is available the instant the tag compare confirms it (Hennessy & Patterson, _Computer Architecture: A Quantitative Approach_, §2).[^hp] An associative cache cannot forward the data until it knows _which_ way matched, putting a multiplexer in the critical path. On the tightest L1 timing budgets that difference can decide the clock period, which is why several influential processors used direct-mapped L1 caches even after associativity was cheap. Mark Hill's analysis stated the trade-off as "direct-mapped is often faster per hit, associative misses less" — and which wins depends on whether the hit time or the miss rate is the binding constraint (Hill, "A case for direct-mapped caches," _IEEE Computer_ 1988).[^hill] **Victim caches reclaim most of the loss cheaply.** The direct-mapped weakness is narrow: a handful of hot blocks that collide in one set. Jouppi's **victim cache** attacks exactly that — a tiny fully-associative buffer (4 to 16 lines) that catches blocks _as they are evicted_ from the direct-mapped cache, so a block thrashed out by a conflict can be pulled back from the victim cache in one extra cycle instead of going all the way to memory (Jouppi, "Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers," ISCA 1990).[^jouppi] A few extra lines recover most of the conflict misses that associativity would have prevented, at a fraction of the hardware — a recurring theme in cache design: attack the specific pathology, not the general case. > **Takeaway.** A cache holds $S = 2^s$ sets of $E$ lines, each a $B = 2^b$-byte block > with a valid bit and tag, for $C = S\cdot E\cdot B$ bytes. An $m$-bit address splits > into a $t = m - s - b$ bit **tag**, an $s$-bit **set index**, and a $b$-bit **block > offset**. A direct-mapped cache ($E=1$) indexes to one set, hits iff that line is > valid and its tag matches, then selects the byte — and because each block has > exactly one home, blocks whose addresses differ by a multiple of $S \cdot B$ evict > each other: conflict misses, and in a tight loop, thrashing that padding can cure. Giving each set several lines, and choosing which to evict, is [set-associativity](/computer-architecture/memory-hierarchy/set-associative-and-write-policies) — along with the policies that govern what happens on a write. [^hp]: **J. L. Hennessy, D. A. Patterson**, _Computer Architecture: A Quantitative Approach_, 6th ed., Morgan Kaufmann, 2019 — §2 on memory hierarchy design; the direct-mapped hit reads data and checks the tag in parallel, avoiding the way-select multiplexer in the hit path. [^hill]: **M. D. Hill**, "A case for direct-mapped caches," _IEEE Computer_ 21(12), 1988 — argues that lower hit time can outweigh a higher miss rate, favoring direct mapping when hit time is the binding constraint. [^jouppi]: **N. P. Jouppi**, "Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers," _ISCA_ 1990 — the victim cache: a small fully-associative buffer that catches evicted blocks and recovers most conflict misses.