Architecture

Each cache line comes with tag that describes the position in the main memory. It often consists of the leading portion of the memory address of the data.

Cache lines are grouped into sets, in which the cache lines across the sets are called ways. The memory address is used to map the position of the cache: the first 26 bits as the tags, following 6 bits as the set numbering, and last 6 bits as the offset within the data.

• Fully associated cache only has one set and uses entirely the tag to find the data, and direct-mapped cache only has one way so that there's only one way.

• Temporal locality: data is likely to be accessed in a close temporal succession.
• Spatial Locality: data that is physically close in memory is likely to be accessed around the same time.

It motivates the data-oriented programming in which the data that is accessed simultaneously are stored contiguously, since it enables efficient caching.

On the contrary, object-oriented programming stores the data in each object separately.

Replacement Algorithm

The implementation is dependent on the usage characteristic of the cache.

It is used when a cache miss occurs. Commonly used policies includes:

• Least Recently Used (LRU)
  • Full LRU: Track the order of recency
  • Tree-Based Pseudo LRU: Track it in a binary tree
  • Not Recently Used: Use just 1 and 0
  • Quad-Age LRU: Use age between 0 and 3
• Least Frequently Used
• Random Replacement
• First-In Frist-Out
• Most Recently Used
• Adaptive Replacement

When data is in the cache, on write hit:

• Write Through: write directly to the memory
• Write Back: write on flush based on the dirty bit.
  • It can be problematic when a process is ran asynchronously.

When the data is not in the cache, write miss:

• Write-Allocate: load the data into cache and write to the cache.
• No-Write-Allocate: write directly to the main memory.