CS:APP第六章学习

开始学 CSAPP的第六章

逐步更新：

• 2023-1-15：开始写
• 2023-1-18：补完第二小节
• 2023-1-19：写完第六章！

梗概

跟平时理解的差不多，层次存储，越靠近 CPU 的存储器读写速度越快，造价越贵，容量越小。

这里还举了一个例子：如果你的程序需要的数据是存储在CPU寄存器中的，那么在指令的执行期间，在 0 个周期内就能访问到它们。如果存储在高速缓存中，需要4~75个周期。如果存储在主存中，需要上百个周期。而如果存储在磁盘上，需要大约几千万个周期！

因此，为了考虑程序的性能，我们按照访问的频率，让数据在存储器中依次排好，以便于 CPU 能更快的访问到它需要的数据。

存储技术

随机访问存储器

随机访问存储器（Random-Access Memory，RAM）分为两类：静态的和动态的。静态RAM（SRAM）比动态RAM（DRAM）更快，但也贵得多。

SRAM

它的每一位存储单元都是双稳态的，特性就是：可以无限期地在两种电压模式下保存，其它任何电压的状态都是不稳定的。

这里给了一个图，描述了这个特性：

只有倒向左边或者倒向右边两种状态是稳定的，其余状态均不稳定，如果出现干扰，只要干扰不是很大，那么它有能力在干扰结束之后迅速恢复到原来的稳态。

DRAM

每一位使用电容存储，它和SRAM相反，对干扰比较敏感。当电容的电压被扰乱之后，它就永远不会恢复了。暴露在光线下会导致电容电压改变，数码照相机和摄像机中的传感器本质上就是DRAM单元的阵列。

会有很多原因导致DRAM漏电，使得DRAM单元在10~100毫秒时间内失去电荷。但是因为这时间还是足够长的，我们可以周期性地重写来刷新每一位，或者使用纠错码发现每个单元的错误位。

---

两个RAM的特性：只要有供电，SRAM就会保持不变。与DRAM不同，它不需要刷新。SRAM的存取比DRAM快。SRAM对诸如光和电噪声这样的干扰不敏感。代价是SRAM单元比DRAM单元使用更多的晶体管，因而密集度低，而且更贵，功耗更大。

SRAM主要应用在Cache当中，DRAM主要应用在主存当中。

传统DRAM

就是由 d 行 w 列的比特位组成了一个超单元，r 行 c 列的超单元组成了 DRAM 芯片。

在这里，我们在外面可以看到有一根地址线和一根数据线，数据线就是读数据或者写数据，地址线只有两位，是行列共享的，因为我们的数据是 8 位，超单元也是由 2 行 4 列（也有可能是 4 行 2 列）的位组成，因此一个超单元就表示了一个字节。

下图演示了读取 DRAM 数据的一个过程

先从地址线告诉它我要读行 2，于是取出行 2 的所有内容到内部行缓冲区，然后再从地址线输入 1，表示要读列 1 的数据，于是取出第一列的数据给 data 读出。

设计成二维的形式减少了引脚数量，但是增加了访问时间，因为行列需要分两次发送。

内存模块

内存模块是由 DRAM 芯片封装而成的，下图演示了一个 64 位的内存模块情况：

我们发送一个 i 和 j，会被广播到所有 DRAM 芯片，那么 8 个 DRAM 芯片都给出一个字节那么得到的就是一个 64 位的字。

增强的DRAM

这里仅仅是介绍了几种特殊的存储器。

非易失性存储器

如果断电，DRAM 和 SRAM 会丢失它们的信息，从这个意义上说，它们是易失的（volatile）。

非易失性存储器（nonvolatile memory）即使是在关电后，仍然保存着它们的信息。由于历史原因，虽然 ROM 中有的类型既可以读也可以写，但是它们整体上都被称为只读存储器（Read-Only Memory，ROM）。

存储在ROM设备中的程序通常被称为固件（firmware）。当一个计算机系统通电以后，它会运行存储在ROM中的固件。

访问主存

主存和 CPU 是通过总线（bus）交互数据的。

这些部件由一对总线连接起来，其中一条总线是系统总线（system bus），它连接CPU 和I/O桥接器，另一条总线是内存总线（memory bus），它连接I/O桥接器和主存。

下面有一个从内存中读取数据到寄存器的一个过程

那么同样，写的操作就是：

首先，CPU将地址放到系统总线上。内存从内存总线读出地址，并等待数据到达（图6-8a）。接下来，CPU将%rax中的数据字复制到系统总线（图6-8b）。最后，主存从内存总线读出数据字，并且将这些位存储到DRAM中，就像下图一样。

磁盘存储

磁盘是广为应用的保存大量数据的存储设备，存储数据的数量级可以达到几百到几千千兆字节，而基于RAM的存储器只能有几百或几千兆字节。不过，从磁盘上读信息的时间为毫秒级，比从DRAM读慢了10万倍，比从SRAM读慢了100万倍。

