colwidth="49pt" />

Field
Description

Message type
The enumerated message type of this trading event.

Priority
The order priority. Orders of higher priority will get

matched regardless of entry order. All orders of a higher

priority will be matched before matching orders of a

lower priority.

Global
Global sequence number of the individual cell set by the

sequence
sequencer server.

Price
The order price sent by the client.

Side
The side of the order (ASK or BID)

Quantity
The total order quantity, not counting any quantity filled.

Minimum
The minimum quantity of the order to be executed.

quantity

The open order database 170 may be implemented as an array within DRAM. Cells may be indexed within the array of the open order database 170 according to the sequence in which their respective open order messages are received. For example, in a preferred embodiment, the cells may be indexed within the array in order of the Global Sequence Number assigned by the sequencer 130.

The multi-level memory cache 160 is external memory that stores data structures or containers, referred to herein as “tiles”. Whereas each cell contains open order data representing a single open order for a given symbol, side, and price, a tile contains open order data that represents all open orders for a given symbol, side, and price. In some embodiments, a tile can provide an index location (e.g., Global Sequence Number) and priority of each order cell within the open order database 170. Higher priority orders may be matched before lower priority orders. In some embodiments, the open order data contained within a tile may include lists of cell access nodes, where each cell access node contains address information for locating a corresponding cell in the open order database 170. A tile may also include one or more lists of cell access nodes that prioritize the orders for purposes of order execution. An example format of a tile according to a preferred embodiment is described below in connection with FIG. 3.

The gateway 110, the sequencer 130, the ticker plant 140, and the matching engine book 150 may be implemented, at least in part, by fixed logic in hardware, including without limitation Field Programmable Gate Arrays (FPGAs) and Application-Specific Integrated Circuits (ASIC). The external multi-level memory cache 160 and the external open order database 170 may be implemented in DRAM, including but not limited to synchronous DRAM (SDRAM). Persons skilled in the art will recognize that other forms of external memory may be used to implement the external multi-level memory cache 160 and the external open order database 170.

FIG. 2 is a schematic diagram that illustrates detailed components of the matching engine book 150 of FIG. 1 according to an embodiment. As shown, the matching engine book 150 server can include an interconnect interface 180, book processing logic 190, an open order database 170, a cache manager 152, and a symbol registry 154.

The interconnect interface 180 receives incoming messages in the form of cells (“incoming cells”) from the sequencer 130 and other components of the electronic trading system 100 and sends the incoming cells to the book processing logic 190 for further processing. The interconnect interface 180 can also receive outgoing messages in the form of cells (“outgoing cells”) from the book processing logic 190, such as order acknowledgements, rejected orders, and filled orders. The interconnect interface 180, in turn, may send the outgoing cells from the book processing logic 190 to other components of the electronic trading system 100.

The book processing logic 190 can perform various operations, including without limitation, matching orders, cancelling orders, modifying orders, replacing orders, and resting unmatched orders. To perform such operations, the book processing logic 190 may interface with the open order database 170 to read, write, and delete the open order data of individual cells that represent resting open orders. In some embodiments, the book processing logic 190 interfaces with the open order database 170 through a controller 172 that is coupled to an external memory cache 174 (“L3 RAM”). The external memory cache L3 may be implemented using DRAM.

To coordinate access to individual order cells resting in the open order database 170, the book processing logic 190 interfaces with the external multi-level memory cache 160 through the cache manager 152. In particular, the cache manager 152 may provide an interface through which the book processing logic 190 may read or write open order data for individual orders from a tile without any knowledge of the structure of the tile and the external multi-level memory cache 160.

In one example, the cache manager 152 may provide an interface through which the book processing logic 190 may input a side, symbol, and price (SSP) to request open order data for an order that may be used to match against a counter-order in a fill. In response to receiving an open order data request, the cache manager 152 may fetch a tile from the external multi-level memory cache 160 and load the tile into an internal memory cache 156 (“Block RAM L0 Cache”). After verifying that the loaded tile matches the requested side, symbol, and price, the cache manager 152 may return the open order data for one of the open orders that is next in priority for execution through an outgoing interface to the book processing logic 190. The cache manager 152 may access a symbol registry 154 maintained within the internal memory cache 156 as a fast lookup to locate tiles within the external multi-level memory cache 160 as a function of a symbol, side, and price (“SSP”).

In the illustrated embodiment, the external multi-level memory cache 160 includes a first memory cache 160a (“L1 RAM”) and a second memory cache 160b (“L2 RAM”) for tile storage. Each cache may be implemented using external memory in the form of DRAM. The external memory caches 160a and 160b are larger in size than the internal memory cache 156 of the cache manager 152. However, external memory access operations are relatively slower as compared to internal memory access operations. Accordingly, the number of external memory access operations are minimized in a number of ways.

According to one embodiment, the number of external memory accesses may be minimized by organizing open order data for all open orders of a particular symbol, side, and price (“SSP”) into a single tile that can be fetched from an external memory cache with at most two external memory accesses. A tile preferably contains all the open order data needed by the book processing logic 190 to perform order match processing, including not only the data for all orders of a given side, symbol, and price, but also metadata statistics, order indexing and prioritization information for those orders. Once loaded into the internal memory cache of an FPGA or other fixed logic, the tile may be accessed often with minimal delay in order to obtain order data for multiple open orders having the same symbol, side, and price. Having all such relevant data on the orders in the tile already loaded in the internal memory cache 156 allows for extremely fast processing of order matching by the book processing logic 190.

FIG. 3 is a schematic diagram that illustrates the data structure of a tile 300 according to one embodiment. A tile may include a header portion 310 and a body portion 320. The header portion 310 can include various fields that identify the tile type and a symbol, side, and price (“SSP”) tuple. In the illustrated embodiment, the header portion includes the following fields:

Field
Description

Type
An integer representing the type of tile

(e.g., MODE_IMMED,

MODE_COLLISION, MODE_EXTEND,

or MODE_FREE)

open_shares
An integer representing an aggregate

number of shares

open_orders
An integer representing a number of open

orders

PriorityLists[ ]
A pointer array to a free list of empty cell

access nodes and one or more priority lists

of cell access nodes assigned to

corresponding open order cells (e.g.,

P0List, P1List, P2List)

Symbol
A unique integer for identifying a stock or

other financial instrument

Price
An integer representing a price,

sometimes referred to as “a tick”.

Side
A boolean or integer indicating whether

the open orders are (i) buy side or (ii) sell

side.

Tile Capacity
An integer representing the size of the tile

and thus the maximum number of open

orders that may be represented within the

tile (e.g., maximum number of cell access

nodes).

The body portion 320 of the tile depends on the tile type identified in the header portion 310. In the illustrated embodiment, the tile is identified as “an immediate tile” (i.e., Type=MODE_IMMED). Accordingly, the body portion 320 contains open order data that represents all open orders for the given symbol, side, and price.

