Method and system for accelerated stream processing

• US 10,158,377 B2
• Filed: 01/12/2017
• Issued: 12/18/2018
• Est. Priority Date: 05/15/2008
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Ip Reservoir, LLC
• Inventors: Indeck, Ronald S., Indeck, David Mark, Singla, Naveen, White, Jason R.
• Primary Examiner(s): Ojha, Ajay
• Application Number:
  US15/404,794
• Publication Number:
  US 20170123866A1
• Time in Patent Office: 705 Days
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C

Abstract

Disclosed herein are methods and systems for hardware-accelerating various data processing operations in a rule-based decision-making system such as a business rules engine, an event stream processor, and a complex event stream processor. Preferably, incoming data streams are checked against a plurality of rule conditions. Among the data processing operations that are hardware-accelerated include rule condition check operations, filtering operations, and path merging operations. The rule condition check operations generate rule condition check results for the processed data streams, wherein the rule condition check results are indicative of any rule conditions which have been satisfied by the data streams. The generation of such results with a low degree of latency provides enterprises with the ability to perform timely decision-making based on the data present in received data streams.

Claims

1. A stream processing method:

streaming a plurality of data events through a member of the group consisting of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP), wherein the member includes a data processing pipeline, the pipeline including a plurality of parallel processing paths, the parallel processing paths including a first processing path and a second processing path in parallel with the first processing path;

within the first processing path, the member (1) filtering the streaming data events to generate a first reduced stream of the data events, and (2) performing at least one processing operation on the first reduced event stream to generate a first plurality of results for association with the first reduced event stream, wherein the member performs the filtering step and the at least one processing operation within the first processing path in a pipelined manner such that the member performs the at least one processing operation on the first reduced event stream within the first processing path while simultaneously performing the filtering step within the first processing path on new streaming events;

within the second processing path, the member (1) filtering the streaming data events to generate a second reduced stream of the data events, and (2) performing at least one processing operation on the second reduced event stream to generate a second plurality of results for association with the second reduced event stream, wherein the member performs the filtering step and the at least one processing operation within the second processing path in a pipelined manner such that the member performs the at least one processing operation on the second reduced event stream within the second processing path while simultaneously performing the filtering step within the second processing path on new streaming events; and

the member performing the steps within the first processing path in parallel with the steps within the second processing path.

2. The method of claim 1 wherein the at least one processing operation within the first processing path comprises at least one of a matching operation, a range check operation, a character check operation, and a derived value check operation.

3. The method of claim 2 wherein the at least one processing operation within the second processing path comprises at least one of a matching operation, a range check operation, a character check operation, and a derived value check operation.

4. The method of claim 1 wherein the at least one processing operation in at least one of the parallel processing paths comprises a windowing operation that caches data from a plurality of events in a memory to support complex event processing within the pipeline.

5. The method of claim 4 wherein the at least one processing path that performs the windowing operation further performs a join operation downstream from the windowing operation to join a plurality of windows of streaming events according to a join key.

6. The method of claim 5 wherein the join key comprises an approximate join key.

7. The method of claim 1 further comprising the pipeline enriching the streaming events with the first and second plurality of results.

8. The method of claim 1 wherein the streaming events comprise a plurality of fields, and wherein the filtering steps comprise the member selecting which of the plurality of fields are to be included in the reduced event streams.

9. The method of claim 1 further comprising the pipeline performing a path merging operation downstream from the first and second parallel processing paths to merge data from the first and second parallel processing paths into a common stream.

10. The method of claim 1 wherein the first and second plurality of results comprise a plurality of rule condition checking results.

11. A method for processing a bit stream, the method comprising:

receiving a bit stream at a coprocessor;

the coprocessor processing at least a portion of the bit stream against at least one rule condition, wherein the processing step comprises;

performing a hardware-accelerated rule condition check operation on the bit stream portion that compares the bit stream portion with a plurality of rule conditions; and

