NFA COMPLETION NOTIFICATION

• US 20150193681A1
• Filed: 01/09/2014
• Published: 07/09/2015
• Est. Priority Date: 01/09/2014
• Status: Active Grant

• Current Assignee: Netronome Systems Incorporated
• Original Assignee: Netronome Systems Incorporated
• Inventors: Stark, Gavin J., Zagorianakos, Steven W.
• Granted Patent: US 10,362,093 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/12 Protocol engines

Abstract

An automaton hardware engine employs a transition table organized into 2ⁿ rows, where each row comprises a plurality of n-bit storage locations, and where each storage location can store at most one n-bit entry value. Each row corresponds to an automaton state. In one example, at least two NFAs are encoded into the table. The first NFA is indexed into the rows of the transition table in a first way, and the second NFA is indexed in to the rows of the transition table in a second way. Due to this indexing, all rows are usable to store entry values that point to other rows.

Claims

1. A method comprising:

(a) a processor communicates a first command across a bus to an NFA (Non-deterministic Finite Automaton) engine, the first command is an instruction to the NFA engine to perform an NFA operation;

(b) the processor communicates a second command across the bus to the NFA engine, the second command is an instruction to the NFA engine to return a reference value to the processor;

(c) in response to the first command the NFA engine performs the NFA operation thereby generating a result and storing the result in a memory; and

(d) in response to the second command the NFA engine causes the reference value to be transferred across the bus to the processor.

2. The method of claim 1, further comprising:

(e) the processor reads the reference value; and

(f) in response to obtaining the reference value in (e) the processor reads the result from the memory.

3. The method of claim 1, wherein the processor is a part of a first island of an integrated circuit, wherein the NFA engine and the memory are part of a second island of the integrated circuit.

4. The method of claim 3, wherein the first island includes a memory accessible by the processor, and wherein the reference values is transferred in (d) into a part of the memory.

5. The method of claim 1, wherein the processor is one of a plurality of processors that can communicate commands across the bus to the NFA engine, wherein each of the processors has an associated memory, and wherein reference value is transferred in (d) into a part of the memory of the processor that communicated the first command in (a).

6. The method of claim 5, wherein the transferring of the reference value in (d) is a notification to the processor that the NFA engine has completed performing the first command, wherein no other processor of the plurality of processors receives the notification.

7. The method of claim 1, wherein the processor uses the reference value to determine that the NFA engine has completed performing the first command.

8. The method of claim 1, wherein the NFA engine is a part of a transactional memory, wherein the transactional memory includes a pipeline, and wherein the pipeline causes the reference value to be written across the bus in (d).

9. The method of claim 1, wherein the first command includes an NFA identifier value.

10. An apparatus comprising:

a plurality of processors that can supply NFA commands to an NFA engine, wherein one of the processors is a commanding processor that supplies an NFA command to the NFA engine;

an NFA pipeline that performs an NFA operation indicated by the NFA command; and

means for notifying the commanding processor that the NFA command has been completed without notifying any of the other processors of the plurality of processors.

11. The apparatus of claim 10, wherein the means includes a NFA controller, an event bus manager, a transactional memory pipeline, a bus, and a memory, wherein the means notifies the commanding processor that the NFA command has completed by the NFA controller prompting the event bus manager to command the transactional memory pipeline to push a reference value across the bus into a location in the memory, wherein the location is indicated by the commanding processor.

12. The apparatus of claim 10, wherein commanding processor is notified that the NFA command has completed by a reference value having been written into a location, wherein the location is read by the commanding processor and is not read by any of the other processor of the plurality of processors.

13. The apparatus of claim 10, wherein the means notifies the commanding processor by writing a reference value into a location in a memory, wherein the processor is a part of a first island of an integrated circuit, wherein the NFA engine and the memory are part of a second island of the integrated circuit.

14. The apparatus of claim 10, wherein the means notifies the commanding processor by writing a reference value across a bus and into a location in a memory, wherein the processor is a part of a first island of an integrated circuit, wherein the NFA engine and the memory are part of a second island of the integrated circuit, wherein the bus extends from the first island to the second island.

15. The apparatus of claim 10, wherein the commanding processor supplies a first command, a second command, and a third command to the NFA engine, wherein the first command is a configuration command that causes the NFA pipeline to be configured, wherein the second command is the NFA command that indicates the NFA operation, and wherein the third command is an event generate command that causes the means to notify the commanding processor that the NFA command has been completed.

16. The apparatus of claim 10, wherein the apparatus is an integrated circuit.

17. The apparatus of claim 10, wherein the commanding processor is a part of a first island, wherein the NFA engine is a part of a second island, wherein the commanding processor supplies the NFA command to the NFA engine by communicating the NFA command across a bus from the first island to the second island and into a command FIFO (First In First Out) memory of the NFA engine.

18. A method comprising:

(a) communicating an NFA (Non-deterministic Finite Automaton) command from a processor across a bus and into a command FIFO (First In First Out) memory of an NFA engine, wherein the command includes a reference value; and

(b) communicating the reference value from the NFA engine across the bus to the processor.

19. The method of claim 18, wherein the reference value is communicated to the processor by writing the reference value into a memory location polled by the processor.

20. The method of claim 18, wherein the command is an NFA engine event generate command that includes a NFA identifier value.

21. The method of claim 18, wherein the bus is a CPP (Command/Push/Pull) bus, and wherein the reference value is communicated in (b) by pushing the reference value across the bus.