Patent Description:
As there is a growing need for faster processing of large volumes of data in financial industries, data processing systems based on clusters relying on general-purpose CPUs show a number of limitations. Indeed, if cluster approaches involve inexpensive hardware and provide tools that simplify the development, they have a number of constraints which are all the more significant as the requirement for high performance computing increases: high electricity consumption, costly maintenance, important space required for data centers. Further, the overall performance obtained with a cluster does not increase proportionally with the number of clusters. Unlike the cluster approach, data processing systems based on FPGAs allows execution of complex tasks in parallel with an important throughput, with a limited number of machines equipped with FPGAs. Accordingly, this hardware approach appears particularly suitable for the development of applications in the field of financial and investment industries where fast calculation is key to remain competitive.

An FPGA (acronym for Field-programmable gate array) designates an integrated circuit which can be configured after manufacturing. The configuration is generally specified using a Hardware description language (HDL). FPGAs contain a huge number of components ("logic blocks"), and a hierarchy of reconfigurable interconnections that allow the blocks to be "wired together". Logic blocks can be configured to perform complex combinational logic, or merely simple basic logical operations (boolean AND, OR, NAND, XOR etc.). As FPGA can perform parallel calculations, a same algorithm can be executed simultaneously for a number of independent inputs in only a few clock cycles. FPGAs are thus particularly suited for executing complex computation very fast.

For these reasons, more and more market data processing systems are designed using FPGAs.

A market data processing system generally comprises an order book management device (also known as a limit aggregation and book building device) which performs limit aggregation and order book building. The order book management device takes the orders identified in the input commands received via the market. The orders may be initially emitted by traders and filtered by the market computing systems according to predefined criteria. For example, they may be filtered if they are erroneous or if they have been executed immediately when received by the market computing systems. The order book management device sorts the received orders by order book ("book building" functionality) using the instrument identifier passed in each command. Each order book comprises a BID (or buy) side and an ASK (or sell) side. Each order listed in an order book is associated with a tradable object and comprises a price and quantity information. As used herein, the term "tradable object" refers to any object that can be traded in some quantity at a particular price, such as for example financial products. The order book management device is then used to match the orders of the same order book and side by price, adding their quantity (limit aggregation functionality).

One of the roles of the order book management devices is to update the order books depending on the input commands received from the market participants, over the exchange's network, such as a command to add, delete or modify an order. However, in conventional order book management devices, such update operations generate an important overhead and result in an important latency.

In order to address these and other problems, there is provided an order book management device as defined in the appended independent claim <NUM>, and a method as defined in appended claim <NUM>.

The invention thus provides an improved order book management device having a low latency, while still being able to withstand the command rate associated with the exchanges' <NUM> networks. Further, the latency and rate of the proposed order book management device are optimized with respect to conventional order book management devices. In particular, the latency has slight variations, and more generally undergoes far less variations than with conventional order book management devices.

It is another advantage of the invention to output both the previous version and the new version of the books (before and after application of the commands contained in a packet).

Further advantages of the present invention will become more apparent from the following detailed description considered with reference to the accompanying drawings.

Embodiments of the present invention will now be described by way of example with reference to the accompanying drawings in which like references denote similar elements, and in which:.

Referring to <FIG>, there is shown an exemplary market data processing system <NUM> provided to acquire and process market data delivered from one or more data sources such as financial exchanges.

The term "market data" as used herein refers to data received in the form of a data stream from a number of external sources that comprise financial quote and trade-related data associated with equity, fixed-income, financial derivatives, currency, and other investment instruments. Market data are a key element of financial and investment industries. The way they are handled (latency, availability, quality, etc.) directly impacts the competitiveness of such industries. An important feature of market data is their update frequency. Indeed, for strategic and competitive purpose real time updates are required. For example, delivery of price data from exchanges to users approaches real-time.

The first step of a market data processing chain comprises a data acquisition phase which in network applications consists of Network (generally UDP or TCP) acquisition <NUM> and is generally performed by the NIC (Network Interface Card) and the Operating System's Network Stack, as well as a data packet decoding phase. The decoding phase is performed by at least one decoder <NUM> (also referred to as a "market data packets decoder") that interacts with the feed sources for handling the market data streams received according to a given source-specific protocol (e.g. FAST) from exchange networks <NUM>, and decodes them.