in response to the performing step resulting in a finding that the bit stream portion satisfies at least one of the rule conditions, generating a rule condition check result that is indicative of a satisfaction of the at least one rule condition; and

enhancing the bit stream with at least one bit corresponding to the rule condition checking result.

12. The method of claim 11 wherein the hardware-accelerated rule condition check operation comprises a hardware-accelerated matching operation.

13. The method of claim 12 wherein the hardware-accelerated matching operation comprises a hardware-accelerated exact word matching operation.

14. The method of claim 12 wherein the hardware-accelerated matching operation comprises a hardware-accelerated approximate word matching operation.

15. The method of claim 12 wherein the hardware-accelerated matching operation comprises a hardware-accelerated regular expression pattern matching operation.

16. The method of claim 12 further comprising wherein the processing step further comprises:

filtering the received bit stream using the coprocessor to thereby provide a reduced bit stream for use by the performing step.

17. The method of claim 16 wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and wherein the filtering step comprises passing only data corresponding to at least one pre-selected data field to the performing step.

18. The method of claim 12 wherein the hardware-accelerated rule condition check operation comprises a hardware-accelerated range check operation.

19. The method of claim 12 wherein the hardware-accelerated rule condition check operation comprises a hardware-accelerated threshold check operation.

20. The method of claim 11 wherein the bit stream comprises a plurality of records, and wherein the enhancing step comprises generating a new record for insertion in the bit stream, the new record being indicative of the generated rule condition check result.

21. The method of claim 11 wherein the bit stream comprises a plurality of records, and wherein the enhancing step comprises appending a bit string indicative of the generated rule condition check result to the record for which the rule condition check result was generated.

22. The method of claim 11 further comprising:

passing the enhanced bit stream out of the coprocessor for post-processing that is based at least in part on the generated rule condition check result.

23. The method of claim 22 further comprising:

performing the post-processing, wherein the post-processing comprises routing at least a portion of the enhanced bit stream to a particular destination within a network based at least in part on the generated rule condition check result.

24. The method of claim 11 wherein the processing step further comprises delivering the received bit stream to a plurality of parallel paths, and wherein the processing step comprises independently performing the processing step within a plurality of the paths.

25. The method of claim 11 wherein the processing step further comprises:

computing an aggregate value based at least in part upon the bit stream portion;

determining whether a rule condition is satisfied based at least in part upon the computed aggregate value; and

in response to a determination that that rule condition is satisfied, generating a rule condition check result indicative of that rule condition'"'"'s satisfaction.

26. The method of claim 11 wherein the processing step further comprises:

computing a derived value based at least in part upon the bit stream portion;

determining whether a rule condition is satisfied based at least in part upon the computed derived value; and

in response to a determination that that rule condition is satisfied, generating a rule condition check result indicative of that rule condition'"'"'s satisfaction.

27. The method of claim 11 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

28. A method for processing a bit stream, the method comprising:

receiving a bit stream at a coprocessor;

the coprocessor processing at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition checking result for the bit stream portion, the rule condition checking result being indicative of a rule condition being satisfied;

the coprocessor enhancing the bit stream with at least one bit corresponding to the rule condition checking result;

passing the enhanced bit stream out of the coprocessor for post-processing that is based at least in part on the generated rule condition check result; and

performing the post-processing, wherein the post-processing comprises (1) selecting a location within a network for storing at least a portion of the enhanced bit stream based at least in part on the generated rule condition check result and (2) storing that enhanced bit stream portion in the selected location.

29. The method of claim 28 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

30. A method for processing a bit stream, the method comprising:

receiving a bit stream at a coprocessor, wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value; and

the coprocessor processing at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition checking result for the bit stream portion, the rule condition checking result being indicative of a rule condition being satisfied; and

wherein the processing step further comprises (1) delivering the received bit stream to a plurality parallel paths, and (2) independently performing the processing step within a plurality of the paths, and wherein the independently performing step comprises;

