High speed processing of financial information using FPGA devices

• US 8,407,122 B2
• Filed: 03/31/2011
• Issued: 03/26/2013
• Est. Priority Date: 06/19/2006
• Status: Active Grant

• Current Assignee: Exegy Incorporated
• Original Assignee: Exegy Incorporated
• Inventors: Parsons, Scott, Taylor, David E., Schuehler, David Vincent, Franklin, Mark A., Chamberlain, Roger D.
• Primary Examiner(s): Borlinghaus, Jason M
• Application Number:
  US13/076,906
• Publication Number:
  US 20110178911A1
• Time in Patent Office: 726 Days
• Field of Search: None
• US Class Current: 705/35
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis

Abstract

Methods and systems for processing financial market data using reconfigurable logic are disclosed. Various functional operations to be performed on the financial market data can be implemented in firmware pipelines to accelerate the speed of processing. Also, a combination of software logic and firmware logic can be used to efficiently control and manage the high speed flow of financial market data to and from the reconfigurable logic.

Claims

1. A method for processing a plurality of financial market data messages, each message corresponding to a financial instrument and comprising financial market data for its corresponding financial instrument, the method comprising:

storing a plurality of first memory financial instrument records in a first memory at a plurality of first memory addresses, each first memory financial instrument record corresponding to a financial instrument and comprising a plurality of fields for storing financial market data for their corresponding financial instruments;

storing a plurality of second memory financial instrument records in a second memory at a plurality of second memory addresses, each second memory financial instrument record corresponding to a financial instrument and comprising pointer information for locating a first memory financial instrument record in the first memory that corresponds to the same financial instrument; and

processing streaming data corresponding to a plurality of the messages through a reconfigurable logic device, the processed data comprising (1) a plurality of symbol identifiers for the messages'"'"' corresponding financial instruments, and (2) a plurality of message fields having financial market data for the messages'"'"' corresponding financial instruments, the reconfigurable logic device comprising a plurality of pipelined data processing blocks deployed in firmware logic on the reconfigurable logic device, the pipelined data processing blocks comprising (1) an address resolution block, (2) a record retrieval block downstream from the address resolution block, and (3) a field updating block downstream from the record retrieval block, and wherein the processing step comprises;

the address resolution block (1) retrieving a plurality of second memory financial instrument records from the second memory based on the symbol identifiers, the retrieved second memory financial instrument records corresponding to the financial instruments which correspond to the symbol identifiers, and (2) processing the retrieved second memory financial instrument records to resolve the first memory addresses corresponding to the pointer information in the retrieved second memory financial instrument records;

the record retrieval block retrieving a plurality of first memory financial instrument records from the first memory based on the resolved first memory addresses; and

the field updating block generating a plurality of updates for a plurality of the fields of the retrieved first memory financial instrument records based on the financial market data in a plurality of the message fields for the messages corresponding to the financial instruments which correspond to the retrieved first memory financial instrument records; and

wherein the address resolution block, the record retrieval block, and the field updating block perform their respective steps simultaneously with respect to each other in a pipelined fashion.

2. The method of claim 1 further comprising:

communicating data representative of the generated updates from the reconfigurable logic device to customer-supplied application software via an application programming interface (API); and

the application software further processing the communicated data.

31. The method of claim 1 wherein the reconfigurable logic device further comprises a firmware application module (FAM) pipeline, the FAM pipeline comprising a symbol mapping FAM and a last value cache (LVC) updating FAM downstream from the symbol mapping FAM;

wherein the LVC updating FAM comprises the address resolution block, the record retrieval block, and the field updating block; and

wherein the processing step further comprises the symbol mapping FAM (1) receiving at least a plurality of financial market data messages corresponding to financial instruments for which there is a record in the first and second memories, each received financial market data message comprising a string for identifying that message'"'"'s corresponding financial instrument, and (2) mapping each string to an address in the second memory where the second memory financial instrument record corresponding to the financial instrument identified by that string, the mapped addresses comprising the symbol identifiers for use by the address resolution block to retrieve the second memory financial instrument records; and

wherein the LVC updating FAM and the symbol mapping FAM perform their respective steps simultaneously with respect to each other in a pipelined fashion.