In the illustrated embodiment, the open order data includes multiple data structs, sometimes referred to herein as “cell access nodes.” A cell access node 325 represents a single order cell 330 within the open order database 170 and the priority of the order relative to other open orders represented by other cell access nodes 325 in the tile 300. As shown in the above table, the Tile Capacity may be an integer representing the size of a tile and thus, the maximum number of open orders that may be represented therein if the tile is an immediate tile. For example, the Tile Capacity may be represented with a 2-bit enumeration (ENUM) which can represent a predefined tile size in kilobytes (e.g., SINGLE, DOUBLE, QUAD, or JUMBO).

As shown, the body portion 320 of an immediate tile can include a free list of cell access nodes 327 that are available for assignment to an open order cell. A cell access node 325 that is assigned to an open order cell 330 in the open order database 170 may include address information for locating the cell in the open order database 170. For example, a global sequence identifier (i.e., GSEQ) assigned by the sequencer 130 of FIG. 1 can be used as an index to locate the cell in the open order database 170.

The body portion 320 of an immediate tile can also include one or more priority lists 329a, 329b, 329c (e.g., P0List, P1List, and P2List). Cell access nodes 325 representing corresponding order cells can be added to one of the priority lists. Cell access nodes on higher priority lists preferably have their respective orders executed before open orders of cell access nodes on lower priority lists. Within each of the priority lists, cell access nodes at or near the top of a list have their respective orders executed before those of cell access nodes at or near the bottom of the list. In the illustrated embodiment, the priority lists are implemented as linked lists. Accordingly, a cell access node can include pointers for internally linking the cell access node to one of the priority lists. For example, as shown, a cell access node can include one pointer to the next cell access node in the list (e.g., next pointer) and another pointer to the previous cell access node in the list. Thus, as shown, an immediate tile may contain cell access nodes that include all information needed for indexing and prioritizing all open orders for a particular symbol, side, and price in the open order database 170.

However, special tiles, sometimes referred to herein as “redirection tiles,” may be used in the multi-level memory cache 160 as placeholders that contain address information for locating an immediate tile elsewhere in the external multi-level memory cache 160. As discussed in more detail below in connection with FIG. 9, redirection tiles can be identified with different Type field values (e.g., Type=MODE_COLLISION or Type=MODE_EXTEND). The structure of a redirection tile is different than the structure of an immediate tile. In particular, a redirection tile may not include any open order data. Rather, a redirection tile may include a specific memory address or other address information for locating at least one immediate tile in the multi-level memory cache 160 for the same symbol, side, and price. Such address information may be provided either in the header portion of the redirection tile or in the body portion of the redirection tile.

To further minimize the number of external memory access, external memory can be provisioned as an asymmetric, multi-level memory cache that is tailored for handling large data sets of matching engine books and ticker plant services. In particular, the multi-level memory cache may include two or more external memory caches for storing tiles according to a price priority scheme.

FIG. 4 is a schematic diagram that illustrates an embodiment of an asymmetric multi-level cache 160 that is provisioned for storage and retrieval of tiles according to a price priority scheme. As shown, the multi-level memory cache 160 includes a first memory cache 410 and a second memory cache 450.

The first memory cache 410 allocates contiguous memory segments 412a, 412b (collectively contiguous memory segments 412) for each given symbol and side to store a limited number of fixed size tiles at consecutive price levels within an actively traded price range. Each contiguous memory segment 412, sometimes referred to herein as an “active order region” can be implemented as a memory array of consecutive price tiles, preferably a circular buffer array. Since each active order region can be a defined memory array of fixed-size tiles, the cache manager 152 can index specific tiles with an active order region by price.

As shown, the first memory cache 410 includes a pair of active order regions for each given symbol, where one of the active order regions contains buy-side tiles 412a and the other region contains sell-side tiles 412b. Although the active order regions for the buy-side and the sell-side of a given symbol (e.g., 412a, 412b) are shown in as being next to one another, the active order regions can be organized in any order provided that the active order regions do not overlap.

The actively traded price range of an active order region 412 is generally a densely distributed price range near the best bid price for buy-side active order regions or near the best ask price for sell-side active order regions. In some embodiments, the actively traded price range can be defined such that the midpoint between the minimum price level and the maximum price level is a best bid price for buy-side active order regions 412a or a best ask price for sell-side active order regions 412b.

The size of each tile within an active order region for a particular symbol is preferably fixed, resulting in the order capacity of each tile being constant within the same active order region. Although tile size is fixed within an active order region, tile size can vary from one active order region to another based in part on historical order volume. In some embodiments, the number of tiles allocated for an active order region of a given stock and/or the maximum open orders per price point for that stock can be based on a stock's historical price variability, daily volatility, and order volume.

It is not an efficient use of space in the first memory cache to allocate a tile for every possible price point of a given symbol and side. Accordingly, the multi-level memory cache 160 also includes a second memory cache 450. The second memory cache 450 allocates space 452, sometimes referred to herein as “an inactive order region,” which stores tiles that fall outside the active order regions 412 of the first memory cache 410.

The inactive order region 452 of the second memory cache 450 does not allocate separate cache space for each symbol and side. Rather, the inactive order region is provisioned for shared tile storage. In the illustrated embodiment, the inactive order region 452 is implemented as a sparse hash array.

To locate a tile within the sparse hash array 452, the cache manager 152 may generate a hash key based on at least the symbol and price of the target tile. A method for generating a hash key for locating a tile within the sparse hash array 452 of the second memory cache 450 is disclosed herein in connection with FIG. 8.

The second memory cache 450 may further include an unstructured memory region, such as a free heap buffer 454 for handling special circumstances, which are disclosed in connection with FIG. 9-10D.

FIG. 5 is a schematic diagram that illustrates an example provisioning of a first memory cache within the multi-level memory cache for a single stock (e.g., MSFT). As shown, the active buy-side order region 512a for MSFT stock has a defined price span of three dollars ($3.00) with a minimum price variation of one penny ($0.01). Accordingly, the active buy order region 512a, which may be implemented in the form of a circular buffer array, stores 300 tiles containing open order data (e.g., cell access nodes) representing buy-side orders of MSFT stock at consecutive prices between $315.41 to $312.41.

Although the best bid price tile 514 is shown as the highest price tile ($315.41), the active buy order region 512a may include one or more tiles for price levels that are higher than the current best bid price. In some embodiments, the active buy order region 512a may extend between the lowest price tile and the highest price tile such that the best bid price tile is located at or near the midpoint price of the region. In some other embodiments, the active buy order region 512a may extend between the lowest bid price tile and the highest bid price tile such that the bid price of the highest bid price tile may be 15% to 25% higher than the best bid price. Accordingly, the tile having the best bid price may be permitted to change without having to constantly adjust the active price range of the active buy order region.

Similarly, the active sell-side order region 512b for MSFT stock has a defined price span of three dollars ($3.00) with a minimum price variation of one penny ($0.01). Accordingly, the active sell order region 512b, which may be implemented in the form of a circular buffer array, stores 300 tiles containing open order data (e.g., cell access nodes) representing sell-side orders of MSFT stock at consecutive prices between $315.51 to $318.51.

