Engine architecture for processing finite automata

Patent metadata

Field	Value
Publication number	US-9785403-B2
Application number	US-201414325841-A
Country	US
Kind code	B2
Filing date	Jul 8, 2014
Priority date	Aug 30, 2013
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

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.

First claim

What is claimed is:

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.

Assignees

• Cavium Inc

Inventors

• Goyal Rajan
• Billa Satyanarayana Lakshmipathi
• Shanava Yossef
• Bouchard Gregg A
• Nakada Timothy Toshio

Classifications

• G06F16/24552 Primary

  Database cache management · CPC title

• G06F9/3885

  using a plurality of independent parallel functional units · CPC title

• G06F16/90344

  by using string matching techniques · CPC title

• G06F13/28 Primary

  using burst mode transfer, e.g. direct memory access {DMA}, cycle steal (G06F13/32 takes precedence) · CPC title

• H04L63/1408 Primary

  by monitoring network traffic (monitoring network traffic per se H04L43/00) · CPC title