Cache organization (direct-mapped): Visual walkthrough

Before we start, one word we will use constantly:

Step 1 — Lay the address out as a row of bits

WHAT. Take any address and write it as a horizontal strip of $m$ bits, most-significant bit (the "biggest" bit, worth the most) on the left, least-significant on the right.

WHY. Everything the cache does is "grab this group of bits, ignore the rest." A picture of the strip lets us literally point at which bits do which job. We choose binary (not decimal) because chopping a number into bit-groups is exactly the same as chopping the ruler into powers of two — and caches are built from powers of two.

PICTURE. Look at the strip below. Right now it is one undivided ribbon of $m$ bits. Our entire job on this page is to draw two vertical cut lines on it.

Step 2 — Make the first cut: the Block Offset

WHAT. Slice off the rightmost $b$ bits. Call this piece the block offset. If a block holds $2^{b}$ bytes, these $b$ bits are exactly enough to name every byte inside one block.

WHY. Memory is byte-addressable, but hauling one byte across the wire wastes the trip. So the cache always fetches a whole block of $2^{b}$ bytes. Once a block has arrived, we still need to point at one byte inside it — that is the only job of the offset. And $b$ bits count from $0$ up to $2^{b} - 1$ , which is precisely "byte 0 … byte last" of the block. Perfect fit, no waste.

PICTURE. In the figure the rightmost slab (yellow) is peeled off. Watch how the offset value cycles $0, 1, 2, \dots, 2^{b} - 1$ and then resets to 0 as we cross into the next block — like an odometer's last digit.

Step 3 — What's left is the Block Address

WHAT. Everything to the left of the offset cut — the top $m - b$ bits — is the block address. It is the address with the "which byte" part thrown away.

WHY. Two bytes in the same block share every high bit; they differ only in offset. So if we erase the offset, all $2^{b}$ bytes of a block collapse to one number. That single number is what the cache reasons about when it decides where to store a block. We had to build this before Step 4 because the placement rule works on whole blocks, never single bytes.

PICTURE. The figure shows the odometer analogy: chopping the last $b$ digits is the same as integer-dividing by $2^{b}$ . Bytes 0–3 all map to block 0; bytes 4–7 all map to block 1.

Step 4 — Make the second cut: the Index (the parking spot)

WHAT. From the block address, slice off the next $c$ bits (the low $c$ bits of the block address). Call this the index. With a cache of $2^{c}$ lines, these $c$ bits name exactly one line.

WHY — and why this tool. The cache has only $2^{c}$ lines but memory has vastly more blocks. We need a rule that sends every block to one definite line, with no searching. The rule is $mod 2^{c}$ : block $0 \to$ line $0$ , block $1 \to$ line $1$ , …, block $2^{c} - 1 \to$ last line, then block $2^{c}$ wraps back to line $0$ . We pick modulo (not, say, "search for a free line") precisely because modulo gives a direct, instantaneous answer — hence the name direct-mapped. And $mod 2^{c}$ is free in hardware: it is just "keep the low $c$ bits," no divider needed.

PICTURE. The figure wraps the block numbers around a ring of $2^{c}$ lines like numbers on a clock face. Blocks $0, 2^{c}, 2 \cdot 2^{c}, \dots$ all land on line 0 — they stack up on the same spot. Remember that stacking; Step 5 exists to untangle it.

Step 5 — What remains is the Tag (the name badge)

WHAT. The topmost $m - c - b$ bits, everything left after both cuts, is the tag.

WHY. Step 4 warned us: many different blocks land on the same line. Line 0 might currently hold block 0, or block $2^{c}$ , or block $2 \cdot 2^{c}$ — they are indistinguishable by index alone. The tag is the leftover high bits, and those high bits are exactly what makes those colliding blocks different. So the tag is a name badge: once the index has walked us to one line, comparing the stored tag to our address's tag tells us "is the block sitting here really mine?"