32. The method of claim 1 wherein the first memory financial instrument records comprise a plurality of regional financial instrument records and a plurality of composite financial instrument records, each regional financial instrument record corresponding to a financial instrument and comprising financial market data that is specific to a particular exchange on which its corresponding financial instrument is traded, each composite financial instrument record corresponding to a financial instrument and comprising financial market data that is general to all exchanges on which its corresponding financial instrument is traded;

wherein the second financial instrument records corresponding to financial instruments that are traded on multiple exchanges comprise pointer information for the regional and composite financial instrument records;

wherein the streaming data further comprises a plurality of exchange identifiers for the messages; and

wherein the field updating block comprises a plurality of regional update engines and a plurality of composite update engines; and

wherein the processing step further comprises;

the address resolution block resolving a plurality of first memory addresses where the regional and composite financial instrument records for the financial instruments corresponding to a plurality of retrieved second memory financial instrument records are stored based on the symbol identifiers and the exchange identifiers; and

the regional and composite update engines generating, in parallel, a plurality of regional and composite field updates for the retrieved first memory financial instrument records.

33. The method of claim 32 further comprising:

storing a plurality of regional list blocks in the first memory at a plurality of first memory addresses, each regional list block corresponding to a financial instrument that is traded on multiple exchanges and comprising (1) a global exchange identifier for each exchange on which the corresponding financial instrument is traded, and (2) pointer information, in association with the global exchange identifiers, to the regional financial instrument records for the corresponding financial instruments; and

wherein the processing step further comprises the address resolution block processing the regional block lists to determine the pointer information associated with the global exchange identifiers that match the messages'"'"' exchange identifiers.

34. The method of claim 33 wherein the address resolution block comprises a plurality of pipelined sub-blocks, the sub-blocks comprising first sub-block, a second sub-block downstream from the first sub-block, a third sub-block downstream from the second sub-block, and a fourth sub-block downstream from the third sub-block;

and

wherein the processing steps further comprise;

the first sub-block issuing a stream of read commands to the second memory to retrieve the second memory financial instrument records based on the symbol identifiers;

the second sub-block (1) processing the second memory financial instrument records returned from the second memory in response to the second memory read commands, and (2) issuing a stream of read commands to the first memory to retrieve the regional list blocks corresponding to the processed second memory financial instrument records;

the third sub-block (1) processing the regional list blocks returned from the first memory in response to the first memory read commands and (2) resolving the pointer information for the regional financial instrument records corresponding to the messages; and

the fourth sub-block outputting the first memory addresses for the regional and composite financial instrument records corresponding to the retrieved second memory financial instrument records and the retrieved regional list blocks; and

wherein the first, second, third, and fourth sub-blocks perform their respective steps simultaneously with respect to each other in a pipelined fashion.

35. The method of claim 32 further comprising:

storing data representative of the retrieved composite financial instrument records in a composite record buffer;

storing financial market data representative of the messages in a message buffer;

storing data representative of the retrieved regional financial instrument records in a regional record buffer;

the regional update engines reading from the message buffer and the regional record buffer to generate the regional field updates; and

the composite update engines reading from the message buffer and the composite record buffer to generate the composite field updates.

36. The method of claim 1 wherein the first memory is external to the reconfigurable logic device.

37. The method of claim 36 wherein the second memory is external to the reconfigurable logic device.

38. The method of claim 36 wherein the second memory is internal to the reconfigurable logic device.

39. The method of claim 1 wherein the first memory is internal to the reconfigurable logic device.

40. The method of claim 1 wherein the second memory is external to the reconfigurable logic device.

41. The method of claim 1 wherein the second memory is internal to the reconfigurable logic device.

42. The method of claim 1 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA), and wherein the address resolution block, the record retrieval block, and the field updating block perform their respective steps at hardware processing speeds.

3. A device for processing a plurality of streaming financial market data messages, each message corresponding to a financial instrument and comprising financial market data for its corresponding financial instrument, the device comprising:

a first memory configured to store a plurality of first memory financial instrument records at a plurality of first memory addresses, each first memory financial instrument record corresponding to a financial instrument and comprising a plurality of fields for storing financial market data for their corresponding financial instruments;

a second memory configured to store a plurality of second memory financial instrument records at a plurality of second memory addresses, each second memory financial instrument record corresponding to a financial instrument and comprising pointer information for locating a first memory financial instrument record in the first memory that corresponds to the same financial instrument; and

