A financial instrument trading system, such as a futures exchange, referred to herein also as an “Exchange”, such as the Chicago Mercantile Exchange Inc. (CME), provides a contract market where financial instruments, for example futures and options on futures, are traded. Futures is a term used to designate all contracts for the purchase or sale of financial instruments or physical commodities for future delivery or cash settlement on a commodity futures exchange. A futures contract is a legally binding agreement to buy or sell a commodity at a specified price at a predetermined future time. An option is the right, but not the obligation, to sell or buy the underlying instrument (in this case, a futures contract) at a specified price within a specified time. The commodity to be delivered in fulfillment of the contract, or alternatively the commodity for which the cash market price shall determine the final settlement price of the futures contract, is known as the contract's underlying reference or “underlier.” The terms and conditions of each futures contract are standardized as to the specification of the contract's underlying reference commodity, the quality of such commodity, quantity, delivery date, and means of contract settlement. Cash Settlement is a method of settling a futures contract whereby the parties effect final settlement when the contract expires by paying/receiving the loss/gain related to the contract in cash, rather than by effecting physical sale and purchase of the underlying reference commodity at a price determined by the futures contract, price.
Typically, the Exchange provides for a centralized “clearing house” through which all trades made must be confirmed, matched, and settled each day until offset or delivered. The clearing house is an adjunct to the Exchange, and may be an operating division of the Exchange, which is responsible for settling trading accounts, clearing trades, collecting and maintaining performance bond funds, regulating delivery, and reporting trading data. The essential role of the clearing house is to mitigate credit risk. Clearing is the procedure through which the Clearing House becomes buyer to each seller of a futures contract, and seller to each buyer, also referred to as a novation, and assumes responsibility for protecting buyers and sellers from financial loss due to breach of contract, by assuring performance on each contract. A clearing member is a firm qualified to clear trades through the Clearing House.
Current financial instrument trading systems allow traders to submit orders to buy or sell contracts to an order book database maintained and managed by an exchange which contains data indicative of previously received, but unsatisfied, referred to as “resting”, orders. A match engine is used by the exchange to, for a particular incoming order, search the order book database to identify a suitable counter order, e.g. for the same financial instrument and same or better price as the incoming order, with which to match the incoming order. Stated a different way, a dataset may involve previously received unsatisfied orders, or resting orders. An incoming order is received and the dataset of resting orders is searched for data that would match the incoming order to a resting order, or what may be known as intersecting data. For example a resting buy order and an incoming sell order may be of the same quantity or price of an underlier, and thus have matching or intersecting data. The process by which it is determined if one or more items of one dataset exist in a second dataset may be referred to as determining the intersection of two sets. Mathematically, the intersection of two sets A and B is the set of elements common to A and B.
Set intersection is a basic problem in computer science, and has a variety of applications. For example, Index-ANDing in database query evaluation calculates set intersection of property index tables. There are several established methods for computing set intersection, for example sort based methods, hash based methods, or search tree methods may be used.
In dataset intersection determination, items in a dataset may be compared. These comparisons involve transferring memory into different memory locations and levels. Because of these transfers, and the large amounts of data that may be involved in storing large datasets, numerous transfers may be required to determine all dataset intersections. For example, multiple data transfers may be required to search for an individual value of one item in a dataset, in another dataset. Therefore, if the datasets have thousands, or millions, of items, the determination of dataset intersection may be very computationally intensive.
Typically computers contain on-board RAM memory such as banks of SRAM and DRAM. Typically, the on-board memory forms a memory hierarchy, for instance where SRAM is smaller in capacity but faster to access, and DRAM is larger in capacity but has longer access times. This type of memory hierarchy may exist through multiple levels of storage, RAM and main computer memories. Also, each level of memory may have a minimum amount of memory required to be transferred between levels of memory in a memory transfer. In cache memory, this minimum amount of memory is known as a cache line or block. A cache line, or block, is generally fixed in size typically ranging from 16 to 256 bytes, but may be any size suitable for a particular hardware configuration or application.