Monte Carlo Method for Stock Options Pricing

How rounding-errors propagate through a serious mathematical calculus done at Intel.

The stock-options price evaluation algorithm that we have analyzed with our tools has been provided by Intel as an example of their know-how in the usage of OpenCL for this kind of applications (source code available here). The software to be analyzed implements three methods in one single tool, written in C++ and OpenCL:
  • Mersenne twister - generation of uniformly distributed pseudorandom number;
  • Box-Muller transform - generation of normally distributed random numbers;
  • Option price calculation using Black-Scholes stock pricing model.
The studied function is written in OpenCL, and is executed by each thread (function described in ""). This function realizes an accumulation on a single variable during an iteration of approximately 140 000 cycles.
Evolution of the value of the variable during the iterationsThis variable increases almost linearly during the iterations (figure on the right), and a mean value is computed at the very end of the execution. It can, therefore, cause absorption problems during the iteration if the accumulated values are not in the same range as its current value.

Absolute value of the discrepancy between the ideal and the calculated value

On the chart on the left we represented the absolute value of the discrepancy between the value of the variable calculated by the computer and the expected mathematical value as a function of the number of iterations.

We can see that the discrepancy between the two values is neither constant nor easily understandable. Indeed, at the beginning the variations seem to be low and the gaps become more and more consequent with the number of iterations. This phenomena testifies of a progressive volatility of the accuracy, which is very good at some points (the gap comes close to zero), and at other times the accuracy crumbles dramatically.

Fortunately, in this example the discrepancy does not impact severely the behavior of the program, in spite of being quite significative.

This phenomena can be partly explained by the variation between the exponents of the measured variable and those of the value that the variable is incremented by during an iteration. During those changes the number of truncated decimals varies too, which causes a variation of the gap between the expected and the calculated results.

It can be seen easily that the behavior of the accuracy of calculations does not depend on mathematical function describing the expected result. In other words, the result being almost linear does not imply a linear behavior of the calculation error. In this example it is very complicated to find a function describing accurately the behavior of the error. Moreover, even if such function could be found, it would only be valid for this specific calculation and the result could not be generalized.

The accuracy evaluation is neither easy nor intuitive for a human brain. Every single software is subject to a specific behavior, and every optimization must be unique, too.

Thanks to : Intel, Vadim Kartoshkin (Intel), Jérôme Piat (Perfcraft).