Optimizing Graph Computing with an Adaptive Cache Structure

With the continuous progress of computer hardware and software, graph computing has been widely used in many fields. The memory access behavior of graph computation is variable. Different kernels accessing property arrays exhibit different spatial localities when graph algorithms are executed on a GPU, and the same kernel accessing different property arrays shows different spatial localities. Current cache optimization strategies in GPU architectures fail to enhance the performance of graph computing. The most advanced cache optimization strategies cannot implement different management strategies for data with different reusability, which is an essential reason for graph computing’s poor performance. In this paper, the AB-cache architecture is designed specifically for the GPU platform. AB-cache adopts an adaptive approach, cleverly utilizing two cache structures to optimize memory access requests with different spatial locality characteristics. An online automatic classification mechanism that fits the AB-cache architecture is also proposed; it can quickly classify memory access requests with different spatial locality with very low overhead. Through comprehensive evaluation of multiple graph algorithms and a wide range of graph datasets, the AB-cache scheme achieves a 1.1377 times speedup compared with the baseline scheme, which demonstrates the effectiveness and practicability of the scheme in graph computing performance optimization.