Method and system for accelerated stream processing

• US 10,411,734 B2
• Filed: 12/17/2018
• Issued: 09/10/2019
• 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:
  US16/222,054
• Publication Number:
  US 20190123764A1
• Time in Patent Office: 267 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 system for applying parallelism to process streaming data at low latency and high throughput, the streaming data comprising data arranged in a plurality of fields, the system comprising:

at least one 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 a processing pipeline is deployed on the at least one member for receiving and processing the streaming data, the processing pipeline including a plurality of parallel paths, each of a plurality of the parallel paths including pipelined logic for performing different processing operations on the streaming data;

wherein each of a plurality of the parallel paths includes field selection logic that filters which fields of the streaming data that downstream pipelined logic in that parallel path will process, wherein a plurality of the parallel paths include field selection logic that filter for different fields of the streaming data so that the processing pipeline is thereby configured to parallel process different fields of the streaming data in different parallel paths with different processing operations.

2. The system of claim 1 wherein the processing pipeline further comprises field parsing logic upstream from the parallel paths, wherein the field parsing logic identifies where boundaries between the fields of the streaming data are located.

3. The system of claim 2 wherein the streaming data further comprises a plurality of records, wherein a plurality of the records include the data arranged in the fields, and wherein the field parsing logic further comprises record parsing logic that identifies where boundaries between the records in the streaming data are located.

4. The system of claim 2 wherein the processing pipeline further comprises join logic downstream from the parallel paths, wherein the join logic merges data from the parallel paths into a consolidated data stream.

5. The system of claim 4 wherein the parallel paths include a bypass path that delivers the received streaming data to the join logic.

6. The system of claim 1 wherein at least one of the parallel paths includes range check logic as one of the different processing operations.

7. The system of claim 1 wherein at least one of the parallel paths includes character check logic as one of the different processing operations.

8. The system of claim 1 wherein at least one of the parallel paths includes threshold check logic as one of the different processing operations.

9. The system of claim 1 wherein at least one of the parallel paths includes matching logic as one of the different processing operations.

10. The system of claim 9 wherein the matching logic comprises regular expression pattern matching logic.

11. The system of claim 1 wherein the at least one member comprises the reconfigurable logic device.

12. The system of claim 11 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA).

13. The system of claim 1 wherein the at least one member comprises the GPU.

14. The system of claim 1 wherein the at least one member comprises the CMP.

15. The system of claim 1 wherein the at least one member comprises the reconfigurable logic device and the GPU.

16. The system of claim 1 wherein the parallel paths augment the streaming data with a plurality of flags indicative of a plurality of data quality conditions.

17. The system of claim 16 further comprising:

a database;

a processor that (1) manages a flow of streaming data into the at least one member and a flow of processed streaming data out of the at least one member, and (2) selectively processes and loads at least a portion of the processed streaming data into the database based on the data quality condition flags.

18. The system of claim 17 further comprising:

a network interface through which the processor receives the streaming data.

19. The system of claim 18 wherein the network interface receives the streaming data from a plurality of different data sources.

45. The system of claim 6 wherein at least one other of the parallel paths includes character check logic as one of the different processing operations.

46. The system of claim 6 wherein at least one other of the parallel paths includes threshold check logic as one of the different processing operations.

47. The system of claim 6 wherein at least one other of the parallel paths includes matching logic as one of the different processing operations.

48. The system of claim 7 wherein at least one other of the parallel paths includes threshold check logic as one of the different processing operations.

49. The system of claim 7 wherein at least one other of the parallel paths includes matching logic as one of the different processing operations.

50. The system of claim 8 wherein at least one other of the parallel paths includes matching logic as one of the different processing operations.

20. A method for applying parallelism to process streaming data at low latency and high throughput, the streaming data comprising data arranged in a plurality of fields, the method comprising:

receiving the streaming data at a processing pipeline deployed on at least one 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 processing pipeline includes a plurality of parallel paths, each of a plurality of the parallel paths including field selection logic and downstream pipelined logic; and

processing the streaming data through the processing pipeline, wherein the processing step comprises;

for each of a plurality of the parallel paths, (1) the field selection logic filtering which fields of the streaming data that the downstream pipelined logic in that parallel path will process, and (2) the downstream logic performing a plurality of different processing operations on the filtered streaming data so that the processing pipeline thereby parallel processes different fields of the streaming data in different parallel paths with different processing operations.

21. The method of claim 20 wherein the processing pipeline further comprises field parsing logic upstream from the parallel paths, the method further comprising the field parsing logic identifying where boundaries between the fields of the streaming data are located.

22. The method of claim 21 wherein the streaming data further comprises a plurality of records, wherein a plurality of the records include the data arranged in the fields, wherein the identifying step further comprises the field parsing logic identifying where boundaries between the records in the streaming data are located.

23. The method of claim 21 further comprising:

merging data from the parallel paths into a consolidated data stream downstream from the parallel paths.

24. The method of claim 23 wherein the parallel paths include a bypass path that delivers the received streaming data to the merging step.

25. The method of claim 20 wherein at least one of the parallel paths includes range check logic as one of the different processing operations.

26. The method of claim 25 wherein at least one other of the parallel paths includes character check logic as one of the different processing operations.

27. The method of claim 25 wherein at least one other of the parallel paths includes threshold check logic as one of the different processing operations.

28. The method of claim 25 wherein at least one other of the parallel paths includes matching logic as one of the different processing operations.

29. The method of claim 20 wherein at least one of the parallel paths includes character check logic as one of the different processing operations.

30. The method of claim 29 wherein at least one other of the parallel paths includes threshold check logic as one of the different processing operations.

31. The method of claim 29 wherein at least one other of the parallel paths includes matching logic as one of the different processing operations.

32. The method of claim 20 wherein at least one of the parallel paths includes threshold check logic as one of the different processing operations.

33. The method of claim 32 wherein at least one other of the parallel paths includes matching logic as one of the different processing operations.

34. The method of claim 20 wherein at least one of the parallel paths includes matching logic as one of the different processing operations.

35. The method of claim 34 wherein the matching logic comprises regular expression pattern matching logic.

36. The method of claim 20 wherein the at least one member comprises the reconfigurable logic device.

37. The method of claim 36 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA).

38. The method of claim 20 wherein the at least one member comprises the GPU.

39. The method of claim 20 wherein the at least one member comprises the CMP.

40. The method of claim 20 wherein the at least one member comprises the reconfigurable logic device and the GPU.

41. The method of claim 20 further comprising the parallel paths augmenting the streaming data with a plurality of flags indicative of a plurality of data quality conditions.

42. The method of claim 41 further comprising:

a processor managing a flow of streaming data into the at least one member and a flow of processed streaming data out of the at least one member; and

the processor selectively processing and loading at least a portion of the processed streaming data into a database based on the data quality condition flags.

43. The method of claim 42 further comprising:

the processor receiving the streaming data via a network interface.

44. The method of claim 43 further comprising:

the network interface receiving the streaming data from a plurality of different data sources.