高速缓存

为了减低成本，增加cpu访问主存的性能，一般都会在主存与cpu之间增加小容量的缓存，可以采用这种方式的一个很主要原因就是程序执行的局部性。

程序的局部性

自我理解程序的局部性就是大多数时候程序都是按照代码一行行的执行可能发生条件转移指令但是程序跳转的范围也不是特别的大。下面来一个专业的解释：在一段时间内，仅会执行程序的一部分，而在这段时间内要执行的指令和数据都放置在某个存储区域内。

1. 时间局部性

   当程序访问某个存储位置的时候可能会多次访问该位置，比如热点方法，循环中的代码以及数据。

2. 空间局部性

   当程序访问了某个存储单元，其附近的存储单元也将被访问，访问主存中的数组,代码，数据结构有较强的空间局部性。

缓存概览

我们增加了高速缓存之后希望cpu可以直接在缓存中可以直接取到数据这样，cpu需要数据的时候肯定先访问缓存，我们的缓存，我们需要一种查找机制来判断是否命中缓存（需要的内容在缓存中），没有命中缓存称之为数据缺失，发生缺失的时候从主存拿到数据所需要的时间称之为缺失补偿。一般缓存跟主存都被划分为以字为单位的固定大小的数据块，缓存跟主存交换数据的时候都是以块为单位，这样数据缺失的时候相邻的数据也被添加到了缓存之中，充分利用了空间局部性，提高了命中率。

块过大会导致程序的时间局部性受到影响，比如a在块blockA中b在BlockB中，但是这两个块放在缓存中相同位置（块越大他俩在缓存之中放置相同位置的机率就越大，也跟置换规则有关），需要频繁的访问a,b就要发生频繁的发生块替换导致时间局部性受到影响。块过小会影响程序的空间局部性。

进行数据分块后，主存地址跟cache地址均可以分为块地址以及块内偏移地址。他俩的偏移地址相同因为块大小相同。

cache读，写流程

cache读流程

当cpu拿到要访问的地址以后首先访问缓存如果数据在缓存中就直接返回数据到cpu。如果发生缺失，就要访问主存当中相应的数据块，如果此时缓存已经满了或者要载入的位置有数据冲突则要发生块替换。并更新查找表。

cache写流程

写的流程相比读流程要复杂一些，写的时候首先在cache之中进行数据查找，如果发生缺失则要判断是否为写分配策略或者不是写分配策略，写分配策略意味着要发生块替换，不是写分配策略则直接写入数据到主存并且写入流程结束（标识数据为脏数据,cache块数据跟主存数据不一致），采用写分配策略以及发生命中的情况下在将cache中的数据更该过以后，可以使用写回或者写穿策略，写穿策略就是直接将cache中修改的数据，在主存中也修改一遍，写回策略就是要等到发生块替换的时候再将数据块上的更改一并写入主存之中，为了标识一个cache数据块是否跟主存相应数据块发生了变化我们一般会使用一个bit的标识为来标识cache块来决定是否在块替换的时候执行主存数据的更新.

cache实现的关键技术

• 数据查找

  怎样快速判断相应的主存地址是否在cache中

• 地址映射

  主存中的数据块是任意放置还是按照一定规则

• 替换策略

  cache满的时候应该替换调哪一块内存

• 写入策略

  如何保证cache与主存数据的一致性，写回还是写穿策略

数据查找

数据查找一般使用相联存储器（CAM）进行查找，CAM根据要查找的Key并发查找。

地址映射

1. 全相联：主存块映射到任意cache块

2. 直接相联：各个主存块只可以映射都特定的主存块

3. 组相联：主存块可以映射到cache固定组的任意位置

4. 全相联：
   由于主存块的数据可以映射到cache的任意位置，所以只有当cache满时才会发生块替换，这样主存的利用率高，但是查找数据的时候比较满，因为每个cache行都要查看是否匹配。
   查找数据时直接并行比较所有cache行的主存地址，如果相同并且有效位为1则表明查找的数据在cache当中。若是写命中则将更改cache中的数据，并且脏数据位置为1；如果是读命中，就输出cache行中offset处的数据。

特点：cache利用率高；cache冲突率低；查找的时候并发比较所有的行，硬件成本高适合小容量缓存。

2. 直接相联：

   将cache行标上序号（假设一共有n个cache行），主存块号 对 n求余 就是 该主存块 可以映射的cache行号，也就是说从主存头部数据块开始的n个数据块，他们是不会发生cache冲突的，因为他们位于同一个区。这样我们可以将主存块划分一个区号，区内行索引，块内偏移，这样查找的适合可以根据行号快速定位到cache行然后比较cache行的区号就行，查找更简单。

特点：cache利用率低，发生cache冲突的几率较高，查找成本低，适合大容量存储。

3. 组相联：

   组相联算是上述两个的结合物，首先将cache划分位行数相同的不同的组，然后根据主存的前几位对组的数量求余，得到的余数就对应主存可以放置的组号，接下来跟直接相联不同的是它不再根据主存地址确定组内行号而是随便放置，使用主存地址的中间几位作为标识确定要找的目标cache行。

特点：cache利用率以及冲突发生几率都属于中等水平

替换算法

1. 先进先出算法(FIFO)

   要给每个数据块一个时间戳，或者时间计数。
   特点：没有考虑程序访问的局部性，命中率低

2. 最不经常使用(LFU)

   给每个数据块一个初始值每次访问就将该值+1，当要替换的时候将计数最小的丢弃。
   特点：只可以反应历史总访问情况，不能反映近期访问情况。

3. 近期最少使用(LRU)

   当访问命中的时候就将cache行对应的计数置为0，其他行的计数+1，替换的时候先替换值最大的cache行

   LRU在数据结构中的应用，并没有采用给每个元素一个计数的方式而是采用链表将各个元素穿起来，如果访问了某个元素就将其放在链表的尾部或者头部，替换的时候直接从链表的另一端开始替换。

4. 随即替换

   随机选取cache行进行替换，不用比较计数器，步骤简单，而且快速，但是冲突的几率可能要大于LRU，以及LFU。

写入策略

1. 写回法

   当写命中的时候只修改cache行中的数据，不修改主存当中对应的数据，而是将cache的脏数据位置为1，当该cache行要发生替换的时候再去同步主存的数据。会导致cache与主存的数据不一致，DMA操作可能会取到不是最新的数据。

2. 写穿法
   当写命中的时候同时将cache行以及主存数据修改。缺点：cache对cpu的写操作没有缓冲功能。

原文：https://www.cnblogs.com/FCY-LearningNotes/p/14811575.html