块替换策略

块替换策略是高速缓存设计的一个重要方面。当不命中时，必须将相应的主存块取入高速缓存，相应地，要把其中已有的某一块替换出去。若高速缓存内有无效块，则替换是不成问题的。对于直接映射高速缓存，只有1个块可供替换。对于相联映射型的高速缓存，主要有随机和最近最少使用两种替换策略。最近最少使用策略利用了时间局部性，可能实现较高的命中率，但当需要追踪的块较多时，实现起来比较复杂。

简介在高速缓冲存储器（Cache）中，块是指Cache存储空间分为多个大小相同的存储空间，是基本的 Cache 存储单位。一个 Cache 块能够存储若干字节的数据。与主存空间中页相对应。Cache工作原理要求它尽量保存最新数据，当从主存向Cache传送一个新块，而Cache中可用位置已被占满时，就会产生Cache替换的问题。块替换策略是指将Cache中最少使用的块替换出去，使得访问的页不在Cache中在的次数为最少，即主要目标获得最高的命中率。块替换策略与块映射策略密切相关。

替换算法最不经常使用算法

LFU（Least Frequently Used，最不经常使用）算法将一段时间内被访问次数最少的那个块替换出去。每块设置一个计数器，从0开始计数，每访问一次，被访块的计数器就增1。当需要替换时，将计数值最小的块换出，同时将所有块的计数器都清零。这种算法将计数周期限定在对这些特定块两次替换之间的间隔时间内，不能严格反映近期访问情况，新调入的块很容易被替换出去。

最近最少使用算法

最近最少使用(Least Recently Used, LRU )替换策略能够依据Cache块的使用情况，选择离最近时间点最近而最少被使用的Cache 块进行替换这种策略较好地体现程序局部性而使得系统 Cache 丢失率较小。这种方法实现方法众多有计数器法、寄存器栈法及硬件逻辑比较对法，其中计数器法实现 LRU 替换策略最为简单，因此这种替换策略得到了广泛的使用，现代多核处理器依然沿用了这种替换策略1。这种算法保护了刚调入Cache的新数据块，具有较高的命中率。LRU算法不能肯定调出去的块近期不会再被使用，所以这种替换算法不能算作最合理、最优秀的算法。但是研究表明，采用这种算法可使Cache的命中率达到90%左右。

随机替换算法

最简单的替换算法是随机替换。随机替换算法完全不管Cache的情况，简单地根据一个随机数选择一块替换出去。随机替换算法在硬件上容易实现，且速度也比前两种算法快。缺点则是降低了命中率和Cache工作效率。Cache命中率除了和替换算法有关外，还与Cache的容量及块的大小有关。

先进先出算法

先进先出策略(FIFO)：最先替换进入 Cache 的块将最先被替换出。这就导致被多次命中的块很可能是最先调入 Cache 的块，而这个块将被优先替换，不符合局部性规律。

块映射策略Cache的容量很小，它保存的内容只是主存内容的一个子集，且Cache与主存的数据交换是以块为单位的。为了把信息放到Cache中，必须应用某种函数把主存地址定位到Cache中，这称为地址映射，或块映射。

当需要将来自内存的新数据块装入高速缓存时，由块映射策略决定它的存放位置。根据块在高速缓存内的位置，块映射策略可分成如3类：

直接映射，每个块在高速缓存中只能有1个位置。该位置通常由求模运算得到，即：高速缓存内块号=块地址(mod 高速缓存中块数)。

全相联映射，块可以放在高速缓存中的任意位置。

组相联映射，高速缓存分为若干个组，块先映射至组，在组中的位置任意。块向组的映射通常也采用取模运算。块地址中对应于组号的若干位称为索引。若组中有n 块，则称高速缓存是n路组相联的。

高速缓存对每个块都设立1 个标志域，其中包括块地址和该地址是否有效的信息。为了实现快速访问，在相联映射型高速缓存中，总是同时查找所有的标志。

高速缓冲存储器高速缓冲存储器（Cache）位于中央处理器与主存储器之间，对程序员透明的一种高速小容量存储器。高速缓冲存储器简称高速缓存。它是存储器层次结构的最顶层，其下层是容量相对较大和访问时间较长的主存储器。在配备有高速缓存的计算机中，每次访问存储器都先访问高速缓存，若欲访问的数据在高速缓存中，则访问到此为止；否则，再访问主存储器，并把有关数据取入高速缓存。这样，如果大部分针对高速缓存的访问都能成功，则在保持主存储器容量不变的前提下，访存速度可接近高速缓存的存取速度。高速缓存的设置是所有现代计算机系统发挥高性能的重要因素之一。高速缓存的工作机制体现了局部性原则。所谓局部性，是指程访问代码和数据的不均匀性，它包括：时间局部性：如果某位置已被访问，则该位置很可能在短时间内还要再被访问；空间局部性：如果某位置已被访问，则其邻近位置很可能还要被访问。因此， 只要程序有较好的访存局部性，高速缓存就能发挥作用。

命中率高速缓存的组织及对高速缓存的访问都是以行或块为单位的，通常1行包括1个或多个字。行也是高速缓存与主存储器交换数据的最小单位。访存时，若能在高速缓存中找到所需数据，称为高速缓存命中，否则就是不命中。命中次数与访存总次数的比率称为命中率，而不命中次数与访存总次数的比率称为不命中率。显然，不命中率 = 1 - 命中率。命中时的访问时间 (包括确定是否命中的时间)称为命中时间，不命中时，将主存块替换入高速缓存并提供给中央处理器所需的时间称为不命中损耗。不命中时的访存时间是命中时间加上不命中损耗。命中率是高速缓存性能的一个重要指标，它不仅依赖于硬件实现 ，而且与应用程序有关。但是，命中率是与硬件速度无关的参数，从而不能单独用于高速缓存的性能评估。较好的标准 是平均访存时间：

平均访存时间 = 命中时间 不命中损耗 不命中率

平均访存时间的单位可以是绝对的(如25 ns)，也可以是相对的(如2个时钟周期)。尽管把块变大有助于提高命中率，但同时也增加了不命中时的传送时间，所以块的大小应有利于缩小平均访存时间。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学