Intelligent Data Storage and Processing Using FPGA Devices

• US 20120109849A1
• Filed: 01/06/2012
• Published: 05/03/2012
• Est. Priority Date: 05/23/2003
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Washington University In St Louis
• Inventors: Chamberlain, Roger D., Franklin, Mark Allen, Indeck, Ronald S., Cytron, Ron K., Cholleti, Sharath R.
• Granted Patent: US 8,751,452 B2
• Time in Patent Office: Days
• US Class Current: 705/36.R
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 17/00 Digital computing or data processing equipment or methods, specially adapted for specific functions information retrieval, database structures or file system structures therefor G06F16/00
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 21/76 in application-specific integrated circuits [ASIC] or field-programmable devices, e.g. field-programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 21/85 interconnection devices, e.g. bus-connected or in-line devices
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 9/44505 Configuring for program initiating, e.g. using registry, configuration files
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis

Abstract

A re-configurable logic device such as a field programmable gate array (FPGA) can be used to deploy a data processing pipeline, the pipeline comprising a plurality of pipelined data processing engines, the plurality of pipelined data processing engines including a data reduction engine, the plurality of pipelined data processing engines being configured to perform processing operations, wherein the pipeline comprises a multi-functional pipeline, and wherein the re-configurable logic device is further configured to controllably activate or deactivate each of the pipelined data processing engines in the pipeline in response to control instructions and thereby define a function for the pipeline, each pipeline function being the combined functionality of each activated pipelined data processing engine in the pipeline.

Claims

1. A data processing apparatus comprising:

a processing device for communicating with a computer system to offload a plurality of processing tasks from a processor within the computer system, wherein the processing device comprises a re-configurable logic device;

wherein the re-configurable logic device is configured to receive and process streaming data through a multi-functional pipeline deployed on the re-configurable logic device;

wherein the multi-functional pipeline comprises a plurality of pipelined data processing engines, each pipelined data processing engine being configured to (1) perform a processing operation on streaming data that it receives, and (2) be responsive to a control instruction that defines whether that pipelined data processing engine is an activated data processing engine or a deactivated data processing engine, wherein an activated data processing engine is configured to perform its processing operation on any received streaming data, and wherein a deactivated data processing engine remains in the pipeline but does not perform its processing operation on any received streaming data, the multi-functional pipeline thereby being configured to provide a plurality of different pipeline functions in response to control instructions that are configured to selectively activate and deactivate the pipelined data processing engines, each pipeline function being the combined functionality of each activated pipelined data processing engine in the pipeline at a given time; and

wherein the pipelined data processing engines comprise a data reduction engine.

2. The apparatus of claim 1 wherein the data reduction engine is configured to process streaming financial information to generate summarized financial information.

3. The apparatus of claim 2 wherein the streaming financial information comprises data representative of a plurality of stocks and their associated prices, wherein the data reduction engine comprises a matching stage and a downstream summarization stage, wherein the matching stage is configured to search within the streaming financial information to find matching stocks of interest with respect to at least one data key, and wherein the summarization stage is configured to summarize the matching stocks in an aggregate form.

4. The apparatus of claim 3 wherein the summarization stage is configured to compute a minimum price for the stock prices of a matching stock found by the search stage.

5. The apparatus of claim 4 wherein the summarization stage comprises:

a data shift register;

a data register configured to store a most recent minimum stock price; and

a comparator;

wherein the summarization stage is further configured to stream the stock prices for the matching stock through the data shift register;

wherein the comparator is configured to compare a current stock price in the data shift register with the stored most recent minimum stock price to determine which is lower; and

wherein the summarization stage is further configured to update the stored most recent minimum stock price in the data register with the current stock price in response to a determination by the comparator that the current stock price is lower.

6. The apparatus of claim 3 wherein the summarization stage is configured to compute a maximum price for the stock prices of a matching stock found by the search stage.

7. The apparatus of claim 6 wherein the summarization stage comprises:

a data shift register;

a data register configured to store a most recent maximum stock price; and

a comparator;

wherein the summarization stage is further configured to stream the stock prices for the matching stock through the data shift register;

wherein the comparator is configured to compare a current stock price in the data shift register with the stored most recent maximum stock price to determine which is higher; and

wherein the summarization stage is further configured to update the stored most recent maximum stock price in the data register with the current stock price in response to a determination by the comparator that the current stock price is higher.

