PARALLEL PATTERN MATCHING ON MULTIPLE INPUT STREAMS IN A DATA PROCESSING SYSTEM

• US 20090307175A1
• Filed: 06/10/2008
• Published: 12/10/2009
• Est. Priority Date: 06/10/2008
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Francesco, Iorio, Van Lunteren, Jan
• Application Number:
  US12/136,386
• Publication Number:
  US 20090307175A1
• Time in Patent Office: Days
• US Class Current: 706/48
• CPC Class Codes: G06F 9/4498 Finite state machines

Abstract

A method, system and computer program product for performing pattern matching in parallel for a plurality of input streams. The method includes calculating a memory address in a translation table responsive to a current input value, a current state and current state information. A transition rule is retrieved from the transition rule table at the memory address, the transition rule including a test input value, a test current state, and next state information. It is determined if the current input value and the current state match the test input value and the test current state. The current state information is updated with the next state information in response to determining that the current input value and the current state match the test input value and the test current state. The current state information is updated with contents of a default transition rule in response to determining that the current input value and the current state do not match the test input value and the test current state.

Claims

1. A method of pattern matching in a data processing system, the method comprising:

performing in parallel for a plurality of input streams;

calculating a memory address in a translation table responsive to a current input value, a current state and current state information;

retrieving a transition rule from the transition rule table at the memory address, the transition rule including a test input value, a test current state, and next state information;

determining if the current input value and the current state match the test input value and the test current state;

updating the current state information with the next state information in response to determining that the current input value and the current state match the test input value and the test current state; and

updating the current state information with contents of a default transition rule in response to determining that the current input value and the current state do not match the test input value and the test current state.

2. The method of claim 1 wherein the transition rule is located in a transition rule table and the current state information includes a table address for the start of the transition rule table.

3. The method of claim 1 wherein the current state information includes a mask for selecting the transition rule from a plurality of transition rules located at the memory address.

4. The method of claim 1 wherein the next state information includes a next state table address, a next state, a next state mask and a result flag.

5. The method of claim 1 wherein the transition rule is located in a transition rule table that spans a plurality of vector registers.

6. The method of claim 5 wherein the test input value for the transition rule is located in a different vector register than the test current state for the transition rule.

7. The method of claim 1 wherein the input streams are received from a plurality of state machines operating in parallel.

8. The method of claim 1 wherein the default transition rule is located in a default transition rule table that spans a plurality of vector registers.

9. A system for pattern matching, the system comprising:

a transition rule table for storing transition rules;

a plurality of state registers storing current states of a plurality of state machines;

an address generator including circuitry for receiving input current input values and for generating addresses corresponding to transition rules in response to the current input values and the current states;

a mechanism operating in parallel on multiple generated addresses for retrieving transition rules corresponding to each of the generated addresses, the retrieving from the transition rule table; and

a rule selector for updating the current states in response to the retrieved transition rules.

10. The system of claim 9 wherein the address generator further includes circuitry for receiving a current table address and a mask and the generating addresses is further responsive to the current table address and the mask.

11. The system of claim 9 further comprising a plurality of vector registers, wherein the transition rule table is stored in the vector registers.

12. The system of claim 11 wherein each transition rule includes a plurality of data fields, and two or more of the data fields for a transition rule are stored in different vector registers.

13. The system of claim 9 further comprising a default rule table for storing default transition rules, wherein the mechanism further retrieves default transition rules from the default rule table in response to the current input values and the current states, and the updating the current states is further responsive to the retrieved default transition rules.

14. A computer program product for pattern matching in a data processing system, the computer program product comprising:

a tangible storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising;

performing in parallel for a plurality of input streams;

calculating a memory address in a transition rule table responsive to a current input value, a current state and current state information;

retrieving a transition rule from the transition rule table at the memory address, the transition rule including a test input value, a test current state, and next state information;

determining if the current input value and the current state match the test input value and the test current state;

updating the current state information with the next state information in response to determining that the current input value and the current state match the test input value and the test current state; and

updating the current state information with contents of a default transition rule in response to determining that the current input value and the current state do not match the test input value and the test current state.

15. The computer program product of claim 14 wherein the transition rule is located in a transition rule table and the current state information includes a table address for the start of the transition rule table.

16. The computer program product of claim 14 wherein the current state information includes a mask for selecting the transition rule from a plurality of transition rules located at the memory address.

17. The computer program product of claim 14 wherein the next state information includes a next state table address, a next state, a next state mask and a result flag.

18. The computer program product of claim 14 wherein the transition rule is located in a transition rule table that spans a plurality of vector registers.

19. The computer program product of claim 18 wherein the test input value for the transition rule is located in a different vector register than the test current state for the transition rule.

20. The computer program product of claim 14 wherein the input streams are received from a plurality of state machines operating in parallel.