基于超图的非规则应用局部性优化 (2012年)

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