Back to results
US 8,392,590 B2Granted
Deterministic finite automata (DFA) processing
AssigneeCavium, Inc.
InventorsGregg A. Bouchard, David A. Carlson, Richard E. Kessler, Muhammad R. Hussain
Life of this patent
Estimating the term…
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.
Claims13
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.
5 more elements
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;
- and
- writing 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.
4 more elements
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.
3 more elements
Dependencies are inferred from the claim text.