High speed processing of financial information using FPGA devices

• US 8,655,764 B2
• Filed: 03/31/2011
• Issued: 02/18/2014
• Est. Priority Date: 06/19/2006
• Status: Active Grant

• Current Assignee: Exegy Incorporated
• Original Assignee: Ip Reservoir, LLC
• 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,929
• Publication Number:
  US 20110178917A1
• Time in Patent Office: 1,055 Days
• Field of Search: None
• US Class Current: 705/36.R
• 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

A high speed apparatus and method for processing a plurality of financial market data messages are disclosed. With respect to an exemplary embodiment, a reconfigurable logic device is employed to map the symbols present in the financial market data messages to another symbology.

Claims

1. An apparatus for processing a stream of financial market data messages, the apparatus comprising:

a first memory configured to store a plurality of financial instrument records, each financial instrument record corresponding to a financial instrument, wherein each financial instrument record is indexed in the first memory by a record key;

a second memory configured to store the record keys for the financial instrument records; and

a reconfigurable logic device configured with a plurality of firmware application modules (FAMs) arranged in a pipeline, at least one of the FAMs comprising a symbol mapping FAM, 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 memory, each received financial market data message comprising a symbol identifier for identifying that message'"'"'s corresponding financial instrument, (2) generate a hash key for each received financial market data message based on the symbol identifier within each financial market data message, and (3) map each generated hash key to a record key in the second memory using a hash function in combination with open addressing.

3. The apparatus of claim 1 wherein the record keys comprise direct record keys.

4. The apparatus of claim 3 wherein the second memory comprises a plurality N of entries, each entry comprising a direct record key, wherein N represents a number of financial instrument symbols supported by the second memory, and wherein each direct record key comprises a binary value having a size of M bits, wherein M=log₂(N).

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

13. The apparatus of claim 3 wherein the second memory comprises a memory device external from the reconfigurable logic device.

14. The apparatus of claim 3 wherein the first memory is separate from the second memory.

15. The apparatus of claim 1 wherein the symbol mapping FAM is further configured to (1) determine a global exchange identifier for each received financial market data message based on data associated with each received financial market data message, and (2) associate each received financial market data message with its mapped record key and determined global exchange identifier.

29. The apparatus of claim 3 further comprising a third memory, the third memory configured to store a plurality of third memory financial instrument records in locations corresponding to a plurality of third memory addresses, each third memory financial instrument record corresponding to a financial instrument and comprising financial market data for its corresponding financial instrument, and wherein each financial instrument record in the first memory comprises pointer information to a third memory address where financial market data can be found for the same financial instrument corresponding to that first memory financial instrument record.

31. An apparatus of claim 1 wherein the pipeline further comprises:

a message parsing FAM configured to receive and parse the financial market data messages, wherein the message parsing FAM is in communication with the symbol mapping FAM;

a last value cache (LVC) updating FAM in communication with the symbol mapping FAM;

an interest and entitlement filtering FAM in communication with the LVC updating FAM; and

a message formatting FAM in communication with the interest and entitlement filtering FAM.

32. The apparatus of claim 29 wherein another of the FAMs comprises:

a last value cache (LVC) updating FAM that is downstream from the symbol mapping FAM, the symbol mapping FAM configured to provide the direct record keys corresponding to the financial market data messages to the LVC updating FAM, the LVC updating FAM configured to (1) retrieve the financial instrument records corresponding to the provided direct record keys from the first memory, (2) retrieve the third memory financial instrument records from the third memory based on the pointer information in the retrieved first memory financial instrument records, and (3) update the retrieved third memory financial instrument records based on financial market data within the financial market data messages; and

wherein the symbol mapping FAM and the LVC updating FAM are configured to operate together simultaneously in a pipelined fashion such that the symbol mapping FAM is configured to operate with respect to a first financial market data message while the LVC updating FAM operates with respect to a second financial market data message.

33. The apparatus of claim 32 wherein the first memory comprises a cache memory internal to the reconfigurable logic device.

34. The apparatus of claim 32 wherein the first memory comprises a memory device external from the reconfigurable logic device.

35. The apparatus of claim 32 wherein the first memory is internal to the reconfigurable logic device.

36. The apparatus of claim 32 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA), wherein the symbol mapping FAM and the LVC updating FAM are configured to operate together simultaneously in the pipelined fashion at hardware processing speeds.

2. A method for processing a stream of financial market data messages, the method comprising:

storing a plurality of financial instrument records in a first memory, each financial instrument record corresponding to a financial instrument, wherein each financial instrument record is indexed in the first memory by a record key;

