缓存机制

原理

注意！！！！

缓存的工作机制：

由一个内存地址，判断其是否在缓存中

考虑一个计算机系统，其中每一个存储器地址有$m$位，形成$M=2^m$个不同的地址，这样一个机器的高速缓存被组织成一个有$S=2^s$个高速缓存组cache set的数组，每个组包含E个高速缓存行cache line，每个行由一个$B=2^b$字节的数据块block组成，在行中，一个有效位valid bit指明这个行是否包含有意义的信息，还有$t=m-(s+b)$个标记位tag bit，它们唯一地标识存储在这个高速缓存行中的块。

$\textcolor{red}{一般而言，高速缓存的结构可以用元组(S,E,B,m)来描述}$

$\textcolor{red}{高速缓存的容量：C=SEB}$

直接映射

根据每个组的高速缓存行数E，高速缓存被分为不同的类，每个组只有一行的高速缓存称为$\textcolor{red}{直接映射高速缓存}$。

组相连

每个组set有多个行，每个行为一路way，但是需要依次组中的所有行来匹配标识位。

全相联

没有组索引位，全都是一个组，地址只被划分成一个标记位和一个块偏移。

组相连缓存示例

考虑一个64GB内存大小的计算机系统，L1 cache容量32KB，使用64组8路组相连方式，每个缓存行64字节

$C=SEB=64864=32768BTYE=32KB$

• 内存64GB，共需要36位比特来进行寻址

• 64组，则需要占用6个比特

• 每个缓存行有64字节，也需要6个比特

• TAG位则需要$36-6-6=24$个比特

• 在至于缓存在哪个路中，则需要遍历

+---------------------+---+-------+------+
|        TAG          | V | index |offset|
+---------------------+---+-------+------+

CPU读数据——缓存miss——填充缓存

当CPU发起一个地址访问操作时，会首先向缓存发出一个地址，比如：0x8000200E4，对应二进制位为1000 0000 0000 0000 0010 0000 | 000011 | 100100

缓存拿到这个地址后，首先拿出index位段的比特，这里是000011，确定组索引

然后遍历这个组中所有的路，对比有效位V和TAG位，这里的TAG是寻址地址的高24位，也就是1000 0000 0000 0000 0010 0000，将其与每一路的TAG位进行对比，如果存在V有效并且TAG一致，则为缓存hit，hit之后根据offset位段获取对应字节即可

否则为缓存miss，这里考虑miss的情况

当缓存miss时，CPU向主存进行内存访问，其访问单位为64字节，也就是一个缓存行，CPU将获得主存上对应内存地址（以64字节对齐的那一整个缓存行大小的区域）的内容DATA和地址都发给缓存

缓存根据索引位index的位段确定组编号，在对应的组中使用某种策略（如LRU等）对某个缓存行进行替换，即将数据填充到缓存行内，将地址的高24bits填充到TAG中，V填充为1，标记为有效，并将对应offset的字节发给CPU

到此完成一次CPU读数据操作

缓存替换策略——Replacement Algorithm

LRU——Least Recently Used

最近最少使用算法：当缓存行满且需要加载新数据时，最近最长时间未使用的数据将被替换

Full LRU

缓存需要跟踪访问数据的顺序，由于缓存行只可能在同组之内，即不同的路之间随机放置，那么每一组需要维护一个组内不同路的访问顺序

如果以4路组相连为例，4路表示一个组内有四个缓存行，访问的数据可以是这四个缓存行之一，那么这四个缓存行的访问顺序可以是路数的阶乘，如4路则是$4!=24$，24需要5个比特位来表示

通常，对于具有n种排列方式的缓存，每组需要的LRU位的数量是n阶乘的对数（以2为底）

当访问数据并且发生缓存命中，相关组中的LRU 位将更新以反映新顺序

如果缓存已满且发生缓存未命中，则需要对LRU位进行解码，逐出该顺序中的最后一个缓存行，并更新LRU位以反映新顺序

优势：当最近使用的数据可能很快再次使用时，表现较好

劣势：开销相当大，使用较少

Tree-Based Pseudo LRU

使用二叉树树来近似LRU

树的结点都表示一个比特位，树的叶子表示一组缓存行

每个位的值表示最近使用的数据的路径：

• 0表示左子树较新
• 1表示右子树较新

占用的LRU位数为路数减一

当访问缓存行并且请求地址在缓存行中，算法会沿着根到该行的路径更新树位，以将其标记位最近使用的数据

当请求的缓存行不在缓存中，树算法会沿相反方向（比如一个结点是0，表示左侧较新，但是我去右边较久的地方）遍历树，以查找最近最少使用的数据逐出，更新树位数

Not Recently Used

最近未使用算法：在每个缓存行增加一个位NRU，为0表示相关缓存行最近使用过，为1表示最近未使用过

最开始，所有NRU都为1，表示都未使用过，访问某个缓存行时，将其标记为1，表示最近使用过

发生缓存未命中时，系统查找组中第一个仍为1的缓存行，将其逐出，加载新数据，并将NRU位翻转为0，标记其最近使用过

如果发生缓存未命中，并且该组中只有一个缓存行的NRU值为1，则该行中的数据被替换，其NRU位置0，并且该组中其他所有的缓存行NRU位都翻转为1，表示现在该组中的其他缓存行都被视为最近未使用过

在某组中所有NRU位为0的情况下，该组中的所有缓存行的NRU位都被翻转为1

Quad-Age LRU

四倍年龄LRU算法：通常用于具有更高关联性的缓存，如L3缓存，每个缓存行都有额外的两位AGE，表示其与同一组中其他缓存行相比的相对年龄，年龄较低的缓存行意味着比年龄较高的缓存行访问更近

最初，所有缓存行的AGE位均置为1，发生缓存命中时，根据其当前年龄进行修改，值2或3将变为1，值1将减少为0

如果在访问，命中或未命中后，没有年龄为3的缓存行，则所有缓存行的年龄加一，重复此操作，直到找到一个年龄为3的缓存行

当缓存未命中时，第一个年龄为3的缓存行将被逐出，新数据被写入，AGE被更新为1

LFU——Least Frequently Used

最不常用算法：跟踪数据访问频率，并将最长使用的数据保留在缓存中

因此需要为每个缓存行维护一个频率计数器，该计数器表示该缓存行进行读写的次数

当需要逐出数据时，将替换频率最低的行

RR——Random Replacement

随机替换算法：随机选择任何缓存行进行替换

优势：适用于不可预测系统，实现简单

劣势：在相关性较强的系统中表现不佳

FIFO——First-In First-Out

先入先出算法：需要逐出数据时，将缓存行按加载顺序逐出，无论访问次数和访问频率

优势：简单实现，开销最小

劣势：某些情况下，性能不佳

MRU——Most Recently Used

最近使用算法：需要逐出数据时，将最近使用的数据逐出（LRU的相反操作）

优势：适用于旧数据比新数据更可能被访问的系统（比如大文件的重复访问）

劣势：其他情况性能不佳

AR——Adaptive Replacement

自适应替换算法：根据工作负载的访问模式，以及每种算法的实际命中率和未命中率在两种算法之间动态平衡

实现方式是将缓存集分组，通常分为三组。

比如第一组用LRU，第二组用MRU，第三组自适应，根据策略将其改为上述两种算法之一