a reconfigurable logic device configured to process data corresponding to a plurality of the streaming messages, the processed data comprising (1) a plurality of symbol identifiers for the messages'"'"' corresponding financial instruments, and (2) a plurality of message fields having financial market data for the messages'"'"' corresponding financial instruments, the reconfigurable logic device comprising a plurality of pipelined data processing blocks deployed in firmware logic on the reconfigurable logic device, the pipelined data processing blocks comprising;

an address resolution block;

a record retrieval block downstream from the address resolution block; and

a field updating block downstream from the record retrieval block;

wherein the address resolution block is configured to (1) retrieve a plurality of second memory financial instrument records from the second memory based on the symbol identifiers, the retrieved second memory financial instrument records corresponding to the financial instruments which correspond to the symbol identifiers, and (2) process the retrieved second memory financial instrument records to resolve the first memory addresses corresponding to the pointer information in the retrieved second memory financial instrument records;

wherein the record retrieval block is configured to retrieve a plurality of first memory financial instrument records from the first memory based on the resolved first memory addresses; and

wherein the field updating block is configured to generate a plurality of updates for a plurality of the fields of the retrieved first memory financial instrument records based on the financial market data in a plurality of the message fields for the messages corresponding to the financial instruments which correspond to the retrieved first memory financial instrument records; and

wherein the address resolution block, the record retrieval block, and the field updating block are configured to operate simultaneously with respect to each other in a pipelined fashion.

4. The device of claim 3 further comprising:

an application programming interface (API) and customer-supplied application software in communication with the reconfigurable logic device, and wherein the customer-supplied application software is configured to (1) receive data representative of the generated updates from the reconfigurable logic device via the API and (2) further process the received data.

5. The device of claim 3 further comprising a third memory, the third memory comprising a cache memory configured to store a plurality of cached financial instrument records at a plurality of third memory addresses, each cached financial instrument record corresponding to a financial instrument and comprising financial market data for its corresponding financial instrument, and wherein the reconfigurable logic device is further configured to cache the retrieved first memory financial instrument records in the third memory.

6. The device of claim 5 wherein the pipelined data processing blocks further comprise a cache determination block downstream from the address resolution block and upstream from the record retrieval block, the cache determination block configured to (1) process the resolved first memory addresses for the retrieved second memory financial instrument records to determine whether a most up-to-date record for the financial instrument corresponding to each retrieved second memory financial instrument record is located in the first memory or the third memory, and (2) provide the record retrieval block with addresses in the first and third memories where the most up-to-date records for the financial instruments corresponding to the retrieved second memory financial instruments are stored;

wherein the record retrieval block is further configured to retrieve a plurality of third memory financial instrument records from the third memory based on the third memory addresses provided by the cache determination block; and

wherein the address resolution block, the cache determination block, the record retrieval block, and the field updating block are configured to operate simultaneously with respect to each other in a pipelined fashion.

7. The device of claim 6 wherein the pipelined data processing blocks further comprise a record updating block downstream from the field updating block, the record updating block configured to update the first memory in accordance with the generated updates;

and

wherein the address resolution block, the cache determination block, the record retrieval block, the field updating block, and the record updating block are configured to operate simultaneously with respect to each other in a pipelined fashion.

8. The device of claim 6 further comprising a plurality of processing buffers, wherein the record retrieval block is further configured to load the retrieved first and third memory financial instrument records into the processing buffers, wherein the field updating block is configured to read from the processing buffers to determine the financial instrument records for which the updates are to be generated, and wherein the third memory and the processing buffers are located in the same memory space.

9. The device of claim 5 wherein the first memory financial instrument records comprise a plurality of regional financial instrument records and a plurality of composite financial instrument records, each regional financial instrument record corresponding to a financial instrument and comprising financial market data that is specific to a particular exchange on which its corresponding financial instrument is traded, each composite financial instrument record corresponding to a financial instrument and comprising financial market data that is general to all exchanges on which its corresponding financial instrument is traded;

wherein the second financial instrument records corresponding to financial instruments that are traded on multiple exchanges comprise pointer information for the regional and composite financial instrument records;

wherein the processed data further comprises a plurality of exchange identifiers for the messages;

wherein the address resolution block is further configured to resolve a plurality of first memory addresses where the regional and composite financial instrument records for the financial instruments corresponding to a plurality of retrieved second memory financial instrument records are stored based on the symbol identifiers and the exchange identifiers; and

wherein the field updating block comprises a plurality of regional update engines and a plurality of composite update engines that are configured to generate, in parallel, a plurality of regional and composite field updates for the retrieved first memory financial instrument records.