storing the record keys for the financial instrument records in a second memory;

receiving, in firmware logic deployed on a reconfigurable logic device, a plurality of financial market data messages corresponding to financial instruments for which there is a record in the first memory, each received financial market data message comprising a symbol identifier for identifying that message'"'"'s corresponding financial instrument, the firmware logic comprising a plurality of firmware application modules (FAMs) arranged in a pipeline, at least one of the FAMs comprising a symbol mapping FAM; and

the symbol mapping FAM mapping each symbol identifier to the record key in the second memory for the financial instrument corresponding to the financial market data message having that symbol identifier by (1) generating a hash key for each received financial market data message based on the symbol identifier within each financial market data message, and (2) mapping each generated hash key to a record key in the second memory by performing a near-perfect hashing operation in combination with open addressing on each generated hash key.

16. The method of claim 2 wherein the record keys comprise direct record keys.

17. The method of claim 16 wherein the second memory comprises a plurality N of entries, each entry comprising a direct record key, wherein N represents a number of financial instrument symbols supported by the second memory, and wherein each direct record key comprises a binary value having a size of M bits, wherein M=log₂(N).

25. The method of claim 16 wherein the second memory is internal to the reconfigurable logic device.

26. The method of claim 16 wherein the second memory comprises a memory device external from the reconfigurable logic device.

27. The method of claim 16 wherein the first memory is separate from the second memory.

28. The method of claim 2 further comprising the symbol mapping FAM (1) determining a global exchange identifier for each received financial market data message based on data associated with each received financial market data message, and (2) associating each received financial market data message with its mapped record key and determined global exchange identifier.

30. The method of claim 16 further comprising:

storing, in a third memory, a plurality of third memory financial instrument records in locations corresponding to a plurality of third memory addresses, each third memory financial instrument record corresponding to a financial instrument and comprising financial market data for its corresponding financial instrument; and

wherein each financial instrument record in the first memory comprises pointer information to a third memory address where financial market data can be found for the same financial instrument corresponding to that first memory financial instrument record.

37. The method of claim 30 wherein another of the FAMs comprises a last value cache (LVC) updating FAM that is downstream from the symbol mapping FAM, the method further comprising:

the symbol mapping FAM providing the direct record keys corresponding to the financial market data messages to the LVC updating FAM;

the LVC updating FAM (1) retrieving the financial instrument records corresponding to the provided direct record keys from the first memory, (2) retrieving the third memory financial instrument records from the third memory based on the pointer information in the retrieved first memory financial instrument records, and (3) updating the retrieved third memory financial instrument records based on financial market data within the financial market data messages; and

the symbol mapping FAM and the LVC updating FAM operating together simultaneously in a pipelined fashion such that the symbol mapping FAM performs its operations with respect to a first financial market data message while the LVC updating FAM is performing its operations with respect to a second financial market data message.

38. The method of claim 37 wherein the first memory comprises a cache memory internal to the reconfigurable logic device.

39. The method of claim 37 wherein the first memory comprises a memory device external from the reconfigurable logic device.

40. The method of claim 37 wherein the first memory is internal to the reconfigurable logic device.

41. The method of claim 37 wherein the reconfigurable logic device comprises:

a field programmable gate array (FPGA); and

the symbol mapping FAM and the LVC updating FAM operating together simultaneously in the pipelined fashion at hardware processing speeds.

5. An apparatus for processing a stream of financial market data messages, the apparatus comprising:

a first memory configured to store a plurality of financial instrument records, each financial instrument record corresponding to a financial instrument, wherein each financial instrument record is indexed in the first memory by a direct record key;

a second memory configured to store the direct record keys for the financial instrument records; and

a reconfigurable logic device configured with a plurality of firmware application modules (FAMs) arranged in a pipeline, at least one of the FAMs comprising a symbol mapping FAM, 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 memory, each received financial market data message comprising a symbol identifier for identifying that message'"'"'s corresponding financial instrument, (2) generate a hash key for each received financial market data message, (3) perform hashing on the generated hash keys to map the hash keys to addresses in the second memory where the direct record keys corresponding to the financial market data messages are stored, and (4) retrieve the direct record keys from the second memory using the addresses.

6. The apparatus of claim 5 wherein the symbol identifiers of the received financial market data messages comprise variable length strings having any of a plurality of formats, wherein the symbol mapping FAM is further configured to receive a plurality of symbology identifiers, each symbology identifier being (1) associated with a financial market data message and (2) indicative of the format for the associated financial market data message'"'"'s symbol identifier, the apparatus further comprising a third memory, the third memory configured to store a plurality of key codes indexed by symbology identifiers, each key code being indicative of a format-specific compression technique for a symbol identifier, and wherein the symbol mapping FAM is further configured to retrieve, for each of the received financial market data messages, a key code from the third memory based on the symbology identifier associated with each received financial market data message.

