程序局部性的量化分析

刘 扬，安 虹，邓博斌，毛梦捷，刘 玉

(中国科学技术大学计算机科学与技术学院，合肥 230027)

1 概述

在现代计算机系统结构中，存储墙问题是限制计算机性能的一个主要因素，成为计算机领域研究的重要问题之一[1]。存储系统的层次化结构设计，是解决这一问题的经典方法，即引入缓存(cache)。在过去的几十年里，关于cache的研究和优化一直在进行，从单一 cache到指令和数据分离的 cache，从简单的堆栈结构到多种替换策略，从只能处理一个请求的cache到并发处理多个请求的cache[2]，从被动访问到主动预取，甚至在分离式结构[3]设计中，发展成访存处理器(access processor)与执行处理器(execute processor)并行。然而，这些都离不开局部性这个前提。理解程序的局部性原理，即有助于应用软件程序员优化程序代码[4]，有利于系统程序员写出更有效率工具[5]，又能给系统结构设计师带来灵感，设计出更高性能的硬件[6]。因此，本文分析基准测试程序SPEC2000，量化其局部性，便于比较程序间局部性的高低。通过对局部性的分类分析讨论，理解程序局部性。

2 相关研究

很多学者研究程序的访存模式分析程序访存行为。文献[7]提出通过多叉树结构记录访存的地址，作为回溯查找窗口。虽然准确性很高，但这种方法的空间/时间复杂度比较大。本文用cache作为回溯查找窗口。也有学者用取样统计的方法测量分析程序的空间局部性[8]。取样的方法准确性相对较低，本文采用全程序分析，统计计算每次访存地址。还有学者分析HPC的 benchmark，用cache line数目为 N的cache统计重用距离不大于N的访存数目[9]。该方法的缺点是做多次实验才能组合得到完整的重用距离分布数据。用cache的命中率来分析技术时间空间局部性也是一种方法[10]。这种方法计算出来的时间局部性和空间局部性必然有交叉，而且与运行平台有关，并不完全是程序所固有的特性。上述研究分析程序的全局数据局部性，本文进一步划分分别测量分析程序的代码段、数据段和堆、栈的局部性。

3 局部性测量方法

本文希望用简单、易于实现且与平台无关的方法，测量程序的局部性。从局部性的定义入手，根据前人的经验，做出适当的折衷。实验中跟踪每条指令的执行，记录访存指令，并对访存地址进行统计。对量化统计的结果进行化简，化简成0～1之间的数，以方便比较2个程序的局部性。程序的逻辑分段被映射到硬件的4个段：静态数据到数据段，用户管理的数据到堆段，系统管理的数据到栈段，指令到代码段。进一步，分别测量各段的时间、空间局部性。

3.1 时间局部性测量

时间局部性是指某数据被访问，那么很快被再次访问。通过分析重用距离，能量化出同一数据究竟有多快被再次访问。本文中定义对同一数据2次访问期间的访存数目为重用距离。为了测量重用距离，用访问计数器记录数据上次被访问时间(每次访存时间递增一次)，当数据再次被访问时，当前时间减去计数器记录的时间，就得到了重用距离。为每个数据配置一个计数器代价太高，因此，把cache配置成cache line大小为一个数据项的cache，并在cache line里增加一个数据项，作为访问计数器。值得注意的是，这样的测量精度有所下降，但只要把cache性能配置高些，即命中率 90%以上，则本文方法的准确率也在 90%以上。

根据重用距离的值，按照(0,32], (32,64],…,(16×2N−1,16×2N]区间，分别统计每个区间内的访存总数。最后根据式(1)计算时间局部性的得分，分值的值域为[0,1]，分值越高代表时间局部性越好。

其中，N为区间数目。

3.2 空间局部性测量

空间局部性是指某数据被访问，那么地址相近的数据很快被访问。类似地，用步长来量化被访问数据之间的相对地址距离。对同一个地址的2次访问，即具有重用距离为1的时间局部性，也具有步长为0的空间局部性，因此步长的下限为0。为了测量步长，设长度为 N的查找窗口，用来记录之前 N个被访问的数据。当访问一个数据时，遍历查找窗口，相对步长最短的值为当前数据空间局部性的步长。这里N的值即要设的足够大，保证捕捉到大部分空间局部性，又要设的足够小，保证程序的性能。这里设N的值为32。类似地，根据步长的值，按照区间分别统计各个区间的访存数目。同样利用式(1)计算出空间局部性的量化得分，分值的值域为[0,1]，分值越高代表空间局部性越好。

4 实验环境

本文涉及到的实验方法基于 CPU模拟器SimpleScalar和基准测试程序SPEC2000。在原有模拟器代码上，实现了上述测量局部性的算法。该模拟器是的指令是64位，根据上节讨论，cache line大小为8 Byte。一级指令Cache大小配置为1 MB，16路组相连，LRU替换算法。一级数据Cache大小4 MB，32路组相连，LRU替换算法。

到目前为止，SPEC2000是最为广泛研究的处理器基准测试程序，它代表了绝大多数应用程序的典型程序行为。编译程序(176.gcc)、压缩程序(164.gzip和256.bzip2)、系统管理程序(253.perlbmk)有多种输入集。面向科学研究和工程计算的程序(175.vpr、181.mcf和 255.vortex)与现实世界的应用程序有很大的相似性。纯粹面向科学计算的浮点型程序(177.mesa、179.art和188.ammp)，因其输入集和程序本身复杂度的不同，很好地体现了现实世界的科学计算应用。尽管SPEC2000为计算专门设计的而非访存，这恰恰是选择它来测量访存局部性的原因——它的代表性强；为访存专门设计的程序，如 Random Access，过分夸大了存储器的重要性，与现实世界的程序行为相差太大，不具有广泛的代表性。所使用的程序说明如表1所示。

