第一部分

理想状态中，我们将存储器系统视为一个线性字节数组，CPU能在常数时间内访问每个存储器位置。但实际上存储器系统（Memory System）是一个具有不同容量、成本和访问时间的存储设备的层次结构，分别具有以下几部分：

CPU中的寄存器保存最常使用的数据，能在0个时钟周期内访问

高速缓存存储器（Cache Memory）是靠近CPU的、较小的快速存储器，保存一部分从主存储器（Main Memory）取出的常用指令和数据，能在4~75个时钟周期内访问

主存缓存存储磁盘上的数据，需要上百个时钟周期访问

磁盘存储通过网络连接的其他机器的磁盘或磁带上的数据，需要几千万格周期进行访问

上方存储器作为下方存储器的缓存，速度更快、容量更小。

存储器的层次结构之所有有效，是因为程序具有局部性（Locality）的基本属性，倾向于不断访问相同的数据项集合，或者倾向于访问相邻的数据项集合。我们希望程序能具有更好的局部性，使得数据项存储在较高层次的存储器中，这样程序就会倾向于从存储器结构中较高层次访问数据项，运行会更快。

存储技术

随机访问存储器

随机访问存储器（Random-Access Memory，RAM）根据存储单元实现方式可以分为两类：静态的RAM（SRAM）和动态的RAM（DRAM）。

SRAM

将每个位保存到由6个晶体管电路构成的双稳态的（Bistable）存储器单元。
属性：可以无限期地保持在两个不同的电压配置或状态之一，而其他的都是不稳定状态，会迅速转移到两个稳定状态之一。
特点：由于具有双稳态，所以只要有电，就会永远保持它的值，即使有干扰，当干扰消除时就会恢复到稳态。

由于SRAM存取速度较快，只要供电就会保持不变，对光和电噪音等干扰不敏感，但是每位的存储需要6个晶体管，使得造价较为昂贵，且密集度低，使其适合作为小容量高速的高速缓存存储器。

DRAM

将每个位保存为，对一个由访问晶体管控制的电容的充电。
特点：
- 由于每个存储单元比较小，DRAM可以制造的十分密集，可以作为主存或图形系统的帧缓冲区。
- 由于通过电容电压来保存位，当电容电压受到扰动时就无法恢复了。并且电容存在漏电现象，存储单元10~100毫秒会失去电荷，使得内存系统必须周期性通过读出重写来刷新内存的每一位。
- 暴露在光线中会导致电容电压改变。

我们可以将w个DRAM单元组成一个超单元（Supercell），使得一个超单元就能存储w位的信息，并且将d个超单元组合在一个构成一个 d x w DRAM芯片，能够存储dw位信息，并且能对每个超单元进行寻址。并且为了降低地址引脚的数量，我们可以将d个超单元组织成r行、c列的阵列形式。

如上图所示，我们有一个 16 x 8 的DRAM芯片，其中包含16个超单元，每个超单元由8个DRAM单元组成，使得每个超单元能存储8位信息。并且16个超单元被组成4行4列的阵列形式。由一个内存控制器（Memory Controller）通过addr引脚和data引脚将控制DRAM芯片数据的传入和传出，比如想要获得(2,1)处超单元的数据

内存控制器发送行地址（Row Access Strobe，RAS）2到DRAM芯片，则DRAM芯片会将行2中的整行内容复制到内部行缓冲区。
内存控制器发送列地址（Column Access Strobe，CAS）1到DRAM芯片，则DRAM芯片会从内部行缓冲区获得1列的数据，将其发送到内存控制器。

注意：

内存控制器发送RAS和CAS时，使用相同的addr引脚，使得必须分两步发送地址，会增加访问时间。
如果将16个DRAM单元组织成线性形式，则需要4位的地址引脚才能索引到每个超单元，但是将其组织成4行4列的阵列形式，只需要2位的地址引脚。

为了一次性能访问更多的数据，可以将多个DRAM芯片封装到一个内存模块（Memory Module）中，将其扎到主板的扩展槽中。

如上图所示是封装了8个 8M x 8 DRAM芯片的内存模块，每个DRAM芯片负责8位数据，这样一次能对64位字进行读写。比如想要获得地址A处的字：

内存控制器首先将A转化为(i,j)的超单元地址，然后内存控制器依次将i和j广播到所有DRAM芯片中
每个DRAM芯片依次接收到RASi和CASj，会通过上述的方法输出8位数据
模块中的电路收集到所有DRAM芯片输出的8位数据，然后将其合并成一个64位的字，返回给内存控制器

为了进一步扩大存储能力，可以将多个内存模块连接到内存控制器，能够聚合成主存。当内存控制器想要读取地址A处的字时，会先找到包含地址A的内存模块k，然后根据上述步骤得到对应的字。