Although the best ask price tile 516 is shown as the lowest price tile ($315.51), the active sell order region 512b may include one or more tiles for price levels that are lower than the current best ask price. In some embodiments, the active sell order region may extend between the lowest ask price tile and the highest ask price tile such that the best ask price tile is located at or near the midpoint price of the region. In some other embodiments, the active sell order region 512b may extend between the lowest ask price tile and the highest ask price tile such that the ask price of the lowest ask price tile may be 15% to 25% lower than the best ask price. Accordingly, the tile having the best ask price may be permitted to change without having to constantly adjust the active price range of the active sell order region.

The size of each tile within an active order region is preferably fixed for a given stock and side. However, as discussed above, tile size can vary between the active order regions of different stock-side tuples. For example, in FIG. 5, the size of each tile within the respective active order regions 512a and 512b accommodates up to a maximum order capacity of 1024 cell access nodes (i.e., a quad-sized tile). Tile size for other active order regions may accommodate a greater or smaller maximum number of cell access nodes. For example, single-sized tiles may have a first size in the amount of 4 kilobytes (4 KB) to provide a maximum order capacity of 256 cell access nodes, double-sized tile may have a second size in the amount of 8 kilobytes (8 KB) having a maximum order capacity of 512 cell access nodes, and a quad-sized tile may have a third size in the amount of 16 kilobytes (16 KB) to provide a maximum order capacity of 1024 cell access nodes.

FIG. 5 also illustrates buy order tiles 518a and sell order tiles 518b having outlier prices that fall outside the respective price ranges of the active buy order region 512a and the active sell order region 512b for MSFT stock. As discussed in more detail in connection with FIGS. 6 and 8-10D, tiles having outlier prices may be stored in the second memory cache 450 of the external multi-level memory cache 160.

FIG. 6 is a flow diagram that illustrates a method 600 for fetching tiles from the external multi-level cache 610 according to an embodiment. In some embodiments, the method 600 can be implemented by the cache manager 152 described above in connection with FIGS. 1 and 2.

At block 610, the cache manager 152 receives a request for open order data that represents an order to buy or sell a stock or other financial instrument. The request may be inputted by the book processing logic 190 of a matching engine book 150, an embodiment of which is described in connection with FIGS. 1 and 2. The request may also be inputted by a component of a ticker plant or other market data feed server, embodiments of which are described in connection with FIGS. 18 and 19.

In a preferred embodiment, the open order data request may include a symbol identifying the stock or other financial instrument, a side indicating whether the order is to buy or to sell, and a price (“SSP”). In a preferred embodiment, the price may be initially represented by an integer having an implied decimalization, referred to herein as a tick. For example, $1.00 may be initially represented as 10000 ticks with an implied decimalization equal to 4.

At block 620, the cache manager 152 converts the price to a target price tick within a sequence of consecutive ticks. In the U.S. and other financial markets, prices can be defined to have a minimum price variation that differs above and below one or more price precision levels. For example, prices may have a first minimum price variation (MPV) of one cent ($0.01) above a price precision level of one dollar ($1.00) and a second minimum price variation of one hundredth of one cent ($0.0001) below one dollar. Such differences in MPV can result in non-consecutive tick sequences. For example, the tick sequence corresponding to prices $0.9999, $1.00, $1.01 can be 9999, 10000, 10100, resulting in a gap of 10 ticks between $1.00 to $1.01.

Since tiles are preferably indexed in the external multi-level memory cache 160 according to price, prices are preferably normalized to fall within a consecutive tick sequence regardless of differences in minimum price variation. Details regarding an embodiment for converting a target price to a normalized target price tick within a consecutive tick sequence is described below in connection with FIGS. 14A-14B.

At conditional block 630, the cache manager 152 determines whether the target price falls within the active price range defined for the active order region for the given symbol and side. The active price range may include consecutive prices that fall between a most aggressive price and a least aggressive price, depending on the side. For buy-side orders, the most aggressive price is the highest bid price and the least aggressive price is the lowest bid price of the range. Conversely, for sell-side orders, the most aggressive price is the lowest ask price of the range and the least aggressive price is the highest ask price of the range.

If the target price is determined at conditional block 630 to fall within the active price range, the process proceeds to block 640. At block 640, the cache manager 152 fetches the tile from the active price region for the given symbol and side in the first memory cache 410 using the target price tick as an index. Details of an example for determining a tile location within an active price region of the first memory cache using a target price tick as an index is described below in connection with FIGS. 7A and 7B.

If the target price is determined at conditional block 630 to fall outside the active price range, the process proceeds to blocks 650 and 660. At block 650, the cache manager 152 generates a hash key based on the target price tick and symbol. At block 660, the cache manager 152 fetches the tile from the inactive price region of the second memory cache using the hash key as an index. Details of an embodiment for generating a hash key to index an inactive price region of the second memory cache in the form of a sparse hash array is described below in connection with FIG. 8.

As discussed above, the cache manager 152 can fetch the tile from the active price region for the given symbol and side in the first memory cache 410 using the target price tick as an index. FIGS. 7A and 7B are schematic diagrams that illustrate an example for determining a tile location within an active order region of the first memory cache using a target price tick as an index.

In particular, FIG. 7A illustrates an active buy order region 710 for a financial instrument, while FIG. 7B illustrates an active sell order region 720 for the financial instrument. Each active order region may be implemented as a circular buffer array of tiles.

The cache manager 152 may maintain the boundaries and state of the circular buffer array for a given symbol and side in a symbol registry 154 maintained in internal memory cache 156 as described above in connection with FIGS. 1 and 2. In particular, the symbol registry 154 may include the following parameters to define the current boundaries and state of an active order region in the form of a circular buffer array for a given symbol and side:

- base address of the active order region,
- total number of tiles allocated to the active order region,
- fixed tile size within the active order region (e.g., single-size tile (4 KB) double-size tile (8 KB), or quad-size tile (16K)),
- current best price (i.e., best bid price if active buy order region or best ask price if active sell order region)
- current best price index (i.e., current index of the array element containing the current best price tile), and
- current wrap index (i.e., current index of the array element containing the tile at the worst bid or ask price of the active order region).

Given the foregoing information from the symbol registry 154 for a given symbol and side and that tiles are indexed consecutively by price, the cache manager 152 can determine that the active buy order region 710 of FIG. 7A starts at the buy-side base address 712 and contains a total number of 1024 indexable tiles.

Referring to FIG. 7A and given that the symbol registry can provide, among other information, (i) the wrap index (e.g., index number 1023) that identifies the location of the tile 714 having the worst or least aggressive bid price (e.g., 9077 ticks ($0.9077)), (ii) the current best price index (e.g., index number 300) that identifies the location of the tile 716 having the current best bid price (e.g., 9800 ticks ($0.9800)), and (iii) the total number of indexable tiles (e.g., 1024 total tiles), the cache manager 152 can determine whether a target buy-side tile falls within the consecutive price range of the active buy order region 710. In this example, the consecutive price range of the active buy order region 710 extends from the highest (or most aggressive) bid price of 10100 ticks ($2.00) at index 0 of the array to the worst (or least aggressive) bid price of 9077 ticks ($0.9077) at index 1023. Furthermore, given that the tiles of the active buy order region 710 are indexed consecutively by price, the cache manager 152 can determine the index location for any buy-side tile within the active buy order region for a given symbol at a price relative to the best price index, the worst price index, and total number of tiles as identified in the symbol registry.

