  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.
