Cache运行与冲突替换

Cache运行流程

如下图所示，当我们对一个地址进行访存操作时，我们按照前文所述的地址结构进行匹配。

首先我们根据地址中的组号（set），查找到Cache中的对应组（图中绿色箭头所指的部分）。之后我们将标记（tag）与Cache中该组所有行的tag进行比较（即图中左部比较的部分）。

如果Cache中某行的tag能够匹配，则说明Cache中有对应的数据块，即命中（hit）。当命中时，处理器直接对Cache进行对应的访存操作，可以通过地址中的offset，查找Cache存储的block中的offset，从而找到该地址对应的数据信息。

如果Cache中没有对应的数据块，那么就是不命中（miss）的情况。当不命中时，缓存从主存中取出包含该地址的块，并需要放入缓存中。假如Cache中该地址所属组的所有行均已被占用，那么就需要覆盖一个现有的块，这一过程通常称为替换/驱逐（eviction）。在本实验中，我们假设当Cache的块被换出时，被换出块中如果发生数据更改则此时写回主存。

这里我们就会遇到一个问题，当需要替换时，如何在Cache中选择被替换的块？我们的目的是使得发生替换的情况尽可能少，从理论上来说，我们应当选择现有块中将来不再使用的块，或者选择现有块中经过最长时间才会使用到的块，因为这最大程度上推迟了下一次发生替换的时刻，我们可以证明，如果我们能够预知程序未来将要访问的地址的话，上述的替换策略是最优的，这一策略被称为最佳置换算法（OPT，OPTimal selection）。

事实上，我们很难达到预知未来的要求，我们的替换选择往往通过已有的命中情况来推算，因此我们介绍以下三种常见的替换算法。

常见替换算法

先进先出法（FIFO，First-In-First-Out），顾名思义，即选择最早装入的块进行替换。它的实现比较简单，不需要记录各个块的访问情况，比较容易实现，开销小。但是这种算法没有依据访存的局部性原理（最早调入的块有可能是经常访问的块），因此不能提高Cache的命中率。

FIFO策略的实现：

• 缓存的每一块都设定一个计数器，初始时均为0。
• 当某块被装入或被替换时该块的计数器清为0，而同组的其它各块的计数器均加1，
• 当需要替换时就选择计数值最大的块被替换掉。

最低使用频率法（LFU，Least-Frequently Used），即替换出使用频率最低的块，又称最不经常使用算法。

LFU策略的实现：

• 缓存的每一块都设定一个计数器，初始时均为0。
• 当某块被装入或被访问时该块的计数器加1。
• 当需要替换时就选择计数值最小的块被替换掉，如果计数值相同则替换出装入时间更早的块。

最近最少使用法（LRU，Least-Recently Used），含义为替换出近期用的最少的块。它与LFU的区别在于它更加关注各个块在近期的访问情况，即近期的权重会更高。LRU需要随时记录Cache中各块的访问情况，以便确定近期最少使用的块。LRU比较复杂，一般来说我们采用简化的方法，只记录每个块最近一次使用的时间，替换时选择距上一次使用经过时间最长的块。

LRU策略的实现：

• 缓存的每一块都设置一个计数器，初始时均为0。
• 访问命中时，所有块的计数值与命中块的计数值进行比较，如果某块计数值小于命中块的计数值， 则该块的计数值加 1；如果该块的计数值大于命中块的计数值，则数值不变；最后将命中块的计数器清为0。
• 访问未命中，需要替换/装入时，则选择计数值最大的块被替换/装入，其计数器清为0，而其它的计数器则加1（除了初始装入之外，计数值是不会出现相等情况的，可以思考一下为什么）。

分块技术与实验提示

分块技术

分块技术是一项很有趣的技术，它可以提高循环中的时间局部性。分块的大致思想是将一个程序中的数据结构组织成大的块（在这里，“块”指的是一个应用级的数据组块，而不是我们之前介绍的高速缓存块）。这样构造程序，使得能够将一个块加载到高速缓存中，并在这个块内进行所需的所有读和写，然后丢掉这个块再加载下一个块。

分块会使得代码更难阅读和理解，由于这个原因，它最适合优化编译器或者频繁执行的库函数。这项技术学习和理解起来还是很有趣的，因为它是一个通用的概念，可以在一些系统上获得极大的性能收益。

实验提示

我们将以 $s=5,E=1,b=5$ 结构的Cache为例，结合大小为 $32\times 32$ 的矩阵，来初步分析在矩阵转置中应用分块等技术可以优化的方面，希望能够启发同学们的思路。我们假设矩阵A和B的地址都是block大小对齐的。

最常规的转置思路即，遍历A的所有行，将其存放到B的对应列中。

void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            B[j][i] = A[i][j];
        }
    }
}

我们来结合Cache的结构分析一下转置过程中产生的缺失（miss）情况。首先block大小 $B=2^b=32$ 字节，即可以存放 $8$ 个int型值；$E = 1$ 为直接映射，即Cache中每组只有一行；$S = 2^s=32$ ，即分为 $32$ 个组，整个Cache可以存放 $32\times 8=256$ 个int型值。对应到矩阵中，我们可以发现，矩阵的前8行就正好能够填满我们的Cache。结合下方矩阵B的示意图，我们可以进行进一步的分析。