10. The device of claim 9 wherein the first memory is further configured to store a plurality of regional list blocks at a plurality of first memory addresses, each regional list block corresponding to a financial instrument that is traded on multiple exchanges and comprising (1) a global exchange identifier for each exchange on which the corresponding financial instrument is traded, and (2) pointer information, in association with the global exchange identifiers, to the regional financial instrument records for the corresponding financial instruments, and wherein the address resolution block is further configured to process the regional block lists to determine the pointer information associated with the global exchange identifiers that match the messages'"'"' exchange identifiers.

11. The device of claim 5 wherein the third memory is internal to the reconfigurable logic device.

12. The device of claim 3 wherein the reconfigurable logic device further comprises a firmware application module (FAM) pipeline, the FAM pipeline comprising a symbol mapping FAM and a last value cache (LVC) updating FAM downstream from the symbol mapping FAM;

wherein the LVC updating FAM comprises the address resolution block, the record retrieval block, and the field updating block;

wherein the symbol mapping FAM is configured to (1) receive at least a plurality of financial market data messages corresponding to financial instruments for which there is a record in the first and second memories, each received financial market data message comprising a string for identifying that message'"'"'s corresponding financial instrument, and (2) map each string to an address in the second memory where the second memory financial instrument record corresponding to the financial instrument identified by that string, the mapped addresses comprising the symbol identifiers for use by the address resolution block to retrieve the second memory financial instrument records; and

wherein the LVC updating FAM and the symbol mapping FAM are configured to operate simultaneously with respect to each other in a pipelined fashion.

13. The device of claim 3 wherein the first memory financial instrument records comprise a plurality of regional financial instrument records and a plurality of composite financial instrument records, each regional financial instrument record corresponding to a financial instrument and comprising financial market data that is specific to a particular exchange on which its corresponding financial instrument is traded, each composite financial instrument record corresponding to a financial instrument and comprising financial market data that is general to all exchanges on which its corresponding financial instrument is traded;

wherein the second financial instrument records corresponding to financial instruments that are traded on multiple exchanges comprise pointer information for the regional and composite financial instrument records;

wherein the processed data further comprises a plurality of exchange identifiers for the messages; and

wherein the address resolution block is further configured to resolve a plurality of first memory addresses where the regional and composite financial instrument records for the financial instruments corresponding to a plurality of retrieved second memory financial instrument records are stored based on the symbol identifiers and the exchange identifiers; and

wherein the field updating block comprises a plurality of regional update engines and a plurality of composite update engines that are configured to generate, in parallel, a plurality of regional and composite field updates for the retrieved first memory financial instrument records.

14. The device of claim 13 wherein the first memory is further configured to store a plurality of regional list blocks at a plurality of first memory addresses, each regional list block corresponding to a financial instrument that is traded on multiple exchanges and comprising (1) a global exchange identifier for each exchange on which the corresponding financial instrument is traded, and (2) pointer information, in association with the global exchange identifiers, to the regional financial instrument records for the corresponding financial instruments, and wherein the address resolution block is further configured to process the regional block lists to determine the pointer information associated with the global exchange identifiers that match the messages'"'"' exchange identifiers.

15. The device of claim 14 wherein the address resolution block comprises a plurality of pipelined sub-blocks, the sub-blocks comprising:

a first sub-block configured to issue a stream of read commands to the second memory to retrieve the second memory financial instrument records based on the symbol identifiers;

a second sub-block configured to (1) process the second memory financial instrument records returned from the second memory in response to the second memory read commands, and (2) issue a stream of read commands to the first memory to retrieve the regional list blocks corresponding to the processed second memory financial instrument records;

a third sub-block configured to (1) process the regional list blocks returned from the first memory in response to the first memory read commands and (2) resolve first memory addresses from the pointer information for the regional financial instrument records corresponding to the messages; and

a fourth sub-block configured to output the first memory addresses for the regional and composite financial instrument records corresponding to the retrieved second memory financial instrument records and the retrieved regional list blocks; and

wherein the first, second, third, and fourth sub-blocks are configured to operate simultaneously with respect to each other in a pipelined fashion.

16. The device of claim 13 further comprising a composite record buffer, a message buffer, and a regional record buffer, the composite record buffer configured to store data representative of the retrieved composite financial instrument records, the message buffer configured to store financial market data representative of the messages, and the regional record buffer configured to store data representative of the retrieved regional financial instrument records;

