An Optimization and Auto-Tuning Method for Scale-Free Graph Algorithms on SIMD Architectures

摘要

The advent of heterogeneous HPC systems, such as the Intel Xeon Phi with many integrated cores and wide SIMD lanes, has been widely used by researchers to accelerate scale-free graph algorithms. However, existing methods are not efficiently considering both the grouping strategy and the selection of the optimizing size for tiling the graph, which would decrease the efficiency of the graph computation. In this paper, we propose a novel Optimization and Auto-Tuning Method on SIMD architecture for scale-free graph algorithms, which is comprised of two sections. Firstly, in the Bucket Grouping Approach, an algorithm-based optimization has been employed to transform the scale-free graph data to conflict-free groups, which can decrease the preprocessing time and improve the SIMD efficiency of scalefree graph applications. Secondly, as optimal tile sizes are changing for different applications of different input graphs, an Auto-Tuning Strategy to optimize tile size achieves effective execution of graph computations. Two typical scale-free graph algorithms, Bellman-Ford and PageRank, are elected to evaluate the performance of OATM. According to the experiment results, OATM performs much better than existing methods, obtaining an average speedup of 1.1×, on these two applications both, by using OATM, comparing to the state-of-the-art methods.