6.存储系统与辅存(cache的映射方式的各种问题解析)

6.1 存储系统

衡量存储器有三个指标：容量、速度、价格
一般来讲，速度高的存储器，每位价格也高，因此容量不能太大。
对于存储系统，我们期望实现：
1.增大存储系统的容量
2.提高存储系统的读写速度
3.降低存储系统每位价格

针对提高存储系统的读写速度，我们可以：
采用高速器件提高速度；
采用双端口存储器；
增加字长，在每个存取周期中存取多个字；
将主存划分为多个模块，多模块并行；
增加Cache。

计算机中，CPU可以直接访问主存，因为存储器的速度慢，所以访存的速度主要取决于存储器的速度。

在CPU与主存之间加入高速缓冲存储器（cache），以减少速度差所导致的访存时间较长的问题。
引入cache的依据：程序访问的局限性
如果当前正在执行的程序和数据存放在cache中，当程序运行时，不必从主存储器取指令和数据，而访问这个高速存储器即可，从而提高了程序的运行速度。

6.2 程序访问的局部性原理

计算机在执行程序的过程中，在一个较短的时间间隔，地址往往集中在存储器逻辑地址空间的很小范围内。
①程序的地址分别是连续的，因此，对程序地址的访问具有相对集中的倾向。
②数据分布的集中倾向不如指令明显，但对数组的访问以及工作单元的选择都可以使存储器地址相对集中。
对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象就称为程序的局部性。
局部性分为时间上的局部性和空间上的局部性：
时间局部性：一个存储单元被访问，此单元很快就会再次被访问。
空间局部性：一个存储单元被访问，该单元临近的单元也可能很快被访问。

6.3 主存地址到cache地址的映射

Cache命中率

当前正在执行的指令和数据存放在Cache中，当程序执行时，CPU不用从主存中读出指令和数据，只用从cache中读取即可。
如果访问的数据在Cache中，称为访问cache命中。
如果访问不命中（缺失），仍然需要从主存中读入数据：
缺失：程序执行时，CPU不能从Cache读取到指令和数据，就需要再到主存中获取。

Cache中的指令只允许读，不允许修改；而数据可读可写。
chache映像方式
Cache仅为主存的一个极小子集，不能容纳主存的所有数据。Cache与主存交换数据的单位为字块，为了将主存子块放入cache，必须通过某种方式将主存的地址定位到cache中，这种方式称为“地址映像”。

字块：主存的数据块大小称为字块，简称块。每个块中包含2^b个连续的字，字块所包含的字数或字节数称为块长。

字块是主存和cache交换的最小单位；
字是CPU访问存储器时可存取的最小单位。
标记：cache中存放的主存块地址。
组：多个块组成的逻辑整体。

6.4 cache的映像方式

全相联映像方式

这种方式允许主存中的每个字块映像到cache的任何一个字块位置上。
特点是灵活，实现难度大，成本高。

举例：在某计算机系统中cache的容量为32KB，数据块的大小为16个字节，主存容量为1MB，
按字节编址，地址映像方式为全相联映像方式。求：
①主存地址和cache地址各多少位，如何分配？
②目录表的容量。

解：①以字节编址，cache地址位 log2(32KB/1B)=15位
主存地址位 log2(1MB/1B)=20位
由于主存和cache划分成同样大小的块，因此对cache的字块数32KB/16B=2K……对应11位。
对主存的字块数1MB/16B=64K……对应16位，故地址分配图为（按字节编址）：

对于上面的标准算法容易忽略出错，我建议这么算：
32KB/16B=2¹⁵/2⁴=2¹¹，对应11位；
1MB/16B=2²⁰/2⁴=2¹⁶，对应16位。除法变成减法，是不是更舒服。
②如上例所示：目录表中包含主存块号、cache块号和1位有效位，且其大小与cache的块数相同。
∴目录表容量：2K×(16+11+1)=56K位=7KB