PICTURE. The strip is now fully cut into three coloured pieces: red Tag | blue Index | yellow Offset. Below it, two addresses with the same index but different tags are shown fighting over one line.

Step 6 — Put the pieces to work: the hit/miss decision

WHAT. Use index to pick a line; check that line's valid bit (is anything real stored here?); if valid, compare the stored tag to our tag.

WHY. These are the only two ways the answer could be "no." Either the line was never filled (valid bit = 0 → a cold miss), or it holds someone else's block (tag mismatch → a conflict miss). Only when the line is valid and the tags match is the data ours — a hit. One line lookup, one tag comparison. No loops. That single comparison is the entire speed advantage of direct-mapped over set-associative caches.

PICTURE. A flow: address → split → jump straight to the line → the two checks → HIT (green) or MISS (red).

Step 7 — Edge & degenerate cases (never leave the reader stranded)

WHAT & WHY. Let's test the machine at its extremes so no scenario surprises you.

Offset of zero bits ( $b = 0$ , block size $= 1$ byte). Then there is no yellow slice; each block is a single byte. The offset "wrap" never happens because a block has only one byte. Legal, but you lose the bandwidth win of fetching neighbours — bad for spatial locality (see Cache Performance Metrics).
Index of zero bits ( $c = 0$ , exactly one line). No blue slice; every block maps to the same single line. The tag becomes the whole block address. This is the ultimate collision machine — two alternating addresses thrash forever.
Tag of zero bits ( $m - c - b = 0$ ). No red slice; the index+offset already name every address uniquely, so no two blocks ever collide. This means the cache is as big as memory itself — pointless, but a valid limit.
Valid bit = 0 at power-on. Before the cache has run, every line is invalid, so the first touch of any block is always a cold miss. This is why we compare the valid bit before the tag — an unfilled line may hold leftover garbage bits that could accidentally "match."

PICTURE. Three mini-strips showing $b = 0$ , $c = 0$ , and the all-collide case side by side.

The one-picture summary

Below is the whole walkthrough compressed: one 8-bit address ( $m = 8$ , $b = 2$ , $c = 2$ ) enters, gets cut into Tag | Index | Offset, the index jumps to a line, the valid bit and tag decide hit vs miss, and the offset pulls the final byte. Trace the arrows once and you have re-derived the entire scheme.

Recall Feynman retelling — say it in plain words

A memory address is just a number naming a byte on a giant ruler. I write it in binary as a ribbon of bits. I make two cuts. The rightmost cut peels off a few bits — the offset — which just says "which byte inside a carton of bytes," because I always fetch bytes by the carton (block). The next cut peels off the index — that's a parking-spot number I get by counting blocks around a ring of parking spots and wrapping when I run out; it tells me exactly one line, no searching. Whatever bits are left over on top are the tag — a name badge, because lots of different blocks are forced to share the same parking spot, and the badge is the only thing that tells them apart. To answer "do I have your data?": I use the index to walk straight to the one line, I check its valid bit (is anything real here?), and if so I compare its stored badge to my badge. Both good → hit, and the offset grabs my byte. Badge wrong → conflict miss. Never filled → cold miss. One walk, one comparison, done.

Recall Quick self-test

Which address piece never affects whether you hit or miss? ::: The block offset — it only selects a byte within an already-located block. Why is modulo the natural tool for the index? ::: Because "block number mod number-of-lines" sends blocks around the lines and wraps back — a direct, search-free placement — and mod by $2^{c}$ is just "keep the low $c$ bits" in hardware. With $m = 8$ , $b = 2$ , $c = 2$ , how many tag bits? ::: $8 - 2 - 2 = 4$ tag bits. Two addresses share an index but differ in tag — what happens if you alternate them? ::: They thrash: each access evicts the other, so every access is a conflict miss.

See also: Cache Write Policies · Cache Replacement Policies · Cache Performance Metrics · Set-Associative Caches