Parallel pattern detection engine

• US 7,243,165 B2
• Filed: 01/14/2004
• Issued: 07/10/2007
• Est. Priority Date: 01/14/2004
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Kravec, Kerry A., Saidi, Ali G., Slyfield, Jan M., Tannhof, Pascal R.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): MARTINEZ, DAVID E
• Application Number:
  US10/757,187
• Publication Number:
  US 20050154802A1
• Time in Patent Office: 1,273 Days
• Field of Search: None
• US Class Current: 710/1
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

A parallel pattern detection engine (PPDE) comprise multiple processing units (PUs) customized to do various modes of pattern recognition. The PUs are loaded with different patterns and the input data to be matched is provided to the PUs in parallel. Each pattern has an Opcode that defines what action to take when a particular data in the input data stream either matches or does not match the corresponding data being compared during a clock cycle. Each of the PUs communicate selected information so that PUs may be cascaded to enable longer patterns to be matched or to allow more patterns to be processed in parallel for a particular input data stream.

Claims

1. A parallel pattern detection engine (PPDE) integrated circuit (IC) for detecting one or more patterns in a sequence of input data comprising:

an input/output (I/O) interface for coupling data into and out of the PPDE;

M processing units (PUs), each of the M PUs having compare circuitry for comparing each of the sequence of input data to a pattern stored in each of the M PUs and generating a compare output, wherein an address pointer points to the pattern in each of the M PUs, wherein the address pointer is modified in response to a logic state of the compare output and an operation code stored with the pattern;

an input bus for coupling the sequence of input data to each of the M PUs in parallel;

an output bus coupled to the I/O interface for sending output data to the I/O interface;

control circuitry coupled to the I/O interface and coupling control data on a control data bus and identification (ID) on an ID bus to each of the M PUs;

ID selection circuitry for selecting a match ID from ID data identifying the M PUs in response to a pattern match signal and match mode data, wherein the match ID and match data corresponding to the match ID are saved in a temporary register as the output data; and

cascade circuitry coupled from each of the M PUs to one or more adjacent PUs within the M PUs for selectively coupling chain data between one or more groups of two or more adjacent PUs selected from the M PUs in response to the control data.

2. The PPDE of claim 1 further comprising an input buffer coupled to the I/O interface for receiving and writing input data as parallel data at a write address.

3. The PPDE of claim 2 further comprising a multiplexer coupled to the input bus and the input buffer for sequentially coupling single data from the input buffer data to the input bus, wherein parallel data are selected using a read address.

4. The PPDE of claim 1 further comprising an output buffer coupled to the output bus and to the temporary register for receiving and writing output data to the output buffer at a write address and coupling output data to the output bus corresponding to a read address.

5. The PPDE of claim 1, wherein each of M processing units (PUs) has an ID register for storing a unique ID sent from the control circuitry.

6. The PPDE of claim 1, wherein each of M processing units (PUs) has a control register for storing the match mode data, wherein the match mode data determines criteria for generating the match signal and the match data.

7. The PPDE of claim 1, wherein each of the M PUs has a memory register array for storing a sequence of the pattern and corresponding operation codes addressed by an address register indexed by the address pointer.

8. The PPDE of claim 1, wherein the cascade circuitry enables the stored patterns of two or more PUs to be chained together as a single pattern using the chain data.

9. The PPDE of claim 8, wherein the chain data inhibits indexing the pointer of one PU until an adjacent PU coupled with the cascade circuitry has compared a last pattern to an input data.

10. The PPDE of claim 1, wherein the compare circuitry in each of the M PUs completes a compare of an input data to a selected pattern and generates a compare output and modifies the address pointer in the same cycle of a clock signal.

11. The PPDE of claim 1, wherein the match mode data for each of the M PUs sets a match mode comprising:

an exact match mode, wherein a pattern match indicates that the sequence of pattern matches a sequence of input data exactly;

a longest match mode wherein a pattern match indicates that a particular sequence of pattern corresponding to the match ID has the largest number of data in a sequence that compared to a sequence of data in the sequence of input data wherein the match data indicates the value of the largest number;

a maximum match mode, wherein a pattern match indicates that a particular sequence of pattern bytes corresponding to the match ID has the largest number of data that compared in a broken sequence that compared to a broken sequence of input data, wherein the match data indicates the value of the largest number; and

a fuzzy match mode, wherein a pattern match indicates that a particular sequence of pattern corresponding to the match ID has the closest match to the sequence of input data as determined by a distance value, wherein the match data indicates the distance value.

12. The PPDE of claim 1, wherein the operation codes are selected from a set of operation codes comprising:

a match operation code indicating that the address pointer is incremented if the compare output is a logic one and the address pointer is reloaded to its initial value if the compare output is a logic zero;

