Intuition The one core ideaA cache is a small fast copy of a tiny slice of memory, and to find something in it fast we cut the memory address into three fields of bits — one to pick a row, one to check identity, one to pick a byte. Everything else on the parent page is just counting how many bits go into each field , and every symbol below exists only to help us count those bits.
Before you can read the parent note Cache lines, tags, index, offset , you must be fluent in a handful of tiny ideas. This page builds each one from nothing — no symbol is used before it is drawn.
Picture a row of light switches. Each switch is one bit.
counting explodes as powers of two
With 1 switch you can show 2 0 1 2 switches you get 4 00 , 01 , 10 , 11 3 switches you get 8 doubles the number of patterns.
So k 2 k
This single fact — "k 2 k backwards and it becomes the tool we actually use: if I need to name N That backwards question is what the next symbol answers.
2 k 2 k 2 k 2 0 = 1 2 1 = 2 2 2 = 4 2 3 = 8 2 6 = 64 k exponent . On our switch picture, k 2 k
Recall Fill the table (self-test)2 0 = 1 2 1 = 2 2 2 = 4 2 3 = 8 2 4 = 16 2 5 = 32 2 6 = 64 2 8 = 256 2 10 = 1024
Why the topic needs it Line sizes and set counts are always powers of two (B = 64 = 2 6 S = 256 = 2 8
Now the backwards question from Section 0.
log 2 N log 2 N "2 N It is the undo button of 2 k 2 k = N log 2 N = k
log 2 k 2 k number of things N how many switches , we need the operation that turns 2 k k log 2 N
Worked example Read it off the picturelog 2 64 = 6 2 6 = 64 6 64 log 2 256 = 8 2 8 = 256 8 256
log 2 N N Why it feels right: the button looks universal.
Reality here: log 2 N whole number only when N log 2 100 = 6.64...
Why the topic needs it Every field width — offset = log 2 B = log 2 S log 2
Addresses are long strings of bits. Writing 32
Definition Binary vs hexadecimalBinary = the raw bits, e.g. 1110 1111.
A nibble = a group of 4 Hexadecimal ("hex") writes one nibble as one symbol 0 9 A F A = 10 , ... , F = 15 0x== just announces "the following is hex".
So 0xF = 1111 = 15 0x2F = 0010 1111.
Common mistake "One hex digit lines up with the field boundaries."Why it feels right: hex digits are tidy 4 Why it bites you: the offset is 6 not a multiple of 4 not start on a hex boundary. This is exactly the 0xDEADBEEF trap on the parent page — you must think in bits , not nibbles, when slicing.
Why the topic needs it Addresses like 0xDEADBEEF are hex; you must expand them to bits to slice fields correctly.
A n byte-addressable : every single byte has its own house number, called its address A n 2 n 2 n 32 n = 32 2 32 ≈ 4
Picture a very long street where every byte is one house, numbered 0 , 1 , 2 , … , 2 n − 1
Why the topic needs it The address is the raw material we chop into tag/index/offset. n n = tag + index + offset
The parent uses ⌊ A / B ⌋
Intuition Why dividing an address byB block number
A line/block is B 0.. B − 1 0 B ..2 B − 1 1 A B A ⌊ A / B ⌋ Bonus: in binary, dividing by B = 2 offset deleting the low offset bits . That is why chopping bits = arithmetic for free, the whole reason hardware likes this scheme.
Why the topic needs it The low bits of the block number become the
index ; the leftover high bits become the
tag . See
Spatial and temporal locality for
why grouping bytes into blocks pays off.
Now the four cache dimensions, in build order.
Definition The cache symbols
B bytes per line (block size), e.g. B = 64 offset width = log 2 B L total number of lines the whole cache holds.w ways = how many lines share one set (see Cache associativity & replacement policies ).S number of sets (rows) , and S = L / w index width = log 2 S
Intuition How they fit togetherThink of the cache as a grid: S w L = S × w S = L / w w = 1 S = L w = L S = 1 zero index bits).
Why the topic needs it These four numbers, plugged into log 2
You now own every piece. The parent's headline formula reads, symbol by symbol:
Read it as three "how many bits?" questions answered by log 2 n
bits = yes or no switches
k switches name two-to-the-k things
log base 2 = how many bits
group bits into nibbles = hex 0x
divide by B = drop low bits = block number
ADDRESS SPLIT tag index offset
Convert 2 6 64
Convert log 2 256 8 2 8 = 256
Why must B S So each field is a whole number of bits (log 2
Expand the hex digit 0xF to 4 1111.
What does the prefix 0x announce? The number that follows is written in hexadecimal.
What does n Address width in bits; it names 2 n
What does ⌊ A / B ⌋ The block number — how many whole B A
In binary, dividing by B = 2 k Deleting the low k
Relate S L w S = L / w
How many index bits when S = 1 Zero, since log 2 1 = 0
Offset width formula and what it depends on log 2 B
Tag width formula n − log 2 S − log 2 B
