Engine architecture for processing finite automata

• US 10,466,964 B2
• Filed: 09/13/2017
• Issued: 11/05/2019
• 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): Metzger, Michael J
• Application Number:
  US15/703,638
• Publication Number:
  US 20180004483A1
• Time in Patent Office: 783 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. An apparatus comprising:

at least one hyper non-deterministic automata (HNA) processor specialized for non-deterministic finite automata (NFA) processing, the at least one HNA processor including;

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

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

an HNA scheduler, the HNA scheduler configured to select a given HPU of the plurality of HPUs of the plurality of clusters 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.

2. The apparatus of claim 1, wherein the apparatus further comprises a plurality of super-clusters, each super-cluster including a corresponding plurality of clusters of the plurality of clusters and a super-cluster graph memory exclusive to a corresponding super-cluster, the super-cluster graph memory accessible to a corresponding plurality of HPUs of the 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 apparatus 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 apparatus of claim 3, wherein the super-cluster graph memory and the at least one super-cluster character class memory are unified.

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

6. The apparatus of claim 1, wherein:

the apparatus further comprises a plurality of super-clusters, each super-cluster including a corresponding plurality of clusters of the plurality of clusters; and

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 the 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 apparatus of claim 1, wherein the apparatus further comprises:

a plurality of super-clusters, each super-cluster including a corresponding plurality of clusters of the plurality of clusters; and

at least one Central Processing Unit (CPU) core operatively coupled to the at least one HNA processor, the at least one HNA processor configured to offload pattern matching operations from the at least one CPU core, the at least one CPU core configured to select 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 apparatus 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 apparatus 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 apparatus 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 apparatus 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 apparatus of claim 1, wherein the apparatus further comprises a plurality of super-clusters, each super-cluster including a corresponding plurality of clusters of the plurality of clusters, and 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 apparatus of claim 12, wherein:

the apparatus further comprises at least one CPU core operatively coupled to the at least one HNA processor and the at least one HNA is configured to offload pattern matching operations from the at least one CPU core;

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 apparatus 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, 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 apparatus of claim 1, wherein the at least one HNA instruction is a first at least one HNA instruction and the apparatus further comprises:

at least one CPU core operatively coupled to the at least one HNA processor;

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 apparatus 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 apparatus 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 apparatus 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;

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 apparatus 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 apparatus of claim 1, wherein each HPU of the plurality of HPUs of the plurality of 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 apparatus of claim 1, wherein the apparatus further comprises a plurality of super-clusters, each super-cluster including a corresponding plurality of clusters of the plurality of clusters, and 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 apparatus 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 apparatus of claim 1, wherein the given HPU is 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 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 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:

including a plurality of clusters in at least one hyper non-deterministic automata (HNA) processor specialized for non-deterministic finite automata (NFA) processing, each cluster of the plurality of clusters including a plurality of HNA processing units (HPUs);

storing at least one HNA instruction in an HNA on-chip instruction queue; and

selecting, by an HNA scheduler, a given HPU of the plurality of HPUs of the plurality of clusters and assigning 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.

25. The method of claim 24, further comprising:

including a plurality of super-clusters in the at least one HNA processor;

including, in each super-cluster, a corresponding plurality of clusters of the plurality of clusters and 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

storing, in the super-cluster graph memory, 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, further comprising:

including, in each super-cluster, at least one super-cluster character class memory exclusive to a corresponding super-cluster; and

storing, statically, in each at least one super-cluster character class memory, regular expression pattern character class definitions.

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, further comprising sharing the at least one super-cluster character class memory by a corresponding plurality of HPUs of a corresponding plurality of clusters of the corresponding super-cluster.

29. The method of claim 24, further comprising:

including a plurality of super-clusters in the at least one HNA processor, each super-cluster including a corresponding plurality of clusters of the plurality of clusters;

including, in each super-cluster, at least one super-cluster character class memory, each at least one super-cluster character class memory exclusive to a given cluster of the corresponding plurality of clusters of a corresponding super-cluster and shared by a corresponding plurality of HPUs of the given cluster; and

storing, statically, in each at least one super-cluster character class memory, regular expression pattern character class definitions.

30. The method of claim 24, further comprising:

operatively coupling the at least one HNA processor to at least one Central Processing Unit (CPU) core, the at least one HNA processor configured to offload pattern matching operations from the at least one CPU core;

including a plurality of super-clusters in the at least one HNA processor, each super-cluster including a corresponding plurality of clusters of the plurality of clusters; and

