Engine architecture for processing finite automata

• US 9,785,403 B2
• Filed: 07/08/2014
• Issued: 10/10/2017
• Est. Priority Date: 08/30/2013
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Billa, Satyanarayana Lakshmipathi, Shanava, Yossef, Bouchard, Gregg A., Nakada, Timothy Toshio
• Primary Examiner(s): Caldwell, Andrew
• Assistant Examiner(s): Metzger, Michael
• Application Number:
  US14/325,841
• Publication Number:
  US 20150067123A1
• Time in Patent Office: 1,190 Days
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 21/567 using dedicated hardware
• CPC Class Codes: G06F 2205/126 Monitoring of intermediate fill level, i.e. with additional means for monitoring the fill level, e.g. half full flag, almost empty flag
• CPC Class Codes: G06F 2213/2806 Space or buffer allocation for DMA transfers
• CPC Class Codes: G06F 5/14 for overflow or underflow handling, e.g. full or empty flags
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: H04L 41/28 Restricting access to network management systems or functions, e.g. using authorisation function to access network configuration
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

An engine architecture for processing finite automata includes a hyper non-deterministic automata (HNA) processor specialized for non-deterministic finite automata (NFA) processing. The HNA processor includes a plurality of super-clusters and an HNA scheduler. Each super-cluster includes a plurality of clusters. Each cluster of the plurality of clusters includes a plurality of HNA processing units (HPUs). A corresponding plurality of HPUs of a corresponding plurality of clusters of at least one selected super-cluster is available as a resource pool of HPUs to the HNA scheduler for assignment of at least one HNA instruction to enable acceleration of a match of at least one regular expression pattern in an input stream received from a network.

Claims

1. A security appliance operatively coupled to a network, the security appliance comprising:

at least one Central Processing Unit (CPU) core; and

at least one hyper non-deterministic automata (HNA) processor operatively coupled to the at least one CPU core and specialized for non-deterministic finite automata (NFA) processing, the at least one HNA processor including;

a plurality of super-clusters, each super-cluster including a plurality of clusters, each cluster of the plurality of clusters including a plurality of HNA processing units (HPUs), the at least one CPU core configured to select at least one super-cluster of the plurality of super-clusters;

an HNA on-chip instruction queue configured to store at least one HNA instruction; and

an HNA scheduler configured to select a given HPU of the plurality of HPUs of the plurality of clusters of the at least one super-cluster selected and assign the at least one HNA instruction to the given HPU selected in order to initiate matching at least one regular expression pattern in an input stream received from the network.

2. The security appliance of claim 1, wherein each super-cluster further includes a super-cluster graph memory exclusive to a corresponding super-cluster, the super-cluster graph memory accessible to a corresponding plurality of HPUs of a corresponding plurality of clusters of the corresponding super-cluster and configured to store a subset of nodes of at least one per-pattern NFA statically, the subset of nodes determined by a compiler of the at least one per-pattern NFA.

3. The security appliance of claim 2, wherein:

each super-cluster further includes at least one super-cluster character class memory exclusive to a corresponding super-cluster, each at least one super-cluster character class memory configured to store regular expression pattern character class definitions statically.

4. The security appliance of claim 3, wherein the super-cluster graph memory and the at least one super-cluster character class memory are unified.

5. The security appliance of claim 3, wherein the at least one super-cluster character class memory is shared by a corresponding plurality of HPUs of a corresponding plurality of clusters of the corresponding super-cluster.

6. The security appliance of claim 1, wherein:

each super-cluster further includes at least one super-cluster character class memory, each at least one super-cluster character class memory exclusive to a given cluster of a corresponding plurality of clusters of a corresponding super-cluster and shared by a corresponding plurality of HPUs of the given cluster, each at least one super-cluster character class memory configured to store regular expression pattern character class definitions statically.

7. The security appliance of claim 1, wherein the at least one CPU core is further configured to select the at least one super-cluster of the plurality of super-clusters by restricting super-cluster selection based on a graph identifier associated with the at least one HNA instruction.

8. The security appliance of claim 7, wherein the graph identifier is associated with a given per-pattern NFA of a plurality of per-pattern NFAs and restricting the super-cluster selection includes a determination that at least one node of the given per-pattern NFA is stored in a super-cluster graph memory exclusive to the at least one super-cluster selected.

9. The security appliance of claim 7, wherein:

the graph identifier is associated with a given per-pattern NFA of a plurality of per-pattern NFAs;