磁盘的构造

磁盘是由盘片（platter）构成的。每个盘片有两面或者称为表面（surface），表面覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴（spindle），它使得盘片以固定的旋转速率（rotational rate）旋转，通常是5400~15000转每分钟（Revolution Per Minute，RPM）。磁盘通常包含一个或多个这样的盘片，并封装在一个密封的容器内。

每个盘片包含多个同心圆组成的磁道，每个磁道会被划分为一组扇区（直接这么记：多个扇区构成一个磁道），每个扇区包含相等数量的数据位（通常是512字节）。扇区之间由一些间隙（gap）分隔开这些间隙中不存储数据位。间隙存储用来标识扇区的格式化位。

柱面是指每个盘的同一磁道的集合，比如每个盘的第一个同心圆组成了第一个柱面。

磁盘容量

一个磁盘上可以记录的最大位数称为它的最大容量，或者简称为容量。磁盘容量是由以下技术因素决定的：

• 记录密度（recording density）（位/英寸）：磁道一英寸的段中可以放入的位数。
• 磁道密度（track density）（道/英寸）：从盘片中心出发半径上一英寸的段内可以有的磁道数。
• 面密度（areal density）（位/平方英寸）：记录密度与磁道密度的乘积。

容量计算就显而易见了，首先从外表来看，一个磁盘有多张盘，那么盘的个数 \(\times 2\) 就是表面数，然后再算一面有多少磁道，这就 \(\times \text{磁道密度}\)，算出有多少磁道，根据这里的记录密度大概理解应该是每一磁道上的平均扇区数，再乘上去，最后就是算出来一个扇区数乘每个扇区拥有的字节数就是磁盘的容量了。

所以有了这个公式：

练习题6.2. 计算这样一个磁盘的容量，它有2个盘片，10000个柱面，每条磁道平均有400个扇区，而每个扇区有512个字节。

柱面前面说了，就是有 2k 个磁道构成的集合，这里的 k 是盘片的个数。所以最后就是：

\(2\times 2\times 10^4\times 400 \times 512 \div 1024\text{KB}=8\times 10^6\text{KB}\)

磁盘操作

总的来说，就是磁盘在读写数据的时候，先寻道（seek），找到扇区所在的磁道，因为每个盘面都有一个读写头，这些读写头会保证每次寻道所有读写头都在同一柱面上面。找到了磁道之后，磁盘开始旋转，找到对应的扇区，这里有一个平均时间和最大时间，一般来说，最大时间就是磁盘转一圈所需的时间，而平均时间就是转半圈的时间

然后下面有几个概念：

• 寻道时间：指的是找到磁道所花费的时间
• 旋转时间：指的是找到对应扇区所花费的时间，公式里给的是 \(\frac{1}{RPM}\times \frac{60S}{1min}\)，其实这里的 RPM 就是转速，单位为转/分钟
• 传送时间：其实这就是指的一个扇区被读完所需的时间，公式多乘了一个 \(\frac{1}{\text{平均扇区数}/\text{磁道}}\)，其实也很容易理解，就是转过一个扇区所用的时间。

逻辑磁盘块

我们所看到的磁盘比较复杂，为了便于操作系统读取磁盘数据，现代磁盘为我们构造了一个简单的视图，是一个 B 个扇区大小的逻辑块序列，磁盘封装中有一个设备叫磁盘控制器维护了逻辑块号（对操作系统的抽象）和磁盘扇区（物理扇区）之间的映射关系。

操作系统想要执行 IO 操作读写文件的时候，就会发送一个逻辑块号给磁盘控制器翻译成一个三元组（盘面，磁道，扇区）找到对应的值进行读写。

I/O设备

介绍了一些设备：

• 通用串行总线（Universal Serial Bus，USB）控制器是一个连接到USB总线的设备的中转机构，USB总线是一个广泛使用的标准。
• 图形卡（或适配器）包含硬件和软件逻辑，它们负责代表CPU在显示器上画像素。
• 主机总线适配器连接磁盘。
• 其他的设备，例如网络适配器，可以通过将适配器插入到主板上空的扩展槽中，从而连接到 I/O 总线，这些插槽提供了到总线的直接电路连接。

访问磁盘

地址空间中，有一部分地址是为了与 I/O 设备通信保留的，发起 I/O 通信的时候会映射一个或多个端口。当一个设备连接到总线的时候，它会与一个或多个端口相关联。

我们读取磁盘的时候发生了以下的步骤：

• 发出第一条指令，指明是读指令，还会伴随一些其它参数，例如读取完毕是否中断CPU。
• 发出第二条指令，指明磁盘的逻辑块号。
• 发出第三条指令，指明读取的内容存放在主存的哪个地址上。