Referring to FIG. 7B and given that the symbol registry can provide, among other information, (i) the wrap index (e.g., index number 1023) that identifies the location of the tile 724 having the worst or least aggressive ask price (e.g., 10023 ticks ($1.23)), (ii) the best price index (e.g., index number 200) that identifies the location of the tile 726 having the current best bid price (e.g., 9200 ticks ($0.9200)), and (iii) the total number of indexable tiles (e.g., 1024 total tiles), the cache manager 152 can determine whether a target sell-side tile falls within the consecutive price range of the active sell order region 720. In this example, the consecutive price range of the active sell order region 720 extends from the lowest (or most aggressive) ask price of 9000 ticks ($0.9000) at index 0 of the array to the worst (or least aggressive) ask price of 10023 ticks ($1.23) at index 1023. Furthermore, given that the tiles of the active sell order region 722 are indexed consecutively by price, the cache manager 152 can determine the index location for any sell-side tile within the active sell order region 722 for a given symbol at a price relative to the best price index, the worst price index, and total number of tiles as identified in the symbol registry.

Furthermore, as price behavior for a given symbol and side move during the course of a trading day, the cache manager 152 can adjust the price range of the respective active order region by updating one or more of the foregoing parameters defined in the symbol registry 154. In view of such adjustment, the cache manager 152 may add or remove tiles to response to the adjusted price range of the active order region. Methods 1100 and 1300 for gradually adjusting price-consecutive tile sequences within an active order region of the first memory cache is presented below in connection with FIGS. 11-14B.

As discussed above, when a target price is determined to fall outside the active price range of the first memory cache, the cache manager 152 may generate a hash key as an index to locate a tile location within the sparse hash array of the inactive price order region 452. Hash key collisions may occur when the generated hash key corresponds to a tile location currently occupied by another tile. In particular, hash key collisions may be more likely to occur if a hash key is calculated based on price alone.

Accordingly, to minimize hash key collisions and thus improve access time for fetching tiles from the sparse hash array, the cache manager 152 may generate a hash key based on the target price and a unique offset representing the stock or other financial instrument. Since inactive price levels, sometimes referred to as outlier prices, are generally centered around round-currency values (e.g., dollars rounded to the nearest one, five, and ten), the likelihood of hash key collisions may be reduced by adding a unique offset to the target price as discussed below with respect to FIG. 8.

FIG. 8 is a flow diagram that illustrates a method 800 of generating a hash key to index an inactive price region 452 of the second memory cache 450 in the form of a sparse hash array according to an embodiment. In some embodiments, the method 800 can be implemented by the cache manager 152 described above in connection with FIGS. 1 and 2.

At block 810, the cache manager 152 receives a target price in the form of a target price tick. In some embodiments, the target price tick may be generated by the cache manager 152 in response to receiving a request for open order data associated with a given symbol, side, and price as described above in connection with method blocks 610 and 620 of FIG. 6.

At block 820, the cache manager 152 offsets the target price tick by adding a numerical symbol identifier that uniquely identifies a given stock or other financial instrument, resulting in an intermediate symbol-specific value. As discussed above, the cache manager 152 maintains a symbol registry 154 as a memory lookup for information specific to a stock or other financial instrument. To access information for a specific stock or other financial instrument, the symbol registry 154 assigns a unique symbol index to each instrument (e.g., integers 0, 1, 2, . . . N). Accordingly, in some embodiments, the cache manager 152 can offset the target price tick using the symbol index for the given stock or financial instrument.

At block 830, the cache manager 152 may generate the hash key by applying a modulo operation to the intermediate symbol-specific value with respect to the total number of tile locations within the sparse hash array of the inactive order region 452. Since inactive price levels, or outlier prices, are generally centered around round-currency values (e.g., dollars rounded to the nearest one, five, and ten), the likelihood of hash key collisions may be reduced by offsetting the target price tick with the symbol index or other symbol identifier. For example, given two tiles at the same price (e.g., 10000 ticks or $1.00) for different symbols (e.g., having assumed symbol indexes equal to 1 and 2), the intermediate symbol-specific value would be 10001 for the first tile and 10002 for the second tile. By performing a modulo operation on the respective values with respect to the total number of tiles allocated in the sparse hash array, say one million (1M) tiles the hash key would be 10001 and the hash key for the second tile would be 10002, thereby avoiding a hash key collision for tiles having the same price for different symbols.

At block 840, the cache manager 152 uses the hash key as an index to locate the memory address of a tile within the inactive order region 452 of the second memory cache 450 in the form of a sparse hash array. As discussed above, the sparse hash array of the inactive order region 452 preferably provides shared tile storage for tiles having prices outside the actively traded price range. Given that the sparse hash array may be defined to store tiles having a fixed size, the cache manager 152 can determine the index of the tile location for a given symbol, side, and price by adding the base memory address of the sparse hash array to the product of the hash key and the fixed tile size.

As discussed above in connection with FIG. 3, an immediate tile contains open order data (e.g., cell access nodes) that includes all information needed for indexing and prioritizing all open orders for a particular symbol, side, and price in the open order database 170. However, special tiles, sometimes referred to herein as “redirection tiles,” may be used in the multi-level memory cache 160 as placeholders that contain address information for locating an immediate tile elsewhere in the external multi-level memory cache 160.

Accordingly, as discussed in more detail below in connection with FIG. 9, the cache manager 152 may generally fetch immediate tiles from the multi-level memory cache in one external memory access, while in other circumstances, the cache manager 152 may need at most two external memory access to fetch an immediate tile. For example, as discussed in more detail below in connection with FIG. 9, the cache manager 152 may initially fetch a redirection tile from the either an active order region of the first memory cache or an inactive order region of the second memory cache and then fetch an immediate tile at an address in a free heap buffer or other unstructured memory region of the second memory cache. Once the immediate tile is loaded and verified, the cache manager 152 can access the immediate tile within the internal memory cache with minimal delays in order to obtain open order data for multiple open orders having the same symbol, side, and price.

FIG. 9 is a flow diagram that illustrates a method 900 of processing different types of tiles according to an embodiment. The method 900 may be implemented by the cache manager 152 described above in connection with FIGS. 1 and 2.

At block 910, the cache manager 152 may load a tile into an internal memory cache 156, such as block random access memory (BRAM). As discussed above in connection with FIG. 3, there are different types of tiles. An immediate tile contains open order data (e.g., cell access nodes) that represents multiple buy-side or sell-side orders for a financial instrument. A redirection tile contains at least one address to access a memory location of an immediate tile elsewhere in the multi-level memory cache 160, such as a free heap buffer or other unstructured memory region.

At conditional block 920, the cache manager 152 determines whether the loaded tile is an immediate tile. If the loaded tile is determined to be an immediate tile, the process proceeds to block 960. At block 960, the cache manager 152 verifies the contents of the immediate tile. In some embodiments, the cache manager 152 verifies that the symbol, side, and price of the tile matches the symbol, side, and price of the requested open order data. For example, as discussed above in connection with FIG. 3, the header portion 310 of a tile may contain fields that identify the symbol, side, and price of the tile.

