Cache的原理

冯诺依曼结构的基本特征：指令和数据存在一个存储器中，但在实际应用中采用了哈弗体系结构，将IM和DM分离

处理器和DRAM的速度差距越来越大，需要一个又大又快的存储器，但大和快实际上是相互制约的。于是采用多层结构，营造出又大又快的效果，确保处理器需要的大多数数据放在更快的层中

实际上cache是一个广义的概念，可以认为主存是磁盘的cache，而CPU内cache又是主存的cache，使用cache的目的就是伪造出一个容量有低层次存储器（如磁盘）那么大，而速度又有寄存器（如通用寄存器）那么快的存储器，简单来说就要让存储单元看起来又大又快。

存储访问的局部性原理

空间局部性和时间局部性

时间局部性：刚刚访问过的存储单元可能不久还会被访问（指令按序存放，地址连续，循环程序段或子程序段重复执行）

空间局部性：被访问过的存储单元的临近单元可能不久被访问（连续存放，数组元素重复，按需访问）

对于告诉缓冲处理器，其存在的前提是：

  1. 单级存储系统中，主存的存储速度与CPU的速度严重不匹配，造成CPU资源的浪费
  2. 程序运行时访问内存存在明显的局部特征：两个局部性
  3. 存在比主存DRAM速度更快的存储电路

CPU体系结构

Cache的原理

Cache：CPU和主存之间的一容量较小的高速缓存，存放最活跃的程序块和数据

Block：Cache一次和主存交换数据获取的单位，内存在逻辑上按照Cache Block划分并映射到Cache的相应位置

Cache是存储器的子集，处理器访问Cache和主存使用同一个地址，Cache没有功能的意义，主要目的是为了提高性能，降低延迟。Cache的特点是同时存储数据和地址。

为了利用空间局部性，块的大小必须大于一个字

image-20231216112512956

Cache在初始情况下是空的，需要从主存中加载数据，如果数据在Cache中，则称命中，否则为缺失，命中率/缺失率对CPU的运行速度有显著影响。

Cache的基本结构

  1. 存储单元：保存数据，存取数据，一般由SRAM构成，以block为单位
  2. 地址机构：地址标记tag，一般为数据在内存中的地址出去cache块的地址后的地址高位
  3. 替换机构：有效位，记录block的使用情况，用于标记块中数据是否有效/是否为空

对于标记位，其位数就是除去索引到组、块、字、字节后余下所需以确定地址的位数。

Cache的基本参数

M：地址空间的大小（字节），M=2mM=2^m

G：Cahce访问的粒度大小（字节）：一次能访问的最少字节数

C：Cache的容量（字节），G=2cG=2^c

B：Cache块的大小（字节），B+2bB+2^b

a：相连度

Cache的映射机制

Cache是数据存放的地方，为了提高访问速度，但是数据到哪里去拿，这就需要一个映射机制。

内存到Cache的基本映射机制有三种：直接映射、全相连、组相连

  • 直接映射：每个主存块映射到Cache中的固定块中，块是唯一的
  • 全相连：每个主存块映射到Cache中的任意块中，不同运行情况会导致在不同的块中
  • 组相连：介于直接映射和全相联之间的情况，将Cache中的组分为多个组，每个主存块映射到固定的组中，在组中存储在哪一个块是任意的

Cache索引数据库的顺序：组、块、字、字节

直相连

每个主存块映射到Cache中的固定块中，块是唯一的

主存中的某一块J 映射到Cache中的固定块K，K＝ J mod M，其中M是Cache包含的块数

对于Cache的地址索引，将在主存的位置分为两部分，一部分是由Cache块的位置本身就能确定的，另一部分是无法确定的部分。就像对于直相连Cache中的一块，可能在此的数据的地址低位都是相同的，区别只在于高位。故把高位也存储在Cache中，Cache中同时存储数据和高位地址。

一个块中的存储的数据，就是高位地址（每个字相同）+每个字的数据，存储的地址部分称为标记位。此外，再用一个有效位代表此块中是否有有效数据/是否为空。

  • 优点：实现简单，只需要利用主存地址中的高位地址，与Cache中的标志位进行比较，即可确定是否命中
  • 缺点：映射关系不灵活，每个主存块只能固定对应的Cache块，会使得Cache有较大空闲。新的也无法写入而必须替换，导致Cache利用不充分