8. The apparatus of claim 3 wherein the streaming financial information further comprises data representative of an associated time for each stock price, and wherein the summarization stage is configured to compute a latest price for the stock prices of a matching stock found by the search stage.

9. The apparatus of claim 8 wherein the summarization stage comprises:

a data shift register;

a first data register configured to store a most recent latest stock price;

a second data register configured to store a most recent time; and

a comparator;

wherein the summarization stage is further configured to stream the stock prices and associated times for the matching stock through the data shift register;

wherein the comparator is configured to compare a current time in the data shift register with the stored most recent time to determine which is later; and

wherein the summarization stage is further configured to update the stored most recent latest stock price in the data register with the current stock price in response to a determination by the comparator that the current time is later.

10. The apparatus of claim 3 wherein the streaming financial information further comprises data representative of an associated time for each stock price, and wherein the summarization stage is configured to simultaneously compute a minimum price, a maximum price and a latest price for the stock prices of a matching stock found by the search stage.

11. The apparatus of claim 10 wherein the summarization stage comprises:

a data shift register;

a first data register configured to store a most recent minimum stock price;

a second data register configured to store a most recent maximum stock price;

a third data register configured to store a most recent latest stock price;

a fourth data register configured to store a most recent time;

a first comparator;

a second comparator; and

a third comparator;

wherein the summarization stage is further configured to stream the stock prices and times for the matching stock through the data shift register;

wherein the first comparator is configured to compare the current stock price in the data shift register with the stored most recent minimum stock price to determine which is lower; and

wherein the summarization stage is further configured to update the stored most recent minimum stock price in the first data register with the current stock price in response to a determination by the first comparator that the current stock price is lower;

wherein the second comparator is configured to compare the current stock price in the data shift register with the stored most recent maximum stock price to determine which is higher;

wherein the summarization stage is further configured to update the stored most recent maximum stock price in the second data register with the current stock price in response to a determination by the second comparator that the current stock price is higher;

wherein the third comparator is configured to compare the current time in the data shift register with the stored most recent time to determine which is later; and

wherein the summarization stage is further configured to update the stored most recent latest stock price in the third data register with the current stock price in the data shift register in response to a determination by the third comparator that the current time is later.

12. The apparatus of claim 3 further comprising:

a data store in communication with the re-configurable logic device, the data store being configured to at least temporarily store the financial information; and

wherein the re-configurable logic device is further configured to read the financial information from the data store to thereby receive the financial information stream.

13. The apparatus of claim 12 wherein the data store comprises a mass storage medium.

14. The apparatus of claim 13 wherein the mass storage medium comprises a magnetic storage device.

15. The apparatus of claim 3 wherein the matching stage and the summarization stage are configured to perform their respective operations on different fields of the streaming financial information.

16. The apparatus of claim 3 wherein the matching stage is configured return, in response to finding a match with respect to the data key, a portion of the streaming financial information within a bounding field that encompasses the matching stock for processing by the summarization stage.

17. The apparatus of claim 3 wherein the matching engine comprises:

a compare register, the compare register having a plurality of cells configured to store elements of the data key;

a data shift register, the data shift register having a plurality of cells configured to store elements of the streaming financial information, wherein each data shift register cell has a corresponding compare register cell;

a fine-grained comparison logic device, the fine-grained comparison logic device being configured to perform an element-by-element comparison as between the financial information elements and data key elements stored within corresponding ones of the data shift register cells and compare register cells;

word-level comparison logic, the word-level comparison logic being configured to find the matching stocks based on the element-by-element comparison from the fine-grained comparison logic device; and

wherein the data shift register is configured to continuously shift elements of the financial information from one data shift register cell to the next.

18. The apparatus of claim 17 wherein the fine-grained comparison logic device comprises a plurality of cells, each fine-grained comparison logic cell being in communication with a compare register cell and at least one data shift register cell, and wherein the matching stage is further configured to route financial information elements from at least one of the data shift register cells to a plurality of different fine-grained comparison logic cells as the elements of the streaming financial information shift from one cell to the next within the data shift register to thereby support approximate matching.

19. The apparatus of claim 2 wherein the pipeline is configured to process the streaming financial information on a frame-by-frame basis.

20. The apparatus of claim 2 wherein the pipeline is configured to process the streaming financial information on a frameless basis.

21. The apparatus of claim 2 wherein the re-configurable logic device comprises a field programmable gate array (FPGA).

22. The apparatus of claim 2 further comprising the computer system.