7. The apparatus of claim 6 wherein the symbol mapping FAM is further configured to generate the hash keys based on the retrieved key codes for the financial market data messages.

8. The apparatus of claim 7 wherein the symbol mapping FAM comprises a plurality of parallel logic elements and a multiplexer;

wherein each parallel logic element is configured to perform a different compression operation on the symbol identifiers to yield a compressed symbol string such that the parallel logic elements perform a plurality of different compression operations on the symbol identifiers in parallel to yield a plurality of different compressed symbol strings;

wherein the symbol mapping FAM is further configured to concatenate the retrieved key code with each of the compressed symbol strings to thereby generate a plurality of concatenated strings; and

wherein the multiplexer is configured to (1) receive the concatenated strings in parallel, and (2) select one of the concatenated strings as the hash key for each financial market data message based on the retrieved key code for each financial market data message.

9. The apparatus of claim 8 wherein the different compression operations comprise an alpha-numeric ticker compression operation, an ISIN compression operation, and a commodity compression operation.

10. The apparatus of claim 8 wherein the parallel logic elements are configured to allocate to each compression operation a different subset of the range of possible hash keys.

11. The apparatus of claim 7 wherein the symbol mapping FAM is further configured to perform the hashing by (1) performing near-perfect hashing to compute a primary hash function, and (2) resolving collisions via open-addressing.

18. A method for processing a stream of financial market data messages, the method comprising:

storing a plurality of financial instrument records in a first memory, each financial instrument record corresponding to a financial instrument, wherein each financial instrument record is indexed in the first memory by a record key;

storing the record keys for the financial instrument records in a second memory;

receiving, in firmware logic deployed on a reconfigurable logic device, a plurality of financial market data messages corresponding to financial instruments for which there is a record in the first memory, each received financial market data message comprising a symbol identifier for identifying that message'"'"'s corresponding financial instrument, the firmware logic comprising a plurality of firmware application modules (FAMs) arranged in a pipeline, at least one of the FAMs comprising a symbol mapping FAM; and

the symbol mapping FAM mapping each symbol identifier to the record key in the second memory for the financial instrument corresponding to the financial market data message having that symbol identifier by (1) generating a hash key for each received financial market data message, and (2) hashing the generated hash keys to map the hash keys to addresses in the second memory where the direct record keys corresponding to the financial market data messages are stored, and (3) retrieving the direct record keys from the second memory using the addresses.

19. The method of claim 18 wherein the symbol identifiers of the received financial market data messages comprise variable length strings having any of a plurality of formats, the method further comprising:

the symbol mapping FAM receiving a plurality of symbology identifiers, each symbology identifier being (1) associated with a financial market data message and (2) indicative of the format for the associated financial market data message'"'"'s symbol identifier;

storing a plurality of key codes indexed by symbology identifiers in a third memory, each key code being indicative of a format-specific compression technique for a symbol identifier; and

the symbol mapping FAM retrieving, for each of the received financial market data messages, a key code from the third memory based on the symbology identifier associated with each received financial market data message.

20. The method of claim 19 further comprising the symbol mapping FAM generating the hash keys based on the retrieved key codes for the financial market data messages.

21. The method of claim 20 wherein the symbol mapping FAM further comprises a plurality of parallel logic elements and a multiplexer;

each parallel logic element performing a different compression operation on the symbol identifiers to yield a compressed symbol string such that the parallel logic elements are performing a plurality of different compression operations on the symbol identifiers in parallel to yield a plurality of different compressed symbol strings;

the symbol mapping FAM concatenating the retrieved key code with each of the compressed symbol strings to thereby generate a plurality of concatenated strings; and

the multiplexer (1) receiving the concatenated strings in parallel, and (2) selecting one of the concatenated strings as the hash key for each financial market data message based on the retrieved key code for each financial market data message.

22. The method of claim 21 wherein the different compression operations comprise an alpha-numeric ticker compression operation, an ISIN compression operation, and a commodity compression operation.

23. The method of claim 21 further comprising allocating to each compression operation a different subset of the range of possible hash keys.

24. The method of claim 20 further comprising the symbol mapping FAM performing the hashing by (1) performing near-perfect hashing to compute a primary hash function, and (2) resolving collisions via open-addressing.