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

• 全文链接
• 请求原文

作   者：

曹倩;  刘立红;  颉斌;  陈洪菊; 

作者机构：

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

关键词：

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

期刊名称：

北京科技大学学报

基金项目：

低功耗低复杂度视频编码理论与关键算法研究

i s s n：

1001-053X

年卷期：

2012 年 12 期

页   码：

1469-1477

摘   要：

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