More particularly, the decoder <NUM> is configured to convert the data streams from their source-specific format into an internal format (data normalization process). According to the message structure in each data feed, the decoder <NUM> processes each field value with a specified operation, fills in the missing data with value and state of its cached records, and maps it to the format used by the system. The decoder <NUM> may then call selected Order Management routines based on the decoded message.

The market data processing system <NUM> may further comprise an order information manager <NUM> comprising at least one memory for storing details related to each order to retrieve them when needed.

As shown, the market data processing system <NUM> may also comprise a message dispatch and transport unit <NUM> for formatting the processed data in messages and dispatching them to selected client applications <NUM> for further processing and decision taking. When client applications <NUM> are located on different servers, message transport may be done over a network.

The market data processing system <NUM> further includes an order book management device <NUM> (which may be also referred to as a "limits aggregation and book building device") for aggregating the orders that are pending into order books, present for each instrument a list of orders, possibly aggregated into limits and sorted by price. Generally, client applications <NUM> essentially need to access the first limits of a book. Alternatively, client applications may access the orders directly.

As used herein, an order book refers to the electronic collection of the outstanding limit orders for a financial instrument, such as for example a stock. Further, as used herein:.

The size or quantity of an order designates the number of shares to be bought or sold.

Order Books comprise limits which are sorted by price. The order book management device <NUM> may be configured for taking the orders which are mixed in the memory of the order information manager <NUM> and sent by said order information manager <NUM> to the order book management device <NUM> each time they are modified or otherwise referenced in a command and sort them by book, using the instrument identifier passed in each command. In some cases, order books may comprise orders from several instruments or the same instrument on different markets (consolidated books).

The order book management device <NUM> may be further configured to take the individual orders of the same book and side (bid or ask side) and match them by price, adding their quantity. This process is generally called "limit aggregation".

It should be noted that the term "command" as used in the present description may differ from the term « message ». Indeed, while a « command » designates a message decoded by the decoder <NUM>, a « message » represents a suite of bytes according to a given data protocol (such as FAST, Binary or FIX format). It is generally transmitted on a generic bus in several clock cycles depending on its size with respect to the bus width. On the contrary, a command may be transmitted in only one clock cycle on a parallel bus. According to one aspect of the invention, each command received in the input of the order book management device <NUM> may comprise at least some of the following parameters among: an operation code (opcode), a book identifier, a bit related to the book side, a price, a quantity, an order count and a level.

When the opcode corresponds to a by-limit command (limit creation, for example), the price, quantity and order count can be used to update the limit at the level indicated in the command. In the example of a limit creation, the price, quantity and order count can be copied to the limit at the level indicated by the command, and the limits below it shifted down.

In conventional order book management systems, an order generally remains in the order book until it is fully executed (its size falls to zero as a result of trades) or deleted. When an order is executed, an execution message is generally sent from the exchange to the clients. This message generally contains the size and the price at which the order(s) were executed. The clients then may update their books accordingly, removing the executed size from the book.

Partial executions may occur as a result of trades for less than the entire size of the order.

<FIG> represents an exemplary order book <NUM> containing <NUM> limit orders, on the bid side. Orders on the bid side represent orders to buy. The ask side (not represented) refers to orders to sell. The limit orders maintained in the order book <NUM> comprise:.

The price levels associated with these limit orders are respectively $<NUM>, $<NUM>, $<NUM>, $<NUM>, <NUM> $, <NUM> $, and <NUM> $. The best bid designates the highest bid price, which in the example is $<NUM>. The difference between the best bid (highest price in the bid side) and the best ask (lowest price in the ask side) is referred to as "the spread" and the midpoint designates the average value between the best bid and the best ask.

A market data processing system can receive a variety of messages from the market, including, for "by-order" markets (for example, NASDAQ, BATS):.

The messages may further comprise for "by-limit" markets (for example, CME, EUREX):.

The messages may also comprise for "by-price" markets (for example, LIFFE, TSE) a price update message for updating a limit indexed by its price; such message creates the limit if it does not already exist, and deletes it if its quantity reaches <NUM>.

