High Frequency Trader

HPS

Our HPS code is relatively simple. It operates in two threads. The first thread reads incoming stock data from stdin and writes it to the FPGA. It also reads trades from the FPGA, and keeps track of the balance and holdings. The second thread updates the VGA display with incoming stock information and portfolio information, which arrives from the internet and from the FPGA. Network data is piped into stdio with the netcat command.

Verilog

Our trading algorithm uses an exponentially weighted moving average and variance in order to make a decision to buy, sell, or hold a given stock. For the math behind both of these, we referred to “Online Algorithms in High-frequency Trading: The challenges faced by competing HFT algorithms” by Loveless, Stoikov, and Waeber. In this paper, the authors describe exponential algorithms for both average and variance that both only require one input per iteration and only one value stored in memory between iterations. This helps to keep each instantiation of the average and variance computation lightweight, which in turn allows us to be more efficient with the resources available on the FPGA such as DSPs. The idea was that if we kept this computation efficient then we could compute for more stocks on the FPGA. The calculation done for the moving average is as follows:

\[X^{AVG}_{0,\alpha} = X_0\]

\[X^{AVT}_{t,\alpha} = (1 - \alpha) X_t + \alpha X^{AVG}_{t-1,\alpha}\]

Before any math is done, the average is initialized to be the value of the first input, \(X_0\). After this, each subsequent average is a sum of some portion of the new input and some portion of the old average. The weight placed on the old average, \(\alpha\), is the smoothing factor and determines how much emphasis the computation places on old data versus new data. In other words, can be thought as of a low-pass filter on new data. In our design, \(\alpha\) is hard-set to a value of \(0.94\). To minimize the number of DSP blocks in use, multiplication with as an operand is optimized to be a shift operation instead. To get \(0.94\) times another operand, we simply take the other operand and subtract it by itself shifted to the right four times. To get \(0.06\) times a different operand (\(1-\alpha\)), we shift the operand by four to the right.

To calculate variance, we follow a format similar to the one we used to calculate the moving average. Instead of initializing the starting value to the first input, the first variance value is set to equal one. After that, the second equation of the following two is used:

\[V_0 = 1\]

\[V_{t,\alpha} = (1 - \alpha)(X_t - X^{AVG}_{t,\alpha})^2 + \alpha V_{t-1,\alpha}\]

Because of our shift optimization for \(\alpha\) as discussed before, the module that calculates average and variance only uses one DSP block per instantiation. The only case where actual signed multiplication is necessary is for calculating the square in the variance equation above. As an aside, because the DSP blocks take in operands of 27 bits in length, we opted to use a fixed point format of 13 integer bits (one for sign) and 14 fractional bits. This afforded us enough precision and enough numerical range to properly capture stock prices.

Trading Algorithm

To implement the trader, we made a K-Nearest Neighbors algorithm (KNN). The algorithm's intention is to catch corners in the current trend for a stock. Due to the speed operation, we are using the prior 60 seconds as the training group for comparison The algorithm operates as follows:

Collect 60 seconds and thus 60 instances of stock value at start up. During that collection, take a simple 1 instance Manhattan distance between the current price and the opening price at the start of 60 seconds.If the distance is negative and is below the lowest distance in the set, set that recorded distance as the lowest for the set. If the distance is positive and is above the highest distance in the set, set that recorded distance as the highest in the set. After 60 instances, make trade decisions based on the current price inflows. If the distance of the new price is negative in relation to the price 60 seconds ago but is above the lowest, buy the stock. If the distance is positive in relation to the price 60 seconds ago but is below the highest, sell the stock. If neither is the case, hold the stock. Add the new price to the set and remove the oldest price recorded. Set the new oldest price as the sample price for the distance.

Our original algorithm was close to the flow diagram in the paper by Arévalo, Andrés & Nino, Jaime & Hernandez, German & Sandoval, Javier. However, their design used much more of a deep-learning algorithm which was beyond our scope. Thus we abstracted away but may still have some similarities to. This KNN algorithm described above was then implemented into hardware on the FPGA.