Conversely, if the loaded tile is not an immediate tile, the cache manager 152 proceeds to blocks 930 through 960. At conditional block 930, the cache manager 152 determines whether the loaded tile is a redirection tile. As mentioned above, a redirection tile contains an address of an immediate tile at a memory location in a free heap buffer 454 or other unstructured memory region of the second memory cache 450. In some circumstances, a redirection tile (e.g., Type==MODE_EXTEND) can provide a memory address location of an extended immediate tile having a larger tile size that accommodates open order data (e.g., cell access nodes) that exceeds a maximum order capacity for tiles of a given active order region 412 or the inactive order region 452. In other circumstances, a redirection tile (e.g., Type==MODE_COLLISION) can provide respective memory address locations for two or more immediate tiles in the free heap buffer 454 that collide at the same hash key location in the sparse hash array of the inactive order region 452.

At block 940, the cache manager 152 gets the memory address location for the immediate tile in the free heap buffer 454 of the second memory cache 450 from the redirection tile. In some embodiments, the cache manager 152 reads a redirection tile from the internal memory cache 156 and obtains a memory address location contained in the redirection tile for a given symbol, side, and price (“SSP”) of the target immediate tile. In some embodiments, the cache manager 152 reads a specific memory address or other address information for locating the target immediate tile from the body portion of the redirection tile. In some other embodiments, the cache manager 152 may read the specific memory address or other address information from the header portion of the redirection tile. An advantage of reading the address information from the header portion of a redirection tile is that the cache manager is not required to load the redirection tile in its entirety (e.g., the header and body portions) into the internal memory cache 156 before starting to fetch the immediate tile referenced by the address information in the header portion.

At block 950, the cache manager 152 fetches the immediate tile from the free heap buffer 454 at the memory address location provided by the redirection tile and loads the immediate tile into the internal memory cache 156 of the cache manager.

At block 960, the cache manager 152 verifies the contents of the immediate tile as described above, e.g., price, symbol, symbol.

FIGS. 10A-10D are schematic diagrams that illustrate examples of retrieving different types of tiles according to the method of FIG. 9. As discussed above, different tile types can be stored in the multi-level memory cache 160 described herein. In particular, an immediate tile contains open order data (e.g., cell access nodes) that represent multiple buy-side or sell-side orders for a financial instrument, while a redirection tile contains at least one address to access a memory location of an immediate tile elsewhere in the multi-level memory cache 160, such as a free heap buffer or other unstructured memory region.

FIG. 10A illustrates a second memory cache 450 provisioned with a sparse hash array representing an inactive order region 452 and a free heap buffer 454 or other type of unstructured memory. Although the sparse hash array 452 and the free heap buffer 454 are shown as being included in a single cache 450, persons skilled in the art will recognize the sparse hash array and the free heap buffer can be implemented in separate caches. The sparse hash array 452 represents an inactive order region that can contain immediate tiles and redirection tiles, each immediate tile and redirection tile being respectively associated with a symbol, side, and price (“SSP”) that falls outside a respective active order region of the first memory cache 410. The free heap buffer 454 is a region of unstructured memory capable of storing immediate tiles at memory address locations that are referenced by respective redirection tiles. Although not shown in FIG. 10A, the active order regions of the first memory cache may also store both immediate tiles and redirection tiles that reference other immediate tiles in the free heap buffer 454.

FIG. 10B illustrates an example for retrieving immediate tiles 1010a, 1010b, 1010c (collectively immediate tiles 1010) in one external memory access from a sparse hash array 452 of a second memory cache 450 according to an embodiment. As discussed above in connection with FIG. 3, immediate tiles contain open order data, e.g., in the form of cell access nodes, that represent all orders to buy or sell a given stock or other financial instrument at a given price. Thus, the cache manager 152 can read immediate tiles 1010 directly from the sparse hash array 452 into the internal memory cache (e.g., 156 of FIG. 2) in a single memory access for immediate verification (e.g., block 960 of FIG. 9) and subsequent use.

FIG. 10C illustrates an example for retrieving extended immediate tiles 1022 in two external memory accesses from the free heap buffer 454 of a second memory cache 450 according to an embodiment. In a preferred embodiment, tiles are defined to have a predetermined size and are thus capable of representing orders to buy or sell a given financial instrument up to a maximum order capacity. In the event that the number of orders for a given symbol, side, and price exceeds the maximum order capacity, the cache manager 152 can create an extended immediate tile 1022 for the given symbol, side, and price for storage in the free heap buffer 452 of the second memory cache 450. An extended immediate tile 1022 can have the same data structure as the tile shown in FIG. 3, except that the body portion 320 can have a larger size to accommodate all of the open order data (e.g., cell access nodes) for the given symbol, side, and price.

To locate the extended immediate tile 1022 in the free heap buffer 454, the cache manager 152 can store a redirection tile 1024, sometimes referred to herein as an extended redirection tile (e.g., Type=MODE_EXTENDED), at a tile location in the first memory cache or the second memory cache for the particular symbol, side, and price of the extended tile. As shown schematically in FIG. 10C, an extended redirection tile 1024 can include a memory address along with the extended tile size that points to the extended immediate tile 1022 in the free heap buffer 454.

Thus, as discussed above in connection with FIG. 9, the cache manager 152 can access an extended immediate tile 1022 in at most two external memory accesses. In particular, the cache manager 152 may initially fetch the extended redirection tile 1024 from the sparse hash array of the inactive order region 452 and then fetch the extended immediate tile 1022 at the memory address in a free heap buffer 454 specified in the extended redirection tile 1024. Once the extended immediate tile 1022 is loaded and verified, the cache manager 152 can access the immediate tile 1022 within the internal memory cache (e.g., 156 of FIG. 2) with minimal delays in order to obtain open order data (e.g., one or more cell access nodes) for multiple open orders having the same symbol, side, and price.

FIG. 10D illustrates an example for retrieving collision immediate tiles 1032a and 1032b in two external memory accesses from the free heap buffer 454 of the second memory cache 450 according to an embodiment. As discussed above in connection with FIG. 8, the cache manager 152 can generate a hash key as an index for locating a tile within the sparse hash array 452 for a given symbol, side, and price. The hash key algorithm is presented herein for minimizing the risk of hash key collisions for the same tile location within the sparse hash array of the second memory cache. However, there may be instances in which a hash key collision does occur between two or more tiles 1032a and 1032b. Such instances are more likely to occur where the target price of the tile is not centered around round prices (e.g., $1.00, $15.00, $300.00, etc.)

In the event that a hash key index generated for particular symbol, side, and price collides with the hash key index for a tile location currently occupied by another tile for a different symbol, side, and price, the cache manager 152 can relocate the immediate tiles 1032a and 1032b having the same hash key index to separate memory locations within the free heap buffer 454 of the second memory cache 450.

To locate the immediate tiles 1032a and 1032b relocated to the free heap buffer 454, the cache manager 152 can store a redirection tile 1034, sometimes referred to herein as a collision redirection tile (e.g., Type=MODE_COLLISION), in the sparse hash array 452 at the tile location indexed by the common hash key of the relocated tiles. As shown schematically in FIG. 10D, a collision redirection tile 1034 can include a memory address that points to each of the immediate tiles 1032a and 1032b involved in the hash key collision in the free heap buffer 454.

