Method and apparatus for processing financial information at hardware speeds using FPGA devices

• US 8,069,102 B2
• Filed: 11/20/2006
• Issued: 11/29/2011
• Est. Priority Date: 05/21/2002
• 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 Kaplan
• Primary Examiner(s): Kyle; Charles
• Assistant Examiner(s): POLLOCK, GREGORY A
• Application Number:
  US11/561,615
• Publication Number:
  US 20070078837A1
• Time in Patent Office: 1,835 Days
• Field of Search: 705/35, 705/36.R, 705/36.T, 705/37
• US Class Current: 705/35
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus use decision logic deployed on a reconfigurable logic device to process a stream of financial information at hardware speeds. The decision logic can be configured to perform data reduction operations on the financial information stream. Examples of such data reductions operations include data processing operations to compute a latest stock price, a minimum stock price, and a maximum stock price.

Claims

1. A system for accelerated data reduction with respect to financial information, the system comprising:

at least one field programmable gate array (FPGA) having a hardware template deployed thereon for configuring the FPGA to perform a data reduction operation on streaming financial information, the hardware template deployed on the FPGA defining matching hardware logic and downstream summarization hardware logic that are resident on the FPGA;

wherein the matching hardware logic comprises a first data register configured to store a data key, and wherein the matching hardware logic is configured to (1) receive a stream of financial information, the financial information comprising a plurality of stock symbols and their associated stock prices, each stock price having an associated time, and (2) match the financial information against the data key to find matched data within the financial information, wherein the matched data comprises a plurality of stock prices and times for a stock;

wherein the summarization hardware logic comprises;

a data shift register, wherein the FPGA is further configured to stream the stock prices and times within the matched data through the data shift register;

a second data register configured to store a most recent minimum stock price for the stock of the matched data;

a third data register configured to store a most recent maximum stock price for the stock of the matched data;

a fourth data register configured to store a most recent latest stock price for the stock of the matched data;

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

a first comparator;

a second comparator; and

a third comparator;

wherein the first comparator is configured to, as the stock prices and times stream through the data shift register, 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 hardware logic 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, as the stock prices and times stream through the data shift register, 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 hardware logic 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, as the stock prices and times stream through the data shift register, compare the current time in the data shift register with the stored most recent time to determine which is later;

wherein the summarization hardware logic 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;

wherein the first, second, and third comparators are in a parallel orientation such that the first, second, and third comparators operate simultaneously with each other; and

wherein the matching hardware logic and the summarization hardware logic are configured in a pipelined orientation such that the matching hardware logic and the summarization hardware logic operate simultaneously with each other, the summarization hardware logic being configured to operate on matched data previously found by the matching hardware logic while the matching hardware logic is configured to operate on new streaming financial information, the matching hardware logic and the summarization hardware logic thereby being configured to simultaneously operate together to generate a running computation of the minimum price, the maximum price, and the latest price for the stock prices within the matched data on a streaming basis as the financial information streams through the FPGA.

2. The system of claim 1 wherein the matching hardware logic is further configured to perform an exact match operation between the stream of financial information and the data key such that the matched data comprises exactly matched data.

3. The system of claim 1 wherein the matching hardware logic is further configured to perform the match operation on a frame-by-frame basis.

4. The system of claim 1 wherein the matching hardware logic is further configured to perform the match operation on a frameless basis.

5. The system of claim 1 wherein the matching hardware logic is further configured to perform an approximate match operation between the stream of financial information and the data key such that the matched data comprises approximately matched data.

6. The system of claim 1 further comprising a network interface, the network interface for receiving the hardware template from a remote source via a network.

7. The system of claim 1 wherein the matching hardware logic and the summarization hardware logic are configured to operate at hardware processing speeds.

8. The system of claim 1 further comprising:

at least one data storage device in communication with the FPGA, the at least one data storage device being configured to at least temporarily store the financial information; and

wherein the FPGA is further configured to read the financial information from the at least one data storage device to thereby receive the financial information stream.

9. The system of claim 8 wherein the at least one data storage device comprises a mass storage medium.

10. The system of claim 1 wherein the first data register comprises a plurality of cells configured to store elements of the data key, and wherein the matching hardware logic further comprises:

a second data shift register, the second data shift register having a plurality of cells configured to store elements of the streaming financial information, wherein each second data shift register cell has a corresponding first data 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 second data shift register cells and first data register cells; and

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

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