组相联

映射关系：Cache分成K组，每组分成L块。主存的块J和Cache 的组I满足I = J mod K的映射关系。

实际上主存与Cache都分成K组，主存每一组内的块数与Cache一组内的块数不一致，主存组M内的某一块只能映射到Cache组M内,但可以是组M内的任意一块。

image-20231216175747127

在读取N路组相联（一个组中有N块）Cache时，可以很方便锁定到组，同时和组中N块的tag进行比较，需要N个比较器。

数据的访问与比较是并行进行的。

全相联

全相联相当于只有一个组。主存分为若干Block，Cache按同样大小分成若干Block。主存中的某一Block可以映射到Cache中的任意一Block。

全相联的tag位数即为主存的块数。

  • 优点：对Cache的使用有最大的灵活性。Cache空闲时可以直接选择新块写入，已满时按照最近最少原则进行替换
  • 缺点：在执行Cache操作时，需要和所有的tag进行比较。电路的成本和复杂度都很高，不适宜大容量Cache采用

组相联是全相联和直相连的折中

Cache的替换策略

缺失

缺失的种类：

  1. 强制缺失：第一次访问某块是总是缺失的，局部性很差时会成为主要的缺失类型

    Cache的大小B和“预选”

  2. 容量缺失：Cache太小，容不下所需要的所有块

    Cache的大小B

  3. 冲突缺失：不同tag的块想要存到同一个块中

    Cache的相连度a

缺失损失：当Cache缺失时，处理器必须等待数据装入Cache后才能继续访问Cache。

  • 指令缺失：由于取指不再Cache中，故此时PC=PC-4，再进行阻塞，直到指令被取入Cache中
  • 数据缺失：对于非乱序执行处理器，处理器阻塞直至取出数据

取出的时间=第一个字的延迟时间（存储器访问）+块剩余部分的传送时间

缺失处理

缺失数据块中各字按照顺序装入Cache，再从Cache中访问所请求的字

  • 尽早重启：缺失数据块中按照各字的顺序进入Cache，于是一旦当所请求的字进入Cache，处理器即访问该字，剩余字再惊蛰传送至Cache
  • 请求字优先：所请求的字先装入Cache，处理器立即访问该字，控制机构接着按照请求字的下一个字，再从块的起始字开始请求

image-20231216181638261

替换策略

  1. 最近最少使用法LRU：记录每一个数据块的相对使用情况，最近没有被使用过的块被替换
  2. 先进先出法FIFO：最先装入数据的块被替换
  3. 最小使用频率法LFU：记录一个块的使用频率，使用次数最少的被替换
  4. 随机法RAND

替换算法由硬件电路实现，因而应以简单、便于硬件实现为依据

LRU

使用计数器进行实现

原则：将近期最少使用的块替换出去

方法：Cache的每一块都设置一个计数器，给不被使用的计数器+1，数值越大代表了最长的时间内未被使用

  • 访问缺失时，被调入或者被替换的块， 其计数器清0，而其它的计数器则+1
  • 访问命中时，将命中块的计数器清为0，所有块的计数值与命中块的原计数值进行比较
    1. 如果计数值小于命中块的计数值， 则该块的计数值加1
    2. 如果块的计数值大于命中块的计数值，则数值不变
  • 需要替换时，则选择计数值最大的块被替换

优点：符合Cache基本原理，同时考虑了新进入Cache的块，命中率较高

缺点：对于周期性、偶发性的访问数据，有大几率可能形成缓存污染，也就是置换出去了热点数据，把这些偶发性数据留下了，从而致使LRU的数据命中率急剧降低。

LRU-K

LRU-K 的主要目的是为了解决 LRU 算法"缓存污染"的问题，其核心思想是将"最近使用过 1 次"的判断标准扩展为"最近使用过 K 次"。

