Cache Design

Review of Cache Terms

• Direct Mapped: Only one location for an item at an index.
• Associativity: Multiple locations for an item at a given index
• Write Through: Stores update the cache and the RAM
• Write Back: Stores go to RAM only when the cached item is about to be replaced

Techniques to Reduce Miss Penalty

1. Multi-level caches - add slower, but larger caches between CPU and RAM
2. Victim cache (victim buffer)
   1. Place the most recently removed item from the cache in a small, fast buffer
   2. Fully associative = check every location in the buffer
   3. If there is an L1 cache miss, check this buffer often while checking L2

Reducing the Number of Misses

• Types of Misses
  • Compulsory: First access to a cache block
  • Capacity: The cache cannot hold all of the needed blocks
  • Conflict: Too many blocks map to the same location
• How to fix
  • Compulsory: Increase the cache block size
    • Hardware/Software prefetching
  • Capacity: Get a larger cache
  • Conflict: Increase associativity (makes the cache slower)

Techniques to Reduce the Number of Misses

• Compiler Optimizations
• Loop Interchange
  • Run through an array in the way the data is stored in RAM.
• Blocking (Tiling)
  • Operate on a subsection of the data to maximize the locality