一般发出请求之后，CPU就会去干其他事情，因为读取磁盘相对于执行指令来说是慢了好几个数量级的。

在磁盘控制器收到指令的时候，CPU就不必去管它了，因为剩下的就是主存和磁盘之间的数据交互了，像这样子设备可以自己执行读写而不需要 CPU 的干涉的过程称为直接内存访问（Direct Memory Access，DMA）

传送完成之后，磁盘控制器会给 CPU 发一个中断信号来通知 CPU 已经完成了数据传送的操作。基本思想就是通过发送信号给 CPU 芯片的外部引脚，让 CPU 暂停执行的工作，跳转到一个操作系统的例程，执行完一些擦做之后回到被中断的地方。

固态硬盘

固态硬盘（Solid State Disk，SSD）是一种基于闪存（flash）的存储技术。封装了一些其它设备，这个设备使得我们操作系统访问起来与传统硬盘没有区别，且比传统硬盘访问速度更快。

这里的闪存翻译层就相当于前面磁盘的磁盘控制器。

一个闪存由 B个块的序列组成，每个块由P页组成。通常，页的大小是512字节~4KB，块是由32~128页组成的，块的大小为16KB~512KB。数据是以页为单位读写的。只有在一页所属的块整个被擦除之后，才能写这一页（通常是指该块中的所有位都被设置为1）。不过，一旦一个块被擦除了，块中每一个页都可以不需要再进行擦除就写一次。在大约进行100000次重复写之后，块就会磨损坏。一旦一个块磨损坏之后，就不能再使用了。

固态硬盘能耗低，速度快，但是反复写之后会磨损，硬盘内部有一个逻辑，使得反复写会均摊到每一个块上去，使得固态硬盘寿命没有看上去那么低。那么同样，高性能带来的必定是昂贵的价格，同等存储容量下，固态会比普通磁盘贵 30 倍。不过因为 SSD 越来越受欢迎，它们之间的价格差距也在逐步减少。

存储技术的优势

按照存储速度排序，我们讲过的四个存储器，它们从大到小的存储速度是 SRAM>DRAM>SSD>旋转磁盘。

局部性

计算机程序通常是具有局部性的，它们会倾向于引用自己附近的内存区域或者是自己本身，比如一个循环程序，它就会反复执行一个局部的代码或者是局部的一个变量，这种倾向性被称为局部性原理。

• 时间局部性：被引用过一次的内存位置很可能在不远的将来再被多次引用
• 空间局部性：如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置

书上讲了一个例子，是分别对取指和数据引用的局部性的讨论。

sum = 0; 
for (i = 0; i<n; i++){
    sum += a[i]; 
}
return sum;

还有下面两个局部性很好和很差的看起来差不多的两个程序：

int sum(int a[M][N]){
    int i,j,sum=0;
    for(i=0;i<M;i++){
        for(j=0;j<N;j++){
            sum+=a[i][j];
        }
    }
}

另一个是：

int sum(int a[M][N]){
    int i,j,sum=0;
    for(i=0;i<N;i++){
        for(j=0;j<M;j++){
            sum+=a[j][i];
        }
    }
}

对程序数据引用的局部性

这里的数据就只有 sum 和 a[i] 数组。

空间局部性体现在我访问 a[i] 数组上，因为我下一次循环我就会访问我上一次访问过的元素的后面一个位置。

时间局部性就体现在我访问 sum 变量上，因为每次我都会取得 sum 变量去进行运算。

我们再来看第二个程序和第三个程序，显然，第二个程序拥有更好的空间局部性，因为每次循环我会制造步长为 1 的空间移动，而第三个程序每次循环会制造间隔为 N 的空间移动（在a[M][N] 中，a[i][j]~a[i][j+1] 地址紧邻而 a[i][j] 和 a[i+1][j] 相差了 N 个 int 的数据）。

取指的局部性

空间局部性就体现在循环内部，所有指令都是紧挨着运行的。

时间局部性就体现在循环内部，一条指令会在将来被执行多次。

局部性小结

• 重复引用相同变量的程序有良好的时间局部性。
• 对于具有步长为k的引用模式的程序，步长越小，空间局部性越好。具有步长为1的引用模式的程序有很好的空间局部性。在内存中以大步长跳来跳去的程序空间局部性会很差。
• 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

存储器层次结构

• 对于存储技术来说，我们需要构建出层次结构的体系，离 CPU 越近的容量越小，访问速度越快，单位字节的造假越高。
• 对于计算机程序来说，我们要尽量编写符合局部性原理的程序。

根据存储器层次结构，我们可以构建出以下的存储层次：

存储器层次结构中的缓存

