论文部分内容阅读
在过去的几十年间,处理器主频与内存访问速度间的差距的日益增大,使得许多程序的性能瓶颈集中在内存访问,体系结构中引入了多级高速缓存的结构(cache)来解决内存访问的瓶颈(memory wall),希望多数的访问可以在高速的cache中完成,避免每次直接在较慢的内存中进行存取.程序中内存访问是否有良好的局部性是能否充分发挥cache作用的关键,局部性优化是通过程序变换来提高内存访问的局部性,一直以来围绕着局部性优化展开了许多研究,数据重组是其中很重要的一类,它通过改变数据在内存中的存放位置以及排列方式(数据布局),使得经常先后被访问的数据在内存中尽量靠近,从而改善访问的空间局部性.
现有的研究中针对各种数据布局方式已经提出了许多的数据重组技术,一些简单的数据重组技术已经得认同并被广泛应用,但大部分还停留在研究阶段,数据重组的合法性判断以及优化方案选择是这些数据重组技术实用化的主要障碍.本文的主要贡献是提出了一个结合运行时合法性检查的动态数据重组实用框架,并围绕动态数据重组的优化方案选择以及合法性判断这两个问题展开讨论.
动态数据重组方法的范围是单个计算阶段,避免了静态数据重组方法在全局范围内进行优化方案选择的复杂性.数据重组合法性的判断涉及到数据之间的别名关系,编译器别名分析的保守会导致数据重组的合法性无法静态分析得到,这也是数据重组技术无法被应用到实际系统中的主要障碍,在本文提出的框架中,结合了静态的别名分析和运行时的别名检查来解决合法性判断的难题.此外,对于动态数据重组的运行时开销,本文提出若干优化方法予以克服.实验表明该方法在实际应用中可以取得良好的效果.