TSN Cache: Exploiting Data Localities in Graph Computing Applications
Open Access
- 30 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 22 (2) , 1-26
Abstract
This article finds that the reusability of vertices in the same graph in graph processing differs, and the high-reuse and low-reuse vertices are stored together. These phenomena lead to the inability of existing GPU architectures to capture the reusability of graph processing. The most advanced cache optimization strategies cannot implement different management strategies for data with different reusability, which is an essential reason for graph processing’s poor performance. Therefore, we propose a TSN cache scheme for the GPU platform. This scheme employs distinct management strategies for data with varying reusability in the cache, effectively leveraging the locality of these different data types. In addition, the TSN cache scheme can also reduce the probability of cache thrashing caused by low-reuse data. This article evaluates multiple graph algorithms and datasets and shows that the TSN cache scheme achieves an average speedup of 1.38 compared with the baseline scheme.Keywords
Funding Information
- Key Program of the National Natural Science Foundation of China (62032001)
- National Natural Science Foundation of China (62472436)
- Foundation of Key Laboratory (WDZC20245250110)
This publication has 47 references indexed in Scilit:
- QuatCNNEx: A Knowledge Graph Embedding Model based on Quaternion Convolutional Neural Network2022
- Compressed page walk cacheFrontiers of Computer Science, 2021
- P-OPT: Practical Optimal Cache Replacement for Graph Analytics2021
- Designing a Cost-Effective Cache Replacement Policy using Machine Learning2021
- Repurpose Open Data to Discover Therapeutics for COVID-19 Using Deep LearningJournal of Proteome Research, 2020
- Domain-Specialized Cache Management for Graph Analytics2020
- A Closer Look at Lightweight Graph Reordering2019
- CoreScope: Graph Mining Using k-Core Analysis — Patterns, Anomalies and Algorithms2016
- NXgraph: An efficient graph processing system on a single machine2016
- Minimal disturbance placement and promotion2016