而基于传统的DRAM单元，可以做一些优化来提高访问基本DRAM单元的速度：

快页模式DRAM（Fast Page Mode DRAM，FPM DRAM）：传统的DRAM芯片通过CAS获得数据后，会将那一行的数据从内部行缓冲区直接删掉，如果访问多个在同一行的超单元时，需要反复读取相同的行。而FPM DRAM能够获取一次行数据后，后面的读取直接从内部行缓冲区读取。
扩展数据输出DRAM（Extended Data Out DRAM，EDO DRAM）：对FPM DRAM进行改进，使得各个CAS信号在时间上更加紧密。
同步DRAM（Synchronous DRAM，SDRAM）：DRAM芯片与内存控制器的通信使用一组显示的控制信号，通常是异步的，而SDRAM使用了，控制内存控制器的外部时钟信号的上升沿来代替控制信号。
双倍数据速率同步DRAM（Double Data-Rate Sychronous DRAM，DDR SDRAM）：对SDRAM的优化，通过使用两个时钟沿作为控制信号，从而使得DRAM的速度翻倍。
视频RAM（Video RAM，VRAM）：用于图形系统的帧缓冲区，与FPM DRAM的区别：VRAM的输出是通过对内部缓冲区的移位得到的，VRAM允许对内存并行地读和写。

从更高层面来看，数据流是通过称为总线（Bus）的共享电子电路在处理器和DRAM主存之间传递数据的。总线是一组并行的导线，能够携带地址、数据和控制信号，也可以将数据和地址信号使用相同的导线。

如上图所示是一个连接CPU和DRAM主存的总线结构。其中I/O桥接器（I/O Bridge）芯片组包括内存控制器，能够将系统总线的电子信号和内存总线的电子信号互相翻译，也能将系统总线和内存总线连接到I/O总线。

当从内存加载数据到寄存器中：

CPU芯片通过总线接口（Bus Interface）在总线上发起读事务（Read Transaction）
CPU会将内存地址发送到系统总线上
I/O桥将信号传递到内存总线
内存接收到内存总线上的地址信号，会从DRAM读取出数据字，然后将数据写到内存总线
I/O桥将内存总线信号翻译成系统总线信号，然后传递到系统总线上
CPU从系统总线上读取数据，并将其复制到寄存器中

当将寄存器中的数据保存到内存中：

CPU芯片通过总线接口发起写事务（Write Transaction）
CPU会将内存地址发送到系统总线上
I/O桥将信号传递到内存总线
内存接收到内存总线上的地址信号，会等待数据到达
CPU将寄存器中的数据字复制到系统总线
I/O桥将系统总线信号翻译成内存总线信号，然后传递到内存总线上
内存从内存总线读出数据，并将其保存到DRAM中。

这里的读事务和写事务统称为总线事务（Bus Transaction）。

非易失性存储器

之前介绍的DRAM和SRAM在断电时都会丢失数据，所以是易失的（Volatile），而非易失性存储器（Nonvolatile Memory）即使断电后，也会保存信息，该类存储器称为只读存储器（Read-Only Memory，ROM），但是现在ROM中有的类型既可以读也可以写了，可以根据ROM能够重编程的次数以及对它们进行重编程所用的机制进行区分，包括：

可编程ROM（PROM）：可以编程一次
可擦写PROM（EPROM）：可以批量擦除
闪存（Flash Memory）：具有部分（块级）擦除功能，大约擦除十万次后会耗尽

存储在ROM设备中的程序称为固件（Firmware），包括BIOS、磁盘控制器、网卡、图形加速器和安全子系统等。当计算机系统通电后，会运行存储在ROM中的固件。

磁盘存储

磁盘（Disk）是被用来保存大量数据的存储设备，但是读信息的速度比DRAM慢10万倍，比SRAM慢100万倍。

如上图所示是一个磁盘的构造。磁盘是由多个叠放在一起的盘片（Platter）构成，每个盘片有两个覆盖着磁性记录材料的表面（Surface）。每个表面由一组称为磁道（Track）的同心圆组成，每个磁道被划分为若干扇区（Sector），每个扇区包含相同数量的数据位（通常为512位）作为读写数据的基本单位。扇区之间通过间隙（Gap）分隔开来，间隙不保存数据信息，只用来表示扇区的格式化位。通常会使用柱面（Cylinder）来描述不同表面上相同磁道的集合，比如柱面k就是6个表面上磁道k的集合。盘片中央会有一个可以旋转的主轴（Spindle），使得盘片以固定的旋转速率（Rotational Rate）旋转，单位通常为RPM（Revolution Per Minute）。

