L12 Cache Memories

Source: https://www.bilibili.com/video/BV1iW411d7hd?p=12

Cache memories（高速缓存存储器）

cache memories are small, fast SRAM-based memories managed automatically in hardware.

Hold frequently accessed blocks of main memory.

CPU looks first for data in cache.

Typical system structure: CPU chip <-> I/O bridge <-> Main memory

通用的缓存结构 General Cache Organization (S, E, B)

               E = 2^e lines per set（行）
 --------------|--------------
/                             \
-------------------------------  \
|    |    |    |    |    |    |   |
-------------------------------   |
|    |    |    |    |    |    |   |
-------------------------------   |
|    |    |    |    |    |    |   S = 2^s sets（组）
-------------------------------   |
|    |    |    |    |    |    |   |
-------------------------------   |
|    |    |    |    |    |    |   |
-------------------------------   /

高速缓存存储器完全由硬件管理，因为我们要高校地查找，所以我们必须以非常严格且简单地方式去组织高速缓存存储器。

我们从这个结构图可以看出来，每个缓存含有 S 个组，每个组内有 E 行，每一行由一个 B = 2^b 字节的数据块组成，另外存在一个有效位（valid bit），指示这些数据位和数据块实际上是存在的；另外可能还存在标签位（tag bits）用于指示缓存查找。

缓存大小 C 是块中包含的数据字节数，显然 C = S * E * B.

Cache Read

对于一串地址，在 x86-64 中是 64 位，其被划分为 t + s + b 位（从高到低），其中 t 位 tag、s 位 set index、b 位 block offset.

E = 1 的高速缓存称为直接映射高速缓存（direct mapped cache）

首先，提取 s 位 set index，找到对应组。

其次，检查 t 位标签位，查看是否有匹配的行，当然有效位应指示存在；否则称未命中，做一些操作。

最后，根据 b 位找到对应字节。

此处未命中需要做这样的操作：从内存中读取值，修改该行有效位（valid bit）为 1，并覆盖该行 tag 的值。

If tag doesn't match: 旧行被撤除并被替换 old line is evicted and replaced.

换句话说，每一行管内存一部分，tag 构成对其中一部分中数据的散列（hashing），因为此时 E = 1，所以无论是 tag 未匹配，还是匹配但 v = 0，显然都是未命中，于是将内存对应数据塞进来。【这个设计一个 tag 作为散列太神秘了，可能要配合什么东西？老师和书上关于这部分都讲得不清楚，hashing 是我自己总结的，不过事实上来看这个 hashing 就是很简单的取头的 hashing function，实现很简单。故而这里最神秘的是 t + s + b 的高低位排序，换成 s + t + b 未命中率会更低吗，我不知道，但应该会更高，这是因为空间局部性，所以 s 放在中间是一个比较好的想法，不过 t + s + b 是最好的吗，我不知道。】

另外还需注意这个 offset，这表明读取的是块内相对的位置的字节。【这个 offset 的机制也没怎么讲清楚，说明白是块内 2^b 个字节中具体的某个字节不好么，非要强调一个 offset 搞得我还以为要加减什么东西，无言了。】

E > 1 的高速缓存称为 E 路组相连高速缓存（E-way set associative cache）

特别地，如果 S = 1，则称为全相连高速缓存（fully associative caches）。

首先，提取 s 位 set index，找到对应组。

其次，检查 t 位标签位，在 E 行中并行匹配。

如果匹配上了并且有效位指示存在，则称缓存命中。

未命中还是将内存写入，如果未匹配上，则优先写入空槽，之后按顺序写入行；如果有效位指示无效，则更改有效位并写入。

最后，根据 b 来查块内相对位置的字节。

No match:

One line in set is selected for eviction and replacement.

Replacement policies: random, least recently used (LRU), ...

分为这两类情况，是因为 hashing 的存在就会使得 E 的多少有个权衡（trade-off），E 小会导致冲突次数增加，也就提高了未命中率，E 大则 hashing 匹配就对算法提出了要求，不过在 E 不过大时，这样去要求复杂的算法还是很值得的，故而 E = 2 的情形是很值得一提的。

另外缓存应保持数据一致性，即写入数据时，当因为未命中，缓存要踹下这部分数据时，数据应回写至内存以保证数据一致，也即数据真的被写入（更改）了，而不是停留在缓存还被覆盖（这意味着写入数据丢失）。【此行对应下文 write-back】

另外此处有学生问到参数设计，只能说缓存设计如此复杂，但每一步又很简单，是需求导致的设计，所有参数都必须适当，E 的大小已说明。S 或 B 过大显然会扩大缓存，这就降低了缓存的性能，但 S 过小或 B 过小必然导致其余的部分过大，进而导致未命中率增加。

What about writes?

Multiple copies of data exists.

L1, L2, L3, Main Memory, Disk.

What to do on a write-hit?

Write-through (write immediately to memory)

Write-back (defer write to memory until replacement of line)

需要一些修改位来说明是否向下写了 Need a dirty bit (line different from memory or not)

What to do on a write-miss?

暂时写入到缓存，之后再向下写 Write-allocate (load into cache, update line in cache)

Good if more writes to the location follow.

直接写入内存，不写入到缓存 No-write-allocate (writes straight to memory, does not load into cache)

Typical

Write-through + No-write-allocate

Write-back + Write-allocate

两者各有利弊，一个是花费时间但保留内存和其局部性，一个是时间短但摧毁了单独读入或单独写入的局部性（二者混在一起了）。

Intel Core i7 Cache Hierarchy (39:46)