Thus, as discussed above in connection with FIG. 9, the cache manager 152 can access an immediate tile involved in a hash key collision in at most two external memory accesses. In particular, the cache manager 152 may initially fetch the collision redirection tile 1034 from the sparse hash array 452 and then fetch one of the immediate tiles (i.e., 1032a or 1032b) involved in the hash key collision at a memory address in a free heap buffer 454 specified in the collision redirection tile 1034 for the given symbol, side, and price tuple. Once the immediate tile 1032a or 1032b is loaded and verified, the cache manager 152 can access the immediate tile 1032a or 1032b within the internal memory cache (e.g. 156 of FIG. 2) with minimal delays in order to obtain open order data (e.g., one or more cell access nodes) for multiple open orders having the same symbol, side, and price.

Changes in market conditions can cause price behavior of orders on a given side of a financial instrument to shift throughout a trading day. For example, if the best price for a given side and financial instrument starts trending either upward or downward, the cache manager 152 may gradually adjust the sequence of price-consecutive tiles, and thus the price range of the active order region in the first memory cache to reflect such price behavior.

In particular, the cache manager may invalidate one or more tiles from one end of a price-consecutive active order region of the first memory cache of the multi-level memory cache to make space available at the opposite end of the active order region for adding one or more other tiles. The tiles added to the active order region may include newly created tiles or relocated tiles from the inactive order region of the second memory cache of the multi-level memory cache. The tiles added to the active order region may represent orders having more aggressive prices or less aggressive prices, depending on the trending direction of the price behavior. For buy-side orders, higher prices are considered more aggressive than lower prices. Conversely, for sell-side orders, lower prices are considered are considered more aggressive than higher prices.

FIG. 11 is a flow diagram that illustrates a method 1100 for gradually adjusting a price-consecutive tile sequence within an active order region of the first memory cache to include more aggressive price tiles according to an embodiment. For buy-side orders, more aggressive prices refers to higher prices. Conversely, for sell-side orders, more aggressive prices refers to lower prices. The method 1100 can be implemented by the cache manager 152 described in connection with FIGS. 1 and 2.

At block 1110, the cache manager 152 detects prices for orders to either buy or sell a financial instrument trending more aggressively. For buy-side orders, the cache manager 152 may detect an increase in the volume of buy-side orders at or above the best bid price. For sell-side orders, the cache manager 152 may detect an increase in the volume of sell-side orders at or below the best ask price.

At conditional block 1120, the cache manager 152 determines whether the least aggressive price tile within the active order region of the first memory cache contains any open order data (e.g., cell access nodes) that represents at least one order to either buy or sell the financial instrument at the least aggressive price (e.g., symbol, side, price). For buy-side orders, the least aggressive price tile is a tile having the lowest bid price in the price-consecutive active order region. For sell-side orders, the least aggressive price tile is a tile having the highest bid price in the price-consecutive active order region. In some embodiments, the cache manager can reference a symbol registry (e.g., 154 at FIG. 1) that may include a memory lookup table that indicates whether or not a tile contains any open order data that corresponds to at least one order to buy or sell a stock or other financial instrument at different price levels. Referring to FIG. 3, the memory lookup table may indicate that a tile for a particular price contains open order data if the tile includes at least one cell access node (e.g., access node 325 of FIG. 3) assigned to a corresponding open order cell (e.g., cell 330 of FIG. 3) under one of the priority lists (e.g., priority lists 329 of FIG. 3).

If the least aggressive price tile is determined at conditional block 1120 to be empty having no open order data, the process continues to block 1140. At block 1140, the cache manager 152 may overwrite the least aggressive price tile in the active order region with a new most aggressive price tile. The cache manager 152 may create a new most aggressive price tile having a price that exceeds the most aggressive price tile by one tick. For buy-side orders, the newly created most aggressive price tile has a bid price one tick higher than the highest bid price in the price-consecutive active order region. For sell-side orders, the newly created most aggressive price tile has an ask price one tick lower than the lowest ask price in the price-consecutive active order region.

Conversely, if the least aggressive price tile is determined at conditional block 1120 to include open order data that represents at least one order to either buy or sell the financial instrument at the least aggressive price (e.g., lowest/worst bid price within the active order region), the process may continue to blocks 1130 and 1140. At block 1130, the cache manager 152 copies the least aggressive price tile from the active order region of the first memory cache to the inactive order region of the second memory cache. As described above, the inactive order region can be implemented in the form of a sparse hash array. At block 1140, the cache manager 152 may overwrite the least aggressive price tile in the active order region with a newly created most aggressive price tile created. As discussed above, the cache manager 152 may create a new most aggressive price tile having a price that exceeds the most aggressive price tile by one tick. For buy-side orders, the newly created most aggressive price tile has a bid price one tick higher than the highest bid price in the price-consecutive active order region. For sell-side orders, the newly created most aggressive price tile has an ask price one tick lower than the lowest ask price in the price-consecutive active order region.

FIGS. 12A and 12B are schematic diagrams illustrating an example of gradually adjusting a price-consecutive tile sequence within the active buy order region of the first memory cache to include more aggressive price tiles having higher bid prices. This process is sometimes referred to herein as “crawling hotter.”

In particular, FIG. 12A illustrates an example of an active order region 1210 within a first memory cache (e.g., 410 of FIG. 4) that stores consecutive bid prices tiles for buy-side orders of a given financial instrument having a symbol index SYM_0. The price range of the consecutive bid prices tiles span between a most aggressive (highest) bid price of $315.71 to a least aggressive (lowest) bid price of $312.41. As shown in the illustrated example, the active order region 1210 can be implemented as a circular buffer array having a wrap index that corresponds to a tile 1212 having order data at the lowest bid price. The best bid price in this example is $315.41. Although the bid prices are shown in a currency format to aid in understanding, prices are preferably represented as ticks.

To gradually adjust the price range of the active buy order region to include a newly created most aggressive price tile 1214 having a higher bid price at $315.72, the cache manager 152 determines whether the least aggressive price tile 1212 is empty (e.g., at conditional block 1120 of FIG. 11). In this example, the least aggressive price tile 1212 is determined to contain open order data for at least one buy-side order at the lowest bid price and thus not empty. Thus, as shown in FIG. 12B, the cache manager 152 copies the least aggressive price tile 1212 from the active order region 1210 of the first memory cache 410 to a free tile location 1232 in the sparse hash array of the inactive order region 1230 of the second memory cache 1220 (e.g., at block 1130 of FIG. 11). The cache manager 152 can then overwrite the tile location vacated by the least aggressive price tile 1212 with the newly created most aggressive price tile 1214 having a higher bid price of $315.72. In some circumstances, the new most aggressive price tile 1214 may be a redirection tile that points to an immediate tile in the free heap buffer 1240 of the second external memory cache 1220.

FIG. 13 is a flow diagram that illustrates a method 1300 for gradually adjusting a price-consecutive tile sequence within an active order region of the first memory cache to include less aggressive price tiles according to an embodiment. For buy-side orders, less aggressive prices refers to lower prices. Conversely, for sell-side orders, less aggressive prices refers to higher prices. The method 1300 can be implemented by the cache manager 152 described in connection with FIGS. 1 and 2.