存储器层次结构的中心思想是，对于每个k，位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存。例如，本地磁盘作为通过网络从远程磁盘取出的文件（例如Web页面）的缓存，主存作为本地磁盘上数据的缓存，依此类推，直到最小的缓存-—CPU寄存器组。

下图就展示了缓存的一个原理

数据总是以块大小为传送单元（transfer unit）在第k层和第k+1层之间来回复制的。 虽然在层次结构中任何一对相邻的层次之间块大小是固定的，但是其他的层次对之间可以有不同的块大小，比如 CPU 和 Cache 之间可能只有十几个字节的大小，而主存到硬盘之间可能有几兆甚至几十兆的大小。

缓存命中

如果我们需要第 k+1 层的数据 d 时，如果它刚好在第 k 层中，那么称为缓存命中（cache hit）。

缓存不命中

另一方面，如果第k层中没有缓存数据对象d，那么就是我们所说的缓存不命中（cache miss）。当发生缓存不命中时，第k层的缓存从第k+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了，可能就会覆盖现存的一个块。

---

覆盖一个现存的块的过程称为替换（replacing）或驱逐（evicting）这个块。被驱逐的这个块有时也称为牺牲块（victim block）。决定该替换哪个块是由缓存的替换策略（replace-ment policy）来控制的。例如，一个具有随机替换策略的缓存会随机选择一个牺牲块。一个具有最近最少被使用（LRU）替换策略的缓存会选择那个最后被访问的时间距现在最远的块。

缓存不命中的种类

有一种命中称为冷不命中（cold miss），是指当第 k 层的缓存为空时，此时无论访问什么数据都会发生不命中，此类也成为强制不命中。

只要发生了不命中，就需要执行替换策略，有一种很简单的替换策略是我们允许 k+1 层中的块放在任何一个位置，这样我们替换的时候很方便，但是需要用到的时候则需要遍历整个 k 层存储器，代价很高。

再上面那张图中，就不一样了，因为 k+1 层的第 i 块只会放到 k 层中第 i mod 4 块的位置上。我们在寻找的时候，就可以用很低的复杂度快速判断我们的块在不在第 k 层了。

但是这种策略会引起另一种不命中叫冲突不命中（conflict miss），比如还是上面那张图，我先访问 0 块，不命中替换到 k 层第 0 块，再访问第 8 块，不命中替换掉里面的 0 块。如此反复 0 8 0 8 的访问会导致缓存一直不命中，然而 k 层的缓存还有很多空间可以使用。

如果循环体过大，或者是数组遍历过大，我们也有概率发生不命中，因为这个大小已经远远超过缓存能容纳的大小，此时缓存会经历容量不命中（capacity miss），就是说缓存太小了，容纳不下。

缓存管理

缓存一般需要由硬件、软件，或两者的结合来管理。

• 例如编译器管理寄存器文件是缓存结构的最高层，它将决定哪些数据放寄存器，哪些数据放内存中，以及决定不命中时如何替换的策略。
• L1，L2，L3层的缓存是由内置的硬件逻辑来管理的。
• 在一个有虚拟内存的系统中，DRAM主存作为存储在磁盘上的数据块的缓存，是由操作系统软件和CPU上的地址翻译硬件共同管理的。
• 对于一个具有像AFS这样的分布式文件系统的机器来说，本地磁盘作为缓存，它是由运行在本地机器上的AFS客户端进程管理的。在大多数时候，缓存都是自动运行的，不需要程序采取特殊的或显式的行动。

存储器层次结构概念小结

总的来说，因为程序的局部性，我们的层次结构就有很大的作用。

• 利用时间局部性：由于时间局部性，同一数据对象可能会被多次使用，后续我们的多次访问都会访问上一级的存储器，速度快的多。
• 利用空间局部性：块通常包含有多个数据对象。由于空间局部性，我们会期望后面对该块中其他对象的访问能够补偿不命中后复制该块的花费。

高速缓存存储器

缓存的出现是因为 寄存器 存储速度和主存的存储速度不断加大导致的，系统设计者就在主存和寄存器之间插入了一个缓存，它的存储速度和 寄存器 差不多，四个时钟周期可以访问到，称为 L1 高速缓存。随着差距再不断增大就出现了 L2 L3 高速缓存。

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

高速缓存大概是长这样：

这么想：

假设内存地址长度为 m，那么每一行中，他会存储 \(2^b\) 个字节，这就证明地址的低 b 位不影响判断结果，剩余的 m-b 位中，就剩下了 \(2^{m-b}\) 个的情况，又因为它们会被均分到 s 个组，假设是取模实现的，那么在此情况下，低 s 位就确定了你放在哪一组。即便是确定了哪一组，依然无法准确判断出就是我要找的那个，因为我的高 \(m-b-s\) 位产生了 \(2^{m-b-s}\) 种类的情况，因此这个标记就是存这高 \(m-b-s\) 位的地址，以确保放在这的一定是我要找的值。

