Cache Mapping Techniques

Cache maps main memory blocks to cache lines. For memory address: Tag | Line/Set Index | Word/Offset. Three techniques:

1. Direct Mapping

• Rule: Each memory block $j$ maps to exactly one cache line: Line = j mod (number_of_lines)
• Address: Tag | Line | Word (e.g., 12-bit tag, 8-bit line, 6-bit word for 64-byte block)
• Hardware: One comparator per access, simple.
• Pros: Simple, cheap, fast hit time (one tag compare).
• Cons: Conflict misses high - if two blocks map to same line they thrash (even if other lines empty). No flexibility. Worst hit ratio.
• Use: Low-cost caches.

2. Fully Associative Mapping

• Rule: Any memory block can go to any cache line. No index field.
• Address: Tag | Word only. Cache stores Tag per line.
• Hardware: CAM - all tags compared in parallel (content-addressable memory) + valid bit. Replacement algorithm needed (LRU, FIFO, Random).
• Pros: Most flexible, lowest conflict misses - best hit ratio for given size. No thrashing.
• Cons: Expensive (parallel comparators for every line), slow for large cache (many comparators, high power). Replacement logic complex. Suitable only for small caches (e.g., TLB).
• Use: Small fully-associative TLB, victim caches.

3. Set-Associative Mapping (k-way)

• Compromise between 1 and 2. Cache divided into sets, each set has $k$ lines. Set = j mod (number_of_sets). Block can go to any of $k$ lines within set.
• Address: Tag | Set | Word
• Examples: 2-way, 4-way, 8-way. If $k=1$ -> Direct, if $k = lines$ -> Fully associative.
• Hardware: $k$ comparators per set (parallel within set), plus set decode.
• Pros: Good balance - reduces conflict misses greatly (e.g., 4-way removes most thrashing) with modest hardware cost. Most used in modern CPUs (L1: 4-8 way, L2/L3: 8-16 way).
• Cons: Slightly slower than direct (k compares + mux), needs replacement within set (LRU approx).
• Intel Example: 32KB 8-way L1, 1MB 16-way LLC.

Comparison Summary

Technique	Lines per block	Comparators	Hit time	Miss rate	Cost
Direct	1	1	Fastest	Highest	Lowest
2/4-way Set	k	k	Medium	Medium-Low	Medium
Fully Associative	All	All lines	Slow (large)	Lowest	Highest

Other merits/demerits:

• Capacity vs Conflict vs Compulsory misses: Direct suffers conflict; Fully associative only compulsory+capacity; Set-associative reduces conflict sharply even 2-way improves miss rate ~30-40%.
• Replacement: Direct - no choice; Associative/Set - need LRU.
• Victim Cache / Pseudo-associative: Extra small fully-associative buffer for direct-mapped conflict blocks.

Modern processors use Set-Associative (typically 4-16 way) as sweet spot; TLBs use Fully-Associative; cheap microcontrollers may use Direct-mapped.