LRU-K 提供两个 LRU 队列，一个是访问计数队列，一个是标准的 LRU 队列，两个队列都按照 LRU 规则淘汰数据。当访问一个数据时，数据先进入访问计数队列，当数据访问次数超过 K 次后，才会进入标准 LRU 队列。标准的 LRU 算法相当于 LRU-1；

  • 数据第一次被访问，加入到访问历史列表；
  • 如果数据在访问历史列表里后没有达到 K 次访问，则按照一定规则（LRU）淘汰；
  • 当访问历史队列中的数据访问次数达到 K 次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；
  • 缓存数据队列中被再次访问后，重新排序；
  • 需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即淘汰“倒数第 K 次访问离现在最久”的数据。

LRU-K 具有 LRU 的优点，同时能够避免 LRU 的缺点，实际应用中 LRU-2 是综合各种因素后最优的选择，LRU-3 或者更大的 K 值命中率会高，但适应性差，需要大量的数据访问才能将历史访问记录清除掉。

img

FIFO

思路：总是将最先调入Cache的块替换出去。需要注意的是，当访问命中时不清零，严格地执行+1操作，总是替换最早进来的

方法：当需要替换时就选择计数值最大的块被替换掉

  • 对于组相联方式的Cache，每组内的每块都设定一个计数器
  • 当某块被装入或被替换时该块的计数器清为0，而同组的其它各块的计数器均加1

优点：实现容易，开销小

缺点：可能会把一些较早进入Cache、但经常使用的块（如循环）替换出去

LFU

LFU（The Least Frequently Used）最近不多使用算法，与LRU的区别在于LRU是以时间衡量，LFU是以时间段内的次数

  • 算法：若是一个数据在必定时间内被访问的次数很低，那么被认为在将来被访问的几率也是最低的，当规定空间用尽且需要放入新数据的时候，会优先淘汰时间段内访问次数最低的数据。
  • 优势：LFU也能够有效的保护缓存，相对场景来说，比LRU有更好的缓存命中率。由于是以次数为基准，因此更加准确，天然能有效的保证和提升命中率。
  • 缺点：由于LFU须要记录数据的访问频率，所以需要额外的空间；当访问模式改变的时候，算法命中率会急剧降低，这也是他最大弊端。。

下面描述了LFU的简单工做过程，首先是访问元素增长元素的访问次数，从而提升元素在队列中的位置，下降淘汰优先级，后面是插入新元素的时候，由于队列已经满了，因此优先淘汰在必定时间间隔内访问频率最低的元素。

img

随机替换

虽然随机听起来没什么规律，但这确实是一种折中的办法

在处理器中替换算法都是用硬件直接实现的，硬件复杂度可能会很高，有些情况下我们需要简单地实现替换功能，这时候随机替换就派上用场了。

随机替换不需要记录年龄，它只需要一个内置的时钟计数器，每当要替换cache line，就根据计数器的当前计数结果来替换cache line。

这样的方法优点是实现起来很简单，缺点是它不能体现出数据的使用的规律，因为它可能把最近最新使用的数据给替换出去，不过随着cache的容量越来越大，这个缺点所带来的性能损失也越来越小。总的来说，这是一个折中的办法。

几种方法的优劣

Cache容量小时，LRU最好；cache容量大时，随机替换和LRU差不多。

总的来说，当Cache容量越大、相联度越高，LRU和随机替换相差越小。

img

Cache的写策略

当有Cache时，写操作只需要改变Cache时就能继续运算，会在主存和Cache之间不一致。

读取时可以随意访问超出的字节，忽略不需要的部分即可。写操作的复杂在于写入数据的大小，通常小于一个cache line，只能改变一个块对应部分，而想修改一个Cache line，必须先核对Tag，查看是否命中。由于无法并行执行，因此写操作的时间一般大于读操作。

Cache的写也有命中和缺失，当写地址对应的块被加载到Cache中时为写命中，不在时为写失效。

写时常用写缓冲：设置一个Buffer，类似一个队列进行写，漫长的写操作不干扰处理器的其他指令。当Buffer满且有新的写指令时，处理器进行阻塞

写命中

写命中时有两种策略：

  1. 写穿透（Write-Through）：处理器在写cache的同时写内存
  2. 写回（Write-Back):处理器只写cache不写内存