wherein the regional update engines are configured to read from the message buffer and the regional record buffer to generate the regional field updates; and

wherein the composite update engines are configured to read from the message buffer and the composite record buffer to generate the composite field updates.

17. The device of claim 3 wherein the first memory is external to the reconfigurable logic device.

18. The device of claim 17 wherein the second memory is external to the reconfigurable logic device.

19. The device of claim 17 wherein the second memory is internal to the reconfigurable logic device.

20. The device of claim 3 wherein the first memory is internal to the reconfigurable logic device.

21. The device of claim 3 wherein the second memory is external to the reconfigurable logic device.

22. The device of claim 3 wherein the second memory is internal to the reconfigurable logic device.

23. The device of claim 3 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA), and wherein the address resolution block, the record retrieval block, and the field updating block are configured to perform their respective operations at hardware processing speeds.

24. The method of claim 3 further comprising:

the reconfigurable logic device caching a plurality of retrieved first memory financial instrument records in a third memory at a plurality of third memory addresses, each cached financial instrument record corresponding to a financial instrument and comprising financial market data for its corresponding financial instrument.

25. The method of claim 24 wherein the pipelined data processing blocks further comprise a cache determination block downstream from the address resolution block and upstream from the record retrieval block, and wherein the processing step further comprises:

the cache determination block (1) processing the resolved first memory addresses for the retrieved second memory financial instrument records to determine whether a most up-to-date record for the financial instrument corresponding to each retrieved second memory financial instrument record is located in the first memory or the third memory, and (2) providing the record retrieval block with addresses in the first and third memories where the most up-to-date records for the financial instruments corresponding to the retrieved second memory financial instruments are stored;

the record retrieval block retrieving a plurality of third memory financial instrument records from the third memory based on the third memory addresses provided by the cache determination block; and

wherein the address resolution block, the cache determination block, the record retrieval block, and the field updating block perform their respective steps simultaneously with respect to each other in a pipelined fashion.

26. The method of claim 25 wherein the pipelined data processing blocks further comprise a record updating block downstream from the field updating block, and wherein the processing step further comprises:

the record updating block updating the first memory in accordance with the generated updates; and

wherein the address resolution block, the cache determination block, the record retrieval block, the field updating block, and the record updating block perform their respective steps simultaneously with respect to each other in a pipelined fashion.

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

the record retrieval block loading the retrieved first and third memory financial instrument records into s plurality of processing buffers; and

the field updating block reading from the processing buffers to determine the financial instrument records for which the updates are to be generated; and

wherein the third memory and the processing buffers are located in the same memory space.

28. The method of claim 24 wherein the first memory financial instrument records comprise a plurality of regional financial instrument records and a plurality of composite financial instrument records, each regional financial instrument record corresponding to a financial instrument and comprising financial market data that is specific to a particular exchange on which its corresponding financial instrument is traded, each composite financial instrument record corresponding to a financial instrument and comprising financial market data that is general to all exchanges on which its corresponding financial instrument is traded;

wherein the second financial instrument records corresponding to financial instruments that are traded on multiple exchanges comprise pointer information for the regional and composite financial instrument records;

wherein the streaming data further comprises a plurality of exchange identifiers for the messages;

wherein the field updating block comprises a plurality of regional update engines and a plurality of composite update engines; and

wherein the processing step further comprises;

the address resolution block resolving a plurality of first memory addresses where the regional and composite financial instrument records for the financial instruments corresponding to a plurality of retrieved second memory financial instrument records are stored based on the symbol identifiers and the exchange identifiers; and

the regional and composite update engines generating, in parallel, a plurality of regional and composite field updates for the retrieved first memory financial instrument records.

29. The method of claim 28 further comprising:

storing a plurality of regional list blocks in the first memory at a plurality of first memory addresses, each regional list block corresponding to a financial instrument that is traded on multiple exchanges and comprising (1) a global exchange identifier for each exchange on which the corresponding financial instrument is traded, and (2) pointer information, in association with the global exchange identifiers, to the regional financial instrument records for the corresponding financial instruments; and

wherein the processing step further comprises the address resolution block processing the regional block lists to determine the pointer information associated with the global exchange identifiers that match the messages'"'"' exchange identifiers.

30. The method of claim 24 wherein the third memory is internal to the reconfigurable logic device.