Graph caching

• US 9,787,693 B2
• Filed: 12/05/2011
• Issued: 10/10/2017
• 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
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US13/311,244
• Publication Number:
  US 20120143854A1
• Time in Patent Office: 2,136 Days
• Field of Search: 707739, 707798, 707797
• 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 (DFA-based) graph, the method comprising:

analyzing nodes in the DFA-based graph to search for cacheable portions of the DFA-based graph by utilizing an accessibility ranking associated with each node in the DFA-based graph, the accessibility ranking for each node in the DFA-based graph determined by a compiler generating the DFA-based graph and characterizing the likelihood each node will be accessed during a search of the DFA-based graph for a pattern described by a regular expression in an input string, the compiler determining the accessibility ranking for each node during a graph compilation stage;

selecting the cacheable portions of the DFA-based graph based on the accessibility rankings of the nodes; and

caching, during a loading stage of the DFA-based graph, the cacheable portions of the DFA-based graph selected based on the accessibility rankings determined during the graph compilation stage and storing non-cacheable portions of the DFA-based graph in a main memory, wherein a walker process is configured to search for the pattern by traversing the cacheable portions of the DFA-based graph in cache and traversing the non-cacheable portions of the DFA-based graph in the main memory.

2. The method of claim 1 wherein determining the accessibility ranking for each node includes:

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

3. The method of claim 1 wherein determining the accessibility ranking for each node includes:

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

4. The method of claim 1 wherein determining the accessibility ranking for each node includes:

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

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

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

7. The method of claim 1 further comprising:

adjusting the accessibility rankings determined during the graph compilation stage, the accessibility rankings adjusted during the search of the DFA-based graph, wherein the accessibility rankings of frequently accessed nodes is increased.

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

9. 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 cached.

10. The method of claim 1 further comprising selecting a sub-section of the DFA-based graph, the sub-section including a plurality of nodes in the DFA-based graph, based on an accessibility ranking for the sub-section, and caching the sub-section selected.

11. A system comprising a hardware processor, the hardware processor configured to:

analyze a searchable graph including a plurality of interconnected nodes to determine cacheable portions of the searchable graph by utilizing an accessibility ranking associated with each node in the searchable graph;

determine the accessibility ranking of each node in the searchable graph during generation of the searchable graph, the accessibility ranking for each node characterizing the likelihood each node will be accessed during a search of the searchable graph for a pattern described by a regular expression in an input string;

determine the accessibility ranking during a graph compilation stage;

select the cacheable portions of the searchable graph based on the accessibility ranking of the nodes; and

cache, during a loading stage of the searchable graph, the cacheable portions of the searchable graph selected based on the accessibility rankings determined during the graph compilation stage and store non-cacheable portions of the searchable graph in a main memory, wherein a walker process is configured to search for the pattern by traversing the cacheable portions of the searchable graph in cache and traversing the non-cacheable portions of the searchable graph in the main memory.

12. The system of claim 11 wherein the hardware processor is further configured to determine the accessibility ranking for each node by evaluating an in-degree and an out-degree of the node, wherein a greater in-degree or out-degree of the node results in a higher accessibility ranking.

13. The system of claim 11 wherein the hardware processor is further configured to determine the accessibility ranking for each node by evaluating a distance from the node to a root node, with nodes closer to the root node having a higher accessibility ranking.

14. The system of claim 11 wherein the hardware processor is further configured to determine the accessibility ranking for each node by evaluating a heaviness of the node, wherein a heavier node comprises a higher accessibility ranking.

15. The system of claim 11 wherein the hardware processor is further configured to adjust the accessibility rankings determined during the graph compilation stage, the accessibility rankings adjusted during the search of the searchable graph, wherein the accessibility rankings of frequently accessed nodes is increased.

16. The system of claim 11 wherein the hardware processor is further configured to cache the cacheable portions of the searchable graph based on an adjusted accessibility ranking.

17. The system of claim 11 wherein the cache is located in an on-chip memory.

18. The processor system of claim 11 wherein the cache is dedicated to graph usage.

19. A computer implemented method for caching a deterministic finite automata-based (DFA-based) graph, the method comprising:

analyzing nodes in the DFA-based graph to search for cacheable portions of the DFA-based graph by utilizing an accessibility ranking associated with each node in the DFA-based graph, the accessibility ranking for each node in the DFA-based graph determined by a compiler generating the DFA-based graph and characterizing the likelihood each node will be accessed during a search of the DFA-based graph for a pattern described by a regular expression in an input string, the compiler determining the accessibility ranking for each node during a graph compilation stage, wherein determining the accessibility ranking for each node during the graph compilation stage includes evaluating an in-degree and an out-degree of the node and a greater in-degree or out-degree of the node results in a higher accessibility ranking;

selecting the cacheable portions of the DFA-based graph based on the accessibility rankings of the nodes; and

caching the selected cacheable portions of the DFA-based graph and storing non-cacheable portions of the DFA-based graph in a main memory, wherein a walker process is configured to search for the pattern by traversing the cacheable portions of the DFA-based graph in cache and traversing the non-cacheable portions of the DFA-based graph in the main memory.

20. A computer implemented method for caching a deterministic finite automata-based (DFA-based) graph, the method comprising:

analyzing nodes in the DFA-based graph to search for cacheable portions of the DFA-based graph by utilizing an accessibility ranking associated with each node in the DFA-based graph, the accessibility ranking for each node in the DFA-based graph determined by a compiler generating the DFA-based graph and characterizing the likelihood each node will be accessed during a search of the DFA-based graph for a pattern described by a regular expression in an input string, the compiler determining the accessibility ranking for each node during a graph compilation stage, wherein determining the accessibility ranking for each node during the graph compilation stage includes evaluating a heaviness of the node and a heavier node comprises a higher accessibility ranking;

selecting the cacheable portions of the DFA-based graph based on the accessibility rankings of the nodes; and

caching the selected cacheable portions of the DFA-based graph and storing non-cacheable portions of the DFA-based graph in a main memory, wherein a walker process is configured to search for the pattern by traversing the cacheable portions of the DFA-based graph in cache and traversing the non-cacheable portions of the DFA-based graph in the main memory.