将磁盘能记录的最大位数称为最大容量（容量），主要由以下方面决定：

记录密度（Recording Density）：一英寸的磁道中可以放入的位数
磁道密度（Track Density）：从盘片中心出发，沿着半径方向一英寸，包含多少磁道
面密度（Areal Density）：记录密度和磁道密度的乘积

磁盘容量的计算公式为：

在面密度较低时，每个磁道都被分成了相同的扇区，所以能够划分的扇区数由最内侧磁道能记录的扇区数决定，这就使得外侧的磁道具有很多间隙。现代大容量磁盘采用多区记录（Multiple Zone Recording）技术，将一组连续的柱面划分成一个区，在同一个区中，每个柱面的每条磁道都有相同数量的扇区，由该区中最内侧的磁道决定，由此使得外侧的区能划分成更多的扇区。

如上图所示，磁盘通过一个连接在传动臂（Actuator Arm）上的读/写头（Read/Write Head）来进行读写，对于有多个盘面的磁盘，会用多个位于同一柱面上的垂直排列的读/写头。对于扇区的访问时间（Access Time）由以下几部分构成：

寻道时间：为了读取到目标扇区，会先控制传动臂将读/写头移动到该扇区对应的磁道上，该时间称为寻道时间。
- 影响因素：依赖于读/写头之前的位置，以及传动臂在盘面上移动的速度。
- 通常为3~9ms，最大时间可为20ms。
旋转时间：当读/写头处于目标磁道时，需要等待目标扇区的第一个位旋转到读/写头下。
- 影响因素：目标扇区之前的位置，以及磁盘的旋转速度。
- ，平均旋转时间为该值的一半
传送时间：当读/写头处于目标扇区的第一位时，就可以进行传送了
- 影响因素：磁盘旋转速率，以及每条磁道的扇区数

可以发现：寻道时间和旋转时间是主要影响部分，并且两者大致相等，通常可以寻道时间乘2来估计访问时间。

由于磁盘构造的复杂性，现代磁盘将其抽象为B个扇区大小的逻辑块序列，编号为0,1,...,B-1，通过磁盘中的磁盘控制器来维护逻辑块号和实际扇区之间的映射关系。为此需要通过磁盘控制器对磁盘进行格式化：

会用表示扇区的信息填写在扇区之间的间隙
表示出表面有故障的柱面，并且不进行使用
在每个区会预留一组柱面作为备用，没有映射为逻辑块。当损坏时，磁盘控制器会将数据复制到备用柱面，则磁盘就可以继续正常工作了。

当从磁盘读取数据到主存，需要以下步骤：

操作系统发送一个命令到磁盘控制器，读取某个逻辑块号
磁盘控制器上的固件执行快速表查找，得到该逻辑块号翻译成一个三元组（盘面，磁道，扇区）
磁盘控制器解释三元组信息，将读/写头移动到对应的扇区
将读取到的信息放到磁盘控制器的缓冲区中
将缓冲区中的数据保存到主存中。

如上图所示是一个总线结构实例。对于像图形卡、鼠标、键盘、监视器这类输入/输出设备，都是通过I/O总线连接到CPU和主存的，比如Intel的外围设备互联（Peripheral Component Interconnect，PCI）总线，在PCI模型中，系统中所有的设备共享总线，一个时刻只能有一台设备访问这些线路，目前PCI总线已被PCEe总线取代了。虽然I/O总线比系统总线和内存总线慢，但是能容纳种类繁多的第三方I/O设备

通用串行总线（Universal Serial Bus，USB）控制器：USB总线是一个广泛使用的标准，连接许多外围I/O设备，而USB控制器作为连接到USB总线的设备的中转站。
图形卡（或适配器）：包含硬件和软件逻辑，负责CPU在显示器上画像素。
主机总线适配器：用于将一个或多个磁盘连接到I/O总线，使用主机总线接口定义的通信协议，磁盘接口包括SCSI和SATA，通常SCSI磁盘比SATA磁盘速度更快更昂贵，且SCSI主机总线适配器可以支持多个磁盘驱动器，而SATA只能支持一个。
网络适配器：可以通过将适配器插入到主板上空的插槽，从而连接到I/O总线。

注意：系统总线和内存总线是与CPU相关的，而PCI总线这样的I/O总线被设计成与底层CPU无关。

CPU会在地址空间中保留一块地址用于与I/O设备通信，每个地址称为I/O端口（I/O Port），而连接到总线的设备会被映射到一个或多个端口，则处理器可通过端口地址来访问该I/O设备，该技术称为内存映射I/O（Memory-mapped I/O）。