the HNA scheduler is configured to select the given HPU from a restricted set of HPUs that includes each corresponding plurality of HPUs of each corresponding plurality of clusters of the at least one super-cluster selected; and

the at least one CPU core is further configured to select the at least one super-cluster of the plurality of super-clusters based on a determination that at least one node of the given per-pattern NFA associated with the graph identifier is stored in a super-cluster graph memory exclusive to the at least one super-cluster selected.

10. The security appliance of claim 9, wherein the HNA scheduler is further configured to select the given HPU from the restricted set of HPUs based on a round robin schedule for HPUs in the restricted set of HPUs.

11. The security appliance of claim 9, wherein the HNA scheduler is further configured to select the given HPU from the restricted set of HPUs based on instantaneous loading of each HPU in the restricted set of HPUs.

12. The security appliance of claim 1, wherein:

each super-cluster further includes a super-cluster graph memory exclusive to a corresponding super-cluster; and

each super-cluster graph memory is configured to store at least one node of at least one per-pattern NFA of a plurality of per-pattern NFAs to replicate the at least one node in each super-cluster graph memory of each super-cluster of the at least one HNA processor.

13. The security appliance of claim 12, wherein:

the at least one CPU core is further configured to provide the HNA scheduler with an option to select the at least one super-cluster based on a determination that a given per-pattern NFA of the at least one per-pattern NFA associated with the at least one HNA instruction is replicated; and

the HNA scheduler is further configured to;

select the at least one super-cluster based on the option provided and (i) a first round robin schedule for the plurality of super-clusters, (ii) a first instantaneous loading of the plurality of super-clusters or (iii) a combination of (i) and (ii); and

select the given HPU from the plurality of HPUs of the plurality of clusters of the at least one super-cluster selected based on a second round robin schedule for the plurality of HPUs of the plurality of clusters of at least one super-cluster selected, a second instantaneous loading of the plurality of HPUs of the plurality of clusters of the at least one super-cluster selected, or a combination thereof.

14. The security appliance of claim 1, wherein the at least one HNA processor further includes an HNA on-chip graph memory accessible to the plurality of HPUs of the plurality of clusters of the plurality of super-clusters, the HNA on-chip graph memory configured to store a subset of nodes of at least one per-pattern NFA statically, the subset of nodes determined by a compiler of the at least one per-pattern NFA.

15. The security appliance of claim 1, wherein the at least one HNA instruction is a first at least one HNA instruction and the security appliance further comprises:

at least one system memory operatively coupled to the at least one CPU core and the at least one HNA processor, the at least one system memory configured to include;

an HNA off-chip instruction queue for storing a second at least one HNA instruction, the second at least one HNA instruction pending transfer to the HNA on-chip instruction queue of the HNA processor; and

an HNA off-chip graph memory configured to store a subset of nodes of at least one per-pattern NFA statically, the subset of nodes determined by a compiler of the at least one per-pattern NFA.

16. The security appliance of claim 15, further comprising:

at least one Local Memory Controller (LMC), wherein the at least one LMC is operatively coupled to the at least one HNA processor and the at least one system memory and a given LMC of the at least one LMC is configured to enable non-coherent access of the at least one system memory for access of the HNA off-chip graph memory by the at least one HNA processor.

17. The security appliance of claim 15, wherein the at least one system memory is further configured to include an HNA packet data memory configured to store multiple payloads contiguously, each of the multiple payloads having a fixed maximum length and associated with a given HNA instruction of the first at least one HNA instruction stored in the HNA on-chip instruction queue or the second at least one HNA instruction pending transfer to the HNA on-chip instruction queue.

18. The security appliance of claim 17, further comprising at least one LMC and wherein the at least one system memory is further configured to include:

an HNA input stack partition configured to store at least one HNA input stack, each at least one HNA input stack configured to store at least one HNA input job for at least one HPU of the plurality of HPUs of the plurality of clusters of the plurality of super-clusters;

an HNA off-chip run stack partition configured to store at least one HNA off-chip run stack to extend storage of at least one on-chip run stack, each at least one on-chip run stack configured to store at least one run-time HNA job for the at least one HPU;

an HNA off-chip save buffer partition configured to extend storage of at least one on-chip save buffer, each at least one on-chip save buffer configured to store the at least one run-time HNA job for the at least one HPU based on detecting a payload boundary; and