an inverse operation code indicating that the address pointer is to be incremented if the compare output is a logic zero and the address pointer is reloaded to its initial value if the compare output is a logic one;

a wildcard operation code indicating that the address pointer is incremented if the compare output is a logic zero or a logic one;

a multiple wild card operation code indicating that the address pointer is to be held if the compare output is a logic zero otherwise the address pointer is incremented; and

a last operation code indicating that the address pointer is frozen until the matching process receives a reset if the compare output is a logic one and the address pointer is reloaded to its initial value if the compare output is a logic zero.

13. The PPDE of claim 1, wherein bits of the selected pattern are masked by a mask data stored in a mask register when the selected pattern is compared to an input data, the mask data indicating which bits of the selected pattern are not compared.

14. A data processing system comprising:

a central processing unit (CPU);

a random access memory (RAM);

one or more parallel pattern detection engines (PPDEs); and

a bus coupling the CPU, RAM, and the one or more PPDEs, wherein each of the PPDEs has an input/output (I/O) interface for coupling data into and out of the PPDE;

M processing units (PUs), each of the M PUs having compare circuitry for comparing each of a, sequence of input data to a pattern stored in each of the M PUs and generating a compare output, wherein an address pointer points to the pattern in each of the M PUs, wherein the address pointer is modified in response to a logic state of the compare output and an operation code stored with the pattern;

an input bus for coupling the sequence of input data to each of the M PUs in parallel;

an output bus coupled to the I/O interface for sending output data to the I/O interface;

control circuitry coupled to the I/O interface and coupling control data on a control data bus and identification (ID) on an ID bus to each of the M PUs;

ID selection circuitry for selecting a match ID from ID data identifying the M PUs in response to a pattern match signal and match mode data, wherein the match ID and match data corresponding to the match ID are saved in a temporary register as the output data; and

cascade circuitry coupled from each of the M PUs to one or more adjacent PUs within the M PUs for selectively coupling chain data between one or more groups of two or more adjacent PUs selected from the M PUs in response to the control data.

15. The data processing system of claim 14, wherein each of M processing units (PUs) has an ID register for storing a unique ID sent from the control circuitry.

16. The data processing system of claim 14, wherein each of the M PUs has a memory register array for storing a sequence of the pattern and corresponding operation codes addressed by an address register indexed by the address pointer.

17. The data processing system of claim 14, wherein the cascade circuitry enables the stored patterns of two or more PUs to be chained together as a single pattern using the chain data.

18. The data processing system of claim 17, wherein the chain data inhibits indexing the pointer of one PU until an adjacent PU coupled with the cascade circuitry has compared a last pattern to an input data.

19. The data processing system of claim 14, wherein the compare circuitry in each of the M PUs completes a compare of an input data to a selected pattern and generates a compare output and modifies the address pointer in the same cycle of a clock signal.

20. The data processing system of claim 14, wherein the match mode data for each of the M PUs sets a match mode comprising:

an exact match mode, wherein a pattern match indicates that the sequence of pattern matches a sequence of input data exactly;

a longest match mode wherein a pattern match indicates that a particular sequence of pattern corresponding to the match ID has the largest number of data in a sequence that compared to a sequence of data in the sequence of input data wherein the match data indicates the value of the largest number;

a maximum match mode, wherein a pattern match indicates that a particular sequence of pattern corresponding to the match ID has the largest number of data that compared to a broken sequence of input data, wherein the match data indicates the value of the largest number; and

a fuzzy match mode, wherein a pattern match indicates that a particular sequence of pattern corresponding to the match ID has the closest match to the sequence of input data as determined by a distance value, wherein the match data indicates the distance value.

21. The data processing system of claim 20, wherein the operation codes are selected from a set of operation codes comprising:

a match operation code indicating that the address pointer is incremented if the compare output is a logic one and the address pointer is reloaded to its initial value if the compare output is a logic zero;

an inverse operation code indicating that the address pointer is to be incremented if the compare output is a logic zero and the address pointer is reloaded to its initial value if the compare output is a logic one;

a wildcard operation code indicating that the address pointer is incremented if the compare output is a logic zero or a logic one;

a multiple wildcard operation code indicating that the address pointer is to be held if the compare output is a logic zero otherwise the address pointer is incremented; and

a last operation code indicating that the address pointer is frozen until the matching process receives a reset if the compare output is a logic one and the address pointer is reloaded to its initial value if the compare output is a logic zero.

22. The data processing system of claim 20, wherein bits of the selected pattern are masked by a mask data stored in a mask register when the selected pattern is compared to an input data, the mask data indicating which bits of the selected pattern are not compared.