PATTERN MATCHING ACCELERATOR

• US 20120203761A1
• Filed: 02/08/2011
• Published: 08/09/2012
• Est. Priority Date: 02/08/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Biran, Giora, Hagleitner, Christoph, Heil, Timothy H., Hoover, Russell D., Van Lunteren, Jan
• Granted Patent: US 8,478,736 B2
• Time in Patent Office: Days
• US Class Current: 707/713
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

A pattern matching accelerator (PMA) for assisting software threads to find the presence and location of strings in an input data stream that match a given pattern. The patterns are defined using regular expressions that are compiled into a data structure comprised of rules subsequently processed by the PMA. The patterns to be searched in the input stream are defined by the user as a set of regular expressions. The patterns to be searched are grouped in pattern context sets. The sets of regular expressions which define the pattern context sets are compiled to generate a rules structure used by the PMA hardware. The rules are compiled before search run time and stored in main memory, in rule cache memory within the PMA or a combination thereof. For each input character, the PMA executes the search and returns the search results.

Claims

1. A pattern matching apparatus, comprising:

a data engine operative to receive search commands each comprising input data and one or more patterns to be searched; and

an algorithm engine in communication with said data engine, said algorithm engine operative to execute said search commands and attempt to match said one or more patterns to said input data corresponding thereto and to generate match results therefrom.

2. The apparatus according to claim 1, wherein said pattern contexts comprise one or more sets of regular expressions.

3. The apparatus according to claim 1, wherein said algorithm engine comprises:

a rules cache for storing a limited set of pattern based rules providing fast access to said rules by said algorithm engine; and

a main memory coupled to said rules cache for storing pattern based rules not currently loaded into said rules cache.

4. The apparatus according to claim 1, further comprising a pattern compiler operative to compile said patterns into rules readable by said algorithm engine.

5. The apparatus according to claim 1, further comprising an upload manager operative to manage the storage of rules in memory coupled to said algorithm engine, said rules generated from compiled pattern contexts.

6. The apparatus according to claim 1, further comprising a interconnect for facilitating data communications between said data engine and said algorithm engine.

7. The apparatus according to claim 1, wherein said data engine comprises a command queue operative to receive said search commands.

8. The apparatus according to claim 1, wherein said data engine comprises a plurality of command units, each said command unit comprising one or more search units operative to arbitrate for a search lane in said algorithm engine that contains rules required for executing a particular search command.

9. The apparatus according to claim 1, wherein said algorithm engine comprises a plurality of lanes, each lane comprising a plurality of search engines.

10. The apparatus according to claim 9, wherein each said search engine comprises a programmable finite state machine.

11. The apparatus according to claim 1, wherein said algorithm engine comprises a local results processor (LRP) operative to receive and analyze partial match data to aid in processing complex pattern contexts.

12. The apparatus according to claim 1, wherein said algorithm engine is operative to determine the starting location of a matching pattern in said input data.

13. The apparatus according to claim 1, wherein said algorithm engine is operative to determine the ending location of a matching pattern in said input data.

14. The apparatus according to claim 1, wherein said search command comprises a first pointer to an input data buffer, one or more identifiers of pattern contexts to be searched and a second pointer to an output buffer for storing pattern matching search results.

15. A method of pattern matching, said method comprising the steps of:

receiving search commands, each said search command including input data and one or more patterns to be searched;

performing pattern matching on the input data associated with a search command in accordance with the one or more patterns corresponding thereto; and

generating match results in response to said pattern matching.

16. The method according to claim 15, wherein said patterns comprise one or more sets of regular expressions.

17. The method according to claim 15, further comprising compiling user defined pattern contexts to generate rules readable by a hardware search engine.

18. The method according to claim 15, further comprising managing dynamic loading of rules into memory coupled to search engines for performing said pattern matching, said rules generated from compiled pattern contexts.

19. A pattern matching apparatus, comprising:

a plurality of data engines, each data engine operative to receive search commands each comprising input data and one or more pattern contexts to be searched;

said data engine comprising;

a command queue for storing received search commands;

a plurality of command units for coordinating and arbitrating the execution of said search commands;

a plurality of algorithm engines in communication with said data engines, each algorithm engine operative to execute said search commands and attempt to match said one or more patterns to said input data corresponding thereto and to generate match results therefrom; and

algorithm engine comprising;

a plurality of search lanes, each said search lane comprising a plurality of search engines; and

memory coupled to each search engine, said memory for storing patterns to be searched within the input data associated with a search command assigned to a particular search engine.

20. The apparatus according to claim 19, wherein said memory comprises a hardware managed cache.

21. The apparatus according to claim 19, wherein said memory comprises a hardware and software managed cache.

22. The apparatus according to claim 19, further comprising a pattern compiler operative to compile said pattern contexts into rules readable by said search engines.

23. The apparatus according to claim 19, further comprising an upload manager operative to manage the storage of rules in memory coupled to each search engine.

24. The apparatus according to claim 23, wherein said upload manager is operative to update the rules in a local store and in a main memory during processing of a search operation.

25. The apparatus according to claim 23, wherein said upload manager is operative to define a group of search lanes that can serve the search operations whereby said command units performs queuing between search units looking for the same pool of lanes.

26. The apparatus according to claim 19, wherein said algorithm engine comprises a local results processor (LRP) operative to receive and analyze partial match data to aid in processing complex pattern contexts.

27. The apparatus according to claim 19, wherein each data engine is operative to use any algorithm engine.

28. The apparatus according to claim 19, wherein each algorithm engine is operative to switch from one data engine to another in the event a data engine is busy.

29. The apparatus according to claim 19, further comprising means for powering down one or more data engines.

30. The apparatus according to claim 19, wherein said command units are operative to manage assignment of input commend requests to data engines in accordance with the availability of data engines and one or more constraints placed on the completion in order of related search commands.

31. A method of pattern matching, comprising the steps of:

compiling said one or more patterns into a plurality of rules readable by a hardware search engine;

receiving search commands, each said search command including a first pointer to an input data buffer, one or more pattern contexts to be searched and a second pointer to an output buffer;

executing a pattern search on the input data buffer associated with a search command in accordance with said plurality of compiled rules corresponding thereto; and

generating match results in response to said pattern search and storing said match results in said output buffer.

32. The method according to claim 31, further comprising managing dynamic loading of said rules into memory coupled to said search engines for performing said pattern matching.