Cache

Jun 18, 2023

• What is a “cache-friendly” code? - Stack Overflow

We have t, s and b

• A cache is a set of 2^s cache sets
• A cache set is a set of E cache lines
  • E is called associativity
  • If E=1, it is called “direct-mapped"
• Each cache line stores a block
• We need to add tags to the cache, which supply the rest of the address bits to let us distinguish between different memory locations that map to the same cache block.

• With temporal locality, the idea is that an instruction or data item that has been recently accessed will likely be re-accessed soon in the future.
• With spatial locality, the idea is that if a program accesses memory at address x, it will likely soon access memory near x.

• Cache hit: $h = N_{c} / (N_{c} + N_{m})$
  • Nc 表示 Cache 完成存取访问的总次数
  • Nm 表示主存完成存取访问的总次数
• 平均访问时间: $t_{a} = ht_{c} + (1-h)t_{m}$
  • tc 表示命中 Cache 时的访问时间
  • tm 表示命中主存时的访问时间
  • $t_{a} = \frac{t_{c}}{e}$
• Cache 访问效率：$e = \frac{t_{c}}{t_{a}}$

• cache block: The basic unit for cache storage. May contain multiple bytes/words of data

• cache line: Same as cache block. Note that this is not the same thing as a “row” of cache.

• cache set: A “row” in the cache. The number of blocks per set is determined by the layout of the cache (e.g. direct mapped, set-associative, or fully associative).

• tag: A unique identifier for a group of data.

• valid bit: A bit of information that indicates whether the data in a block is valid (1) or not (0).

• index: the index of the position in cache block

• Cache placement policies - Wikipedia

Look-Aside Caching is a pattern of caching where the input of a cacheable operation is used as the key for looking up any cached results from a prior invocation of the operation when given the same input.

Only 1 choice of where to place a block.
Single cache line pre set (n x 1 column matrix)

• 主存总容量：$2^{S}$ （块）x $2^{W}$ （字）
• Cache 总容量：$2^{r}$ x $2^{W}$
• CAM $2^{r}$ 行，每行 S 位 Tag（选主存），需遍历
  随便放，用 Tag 区分， Tag 是内存地址

• The cache is divided into groups of blocks, called sets.
• Each memory address maps to exactly one set in the cache, but data may be placed in any block within that set.