Hypergraph-based irregular application locality optimization

Multiple 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.4%. 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