1. cache背景知识
为什么的CPU内部需要cache单元？
??主要的原因是CPU的速度和内存的速度之间严重不匹配，Cpu处理速度极快，而访问内存慢，cache在这个背景下就诞生了。设计人员通过在CPU和内存之间建立一个缓冲区，提高访问的速度。
??建立cache的好处在于：假设CPU和内存之间没有cache，那么CPU每次访问内存，都要从访问速度较慢的内存中读取，这无疑是很浪费cpu的性能的；但是如果在CPU和内存之间设立一个高速的cache，虽然第一次读，都要从内存中读取，但是第一次读完成之后，可以把数据放到这个高速cache里；那么第二次读，我就直接从高速cache里取数据就行，这个高速cache的速度基本上是和CPU匹配的，比内存速度快很多。这样的，CPU第2次，第3次去读这个数据的时候，就得到加速的效果了。这也是设计cache的最初的初衷。
??cache一般是集成在CPU内部的RAM，相对于外部的内存颗粒来说造价昂贵，因此一般cache是很小的RAM，但是访问速度和CPU是匹配的。此外，如果访问数据在cache命中的话，不仅仅能提速，提高程序的性能，还能降低功耗（cache命中的情况，不需要去访问外部的内存设备，自然会降低功耗）。
2. 典型的cache架构
??下图是一个典型的cache架构。CPU在访问内存的时候，首先发出的虚拟地址，并把这个虚拟地址发送给TLB和cache。TLB是一个用于存储虚拟地址到物理地址转换的小缓存，处理器先使用EPN（effective page number，有效页帧号）在TLB中进行查找最终的RPN（Real Page Number，实际页帧号）。如果这期间发生TLB未命中（TLB Miss），处理器需要继续访问MMU并且查询页表。假设这里TLB 命中（TLB Hit），此时很快获得期望的RPN，并得到相应的物理地址（Physical Address，PA）。
??同时，处理器通过高速缓存编码地址的索引域（Index）可以很快找到相应的高速缓存行对应的组。但是这里的高速缓存行的数据不一定是处理器所需要的，因此有必要进行一些检查，将高速缓存行中存放的标记域和通过虚实地址转换得到的物理地址的标记域进行比较。如果相同并且状态位匹配，那么就会发生高速缓存命中（cache hit），处理器经过字节选择与对齐（byte select and align）部件，最终就可以获取所需要的数据。如果发生高速缓存 未命中（cache miss），处理器需要用物理地址进一步访问主存储器来获得最终数据，数据也会填充到相应的高速缓存行中。上述描述的是VIPT（Virtual Index Physical Tag 虚拟索引物理标记）的高速缓存组织方式。这个也是经典的cache运行模式了。
3. Cache映射方式
3.1 直接映射方式
??出于对成本的考虑，cache大小相对于主存来说会小很多。因此**cache只能缓存主存中极小一部分数据**。如何根据地址在有限大小的cache中查找数据呢？硬件采取的做法是对**地址进行散列**（可以理解成地址取模操作）。上图是CPU从0x1234地址读取一个字节的例子：
- 图中一共有8行cache line，cache line大小是8 Bytes。可以利用地址低3 bits寻址8 bytes中某一字节，我们称这部分bit为 offset。
- 8行cache line，为了查找能够覆盖所有行，需要3 bits查找某一行，我们称这部分bit为 index。
- 现在如果有两个不同的地址，其地址的bit[3 - 5]如果完全一样，那么这两个地址经过硬件散列之后都会找到同一个cache line。所以，当找到cache line之后，只代表我们访问的地址对应的数据可能存在这个cache line中，但是也有可能是其它地址对应的数据。所以，又引入 tag array的概念，tag array和data array一一对应。每一个cache line都对应唯一一个tag，tag中保存的是整个地址位宽去除index和offset使用的bit剩余部分。
??tag、index和offset三者组合就可以确定一个唯一的地址了。因此，当我们根据地址中index位找到cache line后，取出当前cache line对应的tag，然后和地址中的tag进行比较，如果相等，这说明cache命中。如果不相等，说明当前cache line存储的是其它地址的数据，这就是cache缺失（cache miss）。在上图中，我们看到tag的值是0x48 ，和地址中的tag部分相等，因此在本次访问会命中（cache hit）。
tag的引入，解答了之前的一个疑问？ “为什么硬件cache line不做成一个字节？” 因为这样会导致硬件成本的上升，因为原本8个字节对应一个tag，现在需要8个tag，占用了很多内存。
从图中看到tag旁边有一个valid bit，这个bit用来表示cache line中数据是否有效（例如：1代表有效；0代表无效）。当系统刚启动时，cache中的数据都应该是无效的，因为还没有缓存任何数据。cache控制器可以根据valid bit确认当前cache line数据是否有效。所以，上述比较tag确认cache line是否命中之前还会检查valid bit是否有效。只有在有效的情况下，比较tag才有意义。如果无效，直接判定cache缺失。
从图中看到8byte的cache line 旁边有一个D(dirty) bit，这一个dirty bit代表着整个cache line是否被修改的状态。
直接映射方式缓存的优缺点：
（1）优点
直接映射缓存在硬件设计上会更加简单，因此成本上也会较低。
（2）缺点
会造成chche的颠簸。
原因如下：
假设memory的大小为0xc0，根据直接映射缓存的工作方式，可以画出主存地址0x00-0xC0地址对应的cache分布图。
??可以看到，地址0x00-0x40/0x40-0x80/0x80-0xc0地址处对应的数据每一个都可以对应整个cache。现在就出现了一个问题，如果试图依次访问地址0x00、0x40、0x80，cache中的数据会发生什么呢？
- 首先由于0x00、0x40、0x80地址中index部分是一样的。因此，这3个地址对应的cache line是同一个。当首次访问0x00地址时，cache会缺失，然后数据会从主存中加载到cache中第1行的cache line。
- 当继续访问0x40地址时，依然索引到cache中第0行cache line，由于此时cache line中存储的是地址0x00地址对应的数据，所以此时依然会cache缺失。然后又要从主存中加载0x40地址数据到第1行cache line中。
- 同理，继续访问0x80地址，依然会cache缺失。这就相当于每次访问数据都要从主存中读取，这种情况下cache的存在并没有对性能有什么提升。
访问0x40/0x80地址时，就会把0x00地址缓存的数据替换。这种现象叫做cache 颠簸（cache thrashing）。
3.2 组相联映射方式
路（way）的概念：将cache平均分成多份，每一份就是一路。本小节我们依然假设cache size为64 Bytes ，cache line size是