基于超图的非规则应用局部性优化

曹倩¹，刘立红²，颉斌³，陈洪菊¹

1. 北京工商大学计算机与信息工程学院2. 军械工程学院基础部3. 北京科技大学计算机与通信工程学院

摘 要：针对非规则循环应用中存在的一次迭代访问多个间接数组的问题,给出了超图数组的形式化描述,提出了三种基于超图的数据重排算法,即基于超图的非重复编码数据重排算法、基于超图的回溯搜索数据重排算法和基于超图的先划分再回溯数据重排算法,以及两种基于超图的迭代重排算法,即基于超图的非重复编码迭代重排算法和基于超图的回溯搜索迭代重排算法.通过对典型的非规则应用实例——流体力学问题进行实验,表明单独的重排算法提高程序执行速度约25.4%.在最好的数据重排与迭代重排的组合算法下,一级和二级高速缓存的平均命中率分别增加到91.7%和96.5%.

关键词：数据局部性;高速缓冲存储器;重排;非规则;编译;