自制一块 CPU Cache！
共 3766字，需浏览 8分钟
·
2021-11-20 00:20
象山公园
理想情况下，我们希望拥有无限大的内存容量，这样就可以立刻访问任何一个特定的机器字，但我们不得不认识到有可能需要构建分层结构的存储器，每一层次容量都要大于前一层次，但其访问速度也要更慢一些。
早在计算机刚被发明出来的时候，那些计算科学界的先驱们就已经预测到之后的计算机结构。
他们觉得以后的程序员们肯定都会幻想着拥有无限容量甚至是无限数量的快速存储器。
但是理想总是很丰满，现实很骨感。在实际的计算机系统中，并不可能拥有程序员所幻想的那种存储器。
1
事实上，存储器层级结构的提出是存在重要背景的。计算机由于其使用者的特殊性，所以往往都会存在一些局域性原理。
局域性原理意味着大多数的计算机程序不会均衡的去访问所有代码和数据，计算机的执行并不是一个等概率事件。
所以往往可以利用计算机程序的局域性原理去在性能和成本上对系统结构做出取舍和折中。
下图是一个典型的存储器层次结构，可以看出为了实现性能和成本上的折衷，存储器层次结构会由不同速度、不同大小的存储器组成。
这些不同的存储器拥有不同的大小和速度，在存储器系统中也位于不同的地位。
一般而言，存储器级别离处理器越远，速度越慢，容量越大。而越接近处理器，容量就越小，速度越快，每字节的成本也就越高。
科学家是想实现一种存储器结构，能够每字节的成本与最便宜的存储器相当，而速度则与最快速的级别相当。这看起来的确是一个非常划算和高性价比的买卖。
除此之外，一般这样的存储器结构中，还存在这样一种特征。那就是低层次存储器中的数据一般是上一级存储器中数据的超集。
之所以这样设计，是因为我们知道存储器性能跟处理器性能之间存在巨大的差距。这也是程序员们渴求快速存储器的原因。
当在缓存中找不到某一个字时，就需要从结构层次更低的存储器中去寻找这个字。这样一来，再结合空间局域性原理，我们就能够很容易的通过对缓存块的标记来快速的从存储器中找到程序所需要的数据。
所以在设计存储器的层次结构时，需要对缓存的安排做出重要的决策。
这些决策会决定哪些数据块会可以放在缓存中。这就是计算机教材里常说的组相联、全相联的概念。
具体的描述可以看我这篇故事文：半夜，滴滴司机问我会LRU吗？ 放几张精美图帮助大家回忆回忆。
直接映像，主存单元中的区块与缓存中内存块的关系是固定的，主存中的内存块只会存放在高速缓存存储器中的相同块号。
因此，只要主存地址中的主存区号与缓存中的主存区号相同，则表明访问缓存命中。
全相联与直接映像就是两个极端，一个只能整个区块进行对应，一个就允许任意主存的块调入高速缓存存储器中任意的块。
2
从原理上来看，要缓存一份只读数据其实是一件很容易的事情，因为本身缓存和主存储器中备份是一致的。
问题难就难在缓存的写入。如何保证缓存和存储器中的备份数据一致是一个难点。一般而言也会有缓存写入的策略:
直写缓存
它在更新缓存中数据的同时，会同步写入主存储器，更新双方的数据
回写缓存
它只更新缓存中的数据，但当缓存中的数据块将要被替换时，再将其复制回主存储器
当然了，由于缓存和主存储器本身就会存在性能和速度的问题，所以在写入的时候还需要依赖写缓冲区。
需要写入主存储器的数据应该先被丢到缓冲区中，这样就可以及时释放缓存，而不需要等待主存储器的写入时间。
说到这，既然存在缓存和主存储器同步的问题，那么其实就必然存在缓冲未命中的问题。
这就涉及到一个指标，缺失率。其实就是未命中率。也就是目标数据能够在缓存中找到的概率。
一般而言，缓存未命中有一下三种场景：
强制缺失，意味着这是第一次对某个数据块的访问，这个数据块开始不在缓存中，需要从主存中将该数据调入缓存。 容量缺失，顾名思义就是由于容量不足，导致某些在程序运行期间需要的数据块无法一次性放入缓存，需要下一次被调用，从而就会导致容量缺失。 冲突缺失，当缓存置换策略不是全相联策略时，那么当多个数据块被映射到同一个块，那么对不同数据块多访问就会混杂在一起。这个数据块就有可能被放弃，下一次再被调入，这时候就会发生冲突缺失。
3
因此，为了解决不同场景下所带来的缓存缺失问题，需要从几个方面去优化缓存结构，来获得更高的命中率。
增大缓存块以降低强制缺失
这应该是最容易优化的一个点，由于数据块可能第一次访问时不在缓存中会导致强制缺失。
那么理论上增大缓存块，在一个块中存放更多的数据，由于空间局域性，就可以在一定程度上降低强制缺失。
但是若块的大小过大，却会增大容量缺失和冲突缺失的概率。所以选择合适的块大小是一个值得权衡的问题。
增大缓存以降低容量缺失
这同样也是一个显而易见的可以用来降低容量缺失的方法。但是缓存过大可能会影响数据的命中时间，同时也会造成成本的增加。
提高相联程度以降低冲突缺失
很明显，当缓存块的映射策略不同时，相联程度越低，所产生的冲突缺失也就越大。
因此可以通过采用相联程度更高的策略来降低冲突缺失。
采用多级缓存以降低缺失代价
可以发现，存储器层次结构的主要特点，其实就是在处理器与主存储器之间存在多个速度不同大小不一的缓存。
这些多级缓存存在的目的就是为了在靠近处理器那头能够跟上处理器的高频速度，在靠近主存储器那头获得接近主存的容量。
原因就在于多级缓存能够在不同级别的层次中分别降低不同类型的缺失。这样使得总体的缺失率最低。
提高读取缺失优先级
我们在上面说到过，一般缓存向主存储器写入的时候，中间会使用一个写缓存区。
当需要向主存储器中写入数据时，会先写入缓存区，之后等待合适时机再将缓存区中的数据写回主存储器。
而在这个期间，可能某个数据刚写入缓存区，还没写入到主存储器，这时候又需要访问该数据。
这个时候，若读取优先级低于写入优先级，那么此时会优先执行写入逻辑，则需要等待缓冲区写入主存，再进行数据的读取。
这很明显不是一件高效的事情。所以往往会设置读取优先级高于写入优先级。
这时，无论写缓冲区是否正在执行写入逻辑，都会优先处理读取逻辑。
使用虚拟地址
虚拟地址是操作系统为每个进程所分配的存储空间的地址，与实际的物理地址需要通过地址转换和映射操作。
所以对于使用物理地址的缓存，则需要先将处理器给出的虚拟地址转换成物理地址，然后再根据缓存中的物理地址来访问数据。
这样的实现需要对处理器虚拟地址到访问存储器物理地址之间的转换，使得缓存命中时间变长，从而不利于缺失率的降低。
所以单从这点上来看，缓存若是使用虚拟地址，则可以节省地址转换的时间。但是使用虚拟地址也并不是一件一劳永逸的事情。采用虚拟地址会导致一系列的问题。
比如由于每个进程都有自己的虚拟地址空间，所以在切换进程时，会出现不同的进程可能会有相同的虚拟地址，但这两个相同的虚拟地址却对应不同的物理地址。
因此在切换进程时，需要同步切换缓存，刷新缓存数据，在这个期间不可避免的也会产生大量缺失。
当然这样的问题是可以解决的，可以将每个进程的pid与缓存块绑定，在命中时检查即可。
4
虽然这几种方法不能给我们优化出一个很完美的具备层次结构的存储器，但是给予了我们优化缓存的方向和思路。
事实上，若引入更多的优化度量指标，比如缓存带宽和功耗等。还可以引申出更多的优化方法。
常见的还有10种高级的缓存优化方法。这里就不一一细讲，感兴趣的可以深入理解一下。
一、 采用小而简单的第一级缓存，用以缩短命中时间、降低功率
二、 采用路预测以缩短命中时间
三、 实现缓存访问的流水化，以提高缓存带宽
四、 采用无阻塞缓存，以提高缓存带宽
五、 采用多种缓存分组以提高缓存带宽
六、 关键字优先和提前重启动以降低缺失代价
七、 合并写缓冲区以降低缺失代价
八、 采用编译器优化以降低缺失率
九、 对指令和数据进行硬件预取，以降低缺失代价或缺失率
十、 用编译器控制预取，以降低缺失代价或缺失率
计算机科学家们老早就意识到存储器没办法直接满足程序的使用，所以在计算机出现的早期就已经研究出这种存储器层次结构。
后来又逐渐引入了虚拟存储器以及真正高性能的缓存，但是一直以来关于存储器层次结构的基本概率和理论却没有本质的变化。
如果将计算机比作人类的大脑的话，那么存储器就相当于是记忆细胞。
缓存技术一种能够大幅度提升计算机性能的技术，在历史上已经得到了充分的证明。
但是在真正研究出更强大的缓存之前，存储器层次结构依然是解决问题最有效和性价比最高的方案。
今天的文章就到这，期待你的点赞、关注、转发。
推荐阅读：