1. 基本概念

1. 存储系统的体系结构

图片摘自这篇博客：图片来源

2. cache在存储系统中的位置

cache（缓存）位于CPU内部，其读取速度快于主存，但容量小于主存。cache中存放的是程序需要用到的数据，CPU处理时直接从cache中读取数据速度要快于从主存中读取。

在CPU和主存之间引入cache是为了：

①避免CPU与外部设备争抢主存
外设向主存请求数据级别高于CPU，可能导致CPU等待较长时间。
②提高取指令和取数据的速度
主存速度提高跟不上CPU的发展速度，差距总在5倍以上。

3. 程序访问的局部性原理

之所以可以把CPU当前需要的数据和程序放在cache中，是因为程序访问具有局部性的原理：

时间局部性 一个存储单元被访问，此单元很快就会再次被访问

空间局部性 一个存储单元被访问，该单元临近的单元也可能很快被访问。

4. 命中率

如果访问的数据在cache中，称为访问cache命中。

设某Cache的命中率为h，其中访问Cache的时间为tc，访问M的时间为tm。设Nc访问cache命中的总次数，Nm表示访问cache不命中而访问M的次数，则有：
h=Nc/(Nc+Nm)×100%
①若CPU在访问cache不命中时再访问主存
平均访存时间ta=h·tc+(1-h)·(tc+tm)=tc+(1-h)·tm
②若CPU同时访问cache和主存，访问命中时中止对主存的访问。
平均访存时间ta=h·tc+(1-h)·tm

5. 字、字块、标记、组

字 ：1个字由n个字节组成（n≥1），字是CPU访问存储器时可存取的最小单位

字块 ：1个字块包含n个字（n≥1），字块是主存与cache交换的最小单位

也就是说，cache和主存在交换时是以字块为单位的，一次交换一个字块（包含好多个字，利用到了局部性原理）。而CPU在访问cache时，一次只存取一个字。

标记 ：cache中存放的主存块地址称为标记。

组 ：多个字块组成的一个逻辑整体称为组。

2. cache-主存的三种映射方式

2.1 全相联映射

思路

允许主存中的每个字块映像到cache的任何一个字块位置上。

示意图

主存地址和cache地址

设置主存地址和cache地址的一个目的是，可以通过主存地址来找到cache地址，这样才能实现主存和cache字块的交换。

主存地址：

包括块标记和字块内地址两部分，其中块标记相当于字块在主存中的地址，字块内地址为字块中某个字的地址。

示意图：

cache地址：

包括字块号和字块内地址，其中，字块号为字块在cache中的地址，字块内地址为字块中某个字的地址。

注意：主存地址和cache地址中的字块内地址相同。

示意图：

相联存储器：

既然全相联映射方式的思路是：主存中的字块映射在cache中的任一字块，计算机怎么知道映射到哪一字块了？到时候怎么操作呢？这就需要一个目录表来查找主存中的某一字块与cache中某一字块的对应关系：

该目录表由三部分组成：主存字块标记（主存地址的第一部分），cache字块地址（cache地址的第一部分），有效位（1位）。目录表的行数为cache的字块数，这很好理解，因为目录表的目的就是查找主存字块和cache字块的对应关系。

特点

（1）映像方式灵活，主存中的一个字块可以对应cache的任意一块；
（2）主存地址映射到cache无规则可言，必须使用相联存储器通过按内容查找获取cache块号。
（3） 全部由硬件实现，速度快，但硬件实现难度大；
（4）由于使用相联存储器存储目录表，成本高。当cache容量越大时，所需相联存储器的容量也越大，成本也越高。仅适用于小容量cache采用。

2.2 直接映射方式

思路

主存中的一块只能拷贝到cache中的一个特定行位置。设主存的块号为i，cache中的块号为j，cache的总块数为N，则映射关系为：
j = i mod N

示意图

主存地址与cache地址

主存地址：

包括块标记、字块地址、字块内地址三部分。其中，块标记为字块在主存中的地址，字块地址为字块在cache中的地址（计算方法就是上面说的），字块内地址为字在字块中的地址。

因此这种映射方法不需要目录表了。（因为主存地址中存有要映射到cache相应字块的字块地址了）

示意图：

cache地址：

包括字块地址、字块内地址两部分：其中，字块地址为字块在cache中的地址，字块内地址为字在字块中的地址。

注意：cache地址中的字块地址和字块内地址和主存地址中的相同。

示意图：

特点

（1）映像函数简单，实现硬件简单，无需相联存储器，实现成本较全相联映像方式低；
（2）地址变换速度快，如果命中且字块有效，那么主存地址去掉区号后的低位部分就是cache地址。
（3）块冲突率高，当两个或两个以上的主存块映射到相同的cache发生冲突时，即使其他cache块空闲也不能被使用。当两块交替映射到同一cache时，造成频繁置换——抖动。

2.3 组相联映射方式

思路

组相联映像方式为前两种方式的折衷。其方法是将cache按某种规格分组，主存中若干字块映射到同一个组中，组间为直接映像方式，组内为全相联映像。

主存字块在cache组号求法为：主存字块号 mod cache组数
示意图

主存地址和cache地址

主存地址：

主存地址包括主存字块标记、组号和字块内地址三部分。其中主存字块标记为字块在主存中的地址，组号为cache分的组的组号，字块内地址为字在字块中的地址。

示意图：

cache地址：

cache地址包括组号、字块号和字块内地址三部分组成。其中，组号为cache分组的组号，字块号为每组内字块的地址，字块内地址为字在字块中的地址。

注意：主存地址和cache地址中的组号和字块内地址相同。

示意图：

特点

