利用程序分析和优化提高Cache性能

发布时间：2020-08-01 22:08

【摘要】： 在近40年来，处理器运行速度的增长和存储器访问速度的增长之间存在着巨大的差距，这使得两者之间的速度差距越来越大，导致的“Memory Wall”问题变得越来越严重，已经成为整个系统性能最主要的瓶颈之一。现代计算机体系结构中广泛采用Cache来缓解这两者之间的速度差距，使得Cache已经成为影响处理器性能、能耗、价值的重要因素之一。Cache的充分利用很大程度上取决于程序自身的局部性，特别是访问数据的局部性，包括时间局部性和空间局部性。优化程序的数据局部性成为提高Cache性能的重要方法之一。 由于无需硬件的支持，具有良好的跨平台性．利用程序分析和优化来改善程序的局部性，提高Cache性能成为当前研究的热点。过去在这方面的工作有两个重要的思路：一是针对程序运行时的访问数据，利用相关的Cache行为模型，建立一些程序分析工具，从源代码级给出程序Cache性能的瓶颈，指导程序员通过程序变换来优化程序的局部性，从而提高Cache性能；二是在编译器上开发编译优化过程，或者开发专门的程序优化工具，通过对程序进行分析，在此基础上自动进行程序变换，包括代码变换和数据变换两种，优化程序的局部性，从而提高Cache性能。 本文根据上面的思路进行了下面的一些工作： (1)程序Cache行为模型的研究 虽然复用距离已经成为程序Cache行为的一种重要度量标准，但是高复杂度和可能存在的内存溢出问题使得其难以被应用。在通过引入最大Cache大小，限制复用距离分析范围的基础上，本文提出了一种受限的复用距离模型。受限的复用距离舍弃少量访问的复用距离分析精度，有效地避免了进行复用距离分析时可能导致的内存溢出问题，同时使得复用距离的分析达到访问数据次数的线性时间复杂度。文章还通过实验说明了基于受限的复用距离进行Cache失效率分析的可行性和正确性。 (2)程序Cache行为分析工具的设计与实现 程序Cache行为的分析和理解能够帮助程序员寻找程序中Cache性能的瓶颈，指导程序员通过程序变换改善程序局部性，提高程序Cache性能。本文介绍一种基于复用距离的程序Cache行为分析工具的设计与实现，该工具利用一种基于中间信息栈的源代码级插桩收集程序的访存信息，然后基于受限的复用距离模型分析程序的Cache行为。同时还通过示例表明该分析工具不但能在源代码中给出Cache性能瓶颈的位置，指导进行代码变换；而且还能分析变量的Cache行为关系，指导进行数据变换。 (3)基于复用距离分布的数据布局优化 在利用程序Cache行为分析工具进行分析时，总结出程序中经常在一起访问的变量的复用距离在分布上具有一定的相似性。如果将这些变量进行重组，改变其布局，则能提高Cache性能。根据这个原理，本文设计并实现了一个数据布局优化框架，在框架中采用了一种基于复用距离分布的变量关系模型，用于寻找程序中经常在一起访问的变量。目前在框架中实现了一种动态数组的重组方法，用来重组利用变量关系模型发现的动态数组，以此来提高程序的数据局部性。针对SPEC CPU2000中部分测试程序的实验表明了该优化框架在优化数据局部性和提高数据Cache性能上具有一定的可行性和有效性。 (4)利用结构拆分提高Cache性能 结构拆分作为一种常用的通过数据变换提高Cache性能的方法，由于只需要分析结构属性域之间的相对关系，具有一定的特殊性。为了克服复用距离分析的复杂性，本文在引入一种较复用距离更为简单的距离的基础上，提出了一种属性域关系模型来度量结构中属性域之间的关系，然后寻找程序中的结构的优化布局，通过结构拆分来优化数据布局，从而提高数据Cache性能。相关的实验表明了这种基于属性域关系模型的结构拆分在提高Cache性能上有一定的有效性。
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2007
【分类号】：TP332.3
【图文】：

图2-2:受限的复用距离分析示例问一个数据元素时，从栈顶开始检索该数据元素在栈中的位置.如果在栈中检索到该数据元素，则其复用距离为栈顶到当前元素的距离，然后将该元素从当前位置移走，并且在栈顶压入该元素;否则其复用距离为co，然后将该元素压入栈顶。图2-l(c)给出了利用基于栈的方法计算访问序号为12的数据元素e的复用距离的示例:搜索栈时，在栈中发现该元素到栈顶的距离为4(此时栈中到栈顶含有h，f，a，g四个数据元素)，则记数据元素e的复用距离为4。得到相应的复用距离后，需要重新调整栈的结构(按图中虚线所示的方法)，原有的数据元素e将被从栈中删除，并且新的数据元素e被压入到此时的栈顶，这样此次复用距离计算完毕.后面数据元素的复用距离的计算同样依据这样的过程。在利用基于栈的方法计算复用距离的同时，出现了一些基于和栈比较接近的数据结构的复用距离分析方法，如队列’159}、向量!6，10]等，这些

复用距离分布图

图冬5:基于复用距离的C创上e失效率分布图31

【引证文献】

相关硕士学位论文 前4条

1 王炜;基于ASIP的实时GPS软件接收机的实现[D];哈尔滨工业大学;2010年

2 张梦龙;盘阵列中基于分组的缓存优化技术研究与实现[D];华中科技大学;2011年

3 杨明;基于存储访问的SIMD优化技术研究[D];解放军信息工程大学;2011年

4 张颖;在达芬奇DSP上对AVS视频编码器的结构优化[D];华中科技大学;2008年

本文编号：2778076