11. The system of claim 10 wherein the fine-grained comparison logic device comprises a plurality of cells, each fine-grained comparison logic cell being in communication with a first data register cell and at least one second data shift register cell, and wherein the matching hardware logic is further configured to route financial information elements from at least one of the second 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 second data shift register to thereby support approximate matching.

12. The system of claim 1 further comprising a memory for storing the hardware template, wherein the FPGA is configured to receive the hardware template from the memory for loading onto the FPGA to thereby configure the FPGA for performing the data reduction operation on streaming financial information.

13. The system of claim 12 further comprising:

a processor that is in communication with the FPGA, wherein the processor is configured to execute a software program, the software program being configured to transform an inquiry into the hardware template and communicate the hardware template to the memory for loading onto the FPGA.

14. The system of claim 13 further comprising:

a system bus, wherein the FPGA is in communication with the system bus; and

wherein the processor is in communication with the FPGA via the system bus; and

wherein the FPGA is further configured to provide the computed minimum, maximum and latest stock prices to the system bus for access by the processor.

15. The system of claim 13 further comprising:

a cache, wherein the FPGA is in communication with the cache; and

wherein the processor is in communication with the cache; and

wherein the FPGA is further configured to provide the computed minimum, maximum and latest stock prices to the cache for access by the processor.

16. The system of claim 13 wherein the hardware template is configured to support a plurality of different word matches for the matching hardware logic without requiring that a new hardware template be loaded onto the FPGA, and wherein the software program is further configured to determine a new data key and communicate the new data key to the FPGA for loading into the first data register to thereby modify the matching hardware logic to search for the new data key within the streaming financial information.

17. The system of claim 13 wherein the memory is configured to store a plurality of pre-compiled hardware templates, each pre-compiled hardware template defining a different data processing operation to be performed by the FPGA, wherein at least one of the pre-compiled hardware templates comprises the hardware template for performing the data reduction operation on streaming financial information;

and

wherein the software program is further configured to, in response to the inquiry processing, select one of the stored pre-compiled hardware templates for communication from the memory to the FPGA to thereby transform the FPGA to perform the data processing operation defined by the selected pre-compiled hardware template.

18. A method for accelerated data reduction with respect to financial information, the method comprising:

receiving, by at least one field programmable gate array (FPGA), streaming financial information, the financial information comprising a plurality of stock symbols and their associated stock prices, each stock price having an associated time, the FPGA having a hardware template deployed thereon that configures the FPGA to perform a data reduction operation on streaming financial information, the hardware template deployed on the FPGA defining matching hardware logic and downstream summarization hardware logic that are resident on the FPGA;

storing a data key in a first data register, the first data register being a part of the matching hardware logic;

matching the financial information against the data key to find matched data within the financial information, wherein the matched data comprises a plurality of stock prices and times for a stock, the matching step being performed by the matching hardware logic;

streaming the stock prices and times within the matched data through a data shift register, the data shift register being a part of the summarization hardware logic;

storing a most recent minimum stock price for the stock of the matched data in a second data register;

storing a most recent maximum stock price for the stock of the matched data in a third data register;

storing a most recent latest stock price for the stock of the matched data in a fourth data register;

storing a most recent time in a fifth data register; and

as the stock prices and times stream through the data shift register, (i) comparing a current stock price in the data shift register with the stored most recent minimum stock price to determine which is lower using a first comparator, the first comparator being a part of the summarization hardware logic, (ii) updating the stored most recent minimum stock price with the current stock price if the minimum price comparing step results in a determination that the current stock price is lower, (iii) comparing the current stock price in the data shift register with the stored most recent maximum stock price to determine which is higher using a second comparator, the second comparator being a part of the summarization hardware logic, (iv) updating the stored most recent maximum stock price with the current stock price if the maximum price comparing step results in a determination that the current stock price is higher, (v) comparing a current time in the data shift register with the stored most recent time to determine which is later using a third comparator, the third comparator being a part of the summarization hardware logic, and (vi) updating the stored most recent latest stock price with the current stock price in the data shift register if the latest price comparing step results in a determination that the current time is later;

wherein the first, second, and third comparators are in a parallel orientation such that the minimum price comparing step, the maximum price comparing step, and the latest price comparing step operate simultaneously with respect to each other; and

