Method and system for accelerated stream processing

Patent metadata

Field	Value
Publication number	US-10158377-B2
Application number	US-201715404794-A
Country	US
Kind code	B2
Filing date	Jan 12, 2017
Priority date	May 15, 2008
Publication date	Dec 18, 2018
Grant date	Dec 18, 2018

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.

First claim

What is claimed is:

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 comp

Assignees

• Ip Reservoir Llc

Inventors

• Indeck Ronald S
• Indeck David Mark
• Singla Naveen
• White Jason R

Classifications

• G06F15/7867 Primary

  with reconfigurable architecture · CPC title

• G06F16/24568

  Data stream processing; Continuous queries · CPC title

• G06F16/24544

  Join order optimisation · CPC title

• G06F9/542

  Event management; Broadcasting; Multicasting; Notifications · CPC title

• G06N5/025 Primary

  Extracting rules from data · CPC title