The messages may be transformed into commands by the cores which are provided upstream the Decoder <NUM> and the Order Book Management Device <NUM>. The commands thus obtained may comprise:.

Accordingly, it is possible to add a limit order to an order book. As shown in <FIG>, the addition of a first order "add <NUM>@<NUM>" (designated by reference <NUM>) creates a new limit <NUM> at price "<NUM>", and the addition of a second order "Add <NUM>@<NUM>" (designated by reference <NUM>) adds more volume to limit number "<NUM>" as a limit at price "<NUM>" already exists in the order book <NUM>.

In conventional order book management devices, each new limit order is inserted in the order book so that the order book remains ordered by price, from the highest to the lowest on the bid side, and from the lowest to the highest on the ask side.

It is also possible to remove a limit order from the order book (cancel/remove operation). This operation simply removes the designated limit order from the order book <NUM> while maintaining the remaining limit orders sorted by price. Also, it is possible to reduce the quantity of each order (cancel/replace update). Such operation cancels the limit order and then replaces it with another order at the same price, but with a lower quantity. Generally, cancel orders can only lower the size of an order, but not increase it.

Each limit order added to the order book is assigned a unique identifier by the exchange. The limit order identifiers (also referred to as order identifier or order ID) are used to identify the limit orders that are to be updated, when receiving a cancel, cancel/replace request.

The inside market refers to the best bid (buy) and the best ask (sell) in a given order book. Generally, market processing systems comprise order matching engines (not shown) which are configured to determine if a market order on a given side (bid or ask) "hits" a limit order on the other side (respectively ask or bid) of the inside market (in such case a trade occurs). As used herein, a market order refers to an order requiring to immediately buy or sell a given quantity of a stock at the best available prices.

In conventional order book management devices, limits are sorted by price so that the client application can have an easy and quick access to the top of the book (represented by the first limits). In addition to the price and quantity, a limit can contain the number of orders it is made of (when the quantities of different orders having a same price level have been merged in a unique limit by adding their quantities).

When implemented in software, the order book management device <NUM> may use a variety of data structures to manage the limits depending on the desired performance and amount of instruments or books kept up to date. In some existing order book management devices, a simple table or array is used. However, this is only suitable when few books are processed and when it is acceptable to spend CPU (acronym for "Central Processing Unit") time shifting the limits in the books. In other order book management devices, more complex data structures (such as heaps, trees, etc.) are used to avoid shifting too many data. However, this results in a more difficult and slow access to the deeper limits.

Further, existing software implementations of the order book management device become slow and inefficient when processing an important number of books, mostly because it requires handling huge amounts of data and leads to lots of CPU cache misses. Such solutions are not suitable for firms that need to process all the instruments on a given set of markets. In such software approach, the load can be easily spread across several servers, each processing only some of the books. However, this requires routing the orders to the correct server using the instrument identifier, which may add extra network hops. Other drawbacks of such approach include the cost of the servers, the power consumption, rack space usage, and the latency of the total system.

Other existing solutions resort to hardware acceleration to overcome the deficiencies of the software approach, such as <CIT> which provides a book building system. This solution however requires more transfers back and forth between the CPU and the hardware acceleration card. It helps offload some processing from the CPU, but is not as optimized for latency.

The invention provides an improved order book management device <NUM> with an optimized latency.

<FIG> represents the general structure of the order book management system <NUM> according to certain embodiments of the invention. The order book management system <NUM> comprises a first management core <NUM>, thereinafter referred to as "top-of-book management core", and a second management core <NUM>, thereinafter referred to as "bottom-of-book management core".

The top-of-book management core <NUM> is configured to manage the top part of each order book while the bottom-of-book management core <NUM> is provided to manage the bottom part of the book. The top part of each order book (also referred to thereinafter as "top-of-book") comprises, for each side of the book, a list of P limits having the best prices, depending on the side (highest prices in the BID side or lowest prices in the ASK side) among all the N limits in the book. Each limit may comprise a plurality of orders and may be associated with a quantity, price and order count information.

