Cache organization (direct-mapped)

What Is a Direct-Mapped Cache?

A direct-mapped cache is the simplest cache organization where each block of main memory maps to exactly one cache line. The cache location is determined by the memory address using:

$\text{Cache Index} = (\text{Block Address}) \bmod (\text{Number of Cache Lines})$

Derivation From First Principles

WHY do we need these three address components? Let's build it step-by-step.

Step 1: Block Offset (Why?)

Problem: Memory is byte-addressable, but fetching one byte at a time wastes bus bandwidth.

Solution: Fetch a cache block (multiple consecutive bytes). If block size = $2^b$ bytes, the lowest $b$ bits select the byte within the block.

Formula: $\text{Block Offset} = \text{Address} \bmod 2^b$

WHY this works: The offset bits "wrap around" every $2^b$ bytes, naturally indexing bytes 0, 1, 2, ..., $2^b-1$ within a block.

Step 2: Cache Index (Why?)

Problem: We have $2^c$ cache lines. Which line should hold a given block?

Solution: Use the block address (address with offset bits removed) modulo the number of lines.

Derivation:

• Block address = $\lfloor \frac{\text{Address}}{2^b} \rfloor$
• Cache index = Block address $\bmod 2^c$
• In binary, this means extract bits $[b+c-1 : b]$ from the address

Formula: $\text{Index} = \left\lfloor \frac{\text{Address}}{2^b} \right\rfloor \bmod 2^c$

WHY modulo? We want blocks0, 1, 2, ... to cycle through cache lines 0, 1, 2, ..., $2^c-1$, then wrap back to line 0. Block $2^c$ maps to line 0, block $2^c+1$ to line 1, etc.

Step 3: Tag (Why?)

Problem: Multiple memory blocks map to the same cache line (e.g., blocks 0, $2^c$, $2 \cdot 2^c$, ... all map to line 0). How do we know which block is currently stored?

Solution: Store the tag (remaining high-order bits). The tag distinguishes blocks that collide at the same index.

Formula: $\text{Tag} = \left\lfloor \frac{\text{Address}}{2^{b+c}} \right\rfloor$

WHY it works: If two addresses have the same index but different tags, they're different blocks competing for the same cache line. The tag acts as a "full identifier" once we've narrowed down to one cache line.

Complete Access Algorithm

1. Extract index bits → find cache line L
2. Check valid bit: if V=0, it's a MISS (cold miss)
3. Compare stored tag with address:
   - Match? → HIT, extract data using offset
   - No match? → MISS (conflict miss), evict and fetch new block

Worked Examples

Common Mistakes (Steel-Man Analysis)

Connections

• Cache Performance Metrics - Hit rate, miss rate, AMAT depend heavily on conflict misses in direct-mapped caches
• Set-Associative Caches - Solve the conflict problem by allowing multiple blocks per index (direct-mapped is 1-way set-associative)
• Memory Addressing - Address decomposition (tag/index/offset) is the foundation of spatial and temporal locality exploitation
• Cache Replacement Policies - Direct-mapped has no choice (forced eviction), but this connects to LRU/FIFO in associative caches
• Cache Write Policies - Write-through vs. write-back apply to direct-mapped caches with additional complexity on conflicts

#flashcards/hardware

What are the three components of a memory address in a direct-mapped cache? :: Tag (identifies which memory block), Index (selects cache line), Block Offset (selects byte within block)

Formula for cache index in direct-mapped cache :: Index = (Address / 2^b) mod 2^c, where b = block offset bits, c = index bits

Calculate tag bits for: 32-bit address, 512 lines, 64-byte blocks :: Tag = 32 - log₂(512) - log₂(64) = 32 - 9 - 6 = 17 bits

Concept Map

Hinglish (regional understanding)