概述
在CPU发展中，除了优化指令流水线提高指令的运行效率之外，另一种提高CPU处理速度的思路则是分级存储，通过增加缓存（Cache），来提高对存储器的访问速度，减少读写造成的时间等待。从486处理器，就开始使用片上Cache了。因为随着CPU的发展，现在速度已经远远高于DRAM结构的主存储器，而对于SRAM来说，速度远远高于DRAM，但是成本非常高昂。对于SRAM来说，单位容量的价格大约是DRAM的数百倍，而DRAM的价格是磁盘的数百倍，速度是磁盘数十万倍。
在程序执行过程中，适用于这样一种局部性原理：如果某个数据项被访问，在不久的时间之内将会被再次访问，并且在这个数据周围的数据项，往往与数据相关，也很与可能被用到。这分别被称为是时间的局部性和空间的局部性。利用这个原理，可以将计算机存储设备进行分级。最靠近CPU一级被是基于SRAM的Cache，然后是DRAM组成的主存，最低一级则是磁盘。利用局部性原理，将可能用到的数据项提前从低级的慢速存储器搬移到高层次的存储器，就能实现提高存储器访问速度的效果。但是对于数据搬移的策略，涉及到命中率的问题。如果CPU能够在最高级的Cache中找到需要的数据，那么就实现了Cache的命中，如果没有命中，则发生了缓存缺失，就要付出一定的缺失代价，需要耗费较多的时间将下层的数据逐级搬移到上层的Cache中。一般来说现在的X86 CPU中都有三级Cache，典型的一个数值（正在使用的电脑）是L1 Cache 265KB，L2 Cache 1MB，L3Cache 8MB，三级的命中率能够达到90%以上。逐级增大的Cache可以在上层Cache被使用时在下层制定一些策略来减少缓存缺失的发生。Cache分为数据Cache和指令Cache等，使用合理的Cache管理策略可以大大的提升CPU的读写效率。
Cache管理
Cache管理作为商业机密，很难获得现代Cache的具体操作方法。但是有这样几个共同存在的问题：
1.Cache块应该放在那里
2.Cache块如何查找
3.Cache缺失处理
4.Cache回写和替换如何处理
Cache块的分配
一种简单的办法是使用直接映射，根据这个块在主存中的地址，为每个主存地址分配到Cache中的一个确定地址。典型的方法是使用
\[(块地址) mod (Cache中的块数)\]为了映射方便，往往会取Cache的块数为2的整数次幂
另外一种叫做全相联，一个块可以被放置在Cache中的任何位置，但是这样因为存储器中的地址可能与Cache中的任何一个块相关联，所以当要查找到一个指定的块，就要对所有的项全部检索，这样就会造成极大地时间开销，如果使用硬件并行设计，则会产生很大的硬件开销。因此这种方法，仅对块数较少的Cache较为有效。
介于直接映射和全相联之间的是组相联，对于组相联，每个主存中的块，在Cache中有固定的n个位置可以放置，被称为n路组相联Cache。
\[(块号)mod(Cache中的组数)\]更高的关联度往往能够带来更低的缺失率，但是高关联会带来更高的查询时间。
Cache块的查找
Cache中需要增加一组标记用来表示块对应的主存地址信息，例如，对于直接映射，只需要包含地址的高位。
\[[标记 | 索引 | 块内偏移地址]\]索引表示一个组，表一用来和选中组的块来比较选择快，块内偏移地址是块中被请求的数据地址。如果Cache总容量不变，提高关联度就增加了每组中的块数，也就增加了查找时间。
在全关联的Cache中，只有一组，所以没有索引，整个地址都要和Cache的标记比较，直接映射中，只需要索引就可以快速的访问Cache，因为每一项只能对应Cache中唯一的块。具体选择全关联还是组关联，要考虑硬件和时间要求。
Cache的缺失
当缺失发生时，控制单元要能够检测到缺失的发生，然后从主存中取回需要的数据；如果命中，则不需要处理缺失。相对于命中，缺失发生的时候需要一些额外的工作。缺失处理需要两部分共同完成：处理器控制单元和进行初始化主存访问和重新填充Cache的独立控制器。Cache缺失发生时会引起流水线阻塞，我们需要等待主存操作完成时，整个处理器中所有可见部分都被冻结，如果是具有乱序执行功能的处理器，则能够进行一些其他指令的执行。具体的处理步骤如下
1.把程序计数器（PC，在x86中通常是IP）的原始值（当前带有增量）送到存储器中
2.通知主存进行一次读操作，并等待访问完成
3.写Cache项，将主存取回的数据写入Cache中相应的部分，并将地址高位写入标记位
4.返回指令执行第一步，重新取指令，这一次指令存在于Cache中。 数据缺失的处理是类似的，发生缺失时，CPU阻塞，直到取回数据后响应。
Cache块的替换
Cache块的替换选择仅发生在组相联和全相联的CPU中，对全相联的情况，替换时仅有唯一的选择。最常使用的是LRU（最近最少使用法），这样做需要追踪组中的数据项使用情况：例如一个两路组相联的Cache，可以在每组中单独保留一位，表示哪一项被访问过。另外还有随机替换，会被使用在TLB缺失的情况，即随机选择一块候选块进行替换。在实际使用中在较低相联度（典型是2路到4路），中实现LRU需要极高的代价，通常仅仅近似实现，例如使用两位来记录最近最少使用的块。在关联度更高的情况下，所有算法的缺失率都有所降低，这时候使用不同的策略进行替换的差别就会逐渐变小，在这种情况下使用随机替换和近似LRU的性能相比，可能随机替换更好一些。
Cache的回写操作
如果只将数据回写到Cache，那主存的值将会与Cache中不同，最简单的办法就是同时将数据写入主存和Cache，这是写直达法。这样简单有效，但是会耗费大量的时间。解决方法是写缓冲。当数据等待写入主存，先把他放入到缓冲中，数据写入缓冲和Cache中后，CPU可以继续执行。另一种方法是写回机制。仅将将要被替换的块回写到主存中，可以提高性能但是会增加复杂度。如果要写回到低层次的存储器中，因为超高的延迟，只能使用写回法，对于高层次的存储器，写直达会比较方便而且缺失代价小。
Cache优化策略
降低缺失率、降低缺失代价、缩短在缓存中的命中时间
增大块大小以降低缺失率。
较大的块会充分利用空间局部性的优势，但是较大的块会降低了缓存中的块数，当多个块竞争同一个组的时候，就会发生冲突缺失。块大小和缺失率之间的关系是一个U型曲线。
增大Cache容量降低缺失
增大缓存是最为直接的降低缺失率的方法，但是更大的Cache会带来更长的查找时间，增加功耗和成本。
提高关联度降低缺失率
增大相联度可能会提高缺失率，但是会延长命中时间，并且提高缺失代价。
采用多级缓存降低缺失代价
既要提高缓存速度又要提高缓存容量减少缓存和主存储器之间的差距，增加第二级的缓存，第一级快到能够与时钟周期匹配，第二级则大到减少主存的访问次数，从而降低实际缺失代价。对于第二级缓存，命中数比第一级要少得多，所以重心更加偏向于增大容量减少缺失。
使读取缺失优先级高于写入缺失，降低缺失代价。
在直写法中，如果写入缓冲区包含读取缺失时需要的更新值，存储器的访问会非常复杂，可能需要大量的额外检查，因此最简单的方法是让读取缺失一直等待到写入缓冲区为空。
结语
基于DRAM的存储器越来越难以跟上处理器的速度，想要加快存储的读写速度就要使用局部性原理，利用高速的缓存来缩短延时时间，现代的计算机中各个层次都证明了分级存储的正确性，存储系统的设计越来越重要，是决定了未来系统性能增长的焦点。
参考文献
[1]John L. Hnnessy, David A. Patterson. Computer Architecture:A Quantitative Approach,Fifth Edition [M]. Morgan Kaufmann,2011.
[2]John L. Hnnessy, David A. Patterson. Computer Organization and Design：The Hardware/Software Interface，Fourth Edition [M]. Morgan Kaufmann,2004.
