CPU设计之Cache-写/包含/替换策略

惟沉默是最高的轻蔑

-- 鲁迅

Cache的写策略

第一个写策略问题是，当处理器修改了高速缓存中的数据后，这些修改什么时候会被传播到外层的存储层次。对于D-cache来说，当执行一条store指令时，如果只是向D-Cache中写入数据，而并不改变它的下级存储器中的数据，这样就会导致D-cache和下级存储器中，对于这一个地址有着不同的数据，这称作不一致(non-consistent)。对应的两种策略是：

写直达（write through），缓存中任何一个字节的修改都会被立即传播到外层的存储层次。

写回（write back），只有当缓存块被替换的时候，被修改的数据块会写回并覆盖外层存储层次中的过时数据。

采用写直达还是写回策略，首先要考虑的系统带宽。对于处理器芯片最外层的高速缓存，由于片外带宽有限，往往采用写回策略；而对于内层高速缓存，由于片上带宽较大，因此往往采用写直达策略。

一个影响是要考虑两种策略在硬件故障下的容错。例如，当遇到阿尔法粒子或者宇宙射线时存储在高速缓存中的数据会反转其存储的值。在写直达策略中，当检测到故障时，可以安全的丢弃出故障的数据块并从外层存储中重新读取该数据块。但在写回策略中，仅仅有故障检测并不够。为了增加纠错功能，需要添加冗余的数据位ECC。但由于ECC计算开销大，因此ECC会增加高速缓存的访问时延。

另一个影响是要考虑两种策略中外层高速存储的功耗。在写直达策略中，外层高速缓存会被频繁写入，导致外层高速缓存较高的功耗。解决办法之一是在内层缓存和外层缓存中间增加一个写缓冲，用于临时保存对内层缓存的最近若干更新。当写缓冲满的时候，将存储最久的或最近最少使用的数据块写入外层缓存。当内层缓存缺失时，首先检查写缓冲区。

第二个问题是，如果要写入字节的数据块不在高速缓存中时，是否将其读入高速缓存中。上面所讲述的情况都是假设在写D-cache时，要写入的地址总是D-cache中存在的，而实际当中，有可能发现这个地址并不在D-cache中，这就发生了写缺失(write miss)，此时最简单的处理方法就是将数据直接写到下级存储器中，而并不写到D-cache中，这种方式称为写不分配（Write non-Allocate）。与之相对应的方法就是写分配（Write Allocate），在这种方法中，如果写cache时发生了缺失，会首先从下级存储器中将这个发生缺失的地址对应的整个数据块(data block)取出来，将要写入到D-cache中的数据合并到这个数据块中，然后将这个被修改过的数据块写到D-cache中。如果为了保持存储器的一致性，将这个数据块也写到下级存储器中，这种方法就是刚才提到的写直达(Write Through)。如果只是将D-cache中对应的line标记为脏(Dirty)的状态，只有等到这个line要被替换时，才将其写回到下级存储器中，则这种方法就是前面提到的写回(WriteBack)。Write Allocate为什么在写缺失时，要先将缺失地址对应的数据块从下级存储器中读取出来，然后在合并后写到cache中？因为通常对于写D-cache来说，最多也就是写入一个字，直接写入cache的话，会造成数据块中的其它部分和下级存储器中对应的数据不一致，且是无效的，如果这个cache line由于被替换而写回到下级存储器中时，就会使下级存储器中的正确数据被篡改。

写直达策略可能会使用写分配或者写不分配策略。然而，一个写回策略通常会使用写分配策略，否则如果使用写不分配策略，写缺失会被直接传播到外层存储层次，从而变的与写直达相似。

对于多核处理器设计来说，往往最后一级cache（last level cache，LLC）是所有处理器共享，而其它级cache是某处理器独享，因此还有一个写操作如何传播的问题。有两种实现方式：写更新（write update）和写无效（write invalidate）。区别是对某个处理器的缓存中的某个值执行写操作时，对于保有该数据副本的其他所有缓存的值是全部更新还是全部置为无效。

多级cache的包含策略

在多级高速缓存的设计中，另一个相关的问题是内层高速缓存的内容是否包含在外层高速缓存中。如果外层高速缓存包含了内层高速缓存的内容，则称外层高速缓存为包含的（inclusive），相反如果外层高速缓存只包含不在内层高速缓存中的数据块，则称外层高速缓存是排他的（exclusive）。包含性和排他性需要特殊的协议才能实现，否则无法保证包含性或者排他性，这种情况称之为不包含又不排他（non-inclusive non-exclusive，NINE）。

包含策略的优点是，前处理器缓存缺失的时候想看看所需的块是不是在其他处理器的私有cache中，不需要再去一个个查其他处理器的cache了，只需要看看共享的外层cache中有没有即可，对于实现cache一致性非常方便，也有效降低了缓存缺失时的总线负载和miss penalty；缺点是整体cache的容量变小。

包含策略的特性会产生两个影响。一是在采用包含策略的高速缓存中，缓存缺失的时延较短，而采用排他和NINE策略则较长。二是对对所有内层高速缓存检查访问的数据块是否存在意味着增加对高速缓存控制器和内层高速缓存标签阵列的占用。

排他策略正好相反，其优点是，可以最大限度的存储不同的数据块，相当于增大整体了cache的容量；其缺点是需要频繁填充新的数据块，会消耗更多的内外层间缓存带宽，并且对标签和数据阵列产生更高的占用率。

Cache的替换策略

在一个cache set内的所有line都已经被占用的情况下，如果需要存放从下游存储器中读过来的其它地址的数据，那么就需要从其中替换一个，如何从这些有效的cache line找到一个并替换之，这就是替换(cache replacement)策略。常见的替换算法有以下几种：

先进先出（FIFO）算法

最不经常使用（LFU）算法

近期最少使用（LRU）算法

随机替换算法

关于cache的替换策略有很多分析文章，如果感兴趣可以慢慢研究~~