Method and System for Low Latency Basket Calculation

Abstract

A basket calculation engine is deployed to receive a stream of data and accelerate the computation of basket values based on that data. In a preferred embodiment, the basket calculation engine is used to process financial market data to compute the net asset values (NAVs) of financial instrument baskets. The basket calculation engine can be deployed on a coprocessor and can also be realized via a pipeline, the pipeline preferably comprising a basket association lookup module and a basket value updating module. The coprocessor is preferably a reconfigurable logic device such as a field programmable gate array (FPGA).

What is claimed is: 
     
         1 . A system for low latency basket calculation, the system comprising:
 a member of the group consisting of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP), wherein the member comprises a processing pipeline configured to receive streaming messages that comprise a plurality of data values for a plurality of elements, the processing pipeline comprising a basket association lookup module and a downstream basket value updating module;   wherein the basket association lookup module is configured to retrieve stored data based on the messages, the retrieved data corresponding to a plurality of baskets, the baskets having at least one of the elements as a basket member;   wherein the basket value updating module is configured to compute a plurality of net values for the baskets based on the retrieved data and the messages; and   wherein the basket association lookup module and the basket value updating module are configured to operate with respect to different messages and/or baskets at the same time in parallel with each other.   
     
     
         2 . The system of  claim 1  wherein each net value of a plurality of the net values comprises an aggregation of a plurality of the data values for the basket member elements of the basket corresponding to that net value. 
     
     
         3 . The system of  claim 2  wherein the basket value updating module comprises:
 a plurality of parallel computing paths, each computing path comprising compute logic configured to compute a plurality of the net values such that the computing paths are configured to simultaneously compute a plurality of different net values for the baskets. 
 
     
     
         4 . The system of  claim 2  wherein each of a plurality of the streaming messages further comprises identifying data for the element to which that streaming message pertains; and
 wherein the basket association lookup table is further configured to determine the baskets to which the messages pertain based on the identifying data. 
 
     
     
         5 . The system of  claim 4  further comprising:
 a memory configured to store a basket set pointer table and a basket set table, wherein the basket set pointer table comprises a plurality of basket set pointer table entries, and wherein the basket set table comprises a plurality of basket set table entries; 
 wherein the basket set pointer table entries are configured to associate the identifying data for the elements with pointers to the basket set table entries; 
 wherein the basket set table entries are configured to associate the elements with the baskets of which the elements are basket members, each of a plurality of the basket set table entries corresponding to an element and comprising (1) at least one basket identifier and weight pair, wherein the basket identifier identifies a basket of which that element is a basket member, and wherein the weight identifies a weight of that element in the identified basket, and (2) a previous data value for that element; and 
 wherein the basket set association lookup module is further configured to, for a streaming message, (1) retrieve the pointer from the basket set pointer table that is associated with the identifying data of that streaming message, (2) retrieve the basket set table entry corresponding to the retrieved pointer, and (3) provide data from the retrieved basket set table entry to the basket value updating module. 
 
     
     
         6 . The system of  claim 5  wherein the basket association lookup module is further configured to compute a delta value indicative of a difference between (1) the previous data value from the retrieved basket set table entry and (2) the data value in the streaming message corresponding the retrieved basket set table entry, and wherein the delta value is included in the provided data. 
     
     
         7 . The system of  claim 5  wherein the memory is external to the member. 
     
     
         8 . The system of  claim 5  wherein the memory is internal to the member. 
     
     
         9 . The system of  claim 5  wherein the basket value updating module is further configured to compute the net values according to a delta calculation approach. 
     
     
         10 . The system of  claim 9  wherein the provided data comprises a plurality of delta events, and wherein the system further comprises a buffer between the basket association lookup module and the basket value updating module, wherein the basket association lookup module is configured to write the provided data to the buffer as the delta events, and wherein the basket value updating module is configured to (1) read the delta events from the buffer, and (2) compute the net values for the baskets based on the read delta events. 
     
     
         11 . The system of  claim 1  wherein the processing pipeline further comprises a price event trigger module downstream from the basket value updating module, the price event trigger module being configured to process the computed net basket values against a triggering condition to determine whether any of the computed net basket values are to be reported to a client; and
 wherein the basket association lookup module, the basket value updating module, and the price event trigger module are arranged in a pipelined manner. 
 
     
     
         12 . The system as defined in  claim 11  wherein the processing pipeline further comprises an event generator module downstream from the price event trigger module, wherein the event generator module is configured to generate a message for delivery to the client in response to a determination by the price event trigger module that a computed net basket value is to be reported to the client, the generated message comprising the computed net basket value; and
 wherein the basket association lookup module, the basket value updating module, the price event trigger module, and the event generator module are arranged in a pipelined manner. 
 
     
     
         13 . The system of  claim 1  wherein the member comprises the reconfigurable logic device. 
     
     
         14 . The system of  claim 13  wherein the reconfigurable logic device comprises a field programmable gate array (FPGA). 
     
     
         15 . The system of  claim 1  wherein the member comprises the GPU. 
     
     
         16 . The system of  claim 1  wherein the member comprises the CMP. 
     
     
         17 . The system of  claim 1  wherein the streaming messages comprises a plurality of financial market data messages for a plurality of financial instruments, and wherein the baskets comprise financial instrument baskets. 
     
     
         18 . The system of  claim 1  the streaming messages comprise messages about product sales and/or product deliveries, and wherein the baskets comprise inventory baskets. 
     
     
         19 . The system of  claim 1  wherein the streaming messages comprise data about monitored events from one or more monitoring stations, and wherein the baskets comprise data point baskets for the monitored events. 
     
     
         20 . The system of  claim 1  wherein the member serves as a coprocessor for the system, the system further comprising:
 a processor for communication with the member, wherein the processor is configured to manage a delivery of the streaming messages to the member. 
 
     
     
         21 . The system of  claim 20  wherein the processor comprises a general purpose processor (GPP) configured to execute software to manage the delivery of the streaming messages to the member. 
     
     
         22 . A system for low latency basket calculation, the system comprising:
 a field programmable gate array (FPGA), the FPGA comprising a firmware pipeline, the firmware pipeline configured to receive a message, the message comprising (1) identifying data for an element, and (2) a data value for the element;   wherein the firmware pipeline comprises:
 first hardware logic configured to determine at least one basket of which the element is a basket member based on the identifying data; and 
 second hardware logic configured to compute a net value for each determined basket based on the data value; 
   wherein the FPGA is further configured to stream a plurality of messages through the firmware pipeline such that the first and second hardware logic are configured to operate in a pipelined fashion wherein the first hardware logic is configured to repeatedly operate with respect to a new message while the second hardware logic is configured to repeatedly operate with respect to a message previously operated on by the first hardware logic.   
     
     
         23 . The system of  claim 22  wherein the second hardware logic comprises a plurality of parallel computing paths configured to compute a plurality of net values for the baskets in parallel. 
     
     
         24 . The system of  claim 22  further comprising:
 a basket set table configured to store a plurality of basket set table entries that associate elements with (1) baskets of which the elements are member, and (2) data for supporting the net value computation; and 
 a basket set pointer table configured to store a plurality of pointers to the basket set table entries, wherein the pointers are associated with the identifying data for the elements; and 
 wherein the first hardware logic, for each of a plurality of the streaming messages, is further configured to:
 retrieve a pointer from the basket set pointer table entry that is associated by the basket set pointer table with the identifying data of that streaming message; 
 retrieve data from the basket set table entry corresponding to the retrieved pointer, wherein the retrieved data comprises, for each basket of which the element is a basket member, (1) a basket identifier and weight pair, wherein the basket identifier serves to identify a basket of which the element is a member, and wherein the weight serves to identify a weight of the element in that basket, and (2) a previous data value for the element. 
 
 
     
     
         25 . The system of  claim 24  wherein the basket set table and the basket set pointer table are resident in the FPGA. 
     
     
         26 . The system of  claim 24  wherein the second hardware logic is further configured to compute, for each of a plurality of the baskets corresponding to the basket identifiers in the retrieved data, the net value for that basket, wherein the computed net value is based on the weight, the previous data value within the retrieved data, and the data value in the streaming message. 
     
     
         27 . The system of  claim 24  wherein the second hardware logic is configured to compute the net values according to a delta calculation approach using data within the retrieved data. 
     
     
         28 . A method for low latency basket calculation, the method comprising:
 receiving a message, the message comprising (1) identifying data for an element, and (2) a data value for the element;   determining at least one basket of which the element is a basket member based on the identifying data;   computing a net value for each determined basket based on the data value;   repeating the method steps for a plurality of streaming messages; and   wherein the determining and computing steps are performed by a member of the group consisting of (1) a reconfigurable logic device, (2) a graphics processor unit (GPU), and (3) a chip multi-processor (CMP), and wherein the member performs the determining and computing steps in a pipelined fashion such that the determining step is performed with respect to a new streaming message while the computing step is performed with respect to a previous streaming message.   
     
     
         29 . The method of  claim 28  wherein the determining step comprises:
 accessing a basket set pointer table; 
 retrieving a pointer from the accessed basket set pointer table that is associated by the basket set pointer table with the identifying data; 
 accessing a basket set table based on the retrieved pointer; and 
 retrieving data from the accessed basket set table that is associated by the basket set table with the retrieved pointer, wherein the retrieved data comprises, for each basket of which the element is a basket member, (1) a basket identifier and weight pair, wherein the basket identifier serves to identify a basket of which the element is a member, and wherein the weight serves to identify a weight of the element in that basket, and (2) a previous data value for the element. 
 
     
     
         30 . The method of  claim 29  wherein the computing step comprises:
 computing the net value for a basket identified by a basket identifier within the retrieved data, wherein the computed net value is based on the weight, the previous data value within the retrieved data, and the data value in the streaming message. 
 
     
     
         31 . The method of  claim 28  wherein the computing step comprises computing in parallel a plurality of net values for the determined basket via a plurality of parallel computing paths. 
     
     
         32 . The method of  claim 28  wherein the computing step comprises computing the net value according to a delta calculation approach.