Parallel pattern detection engine
First Claim
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 selecting the pattern in each of the M PUs 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 processing units;
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
42 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 selecting the pattern in each of the M PUs 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 processing units;
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13)
-
-
9. The PPDE of claim 9, 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.
-
14. A method of determining if any of N sequences of pattern occurs within a sequence of input data using a parallel pattern detection engine (PPDE) comprising the steps of:
-
a) loading the N sequences of pattern into M processing units (PUs), each of the M PUs having compare circuitry for comparing each of the sequence of input data, in parallel, to a selected pattern in each of the N sequences of pattern stored in the M PUs;
b) loading identification (ID) data into each of the M PUs, wherein the ID data determines an ID for each of the M PUs;
c) loading match mode data into each of the M PUs setting criteria for determining when conditions have been met for indicating that one of the N sequences of pattern has been detected in the sequence of input data;
d) coupling a first input data in parallel to each of the M PUs;
e) comparing the first input data to the selected pattern determined by an address pointer in each of the M PUs and generating a compare output in each of the M PUs within a same clock cycle;
f) modifying the value of the address pointer in each of the M PUs in response to a logic state of the corresponding compare output and an operation code stored with the selected pattern in each of the M PUs;
g) selecting a match ID from the ID data in response to a pattern match signal indicating one of the N sequences of pattern has been detected;
h) storing the match ID and match data corresponding to the match ID; and
i) repeating steps (a-g) until a last input data of the sequence of input data has been compared. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. 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 PPOEs, 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 the sequence of input data to a pattern stored in each of the M PUs and generating a compare output, wherein an address pointer selecting the pattern data in each of the M PUs is modified in response to a logic state of the compare output and an operation code stored with the pattern data;
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 processing units;
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. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. A method to recognize objects comprising:
-
providing a database of patterns representative of objects to be recognized;
storing an operation code with predefined sector of said database;
generating a data stream representative of unknown objects;
providing an address pointer to select patterns in said database;
correlating a pattern selected with a block of data from said data stream; and
generating a status signal based upon result of the correlation and the operation code stored with the selected pattern. - View Dependent Claims (34, 35, 36, 37, 38, 39, 40, 41)
-
-
42. A device comprising:
-
a memory;
a database of patterns stored in said memory;
a plurality of operation codes, with each one of said plurality of operation codes being associated with selected pattern stored in said memory;
a register for storing a sequence of input data;
a pointer to select patterns in said memory; and
a controller correlating data from said register with selected pattern from said database and issuing a status signal based upon result of the correlation and the operation code stored with said selected pattern.
-
Specification