Cache

This is a Hardware structure fabricated in the Same chip as CPU, not inside CPU.

Cache Levels

Terminology

Cache block

Minimum unit of data that is transferred between cache and main memory. Tagged with memory address. Searched in parallel. A cache block stores data, tag for the memory address and some other metadata. A block may contain large amount of words.

Multiple blocks are moved between levels in cache hierarchy.

Hit ratio

Fraction of memory accesses found in cache.

Hit time

Time to access a block in cache.

Cache miss

When required item is not found in cache.

3 types:

• Compulsory: This is unavoidable. Happens when the Cache isn't initialized yet, like at the CPU startup.
• Capacity: Cache is not enough to load all data of the program needs. If new item needs to be added, older ones must be replaced.
• Conflict (collision): when space is left, but multiple blocks compete for the same set Conflicts cannot be removed but can be reduced by the Cache Replacement Policy.

Miss Penalty

Time to bring a block from memory + Deliver it to processor

$$\text{Time} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$$

Cache Access

Cache should be able to provide the correct data when given Only the Memory Address.

For this, cache uses the first few bytes as a Tag, that can uniquely identify Each Memory Value. But MSBs can be shared by a lot of memory addresses, therefore the next bits after the Tag used for Row Index. Which guarantees non of memory locations adjacent will be in same cache block.
Last Few bits (LSBs) used to identify the offset of the actual data in the block.

Cache Record Structure

• Index - this is not stored as a record but searched by indexing.
• Valid Bit - a single bit used to indicate if the record is correct or not.
• Tag - act as the unique Identifier of the cache line.
• Data - Actual data that matches the main memory address

Other than these, A Dirty Bit is used to indicate if main memory value and cache value is Out of Sync. This happens when the cache is updated by CPU but haven't been written back into Memory.

Cache Associativity

This defines how the cache blocks are filled from the memory.

Direct Mapping

One Memory Block can go to only one place in cache. If cache has 10 spaces, $X \, \text{mod} \, 10$ Memory Address 0x00009, 0x00079, 0x88789 would all go into same cache block.

Fully Associativity

One Memory Block can go into anywhere in the cache, Searching will be done parallelly

Set Associativity

Combination of Direct Mapping and Fully Associativity. One Memory Block can go to any block in a set of blocks. One set will have $n$ no. of blocks.

• n-way set associative $\to$ n amount of blocks in a set

A way is one block in a set. Ways are searched parallelly. The Set cache goes into is determined by Direct Mapping.

Cache Replacement Policy

This policy determines which item to remove from cache when a new one comes in. The end goal is to achieve the maximum cache hit rate as much as possible. Since the policy need extra knowledge like no. of times accessed, time last accessed etc, the Complexity grows as a caveat.

Common Cache Replacement Policies

• Least Recently Used (LRU): Remove the oldest item which haven't accessed in long time.

  • Drawback: High tracking overhead (e.g., maintaining a doubly linked list + hash map).

• First-In, First-Out (FIFO): Oldest goes out no matter how frequently its been accessed. Simple implementation cost.

  • Drawback: Poor hit rates for items that are accessed repeatedly over long periods.

• Least Frequently Used (LFU): Count the number of times hit, and drop the least hit one.

  • Drawback: If a item has 1000 hit count but haven't accessed in a while, it will keep persisting since the hit count is much larger so will not be replaced. ( frequency pollution ).

• Random Replacement (RR): Randomly selects an entry to discard. Simple so best on Hardware implementations (like hardware CPU L1/L2 caches) where simple logic saves silicon area and power.

  • Drawback: Makes non-optimal choices compared to usage-aware algorithms.

• Adaptive Replacement Cache (ARC): Dynamically tunes its balance between recency (LRU) and frequency (LFU) based on workload changes.

  • Drawback: Complex AF

• Clock / Second Chance: Uses a circular queue and a usage bit per entry to approximate LRU with low overhead.