2023/05/11 by Alexandre Valentin Jamet, Jamet, Alexandre Valentin, Lluc Alvarez +3
Computer Science · Engineering · #Cloud Computing and Resource Management #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Hardware Architecture (cs.AR) #Parallel Computing and Optimization Techniques
paper · doi:10.48550/arxiv.2305.06696
openalex publication_date 2023/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In recent years, graph-processing has become an essential class of workloads with applications in a rapidly growing number of fields. Graph-processing typically uses large input sets, often in multi-gigabyte scale, and data-dependent graph traversal methods exhibiting irregular memory access patterns. Recent work demonstrates that, due to the highly irregular memory access patterns of data-dependent graph traversals, state-of-the-art graph-processing workloads spend up to 80 % of the total execution time waiting for memory accesses to be served by the DRAM. The vast disparity between the Last Level Cache (LLC) and main memory latencies is a problem that has been addressed for years in computer architecture. One of the prevailing approaches when it comes to mitigating this performance gap between modern CPUs and DRAM is cache replacement policies. In this work, we characterize the challenges drawn by graph-processing workloads and evaluate the most relevant cache replacement policies.