within a first of the parallel paths, (1) filtering the bit stream to pass only data corresponding to at least one pre-selected data field, and (2) processing that passed data against at least one rule condition to thereby generate a rule condition check result for that passed data if that passed data satisfies that at least one rule condition; and

within a second of the parallel paths, (1) filtering the bit stream to pass only data corresponding to at least one pre-selected data field that is different than the at least one pre-selected data field of the first path, and (2) processing that passed data against at least one rule condition to thereby generate a rule condition check result for that passed data if that passed data satisfies that at least one rule condition.

31. The method of claim 30 further comprising merging data outputs for the plurality of parallel paths using the coprocessor.

32. The method of claim 31 further comprising delivering the received bit stream to the merging step via a bypass path, and wherein the merging step further comprises inserting the rule condition check result generated within the plurality of paths into the received bit stream at a plurality of locations.

33. The method of claim 30 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

34. A method for processing a bit stream, the method comprising:

receiving a bit stream at a coprocessor; and

the coprocessor processing at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition checking result for the bit stream portion, the rule condition checking result being indicative of a rule condition being satisfied, wherein the processing step comprises;

computing an aggregate value based at least in part upon the bit stream portion;

determining whether a rule condition is satisfied based at least in part upon the computed aggregate value; and

in response to a determination that that rule condition is satisfied, generating a rule condition check result indicative of that rule condition'"'"'s satisfaction;

storing the aggregate value in a memory; and

retrieving the aggregate value from the memory as additional bit stream portions are processed by the processing step.

35. The method of claim 34 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

36. A method for processing a bit stream, the method comprising:

receiving a bit stream at a coprocessor, wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value; and

the coprocessor processing at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition checking result for the bit stream portion, the rule condition checking result being indicative of a rule condition being satisfied, and wherein the processing step comprises;

filtering the bit stream to pass only data corresponding to at least one pre-selected data field;

performing a range check on the each field of the passed data to determine whether the passed data has a data value within a range of acceptable values corresponding to at least one range-based rule condition; and

in response to a determination that that at least one range-based rule condition is satisfied, generating a rule condition check result indicative of that range-based rule condition'"'"'s satisfaction.

37. The method of claim 36 further comprising:

enhancing the bit stream with at least one bit corresponding to the rule condition checking result.

38. The method of claim 37 wherein the coprocessor comprises a reconfigurable logic device.

39. The method of claim 38 wherein the reconfigurable logic device has firmware deployed thereon, wherein the firmware is configured to perform the processing step.

40. The method of claim 39 wherein the firmware is further configured to perform the enhancing step.

41. The method of claim 36 wherein each rule condition has a corresponding action, the method further comprising:

performing the action corresponding to a rule condition that is identified by the generated rule condition check result.

42. The method of claim 36 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

43. A method for processing a bit stream, the method comprising:

receiving a bit stream at a coprocessor; and

the coprocessor processing at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition checking result for the bit stream portion, the rule condition checking result being indicative of a rule condition being satisfied, and wherein the processing step comprises performing an approximate join operation with the coprocessor on data within the received bit stream.

44. The method of claim 43 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

45. A method for processing a bit stream, the method comprising:

receiving a bit stream at a coprocessor; and

the coprocessor processing at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition checking result for the bit stream portion, the rule condition checking result being indicative of a rule condition being satisfied, and wherein the processing step comprises performing a join operation with the coprocessor between data within the received bit stream and data stored in a database.

46. The method of claim 45 further comprising:

enhancing the bit stream with at least one bit corresponding to the rule condition checking result.

47. The method of claim 45 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

62. The system of claim 46 wherein the processor is configured to perform the post-processing, wherein the post-processing comprises a routing operation to route at least a portion of the enhanced bit stream to a particular destination within a network based at least in part on the generated rule condition check result.

48. A system for processing a bit stream, the system comprising:

a processor; and

a coprocessor in communication with the processor, wherein the coprocessor comprises a reconfigurable logic device, wherein the reconfigurable logic device has firmware deployed thereon;

wherein the coprocessor is configured to accept a bit stream;