The bottom part of the order book (also referred to thereinafter as "bottom-of-book") maintains the remaining N-P limits, each being associated with a quantity, price and order count information. Accordingly, the limits of the bottom part of the order book have lower (or higher, depending on the side) prices than the prices associated with top part of the order book. Advantageously, the top part of the order book is maintained in a different data structure as the bottom part of the order book. Further, the operation of the bottom-of-book management core <NUM> is triggered by the top-of-book management core <NUM> depending on the received input commands.

Such twofold architecture of the order book management device <NUM> according to the invention has the advantage to optimize the processing performances. In particular, it allows processing differently the top of each order book from the bottom of the order book, which optimizes latency as the top of the order book needs to be updated quickly in order to send the processed data to the client applications, while the bottom of the order book can be updated more slowly.

Clients can subscribe to the books of their interest via an API that configures the Message Dispatch and Transport Unit <NUM> to forward to them the modifications applied to a configurable depth of the selected books. This allows different clients to subscribe to different subsets of the books processed by the system. In the preferred embodiments of the invention, a client can only subscribe to the top part of the book and cannot subscribe to the bottom part of the book. This is because the bottom of book management core <NUM> is generally not connected to the Message Dispatch and Transport Unit <NUM>.

The number P of limits maintained in the top part of the order book may be chosen depending on a number of factors or criteria for enabling optimization of resources and performances. In particular:.

where N is an integer, S is the size of a limit in bits, and W is the memory word width in bits.

Alternatively, the order book management device may be configured to load half of the book (only the bid side or the ask side, whichever corresponds to the side received in the command) in the top part of the book, thereby reducing the time required for loading a book.

The input commands <NUM> are received by the top-of-book management core <NUM> which interacts with a top memory <NUM> provided to store the top part of books. Output commands <NUM> are generated based on the processing of the top-of-book management core <NUM> and the bottom-of-book management core <NUM> which interacts with a bottom memory <NUM> provided to store the bottom part of books.

Reference is now made to <FIG> which represents the architecture of the top-of-book management core <NUM>. The top part of each book is loaded in a first data structure stored in an internal cache <NUM>. The internal cache <NUM> comprises a set of entries, each entry storing such a data structure for an order book. The first data structure is processed by the top-of-book management core <NUM>. The internal cache <NUM> is provided to hide the latency of the external memory. This allows processing several instructions on a same order book in a row, and avoids back-pressuring the processing part which would affect timings because of the very wide buses.

The cache entries may be allocated according to a "Least Recently Used" (LRU) scheme. More specifically, when a cache entry is required to copy an order book in it, the least recently used entry is overwritten with the new book. For each cache entry, the "old version" <NUM> of the book before processing, and the "new version" <NUM> of the book (version being processed) are stored. Thus, at the end of each packet, after the commands in the packet have been applied on the "new version" cache <NUM>, only the limits that have been modified can be sent to the client application, thereby saving bandwidth and processing power. The comparison between the new and the old versions of the books may be performed by the array of comparators <NUM> to detect updated limits.

Additionally, the order book management device may be configured to output both the previous version and the new version of a book (corresponding respectively to the book state before the packet command is applied and after the packet command is applied), based on the information maintained in the cache's parts <NUM> and <NUM>.

According to another aspect of the invention, order limits may be stored in sorted arrays (first data structure) maintained in top memory <NUM>. The current depth of the book for both sides (bid and ask sides) may be stored in an internal memory in the Read Memory core <NUM>, which allows reading only the minimal amount of memory to load a book in cache, thereby saving memory bandwidth. The processing core <NUM> is configured to receive input commands (such as add, delete, modify commands, etc.) and the first data structure representing the top-of-book, stored in cache memory <NUM>, in the same clock cycle from the internal cache <NUM>. By thus receiving both a command and data, the processing core <NUM> can identify the data to which the command is to be applied. The processing core <NUM> further comprises an array of comparators for comparing the price in the command with the price in each limit of the book.

According to one aspect of the invention, the processing core <NUM> is configured to process each input command <NUM> and the associated first data structure in three clock cycles, by processing the limits inside the first data structure in parallel and in a pipelined way (no Finite State Machine).

<FIG> is a flowchart of the steps performed by the top-of-book management core <NUM>.

In response to an input command <NUM> related to an order (coming from a "by-order" or a "by-price" market) (step <NUM>) associated with a price and quantity information, the price in the command is compared in step <NUM> with the price in each limit of the order book.

