CPU Cache是如何映射与寻址的？
CPU Cache的组织结构
Cache与内存地址映射
直接映射
全相联映射
组相联映射
Cache寻址方式
VIVT、VIPT、PIPT(补充)
尾语
往期推荐
哈喽，大家好，我是呼噜噜，在上一篇文章我们介绍了突破计算机性能瓶颈的利器CPU Cache，今天我们来聊聊CPU Cache的组织结构及其它是如何映射与寻址的？
CPU Cache的组织结构
CPU Cache的组织结构：CPU Cache被划分成多个组Set，每个Set中还可以有多个行Cache Line，需要注意的是Cache Line是CPU Cache中的基本缓存单位，也有人叫它块（Block），也就是说它每次读写不是一个字节的去读写，而是以Cache Line为单位，一块块地去读取
一般主流的 CPU 的 Cache Line 大小是64 Byte，当然也有其他大小，在Cache块比较小的时候，这时的命中率很低，随着块大小的增加，空间局部性起作用，命中率会快速提高；如下图：这种增加趋势在某一个最佳块大小处达到最大值。当到达顶峰以后，命中率随着块大小的增加反而会逐渐降低。因为当块大小非常大时，进入Cache中的许多数据可能根本用不上，同时随着块继续增大，时间局部性会逐渐失去作用
而 CPU Line 又由有效标志Valid、标志Tag、数据块Data这3个部分组成，其中data是真正要来缓存一片连续内存地址中的数据，而tag是用来查找Cache Line的标志，存储这片连续数据的公共地址，valid表示当前缓存的数据是否有效，也可以用来协助查找Cache Line
可以参考下图：
Cache与内存地址映射
我们知道高速缓存的速度要远远快于主存(内存)的速度，但Cache的容量却是远远小于主存，相较于主存的价格，缓存则昂贵的多
另一方面CPU Cache是需要缓存内存中的数据，无论对Cache数据读取还是写入，CPU都需要知道访问的内存数据，对应于Cache上的哪个位置，而由于Cache容量不够，无法做到Cache与内存地址一一对应
那么Cache是如何与内存地址进行映射的？
其实CPU Cache主要有3种的实现方式：
直接映射(direct-mapped)，也就是每个 组Set只有一个Cache Line，选中Set之后不需要和Set中的每个Line进行比对全相连映射(fully associative)，即只有一个Set，所以这个Set中包含所有的Line 组相连映射(set-associative )， 有多个Set，每个Set有多个Line；需要注意的是，组相连也会被称为路Way，比如6路组相联，表示每个Set有6个Line
直接映射
直接映射会在内存块和缓存块之间建立起固定的映射关系，也就是内存中的某个块总是映射到Cache的一特定块上
在Linux内核中，并非总使用基于我们更熟悉的页来当页缓存。内核的早期版本使用了块缓存，来加速文件系统，提高系统性能
我们这里以8块主存和4块(行)为例，具体如下图所示：
通过上图，我们可以发现B0块和B4块主存只能映射到Cache的第0块，B3块和B7块只能只能映射到Cache的第3块，其他内存块同理
其实相当于给主存空间按照Cache Line的大小(也就是Line的行数)来进行分区，每个内存块编号需要与Cache Line的大小取模，得到固定的映射位置即区内编号，映射到与它区内编号相同的Cache Line上
可以发现直接映射的优点：查找效率高，硬件设备简单，地址变换速度快，但是它也有缺点：由于每个主存块只有一个固定位置可存放，即使Cache中别的Line空着也不能占用，无法充分利用Cache空间，这样冲突概率较大
如果冲突了，这多个内存块会不断地交替装入固定的映射Cache Line中，导致缓存命中率降低，所以直接映射适合大容量Cache
全相联映射
全相联映射 主存的数据可以放在任意一个Cache line中，映射方式比较灵活，Cache的利用率高，块冲突的概率低，因为只有当所有的Line都被占满后才会出现冲突
但是另一方面，访问缓存时，每次都要和全部Line中的内存进行比较，速度低延迟高是它无法避免的缺点，因此适合于小容量Cache采用
组相联映射
组相联映射是直接映射和全相联映射的折中方案，吸取2者的优点，尽量避免2者的缺点，组间采用直接映射，组内采用全相联映射，即主存块存放到哪个组Set是固定的，存到Set内哪一个
Cache Line是灵活随意的
当查找缓存时，不再需要全部进行遍历，只需先查到cache的组号，然后在那一组内，进行小范围遍历。这样冲突概率较小，同时命中率较高，所以这种方式在现代的处理器中得到了广泛的应用
Cache寻址方式
通过前文的阅读，相信大家都对CPU Cache的组织结构和Cache与内存地址映射方式有所了解，而Intel多数处理器的 L1 Cache 都是32KB，8-Way 组相联，Cache Line 是 64 Byte，我们以这个参数为例，来看看Cache是如何寻址的？
因为Cache Line是最小单位（64Bytes），所以可以得出Cache Line的条数 = 32KB /64=512，每一Way的Cache Line条数 = 512 / 8 = 64(也就是每一个Set的Cache Line条数)
那么我们可以得到，每一Set的内存大小 = 64 x 64 = 4096B=4KB，是不是很熟悉，这不正是一个内存页page的大小嘛！本文前面用块来划分内存，和页一样都是内存划分的方式，在操作系统中，页是固定大小的存储单元，而块是可变大小的存储单元
首先我们得知道内存地址如何被分解？内存地址被分成了3部分：tag, set index和block offset
tag：与Cache Line中的tag匹配,内存地址的前24bit set index：set索引，用来寻找定位Set，内存地址中间的6个bit，正好能查询2^6=64个line block offset：块偏移量，用来寻找Cache Line里data中的内存数据，内存地址最后6位
那么Cache寻址的具体方式，我们可以将其分为3个步骤：
先根据set index来找到对应的Set 接着根据tag在上一步步找到的set中找到对应的 Cache Line,如果找到且对应的有效位valid为1，表示缓存命中，反之无论其中的tag和Cache Line里的数据内容是什么，CPU 都不会管这些数据，而是会直接访问主存，重新加载数据(当然这里涉及到缓存一致性的问题，比较复杂，先挖个坑，本文暂不讲解)，那如果没找到，说明当前发生cache缺失，即cache miss最后根据 block offset在上一步找到的Cache Line的data中找到对应内存的数据
笔者这里再吐血画了张图，帮助大家更加直观了解Cache寻址的具体方式
VIVT、VIPT、PIPT(补充)
最后再介绍一下几个概念，就是Cache寻址时，可以根据物理地址，也可以根据虚拟地址，或者二者结合起来查找
VIVT（Virtually Indexed, Virtually Tagged ）表示index和tag都是采用虚拟地址 VIPT（Virtually Indexed, Physically Tagged ）表示index采用虚拟地址，tag采用物理地址，一般用于 L1 CachePIPT（Physically Indexed, Physically Tagged ）表示index采用物理地址，tag采用物理地址，一般用于 L2 Cache
尾语
本文先后介绍了CPU Cache的组织结构，Cache与内存地址映射的3种方式，以组相联Cache来讲解Cache的寻址方式，画图太耗心神了，先到这了，后面我们继续更新Cache的缓存一致性，提高代码性能等难点
参考资料：
《Cache: a place for concealment and safekeeping》
https://blog.csdn.net/qq_38768922/article/details/78737284
http://staff.ustc.edu.cn/~hdrq/jsjzcyl/text/chapter5/sec3/part4/r1.htm
往期推荐
图解ReentrantLock的基石AQS源码-独占锁的获取与释放
全文完，感谢您的阅读，如果我的文章对你有所帮助的话，还请点个免费的赞，你的支持会激励我输出更高质量的文章，感谢！
扫描下方二维码，加作者微信，共同成长，追求卓越，我们下期再见!