读CSAPP之RAM、Locality和Cache

今年是离开校园的第六年，这六年来我一直在从事应用软件的设计、开发工作，大部分时间是在与高级编程语言、设计模式、业务逻辑打交道。它们大多流于表面，久而久之，与技术底层疏远了，诸如计算机组成原理、汇编语言、编译原理、数据结构以及算法慢慢得生疏，时至今日，向上碰到天花板，向下触到花岗岩。五年是一个契机，趁着下一个五年开始之际，我计划用三个月至半年时想间，重新学习这些知识，以期达到巩固基础，厚积薄发的目的。

本篇是我阅读《Computer System: A Programmer’s Perspective》一书的笔记，该书和与之搭配的《Professional Assembly Language》是我当下阅读计划的一部分。

关于RAM

RAM（Random Access Memory）中文译作随机存取存储器，所谓“随机存取”，指的是当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。相对的，读取或写入顺序访问（Sequential Access）存储设备中的信息时，其所需要的时间与位置就会有关系^[1]，比如磁盘存储器。

RAM 分为 SRAM 与 DRAM 两大类，二者区别在于前者对干扰（光、电）不敏感，用于高速缓存存储器，后者用于主存和显存，以及数码相机和摄像机中的传感器。

DRAM 被分成 d 个超单元，每个超单元都是由 w 个 DRAM 单元组成。DRAM 每次传输 w 位信息。超单元被组织成一个 r 行 c 列的阵列，此时 r*c=d。之所以组织成阵列而不是线性数组，原因之一是降低芯片上地址引脚（pin）的数量，缺点是必须分两次发送地址，增加了访问时间。

关于局部性

局部性（locality）有两种：时间局部性（temporal locality）和空间局部性（spatial locality）。在一个具有良好时间局部性的程序中，被引用过一次的存储器位置很可能很快不远的将来再被多次引用。在一个具有良好空间局部性的程序中，如果一个存储器位置被引用了一次，那么程序很可能很快引用其附近的位置。

对于具有步长为k的引用模式的程序，步长越小，空间局部性越好。如果步长为1，则存储器层次结构中所有层次上的缓存都是将数据存储为连续的块。

对于取指令来说，循环具有很好的时间和空间局部性，循环体越小，循环迭代次数越多，局部性越好。重复引用同一个变量的程序有良好的时间局部性。

关于高速缓存

高速缓存存储器，作为CPU和主存之间的缓存区域，对应用程序性能的影响最大。其结构可以用元组（S，E，B，m）来描述，其大小 C 指的是所有块的大小的和，标记位和有效位不包含在内，因此，C=S*K*B。S=2s，即组数；E 是每个组的行数；B=2b 是块大小。

高速缓存的结构将 m 个地址位分成了 t 个标记位、s 个组索引位和 b 个块偏移位。组索引位告诉字存储在哪个组内；标记位告诉字存储在这个组的哪一行里，只有该行的标记位和地址中的标记位相匹配，并且有效位被设置，才能确定该行确实包含了该字；块偏移位则告诉在 B 个字节的数据块中的字偏移。

块是一个固定大小的信息包，在高速缓存和主存之间来回传送。行是高速缓存中存储块以及其他信息（例如标记位和有效位）的容器。组是一个或多个行的集合。直接映射高速缓存的的组只有一行。全相联高速缓存中组只有一个。

如果每一组里只有一行，即 E=1，那么这个高速缓存被称为直接映射高速缓存（direct-mapped cache）。如果每一组里有多个行，即 1< E<C/B，那么这个高速缓存被称为组相连高速缓存（set associative cache）。如果一个组包含了所有行，即 E=C/B，那么这个高速缓存被称为全相连高速缓存（fully associative cache）。

高速缓存确定一个请求是否被命中，然后抽取出被请求的字的过程，可分为三步：组选择、行匹配、字抽取。

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

全相联高速缓存只适合做小的高速缓存，例如虚拟存储器系统中的翻译备用缓冲器（TLB），它缓存页表项。

直写（write-through）就是立即将高速缓存块写回到接邻着的低一层中，简单，但是每次写都会引起总线流量。写回（write-back）就是尽可能地推迟存储器更新，只有当替换算法要驱逐更新过的块时，才将其写回到低一层中，其显著减少了总线流量，但增加了复杂性。

写分配（write-allocate）就是先加载低一层中的块到高速缓存中，然后更新这个高速缓存块。非写分配（non-write-allocate）就是避开高速缓存，直接写到低一层中。

---

1. 维基百科上关于 RAM 的解释