Cache

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

Overview

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.

Locality

• 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.

---

Efficiency

• Cache hit: $h=N_c/(N_c+N_m)$
  • Nc 表示 Cache 完成存取访问的总次数
  • Nm 表示主存完成存取访问的总次数
• 平均访问时间: $t_a=h{t}_c+(1-h)t_m$
  • tc 表示命中 Cache 时的访问时间
  • tm 表示命中主存时的访问时间
  • $t_a=\frac{t_c}{e}$
• Cache 访问效率：$e=\frac{t_c}{t_a}$

Details

• 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 Cache

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.

Direct-Mapped

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

Fully Associative

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

Set-Associative

• 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.

Links

• Page Cache