假设磁盘控制器映射到端口0xa0，探讨磁盘的读取过程：

CPU会通过对地址0xa0执行三个存储指令，将地址0xa0的内容保存到内存中，完成对磁盘的读取。发送完指令后，由于磁盘读取速度比CPU执行速度慢很多，所以CPU会先去执行其他工作。
- 指令1：发送一个命令字，告诉磁盘发起一个Read
- 指令2：指明应该读取的逻辑块号
- 指令3：指明保存的内存地址
磁盘控制器接收到Read命令后，会通过上述方法直接将磁盘内容传送到主存中。这种设备可以自己执行读写总线事务而无需CPU干涉的过程，称为直接内存访问（Direct Memory Access，DMA）。
磁盘发送完数据后，会给CPU发送一个中断信号，暂停CPU正在做的工作，然后将控制返回到CPU被中断的地方。

固态硬盘

固态硬盘（Solid State Disk，SSD）是一种基于闪存的存储技术，插在I/O总线上标准硬盘插槽（通常为USB或SATA），处于磁盘和DRAM存储器的中间点。从CPU的角度来看，SSD与磁盘完全相同，有相同的接口和包装。

如上图所示是一个SSD的基本结构。它由闪存和闪存翻译层（Flash Translation Layer）组成

闪存翻译层是一个硬件/固件设备，用来将对逻辑块的请求翻译成对底层物理设备的访问。
闪存的基本属性决定了SSD随机读写的性能，通常由B个块的序列组成，每个块由P页组成，页作为数据的单位进行读写。通常页大小为512字节~~4KB，块中包含32~~128页，则块的大小有16KB~512KB。

当对页进行写操作时，首先需要先对该页所处的整个块进行擦除。

以上是Intel SSD 730的性能，IOPS是每秒I/O操作数，吞吐量数量基于4KB块的读写。我们可以发现随机写操作较慢，这是因为：

对页进行写操作时，通常需要花费较长时间来擦除块，比访问页所需的时间慢了一个数量级
当块中包含其他数据时，会先将块中带有有效数据的页复制到被擦出过的块中，才能对那个块进行擦除。在闪存翻译层中实现了复杂的逻辑，试图最小化这些重复的操作。

块的擦除次数是有限的，当块磨损后，就不能再使用了，闪存翻译层中的平均磨损（Wear Leveling）逻辑会试图将擦除平均到所有块中，来最大化每个块的寿命。

SSD的优缺点：

优点：由于闪存是半导体存储器，没有移动的部件，所以速度比磁盘更快且磨损小，能耗低
缺点：SSD每字节比磁盘贵大约30倍，所以常用的存储容量比磁盘小100倍左右。

存储技术趋势

具有以下重要思想：

不同存储技术有不同的价格和性能折中：从性能而言，SRAM>DRAM>SSD>磁盘，而从每字节造价而言，SRAM>DRAM>SSD>磁盘。
不同存储技术的价格和性能属性以不同的速率变化着

从上一图中可看出，DRAM主存和磁盘的性能滞后于CPU性能，访问时间比单个处理器的周期时间更慢，而SRAM的性能虽然也滞后于CPU性能，但是还保持增长，所以现代计算机会使用基于SRAM的高速缓存，来弥补CPU和内存之间的差距。

局部性

具有良好局部性（Locality）的程序，会倾向于引用最近引用过的数据项本身，或者引用最近引用过的数据项周围的数据项。局部性主要具有两种形式：

时间局部性（Temporal Locality）：引用过的数据项在不久后会被多次引用。

空间局部性（Spatial Locality）：引用过的数据项，在不久后会引用附近的数据项。

从硬件到操作系统，再到应用程序，都利用了局部性

硬件：在处理器和主存之间引入一个小而快速的高速缓存存储器，来保存最近引用的指令和数据，从而提高对主存的访问速度。
操作系统：用主存来缓存虚拟空间中最近被引用的数据块。
应用程序：比如Web浏览器会将最近引用的文档放入本地磁盘中，来缓存服务器的数据。

有良好局部性的程序比局部性较差的程序运行更快。

想要分析一个程序的局部性是否好，可以依次分析程序中的每个变量，然后根据所有变量的时间局部性和空间局部性来综合判断程序的局部性。

例1：

分析上述程序的局部性。对于变量sum，每一轮迭代都会引用一次，所以sum具有好的时间局部性，而sum是标量，所以没有空间局部性。对于变量v，其数据在内存中的分布如图b中所示，每一轮迭代都是引用不同的数据项，所以时间局部性较差，但是会按照内存存储的顺序依次引用数据项，所以空间局部性较好。综合来说，该程序具有较好的局部性。

