中文摘要：

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

英文摘要：

Muhiple indirection arrays often exist in one iteration, which is involved in irregular loop applications. A formal description of the hypergraph arrays was presented to solve this problem. Besides, three hypergraph-based data reordering algorithms （hypergraph-based non-repetitive coding data reordering algorithm, hypergraph-based backtracking search data reordering algorithm, and hypergraph-based partition first and then backtracking data reordering algorithm ） and two hypergraph-based iteration reordering algorithms （hypergraph-based non-repetitive coding iteration reordering algorithm and hypergraph-based backtracking search iteration reordering algorithm） were put forward. Experiments were performed on computational fluid dynamics, which was a representative irregular application. It is indicated that data locality is improved by the single reordering algorithm, with the execution speed increasing by 25. d%. The combination of the data reordering algorithm and the iteration reordering algorithm demonstrates the best performance, with the average hit rates of level-1 and level-2 cache reaching 91.7% and 96. 5% , respectively.