Based on the comparison results, a decision is made as regards the action to take. In particular, if it is determined in step <NUM> that the input command <NUM> relates to an existing limit (the command has the same price as an existing limit), such limit may be updated in step <NUM>. If the update results in a quantity for the updated limit amounting to zero (step <NUM>), the limit is then deleted from the order book (step <NUM>), and the limits which are located below it in the order book are shifted toward the top of the book (step <NUM>). If this creates or widens a gap at the end of the top-of-book, a pop command is sent to the bottom-of-book core <NUM>, in step <NUM>, in order to request the next limit in the top-of-book.

If it is determined that the price associated with the input command <NUM> is within the range of the prices associated with the existing limits in the top of the order book (step <NUM>), a new limit is created in step <NUM>, and the limits located below it are shifted toward the bottom of the book in step <NUM>. If the top of the order book is already complete, a push command is sent to the bottom-of-book core <NUM>, in step <NUM>, to push the last limit to the bottom of the book.

If it is determined that the price associated with the input command <NUM> is outside the range of the prices in the top-of-book (step <NUM>) and the top-of-book is already complete, the command is forwarded to the bottom-of-book core <NUM> in step <NUM>.

In response to an input command <NUM> related to a limit (coming from a "by-limit" market), the limit at the provided level can be updated, ignoring the result of the price comparisons.

A limit may be created or deleted, according to the opcode in the command and the resulting quantity, and the limits below it may be shifted up or down.

A decision code may then be generated for each limit, using the results of the comparators and the input operation code. The decision code is used to update each limit, and write back the result to the cache <NUM>. This decision code can comprise the following codes:.

For example, in response to the insertion of a limit at level <NUM>, limits <NUM> and <NUM> will be given the "no operation" code, limit <NUM> will be given the "insert" code, and the limits under it will be given the "shift down" code.

According to another aspect of the invention, the top-of-book management core <NUM> may be arranged to fully exploit the level of parallelism offered by FPGAs and allows processing commands in as few clock cycles as possible. More specifically, limits may be compared in parallel, during the same clock cycle to the input command. The result of these comparators is then used to compute a decision code for each limit. Finally the resulting decision codes can be used to update the book. Accordingly, the whole updating process can take only <NUM> clock cycles, while a sequential processing on each limit would take as many clock cycles as limits in the top-of-book.

The bottom-of-book management core <NUM> is configured to manage the bottom part of each order book. The bottom part of each book can be updated more slowly than the top part of the book as the bottom part of the books is not sent to the output, and its processing time does not directly impact the total system's latency. Further, order books are generally small enough to fit completely in the top part. In most cases, modifications on the order book will not generate commands <NUM> to the bottom-of-book management core <NUM>. Even for the books that are large enough to span across both management cores <NUM> and <NUM>, many commands only relate to the top of the books.

As order books generally do not have a maximum depth and can expand infinitely in theory, more dense memories like DDR SDRAM (acronym for "Double Data Rate Synchronous Dynamic Random-Access Memory") may be used for storing the bottom part of the order book. To provide access to all the limits in the bottom part of the order books in a reasonable time, a specific data structure (also referred to as "second data structure" in the present description) is provided for the bottom part of the order book. The second data structure may be based on modified B+ trees. B+ trees consist of a root, internal nodes and leaves.

Contrary to binary trees, B+ trees have a very high fan-out, which means less memory accesses are needed to get from the root to the leaves, and as a result less latency to reach the right limit.

The B+ trees used for the bottom part of the order book, according to certain embodiments of the invention, may comprise one fixed-size root node and leaf nodes which are chained. The data structures composing the tree have thus fixed sizes, and the tree only comprises two levels: the level represented by the root node and the level represented by the leaf nodes.

Even if modified B+ trees present particular advantages, the bottom part of the order book may be based on other data structures. Such data structures may be chosen such that the bottom of book manager <NUM> is able to access every limit in a limited amount of time, preferably constant. For example, trees, which have a logarithmic access time, may be used for the bottom part of the order book. The following description will be made with reference to a bottom part of the order book based on a B+ tree data structure, for illustration purpose only.