wherein the matching hardware logic and the summarization hardware logic are configured in a pipelined orientation such that the matching step and the comparing steps are performed simultaneously with each other, the comparing steps operating on matched data previously found by the matching step while the matching step operates on new streaming financial information, the matching hardware logic and the summarization hardware logic thereby operating together simultaneously to generate a running computation of the minimum price, the maximum price, and the latest price for the stock prices within the matched data on a streaming basis as the financial information streams through the FPGA.

19. The method of claim 18 wherein the matching step comprises the matching hardware logic performing an exact match operation between the streaming financial information and the data key such that the matched data comprises exactly matched data.

20. The method of claim 18 wherein the matching step comprises the matching hardware logic performing the matching step on a frame-by-frame basis.

21. The method of claim 18 wherein the matching step comprises the matching hardware logic performing the matching step on a frameless basis.

22. The method of claim 18 wherein the matching step comprises the matching hardware logic performing an approximate match operation between the streaming financial information and the data key such that the matched data comprises approximately matched data.

23. The method of claim 18 further comprising:

a network interface receiving the hardware template from a remote source via a network; and

loading the received hardware template onto the FPGA to thereby configure the FPGA for performing the data reduction operation on streaming financial information.

24. The method of claim 18 wherein the FPGA performs the method steps at hardware processing speeds.

25. The method of claim 18 wherein the receiving step comprises:

the FPGA reading the financial information from a data storage device to thereby receive the stream of financial information.

26. The method of claim 25 wherein the data storage device comprises a mass storage medium.

27. The method of claim 18 further comprising:

loading the data key into the first data register, the first data register having a plurality of cells in which elements of the data key are stored;

the FPGA (i) loading the streaming financial information into a second data shift register, the second data shift register being a part of the matching hardware logic, the second data shift register having a plurality of cells in which elements of the streaming financial information are stored, wherein each second data shift register cell has a corresponding first data register cell, and (ii) streaming the financial information elements through the second data shift register cells;

wherein the matching step comprises the matching hardware logic (i) performing an element-by-element comparison as between the financial information elements and data key elements stored within corresponding ones of the second data shift register cells and the first data register cells using a fine-grained comparison logic device, the fine-grained comparison logic device being a part of the matching hardware logic, and (ii) responsive to the comparison by the fine-grained comparison logic device, finding the matched data using word-level comparison logic, the word-level comparison logic device being a part of the matching hardware logic; and

wherein the matching hardware logic performs the matching step continuously as the elements of the streaming financial information shift from one cell to the next within the second data shift register.

28. The method of claim 27 wherein the fine-grained comparison logic device comprises a plurality of cells, each fine-grained comparison logic cell being in communication with a first data register cell and at least one second data shift register cell, and wherein the matching step comprises the matching hardware logic routing financial information elements from at least one of the second 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 second data shift register to thereby support approximate matching.

29. The method of claim 18 further comprising:

storing the hardware template in a memory;

the FPGA receiving the hardware template from the memory; and

loading the received hardware template onto the FPGA to thereby configure the FPGA for performing the data reduction operation on streaming financial information.

30. The method of claim 29 further comprising:

executing a software program on a processor that is in communication with the FPGA, wherein the executing step comprises the processor processing an inquiry to transform the inquiry into the hardware template;

communicating the hardware template to the memory; and

loading the communicated hardware template from the memory onto the FPGA.

31. The method of claim 30 further comprising:

the FPGA communicating the computed minimum, maximum and latest stock prices to a system bus; and

reading the communicated minimum, maximum and latest stock prices with a processor from the system bus.

32. The method of claim 30 further comprising:

the FPGA communicating the computed minimum, maximum and latest stock prices to a cache; and

reading the communicated minimum, maximum and latest stock prices with a processor from the cache.

33. The method of claim 30 wherein the hardware template is configured to support a plurality of different word matches for the matching step without requiring that a new hardware template be loaded onto the FPGA, wherein the executing step comprises the processor processing an inquiry to determine a new data key, the method further comprising:

communicating the new data key to the FPGA; and

loading the new data key into the first data register to thereby modify the matching step to search for the new data key within the streaming financial information.

34. The method of claim 30 further comprising:

storing a plurality of pre-compiled hardware templates in the memory, each pre-compiled hardware template defining a different data processing operation to be performed by the FPGA, wherein at least one of the pre-compiled hardware templates comprises the hardware template for performing the data reduction operation on the streaming financial information; and

wherein the executing step comprises the processor processing an inquiry to select one of the stored pre-compiled hardware templates for communication from the memory to the FPGA to thereby transform the FPGA to perform the data processing operation defined by the selected pre-compiled hardware template.