GRAPH CACHING

• US 20120143854A1
• Filed: 12/05/2011
• Published: 06/07/2012
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Hussain, Muhammad Raghib, Parker, Trent
• Granted Patent: US 9,787,693 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 9/4498 Finite state machines
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

In a method and apparatus for analyzing nodes of a Deterministic Finite Automata (DFA), an accessibility ranking, based on a DFA graph geometrical configuration, may be determined in order to determine cacheable portions of the DFA graph in order to reduce the number of external memory accesses. A walker process may be configured to walk the graph in a graph cache as well as main memory. The graph may be generated in a manner allowing each arc to include information if the node it is pointing to is stored in the graph cache or in main memory. The walker may use this information to determine whether or not to access the next arc in the graph cache or in main memory.

Claims

1. A computer implemented method for caching a deterministic finite automata-based graph, the method comprising:

analyzing nodes in the graph to search for cacheable portions of the graph based on a geometrical configuration of the graph; and

caching the cacheable portions of the graph.

2. The method of claim 1 wherein analyzing the searchable graph comprises:

determining an accessibility ranking for each node, the accessibility ranking characterizing the likelihood each node will be accessed during a search; and

selecting the cacheable portions of the graph based on the accessibility ranking of the nodes.

3. The method of claim 2 wherein determining the accessibility ranking further comprises:

determining the accessibility ranking during a graph compilation stage.

4. The method of claim 2 wherein determining the accessibility ranking comprises:

evaluating a distance from a node to a root node, wherein a smaller distance from a node to a root node results in a higher accessibility ranking.

5. The method of claim 2 wherein determining the accessibility ranking further comprises:

evaluating an in-degree and an out-degree of a node, wherein a greater in-degree or out-degree of the node results in a higher accessibility ranking.

6. The method of claim 2 wherein determining the accessibility ranking comprises:

evaluating a heaviness of a node, wherein a heavier node comprises a higher accessibility ranking.

7. The method of claim 1 wherein caching further comprises storing and retrieving graph data from an on-chip memory location.

8. The method of claim 1 wherein caching further comprises storing and retrieving graph data from a memory location dedicated to graph usage.

9. The method of claim 1 wherein caching is performed during a loading stage of the graph.

10. The method of claim 2 wherein determining an accessibility ranking comprises:

adjusting the accessibility ranking during a search of the graph, wherein the accessibility ranking of frequently accessed nodes is increased.

11. The method of claim 10 wherein upon the adjusted accessibility ranking of a node reaching a threshold value, that node is cached.

12. The method of claim 1 wherein each node comprises at least one arc pointing to the node, the method further comprising:

reading a location indicator associated with each arc to determine if a next node is in the cache.

13. The method of claim 1 further comprising:

traversing the cacheable portions of the graph in cache with a walker process; and

further traversing non-cacheable portions of the graph with the walker process in a main memory.

14. A processor comprising:

a processing unit configured to analyze a searchable graph including a plurality of interconnected nodes to determine cacheable portions of the graph based on a geometrical configuration of the graph; and

a cache configured to cache the cacheable portions of the graph.

15. The processor of claim 14 wherein the processing unit is further configured to determine an accessibility ranking for each node, the accessibility ranking characterizing the likelihood each node will be accessed during a search, and to select the cacheable portions of the graph based on the accessibility ranking of the nodes.

16. The processor of claim 15 wherein the processing unit is configured to determine the accessibility ranking by evaluating an in-degree and an out-degree of a node, wherein a greater in-degree or out-degree of the node results in a higher accessibility ranking.

17. The processor of claim 15 wherein the processing unit is configured to determine the accessibility ranking by evaluating a distance from a node to a root node, with nodes closer to the root node having a higher accessibility ranking.

18. The processor of claim 15 wherein the processing unit is configured to determine the accessibility ranking by evaluating a heaviness of a node, wherein a heavier node comprises a higher accessibility ranking.

19. The processor of claim 15 wherein the processing unit is configured to determine the accessibility ranking during a graph compilation stage.

20. The processor of claim 14 wherein the cache is further configured to cache the cacheable portions of the graph during a loading stage of the graph.

21. The processor of claim 14 wherein the processing unit is further configured to adjust the accessibility ranking during a search of the graph, with the accessibility ranking increased if a node is frequently accessed.

22. The processor of claim 14 wherein the cache is further configured to cache the cacheable portions of the graph based on an adjusted accessibility ranking.

23. The processor of claim 14 wherein the cache is located in an on-chip memory unit.

24. The processor of claim 23 wherein the cache is dedicated to graph usage.

25. The processor of claim 14 further comprising a walker process configured to walk the cacheable portions of the graph in the cache and further configured to walk non-cacheable portions of the graph in a main memory.