In the embodiments of the invention where the order book management device <NUM> is integrated in data management platforms, regular DDR SDRAM (acronym for "Double Data Rate Synchronous Dynamic Random-Access Memory") memory may be used to store the leaves of the trees (bottom part of the order book), while QDR SRAM (acronym for "Quadruple Data Rate Static Random-Access Memory") memory may be used for the top of books and for the roots of the trees.

<FIG> represents exemplary data structures used for storing one side (bid or ask side) of an order book. As shown, the data structures comprise the top part of the order book <NUM> and a root node <NUM> and two leaf nodes <NUM> of the bottom part of the order book. The root node <NUM> comprises a first row comprising a quantity associated with a price, and in the other rows, it comprises pointers <NUM> to bottom-of-book leaf nodes <NUM> (two leaf nodes 55A and 55B are shown in <FIG>), each leaf node pointer <NUM> being associated with a price <NUM> in the root node (also designated thereinafter as "reference price").

According to a preferred embodiment of the invention, the first row of the root node <NUM> comprises the best limit <NUM> of the bottom part of the order book. For the bid side, the best limit is the highest limit of the bottom-of-book and corresponds to the highest price among the limits of the bottom part of the order book. For the ask side, the best limit is the lowest limit of the bottom-of-book and corresponds to the lowest price among the limits of the bottom part of the order book for the ask side. This allows for a fast response to pop requests coming from the top-of-book management core <NUM>. To facilitate the understanding of the embodiments of the invention, the following description will be made with reference to the bid side of an order book (the best limit corresponding to the highest price). However, the skilled person will readily understood that the same applies to the ask side (the best limit corresponding to the lowest price).

In the example of <FIG>, the highest limit is associated with quantity "<NUM>" and price "<NUM>".

This involves computing a new highest limit out of the first leaf node 55A after emitting a response to the pop request (the new highest limit is represented in the example by the limit associated with quantity "<NUM>" and price "<NUM>"). A leaf node <NUM> includes a number of order limits, each order limit comprising a quantity <NUM> associated with a respective price <NUM>. Each order limit may be further associated with an order count.

The prices <NUM> in each leaf node <NUM> range from a first value to a second value. The first value is the reference price <NUM> associated with the corresponding pointer <NUM> to the leaf node <NUM> in the root node <NUM> (this price being included in the leaf node <NUM>). The second value is the price associated with the previous row in the root node <NUM>, or alternatively the highest limit (the highest price in the root node) if the previous row is the first row of the root node, the second value being excluded from the considered leaf node. For example:.

<FIG> is a flowchart of the steps performed by the bottom-of-book management core <NUM>.

In response to an add or push command from the top-of-book core <NUM> associated with a price, thereinafter referred to as "price command" (step <NUM>), the bottom-of-book management core <NUM> compares the price in the command to the prices in the root node <NUM> (step <NUM>).

If it is determined that the price command is higher than the highest limit <NUM> in the root node <NUM> (step <NUM>), then the highest limit is updated to insert instead a line corresponding to the command in step <NUM>. The former highest limit is then pushed in the first leaf 55A in step <NUM>. If this first leaf is already full, the contents of the root node are shifted so that leaf <NUM> becomes leaf <NUM>, leaf <NUM> becomes leaf <NUM>, etc, and a new first leaf is created, that contains the former highest limit.

If it is determined that the command's price is equal to the price of the highest limit <NUM> in the root node <NUM>, then the command's and the highest limit's quantities and order counts are added up to form the new highest limit.

If it is determined that the price command is lower than the highest limit in the root node <NUM>, then the new limit is inserted in the leaf node <NUM> corresponding to the pointer <NUM> having the higher reference price <NUM> among the reference prices that are lower than the price command in the root node <NUM>, in step <NUM>. For example, a command price amounting "<NUM>" will be inserted in leaf node 55B. The selected leaf node <NUM> is then loaded in internal registers, and updated, if there remains available space in the leaf node (<NUM>).

However, if the leaf node is already full, the leaf node <NUM> may be split in two leaf nodes, shifting the entries in the root node (step <NUM>). This splitting is done by copying a part of the limits, the ones with the lowest prices, to a newly allocated leaf, and removing those limits from the "old" leaf. A pointer to the new leaf is then added to the root node <NUM>, shifting the lower pointers down.