并且由于程序是以指令形式保存在内存中的，而CPU会从内存中读取指令，所以也可以考虑取指的局部性。由于该循环体内的指令是顺序保存在内存中的，而CPU会按顺序进行取指，所以具有良好的空间局部性，并且迭代多次会反复读取相同的指令，所以具有良好的时间局部性，所以该程序的局部性较好。

对于一个向量，如果每一轮引用的数据项之间在内存空间中相隔k，则称该程序具有步长为k的引用模式（Stride-k Reference Pattern）。步长k越大，则每一轮引用的数据在内存中间隔很大，则空间局部性越差。

例2：

对于以上代码，变量sum的时间局部性较好且不具有空间局部性，对于二维数组变量a，在内存中是按照行优先存储的，而代码中也是按照行优顺序进行应用的，所以变量a具有步长为1的引用模式，所以具有较好的空间局部性，而时间局部性较差。总体来说，该程序具有良好的局部性。

例3：

上述代码将变量a的引用顺序变为了列优先，则根据a的内存存储形式，变量a具有步长为N的引用模式，则时间局部性较差，且空间局部性也较差。总体来说，该程序的局部性较差。

例4：

我们需要判断以上三个函数的局部性。首先根据结构体的定义可以得到结构体数组在内存中的存储形式如下所示

则clear1函数的步长为1，具有良好的空间局部性；而clear2函数会在结构体中不同的字段中反复跳跃，空间局部性相对clear1差一些；而clear3函数会在相邻两个结构体中反复跳跃，空间局部性相比clear2更差。

总体而言：

重复引用相同变量的程序具有良好的时间局部性
考虑变量的内存存储形式，判断程序引用模式的步长，步长越大则空间局部性越差
从取指角度而言，具有循环体则空间局部性和时间局部性较好，而且循环体越小、迭代次数越多，则局部性越好。

存储器层次结构

通过上面两节，我们可以得到存储技术和软件的基本属性：

不同存储技术的访问时间相差较大，速度快的技术每字节的成本比速度慢的技术高，且容量小。并且CPU和主存之间的差距在变大。
编写良好的程序具有良好的局部性。

两者存在一定的互补，由此可以得到一种组织存储器系统的方法，存储器层次结构（Memory Hierarchy）。

如上图所示是一种经典的存储器层次结构，会使用基于SRAM的高速缓存存储器来解决CPU和DRAM主存之间的鸿沟，通常还可以在DRAM主存和本地磁盘之间添加一层SSD，来弥补两者之间的差距。通常还可以在本地磁盘下方添加一个本地磁带，提供成本更低的存储。

高速缓存（Cache）是一个小而快速的存储设备，用来作为存储在更大更慢设备中的数据对象的缓冲区域。而使用高速缓存的过程称为缓存（Caching）。

存储器层次结构的中心思想是让层次结构中的每一层来缓存低一层的数据对象，将第k层的更快更小的存储设备作为第k+1层的更大更慢的存储设备的缓存。

该结构之所以有效，是因为程序的局部性原理。相比于第k+1层的数据，程序会倾向于访问存储在第k层的数据。如果我们访问第k+1层存储的数据，我们会将其拷贝到第k层，因为根据局部性原理我们很有可能将再次访问该数据，由此我们就能以第k层的访问速度来访问数据。而且因为我们不经常访问第k+1层的数据，我们就可以使用速度更慢且更便宜的存储设备。

上图展示的是存储器层次结构的基本缓存原理。每一层存储器都会被划分成连续的数据对象组块，称为块（Block），每个块都有一个唯一的地址或名字，并且通常块的大小都是固定的。第k层作为第k+1层的缓存，数据会以块大小作为传送单元（Transfer Unit）在第k层和第k+1层之间来回赋值，使得第k层保存第k+1层块的一个子集的副本。通常存储器层次结构中较低层的设备的访问时间较长，所以较低层中会使用较大的块。

缓存命中

当程序需要第k+1层的某个数据对象d时，会现在第k层的块中搜索d，如果d刚好缓存在第k层中，则成为缓存命中（Cache Hit），则该程序会直接从第k层中读取d。根据存储器层次结构，可以知道第k层的读取速度更快，因此缓存命中会使得程序更快。

缓存不命中

如果第k层没有缓存数据对象d，则称为缓存不命中（Cache Miss），则会从第k+1层中取出包含d的块，然后第k层的缓存会执行某个放置策略（Placement Policy）来决定该块要保存在第k层的什么位置

