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

发布时间：2017-04-13 07:35

  本文关键词：针对循环的内存访问模式分析与应用，由笔耕文化传播整理发布。

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

• 摘要5-6
• Abstract6-8
• 目录8-11
• 图目录11-13
• 表目录13-14
• 第1章 绪论14-22
• 1.1 研究背景14-15
• 1.2 相关工作与研究现状15-19
• 1.2.1 提高缓存性能：基于硬件的方法15-16
• 1.2.2 提高缓存性能：基于软件的方法16-18
• 1.2.3 函数指针分析技术18-19
• 1.3 研究内容19-20
• 1.4 论文组织20-22
• 第2章 LLVM编译器系统22-32
• 2.1 LLVM总体结构和工具链22-26
• 2.2 LLVM中间代码26-27
• 2.3 LLVM虚拟指令集27-29
• 2.4 LLVM类型系统29-30
• 2.5 本章小结30-32
• 第3章 APCACHE设计和实现32-50
• 3.1 APCache总体架构32-33
• 3.2 循环访问模式分析33-41
• 3.2.1 总体框架33-34
• 3.2.2 一个简单例子34-36
• 3.2.3 具体实现36-41
• 3.3 矩阵变换框架41-45
• 3.3.1 数据布局优化基础42
• 3.3.2 数据布局优化理论42-43
• 3.3.3 计算转换矩阵43-45
• 3.4 LLVM中间代码更新框架45-48
• 3.4.1 总体框架45-46
• 3.4.2 数组和索引生成46-47
• 3.4.3 数组访问生成47-48
• 3.4.4 中间代码def-use更新48
• 3.5 本章小结48-50
• 第4章 跨文件的函数调用图构造50-58
• 4.1 FP算法特点50-51
• 4.2 一个简单例子51-52
• 4.3 FP算法实现52-56
• 4.3.1 全局变量分析52-53
• 4.3.2 SCC流敏感过程内分析53-55
• 4.3.3 上下文敏感过程间分析55-56
• 4.4 跨文件的函数调用图的构造56-57
• 4.5 本章小结57-58
• 第5章 实验结果与分析58-74
• 5.1 测试程序集的选用58-60
• 5.1.1 APCache的测试程序58-59
• 5.1.2 FP的测试程序59-60
• 5.2 实验方法60-61
• 5.2.1 APCache的实验方法60-61
• 5.2.2 FP的实验方法61
• 5.3 效果测试61-71
• 5.3.1 APcache原型系统测试61-69
• 5.3.2 FP算法性能和分析精度测试69-71
• 5.4 实验结论71-74
• 5.4.1 对于APCache原型系统71-72
• 5.4.2 对于函数指针分析算法FP72-74
• 第6章 结束语74-76
• 参考文献76-82
• 致谢82-84
• 在读期间发表的学术论文与取得的研究成果84

【参考文献】

中国期刊全文数据库 前1条

1 于洪涛;张兆庆;;激进域敏感基于合并的指针分析[J];计算机学报;2009年09期

  本文关键词：针对循环的内存访问模式分析与应用，，由笔耕文化传播整理发布。

本文编号：303117