1. [Publications](/index.php/publications) 2. P-OPT: Practical Optimal Cache Replacement for Graph Analytics # P-OPT: Practical Optimal Cache Replacement for Graph Analytics ![Publication image](/sites/default/files/styles/wide/public/default_images/default.jpeg?itok=qUFsuJCP "Publication image") Graph analytics is an important workload that achieves suboptimal performance due to poor cache locality. State-of-the-art cache replacement policies fail to capture the highly dynamic and input-specific reuse patterns of graph application data. The main insight of this work is that for graph applications, the transpose of a graph succinctly represents the next references of all vertices in a graph execution; enabling an efficient emulation of Belady's MIN replacement policy. In this work, we propose P-OPT, an architecture solution that uses a specialized compressed representation of a transpose's next reference information to enable a practical implementation of Belady's MIN replacement policy. Our evaluations across multiple applications and inputs reveal that P-OPT improves cache locality for graph applications providing an average performance improvement of 33% (56% maximum) over LRU replacement. ## Authors Vignesh Balaji (Carnegie Mellon University) [Neal Crago](/index.php/person/neal-crago) [Aamer Jaleel](/index.php/person/aamer-jaleel) Brandon Lucia (Carnegie Mellon University) ## Publication Date Saturday, February 27, 2021 ## Published in [International Symposium on High Performance Computer Architecture (HPCA)](https://ieeexplore.ieee.org/document/9407090) ## Research Area [Computer Architecture](/index.php/research-area/computer-architecture) ## External Links [IEEE Digital Library](https://ieeexplore.ieee.org/document/9407090) ## Uploaded Files [Published Manuscript](https://d1qx31qr3h6wln.cloudfront.net/publications/HPCA_2021_Cache_Replacement.pdf "Open file in new window")1.1 MB ## Award Best Paper nominee ## Copyright This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to .