针对循环的内存访问模式分析与应用

摘要

随着硬件工艺技术的进步，处理器芯片集成了越来越多的晶体管，处理器速度的飞速提高导致其与内存的速度鸿沟不断拉大。现代主流的体系结构都采用分层缓存架构来缓和处理器和内存访问速度差距带来的影响。有效地利用缓存成为系统性能的关键因素之一。除了硬件上的设计考虑，常用的软件方法是借助编译器强大的分析和优化能力，在中间代码层次对软件程序进行变换，使程序的指令局部性和数据局部性尽可能高，从而降低缓存的失效次数，提高缓存性能。基于编译器来优化程序局部性常分为软件预取、代码变换和数据变换三种。
　　本文基于以上研究思路，致力于在LLVM(Low Level Virtual Machine)编译器系统上开发一个缓存优化原型系统，从而能够结合LLVM强大的分析和优化能力实现对缓存性能地提升。为此，本文基于LLVM中间代码进行了下面的一些工作:
　　1、设计实现一个使用数据变换技术来进行缓存优化的原型系统APCache，涉及代码分析到代码优化的完整过程。系统以LLVM遍的方式对中间代码中的循环进行内存访问模式分析，根据分析结果优化并生成新的访问模式，再更新中间代码。
　　2、以对循环中的数组进行布局优化为重点研究，探讨在LLVM中实现经典算法所需要的技术。循环加数组的使用方式常用在访存密集型程序中，本文采用Leung提出的经典算法来对循环中数组进行重布局优化，提高数据的空间局部性。
　　3、提出一种轻量级的函数指针分析算法FP，为跨过程的缓存优化提供精确的函数调用图支持。算法使用强连通分量(SCC)流敏感和上下文敏感技术确保分析精度，通过缩小分析对象的范围提高分析速度。基于FP的分析结果构造的跨文件函数调用图为跨过程的缓存优化提供了部分技术支持。

目录

声明

摘要

图目录

表目录

第1章 绪论

1．1 研究背景

1．2 相关工作与研究现状

1．2．1 提高缓存性能：基于硬件的方法

1．2．2 提高缓存性能：基于软件的方法

1．2．3 函数指针分析技术

1．3 研究内容

1．4 论文组织

第2章 LLVM编译器系统

2．1 LLVM总体结构和工具链

2．2 LLVM中间代码

2．3 LLVM虚拟指令集

2．4 LLVM类型系统

2．5 本章小结

第3章 APCache设计和实现

3．1 APCache总体架构

3．2 循环访问模式分析

3．2．1 总体框架

3．2．2 一个简单例子

3．2．3 具体实现

3．3 矩阵变换框架

3．3．1 数据布局优化基础

3．3．2 数据布局优化理论

3．3．3 计算转换矩阵

3．4 LLVM中间代码更新框架

3．4．1 总体框架

3．4．2 数组和索引生成

3．4．3 数组访问生成

3．4．4 中间代码def-use更新

3．5 本章小结

第4章 跨文件的函数调用图构造

4．1 FP算法特点

4．2 一个简单例子

4．3 FP算法实现

4．3．1 全局变量分析

4．3．2 SCC流敏感过程内分析

4．3．3 上下文敏感过程间分析

4．4 跨文件的函数调用图的构造

4．5 本章小结

第5章 实验结果与分析

5．1 测试程序集的选用

5．1．1 APCache的测试程序

5．1．2 FP的测试程序

5．2 实验方法

5．2．1 APCache的实验方法

5．2．2 FP的实验方法

5．3 效果测试

5．3．1 APcache原型系统测试

5．3．2 FP算法性能和分析精度测试

5．4 实验结论

5．4．1 对于APCache原型系统

5．4．2 对于函数指针分析算法FP

第6章 结束语

参考文献

致谢

在读期间发表的学术论文与取得的研究成果