Data-Aware Cache Management for Graph Analytics
Neelam Sharma1, Varun Venkitaraman1, Newton1,2, Vikash Kumar1, Shubham Singhania1 and Chandan Kumar Jha1
1Indian Institute of Technology Bombay
2National University of Singapore
ABSTRACT
Graph analytics is powering a wide variety of applications in the domains of cybersecurity, contact tracing, and social networking. It consists of various algorithms (or workloads) that investigate the relationships between entities involved in transactions, interactions, and organizations. CPU-based graph analytics is inefficient because their cache hierarchy performs poorly owing to highly irregular memory access patterns of graph workloads. Policies managing the cache hierarchy in such systems are ignorant to the locality demands of different data types within graph workloads, and therefore are suboptimal.
In this paper, we conduct an in-depth data type aware characterization of graph workloads to better understand the cache utilization of various graph data types.We find that different levels of the cache hierarchy are more sensitive to the locality demands of certain graph data types than others. Hence, we propose GRACE, a graph data-aware cache management technique, to increase cache hierarchy utilization, thereby minimizing off-chip memory traffic and enhancing performance. Our thorough evaluations show that GRACE, when augmented with a vertex reordering algorithm, outperforms a recent cache management scheme by up to 1.4×, with up to 27% reduction in expensive off-chip memory accesses. Thus, our work demonstrates that awareness of different graph data types is critical for effective cache management in graph analytics.
Keywords: Cache Management, Graph Analytics, Cache Bypassing.
