-Modern financial mathematics consume more and more computational power and energy. Finding efficient algorithms and implementations to accelerate calculations is therefore a very active area of research. We show why interdisciplinary cooperation such as (CM)2 are key in order to build optimal designs. For option pricing based on the state-of-the-art Heston model, no implementation on dedicated hardware is known, yet. We are currently designing a highly parallel architecture for field programmable gate arrays based on the multi-level Monte Carlo method. It is optimized for high throughput and low energy consumption, compared to GPGPUs. In order to be able to evaluate different algorithms and their implementations, we present a benchmark set for this application. We will show a very promising outlook on future work, including dedicated ASIPs, fixed-point research and real-time applications. Index Terms-finance, benchmarking, hardware acceleration
modern electronic markets, stock prices may change several times within a few milliseconds. Participating traders (that can also be computers) have to evaluate the prices and react very quickly in order to get the highest profit, which requires a lot of computational effort.
In general, running these computations on servers or clusters
with standard CPUs is not feasible due to either long run times
or high energy consumption. Using general purpose graphics
processing units (GPGPUs) as accelerators helps to increase
the speed, but still requires a lot of energy. Besides, at the
moment energy efficiency becomes more and more crucial for
the reason of high energy costs and - even more critical - a
limited supply of energy that can be provided. For example,
in [
This leads to the dilemma of needing faster computations on the one hand and limited energy resources on the other hand. PC
Fig. 1. PC vs. GPGPU vs. FPGA
Moving away from GPGPUs to dedicated hardware
accelerators can help to drastically reduce the power consumption
at the same or even higher throughput. For different
application domains, some comparisons between CPU, GPGPU and
programmable hardware units (field programmable gate arrays,
FPGAs) have already been shown in [
A big challenge is the complexity of many models used to estimate the future price behavior of financial products. In many cases no mathematical closed-form solution exists so that approximation methods like Monte Carlo simulations or the finite difference method must be employed. Though, it is necessary to precisely specify a solution right at the beginning of the design process. Re-designing a nearly finished hardware implementation can require a very high amount of effort. The Center of Mathematical and Computational Modeling (CM)2 of the University of Kaiserslautern is a perfect forum for an interdisciplinary cooperation to tackle this issue.
For this project, we have developed a design methodology that helps to select a feasible parameter set for a hardware accelerator in question that we present in Section III. In order to make implementations transparently comparable, we propose to use standardized benchmark sets - we elaborate on this in Section IV. By applying this methodology and our benchmark, we have developed some reference implementation designs that we show in Section V, together with the status quo of our research and our contributions up to now. In Section VI we give an overview of open issues and what we plan to examine in the future. Section VII concludes the paper.
One is concerned with the evaluation of optimal investment strategies under certain market conditions and the other direction is the pricing of derivatives. The basic idea of pricing options is to assume some sort of model for the underlying price process and take the discounted expected value - under a certain measure - of an option as the option price.
A very common problem treated is the calculation of option prices based on the Black-Scholes model from 1973. This model relies on one stochastic differential equation and describes the price development of an option over the time, depending on market parameters such as riskless interest rate, long term drift and a constant volatility.
Accelerator design for financial mathematics is a very active
research area, and several FPGA implementations have been
published in the past. At the FPL 2008 Woods and VanCourt
[
However, nowadays the Black-Scholes model is no longer
up to date and does not provide an accurate reflection of
modern financial market behaviors, mostly because of the
volatility not being constant in reality. Furthermore,
closedform solutions for the Black-Scholes model exist and it only
has demonstration purposes to apply stochastic solution
methods such as Monte Carlo simulations or the finite difference
method [
In 1993, Steven L. Heston presented a more accurate model
[
The presented speed-ups look very impressive. However, unfortunately we were not able to fairly decide which solution seems to be the most promising for further research and refinements. We will go a bit more into the details of that problem in Section IV.
design under certain constraints is a difficult job. The main reason for this is a large design space. The design space is made up of all possible parameter choices for the design, that means all possible implementation instances.
Most parameters are not adjustable independently, since they are mutually linked. For example, fixing the target architecture to FPGAs one the one hand has a large impact on the selection of suitable algorithms and number systems, and on the other hand affects many performance metrics such as energy consumption, throughput and numerical precision.
Furthermore, the parameters within the design space are in many cases not limited to a single domain of expertise, but require interdisciplinary know-how and decisions. This makes not only the choice of the right values a challenge, but also the evaluation and comparison of different implementations. Besides speedup, more characteristics such as energy efficiency, convergence rate or numerical precision may be very important. This especially holds true for financial mathematics accelerators.
During our research we have seen a lot of papers that show elaborate implementations of a specific algorithm (see Section II) that is not questioned in the papers anymore. However, we claim that the algorithm itself is in fact not the most important selection. An accelerator should be designed to solve a specific problem - it does not matter which algorithm is used, as long as the result is calculated correctly. We therefore propose to distinguish clearly between three terms: the problem that is tackled (what to solve) the employed model (how to solve) the solution (how to build)
To clarify the situation, we use the problem “calculate the price of an option with two barriers for a given duration” as an example. European knock-out barrier options pay a certain amount of money at a fixed maturity time depending on the value of the underlying asset. This amount is only paid when the barrier is not crossed up to the maturity time. If one of the barriers is hit, the option becomes worthless. Thus it needs to be checked whether the barrier was ever hit or not. Figure 2 illustrates the typical random behavior of different realizations of an asset price over the time.
It is obvious that the problem description itself does not yet give any suggestions to the solution. Since the price of an option is tightly coupled to the price of a certain stock at the market, we need a model that provides the stock price behavior. For our chosen example, suitable models are for example the Black-Scholes model (outdated nowadays) or the Heston model. The model in general gives a formal and abstract view of (a certain aspect of) the problem.
The solution finally is a dedicated approach for solving a (modeled) problem. It is characterized by a specific algorithm and its implementation. For evaluating the Heston model, for example, finite difference methods or stochastic Monte Carlo simulations can be used. They may be implemented for example on standard PC clusters, GPGPUs or on FPGAs.
The parameters of the design space can basically be divided into two groups: the algorithmic parameters that are mostly selected by mathematicians, and the implementation parameters determined by the hardware designers. However, as mentioned before correlations exist between several parameters, so that the selection should be optimally made by having a generative exchange between experts of both groups.
For the rest of the paper, we will use the
problem-modelsolution triple “calculate the price of an option with two
barriers for a given duration with the Heston model by using
Monte Carlo methods” as a showcase. Even for that specific
selection, the design space is still very large. An extract of
the related design space is shown in Figure 31. We cannot
explain every parameter here (for details see [
Many attributes can be considered, including speed, accuracy and energy consumption. This becomes even more difficult when it is not clear which algorithm was used. Furthermore, in many cases it is not possible to distinct whether a presented algorithm or implementation has the displayed behavior only with the employed example or in a more general setting. Nevertheless, it is important to be able to compare various algorithms and different implementations, also over various target architectures.
Therefore the need for a benchmark set arises. This set
should be independent of the algorithm and implementation
used. For option pricing in financial mathematics, this need
has already been claimed by Morris and Aubury in 2007 [
With the benchmark set it is possible to use different metrics, like speed (that is now the real time until the results are available), accuracy and power consumption, for the calculations leading to the right (or approximate) result without actually looking at the implementation and the algorithm itself. This allows a fair and publicly traceable comparison of the solution part of the problem/model/solution triplet.
The benchmark itself consists of different combinations
of parameters for the Heston model and for barrier options,
including the prices. The data for the Heston parameters is
taken from different recent publications ( [
For further publications we not only encourage the authors to use the presented benchmark but also give details of the algorithm and the implementation used. Thus it is possible to see where an increase in performance comes from. This is essential in order to evaluate the contribution of a certain result and to find ways to improve it even further. To achieve a higher transparency we will publish the code we used to
MC Simulation
Heston Model (a) Algorithmic parameters
Path-Serial
Path-Parallel
Calculation (b) Implementation parameters analyze the algorithms and the one we implemented on the FPGA.
The benchmark was directly used when comparing different Monte Carlo algorithms with the metric of computational complexity. In our special problem/model combination there are a lot more adjustments to the algorithms than seen in figure 3(a). Many of them can be combined, what leads to a huge design space that now can be handled by applying the benchmark set, so that we haven been able to choose a specific algorithm to be efficiently implemented on dedicated hardware. The multi-level Monte Carlo method provides a better asymptotic convergence behavior, using our benchmark we checked whether this method is beneficial for our application. We will show our first results in the next section.
We have started this cooperation within (CM)2 about one year ago now. Both participating chairs have experience of more than ten years in their respective field of research, so that we can profit from a lot of knowledge in the areas of efficient hardware design respectively stochastics and financial mathematics.
After evaluating the state-of-the-art, we decided to focus on
accelerators for option pricing based on the Heston model - it
seems to be a very promising topic since no implementations
(either on GPGPUs or FPGAs) have been available one year
ago. In contrast to that, the Heston model is already widely
spread within the financial community. From former research
done in the group of Prof. Korn, multi-level Monte Carlo
methods [
A. A New Random Number Generator for Non-Uniform Distributions
amount of random numbers. To obtain the maximum hardware efficiency for our implementation, we have developed a new random number generator for non-uniform distributions tailored to our application.
For our option pricing accelerators, we need two independent, normally distributed random numbers for each time step of a single simulated stock price path. In general, nonuniformly distributed random numbers are generated in two steps: First, a uniform random number generator creates uniformly distributed values, and in a second step this number is transformed into the desired target distribution.
For the uniform random number generation, a lot of research
has already been made leading to efficient and well-proven
implementations, such as the Mersenne Twister MT19937 that
we use. The three main approaches for obtaining non-uniform
distributions are transformation, rejection, and inversion
methods [
For FPGAs, inversion methods are the usual way to go.
They combine many desireable properties: by applying the
respective inverse cumulative distribution function (ICDF),
they transform every input sample x 2 (0; 1) from a uniform
distribution to one output sample y = icdf (x) of the desired
output distribution by using piecewise polynomial
approximation of the ICDF. The works of Woods and VanCourt [
However, both implementations use fixed-point number
representations at the input. This leads to a loss of precision
in the tail regions where the probability of a value lying there
is very low. But these extreme events can have a large impact,
for example for options with barriers it is crucial to know if a
barrier was hit or not, since it completely changes the refund values for a higher step width, this means for a lower Monte
conditions. We have therefore developed a new implementa- Carlo simulation level. In the configuration memory, all model
tion based on floating-point representation that provides the parameters are stored.
same precision over the whole ICDF implementation at much Due to the inherent parallelism of Monte Carlo simulations,
lower hardware costs. This work has been presented at the it is not only feasible but self-evident to instantiate as many
2010 International Conference on ReConFigurable Computing of these circuits as possible on an FPGA in order to increase
and FPGAs (ReConFig) in December in Cancu´n, Mexico [
Our random number converter unit requires only about half The accelerator is implemented on a Xilinx ML-605 evalulaof the area compared to other state-of-the-art implementations tion board equipped with a Xilinx Virtex-6 FPGA. The board by even higher numerical precision. is connected via Gigabit ethernet to a host PC running the
To validate our work, it was crucial to develop a new testing user interface and the program that calculates and sets the methodology, since standardized test suites do not exist for configuration values for the accelerator based on the retrieved non-uniform distributions. This work has been carried out in simulation results. cooperation with Elke Korn who has a lot of knowledge in the Synthesis and benchmarking results will be available soon. field of random numbers. The methodology and the validation We are currently supporting single- and double-precision results for our implementation are also presented in the paper. floating-point computations and are working on a fixed-point Our random numbers did not show any noticeable problems implementation as well. in the stochastic tests and also perfectly passed two different application simulations. VI. OUTLOOK AND FUTURE WORK
B. Fully Parallel Hardware Accelerator between financial mathematics and electrical engineering will
To the best of our knowlege, no hardware implementations be mandatory, since we are planning to research aspects out of option price accelerators based on the Heston model exist of both fields. at the moment. We have therefore started with the first imple- One characteristic of the Monte Carlo method is the inherent mentation, that is nearly finished now. The hardware is fully- capability to parallelize the calculation. It therefore makes no parallel, fully-pipelined and designed for high throughput. difference whether several calculations are done in parallel but slowly or only one calculation is done at high speed, as long Uniform Random Uniform Random as the number of calculations remains equal altogether. At the Number Generator Number Generator moment, our parallel implementation allows simulating one
User Interface time step on many assets simultaneously. The whole procedure
Floating-Point Floating-Point of calculating one time step is fixed on the FPGA and limited Gaussian Converter Gaussian Converter to a single algorithm that is set at design time. price variations volatility One possible way to improve this is to sequentially comHeston StUepnitGenerator Multi-Level pute the basic calculations needed for one time step on a
Monte Carlo Application-Specific Instruction-Set Processor (ASIP) within TeVmapluoerasry CSotaerpse CoMnfeigmuorarytion Controller tchaen FrePdGuAce, tih.ee. rietqiusirerudnatirmeae-apnrodgarallmowmsabtole.caTlchuislatperovcaerdiouures Memory Unit algorithms since the functionality is defined in a corresponding program. It is therefore sufficient to load a different program IEnttheerfranceet ESthtearcnket without changing the hardware. The ASIP will occupy much
less area than the parallel implementation presented in SecFPGA Board Host PC tion V-B, therefore many ASIPs can be instantiated in parallel.
We are currently investigating the necessary instruction set.
Fig. 4. Fully Parallel Accelerator Structure To increase the speed of the implementation even more, the floating-point computation can be replaced by fixed point
Figure 4 shows the structure of one pipelined accelerator computations. In order to do so, errors resulting from the use circuit. In each clock cycle, our unit consumes two normally of fixed-point calculations have to be approximated. This task distributed random numbers, one for the stock price variation will also require both theoretical and practical expertise. and one for the volatility variation. The Heston step generator Besides working on the implementation, the benchmark unit calculates the price and volatility values for the next is very important to evaluate the designs. It will also allow time step based on a multi-level Monte Carlo algorithm. The to research fixed-point solutions with respect to necessary pipeline depth is about 60 stages. In order to maximally precision. Further steps will be to publish the analysis of the utilize the pipelined hardware, it computates one time step algorithms with the benchmark in a journal. To increase the for 60 assets in parallel, before moving to the next time transparency even more, we are currently setting up a web step. The values for the respective time steps are stored in site offering all the program code used to create the analysis. a memory temporarily. The coarse step memory holds interim It will contain an implementation of the multi-level and the crude Monte Carlo algorithm with a focus on the calculation complexity rather than the implementation.
architectures, we are working on a GPGPU implementation. It provides more flexibility and less implementation work than hardware designs do, but also requires higher energy consumption. In order to verify this assumption the implementation is required. The Monte Carlo simulation algorithm for the Heston model is currently carried out as a student work.
eration of financial calculations. This means that hardware or GPGPU accelerators are linked to real-time data streams. This approach seems to be very promising for keeping track with the prices changing quickly in high-frequency trading.
The financial world is running faster and faster and the importance of energy consumption increases drastically. To address this challenge the question of pricing double barrier options in the Heston setting is faced. As the model is more complex than the famous Black-Scholes model and these types of options are path dependent, the algorithms for the calculations are more distinct and also the implementation thereof. In order to be able to cope with the strong connection between the algorithm and the implementation, a combined mathematical and electrical engineering view is needed. (CM)2 provides a perfect framework to do so.
To approximate the pricing process Monte Carlo simulations are used. For a good implementation a fast algorithm with an adjusted implementation thereof is needed. In order to distinguish the different algorithms we have created a benchmark set for double barrier options. This benchmark allows to fairly analyze and compare the diverse algorithms and designs, which is a very important issue due to the big differences in the convergence speed of these algorithms.
choice if implementation time is not considered. It allows fast computation with low energy consumption. Nevertheless, optimal FPGA designs require deep understanding of the FPGA characteristics and the calculations need to be optimized for it. One commonality of all the Monte Carlo algorithms is the use of (pseudo-)random numbers. In the Heston setting standard normal random numbers are used. There are procedures to create these running efficiently on GPGPUs and CPUs. A new
method was presented which is very efficient for an implementation on a FPGA.
The detailed analysis of the diverse algorithms was used to make an efficient implementation. Therefore the algorithm is implemented on an FPGA. This should allow a fast computation with low energy consumption. As far as we know, this will be the first implementation of a Monte Carlo simulation in the Heston model on a FPGA. Furthermore it will be the first implementation of the multi-level Monte Carlo method on this hardware. Thus this work expands the field of implementations of financial mathematical problems on dedicated hardware in several ways as new concepts are taken into consideration.
from Center of Mathematical and Computational Modeling (CM)2 of the University of Kaiserslautern.