Cache

Hit or Miss

• Hit: Data needed is already in cache
  • Hit rate: fraction of memory accesses that hit
  • Hit time: Time to access cache
• Miss: Data is not in cache
  • Miss rate: 1 - hit rate
  • Miss penalty: Time to replace cache block + hit time
• Hit time << miss penalty
• Average access time: hit rate $\times$ hit time + miss rate $\times$ miss penalty

Memory to cache mapping

• Cache block/line: unit of transfer between memory and cache
• Block size is usually 1 or more words (e.g. 16-byte block → 4-word block)
• Direct mapped cache: cache index is LSB of block number
  • Block numbers ending with 00 will only be stored in cache at index 00 etc.
  • Mapping fn: (blk number) modulo (no. of cache blocks) i.e. take the least significant n bits
  • Tag number: block number excluding the cache index bits (Tag = blk number // no. of cache blocks)
  • Mapping overview: [31 : N+M] Tag, [N+M-1 : N] Index (in cache), [N-1 : 0] Offset (within block)
    • Cache block size $2^N$ bytes, with $2^M$ cache blocks
    • Offset: N bits, Index: M bits, Tag: 32-(M+N) bits

Cache Miss

Read Miss Policies

• Compulsory miss or cold start miss or first reference miss
  • The first time a block is accessed, it must be brought into the cache
• Conflict miss or collision miss or interference miss
  • When several blocks are mapped to the same place in the cache, and the wrong block is currently there
• Capacity miss (Only for fully associative cache)
  • When blocks are discarded from cache because it is full/cannot contain all the blocks needed

Write Miss Policies

• Write allocate
  • Load the complete block of memory into cache, then continue with write policy
• Write around
  • Write directly into main memory only

Cache Write Policy

• Write-through cache
  • Write to both cache and main memory (good for when there are very few write operations)
  • Write buffer keeps this fast
• Write-back cache
  • Write to main memory only when cache block is replaced (evicted)
  • Additional bit (dirty bit) indicates whether data is changed, if data is not changed, don’t need to write back to memory