Cache Memory

Cache memory is a small, fast memory placed between the processor and main memory (RAM). It holds recently used instructions and data so that the processor does not need to access the slower main memory repeatedly. Since accessing RAM can take tens to hundreds of clock cycles, cache memory is essential for achieving the performance levels expected from modern processors.

Cache memory is a high-frequency GATE topic covering L1, L2, L3 cache hierarchy, hit and miss rates, mapping techniques (direct, associative, set-associative), and replacement policies. Understanding cache helps explain why real processor performance differs from theoretical peak speed.

Core Concept: Why Cache Exists

Modern processors operate at clock frequencies of several GHz, completing billions of cycles per second. Main memory (DRAM), however, has access latencies of 60 to 100 nanoseconds, equivalent to 100 to 200 processor cycles at 2 GHz. If every memory access went directly to RAM, the processor would be idle for most of the time waiting for data. Cache memory bridges this memory wall by exploiting two fundamental properties of programs.

The first is temporal locality: if a memory location is accessed, it is likely to be accessed again soon. The second is spatial locality: if a memory location is accessed, nearby locations are likely to be accessed soon. Cache exploits both by storing recently accessed data (temporal) and fetching an entire cache line (typically 64 bytes) on each access (spatial). Programs with loops and sequential data access benefit enormously from cache.

Cache Hit and Miss

When the processor requests data, it first checks the cache. If the data is found, it is called a cache hit and the data is supplied in a few cycles. If the data is not in cache, it is called a cache miss and the processor must fetch it from the next lower level of the hierarchy (L2, L3, or RAM), incurring a significant penalty called the miss penalty.

The hit ratio h is defined as the fraction of accesses that result in a hit. If h = 0.95, then 95% of accesses are served from cache. The effective memory access time (EMAT) accounts for both hits and misses: EMAT = h x t_cache + (1 - h) x t_memory, where t_cache is the cache access time and t_memory is the main memory access time.

Cache Mapping Techniques

Since cache is much smaller than main memory, a mapping scheme is needed to determine which cache location stores which main memory block. The three schemes are direct mapping, fully associative mapping, and set-associative mapping.

In direct mapping, each main memory block maps to exactly one cache line using the formula: cache line = (block number) mod (number of cache lines). This is simple and fast but suffers from conflict misses when two frequently used blocks map to the same cache line. In fully associative mapping, any block can go into any cache line, eliminating conflict misses, but it requires searching all cache lines simultaneously which is hardware-intensive.

Set-associative mapping is a compromise. The cache is divided into sets, each containing k ways (k-way set-associative). A block maps to exactly one set (using the set index bits) but can occupy any of the k ways within that set. 2-way and 4-way set-associative caches are common in practice. When a new block must enter a full set, a replacement policy decides which existing block to evict. Common policies are LRU (Least Recently Used), FIFO, and Random.

Mathematical Expression

The effective memory access time formula is the most frequently tested cache formula. Given hit ratio h, cache time t_c, and main memory time t_m, EMAT = h x t_c + (1 - h) x t_m. For multi-level caches, the formula extends: EMAT = t_L1 + (1 - h1)(t_L2 + (1 - h2) x t_RAM). This accounts for the hierarchical lookup that happens on a miss at each level.

Given:
L1 cache hit ratio h1 = 0.90, L1 access time t_L1 = 4 ns
Main memory access time t_mem = 80 ns

Why this formula applies:
On a hit, only L1 is accessed. On a miss, both L1 and RAM are accessed.

Formula:
EMAT = h1 x t_L1 + (1 - h1) x (t_L1 + t_mem)

Substitution:
EMAT = 0.90 x 4 + 0.10 x (4 + 80)

Calculation:
= 3.6 + 0.10 x 84
= 3.6 + 8.4
= 12 ns

Final Answer: Effective Memory Access Time = 12 ns  (compared to 80 ns without cache, a 6.67x improvement).

Exam Tip: In GATE, always check whether the formula uses simultaneous access (EMAT = h x t_c + (1-h) x t_m) or sequential access (EMAT = t_c + (1-h) x t_m). The question usually specifies this. Sequential access adds t_c even for misses.

• Cache exploits temporal and spatial locality to reduce effective memory access time.
• EMAT = h x t_cache + (1-h) x t_memory for simultaneous access model.
• Direct mapping: fast lookup, prone to conflict misses. Fully associative: no conflict misses, expensive hardware.
• Set-associative: practical compromise used in all modern processors (2-way, 4-way, 8-way).
• L1 cache is private to each core (32-64 KB, ~4 ns); L3 cache is shared across cores (4-32 MB).
• Replacement policies: LRU gives best hit rate but requires tracking usage history.

Quick Revision

• Cache exploits temporal locality (reuse) and spatial locality (nearby addresses accessed together).
• EMAT formula: h x t_c + (1-h) x t_m (simultaneous) or t_c + (1-h) x t_m (sequential access).
• Direct mapping: line = block mod cache_lines. Simple, fast, but conflict misses possible.
• Fully associative: no conflict, but hardware cost is high due to parallel tag comparison.
• Set-associative: block maps to a fixed set, any way within that set. Best practical trade-off.
• Address bits: [Tag | Index | Block Offset]. Index selects set; Tag identifies specific block.
• Exam trap: In GATE, check if the question says simultaneous access or hierarchical/sequential access as this changes the EMAT formula.