10月28日笔记

直接映射cache：每个主存地址仅仅对应到cache中的一个块，因此我们只需要检查cache中的一个位置来判断该数据是否在cache中，块block是cache和主存之间的传输单位

被映射的高速缓存索引可以由存储器地址的低2位来决定，例如存储器地址低2位为00的数据映射到cache索引为0的位置

当有多个存储器地址的数据可以选择的时候，哪一个数据应该被放置在cache里？当需要一字节，控制器会找到对应的块，整块load进来

在cache中，通过标记tag来记录地址信息，由此来判断cache中的数据块来源于哪一个存储器地址

将多个存储地址映射到同一个cache索引，如何分辨是哪一个地址的数据在里面？当块大小大于1字节的时候，将存储器地址分成3部分，从高到低，分别标签位（用来检测数据是否是所需要的数据）、索引位（用来在cache中选择块）、块内字节偏移位（用于在块内选择所需要的字节），这三部分都采用无符号整数来表示

cache的字节数由高度×宽度来表示，高度定义为cache中块的数量，宽度定义为每个块的字节数

hit rate、miss rate、miss penalty、hit time

7.3 访问与缺失

写直达：同时更新cache和主存

写回：dirty位

块大小的选择是一个权衡的设计过程，通常来说，使用较大的块可以减少缺失率，因为利用了空间局部性原理，对于连续数组的访问有比较好的效果

缺失率不是唯一的性能指标，同时还要考虑缺失代价，当块大小增加的时候，缺失代价会增加，块越大，需要花费越多的时间去填满它，大的块也不总是有利的，当保持cache的大小不变，增加块的大小，一开始缺失率会由于空间局部性而快速下降，然而过了某一点之后，缺失率会上升，这是因为块大小和cache大小相比太大，块的数量就会很少

乒乓效应，缺失代价随着块大小的增加而不断增加，当保持cache大小不变，增加块的大小，缺失率会先下降，然后再上升，一开始下降的原因是利用了空间局部性原理，随后缺失率上升的原因是块的数量变少，影响了对时间局部性的利用

平均存储访问时间是一个比缺失率更加重要的指标

随着块大小的增加，平均访存时间会先减小，这是由于一开始缺失率下降的速度大于缺失代价增长的速度，但是最终随着块大小不断增加，平均访存时间会快速上升，因为缺失代价和缺失率都上升了

cache缺失类型：cache缺失3C模型中，1、强制缺失，出现在程序第一次开始启动的时候，这类缺失不能轻易被避免，主存中每个块都会发生一次强制缺失，又称为冷启动缺失；2、冲突缺失，当两个不同的主存地址映射到同一个cache地址时，会发生这类缺失，解决方法：1、增加cache大小，没有解决根本问题，2、cache每个索引对应的块数

全相联cache，一共只有一组，一组包含多个块，主存地址中标签域和偏移都和之前一致，由于只有一组，因此不需要索引域，每一个块都可以放在cache中任何一个位置，但是也必须通过cache中每个块的标签来判断数据是否在cache里面

优点：1、数据可以放置在cache中任何位置，因此不存在冲突缺失；缺点在于，对于每个块的标签域都需要一个硬件比较器，如果块大小为4字节，cache大小为64K字节，则需要16384个比较器，这样的设计硬件开销很大，现实中一般不采用这种设计方案

最后一种缺失我们称为容量缺失，这类缺失产生的原因是因为cache的容量有限，如果增加cache的容量，就不会产生这类缺失

首先考虑无限容量的全相联cache，发生的缺失均为强制缺失；其次考虑有限容量的全相联cache，其中除了强制缺失以外，都是容量缺失，最后考虑有限容量的有限关联度的cache，其中除了前两种缺失以外，其余都是冲突缺失

7.4 高速缓存设计

N路组相联cache，N表示每组里面块的数量，对直接映射cache，N=1，主存地址中标签域、偏移和之前一样，但是索引号有所变化，索引号表示组的位置，而不是块，在组相联cache中，每组都包含多个块，由于需要找到的块可能会在组中的任何位置，因此组中所有块的标签都要被检索，cache的尺寸等于组数×每组的块数×块大小