来自第k+1层的任意块能保存在第k层的任意块中，如果第k层的缓存满了，则会覆盖现存的一个牺牲块（Victim Block），称为替换（Replacing）或驱逐（Evicting）这个牺牲块，会根据替换策略（Replacement Policy）来决定要替换第k层的哪个块
- 随机替换策略：会随机选择一个牺牲块
- 最近最少被使用（LRU）替换策略：选择最后被访问的时间离现在最远的块

随机放置块会使得定位起来代价很高。

可以采用更严格的放置策略，将第k+1层的某个块限制放置在第k层块的一个小的子集中，比如第k+1层的第i个块保存在第k层的i mod 4中。但是该放置策略会引起冲突不命中（Conflict Miss），此时缓冲区足够大，但是由于需要的对象会反复映射到同一个缓存块，使得缓存一直不命中。此时就需要修改放置策略。

比较特殊的情况是第k层的缓存为空，那么对于任意的数据对象的访问都会不命中。空的缓存称为冷缓存（Cold Cache），该不命中称为强制性不命中（Compulsory Miss）或冷不命中（Cold Miss）。

程序通常会按照一系列阶段来运行，每个阶段会访问缓存块的某个相对稳定不变的集合，则该集合称为工作集（Working Set），如果工作集大小超过缓存大小，则缓存会出现容量不命中（Capacity Miss），这是由缓存太小导致的。

缓存管理

对于每层存储器，都会有某种形式的逻辑来管理缓存：将缓存划分成块、在不同层之间传递块、判断缓存是否命中并进行处理。

编译器管理寄存器文件，当寄存器文件中不含有数据时出现不命中，它会决定何时发射加载操作，以及确定用哪个寄存器来存放数据。
SRAM高速缓存是DRAM主存的缓存，由内置在缓存中的硬件逻辑管理的。
在有虚拟内存的系统中，DRAM主存是本地磁盘的缓存，由操作系统软件和CPU上的地址翻译硬件共同管理。
在具有分布式文件系统的机器中，本地磁盘作为缓存，由运行在本地机器上的客户端进程管理。

通过以上内容，就能解释局部性好的程序的优势：

时间局部性：当一个数据对象在第一次不命中被复制到缓存中时，我们希望程序的时间局部性好，则在不久的将来就能反复在第k层访问到该块，使得程序运行更快。
空间局部性：由于缓存中一个块包含多个数据对象，我们希望程序的空间局部性好，就可以直接利用第k层的数据块，避免再从第k+1层传输块到第k层。

第二部分

当高速缓存大小大于数据的大小，如果分配良好，则只会出现冷不命中。

缓存不命中比内存访问次数影响更大

由内存系统的设计来决定块大小，是内存系统的固定参数。首先决定块大小，然后决定期望的缓存大小，然后再决定关联性，最终就能知道组的数目。

块的目的就是利用空间局部性

缓存是硬件自动执行的，没有提供指令集对其进行操作

建议：

将注意力集中在内循环中，因为大部分的计算和内存访问都集中在这里

按照数据对象存储在内存中的顺序，以步长为1来读数据，使得空间局部性最大。比如步长为2的命中率就比步长为1的命中率降低一半。

一旦从存储器读入一个数据对象时，就尽可能使用它，使得时间局部性最大。特别是局部变量，编译器会将其保存在寄存器中。

高速缓存存储器

较早期的计算机系统的存储器层次结构只有三层：CPU寄存器、主存和磁盘，但是随着CPU的发展，使得主存和CPU之间的读取速度逐渐拉大，由此在CPU和主存之间插入一个小而快速的SRAM高速缓存存储器，称为L1高速缓存，随着后续的发展，又增加了L2高速缓存和L3高速缓存。

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

如上图的b中所示，会将m位的地址划分成三部分：

s位：高速缓存被组织成一个数组，而该数组通过$S=2^s$ 进行索引。
b位：每个组中包含E个高速缓存行（Cache Line），每个行有一个$B=2^b$字节的**数据块（Block)**组成。
t位：每一个高速缓存行有一个$t = m - (s+b)$ 位的**标记位（Valid Bit)**，唯一表示存储在这个高速缓存行中的数据块，用于搜索数据块。

该高速缓存的结构可以通过元组(S, E, B, m)来描述，且容量C为所有块的大小之和，$C = S * E * B$ 。

注意：如果将组索引放在最高有效位，则连续的内存块就会映射到相同的高速缓存组中，通过将组索引放在中间，可以使得连续的内存块尽可能分散在各个高速缓存组中，可以充分利用各个高速缓存组

当一条加载指令指示CPU从主存地址A中读取一个字w时，会将该主存地址A发送到高速缓存中，则高速缓存会根据以下步骤判断地址A是否命中：

