Cache Memory Organization (7 Marks)

1. Introduction:
Cache is a small, very fast SRAM between CPU and main memory that exploits locality of reference (temporal & spatial) to reduce average access time. CPU first checks cache; on hit data returned quickly, on miss block fetched from main memory.

Hierarchy: CPU ↔ L1 ↔ L2 ↔ Main Memory ↔ Disk. Cache stores blocks/lines consisting of tag + data block + valid/dirty bits.

2. Mapping Techniques:
Mapping determines where a main memory block can be placed in cache.

a) Direct Mapping:
Each memory block $j$ maps to exactly one cache line: Cache Line = j mod m where $m$ = number of lines. Address split: | Tag | Line | Word |.

• Advantage: Simple hardware, low cost, fast lookup.
• Disadvantage: High conflict misses – two blocks mapping to same line thrash even if other lines empty. Hit ratio lower.

b) Fully Associative Mapping:
Any block can go into any line. Address split: | Tag | Word |. Tag compared associatively with all line tags in parallel.

• Advantage: Most flexible, minimum conflict misses, best hit ratio.
• Disadvantage: Expensive – requires associative CAM comparator for every line, slow for large cache.

c) k-Way Set-Associative Mapping: Compromise.
Cache divided into $v = m/k$ sets, each set has $k$ lines. Block $j$ maps to Set = j mod v, can occupy any of $k$ lines within that set. Address split: | Tag | Set | Word |.
Example: 2-way, 4-way. Direct ($k=1$) and Fully Associative ($k=m$) are extremes.

• Advantage: Reduces conflicts while keeping hardware manageable. Widely used (e.g., Intel uses 8-way/16-way).
• Disadvantage: Moderate hardware complexity.

3. Replacement Algorithms (needed when set is full):

• LRU (Least Recently Used): Replaces block not used longest time. Best hit ratio, implemented via counters/stack. Common.
• FIFO: Replaces first-loaded block. Simple but not optimal, suffers Belady effect.
• LFU: Replaces least frequently used.
• Random: Random selection, simple hardware, average performance.

4. Write Policies (on write hit):

• Write-Through: Data written to both cache and main memory simultaneously. Simple, consistent but high bus traffic. Uses write buffer.
• Write-Back (Copy-Back): Write only to cache and set dirty bit. Block written back to memory only on replacement. Less traffic, better performance but coherence complex.
• On write miss: Write-Allocate (fetch block to cache then write) vs No-Write-Allocate (write directly to memory).

Performance: $T_{avg}=h \cdot T_c + (1-h)\cdot T_m$ where $h$=hit rate.