前几天在看论文时看到这样一段话：We observe that a program often exhibits several different memory access patterns with different objects or at different phases, and they benefit from different Cache configurations. For example, sequential accesses fit a small directly mapped Cache with a Cache line size of multiple consecutive data elements, while accesses with good locality but large working sets fit a relatively large set-associative Cache.

这学期在上计算机体系结构课的时候老师提到过Cache的三种映射方式是direct mapping，set associative和fully associative。但是当时只是单纯记住了这个知识点，并没有理解，因此看上面这段话看的一头雾水，Cache里的数据存储形式是怎样的？不同的workload为什么会受益于不同的Cache映射方式？带着这些疑问，我去查了一些资料复习了一下顺便写了这篇笔记。

首先来明确一下Cache是什么，本文中的Cache指的是CPU高速缓存，是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层，仅次于CPU寄存器。其容量远小于内存，但速度却可以接近处理器的频率。

其实在遥远的PC-AT/XT和286时代，CPU是没有Cache，直接访问内存的。那后来为什么要在CPU寄存器和内存之间设置一个CPU缓存呢？这是因为CPU访问寄存器和内存的延迟差距太大了。

那我们现在看看在set associative的情况下如何寻找cache line，在L1 Cache中一共有2^14个cache line，而又因为是4-way associative，因此一共有2^14/2^2=2^12个组，也就是说我们需要12位Index来找到是哪个组。同时我们同样需要6位Offset来在64B的cache line中找出是哪一个Byte。

那64位的地址我们已经用掉了6+12=18位，剩下的46位我们将其作为标记位（tag）

CPU在访问Cache时，先根据index找到set，然后将组内的所有cache line对应的tag和地址中的tag部分对比，如果其中有相等的就说明缓存命中也就是找到了所需数据。

对比一下direct mapping和set associative，我们可以发现其实direct mapping也可以看做成set associative中set大小为1的情况。那有大胆的同学可能会想，如果把set大小增大，变成整个Cache会怎么样呢？这种情况我们就称为fully associative。

在fully associative的情况下，因为整个Cache就是一个组，那么我们就不需要Index来寻找是哪个set了，因此地址只剩下了tag和offset。因为在访问Cache时高速缓存电路必须并行匹配许多tag，想要构造又大又快的fully associative cache是十分困难且昂贵的。因此fully associative cache只适合做小容量的cache，如TLB（又是一个坑）。

最后我们回到刚开始的那段话，为什么顺序访问适合具有多个连续数据元素的cache line大小的小型direct mapped cache，而具有良好局部性但较大工作集的访问适合相对较大的set associative cache呢。这是因为direct mapped Cache能够利用顺序访问的局部性，将连续数据元素映射到同一个cache line中，取了一个元素相当于取了相邻连续的多个元素。具有良好局部性说明程序访问内存会比较集中在某一个范围内，因此最好用大一点的Cache把这块内存尽量装下，此外，工作集较大说明程序运行时访问内存范围较大，如果是direct mapped cache很有可能会出现thrashing，因此最好使用set associative cache。

关于CPU Cache这次先讲这么多，后面会（视心情）更新其他关于存储相关的知识笔记。（可能也会更新一些生活方面的？）

[1] 维基百科编者. CPU缓存[G/OL]. 维基百科, 2023(20231213)[2023-12-13]. http://zh.*********.org/w/index.php?title=CPU%E7%BC%93%E5%AD%98&oldid=80104215.[2] http://cs.brown.edu/courses/csci1310/2020/assign/labs/lab4.html

[3] http://developer.arm.com/documentation/den0024/a/Caches

[4] Bryant, Randal E., and David R. O'Hallaron. Computer Systems: A Programmer's Perspective. 3rd ed., Pearson, 2016.