Part 4: Order Book

Summary

High Level View

The Fpga Ip described in this document is of a simple OrderBook implementation that is part of the Smart Fpga Nic (https://fpganow.com/index.php/smart-fpga-nic/).  This Ip was written so that it can be used in other projects including LabVIEW Fpga based projects, and traditional Verilog/VHDL projects with the use of the LabVIEW FPGA IP Export Utility (https://www.ni.com/en-us/shop/software/products/labview-fpga-ip-export-utility.html) provided by NI (formerly National Instruments).

Integration

The following diagram shows where this OrderBook Ip fits in with the Smart Fpga Nic.

Figure 1

The OrderBook IP accepts a ‘Command’ per clock cycle and produces one ‘Result’ per clock cycle. The OrderBook Ip uses traditional handshake signals such as ‘Input.Valid’ and ‘Ready.for.Input’ to avoid dropping Commands and Results.

Interface

Here is a diagram outlining how the signals of the Command and Result fit in to the OrderBook Ip.

Figure 2

What is a Command?

A Command is made up of the following control and data signals/wires:

  • [Boolean] [in] OrderBook.Command.Valid
  • [Boolean] [out] Ready.For.OrderBook.Command
  • [Boolean] [in] Reset
  • [in] OrderBook.Command
    • Type
      • Add Order
      • Order Executed
      • Order Reduced
      • Modify Order
      • Delete Order
      • Get Top of Book
      • Get All Orders
    • Side
    • Order Id
    • Quantity
    • Symbol
    • Price
    • Executed Quantity
    • Cancelled Quantity

Figure 3

What is a Result?

A Result is made up of the following signals/wires:

  • [Boolean] [out] OrderBook.Result.Valid
  • [out] OrderBook.Result
    • OrderBook.Result
    • Order Id
    • Side
    • Quantity
    • Symbol
    • Price

Figure 4

Examples

Whenever a normalized Market Data message comes in from the Arbitrator, the Arbitrator uses the signals/wires described above to construct and send a new Command to the OrderBook Core. The OrderBook processor then acts on this Command and if there is a result – such as is the case with the ‘Get.Top’ and ‘Get.All’ commands – it will output the results using the Result signals described above and shown in Figure 4. If there are multiple results, it will output each value on a separate clock cycle, with each value using only one clock cycle.

The Results listener is always waiting for a result by monitoring the OrderBook.Result.Valid signal.

Add Order Example

  1. Wait until the OrderBook is ready for a new Command by checking the ‘Ready.for.Command’ signal
  2. Set the following signals:
    1. Command.Valid <= true
    2. Reset <= false
    3. Command
      1. Type <= Add Order
      2. Side <= Buy
      3. Quantity <= 100
      4. Symbol <= MSFT
      5. Price <= 305.00
  3. Wait until ‘Ready.for.Command’ is set to true again.

Figure 5

Get Top of OrderBook Example

Now for the results, first you have to have sent a Command that generates a result, such as the ‘Get Top’ or ‘Get All Orders’ Command.Type.

  1. Wait until the OrderBook is ready for a new Command by checking the ‘Ready.for.Command’ signal
  2. Set the following signals:
    1. Command.Valid <= true
    2. Reset <= false
    3. Command
      1. Type <= Get.Top
      2. Symbol <= MSFT
  3. Wait until Result.Valid is set to true
  4. Read the details of the order at the top of the order book, including:
    1. Order Id
    2. Side
    3. Quantity
    4. Symbol
    5. Price

Figure 6

Data Types

Command Signal Descriptions

  • OrderBook.Command.Valid
  • Ready.For.OrderBook.Command
  • Reset
    • This is your generic FPGA ‘Reset’ command, it will clear any state inside the OrderBook, including the number of buy and sell orders. After this command completes, you will have an empty order book that is awaiting a new command
  • OrderBook.Command
    • Type
      • Add
        • Inserts a new order into the OrderBook by using the Insertion Sort algorithm. It starts at index 0, and iterates up to the length of the OrderBook. If the price of the new order should go at the current index, it is inserted and each of the remaining items are shifted back by one element. Of course, the total # of orders is also incremented.
      • Execute
        • There are two types of executions – execute fully and execute partially. It scans through the orderbook and when it encounters the order which matches the OrderId, it either removes the current order or modifies it. Removing an order is accomplished by maintaining to separate addresses – one for read and one for write. As iteration over the orderbook occurs, normally both are incremented, but if the order is to be removed only the read address is incremented. And finally when the final element is read, the numbers of orders is decremented by one.
      • Reduce
        • The OrderBook iterates over all orders and upon reaching a matching OrderId, it writes the new values that are passed with the Reduce command and stops iterating.
      • Modify
        • Same thing as Reduce, just that modify is able to modify price in addition to size.
      • Delete
        • This deletes an order with the matching OrderId. The order is removed by not incrementing the write address while iterating through the orders where the OrderId matches.
      • Get Top of Book
        • Returns just one order – the best ask or the best bid depending on what the side is in the command
      • Get All Orders
        • Returns all orders, in properly sorted order.
    • Side
      • The side comes in as the ASCII code for the letter ‘B’ or ‘S’, if the data is in BATS format.
    • Order Id
      • The BATS specification sends an Order ID in the format of 8 ASCII characters, which fits nicely into a 64 bit integer.
    • Quantity
      • The BATS specification sends the price as an decimal number multiplied by 100 to move the decimal places out.
    • Symbol
      • An unsigned 32-bit integer.
    • Price
      • The BATS specification for the price are an unsigned integer with 4 implied decimal places.
    • Executed Quantity
      • An unsigned 32-bit integer.
    • Cancelled Quantity
      • An unsigned 32-bit integer.

Result Signal Descriptions

  • OrderBook.Result.Valid
    • Specifies if the output signals are valid. Should remain true for only one clock cycle per valid value/result.
  • OrderBook.Result
    • Result
      • A flag with the value of Found or Not.Found. Keeping things simple for now…
    • Order Id
      • The OrderId of the result – if a result was found.
    • Side
      • Buy = ‘B’, Sell = ‘S’
    • Quantity
      • Integer
    • Symbol
      • ASCII representation of ticker/symbol, right-justified\
    • Price
      • Price that conforms to the BATS standard – i.e. an integer that has to be divided by one hundred, last 2 digits are decimal points.

Core Usage

If you are experienced with FPGAs and the Xilinx toolchain, use the following VHDL wrapper and Xilinx Design Checkpoint:

If you are a LabVIEW FPGA developer, just open the following VI for an example where I wire up the inputs and outputs to a LabVIEW FPGA FIFO:

You can also open any vi in the tests folder. That’s right, Test-Driven Development not only helps the developer (me) develop faster and more accurate, it also helps you – my user – quickly understand and start using my code. See any vi in this folder:

How can you test it?

If you are a Verilog/VHDL FPGA developer, create a testbench that uses the following ip like so:

https://github.com/fpganow/arty_bats/blob/main/vivado/src/hdl/test/orderbook_tb.v

If you are a LabVIEW FPGA developer, open the test runner referenced above and run all of the tests: (make sure you set the FPGA to Simulation mode)

https://github.com/fpganow/arty_bats/blob/main/labview/host/orderbook/test.orderbook.vi

Or, open an individual test such as the “Get.Top” test. Notice it is very simple, it adds 4 orders and then queries for the best order.

https://github.com/fpganow/arty_bats/tree/main/labview/host/orderbook/tests

VHDL Source Code?

You will have to purchase a license to the LabVIEW FPGA IP Export Utility with the “VHDL” option selected, which retails for $2,723.00 as of today (October 11th, 2021)

https://www.ni.com/en-us/shop/software/products/labview-fpga-ip-export-utility.html

LabVIEW Simulation

Vivado Simulation