an HNA off-chip result buffer partition configured to store at least one final match result entry of the at least one regular expression pattern determined by the at least one HPU to match in the input stream, wherein each at least one HNA instruction stored identifies a given HNA input stack of the HNA input stack partition, a given HNA off-chip run stack of the HNA off-chip run stack partition, a given HNA off-chip save buffer of the HNA off-chip save buffer partition, and a given HNA off-chip result buffer of the HNA off-chip result buffer partition.

19. The security appliance of claim 18, further comprising at least one LMC and wherein a given LMC of the at least one LMC is configured to:

enable the at least one HNA processor to access the HNA packet data memory, HNA input stack partition, HNA off-chip instruction queue, HNA off-chip run stack partition, HNA off-chip save buffer partition, and the HNA off-chip result buffer partition via a coherent path; and

enable the at least one HNA processor to access the HNA off-chip graph memory via a non-coherent path.

20. The security appliance of claim 1, wherein each HPU of the plurality of HPUs of the plurality of clusters of the plurality of super-clusters includes:

a node cache configured to cache one or more nodes from a super-cluster graph memory, an HNA on-chip graph memory, or an HNA off-chip graph memory;

a character class cache configured to cache one or more regular expression pattern character class definitions from a super-cluster character class memory;

a payload buffer configured to store a given payload from an HNA packet data memory, the at least one HNA instruction including an identifier for a location of the given payload in the HNA packet data memory;

a top of stack register configured to store a single HNA job;

a run stack configured to store multiple HNA jobs;

a unified memory configured to store first content of a save stack and second content of a match result buffer, the first content including one or more HNA jobs stored in the run stack and the second content including one or more final match results; and

an HNA processing core operatively coupled to the node cache, character class cache, payload buffer, top of stack register, run stack, and the unified memory, the HNA processing core configured to walk at least one per-pattern NFA with payload segments stored in the payload buffer to determine a match of the at least one regular expression pattern.

21. The security appliance of claim 1, wherein:

each super-cluster further includes a super-cluster graph memory exclusive to a corresponding super-cluster;

the at least one HNA processor further includes an HNA on-chip graph memory shared by the plurality of super-clusters;

the security appliance further comprises at least one system memory configured to include an HNA off-chip graph memory shared by the plurality of super-clusters; and

the given HPU selected is configured to walk nodes of a given per-pattern NFA of at least one per-pattern NFA with segments of a payload of the input stream based on the at least one HNA instruction assigned, the nodes walked stored in a node cache exclusive to the given HPU selected, the super-cluster graph memory, the HNA on-chip graph memory, the HNA off-chip graph memory, or a combination thereof.

22. The security appliance of claim 1, wherein the plurality of HPUs of the plurality of clusters of the at least one super-cluster selected from a resource pool of HPUs available to the HNA scheduler for selection to enable acceleration of the matching.

23. A hyper non-deterministic finite automata (HNA) processor specialized for non-deterministic finite automata (NFA) processing, the HNA processor comprising:

a plurality of super-clusters, each super-cluster including a plurality of clusters, each cluster of the plurality of clusters including a plurality of HNA processing units (HPUs); and

an HNA on-chip instruction queue configured to store at least one HNA instruction, the plurality of HPUs of the plurality of clusters of at least one selected super-cluster of the plurality of super-clusters forming a resource pool of HPUs available for assignment of the at least one HNA instruction; and

an HNA scheduler configured to select a given HPU of the resource pool formed and assign the at least one HNA instruction to the given HPU selected in order to initiate matching at least one regular expression pattern in an input stream received from a network.

24. A method comprising:

operatively coupling at least one hyper non-deterministic automata (HNA) processor to at least one CPU core, the at least one HNA specialized for non-deterministic finite automata (NFA) processing; and

configuring the at least one HNA processor to include;

a plurality of super-clusters, each super-cluster including a plurality of clusters, each cluster of the plurality of clusters including a plurality of HNA processing units (HPUs), the at least one CPU core configured to select at least one super-cluster of the plurality of super-clusters;

an HNA on-chip instruction queue configured to store at least one HNA instruction; and

an HNA scheduler configured to select a given HPU of the plurality of HPUs of the plurality of clusters of the at least one super-cluster selected and assign the at least one HNA instruction to the given HPU selected in order to initiate matching at least one regular expression pattern in an input stream received from the network.