写穿透（Write-Through）的好处是内存里的数据永远是最新的，cache里的数据替换时直接扔掉，因此写穿透简化了数据一致性。数据一致性对于多处理器和I/O非常重要，多级缓存使得写穿透适用于高一级的缓存，因为写操作只需要传播到下一级缓存，不需要传播到主存。

写回（Write-Back）的优点是写cache时方便，内存不一致就不一致，但是替换时整个块要写回内存。为了降低在替换时的频率，通常使用一种称为脏位（dirty）的功能，这个状态位表示这个cache line是脏的（在cache中经历了修改）还是干净的（未被修改）。如果它是干净的，在缺失时不会写回改块。在写回策略时，写操作的速度与缓存存储器的速度相同，一个cache line中的多个写操作只需要对低一级的存储器进行一次写入，因此写回方式使用的存储带宽比较少。

那么这两种策略哪个好？两种都很好，都用的很多。一般来说L1到L2使用write-through的比较多，从L2到内存用write-back用的多。因为L2的速度还可以，但是内存的速度比较慢。但这不绝对，因为我们既要一致性又要速度，write-through和write-back有矛盾，需要做tradeoff。

写失效

在写cache 失效时也有两种策略：

  1. 写分配（Write Allocate）：在发生写缺失时，先把这一块读到cache，再在cache中写；
  2. 写不分配（Write Non-Allocate）：写cache失效时直接写进内存。

写分配一般用在写回策略的cache中，写不分配通常用在写穿透的cache中，这好像是很自然的对应。任何一种写缺失策略都可以于写回或者写穿透一起使用。

写的具体策略

写缓冲 Store Buffer

在处理器中，不论是load、store，当Cache发生缺失时，需要从下一级的存储器中读取数据，并写到一个选定的Cache line中，如果这个Cache line是dirty，那么首先需要将它写到下级存储器中。

一般L2或主存只有一个读写端口，上面的过程就是串行完成的。

串行：只在第一层cache缺失时访问第二层cache

对于write back类型的Cache，先要将cache中dirty的数据存到下级存储器中，才能读取下级存储器而得到缺失的数据，L2或者内存的延迟都比较大，这种串行处理过程导致miss penalty的代价比较大。那用write buffer来解决这个问题，可以先将dirty数据放到write buffer中，等到下一级存储器空闲时，再将write buffer的数据放到下一级存储器中，从而将数据写到下级cache的时间mask。

对于write through类型的cache，write buffer更为重要，每次当数据写到cache时，并不会同时也写到下级存储器中，而是将其放到write buffer中，这样减少了cache写操作时的时间，从而提高了处理器性能。

write through类型的cache便于多核的一致性管理，在多核结构中，L1 cache常常采用这个结构。当然加入这个cache后，会增加系统设计的难度，当读cache缺失时，不仅要从下级存储器中查找这个数据，也需要在write buffer中查找数据。这需要在write buffer中加入CAM电路，在write buffer中的数据时最新的，如果在其中发现了缺失的数据，那么就需要使用它，同时抛弃从下一级存储中读出来的数据。

**Write buffer相当于L1 cache到下一级存储器之间的缓冲，通过它向下一级存储器的动作会被mask掉，从而提高了处理器执行的效率，**尤其是对于write through的cache来说尤为重要。

对于读cache失效对指令流水线的影响比写失效大：cache中有write buffer，写指令只要把指令给到write buffer即可，不会导致流水线堵塞。但是取数在数据回来之前无法提交指令，与取数指令存在数据相关的后续指令要等待取数操作回来的数据才能执行，可见读cache失效容易引起堵塞指令流水线。

在cache失效处理时，优先处理读失效以减小阻塞。读失效处理时要注意与write buffer的RAW相关，不能等写缓存为空，要动态检查write buffer。此外，读失效可能要替换dirty cache line，不要把替换块写回到内存再读，要充分使用write buffer，先读内存，再把write buffer中的数据写到内存。

img

现代的乱序执行处理器允许在load和store缺失时都是无阻塞的，但是付出了高复杂度的代价

Cache的分层

想要Cache大，又想要Cache块，于是想出分层的方法，最顶层的最快但是小，中间层在大小和速度之间达成tradeoff

