Cache organization (direct-mapped): Foundations — Hardware deep dive

Before you can follow the parent note, every squiggle it uses has to mean something concrete in your head. This page builds each one from nothing, in an order where every idea rests on the one before it.

0. What is a "bit"? (the atom of everything)

A row of bits written together is a binary number. Reading it is exactly like reading a decimal number, except each place is worth 2 times the place to its right instead of 10 times.

Figure — Cache organization (direct-mapped)

Look at the figure: the rightmost bit is the "ones" place ( $2^{0}$ ), the next is "twos" ( $2^{1}$ ), then "fours" ( $2^{2}$ ), and so on. To find the value you add up the place-values wherever there is a $1$ .

Why the topic needs this: a memory address is a row of bits. All the "chopping" the parent does is grabbing certain bits out of that row — impossible to understand without knowing what a bit is worth.

1. The exponent notation $2^{n}$ (why powers of two rule everything)

$n$ bits	patterns $2^{n}$
$1$	$2$
$2$	$4$
$3$	$8$
$10$	$1024$ (= 1 KB of things)

Why the topic needs this: cache size, block size, and line count are always powers of two precisely so a whole clean group of address bits can name each one.

2. The logarithm $lo g_{2}$ (the exact undo of $2^{n}$ )

$2^{n}$ answers "how many patterns do $n$ bits give?". But the parent constantly asks the reverse question: "I need to name $2048$ lines — how many bits is that?"

Why this tool and not division? Division would tell you how many times something fits; $lo g_{2}$ tells you how many switches it takes — a completely different question, and it is the bit-counting question caches live on.

$x$ must be a power of two for this to land on a whole number — which is exactly why cache sizes always are.

3. Bytes and "byte-addressable memory"

Why the topic needs this: the parent's "block offset" only makes sense once you see memory as individually-numbered byte-mailboxes; the offset is which mailbox inside a group you want. See Memory Addressing for the full picture.

4. The address as a row of $m$ bits

The single most important move in the whole topic: one address is one row of $m$ bits, and we will slice that row into three labelled fields. Hold that image.

5. The block — grouping mailboxes

Why groups at all? Because programs almost always use bytes near each other soon after (this is spatial locality). Fetching a whole neighbourhood at once is cheaper than fetching one mailbox at a time.

6. Modulo `mod` — the wrap-around rule

The parent's core formula uses $mod$ . This is the one piece of "real math" and it deserves a picture.

Why this tool? The cache has only $2^{c}$ lines but memory has millions of blocks. We need a rule that takes any block number and always lands inside $0 \dots 2^{c} - 1$ , cycling fairly. Modulo is exactly the "wrap the counter" operation — no other simple operation gives every block a definite, repeatable home slot.

A beautiful shortcut: when $n = 2^{c}$ , mod is just "keep the lowest $c$ bits" — because those low bits already are the remainder. That is why the parent can grab bits instead of doing real division.

7. The floor $⌊ ⌋$ — throwing away the leftovers

The parent writes the block number as $⌊ \frac{Address}{2 ^{b}} ⌋$ . Dividing an address by $2^{b}$ and flooring means "chop off the last $b$ offset bits" — it discards which byte you wanted and keeps only which block. In bit-terms it is a right shift by $b$ .

8. Putting the slices together — Tag / Index / Offset

Now every symbol earned, the parent's decomposition reads cleanly. Slice the $m$ -bit address:

$Tag m - c - b bits Index c bits Offset b bits$

Offset (low $b$ ): which byte inside the block — from §5.
Index (middle $c$ ): which cache line, via the wrap rule — from §6.
Tag (top $m - c - b$ ): everything left over, used to prove the line holds your block and not a colliding one.

Where do these lead next? Tags-per-line and valid bits drive Cache Performance Metrics; letting a block choose among several slots instead of one is Set-Associative Caches; deciding who to kick out when slots fill is Cache Replacement Policies; deciding how writes update memory is Cache Write Policies.

Prerequisite map

Equipment checklist

Cover the right side and answer each before moving on.

Read the binary number

101 0_{2}

as a decimal value

8 + 2 = 10

What does

2^{n}

count, in one phrase

the number of distinct patterns

n

bits can make

Compute

lo g_{2} 512

9

, because

2^{9} = 512

How many bits to name

2^{c}

cache lines

exactly

c

bits

What does "byte-addressable" mean

every single byte has its own numbered address

If block size is

2^{b}

bytes, how many offset bits

b

bits

Compute

13 mod 4

1

(wraps: 0,1,2,3,0,1... 13 lands on 1)

When

n = 2^{c}

, the fast way to compute

a mod n

keep the lowest

c

bits of

a

What does

⌊ Address / 2^{b} ⌋

give you

the block number (offset bits chopped off)

Which field picks the cache line

the Index (middle bits), never the Tag

What is the Tag for

to prove a line holds your block among all blocks sharing its index

What does the Valid bit being 0 force

a miss — the line is empty

For

m = 8, c = 2, b = 2

, how many Tag bits

8 - 2 - 2 = 4

bits