Cache mapping decides how a main memory block maps to cache line(s). Let cache have $2^c$ lines, memory have $2^m$ blocks, address = Tag + Index/Set + Word/Offset.

1. Direct Mapping

Each memory block $i$ maps to exactly one cache line: $line = i \mod (\text{no. of lines})$.
Address split: $|Tag| + |Line| + |Word|$.
e.g., 4096 lines need 12 line bits. With 64-word blocks (6 bits), address = Tag(remaining)+12+6.

• Search: Compare only that line's tag - fast, simple.
• Miss: Replacement is forced, no choice.
• Drawback: Thrashing - two blocks mapping to same line continuously collide even if cache has free lines.

2. Associative (Fully Associative) Mapping

Any memory block can go to any cache line. Address = $|Tag| + |Word|$ only; no line field.

• Search: Content-addressable memory (CAM) compares incoming Tag with all line tags in parallel.
• Replacement: Need algorithm - LRU, FIFO, Random.
• Advantage: No collision thrashing, best hit rate.
• Drawback: Expensive comparators for all lines, slow for large cache.

3. Set-Associative Mapping

Compromise. Cache divided into $S$ sets, each set has $k$ lines ($k$-way). Block $i$ maps to $set = i \mod S$, can occupy any of $k$ lines within set.

• Address: $|Tag| + |Set| + |Word|$.
  Example $k=2$, 4096 lines → 2048 sets → 11 set bits. Address = Tag+11+6.

• Search: Index set via Set field, associatively compare Tag among $k$ lines in that set only.

• Replacement: Choose within set (LRU).

• Special cases: $k=1$ → Direct, $k = \text{no. of lines}$ → Fully Associative.

• Tradeoff: Hit rate improves with larger $k$ but cost increases. Typical $k=2,4,8$.

Replacement policies (LRU, LFU, FIFO) apply to associative and set-associative when set is full. Write policies: Write-through + write-allocate/no-allocate, Write-back.