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.
1. In a services processor, 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 by: i) determining an accessibility ranking for each node, the accessibility ranking characterizing the likelihood each node will be accessed during a search for a pattern described by a regular expression in an input string, and ii) optimizing a node structure of each node to be cached, and iii) selecting the cacheable portions of the graph based on the accessibility rankings of the nodes during a graph compilation stage; and
caching the cacheable portions of the graph during a loading stage of the graph;
traversing the cacheable portions of the graph in a cache with a walker process; and
further traversing non-cacheable portions of the graph with the walker process in a main memory;
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.
2. The method of claim 1 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.
3. The method of claim 1 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.
4. The method of claim 1 wherein determining the accessibility ranking comprises:
evaluating a heaviness of a 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 further comprises storing and retrieving graph data from a memory location dedicated to graph usage.
7. The method of claim 1 wherein determining the accessibility ranking comprises:
adjusting the accessibility ranking during a search of the graph, wherein the accessibility ranking 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. A services processor comprising:
a processing unit configured to analyze a searchable graph including a plurality of interconnected nodes to search for cacheable portions of the graph by: i) determining an accessibility ranking for each node, the accessibility ranking characterizing the likelihood each node will be accessed during a search for a pattern described by a regular expression in an input string, and ii) optimizing a node structure of each node to be cached, and iii) selecting the cacheable portions of the graph based on the accessibility rankings of the nodes during a graph compilation stage; and
a cache configured to cache the cacheable portions of the graph during a loading stage of the graph; and
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;
wherein each node comprises at least one arc pointing to the node, the walker process further configured to read a location indicator associated with each arc to determine if a next node is in the cache.
10. The processor of claim 9 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.
11. The processor of claim 9 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.
12. The processor of claim 9 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.
13. The processor of claim 9 wherein the cache is located in an on-chip memory unit.
14. The processor of claim 13 wherein the cache is dedicated to graph usage.
15. The processor of claim 9 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.
16. The processor of claim 9 wherein the cache is further configured to cache the cacheable portions of the graph based on an adjusted accessibility ranking.