L1 cache需要和处理器保持相同的速度等级，因此L1的容量和复杂度不能太高。L2cache的容量家要求大些，那么速度比L1稍慢，一般在5-20拍，相联度也会复杂。L1和L2一般都放到同一个die上，高端的cpu一般都会有L3 cache。

一般在处理器中，L2 Cache会使用写回（Write Back）方式，对于L1 cache来说write through的方式也是可以接受的，这样可以简化流水线设计，尤其是便于多核情况下的一致性，因此多核处理器对于L1 基本都按照写通方式设计。

Cache各层之间的区别

高层：

  • C小：受SRAM访问时间上限的约束
  • B小：受C/B影响和细粒度空间局部性收益上限的约束
  • a：需要考虑C/B的影响

底层：

  • C大：芯片面积上限的约束(或愿意支付多少片外开销)
  • B大：减少标签存储开销并利用粗粒度空间局部性
  • a：复杂性上限的约束(片外实现)

Cache的访问时间

对于第i层的Cache，（相对i-1层的）命中率为hih_i，访问本层无论缺失情况的时间为tit_i，能感知到的获取数据时间Ti=ti+(1−hi)∗Ti+1T_i=t_i+(1-h_i)*T_{i+1}，这是一个递归过程

image-20231216203034397

各层之间的数据关系

对于多级cache，还需要了解Inclusive和Exclusive，以L1 cache和L2 cache为例，两个概念如下图所示。

  • Inclusive:如果L2 Cache包含了L1 cache中所有的内容。
  • Exclusive：如果L2 cache与L1 cache的内容互不相同。
Inclusive and Exclusive

从上图中可以看出Inclusive cache是比较浪费资源的，因为它把一份数据同时放到了L1和L2 cache，Inclusive的设计有明显的好处，首先可以将数据直接直接写到L1 cache，但是L2 cache依然有覆盖数据的备份，此外inclusive的设计也简化了一致性的管理。

当前处理器cache miss的时候想看看所需的块是不是在其他处理器的私有cache中，不需要再去一个个查其他处理器的cache了，只需要看看共享的外层cache中有没有即可，对于实现cache coherency非常方便，也有效降低了cache miss时的总线负载和miss penalty。

如果一个处理器改变了存储器的地址（例如store），如果其他处理器的私有cache中也保存了这个数据的地址，那么需要将它们置为无效，以避免这些处理器使用到错误的数据。

  • 如果是Inclusive类型的cache，只需要查寻最低一级的cache的数据，这样就避免了改动L1 cache避免了对流水线的影响。
  • 如果是Exclusive的cache，就会打断流水线的执行。但是Exclusive的方式避免了硬件的浪费，也更大的cache容量，也可以提高处理的性能。

微架构没有对错，只要在该架构下，能发挥出系统性能，那就是优美的，这也是体系结构的魅力所在。

Cache的统一性

指令和数据，究竟是统一还是分离？

现代高性能处理器对指令和数据使用分离和不对称L1Cache，指令和数据内存空间不相交。

  • 取指令通常占用空间较小，空间局部性较高，是“只读”的
  • 分离的L1 Cache提供双倍带宽、无交叉污染和独立设计定制

对于统一的cache:

  • 优点：动态共享cache空间: 不会出现静态分区中可能出现的过度供应问题(将指令和数据cache分开)
  • 缺点：
    • 指令和数据可能互相竞争(对任何一方都没有空间的保证)
    • 指令和数据的访问发生在流水线的不同位置，统一的cache应该放在什么位置才能保证快速的访问?

第一层cache(FLC)几乎总是分开的，主要是因为上面的最后一个原因。第二层和更高层的cache几乎总是统一的

第一层cache (指令和数据)

  • 决策受时钟周期影响很大
  • 容量小, 较低的相联度
  • 标签存储和数据存储并行访问

第二层cache

  • 决策需要平衡命中率和访问延迟
  • 通常比较大而且有较高的相联度; 延迟并不是最重要的因素
  • 标签存储和数据存储串行访问

层次间的串行vs. 并行访问

  • 串行：只在第一层cache缺失时访问第二层cache
  • 第二层与第一层看到的访问行为不一样，第一层更像一个过滤器