|「计算机组成原理」：现代存储器的结构( 六 )

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