Cache line size and tags
Why Cache Lines Exist
Problem: Main memory is ~100× slower than the CPU. Fetching one byte at a time wastes the wide data bus (64–128 bits) and doesn't exploit locality.
Solution: Transfer fixed-size ==cache lines== (or blocks). Modern x86 uses 64-byte lines; ARM often uses 32 or 64 bytes. You pay one slow memory access, but then serve 64 bytes at cache speed.
Anatomy of an Address
Every memory address splits into three fields (for a direct-mapped cache; set-associative uses "set index" instead of "line index"):
Why this decomposition?
- Offset lets us extract the requested byte after fetching the line.
- Index tells hardware where to look (like a hash table bucket).
- Tag confirms what we found is the right data (collision detection).
Derivation: How Many Bits for Each Field?
Given:
- Address space: bits (e.g., 32-bit or 64-bit CPU).
- Cache size: bytes.
- Line size: bytes (always a power of 2).
- Associativity: ways (direct-mapped ⇒ ).
Step 1: Number of cache lines = .
Step 2: Number of sets = . (For direct-mapped, so sets = lines.)
Step 3:
i = \log_2\left(\frac{C}{L \cdot A}\right) \quad \text{(index/set bits)}
Why Line Size Matters
Tag Storage Overhead
Each cache line needs:
- Data: bytes.
- Tag: bits.
- Valid bit: 1 bit (is this line initialized?).
- Dirty bit (write-back): 1 bit (has data been modified?).
Total overhead per line: bits (ignoring replacement policy bits for set-associative).
Common Mistakes
Active Recall
Recall Explain to a 12-year-old
Imagine your desk (cache) can hold 10 folders (cache lines), and each folder holds 8 pages (bytes). Your giant filing cabinet (main memory) has thousands of folders.
When you ask for page 5 of folder 237, the cache doesn't just bring page 5—it brings the entire folder 237 (all 8 pages). Why? Because you'll probably need page 6 and 7 next. That's spatial locality.
The offset tells you which page in the folder (page 5). The index tells you which slot on your desk to check (slot 7). The tag is a label on the folder that says "This is folder 237 from the cabinet" so you know you grabbed the right folder.
If someone asks for folder 450 and it also maps to desk slot 7, you have to kick out folder 237 (a conflict). Bigger folders (bigger line size) mean fewer folders fit on your desk, so more conflicts. Smaller folders mean you're constantly running back to the cabinet. 64 pages per folder is the sweet spot for most homework.
Mnemonic
Connections
- 5.4.01-Cache-fundamentals – why caching is necessary (locality principles)
- 5.4.02-Direct-mapped-caches – simplest cache organization using these address fields
- 5.4.03-Set-associative-caches – index becomes "set index", multiple tags per set
- 5.4.05-Cache-miss-types – how line size affects compulsory vs. conflict misses
- 5.4.08-Write-policies – dirty bit usage in write-back caches
- 6.2.01-Virtual-memory-pages – page tables use similar tag-index decomposition
- 3.1.04-Spatial-locality – the reason cache lines are multi-byte
#flashcards/hardware
What are the three fields of a memory address in a cache system?
If a cache has 1024 lines and 32-byte line size, how many offset bits?
If a cache has 1024 lines and 32-byte line size, how many index bits?
In a 32-bit address space with 10 index bits and 5 offset bits, how many tag bits?
Why do larger cache lines reduce tag overhead?
What is the downside of very large cache lines (e.g., 256 bytes)?
What does the "offset" field select?
What does the "index" field select?
What does the "tag" field do?
Why transfer an entire cache line instead of one byte?
What is typical cache line size in modern x86 CPUs?
For a 64 KiB direct-mapped cache with 64-byte lines, how many cache lines?
Given 1024 cache lines, how many index bits?
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Cache line size aur tags ka concept samajhne ke liye ek simple analogy use karte hain. Jab CPU ek single byte mangta hai memory se, toh cache pora ek "daba" (cache line) lata hai—typically 64 bytes. Kyun? Kyunki agar tumhe ek byte chahiye, toh 99% chance hai ki agle kuch cycles mein tumhe uske pas wale bytes bhi chahiye honge (spatial locality). Toh ek baar slow memory se jane ki jagah, ek sath 64 bytes le ao, phir baki cache se fast serve karo.
Ab address ko teen parts mein todte hain: Tag, Index, aur Offset. Offset bata hai ki us 64-byte line ke andar kaunsa byte chahiye (last 6 bits agar line 64-byte hai). Index batata hai ki cache ki konsi line (slot) check karni hai—jaise ek hash table bucket. Tag high-order bits hote hain jo confirm karte hain ki yeh line memory ke kis block se aayi hai. Jab cache line check kare, toh stored tag ko address ke tag se match karo—match hua toh HIT, nahi toh MISS.
Line size badhane se spatial locality improve hoti hai (ek baar mein zyada data), lekin trade-off hai: kam total lines (zyada conflicts), aur miss penalty bhi badh jati hai (128 bytes transfer karna 64 se zyada slow hai). Industry standard 64 bytes isliye hai ki yeh balance optimal hai—na bahut chhota (bar-bar memory trip), na bahut bada (faltu data lana aur conflicts).
Tag storage bhi overhead hai: har line ke sath tag bits store karne padte hain. 32 KiB cache mein typically 3-4% space sirf tags ke liye jata hai. Agar line size double karo (64->128), toh lines half ho jayengi, tag overhead kam, lekin conflicts badh jayenge. Yeh sab trade-offs hardware designers balance karte hain real-world workloads ke liye.