表1 基准测试程序

由于本文的目的是分析程序的局部性，程序的局部性是程序固有的性质，与所运行的环境无关，因此模拟器中并没如入任何优化选项，没有预取没有分支预测，也没有乱序执行多线程多核等优化技术。

5 测试结果及分析

同一个程序的各个分段的局部性不尽相同，如图1所示。图中d-cache的柱状图代表程序的数据局部性，包括数据段和堆栈段。text代表程序的代码段，也是程序的数据的指令并行性。data、heap和 stack分别代表程序的数据段、栈和堆段。程序中栈的局部性最好，空间局部性和时间局部性得分最高。这与栈的结构设计有关。栈只有入栈和出栈2个操作，访问上要么是相对栈顶增加要么是相对地址减少，因此空间局部性大于0.99。局部性最低的是堆段。堆段的地址空间很大，访问次数最少，空间局部性最低。对这种情况，采用软件预取测量是有效的优化措施，因为软件预取准确性高，且代码膨胀不会很大。由于跳转分支等程序行为，代码段的空间局部性不是很好，循环使得代码的时间局部性很好。针对这个特点，分支预测技术和指令预取技术能有效提高代码的空间局部性。

图1 gzip程序各段的局部性

根据程序的访存指令所占的比例不同，可将程序分为计算受限型和访存受限型。在图2中，绝大多数的访存比例为30%，为计算受限型程序。也有相当数目的程序访存比例超过40%，vortex的访存比例高达 53%。对于这种访存受限高通量型的程序，除了增加带宽保证数据供应外，还有必要采取增加局部性的技术，否则，由于空间局部性较差(vortex的时间局部性仅有 0.4，见图 3)，因此程序的性能不高。

图2 访存比例分布

图3 各程序的二维局部性分布

图3为各个程序的二维局部性，其中，横坐标为空间局部性，纵坐标为时间局部性。在程序中，bzip、gzip、parser和mesa的空间局部性很高，而art、ammp的时间局部性好，vpr的时间局部性差。

图4和图5分别是art和vpr的重用距离分布图。图中横坐标是重用距离，纵坐标代表该访存个数统计，由于数字值之间相差太大，图中为实际值的对数。

图4 art的重用距离分布

图5 vpr的重用距离分布

在图4中，数据局部性与heap段的局部性相似，这是由于heap段的访存量占总数据访问量的92%。由于重用距离小的访存量非常高，重用距离不大于256的访存数量占总访存量的 93%，很容易被 cache捕获，因此实际局部性非常高。相比较而言，图5中重用距离不大于256的访存比仅为72%，时间局部性差。实验中对 cache配置较高，缺失率 1%以下，因此重用距离测量的偏差在1%以内。

6 结束语

本文介绍了如何设计并实现对程序局部性的测量和量化分析。实验测量并量化了时间局部性和空间局部性。通过数据分析表明，大多数程序都具有良好的时间局部性或空间局部性，因此，cache结构对程序性能的提升明显。对于程序本身，堆段的访问比例最高，其局部性决定程序的数据局部性；堆段的地址空间最大，时间局部性和空间局部性最低，程序员通过编程或编译优化，可以提高局部性。对系统而言，可以通过优化cache结构、预取、分支预测等技术手段提高cache对局部性的利用能力。

然而，对于访存密集型的程序，仅使用上面的技术是不够的；由于存储墙的存在，增加访存带宽、提高存储部件的并行能力也许是行之有效的方法。但是，对程序局部性与具体平台上的执行效率之间的关系，以及各种优化机制对局部性的效果，还没有量化的结论。因此，下一步工作将探讨各种访存优化技术，对各种局部性的程序有怎样的可量化的性能提升效果。

[1]McKee S A.Reflections on the Memory Wall[C]//Proc.of the 1st Conference on Computing Frontiers.Ischia, Italy:ACM Press, 2004.

[2]Tuck J, Ceze L, Torrellas J.Scalable Cache Miss Handling for High Memory-level Parallelism[C]//Proc.of the 39th Annual IEEE/ACM International Symposium on Microarchitecture.Washington D.C., USA: IEEE Computer Society, 2006.

[3]Crago N C, Patel S J, OUTRIDER: Efficient Memory Latency Tolerance with Decoupled Strands[C]//Proc.of the 38th Annual International Symposium on Computer Architecture.San Jose, USA: ACM Press, 2011.

[4]王 芳, 高玲刑 郑明春.基于局部性的分布式哈希表资源定位技术[J].计算机应用, 2006, 26(3): 531-546.

[5]夏 军.数据局部性及其编译优化技术研究[D].长沙:国防科学技术大学, 2004.

[6]Sung M, Krashinsky R, Asanovi K.Multithreading Decoupled Architectures for Complexity-effective General Purpose Computing[J].ACM SIGARCH Computer Architecture News, 2001, 29(5): 56-61.

[7]Zhong Yutao, Shen Xipeng, Ding Chen.Program Locality Analysis Using Reuse Distance[J].ACM Transactions on Programming Languages and Systems, 2009, 31(6): 1-39.

[8]Gu Xiaoming, Christopher I, Bai T, et al.A Component Model of Spatial Locality[C]//Proc.of International Symposium on Memory Management.Dublin, Ireland:ACM Press, 2009.

[9]Weinberg J, McCracken M O, Strohmaier E, et al.Quantifying Locality in the Memory Access Patterns of HPC Applications[C]//Proc.of ACM/IEEE Conference on Supercomputing.Washington D.C., USA: IEEE Computer Society, 2005.

[10]Murphy R C, Kogge P M.On the Memory Access Patterns of Supercomputer Applications: Benchmark Selection and Its Implications[J].IEEE Transactions on Computers, 2007,56(7): 937-945.