直接映射高速缓存

特殊的，组内行数为 1 时，我们叫它直接映射高速缓存。

进行组选择，行匹配之后，就能确定是否命中，若命中则执行字抽取

组选择

这个组选择先屏蔽掉低 b 位的块偏移之后，取得低 s 位，这个数值就是组号，像下面这张图一样：

行匹配

就是高的那 t 位，只有这一位和标记位完全对应上才说明 cache 行里面装的是我要的数据。

字选择

通过最低的 b 位块偏移就可以在高速缓存行里找到了

不命中时的行替换

很简单，因为每组只有一行，因此不命中直接替换当前行即可。

运行中的直接映射高速缓存

这里举了一个例子去模拟。

假设 Cache 的参数 (S,E,B,m)=(4,1,2,4)。

那么 Cache 是四组，每组两个字节，地址是四位，用列表去模拟，这里因为四位的地址仅仅 16 种情况，因此可以把它们都列出来。

初始状态下，cache 如下：

组	有效位	标记位	块[0]	块[1]
0	0
1	0
2	0
3	0

读地址 0 的字，找到组 0，有效位为 0，执行替换策略。

组	有效位	标记位	块[0]	块[1]
0	1	0	m[0]	m[1]
1	0
2	0
3	0

读地址 1 的字，找到组 0，有效位为1，标记匹配，直接取出，cache 没有任何变化。

再读地址 13 的字，找到组 2，有效位为 0，执行替换策略。

组	有效位	标记位	块[0]	块[1]
0	1	0	m[0]	m[1]
1	0
2	1	1	m[12]	m[13]
3	0

读地址 8 的字，找到组 0，有效位为 1，标记位没有对上，发生不命中，执行替换策略。

组	有效位	标记位	块[0]	块[1]
0	1	1	m[8]	m[9]
1	0
2	1	1	m[12]	m[13]
3	0

后面就不继续模拟了，到这里应该是很清晰了这个过程。

直接映射高速缓存中的冲突不命中

冲突不命中前面讲过，在直接映射高速缓存中，同一组的不同行多次被反复访问，会导致 cache 一直不命中（因为只有一行，每次都需要替换）。这里举了一个例子：

float dotprod(float x[8],float y[8]){
    float sum=0;
    int i;
    for(i=0;i<8;i++){
        sum+=x[i]*y[i];
    }
    return sum;
}

这个程序看起来是具有很好的局部性的，事实上有可能 x[i] 与 y[i] 的组号永远相同，假设 cache 行的行长为 4，x 数组与 y 数组地址紧邻，那么就会出现这种情况，实际上有可能导致速度下降两倍或者三倍，这个情形我们叫抖动，因为每次循环，它一直在 x 和 y 之间来回访问。

我们的修正思路也很容易，只需要在 x 数组之后填充上 B 个字节（把float[8] 定义为 float[12]），让它们完全不在同一个组当中即可解决问题。

这里的旁注还回答了一个问题：为什么不用高位做索引而是用中间的位作为索引，是有好的原因的。高位做索引和中间位做索引的区别如下：

可以发现，高位做索引的话，同组块基本上物理相邻，而中间位做索引的话同组的块物理都不相邻。因为程序局部性的原理，假设程序的局部性局限在连续的四块中间，那么高位索引的命中率将会很低（冲突不命中比较多，且cache使用率很低，从始至终只用了组0，其余组始终为空），而中间位索引的命中率会很高（只有几次的冷不命中，其余全命中）。

组相联高速缓存

直接映射高速缓存中冲突不命中造成的问题源于每个组只有一行（E=1）这个限制。组相联高速缓存（set associative cache）放松了这条限制，所以每个组都保存有多于一个的高速缓存行。一个1<E<C/B的高速缓存通常称为E路组相联高速缓存，如果 E=C/B，那么组数为 1。

如图就是 2 路组相联高速缓存

组选择

和直接映射的思路一模一样。

行匹配和字选择

行匹配需要遍历组中的每一行，来检验标记位是否相同。

字选择思路也和直接映射的一模一样。

不命中时的行替换

需要使用一定的策略，

• 随机选择要替换的行是最简单的替换策略，也最容易实现。

其他更复杂的策略利用了局部性原理，以使在比较近的将来引用被替换的行的概率最小。

• 最不常使用（Least-Frequently-Used，LFU）策略会替换在过去某个时间窗口内引用次数最少的那一行（适用于空间局部性较高的程序）。
• 最近最少使用（Least-Recently-Used，LRU）策略会替换最后一次访问时间最久远的那一行（适用于时间局部性较高的程序）。

所有这些策略都需要额外的时间和硬件。但是，越往存储器层次结构下面走，远离CPU，一次不命中的开销就会更加昂贵，用更好的替换策略使得不命中最少也变得更加值得了。

