Lectures‎ > ‎


Cache Memory

Cache Memory sits between the CPU and main memory (RAM) and provides fast access to recently access data.

Cache memory is small but very fast. Most memory requests can be served through the cache without going to main memory.

The cache works because of the Principles of Locality exhibited by executing code:
  - Temporal Locality: A data value accessed now will likely be accessed again in the near future.
  - Spatial Locality: If a data value is accessed, it is likely that a nearby data value will be accessed in the near future.

Examples of Temporal Locality:
  - Code and data accessed in a loop

Examples of Spatial Locality:
  - Code segments with out branches: if you access a word at PC, you know the next word will be PC + 4
  - Iterating through an array
  - Accessing data inside a struct

Cache Concepts:
  - Hit - the data value at the requested address is in the cache
  - Miss - the data value at the requested address is no in the cache
  - Hit Rate - give a sequence of address requests, how many are hits (hits / requests)
  - MIss Rate - (1 - Hit Rate)

Main Issues in cache design:
  - Structure of cache
  - How to determine if the data you need is in the cache
  - How to replace an existing element in the cache if needed
  - Usually a cache holds data as blocks (4 bytes, 8 bytes, etc)
  - We will work with a block size of 4 bytes (1 word)
  - The tag of the address is used to determine if value is in cache (upper bits of address)

Types of Cache Designs:
  - Direct Mapped Cache
  - Fully Associate Cache
  - Set Associate Cache

Direct Mapped Cache
  - One place (set) in cache for each address/block
  - Simple calculation from address
  - Assume 4 byte blocks and 8 blocks in cache
  - To find cache set: set = address % 8
  - Or: set = (address >> 2) & 0b111
  - Tag: tag = address >> 5

Fully Associate Cache
  - Every slot in cache available for an address/block
  - Tag = address >> 2
  - To determine a hit, compare the tag of the request will all of the tags in the cache
  - To replace, approximate the slot that has been used least recently

Set Associate Cache
  - Middle ground between direct mapped and fully associative
  - Divide cache into "ways"
  - Each set has multiple ways.
  - Address now has a tag, set number, and byte offset
  - Consider a 2-way cache with 4 sets (8 total blocks)
  - set = address >> 2 & 0b11
  - tag = address >> 4