N路组相联cache，对于组来说，是直接映射的，每一组又相当于是N块的全相联，对于给定的主存地址，首先根据索引号找到对应的组，然后对比地址的标签域，和组内所有块的标记，如果有匹配的块，且有效位为1，则cache命中，否则cache缺失，最后根据块内偏移量，在正确的块中找到对应的数据，

优点：1、即便是2路组相联，都能避免大量的冲突缺失；2、在硬件开销上，只需要N个比较器，在硬件实现上是可行的；

对于一个有M块的cache而言，如果是1路组相联，则相当于是直接映射cache，如果是m路组相联，相当于全相联cache

4路组相联cache需要4个比较器，和1个4选一的多路选择器，比较器用来判断被选中的组中哪一个块和标记匹配，或者一个都没有，4选一的多路选择器根据比较器的结果，采用编码方法，采用4根地址线，选择4个块中的一个数据

块替换策略：

1、对直接映射cache来说，在发生缺失时，由于所需要的块在cache中只有一个地方可以放置，因此这个位置，原来的块必须被替换掉，

2、对于N路组相联cache来说，索引指定了一组，所需要的块可以放置在组内任意位置

3、对于全相联cache来说，所需要的块可以放置在cache中的任意位置

我们应该如何选择所需要的块，放置在哪个位置呢？

如果有有效位为0的块，新的数据块首先应该放置在这里，如果所有块的有效位为1，则表明没有空余位置，那么应该制定一个替换策略，来决定当有新的数据块写入时，哪一个位置的块应该被替换，最常用的方法是最近最少使用法，即LRU法，主要思想是将最近没有使用过的块替换掉，该替换策略的依据是时间局部性原理，最近被使用过的块很有可能将会被使用，事实上，这是一个非常有效的策略

对于2路组相联cache来说，每组设置一个LRU位，来跟踪每组中2个数据块的使用情况，通过该位指出哪块最近被使用，对于4路，或者更多路组相联的cache来说，需要更加复杂的硬件和更多的时间来跟踪数据块的使用情况

其它：

FIFO法：不考虑数据块被访问的次数，首先替换先加载的块

随机法：当数据访问的时间局部性低的时候，随机法效果也不错

平均存储器访问时间 = 命中时间+缺失代价×缺失率

平均存储访问时间受工艺和程序的影响

通过存储器层次结构设计，目的是得到存储容量大，成本低，且平均访问速度快的系统

如何改善缺失代价？当cache刚开始流行的时候，缺失代价约为10个时钟周期，目前2.4GHz的处理器，时钟周期为0.4ns，访问DRAM需要80ns，因此缺失代价约为200个时钟周期

为了进一步减小现代处理器高时钟频率和动态RAM访问时延之间的差距，通常使用2级cache来减少缺失代价，这个两级cache位于DRAM和一级cache之间，

1级cache通常容量很小，小容量cache使得缺失代价降低，相比之下，2级cache的访问时间不是关键，而2级cache的容量很大

对于多级cache，平均存储器访问时间 = 1级cache命中时间+1级cache缺失率×1级cache缺失代价

如果2级cache中包含所需要的数据，那么1级cache的缺失代价就是2级cache的访问时间，如果1级cache和2级cache都不包含所需要的数据，就需要访问主存，就需要更大的缺失代价

降低缺失率的方法：1、采用更大容量的cache，但是cache容量受限于成本和工艺技术，并且更大容量的cache会增加命中时间；2、增加关联度，比如全相联，N路组相联；

一般来说，一级cache的尺寸为几十KB，命中时间在1个时钟周期之内，缺失率在1%~5%之间，2级cache的尺寸在几百KB，命中时间为几个时钟周期，缺失率在10%~20%；

多级cache可以提高平均存储器访问时间，目前的处理器多采用多级cache设计。

主要思想：如果做某件事情的成本很大，但是我们需要重复做，那么就做一次，并且把结果缓存起来，

在cache设计中：cache尺寸、块大小、写策略、关联度、块替换策略、多级cache等进行选择