全相联高速缓存

就是组相联高速缓存中 E=C/B 的情况，也就是只有一个组的情况。

组选择

没得选，只有一组。

行匹配

同样是遍历所有的行。

字选择

都一样。

不命中替换策略

同组相联。

---

全相联高速缓存器只适合做小的高速缓存，如果过大会导致效率降低。

这里的练习题建议做做，加深对 cache 的理解。

有关写的问题

写的情况就要复杂一些了。假设我们要写一个已经缓存了的字 w（写命中，write hit）。在高速缓存更新了它的w的副本之后，怎么更新w在层次结构中紧接着低一层中的副本呢？最简单的方法，称为直写（write-through），就是立即将w的高速缓存块写回到紧接着的低一层中。虽然简单，但是直写的缺点是每次写都会引起总线流量。另一种方法，称为**写回*（write-back），尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块时，才把它写到紧接着的低一层中。由于局部性，写回能显著地减少总线流量，但是它的缺点是增加了复杂性。高速缓存必须为每个高速缓存行维护一个额外的修改位（dirty bit），表明这个高速缓存块是否被修改过。

另一个问题是如何处理写不命中。一种方法，称为写分配（write-allocate），加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块。写分配试图利用写的空间局部性，但是缺点是每次不命中都会导致一个块从低一层传送到高速缓存。另一种方法，称为非写分配（not-write-allocate），避开高速缓存，直接把这个字写到低一层中。直写高速缓存通常是非写分配的。写回高速缓存通常是写分配的。

实际的高速缓存

我们一直假设高速缓存只保存数据，但是其实还有保存指令的高速缓存，称为 i-cache，而只保存数据的称为 d-cache，既保存数据又保存指令的高速缓存叫统一高速缓存（unified cache）。

高速缓存参数的性能影响

• 不命中率（miss rate）。在一个程序执行或程序的一部分执行期间，内存引用不命中的比率。它是这样计算的：不命中数量/引用数量。
• 命中率（hit rate）。命中的内存引用比率。它等于1-不命中率。
• 命中时间（hit time）。从高速缓存传送一个字到CPU所需的时间，包括组选择、行确认和字选择的时间。对于L1高速缓存来说，命中时间的数量级是几个时钟周期。
• 不命中处罚（miss penalty）。由于不命中所需要的额外的时间。L1不命中需要从L2得到服务的处罚，通常是数10个周期；从L3得到服务的处罚，50个周期；，从主存得到的服务的处罚，200个周期。

这四个参数实际上就是要求我们在命中率和命中时间之间做出权衡。我们读取一个数的期望时间就是 ：

\(\text{miss rate} \times \text{miss penalty}+\text{hit rate}\times \text{hit time}\)

如果我们提高了命中率却大幅提高了命中时间，那就得不偿失了。

高速缓存大小的影响

一方面，较大的高速缓存可能会提高命中率。另一方面，使大存储器运行得更快总是要难一些的。结果，较大的高速缓存可能会增加命中时间，所以我们才会有 L1 L2 L3的排列顺序。

块大小的影响

能更高地利用空间局部性，但是可能对时间局部性利用不足。

相联度的影响

E值较大的优点就是解决了抖动冲突不命中的问题，但是我们需要较高的命中时间惩罚来补偿这个问题。

写策略的影响

一般来说，越往下越是采取写回的方式而不是直接写。

编写高速缓存友好代码

我们要在循环体内部，尽量减少缓存的不命中率，所以步长为 1 的代码对高速缓存是友好的。

对局部变量的反复引用也是友好的，因为反复引用的局部变量编译器会考虑放在寄存器当中。

尤其体现在二维数组当中，内循环按行访问和按列访问是完全不一样的结果，按列访问对高速缓存极不友好。

Cache Lab

这个 README 也详细说明了，我们需要在 csim.c 和 trans.c 文件，然后通过运行一些文件来获得测评分数。

至于 cache 模拟器，它题目给了你一个 csim-ref，要求实现差不多的功能。

这里有很多测评数据，存放在 traces 文件夹中。测评数据需要自己读取，每一行表示一个操作，一行有三个数据，第一个数据表示操作。

• L 表示加载数据
• S 表示存数据
• M 表示修改数据之后
• I 表示加载指令

第二列的数据表示我们操作的地址，第三个数据表示数据大小。

并且要求我们使用 LRU 算法实现。

Part A

我们设计从最开始考虑，第一考虑命令行参数的读取。

命令行参数

一般是打印一串文字或者是接收对应的参数。

这里复制一下那个文件打印出的说明就行了，适当改改。