组选择：根据地址划分，将中间的s位表示为无符号数作为组的索引，可得到该地址对应的组。
行匹配：根据地址划分，可得到t位的标志位，由于组内的任意一行都可以包含任意映射到该组的数据块，所以就要线性搜索组中的每一行，判断是否有和标志位匹配且设置了有效位的行，如果存在，则缓存命中，否则缓冲不命中。
字抽取：如果找到了对应的高速缓存行，则可以将b位表示为无符号数作为块偏移量，得到对应位置的字。

当高速缓存命中时，会很快抽取出字w，并将其返回给CPU。如果缓存不命中，CPU会进行等待，高速缓存会向主存请求包含字w的数据块，当请求的块从主存到达时，高速缓存会将这个块保存到它的一个高速缓存行中，然后从被存储的块中抽取出字w，将其返回给CPU。

注意：为了使得地址中的b位能够编码块偏移量，要求从下一层存储器中，根据块偏移量的值从中截取出块大小的数据块。

该编码方式具有以下特点：

能够通过组索引位来唯一确定高速缓存组
映射到同一个高速缓存组的块由标志位唯一地标识
标记位和组索引位能够唯一的表示内存中的每个块
有可能会存在多个块映射到同一个高速缓存组中（只要地址的组索引相同）

可以根据每个组的高速缓存行数E，将高速缓存分成不同的类型

直接映射高速缓存

如上图所示，当$E=1$时，高速缓存称为直接映射高速缓存（Direct-mapped Cache），每个高速缓存组中只含有一个高速缓存行。

当缓存不命中时需要进行缓存行替换，会先从下一层的存储器中请求得到包含目标的块，然后根据地址计算出高速缓存组的索引，然后由于一个组中只含有一个高速缓存行，所以会直接将该块替换当前的块。

这里需要注意的一点是：当程序访问大小为2的幂的数组时，直接映射高速缓存中通常会发生冲突不命中。

如以上代码，该函数具有良好的空间局部性，所以我们期望它的缓存命中率会高一点。

我们首先假设数组x排在数组y之前，且x的地址从0开始。然后直接映射高速缓存的$b = 4$ 和$s = 1$ ，即有两个高速缓存组，每个高速缓存组有一个高速缓存行，每个高速缓存行能保存16字节数据块，即4个浮点数，则高速缓存容量为32字节，我们可以得到高速缓存对地址的划分如下所示（64位系统中)

然后我们可以根据这两个数组的地址得到它们在高速缓存中的组索引（因为只有一个高速缓存行，所以不考虑标志位）

我们可以发现，循环第一次迭代引用x[0]时，缓存不命中会使得包含x[0]~~x[3]的数据块保存到高速缓存组0处，但是当引用y[0]时，会发现高速缓存组0处保存的数据不匹配，又出现了缓存不命中，就会使得包含y[0]~~y[3]的数据块保存到高速缓存0处，依次类推。可以发现始终会发生缓存不命中，使得性能下降。这种情况称为抖动（Thrash），即高速缓存反复地加载和驱逐相同的高速缓存块的组。

可以发现：即使程序的局部性良好，且工作集的大小没有超过高速缓存容量，但是由于这些数据块都被映射到了相同的高速缓存组中，且直接映射高速缓存每个组中只有一个高速缓存行，所以会出现抖动，不断出现缓存不命中。

我们这里想要相同所以的x和y可以保存到不同的高速缓存组中，就能避免抖动现象，这里可以在数组x后填充B个字节，使得数组y的地址向后偏移，得到如下形式

组相联高速缓存

直接映射高速缓存的冲突不命中是由于每个高速缓存组中只有一个高速缓存行，所以扩大E的值，当$1 < E < C/B$ 时，称为**E路组相联高速缓存（Set Associative Cache）**，此时需要额外的硬件逻辑来进行行匹配，所以更加昂贵。（ $E < C/B$ 即要求$S > 1$ )

下图所示的就是二路组相连：

当缓存不命中时需要进行缓存行替换，如果对应的高速缓存组中有空的高速缓存行，则直接将其保存到空行中。但是如果没有空行，就要考虑合适的替换策略：

最简单的替换策略是随机选择要替换的行
最不常使用（Least-Frequently-Used，LFU）策略：替换过去某个时间窗口内引用次数最少的一行。
最近最少使用（Least-Recently-Used，LRU）策略：替换最后一次访问时间最久远的那一行

全相联高速缓存

全相联高速缓存（Full Associative Cache）是用一个包含所有高速缓存行的组组成的，其中$E = C/B$ ，即 $S = 1$ 。

由于全相联高速缓存只有一个组，所以不包含组索引编码

其行匹配和字选择与组相联高速缓存相同，只是规模大小不同。想要得到高速的全相联高速缓存十分困难，所以通常适合用于较小的高速缓存，比如虚拟内存中的翻译备用缓冲器（TLB）。