At block 1310, the cache manager 152 detects prices for orders to either buy or sell a financial instrument trending less aggressively. For buy-side orders, the cache manager 152 may detect an increase in the volume of buy-side orders below the best bid price. For sell-side orders, the cache manager 152 may detect an increase in the volume of sell-side orders above the best ask price.

At conditional block 1320, the cache manager 152 determines whether the inactive order region of the second memory cache contains a tile having a price that exceeds the least aggressive price tile by one tick to serve as a new least aggressive price tile. For buy-side orders, the least aggressive (or worst) price tile has the lowest bid price within the price-consecutive active order region. For sell-side orders, the least aggressive price tile has the highest ask price within the price-consecutive active order region.

If the cache manager 152 determines at conditional block 1320 that the inactive order region contains a tile having a price that exceeds the least aggressive price tile by one tick, the process proceeds to block 1330 and 1340. At block 1330, the cache manager 152 copies the new least aggressive price tile from the inactive order region of the second memory cache (e.g., a sparse hash array) and overwrites the most aggressive price tile in the active order region of the first memory cache (e.g., a circular buffer array) with the new least aggressive price tile. At block 1340, the cache manager 152 marks the space vacated by the new least aggressive price tile in the inactive order region of the second memory cache as free. In some embodiments, the tile location can be marked free by overwriting the tile location with a special tile having a header portion in which the type field indicates that the space is free (e.g., Type==“MODE_FREE”).

Conversely, if the cache manager 152 determines at conditional block 1320 that the inactive order region does not contains a tile having a price that exceeds the least aggressive price tile by one tick, the process proceeds to block 1350. At block 1350, the cache manager 152 overwrites the most aggressive price tile in the active order region with a newly created least aggressive price tile. For buy-side orders, the cache manager 152 creates the new least aggressive price tile with a bid price one tick lower than the lowest bid price in the price-consecutive active order region. For sell-side orders, the cache manager 152 creates the new least aggressive price tile with an ask price one tick higher than the highest ask price in the price-consecutive active order region.

FIGS. 14A and 14B are schematic diagrams illustrating an example of gradually adjusting a price-consecutive tile sequence within the active buy order region of the first memory cache to include less aggressive price tiles having lower bid prices. This process is sometimes referred to herein as “crawling colder.”

In particular, FIG. 14A illustrates an example of an active order region 1410 within the first memory cache that stores consecutive bid prices tiles for buy-side orders of a given financial instrument having a symbol index SYM_0. The price range of the consecutive bid prices tiles span between the most aggressive (highest) bid price of $315.71 to the least aggressive (lowest) bid price of $312.41. As shown in the illustrated example, the active order region 1410 can be implemented as a circular buffer array having a wrap index that corresponds to the lowest bid price tile 1412. The best bid price in this example is $315.41. Although the bid prices are shown in a currency format to aid in understanding, prices are preferably represented as ticks.

To gradually adjust the price range of the active buy order region to include a new least aggressive price tile having a lowest bid price at $312.40, the cache manager 152 determines whether the sparse hash array of the inactive order region 1430 of the second memory cache 1420 contains a tile 1432 having a lower bid price by one tick than the current lowest bid price tile 1412 in the active order region at the wrap index (e.g., at conditional block 1320 of FIG. 13). In this example, the cache manager 152 locates a tile 1432 in the sparse hash array of the inactive order region 1430 for the given symbol and side with a bid price of $312.40, one tick less than the current lowest bid price tile 1412 at $312.41. Thus, as shown in FIG. 14B, the cache manager 152 copies the new lowest bid price tile 1432 from the sparse hash array of the inactive order region 1430 and overwrites the highest bid price tile 1416 in the active order region 1410 (e.g., at block 1330 of FIG. 11). In this example, the highest bid price 1416 has a higher price ($315.71) than the current best bid price (e.g., $315.41). Accordingly, the highest bid price tile 1416 in the active buy order region 1410 can be assumed to be empty and available to be overwritten as any orders at the highest bid price above the current best bid price would have been matched immediately.

In the event that the sparse hash array of the inactive order region 1430 does not contain the target tiles, the cache manager 152 can create a new tile having the lowest bid price by one tick at $312.40 and overwrite the highest bid price tile 1416 in the active order region with the newly created tile. The cache manager 152 can also update the symbol registry 154 to change the wrap index for the circular buffer array of the active order region to correspond to the tile location of newly added lowest bid price tile. In some circumstances, the new least aggressive price tile may be a redirection tile that points to an immediate tile in the free heap buffer 1440 of the second external memory cache 1420.

In U.S. markets, the minimum price variation between prices above one dollar is often one cent ($0.01), while the minimum price variation between prices less than one dollar is often one hundredth of a cent ($0.0001). Instead of representing currencies in decimal format, most financial markets represent prices as integers having an implied decimalization, referred to herein as ticks. For example, with an implied decimalization of 4, the integer sequence for consecutive allowable prices between $0.9998 to $1.02 would be 9998, 9999, 10000, 10100, 10200. Accordingly, the integer sequence is not consecutive after the price precision level of $1.00 (10000) due to the change in minimum price variation.

As discussed above, each active order region within the first memory cache is organized in a price-consecutive manner. Accordingly, to store or fetch a tile for a target price, the cache manager 152 converts the target price to a corresponding tick in a consecutive integer sequence for locating the appropriate address of a tile in the circular buffer array. However, as discussed above, the integer sequence may not be a consecutive integer sequence due to changes in minimum price variation across different price precision levels.

FIGS. 15A-15B is a flow diagram that illustrates a method 1500 for converting a target price to a tick with a consecutive integer sequence regardless of changes in minimum price variation between consecutive prices according to an embodiment. The method 1500 can be implemented by the cache manager 152 described in connection with FIGS. 1 and 2.

At block 1510, the cache manager 152 receives a target price in the form of a tick (i.e., an integer having a first implied decimalization). The following table is example list of target price ticks, each having an implied decimalization of 4 relative to a price precision level of $1.00. As shown in the table below, tick count increases consecutively by one tick up to the price precision level of one dollar. Above the price precision level of one dollar, the tick count increases by 10 ticks, resulting in a non-consecutive tick sequence.

Target Price
Minimum Price Variation
Tick

$0.9998
$0.0001
9998

$0.9999
$0.0001
9999

$1.00
$0.01
10000

$1.01
$0.01
10100

At conditional block 1515, the cache manager 152 determines whether the target price tick is above a price precision level. The price precision level is a price at which the minimum price variation changes. As shown in the example above in Table I, the price precision level is one dollar ($1.00) with a minimum price variation equal to one hundredth of one cent $0.0001 below one dollar and a minimum price variation equal to one cent ($0.01) above one dollar.

If the target price tick is below the price precision level, the process proceeds to block 1555. At block 1555, the target price tick may remain unchanged for use as either (i) an index into the active order region of the first memory cache or (ii) input for generating a hash key as an index into the inactive order region of the second memory cache.

Conversely, if the target price tick above the price precision level, the process proceeds to blocks 1520 through 1555.