25. The method of claim 24, wherein each super-cluster further includes a super-cluster graph memory exclusive to a corresponding super-cluster, the super-cluster graph memory accessible to a corresponding plurality of HPUs of a corresponding plurality of clusters of the corresponding super-cluster and configured to store a subset of nodes of at least one per-pattern NFA statically, the subset of nodes determined by a compiler of the at least one per-pattern NFA.

26. The method of claim 25, wherein:

each super-cluster further includes at least one super-cluster character class memory exclusive to a corresponding super-cluster, each at least one super-cluster character class memory configured to store regular expression pattern character class definitions statically.

27. The method of claim 26, wherein the super-cluster graph memory and the at least one super-cluster character class memory are unified.

28. The method of claim 26, wherein the at least one super-cluster character class memory is shared by a corresponding plurality of HPUs of a corresponding plurality of clusters of the corresponding super-cluster.

29. The method of claim 24, wherein:

each super-cluster further includes at least one super-cluster character class memory, each at least one super-cluster character class memory exclusive to a given cluster of a corresponding plurality of clusters of a corresponding super-cluster and shared by a corresponding plurality of HPUs of the given cluster, each at least one super-cluster character class memory configured to store regular expression pattern character class definitions statically.

30. The method of claim 24, wherein the at least one CPU core is further configured to select the at least one super-cluster of the plurality of super-clusters by restricting super-cluster selection based on a graph identifier associated with the at least one HNA instruction.

31. The method of claim 30, wherein the graph identifier is associated with a given per-pattern NFA of a plurality of per-pattern NFAs and restricting the super-cluster selection includes a determination that at least one node of the given per-pattern NFA is stored in a super-cluster graph memory exclusive to the at least one super-cluster selected.

32. The method of claim 30, wherein:

the graph identifier is associated with a given per-pattern NFA of a plurality of per-pattern NFAs;

the HNA scheduler is configured to select the given HPU from a restricted set of HPUs that includes each corresponding plurality of HPUs of each corresponding plurality of clusters of the at least one super-cluster selected; and

the at least one CPU core is further configured to select the at least one super-cluster of the plurality of super-clusters based on a determination that at least one node of the given per-pattern NFA associated with the graph identifier is stored in a super-cluster graph memory exclusive to the at least one super-cluster selected.

33. The method of claim 32, wherein the HNA scheduler is further configured to select the given HPU from the restricted set of HPUs based on a round robin schedule for HPUs in the restricted set of HPUs.

34. The method of claim 32, wherein the HNA scheduler is further configured to select the given HPU from the restricted set of HPUs based on instantaneous loading of each HPU in the restricted set of HPUs.

35. The method of claim 24, wherein:

each super-cluster further includes a super-cluster graph memory exclusive to a corresponding super-cluster; and

each super-cluster graph memory is configured to store at least one node of at least one per-pattern NFA of a plurality of per-pattern NFAs to replicate the at least one node in each super-cluster graph memory of each super-cluster of the at least one HNA processor.

36. The method of claim 35, wherein:

the at least one CPU core is further configured to provide the HNA scheduler with an option to select the at least one super-cluster based on a determination that a given per-pattern NFA of the at least one per-pattern NFA associated with the at least one HNA instruction is replicated; and

the HNA scheduler is further configured to;

select the at least one super-cluster based on the option provided and (i) a first round robin schedule for the plurality of super-clusters, (ii) a first instantaneous loading of the plurality of super-clusters or (iii) a combination of (i) and (ii); and

select the given HPU from the plurality of HPUs of the plurality of clusters of the at least one super-cluster selected based on a second round robin schedule for the plurality of HPUs of the plurality of clusters of the at least one super-cluster selected, instantaneous loading of the plurality of HPUs of the plurality of clusters of the at least one super-cluster selected, or a combination thereof.

37. The method of claim 24, wherein the at least one HNA processor further includes an HNA on-chip graph memory accessible to the plurality of HPUs of the plurality of clusters of the plurality of super-clusters, the HNA on-chip graph memory configured to store a subset of nodes of at least one per-pattern NFA statically, the subset of nodes determined by a compiler of the at least one per-pattern NFA.

38. The method of claim 24, wherein the at least one HNA instruction is a first at least one HNA instruction and the method further comprises:

at least one system memory operatively coupled to the at least one CPU core and the at least one HNA processor, the at least one system memory configured to include;

an HNA off-chip instruction queue for storing a second at least one HNA instruction, the second at least one HNA instruction pending transfer to the HNA on-chip instruction queue of the HNA processor; and

