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:
    • Nc 表示 Cache 完成存取访问的总次数
    • Nm 表示主存完成存取访问的总次数
  • 平均访问时间:
    • tc 表示命中 Cache 时的访问时间
    • tm 表示命中主存时的访问时间
  • Cache 访问效率:


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


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

Fully Associative

  • 主存总容量: (块)x (字)
  • Cache 总容量: x
  • CAM 行,每行 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.