At block 1520, the cache manager 152 determines the minimum price variation defined above the price precision level. According to the example shown in the table above, the minimum price variation above $1.00 is one cent ($0.01) or an implied decimalization of 2 decimal places.

At block 1525, the cache manager 152 converts the target price tick from the first implied decimalization format to a second implied decimalization format that corresponds to the minimum price variation above the price precision level. According to the example shown in the table above, the cache manager 152 may convert the target price tick of $1.01 from 10100 to 101.

At block 1530, the cache manager 152 determines the total number of ticks that can be represented in the second implied decimalization format below the price precision level. According to the example shown in the table above, the total number of ticks that can be represented with an implied decimalization of 2 decimal places below the price precision level of $1.00 is 99 ticks.

At block 1535, the cache manager 152 determines the total number of ticks by which the target price tick in the second implied decimalization format (i.e., determined at block 1525) exceeds the total number of ticks that can be presented in the second implied decimalization format below the price precision level (i.e., determined at block 1530). According to the example shown in the table above, the target price tick of $1.01 with an implied decimalization of 2 decimal places (i.e., 101 ticks) exceeds the total number of ticks that can be presented with an implied decimalization of 2 decimal places below $1.00 (i.e., 99 ticks) is 2 ticks.

At block 1540, the cache manager 152 determines the minimum price variation defined below the price precision level. According to the example shown in the table above, the minimum price variation defined below the price precision level of $1.00 is one hundredth of one cent ($0.0001).

At block 1545, the cache manager 152 determines the total number of ticks that can be represented in a third implied decimalization format that corresponds to the minimum price variation defined below the price precision level (i.e., determined at block 1540). According to the example shown in the table above, the minimum price variation defined below the price precision level of $1.00 is one hundredth of one cent, and therefore an implied decimalization of 4 decimal places. With an implied decimalization of 4, the total number of ticks that can be represented below $1.00 is 9999 ticks.

At block 1550, the cache manager 152 converts the target price tick from the second implied decimalization format to the third implied decimalization format. In particular, this conversion can be performed by adding the total number of ticks that can be represented in the third implied decimalization format below the price precision level (i.e., determined at block 1545) to the total number of ticks by which the target price tick exceeds the price precision level in the second implied decimalization format (i.e., determined at block 1535). According to the example shown in the table above, the modified target price tick for $1.01 can be represented as 10001 ticks (i.e., 2+9999).

Thus, as shown in the table below, the foregoing method can convert a target price to a tick within a consecutive integer sequence regardless of changes in minimum price variation between consecutive prices.

Target Price
Minimum Price Variation
Tick

$0.9998
$0.0001
9998

$0.9999
$0.0001
9999

$1.00
$0.01
10000

$1.01
$0.01
10001

At block 1555, the cache manager 152 can use the target price tick resulting at block 1550 as either (i) an index into the active order region of the first memory cache or (ii) input for generating a hash key as an index into the inactive order region of the second memory cache.

Another methodology for reducing the overall latency of an electronic trading system may be accomplished through opportunistic pre-fetching of tiles from the external multi-level memory cache. For example, the cache manager 152 may fetch a tile from external memory in response to a request for order data for a given symbol, side, and price, such as the best bid or ask price. Once the tile is loaded into internal cache memory, the cache manager 152 can simply access the loaded tile in response to subsequent order data requests for the same symbol, side, and best price. However, once order data from the loaded tile is exhausted (i.e., all open orders have been filled or canceled), another tile will need to be loaded from external memory to continuing matching orders at a second-best price for the given symbol and side.

To reduce overall latency of the electronic trading system, the cache manager 152 can be configured to pre-fetch a second tile into the internal memory cache 156 prior to exhaustion of a first tile in the internal memory cache 156. In a preferred embodiment, the cache manager 152 can monitor which tiles contain open order data representing at least one order for a given symbol, side, and price and thus not empty. Thus, rather than simply fetch the next tile having the second-best price from external memory, the cache manager 152 can be configured to pre-fetch a tile at the next best price that is not empty. This avoids fetching one or more tiles from external memory that may not have any open order data and unnecessary delay.

FIG. 16 is a flow diagram that illustrates a method 1600 of pre-fetching a tile in advance according to an embodiment. The method 1600 can be implemented by the cache manager 152 described in connection with FIGS. 1 and 2.

At block 1610, the cache manager 152 can track whether each tile among the consecutive price tiles of an active order region for a given symbol and side contains open order data representing at least one open order. In some embodiments, the cache manager 152 can track this information in a memory lookup table, an example of which is shown below. The populated tiles containing open order data are marked “YES” in the table below.

Tile (SSP)
Open orders?

$10.00
YES

$10.01
NO

$10.02
NO

$10.03
YES

$10.04
YES

At block 1620, the cache manager 152 can access the memory lookup table while fetching a first tile having a target price.

At block 1630, the cache manager 152 can determine from the memory lookup table a tile having the next best price that is closest to the target price of the requested tile. For example, assuming that the target price of the requested tile is $10.00, the cache manager 152 can access the table entry for the next best price of $10.01.

At conditional block 1640, the cache manager 152 can determine from the memory lookup table whether the next best price tile contains any open order data representing at least one open order for that symbol, side, and price. If the next best price tile is determined at conditional block 1640 to contain open order data, the process can continue to block 1650. At block 1650, the cache manager 152 can prefetch the next best price tile from the active order region. In some embodiments, the cache manager 152 can initiate prefetch before the first tile has even started to return from external memory. While matching logic is operating on the first tile, the second tile has time to load at the internal memory cache. Conversely, if the next best price tile is empty, the process can return to block 1630 to locate the next best price tile closest to the target price tile.

In this example, the first two tiles having a symbol, side, and price closest to the target price of $10.00 are empty. Accordingly, the cache manager 152 prefetch a populated tile having the fourth-best price and avoid unnecessarily prefetching the empty tiles having the second-best and third-best prices at $10.01 and $10.02.

An advantage of pre-fetching tiles is that the process can have a minimum impact on system performance, particularly where the pre-fetch logic is performed during an idle time.

FIG. 17 is a schematic diagram illustrating a processing unit for optimizing the use of cache space within the multi-level memory cache 160a, 160b, 160c (collectively or individually 160) according to an embodiment. In some embodiments, the processing unit, referred to herein as a fitter tool 1710, may be implemented as a hardware component of any of the electronic trading systems disclosed herein. In some other embodiments, the fitter tool 1710 may be implemented as a separate software processor (e.g., a CPU-based processor that may execute software),

As discussed above in connection with FIG. 4, the amount of physical DRAM that can be allocated to the first memory cache is a finite amount in the product. Furthermore, the per-symbol usage of the first memory cache may be limited to only a certain range of prices at any one time. This price range may be further limited by increasing tile sizes, thus requiring more of the limited physical DRAM for each symbol. Additionally, any crawling adjustments to move the price level bounds of the respective active order regions for each symbol within the first memory cache may incur a processing cost to execute the crawling operation, which may impact performance. As such, the fitter tool may set the foregoing configurable variables for each symbol to maximize the efficiency of the respective active order regions for each symbol.