Cache memory architecture and policies for accelerating graph algorithms

摘要

A cache memory may be configured to store a plurality of lines, where each line includes data and metadata. A circuit may be configured to determine a respective number of edges associated with each vertex of a plurality of vertices included in a graph data structure, and sort the graph data structure using the respective number of edges. The circuit may be further configured to determine a reuse value for a particular vertex of the plurality of vertices using a respective address associated with the particular vertex in the sorted graph, and store data and metadata associated with the particular vertex in a particular line of the plurality of lines in the cache memory.