CSAPP - 存储器层次结构

Jan 14, 2024

Read On Github Read On PDF

局部性
存储器的层次结构
高速缓存存储器
关于写的问题

局部性

一个编写良好的计算机程序往往有良好的局部性。

局部性原理：程序倾向于使用距离最近用过的指令/数据地址相近或相等的指令/数据。

局部性的两种形式：

时间局部性：最近访问过的信息，很可能在近期还会被再次访问。
- 重复引用相同变量的程序有良好的时间局部性。
空间局部性：地址接近的数据项，被使用的时间也倾向于接近。
- 对于具有步长为 $k$ 的引用模式的程序，步长越小，空间局部性越好。

int sumvec(int v[], int n) {
    int sum = 0;
    for(int i = 0 ; i < n ; i ++)
        sum += v[i];
    return sum;
}

对于上面的代码来说, sum 被反复引用, 所以用良好的时间局部性, 通常情况下会被放在 CPU 的寄存器文件中, 而对于数组 v 来说, 连续访问了内存的相邻区域且步长为 $1$, 所以具有良好的空间局部性

存储器的层次结构

存储技术和计算机软件的基本稳定特性：

高速存储器技术成本高、容量下、耗电大、易发热。
CPU和主存之间的速度差距越来越大。
一个编写良好的程序倾向于展示出良好的局部性。

这些特性互相补充，给出一条组织存储器系统的途径——存储器层次结构。

从高层往底层走，存储器变得更慢、更便宜和更大

RAM-intro-0

CPU 直接读取最底层的存储器的速度回非常的慢, 所以就提出了缓存的概念, 简单来说, 位于$k$ 层的更快更小的存储设备作为位于$k+1$ 层的更大更慢的存储设备的缓存。这样, 上层的存储器就没必要直接读取比自己低数级的存储器内容了, 大大的减少了访问的时间

memory-0

当我们想缓存请求数据的时候, 会遇到两种情况 :

缓存命中

当程序需要第 $k+1$ 层的某个数据对象 $d$ 时，它首先在存储在第 $k$ 层的一个块中查找 $d$。如果 $d$ 刚好缓存在第 $k$ 层中，那么就是缓存命中。
缓存不命中
如果第 $k$ 层中没有缓存数据对象 $d$，那么就是缓存不命中。

这时需要第 $k$ 层的缓存从第 $k + 1$ 层缓存张取出包含 $d$ 的那个块 :
- 如果 $k$ 层没有满, 那么直接放在空的地方
- 如果 $k$ 层满了, 那么就替换掉一个有效的块 [不同的替换策略决定替换的块]

不命中也有一下的几种类型 :

冷不命中（强制性不命中）：当缓存为空时，对任何数据的请求都会不命中。

冲突不命中：

大部分缓存将第 $k+1$ 层的某个块限制在第 $k$ 层块的一个子集里。

当缓存足够大，但是被引用的对象都映射到同一缓存块中。

容量不命中：当工作集大小超过缓存的大小时。

高速缓存存储器

memory-1

通用的高速缓存存储器结构

考虑一个计算机系统, 其中的存储地址有 $m$ 位, 那么就会有 $M = 2^m$ 个不同的地址, 那么这个机器的高速缓存就会组织成一个有这 $S = 2^s$ 个高速缓存组的数组, 每个组包含 $E$ 个高速缓存行, 每个行是由一个 $B = 2^b$ 字节的数据块组构成, 同时还有一个有效位和 $t = m-(b+s)$ 哥标记位, 他们唯一标识在高速缓存中的行

memory-2