wherein the firmware is configured to process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of the at least one rule condition being satisfied; and

wherein the coprocessor is further configured to enhance the bit stream with at least one bit corresponding to the rule condition check result.

49. The system of claim 48 wherein the firmware is further configured to enhance the bit stream with at least one bit corresponding to the rule condition check result.

50. A system for processing a bit stream, the system comprising:

a processor; and

a coprocessor in communication with the processor;

wherein the coprocessor is configured to (1) accept a bit stream, (2) process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied, and (3) enhance the bit stream with at least one bit corresponding to the rule condition check result; and

wherein, as part of the process operation, the coprocessor is further configured to (1) perform a rule condition check operation on the bit stream portion that compares the bit stream portion with a plurality of rule conditions, and (2) in response to finding a match between the bit stream portion and at least one of the rule conditions, generate a rule condition check result that is indicative of a satisfaction of the at least one rule condition.

51. The system of claim 50 wherein the rule condition check operation comprises a matching operation.

52. The system of claim 51 wherein the matching operation comprises an exact word matching operation.

53. The system of claim 51 wherein the matching operation comprises an approximate word matching operation.

54. The system of claim 51 wherein the matching operation comprises a regular expression pattern matching operation.

55. The system of claim 51 wherein the coprocessor is further configured to filter the accepted bit stream to thereby provide a reduced bit stream for use by the matching operation.

56. The system of claim 55 wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and wherein coprocessor is further configured to filter the accepted bit stream by passing only data corresponding to at least one pre-selected data field for use by the matching operation.

57. The system of claim 51 wherein the rule condition check operation comprises a range check operation.

58. The system of claim 51 wherein the rule condition check operation comprises a threshold check operation.

59. The system of claim 50 wherein the bit stream comprises a plurality of records, and wherein the coprocessor is further configured to enhance the bit stream by generating a new record for insertion in the bit stream, the new record being indicative of the generated rule condition check result.

60. The system of claim 50 wherein the bit stream comprises a plurality of records, and wherein the coprocessor is further configured to enhance the bit stream by appending a bit string indicative of the generated rule condition check result to the record for which the rule condition check result was generated.

61. The system of claim 50 wherein the coprocessor is further configured to pass the enhanced bit stream to the processor for post-processing that is based at least in part on the generated rule condition check result.

63. The system of claim 50 wherein the coprocessor is further configured to process bits within the accepted bit stream within a plurality of parallel paths, at least a plurality of the paths being configured to independently process at least a portion of the bit stream against a plurality of rule conditions.

64. The system of claim 50 wherein the coprocessor is further configured to:

compute an aggregate value based at least in part upon the bit stream portion;

determine whether a rule condition is satisfied based at least in part upon the computed aggregate value; and

in response to a determination that that rule condition is satisfied, generate a rule condition check result indicative of that rule condition'"'"'s satisfaction.

65. The system of claim 50 wherein the coprocessor is further configured to:

compute a derived value based at least in part upon the bit stream portion;

determine whether a rule condition is satisfied based at least in part upon the computed derived value; and

in response to a determination that that rule condition is satisfied, generate a rule condition check result indicative of that rule condition'"'"'s satisfaction.

66. The system of claim 50 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

67. A system for processing a bit stream, the system comprising:

a processor; and

a coprocessor in communication with the processor;

wherein the coprocessor is configured to (1) accept a bit stream, (2) process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied, and (3) pass the enhanced bit stream to the processor for post-processing that is based at least in part on the generated rule condition check result; and

wherein the processor is configured to perform the post-processing, wherein the post-processing comprises (1) an operation to select a location within a network for storing at least a portion of the enhanced bit stream based at least in part on the generated rule condition check result and (2) an operation to store that enhanced bit stream portion in the selected location.

68. The system of claim 67 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

69. A system for processing a bit stream, the system comprising:

a processor; and

a coprocessor in communication with the processor;

wherein the coprocessor is configured to (1) accept a bit stream, wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and (2) process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied; and