selecting, by the at least one CPU core, 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, further comprising associating the graph identifier with a given per-pattern NFA of a plurality of per-pattern NFAs and wherein restricting the super-cluster selection includes determining 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, further comprising:

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

selecting, by the HNA scheduler, 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

wherein selecting the at least one super-cluster of the plurality of super-clusters is 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 selecting the given HPU from the restricted set of HPUs is based on a round robin schedule for HPUs in the restricted set of HPUs.

34. The method of claim 32, wherein selecting the given HPU from the restricted set of HPUs is based on instantaneous loading of each HPU in the restricted set of HPUs.

35. The method of claim 24, further comprising:

including a plurality of super-clusters in the at least one HNA processor, each super-cluster including a corresponding plurality of clusters of the plurality of clusters and a super-cluster graph memory exclusive to a corresponding super-cluster; and

storing, in each super-cluster graph memory, 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, further comprising:

operatively coupling the at least one HNA processor to at least one CPU core, the at least one HNA processor configured to offload pattern matching operations from the at least one CPU core;

providing, by the at least one CPU core, 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;

selecting, by the HNA scheduler, 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

selecting, by the HNA scheduler, the given HPU from the plurality of HPUs of the plurality of clusters based on a second round robin schedule for the plurality of HPUs of the plurality of clusters, instantaneous loading of the plurality of HPUs of the plurality of clusters, or a combination thereof.

37. The method of claim 24, further comprising:

including, in the at least one HNA processor, an HNA on-chip graph memory accessible to the plurality of HPUs of the plurality of clusters; and

storing, in the HNA on-chip graph memory, 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:

operatively coupling at least one system memory the at least one HNA processor;

including, in the at least one system memory, an HNA off-chip instruction queue and an HNA off-chip graph memory;

storing, in the HNA off-chip instruction queue, 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

storing, in the HNA off-chip graph memory, 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:

operatively coupling at least one Local Memory Controller (LMC) to the at least one HNA processor and the at least one system memory; and

configuring a given LMC of the at least one LMC 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, further comprising:

including, in the at least one system memory, an HNA packet data memory; and

storing, in the HNA packet data memory, 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:

operatively coupling at least one LMC to the at least one HNA processor and the at least one system memory;

including, in the at least one system memory, an HNA input stack partition and storing, in the at least one HNA input stack, at least one HNA input job for at least one HPU of the plurality of HPUs of the plurality of clusters;

including, in the at least one system memory, an HNA off-chip run stack partition and storing 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 storing at least one run-time HNA job for the at least one HPU;

including, in the at least one system memory, an HNA off-chip save buffer partition extending storage of at least one on-chip save buffer, each at least one on-chip save buffer storing the at least one run-time HNA job for the at least one HPU based on detecting a payload boundary; and

including, in the at least one system memory, an HNA off-chip result buffer partition storing 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:

operatively coupling at least one LMC to the at least one HNA processor;

enabling, by a given LMC of the at least one LMC, 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

enabling, by the given LMC, 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, further comprising:

including, in each HPU of the plurality of HPUs of the plurality of clusters, a node cache, a character class cache, a payload buffer, a top of stack register, a run stack, a unified memory, and an HNA processing core operatively coupled to the node cache;

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

caching one or more regular expression pattern character class definitions from a super-cluster character class memory in the character class cache;

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

storing a single HNA job in the top of stack register;

storing multiple HNA jobs in the run stack;

storing first content of a save stack and second content of a match result buffer in the unified memory, 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

operatively coupling the HNA processing core to the node cache, character class cache, payload buffer, top of stack register, run stack, and the unified memory, and walking, by the HNA processing core, 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:

including a plurality of super-clusters in the at least one HNA processor, each super-cluster including a corresponding plurality of clusters of the plurality of clusters and a super-cluster graph memory exclusive to a corresponding super-cluster;

including, in the at least one HNA processor, an HNA on-chip graph memory;

sharing the HNA on-chip graph memory and an HNA off-chip graph memory by the plurality of super-clusters;

storing nodes of a given per-pattern NFA of at least one per-pattern NFA in the HNA on-chip graph memory, the HNA off-chip graph memory, or a combination thereof; and

walking, by the given HPU selected, the nodes with segments of a payload of the input stream based on the at least one HNA instruction assigned and storing the nodes walked 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 form a resource pool of HPUs available to the HNA scheduler for selection to enable acceleration of the matching.