23. The apparatus of claim 22 further comprising a system bus, the system bus interconnecting the computer system with the processing device.

24. The apparatus of claim 22 wherein the pipelined data processing engines further comprise a decryption engine.

25. A data processing method comprising:

receiving a plurality of control instructions at a processing device, the processing device in communication with a computer system over a bus, wherein the processing device comprises a re-configurable logic device configured to receive and process streaming data through a multi-functional pipeline deployed on the re-configurable logic device, the multi-functional pipeline comprising a plurality of pipelined data processing engines, each pipelined data processing engine being configured to (1) perform a processing operation on streaming data that it receives, and (2) be responsive to a control instruction that defines whether that pipelined data processing engine is an activated data processing engine or a deactivated data processing engine, wherein an activated data processing engine is configured to perform its processing operation on any received streaming data, and wherein a deactivated data processing engine remains in the pipeline but does not perform its processing operation on any received streaming data, the multi-functional pipeline thereby being configured to provide a plurality of different pipeline functions in response to control instructions that are configured to selectively activate and deactivate the pipelined data processing engines, each pipeline function being the combined functionality of each activated pipelined data processing engine in the pipeline at a given time, wherein the pipelined data processing engines comprise a data reduction engine; and

responsive to the received control instructions;

activating the data reduction engine, and

the activated data reduction engine processing streaming data to generate summarized data.

26. The method of claim 25 wherein the streaming data comprises streaming financial information, and wherein the processing step comprises the activated data reduction engine processing the streaming financial information to generate summarized financial information.

27. The method of claim 26 wherein the streaming financial information comprises data representative of a plurality of stocks and their associated prices, wherein the data reduction engine comprises a matching stage and a downstream summarization stage, and wherein the processing step comprises (1) the matching stage searching within the streaming financial information to find matching stocks of interest with respect to at least one data key, and (2) the summarization stage summarizing the matching stocks in an aggregate form.

28. The method of claim 27 wherein the summarizing step comprises the summarization stage computing a minimum price for the stock prices of a matching stock found by the searching step.

29. The method of claim 27 wherein the summarizing step comprises the summarization stage computing a maximum price for the stock prices of a matching stock found by the searching step.

30. The method of claim 27 wherein the streaming financial information further comprises data representative of an associated time for each stock price, and wherein the summarizing step comprises the summarization stage computing a latest price for the stock prices of a matching stock found by the searching step.

31. The method of claim 27 wherein the streaming financial information further comprises data representative of an associated time for each stock price, and wherein the summarizing step comprises the summarization stage simultaneously computing a minimum price, a maximum price and a latest price for the stock prices of a matching stock found by the searching step.

32. The method of claim 27 wherein the searching step and the summarizing step operate on different fields of the streaming financial information.

33. The method of claim 26 wherein the method further comprises receiving the streaming financial information from a data source.

34. The method of claim 33 wherein the data source comprises a magnetic storage device, and wherein the receiving step comprises reading the financial information from the magnetic storage device to thereby receive the financial information stream.

35. The method of claim 26 wherein the processing step comprises the data reduction engine processing the streaming financial information on a frame-by-frame basis.

36. The method of claim 26 wherein the performing step comprises the data reduction engine processing the streaming financial information on a frameless basis.

37. The method of claim 26 wherein the re-configurable logic device comprises a field programmable gate array (FPGA).

38. The method of claim 37 wherein the processing step comprises the data reduction engine generating the summarized financial information at hardware speeds.

39. A data processing method comprising:

within a computer system comprising a processor and a re-configurable logic device operating under control of the processor, streaming data through the re-configurable logic device for processing thereby, the re-configurable logic device comprising a multi-functional pipeline, the multi-functional pipeline comprising a control processor and a plurality of pipelined data processing engines, each of the pipelined data processing engines in the pipeline being configured to (1) receive streaming data and (2) perform a data processing operation on the received streaming data, wherein the pipelined data processing engines comprise a data reduction engine;

the control processor selectively activating and deactivating the pipelined data processing engines in the pipeline to achieve a desired pipeline function, each pipeline function being the combined functionality of the activated pipelined data processing engines in the pipeline, wherein the selectively activating and deactivating step comprises the control processor activating the data reduction engine; and

the activated data reduction engine processing streaming data to generate summarized data at hardware speeds.

40. The method of claim 39 wherein the streaming data comprises streaming financial information, and wherein the processing step comprises the activated data reduction engine processing the streaming financial information to generate summarized financial information at hardware speeds.