To explain a bit of the complexity happening in the trader, we made the forward based state machine above which does not show recursion in the state machine. At reset, the system sets all the used registers to zero. This includes distances, prices, trade choice, memory addresses, and state transition variables. Following reset, the machine holds on trades until there is a price change that is inputted by a pio. After a price change, the machine checks to see if the simulation has just begun or not. If it has, then the memory is deemed empty and needs to be written to, thus populating the 60 neighbors in the algorithm. For memory, we are using M10K blocks structured by 256 x 32 blocks (this is based on example 12-16 here). We write both distance and price to memory. In the order seen in the memory, the first index is the price for that specific time instance and the second index is the distance from the 60 second starting price. This pair allocation is followed for all price instances. While populating the initial 60 prices, find the lowest and highest prices in comparison to the sample price and record these distances in a register.

Once the first 60 prices are collected, the algorithm can move onto decisions in the math state. When a new price enters, compare it to the sample price. If the distance of the new price is negative in relation to the price 60 seconds ago but is above the lowest, buy the stock. If the distance is positive in relation to the price 60 seconds ago but is below the highest, sell the stock. If neither is the case, hold the stock. Add the new price to the set and remove the oldest price recorded. Set the new oldest price as the sample price for the distance. Write the price and its distance to memory. This is all contained in the KNN module in the hardware system.

After the trader makes a choice to buy or sell the stock, how does it choose the amount? As we struggled setting exact values, we came up with using percentages. If the trader gives a 0 for a trade, then it is a very weak decision and thus trades 0% of the stock/allowance. If the trader gives a 10 for a trade, then it is a very strong decision and thus trades 100% of the stock/allowance. The middle range fills in by degrees of 10%. Now what determines this percentage. Look at the example below:

This example shows the case for selling. The solid line is the current price trend and the dashed line is the predicted average price for the average unit. We found that at corner changes, the avenge will either transition above or below the trend. This can be used in determining the proximity to a corner change. The example shows that a weak sell occurs when the averager is below the trend as the averager is now expecting the price to fall therefore indicating a higher price rise, and the intersection has passed. A strong sell occurs when the averager is above the trend line as the averager is expecting the price to rise and therefore indicating a lower price, and the intersection has not come yet. This is reversed for buying. Once the trade is determined as being either strong or weak, we can utilize the variation in the price to the averager to determine accuracy of the current guess. We chose the following thresholds for accuracy after manualing analyzing some trends:

• If variation > 450: low accuracy
• Otherwise, if variation > 250: low-medium accuracy
• Otherwise, if variation > 100: medium accuracy
• Otherwise, if variation > 50: high-medium accuracy
• Otherwise: high accuracy

In the final system, we set up 10 parallel traders to perform the described analysis. Each trader was connected to three PIO pins, one pin for the price, one for the trade choice, and one for the amount to move. We also had a VGA subsystem which was utilized by the SoC. This system was derived from example code from the ece5760 course site listed here. These connections are shown in our Qsys. A snippet of our Qsys is shown below.

Other design elements that we scrapped

Initial trading algorithm

We initially tried to use a similar logic flow as the one described in the second referenced paper above. However, we quickly realized that this path was not ideal for the type of flow we were trying to achieve. Our machine needs to evaluate the current flow of data and not the historical trend as that paper was trying to achieve. We also did not have as rigorous of a ML model making it not a great flow for our design. Therefore, we opted to use the algorithm above.

Wallet management on FPGA

We tried to implement the wallet management system on the FPGA to attempt to make the entire system on the FPGA. This proved to be much more troublesome than anticipated. Without using more DSP or making a time consuming divider, the states were becoming very long and complicated. Then when testing, the math would not be correct. It was elected to move this to the SoC to save us on time and resource intensity. This also allows execution time on the FPGA to be much faster than if it had to waste cycles doing division.

Network interface on FPGA

Initially, we planned on implementing the network interface on the FPGA; however, we anticipated numerous issues when sharing the ethernet interface between the FPGA and the HPS. We decided that we would attempt to implement the network interface on the FPGA at the end if we had time, and unfortunately we ran out of time to do so.