（1）因为是两种映像方式的折衷，因此地址结构较为复杂，比较的情况较多，需要引入相联存储器；
（2） 兼顾了映像的灵活性和操作的复杂程度。
（3）目前应用较多。每组具有v个字块的组相联映像方式常称为v路组相联。v一般取值较小，典型值有2、4、8、16。

3. 三种映射方式例题

【例题】

设主存容量为256K字，cache容量为2K字，块长为4，按字编制。
①设计cache地址格式，cache可装入多少块数据。
②在直接映射方式下，设计主存地址格式。
③在四路组相联映射方式下，设计主存地址格式
④在全相联映射方式下，设计主存地址格式

【解答】

因为是按字节编址，所以主存地址有18位，cache地址有11位，因为块长为4，说明每个字块有4个字，故字块内地址为2位。

① 字块内地址为2位，故字块地址有11-2=9位，cache地址如下：

② 直接映射方式下，主存地址包括主存字块标号、字块地址和字块内地址3部分，其中字块地址和字块内地址与cache地址相同，故主存字块标号有18-11=7位。主存地址如下：

③ 四路组相联，说明cache分为4个组，此时cache地址包括：组号、字块地址、字块内地址三部分。

因为分为4组，故组号为2位，因为一个字块长4位，故字块内地址为2位，故字块地址为11-2-2=7位，cache地址如下：

此时主存地址由三部分组成：主存字块标记、组号、字块内地址。

组号和字块内地址和cache地址相同（共7+2=9位），故主存字块标记有18-9=9位，主存地址如下：

④ 全相联方式下，主存地址由主存字块标记和字块内标记组成，字块内标记和cache地址相同，为2位，故主存字块标记为18-2=16位，主存地址如下：

Cache结构图

Cache和主存被划分为很多块， 块(Cache Block ) 作为映射的最小单元，块大小(Cache Block size) 反应块内所包含的字节数。

以256byte大小Cache为例，其Cache Block size=4 byte，被划分为32块。

Cache地址相当于被划分为了2部分：块号(index)+块内地址/偏移量(offset)

主存的结构与Cache相同，Main Memory Block size = Cache Block size

直接映射

直接映射就是每个主存块只与一个缓存块相对应，映射关系为$i=jmodC$(其中$i$为缓存块号,$j$主存块号,$C$为缓存块数)。
以4个Block的Cache与32个Block的主存为例 (Cache Block size = Main Memory Block size)，这里假设每块含4字节，Main Memory中每4个Block为一组 (每组的Block数量 = Cache的Block数量) ，每组的第1块映射到Cache中的Cache Block[0]，第2块映射到Cache Block[1]…

假设现在需要主内存中的地址为15H的数据，CPU首先会在Cache中查找，这就需要将主存中15H地址映射到Cache中。
$15H=00010101$，其中offset(01)表示在块内的偏移量，index(01)表示在Cache的块号。每一组相同index将映射到Cache中的同一块，因此需要一个tag来区分不同的组。

图上还有一个valid bit，这个是用来标记Cache Block是否有效的，当根据Main Memory地址映射到Cache所在块之后会先检查valid bit是否有效，只有在有效的情况下，比较tag才有意义。如果无效，直接判定cache缺失。当系统刚启动时，cache中的数据都应该是无效的，因为还没有缓存任何数据。

直接相连映射的优缺点
优点：简单易实现，硬件成本会比较低
缺点：不够灵活，Cache中的每个Block对应Main Memory中每组index相同的Block，一个一对多的关系，如果需要访问Main Memory每组index=1的Block，则Cache中只有index=0的Block会被使用，并且数据还会被不断替换，其他空闲位置无法使用，命中率降低。

全相联映射

全相联映射允许Main Memory中的每一个Block映射到Cache中的任何一个位置上面，只有当Cache中的Block全部被占用时，才考虑替换。
假设Cache被划分为4个Block，Main Memory被划分为32个Block，(Cache Block size = Main Memory Block size)，假设此时需要地址为15H(00010101)的数据。CPU首先会查找Cache是否有存储，由于采用全相联映射，Main Memory中的Block可以映射到Cache中的任一一Block，因此需要逐一检验tag标签来判断。如下图所示在Cache中Block[1]的tag匹配成功。通过offset来确定该内容在Block中的位置。

全相联映射的优缺点：
优点：因为Main Memory中的Block可以映射到Cache中的任一一Block，不像直接映射一样，Main Memory中某一个Block映射到Cache中唯一的Block灵活，这种方式命中率更高，缩小了块冲突（只有当Cache全部Block都被占用才会冲突）。
缺点：直接相连映射定位到Cache中的Block之后，只需要检验一次tag标签即可，而全相联映射，需要逐一匹配Cache中每一个Block的tag标签，这种方式的硬件成本较高。

组相联映射

组相联映射是直接相连映射和全相联映射的一种折中方法。
直接相连映射是Main Memory中的任一Block只能映射到Cache中唯一的Block，而组相联映射则是映射到Cache中唯一的组(Group)(一组包含若干Block)，映射规则为i$i=jmodC$(其中$i$为Cache中的组号，$j$为Main Memory的块号，C为Cache的组数)。
对于同一组，采用全相联映射，Main Memory中的Block可以映射到对应组中的任一一Block，通过逐一检查tag标签来定位。

假设Cache被划分为4个Group，每个Group有2个Block，Main Memory被划分为32个Block，现需要Main Memory中地址为15H的数据，CPU会先到Cache中寻找，15H = 0001 01 01，其中的index(01)确定为Group[1]，然后逐一匹配Group[1]中所有Block对应的tag，最后确定15H在Cache所映射的位置。

可见直接相联映射和全相联映射都是特殊的组相联映射，直接相联映射是当Cache中每组只有一个Block情况下的组相联映射，而全相联映射则是Cache只划分一个组(即Cache所有Block作为一个组)情况下的组相联映射。

牙牙yyds