直接映像方式

这种方式下，主存中的多个字块只允许映像到cache的某个字块位置上。

直接映像的特点是主存中的一块只能拷贝到cache中的一个特定行位置。

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

【举例】在某计算机系统中cache的容量为64KB，数据块的大小为16个字节，
主存容量为4MB，按字节编址，地址映像方式为直接相联映像方式。求：
①主存地址和cache地址各多少位，如何分配？
②区表的容量。

解：①以字节编址，cache地址位 log2(64KB/1B)=16位
主存地址位 log2(4MB/1B)=22位
由于主存和cache划分成同样大小的块，因此对cache的字块数64KB/16B=4K……对应12位。
主存的字块数为：4MB/64KB=64=26，因此主存字块标记需要6位。地位地址与cache相同，故地址分配图为（按字节编址）：

②如前图所示：区表中包含主存字块标记和1位有效位，且行数与cache相同，为4K行。
∴目录表容量：4K×(6+1)=28K位=3.5KB

【举例】有一主存-cache层次的存储器，
其主存容量1MB，cache容量为64KB，每块8KB，
采用直接地址映射方式。求：
①主存地址格式？
②主存地址为25464H，问它映射到cache的哪一块？

①第一个问题很简单：
②主要是第二个问题：
它这里说主存地址是25464H，注意这个是16进制，一共有20位，然后我们的主存也是20位，这就对应上了：0010 0101 0100 0110 0100 ，是这样的，然后主存的字块地址应该对应010，也就2，所以它映射的cache的字块号也为2。

【举例】设某8位计算机采用直接映射cache，已知容量为4096B，主存容量为4MB。
设开始时，cache为空，
若CPU依次从主存单元0，1，……99和4096,4097，……4195交替取指令，
循环执行10次。考虑两种情况下，各自的命中率是多少？
①字块长度为一个字？
②字块长度为8个字？
③若采用全相联映射方式，上述两种情况命中率又将如何？

组相联映像方式

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

【举例】在某计算机系统中cache的容量为32KB，
数据块的大小为64个字节，主存容量为1MB，按字节编址，
地址映像方式为组相联映像方式，cache共分128组。
求：主存地址和cache地址各多少位，如何分配？

解：①以字节编址
cache地址位数 log2(32KB/1B)=15位
主存地址位数 log2(1MB/1B)=20位
cache分128组，每组字块数为32KB/64B/128=4。因此，对cache而言，分128组，每组4个字块，每个字块内含64个字节；主存地址标记为20-7-6=7位。故地址分配图为：

综合举例

【举例】设主存容量为256K字，cache容量为2K字，块长为4。
①设计cache地址格式，cache可装入多少块数据。
②在直接映射方式下，设计主存地址格式。
③在四路组相联映射方式下，设计主存地址格式
④在全相联映射方式下，设计主存地址格式
⑤若存储字长为32位，存储器按字节寻址，写出上述三种映射方式下主存的地址格式。

解：
① 以字编址的情况下，主存地址位数为18位：256KB/4B=2¹⁸/2²=2¹⁶
cache可包含的块为512块: 2¹⁰/2²=2⁸=512
为了标记各个字块，需要9位 (512=2⁹) 二进制位来表示，用2位来标记字块内每个字。故cache地址格式为：

② 直接映射方式下，主存地址包含主存字块标记，cache字块标记，以及字块内地址构成。且主存字块标记位数为log2(256K/2K)=7位，地址为：

③四路组相联，即每组中包含4个字块，cache可以分成的组为log2(2K/4/4)=7。进一步细分可知cache地址：

主存地址为:

④ 全相联映射方式下，主存地址位数去掉字块内地址即为主存字块标记，地址表示如下：

⑤ 按字节寻址，仅需在地址的最后添加字节地址即可，位数为log2(32/8)=2。按字节寻址，直接、组相联、全相联映射方式对应地址格式分别为：