wherein, as part of the process operation, the coprocessor is further configured to process bits within the accepted bit stream within a plurality of parallel paths, at least a plurality of the paths being configured to independently process at least a portion of the bit stream against a plurality of rule conditions such that the coprocessor is further configured to;

within a first of the parallel paths, (1) filter the bit stream to pass only data corresponding to at least one pre-selected data field, and (2) process that passed data against at least one rule condition to thereby generate a rule condition check result for that passed data if that passed data satisfies that at least one rule condition; and

within a second of the parallel paths, (1) filter the bit stream to pass only data corresponding to at least one pre-selected data field that is different than the at least one pre-selected data field of the first path, and (2) process that passed data against at least one rule condition to thereby generate a rule condition check result for that passed data if that passed data satisfies that at least one rule condition.

70. The system of claim 69 wherein the coprocessor is further configured to perform a merge operation to merge data outputs for the plurality of parallel paths.

71. The system of claim 70 wherein one of the parallel paths comprises a bypass path over which the accepted bit stream is delivered to the merge operation, and wherein the merge operation is configured to insert data corresponding to the rule condition check results generated within the plurality of paths into the received bit stream at a plurality of locations.

72. The system of claim 69 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

73. A system for processing a bit stream, the system comprising:

a processor; and

a coprocessor in communication with the processor;

wherein the coprocessor is configured to (1) accept a bit stream, and (2) process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied;

wherein, as part of the process operation, the coprocessor is further configured to compute an aggregate value based at least in part upon the bit stream portion;

determine whether a rule condition is satisfied based at least in part upon the computed aggregate value; and

in response to a determination that that rule condition is satisfied, generate a rule condition check result indicative of that rule condition'"'"'s satisfaction; and

wherein the coprocessor is further configured to;

store the aggregate value in memory; and

retrieve the aggregate value from memory as additional bit stream portions are processed by the coprocessor.

74. The system of claim 73 wherein the coprocessor is further configured to enhance the bit stream with at least one bit corresponding to the rule condition checking result.

75. The system of claim 74 wherein the coprocessor comprises a reconfigurable logic device.

76. The system of claim 73 wherein each rule condition has a corresponding action, and wherein at least one of the group consisting of the processor and the coprocessor is configured to perform the action corresponding to a rule condition that is identified by the generated rule condition check result.

77. The system of claim 73 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

78. A system for processing a bit stream, the system comprising:

a processor; and

a coprocessor in communication with the processor;

wherein the coprocessor is configured to (1) accept a bit stream, wherein the bit stream comprises a plurality of records, each record having at least one data field, the at least one data field having a data value, and (2) process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied;

wherein, as part of the process operation, the coprocessor is further configured to;

filter the bit stream to pass only data corresponding to at least one pre-selected data field;

perform a range check on the each field of the passed data to determine whether the passed data has a data value within a range of acceptable values corresponding to at least one range-based rule condition; and

in response to a determination that that at least one range-based rule condition is satisfied, generate a rule condition check result indicative of that range-based rule condition'"'"'s satisfaction.

79. The system of claim 78 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

80. A system for processing a bit stream, the system comprising:

a processor; and

a coprocessor in communication with the processor;

wherein the coprocessor is configured to (1) accept a bit stream, and (2) process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied, and

wherein, as part of the process operation, the coprocessor is further configured to perform an approximate join operation on data within the accepted bit stream.

81. The system of claim 80 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).

82. A system for processing a bit stream, the system comprising:

a processor; and

a coprocessor in communication with the processor and a database;

wherein the coprocessor is configured to (1) accept a bit stream, and (2) process at least a portion of the bit stream against at least one rule condition to thereby generate a rule condition check result for the bit stream portion, the rule condition check result being indicative of a rule condition being satisfied; and

wherein, as part of the process operation, the coprocessor is further configured to perform a join operation between data within the accepted bit stream and data stored in the database.

83. The system of claim 82 wherein the coprocessor comprises at least one of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP).