「计算机组成原理」：现代存储器的结构( 五 ) 按照在计算机中作用的不同

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

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

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

有良好局部性的程序比局部性较差的程序运行更快。
想要分析一个程序的局部性是否好，可以依次分析程序中的每个变量，然后根据所有变量的时间局部性和空间局部性来总和判断程序的局部性。
例1：

文章插图
分析上述程序的局部性。对于变量sum ，每一轮迭代都会引用一次，所以sum具有好的时间局部性，而sum是标量，所以没有空间局部性。对于变量v ，其数据在内存中的分布如图b中所示，每一轮迭代都是引用不同的数据项，所以时间局部性较差，但是会按照内存存储的顺序依次引用数据项，所以空间局部性较好。综合来说，该程序具有较好的局部性。
并且由于程序是以指令形式保存在内存中的，而CPU会从内存中读取指令，所以也可以考虑取指的局部性。由于该循环体内的指令是顺序保存在内存中的，而CPU会按顺序进行取指，所以具有良好的空间局部性，并且迭代多次会反复读取相同的指令，所以具有良好的时间局部性，所以该程序的局部性较好。
对于一个向量，如果每一轮引用的数据项之间在内存空间中相隔k ，则称该程序具有步长为k的引用模式（Stride-k Reference Pattern）。步长k越大，则每一轮引用的数据在内存中间隔很大，则空间局部性越差。
例2：

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

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

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

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

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

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

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

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

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