an HNA off-chip graph memory configured to store a subset of nodes of at least one per-pattern NFA statically, the subset of nodes determined by a compiler of the at least one per-pattern NFA.

39. The method of claim 38, further comprising:

at least one Local Memory Controller (LMC), wherein the at least one LMC is operatively coupled to the at least one HNA processor and the at least one system memory and a given LMC of the at least one LMC is configured to enable non-coherent access of the at least one system memory for access of the HNA off-chip graph memory by the at least one HNA processor.

40. The method of claim 38, wherein the at least one system memory is further configured to include an HNA packet data memory configured to store multiple payloads contiguously, each of the multiple payloads having a fixed maximum length and associated with a given HNA instruction of the first at least one HNA instruction stored in the HNA on-chip instruction queue or the second at least one HNA instruction pending transfer to the HNA on-chip instruction queue.

41. The method of claim 38, further comprising at least one LMC and wherein the at least one system memory is further configured to include:

an HNA input stack partition configured to store at least one HNA input stack, each at least one HNA input stack configured to store at least one HNA input job for at least one HPU of the plurality of HPUs of the plurality of clusters of the plurality of super-clusters;

an HNA off-chip run stack partition configured to store at least one HNA off-chip run stack to extend storage of at least one on-chip run stack, each at least one on-chip run stack configured to store at least one run-time HNA job for the at least one HPU;

an HNA off-chip save buffer partition configured to extend storage of at least one on-chip save buffer, each at least one on-chip save buffer configured to store the at least one run-time HNA job for the at least one HPU based on detecting a payload boundary; and

an HNA off-chip result buffer partition configured to store at least one final match result entry of the at least one regular expression pattern determined by the at least one HPU to match in the input stream, wherein each at least one HNA instruction stored identifies a given HNA input stack of the HNA input stack partition, a given HNA off-chip run stack of the HNA off-chip run stack partition, a given HNA off-chip save buffer of the HNA off-chip save buffer partition, and a given HNA off-chip result buffer of the HNA off-chip result buffer partition.

42. The method of claim 41, further comprising at least one LMC and wherein a given LMC of the at least one LMC is configured to:

enable the at least one HNA processor to access the HNA packet data memory, HNA input stack partition, HNA off-chip instruction queue partition, HNA off-chip run stack partition, HNA off-chip save buffer partition, and the HNA off-chip result buffer partition via a coherent path; and

enable the at least one HNA processor to access the HNA off-chip graph memory via a non-coherent path.

43. The method of claim 24, wherein each HPU of the plurality of HPUs of the plurality of clusters of the plurality of super-clusters includes:

a node cache configured to cache one or more nodes from a super-cluster graph memory, an HNA on-chip graph memory, or an HNA off-chip graph memory;

a character class cache configured to cache one or more regular expression pattern character class definitions from a super-cluster character class memory;

a payload buffer configured to store a given payload from an HNA packet data memory, the at least one HNA instruction including an identifier for a location of the given payload in the HNA packet data memory;

a top of stack register configured to store a single HNA job;

a run stack configured to store multiple HNA jobs;

a unified memory configured to store first content of a save stack and second content of a match result buffer, the first content including one or more HNA jobs stored in the run stack and the second content including one or more final match results; and

an HNA processing core operatively coupled to the node cache, character class cache, payload buffer, top of stack register, run stack, and the unified memory, the HNA processing core configured to walk at least one per-pattern NFA with payload segments stored in the payload buffer to determine a match of the at least one regular expression pattern.

44. The method of claim 24, wherein:

each super-cluster further includes a super-cluster graph memory exclusive to a corresponding super-cluster;

the at least one HNA processor further includes an HNA on-chip graph memory shared by the plurality of super-clusters;

the method further comprises at least one system memory configured to include an HNA off-chip graph memory shared by the plurality of super-clusters; and

the given HPU selected is configured to walk nodes of a given per-pattern NFA of at least one per-pattern NFA with segments of a payload of the input stream based on the at least one HNA instruction assigned, the nodes walked stored in a node cache exclusive to the given HPU selected, the super-cluster graph memory, the HNA on-chip graph memory, the HNA off-chip graph memory, or a combination thereof.

45. The method of claim 24, wherein the plurality of HPUs of the plurality of clusters of the plurality of super-clusters form a resource pool of HPUs available to the HNA scheduler for selection to enable acceleration of the matching.