写操作

当CPU想要对地址A进行写操作时，会通过地址A判断是否缓存了该地址，如果缓存了称为写命中（Write Hit），否则称为写不命中（Write Miss）。

写命中：高速缓存会先更新缓存的副本，然后可以采取不同方法更新下一层的副本
- 直写（Write-Though）：立即更新下一层的副本值。缺点是每次写都会引起总线流量。
- 写回（Write-Back）：为每个高速缓存行维护一个修改位（Dirty Bit），表明这个高速缓存块是否被修改。当被修改的高速缓存块被驱逐时，会查看修改位，判断该块是否被修改，只有被修改才会更新下一层的副本值。能够显著减少总线流量，但是复杂性高。
写不命中：
- 写不分配（Not-Write-Allocate）：直接将字写到下一层中。
- 写分配（Write-Allocate）：加载相应的下一层的块到当前层的高速缓存中，然后更新当前高速缓存块。得益于空间局部性，进行一次写分配后，下一次有较高几率会写命中，但是缺点是每次写不命中就要将块从第一层向上传输。

直写高速缓存通常为写不分配的，写回高速缓存通常为写分配的。

建议采用写回写分配模型，因为随着逻辑电路密度的提高，写回的复杂性不再成为阻碍，并且和处理读相同，都利用了局部性原理，效率较高。

真实高速缓存结构

之前介绍的高速缓存值保存程序数据，但是高速缓存同样也能保存指令。可以将高速缓存分成以下几种：

i-cache：只保存指令的高速缓存
d-cache：只保存程序数据的高速缓存
Unified Cache：即能保存指令，也能保存程序数据的高速缓存

如上图所示是Intel Core i7的高速缓存层次结构，可以发现在L1高速缓存中分成了L1 d-cache和L1 i-cache，这样做的好处在于：

将数据和指令分别保存在两个高速缓存中，使得处理器可以同时读一个指令字和一个数据字
i-cache通常是只读的，所以会比较简单
可以针对不同的访问模式优化这两个高速缓存，使用不同的块大小、相联度和容量
确保数据访问和指令访问之间不形成冲突不命中

代价就是会导致高速缓存容量变小，提高出现容量不命中的可能性。

参数对性能的影响

衡量高速缓存的指标有：

命中率（Hit Rate）：内存引用命中的比率，命中数量/引用数量。
不命中率（Miss Rate）：内存引用不命中的比率，不命中数量/引用数量。通常，L1高速缓存为3~10%，L2高速缓存为<1%。
命中时间（Hit Time）： 从高速缓存传输一个字到CPU的时间，包括组选择、行匹配和字选择时间。通常，L1高速缓存需要4个时钟周期，L2高速缓存需要10个时钟周期。
不命中处罚（Miss Penalty）：当缓存不命中时，要从下一层的存储结构中传输对应块到当前层中，需要额外的时间（不包含命中时间）。通常，主存需要50~200个时钟周期。

注意：命中和不命中两者对性能影响很大，比如99%命中率的性能会比97%命中率高两倍。

接下来讨论高速缓存中不同参数对高速缓存性能的影响：

想要编写高速缓存友好（Cache Friendly）的代码，基本方法为：

让最常见的情况运行得快，将注意力集中在核心函数的循环中
尽可能减少每个循环内部的缓存不命中，可以对局部变量反复引用，因为编译器会将其保存到寄存器中，其他的变量最好使用步长为1的引用模式。

可以看书中的练习题6.17探讨缓存命中和不命中的情况。

存储器山

一个程序从存储器系统中读取数据的速率称为读吞吐量（Read Throughput）或读带宽（Read Bandwidth），单位为MB/s。我们通过以下代码来衡量空间局部性和时间局部性对程序吞吐量的影响

第37行我们首先对高速缓存进行暖身，然后在第38行计算程序运行的时钟周期个数。

时间局部性：通过size来控制我们工作集的大小，由此来控制工作集存放的高速缓存的级别。假设工作集很小，则工作集会全部存放在L1高速缓存中，模拟了时间局部性优异的程序反复读取之前访问过的数据，则都是从L1高速缓存读取数据的。假设工作集很大，则工作集会存放到L3高速缓存中，模拟了时间局部性很差的程序，不断读取新的数据，则会出现缓存不命中，而不断从L3高速缓存中取数据的过程。所以通过控制工作集大小，来模拟程序局部性。
空间局部性：通过stride来控制读取的步长，来控制程序的空间局部性。

通过调整size和stride来度量程序的吞吐量，可以得到以下存储器山（Memory Mountain）