Caches

Overview

A cache is a storage device that acts as a staging area for data objects stored in a larger, slower device. The process of using a cache is known as caching.

A cache that only holds instructions is called an i-cache. A cache that holds only program data is called a d-cache. A cache that holds both instructions and data is called a unified cache.

Formalization

Consider a computer system where each memory address has $m$ bits. A cache for such a machine is defined as a tuple $⟨S,E,B,m⟩$ where

• $S$ refers to the number of cache sets;
• $E$ refers to the number of cache lines per set;
• $B$ refers to the size (in bytes) of the cache block found in each line.

Each cache line also contains a valid bit indicating whether or not the line contains meaningful information and $t$ tag bits that uniquely identifies which cache block is stored in the cache line.

The parameters $S$ and $B$ induce a partitioning of the $m$ address bits into the following three fields:

The $s$ set index bits for an index into the array of $S$ sets. The $b$ block offset bits give the offset of the word in the $B$-byte cache block, provided the valid bit is set and the tag bits match.

The capacity of a cache $C$ is usually defined as $C=S\cdot E\cdot B$. Notice this excludes the overhead of the valid and tag bits.

Cache Misses

When a data object can be retreived from a cache as opposed to a larger, slower device, we have what is called a cache hit. Otherwise we have a cache miss.

An empty cache is called a cold cache. A cache miss against a cold cache is called compulsory misses or cold misses. These are no longer relevant once the cache is warmed up.

When there is a miss for some data object $d$, the cache at level $k$ fetches the block containing $d$ from the cache at level $k+1$, possible overwriting an existing block if the level $k$ cache is already full.

Replacement Policies

The process of overwriting an existing block is known as eviction. The evicted block is sometimes referred to as a victim block. The decision about which block to evict is governed by the cache's replacement policy.

Least Recently Used

A least recently used (LRU) replacement policy replaces the cache line that was last accessed the furthest in the past.

Least Frequently Used

A least frequently used (LFU) replacement policy replaaces the cache line that has been referenced the fewest times over some past time window.

Placement Policies

A placement policy determines where to place a block it has retrieved from level $k+1$ into level $k$.

Restrictive placement policies may lead to conflict misses, in which the cache is large enough to hold the referenced data objects, but because they map to the same cache block, the cache keeps missing.

A working set refers to a set of blocks frequently accessed by some portion of a program. A capacity miss is a cache miss that occurs because the working set is larger than the capacity of the cache.

Thrashing refers to any situation in which a cache is repeatedly loading and evicting the same sets of cache blocks.

Direct-Mapped Caches

A cache $⟨S,E,B,m⟩$ where $E=1$ is called a direct-mapped cache.

Set Associative Caches

A cache $⟨S,E,B,m⟩$ where $1<E<C/B$ is called a set associative cache.

Fully Associative Caches

A cache $⟨S,E,B,m⟩$ where $E=C/B$ is called a fully associative cache.

Performance

Cache performance is evaluated with a number of metrics:

• The miss rate refers to the fraction of memory references that miss.
  • $\text{\# misses}/\text{\# references}$
• The hit rate refers to the fraction of memory references that hit.
  • $1-\text{miss rate}$
• The hit time is the time it takes to deliver a word from the cache to the CPU.
  • This includes the time for set selection, line matching, and word retrieval.
• The miss penalty refers to any additional time incurred because of a cache miss.