Cache memory architecture and policies for accelerating graph algorithms

• US 10,417,134 B2
• Filed: 02/23/2017
• Issued: 09/17/2019
• Est. Priority Date: 11/10/2016
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Faldu, Priyank, Diamond, Jeffrey, Patel, Avadh
• Primary Examiner(s): Tsai, Sheng Jen
• Application Number:
  US15/440,400
• Publication Number:
  US 20180129613A1
• Time in Patent Office: 936 Days
• Field of Search: 711136
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2212/68 Details of translation look-aside buffer [TLB]
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

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.

Claims

1. An apparatus, comprising:

a cache memory configured to store a plurality of lines that include data and metadata; and

a circuit configured to;

determine a respective number of edges associated with vertices of a plurality of vertices included in a graph data structure;

sort the graph data structure using the respective number of edges associated with the vertices of the plurality of vertices to generate a sorted graph;

determine a reuse value for a particular vertex of the plurality of vertices using results of a comparison of a respective address associated with the particular vertex in the sorted graph to a plurality of address ranges associated with corresponding addresses of the plurality of vertices, wherein the reuse value is indicative of a frequency with which a particular line of the plurality of lines associated with the particular vertex is accessed in the cache memory; and

store, in the cache memory, data and metadata associated with the particular vertex of the plurality of vertices in the particular line, wherein the metadata includes at least the reuse value for the particular vertex and a list of edges connected to the particular vertex.

2. The apparatus of claim 1, wherein the circuit is further configured to:

in response to receiving new data to store in the cache memory, select a given line of the plurality of lines; and

evict the given line.

3. The apparatus of claim 2, wherein the circuit is further configured to select the given line of the plurality of lines in response to a determination that metadata associated with the given line does not include a corresponding reuse value.

4. The apparatus of claim 2, wherein the circuit is further configured to select the given line in response to a determination that the given line is associated with a given vertex of the plurality of vertices and that a corresponding reuse value for the given vertex indicates low reuse potential.

5. The apparatus of claim 2, wherein the circuit is further configured to select the given line in response to a determination that the given line is associated with a given vertex of the plurality of vertices and that a corresponding reuse value for the given vertex indicates a medium reuse potential and that a particular line of the plurality of lines associated with a particular vertex of the plurality of vertices that has a low reuse is not currently stored in the cache memory.

6. The apparatus of claim 1, wherein to determine the reuse value for the particular vertex of the plurality of vertices, the circuit is further configured to compare an address value associated with a location in the cache memory associated with the particular vertex to at least one previously determined address values.

7. A method, comprising:

identifying a respective number of edges connected to vertices of a plurality of vertices included in a graph data structure stored in memory of a computing system;

sorting the graph data structure using the respective number of edges connected to the vertices included in the graph data structure to generate a sorted graph;

determining a reuse value for a particular vertex of the plurality of vertices using results of comparing a respective address associated with the particular vertex in the sorted graph to a plurality of address ranges associated with corresponding addresses of the plurality of vertices, wherein the reuse value is indicative of a frequency with which a particular line of a plurality of lines stored in a cache memory associated with the particular vertex is accessed; and

storing, in the cache memory, data and metadata associated with the particular vertex of the plurality of vertices in the particular line, wherein the metadata includes at least the reuse value for the particular vertex and a list of edges connected to the particular vertex.

8. The method of claim 7, further comprising:

in response to receiving new data to store in the cache memory, selecting a given line of the plurality of lines; and

evicting the given line.

9. The method of claim 8, further comprising selecting the given line of the plurality of lines in response to determining that metadata associated with the given line does not include a corresponding reuse value.

10. The method of claim 8, further comprising selecting the given line in response to determining that the given line is associated with a given vertex of the plurality of vertices and that a corresponding reuse value for the given vertex indicates low reuse potential.

11. The method of claim 8, further comprising selecting the given line in response to determining that the given line is associated with a given vertex of the plurality of vertices and that a corresponding reuse value for the given vertex indicates a medium reuse potential and that a particular line of the plurality of lines associated with a particular vertex of the plurality of vertices that has a low reuse is not currently stored in the cache memory.

12. The method of claim 8, further comprising selecting the given line in response to determining that the given line is associated with a given vertex of the plurality of vertices and that a corresponding reuse value for the given vertex indicates a high reuse potential and that a particular line of the plurality of lines associated with a particular vertex of the plurality of vertices that has either a low reuse potential or medium reuse potential is not currently stored in the cache memory.

13. The method of claim 7, wherein determining the reuse value for the particular vertex of the plurality of vertices includes comparing an address value associated with a location in the cache memory associated with the particular vertex to at least one previously determined address values.

14. The method of claim 7, further comprising:

receiving new data to be stored in the cache memory; and

bypassing insertion in the cache memory in response to determining that a given vertex of the plurality of vertices associated with the new data has a low reuse potential.

15. A system, comprising:

a memory configured to store a graph data structure that includes a plurality of vertices, and a plurality of edges, wherein each specifies a connection between two vertices of the plurality of vertices;

a cache memory configured to store a plurality of lines, wherein each line of the plurality of lines includes data and metadata; and

a processor configured to;

determine a respective number of edges associated with vertices of the plurality of vertices;

sort the graph data structure using the respective number of edges associated with the vertices of the plurality of vertices to generate a sorted graph;

determine a reuse value for a particular vertex of the plurality of vertices using results of a comparison of a respective address associated with the particular vertex in the sorted graph to a plurality of address ranges associated with corresponding addresses of the plurality of vertices, wherein the reuse value is indicative of a frequency with which a particular line of the plurality of lines associated with the particular vertex is access in the cache memory; and

store, in the cache memory, data and metadata associated with the particular vertex of the plurality of vertices in the particular line of the plurality of lines, wherein the metadata includes at least the reuse value for the particular vertex and a list of edges connected to the particular vertex.

16. The system of claim 15, wherein the processor is further configured to:

in response to receiving new data to store in the cache memory, select a given line of the plurality of lines; and

evict the given line.

17. The system of claim 16, wherein the processor is further configured to select the given line of the plurality of lines in response to a determination that metadata associated with the given line does not include a corresponding reuse value.

18. The system of claim 16, wherein the processor is further configured to select the given line in response to a determination that the given line is associated with a given vertex of the plurality of vertices and that a corresponding reuse value for the given vertex indicates a low reuse potential.

19. The system of claim 16, wherein the processor is further configured to select the given line in response to a determination that the given line is associated with a given vertex of the plurality of vertices and that a corresponding reuse value for the given vertex indicates a medium reuse and that a particular line of the plurality of lines associated with a particular vertex of the plurality of vertices that has a low reuse is not currently stored in the cache memory.

20. The system of claim 19, wherein to determine the reuse value for the particular vertex of the plurality of vertices, the processor is further configured to compare an address value associated with a location in the memory associated with the particular vertex to at least one previously determined address values.