Accelerating Graph Processing with Lightweight Learning-Based Data Reordering

Abstract

Graph processing is a vital component in various application domains. However, a good graph processing performance is hard to achieve due to its intensive irregular data accesses. Noticing that in real-world graphs, a small portion of vertices occupy most connections, several techniques are proposed to reorder vertices based on their access frequency for better data access locality. However, these approaches can be further improved by identifying reordered data more effectively, which will reduce reordering overhead and improve overall performance. In this letter, we propose Learning-Based Reordering (LBR), a novel lightweight framework that identifies and reorders hot data adaptively for given graphs, algorithms, and threads. Our experimental evaluation indicates that LBR decreases reordering overhead by 24.7% while improves performance by 9.9% compared to the best-performing existing scheme.