void PrintUsage(){
    printf( "Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>\n"
            "Options:\n"
            "  -h         Print this help message.\n"
            "  -v         Optional verbose flag.\n"
            "  -s <num>   Number of set index bits.\n"
            "  -E <num>   Number of lines per set.\n"
            "  -b <num>   Number of block offset bits.\n"
            "  -t <file>  Trace file.\n"
            "\n"
            "Examples:\n"
            "  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n"
            "  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}

这里本着最认真负责的态度，编写了处理命令行参数的一个函数。

void ProcessParams(int argc,char **argv){
    int i=1;
    char *error=0,len=0;
    while(i!=argc){
        if(argv[i][0]=='-'){
            switch (argv[i][1])
            {
            case 'h':
                goto Usage;
                break;
            case 'v':
                isVerbose=1;
                break;
            case 's':
                i+=1;
                if(i>=argc){
                    error="Missing params";
                    goto errout;
                }
                s=atoi(argv[i]);
                break;
            case 'E':
                i+=1;
                if(i>argc){
                    error="Missing params";
                    goto errout;
                }
                E=atoi(argv[i]);
                break;
            case 'b':
                i+=1;
                if(i>=argc){
                    error="Missing params";
                    goto errout;
                }
                b=atoi(argv[i]);
                break;
            case 't':
                i+=1;
                if(i>=argc){
                    error="Missing params";
                    goto errout;
                }
                char *filepath=argv[i];
                fd=open(filepath,0);
                if(fd==-1){
                    int len=strlen(argv[i]);
                    error=(char *)malloc(len+20);
                    sprintf(error,"%s: File Not Found!",argv[i]);
                    goto errout;
                }
                break;
            default:
                len=strlen(argv[i]);
                error=(char *)malloc(len+25);
                sprintf(error,"Unknown Param option %s",argv[i]);
                goto errout;
                break;
            }
        }
        else{
            error="Bad params";
            goto errout;
        }
        i++;
    }
    if(s==-1||fd==-1||E==-1||b==-1){
        error="Missing params";
        goto errout;
    }
    return ;
errout:
    printf("%s: %s\n",argv[0],error);
Usage:
    PrintUsage();
}

看着我自己都摇头了，不过第一步就是大功告成了。

之后就是读指令去处理了。

这里试了很多次发现一个坑，就是如果是指令，我们是不需要去处理的，然后就是我分配内存也分配了个寂寞，因为它只是模拟没有真的数据，所以我们就没办法去测试数据准确性，然后就是数据大小我们也不需要管的，虽然我还是通过字符串处理把它分离出来了，但是后面还是注释掉了。

再就是，如果是 M，那么相当于两次连续的访问，第二次不用管必定命中的，所以 M 除了 HitCount 额外 ++ 和其它的没区别。

最终代码：

#include "cachelab.h"
#include <stdlib.h>
#include <stdio.h>
#include <fcntl.h>
#include <string.h>
#include <unistd.h>
#define INF 0x3f3f3f3f
int HitCount,MissCount,EvictCount;
int isVerbose=0,s=-1,b=-1,E=-1,S,e,B;
int fd=-1;
FILE *fp;
int timestamp=1;
char buffer[0x500000];
typedef struct xia0ji233{
    int n;
    int *LastUsed;
    int *flag;
    int *CacheRecord;
    char *CacheLine;
}Cache;
Cache test;
void PrintUsage(){
    printf( "Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>\n"
            "Options:\n"
            "  -h         Print this help message.\n"
            "  -v         Optional verbose flag.\n"
            "  -s <num>   Number of set index bits.\n"
            "  -E <num>   Number of lines per set.\n"
            "  -b <num>   Number of block offset bits.\n"
            "  -t <file>  Trace file.\n"
            "\n"
            "Examples:\n"
            "  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n"
            "  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}
void ProcessParams(int argc,char **argv){
    int i=1;
    char *error=0,len=0;
    while(i!=argc){
        if(argv[i][0]=='-'){
            switch (argv[i][1])
            {
            case 'h':
                goto Usage;
                break;
            case 'v':
                isVerbose=1;
                break;
            case 's':
                i+=1;
                if(i>=argc){
                    error="Missing params";
                    goto errout;
                }
                s=atoi(argv[i]);
                break;
            case 'E':
                i+=1;
                if(i>=argc){
                    error="Missing params";
                    goto errout;
                }
                E=atoi(argv[i]);
                break;
            case 'b':
                i+=1;
                if(i>=argc){
                    error="Missing params";
                    goto errout;
                }
                b=atoi(argv[i]);
                break;
            case 't':
                i+=1;
                if(i>=argc){
                    error="Missing params";
                    goto errout;
                }
                char *filepath=argv[i];
                fd=open(filepath,0);
                fp=fopen(filepath,"r");
                if(fd==-1){
                    int len=strlen(argv[i]);
                    error=(char *)malloc(len+20);
                    sprintf(error,"%s: File Not Found!",argv[i]);
                    goto errout;
                }
                break;
            default:
                len=strlen(argv[i]);
                error=(char *)malloc(len+25);
                sprintf(error,"Unknown Param option %s",argv[i]);
                goto errout;
                break;
            }
        }
        else{
            error="Bad params";
            goto errout;
        }
        i++;
    }
    if(s==-1||fd==-1||E==-1||b==-1){
        error="Missing params";
        goto errout;
    }
    return ;
errout:
    printf("%s: %s\n",argv[0],error);
Usage:
    PrintUsage();
    exit(-1);
}
void InitCache(){
    S=1<<s;
    B=1<<b;
    int x=E;
    while(x==-1){
        x>>=1;
        e++;
    }
    test.CacheLine=(char *)malloc(S*E*B);
    test.CacheRecord=(int *)malloc(S*E*sizeof(int));
    test.flag=(int *)malloc(S*E*sizeof(int));
    memset(test.flag,0,S*E*sizeof(int));
    test.LastUsed=(int *)malloc(S*E*sizeof(int));
}
int SelectLine(int Gid,int Record){//return 0 miss,1 hit,-1 cold miss;
    int LineStart=Gid*E;
    for(int i=LineStart;i<LineStart+E;i++){
        if(!test.flag[i]){
            MissCount++;
            return -1;
        }
        if(test.CacheRecord[i]==Record){
            test.LastUsed[i]=timestamp;
            HitCount++;
            return 1;
        }
    }
    MissCount++;
    return 0;
}
void Replace(int type,int Gid,int Record){
    int LineStart=Gid*E;
    if(type==-1){
        int i;
        if(isVerbose)printf(" cold miss");
        for(i=LineStart;i<LineStart+E;i++){
            if(test.flag[i])continue;
            else break;
        }
        test.CacheRecord[i]=Record;
        test.flag[i]=1;
        test.LastUsed[i]=timestamp;
    }
    else if(type==0){//LRU
        int sel=LineStart;
        for(int i=LineStart+1;i<LineStart+E;i++){
            if(test.LastUsed[sel]>test.LastUsed[i]){
                sel=i;
            }
        }
        test.CacheRecord[sel]=Record;
        test.LastUsed[sel]=timestamp;
        EvictCount++;
        if(isVerbose)printf(" miss evict");
    }
}
int Hex2Int(char *str){
    int len=strlen(str);
    int sum=0;
    for(int i=0;i<len;i++){
        switch(str[i]){
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
            sum*=16;
            sum|=str[i]-'0';
            break;
        case 'a':
        case 'b':
        case 'c':
        case 'd':
        case 'e':
        case 'f':
            sum*=16;
            sum|=str[i]-'a'+10;
            break;
        default:
            break;
        }
    }
    return sum;
}
int FindDot(char *s){
    int len=strlen(s);
    for(int i=0;i<len;i++){
        if(s[i]==',')return i;
    }
    return -1;
}
void ProcessIns(){
    char str[1000];
    int i=0;
    for(;;){
        char *res=fgets(str,1000,fp);
        if(res==0)break;
        //if(str==NULL)break;
        //printf("%d:%s\n",i,str);
        int Dot=FindDot(str);
        i++;
        if(Dot==-1){
            exit(-1);
        }
        char *tmpstr=malloc(Dot-1);
        memcpy(tmpstr,str+3,Dot-2);
        tmpstr[Dot-2]=0;
        int addr=Hex2Int(tmpstr);
        free(tmpstr);
        //int size=atoi(str+Dot+1);
        //int DataOffset=((1<<b)-1)&addr;
        int Gid=(addr>>b)&((1<<s)-1);
        int Record=addr>>(s+b);
        //printf(" Gid: %d,Record: %d",Gid,Record);
        int ret;
        if(str[0]!=' '){
            /*ret=SelectLine(Gid,Record);
            if(ret<=0){
                Replace(ret,Gid,Record);
            }
            else{
                if(isVerbose)printf(" hit");
            }*/
        }
        else{
            switch(str[1]){
                case 'M':
                    HitCount++;
                case 'L':
                case 'S':
                    ret=SelectLine(Gid,Record);
                    //ret=-1;
                    if(ret<=0){
                        Replace(ret,Gid,Record);
                    }
                    else{
                        if(isVerbose)printf(" hit");
                    }
            }
        }
        timestamp++;
        if(isVerbose)putchar(10);
    }
}
int main(int argc ,char **argv)
{
    ProcessParams(argc,argv);
    InitCache();
    ProcessIns();
    printSummary(HitCount,MissCount,EvictCount);
    return 0;
}

初始文件我记得就五六行，活生生给我水到 200 多行，不得不说真的能水。。。。

这个实验其实细心去理解那个 Cache 也没有很难，自己肯定是能写出来的。

运行结果：

自然是 27 分满分的。

Part B

想了想，对我帮助不大，我决定不写了！