In response to a delete command (step <NUM>) associated with a price (thereinafter referred to as "price command"), the bottom-of-book management core <NUM> compares the command price to the prices in the root node <NUM> in step <NUM>.

If the price command matches the highest limit in the root node <NUM> (step <NUM>), then the quantity and order count may be updated. To perform such update, the command's quantity and order count may be subtracted from the highest limit's quantity and order count respectively. If the new quantity and order count thus obtained are null, then the line corresponding to the highest limit is deleted in step <NUM>. The highest limit of the first leaf node 55A is then pushed in the root node <NUM> and deleted therefrom in step <NUM>.

If the price command is lower than the highest limit in the root node <NUM> (step <NUM>), then the bottom-of-book management core <NUM> selects the leaf node <NUM> corresponding to the pointer <NUM> having the higher associated price <NUM> among the reference prices that are lower than the price command in the root node <NUM>, in step <NUM>. For example, for a command price amounting "<NUM>", leaf node 55B will be selected (<FIG>). The selected leaf node <NUM> is then loaded into internal registers, and updated by deleting the limit corresponding to the command price in step <NUM>. If, as a result of the deletion of the limit, the selected leaf <NUM> becomes empty (step <NUM>), its associated pointer <NUM> is removed from the root node <NUM>, and the leaf is deallocated in step <NUM>.

In response to a pop command received from the top-of-book management core <NUM> (step <NUM>), the highest limit is returned after loading the root node <NUM> in step <NUM>. This highest limit is then restored in step <NUM> by finding the highest limit in the first leaf, and possibly deleting this first leaf if it contained only one limit.

In certain embodiments of the invention, additional steps may be performed if the Delete command received at step <NUM> corresponds to a limit that does not exist. This Delete command would result in a "negative" limit associated with a negative quantity and a negative order count in step <NUM>. Such situation could occur in situations where the commands are not executed in the exact same order as they are received in the decoders. As such, these situations have no important impact as the execution order is not taken into account for processing commands: the processing is based on removing and adding quantities and possibly order counts. For example, assuming a limit is deleted from the top-of-book. The top-of-book then sends a POP command to the bottom-of-book, which in turn replies with the first limit of its root node. Meanwhile, the top-of-book receives a delete command for the popped limit. As the limit does not exist in the top-of-book, a delete command is sent to the bottom-of-book. However, the bottom-of-book will not find the limit as it has sent it to the top-of-book. A negative limit is then created (<NUM>). This limit will be merged to the corresponding limit having positive quantity and order count values, namely the limit which was sent to the top-of-book as they have a same price. This processing may take some time depending on on-going actions on the book. However, this has limited impact as such merging will occur before the limit is moved up to the part of book provided to the client.

According to an aspect of the invention, leaves of the bottom part of the order book are not sorted by price, unlike the top part of the order book. This avoids shifting the limits inside the leaves when creating or deleting limits, thus reducing the amount of writes done to the leaves memory. It also reduces the amount of FPGA resources used.

Further, each leaf node may have a pointer <NUM> to the next leaf so as to allow chaining leaves when the root node <NUM> is full. Thus, the root node <NUM> can only point to some of the leaves.

In certain embodiments of the invention, leaves can comprise "holes" (empty limit positions) that correspond to limits that have been deleted. When adding a limit to a leaf, the first available position can be used, without requiring any sorting operation. Further, the deletion of a limit may only require setting the limit validity flag to zero. Accordingly, finding the highest limit of a leaf (to place it in the root node <NUM>) only require prices comparison. Advantageously, such comparison can be done in a few clock cycles by exploiting the parallelism of an FPGA with a tree of comparators. The few clock cycles required for such comparisons are outweighed by the performance gain from saving memory bandwidth.

