Deterministic finite automata (DFA) processing
First Claim
Patent Images
1. A network processor, comprising:
- at least one processor core;
a deterministic finite automata (DFA) module operating asynchronously to the at least one processor core, the DFA module traversing a plurality of nodes of at least one DFA graph stored in a non-cache memory that is;
i) external to the network processor and ii) sized to accommodate the at least one DFA graph having a number of nodes for searching for multiple patterns in one traversal of the at least one DFA graph, the DFA module including a plurality of DFA thread engines associated in a shared configuration with the at least one processor core;
and responsive to instructions for traversing the plurality of nodes of the at least one DFA from the at least one processor core, with packet data stored in a cache-coherent memory, each of the plurality of DFA thread engines is configured to;
traverse at least one DFA graph independent of others of the plurality of DFA thread engines traversing DFA graphs including the at least one DFA graph,fetch the packet data stored in the cache-coherent memory,in response to each byte of packet data fetched from the cache-coherent memory, issue an instruction to access and load a next node of the at least one DFA graph from the non-cache memory to traverse the next node of the at least one DFA graph, andwrite intermediate and final results of traversing the at least one DFA graph to the cache-coherent memory.
8 Assignments
0 Petitions
Accused Products
Abstract
A processor for traversing deterministic finite automata (DFA) graphs with incoming packet data in real-time. The processor includes at least one processor core and a DFA module operating asynchronous to the at least one processor core for traversing at least one DFA graph stored in a non-cache memory with packet data stored in a cache-coherent memory.
-
Citations
13 Claims
-
1. A network processor, comprising:
-
at least one processor core; a deterministic finite automata (DFA) module operating asynchronously to the at least one processor core, the DFA module traversing a plurality of nodes of at least one DFA graph stored in a non-cache memory that is;
i) external to the network processor and ii) sized to accommodate the at least one DFA graph having a number of nodes for searching for multiple patterns in one traversal of the at least one DFA graph, the DFA module including a plurality of DFA thread engines associated in a shared configuration with the at least one processor core;and responsive to instructions for traversing the plurality of nodes of the at least one DFA from the at least one processor core, with packet data stored in a cache-coherent memory, each of the plurality of DFA thread engines is configured to; traverse at least one DFA graph independent of others of the plurality of DFA thread engines traversing DFA graphs including the at least one DFA graph, fetch the packet data stored in the cache-coherent memory, in response to each byte of packet data fetched from the cache-coherent memory, issue an instruction to access and load a next node of the at least one DFA graph from the non-cache memory to traverse the next node of the at least one DFA graph, and write intermediate and final results of traversing the at least one DFA graph to the cache-coherent memory. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method of traversing DFA graphs with incoming packet data, comprising:
-
storing at least one DFA graph, having a number of nodes for searching for multiple patterns in one traversal of the at least one DFA graph, in a non-cache coherent memory that is;
i) external to a processor and ii) sized to accommodate the at least one DFA graph;storing in a cache-coherent memory, a DFA instruction for traversing nodes of the at least one DFA, the DFA instruction indicating packet data stored in the cache-coherent memory to use and the at least one DFA graph stored in the non-cache memory to traverse; traversing the at least one DFA graph by;
i) fetching the packet data stored in the cache-coherent memory, and ii) in response to each byte of packet data fetched from the cache-coherent memory, issuing an instruction to access and load a next node of the at least one DFA graph from the non-cache memory to traverse the next node of the at least one DFA graph; andwriting intermediate and final results of the traversing to the cache-coherent memory, the at least one DFA graph being traversed by a DFA thread engine that is independent of other DFA thread engines traversing DFA graphs, including the at least one DFA graph. - View Dependent Claims (12)
-
-
13. A network processor, comprising:
-
means for storing at least one DFA graph in a non-cache coherent memory that is;
i) external to the network processor and ii) sized to accommodate the at least one DFA graph having a number of nodes for searching for multiple patterns in one traversal of the at least one DFA graph;means for storing in a cache-coherent memory, a DFA instruction for traversing the plurality of nodes of the at least one DFA, the DFA instruction indicating packet data stored in the cache-coherent memory to use and the at least one DFA graph stored in the non-cache memory to traverse; means for traversing the at least one DFA graph by;
i) fetching the packet data stored in the cache-coherent memory, and ii) in response to each byte of packet data fetched from the cache-coherent memory, issuing an instruction to access and load a next node of the at least one DFA graph from the non-cache memory to traverse the next node of the at least one DFA graph, the means for traversing being independent of other means for traversing DFA graphs including the at least one DFA graph, the means for traversing searches a data packet different for data packets being searched by the other means for traversing;means for writing intermediate and final results of the traversing to the cache-coherent memory.
-
Specification