Improving Memory Access Locality for Large-Scale Graph Analysis Applications

Large-scale graph analysis on irregular instances is challenging due to the erratic memory access pattern. Although various techniques have been proposed to improve cache performance, in general they do not apply to algorithms with fine-grained parallelism. Most parallel graph algorithms exhibit poor locality behavior and thus poor cache performance on current architectures. In this paper we present our study of improving spatial locality for graph analysis applications. Our approach is to lay out the graph in a fashion that matches the frequently occurred patterns in parallel graph algorithms. We manipulate the graph layout by permuting the labelings of vertices. We show that the graph layout problem is NP-hard for the traversal pattern, and present performance comparisons of different labeling approaches. We further discuss the impact of labeling on fundamental building blocks of parallel algorithms such as pointer jumping and Euler-tour tree computation. Experimental results show that the labeling technique improves the scalability of the algorithms as a result of more efficient use of memory bandwidth.