Cache映射的三种方式，全相联(Fully Associative cache)，直接相连(Direct-Mapped cache)，组映射(k set-associative cache)

Terminology

Cache line

Data is transferred between memory and cache in blocks of fixed size, called cache lines or cache blocks. When a cache line is copied from memory into the cache, a cache entry is created. The cache entry will include the copied data as well as the requested memory location (called a tag).

Fully associative cache

内存块可以放入任意cache line, 所谓见缝插针。

优点：缓存利用率/命中率高
缺点：寻找cache时需要遍历

Direct-Mapped cache

每个内存块只能被放入固定的cache line. 例如主存有M块, cache line有C个。
那么内存块n会被装入cache line index = n mod C

优点: 寻找cache时，可以直接从内存块地址计算出cache line。 缺点: 同余的内存块争抢cache line, cache 利用率和命中率低(conflict miss)

k Set-Associative cache

cache line 被划分为k个一组, 内存块通过直接相连映射到cache line组，而在组内使用全相连。

e.g. cache line 被分为 G = C/k 组。
内存块n 对应cache set index = n mod G
在该组的k个cache line 中，可以选择任意位置存放。

优点：前面两种的trade-off 缺点：conflict miss 仍然存在