With reference to <FIG>, the processing part of the bottom-of-book management core <NUM> may be implemented by state machines <NUM>. Several of those state machines can be put in parallel so that one state machine can wait for a leaf node to load while other state machines process a command on the node they have just loaded. This allows to have important leafs that take a long time to load (especially when DDR memory is used) and also a long processing time per command. Root node memories <NUM> are provided to store the root nodes <NUM> and the leaf nodes memories <NUM> are provided to store the leaf nodes <NUM>. A command dispatcher core <NUM> dispatches the commands to the different processing cores so that all the commands for a given order book are sent to the same processing core. This avoids processing successive commands concerning the same book at the same time with their results overwriting each other. Further, an order book may be assigned to each processing core using the LRU algorithm.

Allocating and freeing leaf memory space can be performed by filling a FIFO (acronym for "First In First Out") with pointers to statically allocated memory blocks. Thus, when a leaf needs to be allocated, a pointer is read from the FIFO, and when a leaf is freed, the pointer is put back in the FIFO. This allows for cheap dynamic allocation of fixed-size memory blocks.

The root node caches <NUM> are provided to hide the latency effects of the memories <NUM> storing the root nodes <NUM>. More particularly, they allow pipelining the reads while not being subject to the problem where a root node memory returns the result of a read which does not match the last write at the same address because the read order was emitted before the write order.

Additionally, the processing part of the bottom-of-book management core <NUM> may comprise an output arbiter entity <NUM> for mixing the commands from the leaf node processing cores <NUM> to provide them in a unique output bus <NUM>. Further, two other arbiter entities (not shown) may be provided to allow each core <NUM> and <NUM> to access memories <NUM> and <NUM>.

The FIFO comprising the pointers to the non allocated leaf nodes may be also connected to cores <NUM> through two associated arbiter entities, one for reading in the FIFO and the other for writing in the FIFO.

By separating the management of the top of the order book from the management of the bottom of the order book, and having both parts (<NUM> and <NUM>) work asynchronously, the invention provides an improved order book management device <NUM> having a low and constant latency. The dynamic aspect of the memory usage of the bottom-of-book management core <NUM> obviates the need for allocating space statically for each order book, which would require a huge amount of memory (biggest order book size expected multiplied by the number of books) and would place a hard limit on the maximum book size.

The invention presents several advantages over the prior art which include without limitation:.

The foregoing is considered as illustrative only of the principles of the invention. Further, since numerous modifications and changes will readily occur to those skilled in the art, it is not desired to limit the invention to the exact construction and operation shown and described, and accordingly, all suitable modifications and equivalents may be resorted to, falling within the scope of the invention. In particular the invention is not limited to the described data structures used for the bottom part of the book. Other types of trees or heaps could be used alternatively, providing satisfying performances for access to deep limits in important books and a substantially constant latency.

In addition, even if the described embodiments of the invention were focused in one side (bid or ask side), both sides of the book may be loaded simultaneously in cache <NUM> and presented to the processing core <NUM> and subsequent cores, so as to integrate certain mechanisms in the FPGA in processing core <NUM> or between the order book management device <NUM> and the message dispatching unit <NUM>.

Claim 1:
An order management device (<NUM>) for managing orders in response to input commands, each command comprising a command operation identifier, an object identifier and data related to an order, an order comprising at least a value and a quantity information and being related to an object, the order management device being implemented on an integrated circuit, wherein said order management device comprises:
- an order aggregation memory associated with one or more objects, said order aggregation memory being configured to aggregate orders, said order management device being configured to associate the aggregated orders with limits in said order aggregation memory, in response to input commands related to said orders, each limit being associated with a value and a quantity, each order being aggregated into the limit that has the same value as the order value, the quantity associated with a limit corresponding to the sum of the quantities of the orders which are aggregated,
characterised in that
said order aggregation memory comprises:
- a first data structure having a fixed size, said first data structure being configured to store orders associated with a set of P limits, the P limits being a subset of N limits and being selected based upon performance selection criteria, and
- a second data structure comprising the limits in the list of N limits that are not contained in the subset P, the entries in said second data structure being allocated dynamically,
wherein said order book management device further comprises a first management core (<NUM>) configured in said integrated circuit to process an input command related to an order, update said first data structure in response to the processing of said input command and generate at least one update command;
- a second management core (<NUM>) configured in said integrated circuit to update the second data structure in response to said update command received from said first management core,
wherein the first management core is configured to process input commands independently of the update command processing performed by the second processing core, the first management core being further configured to process the input command in a fixed number of clock cycles.