ISBN 9783843927611

978-3-8439-2761-1, Reihe Mathematik

Steffen Omland
Mixed Precision Multilevel Monte Carlo Algorithms for Reconfigurable Computing Systems

113 Seiten, Dissertation Technische Universität Kaiserslautern (2016), Softcover, A5

Zusammenfassung / Abstract

This thesis presents an extension of the multilevel Monte Carlo (MLMC) algorithm that is targeted for reconfigurable computing systems utilizing a field programmable gate array (FPGA). The main idea in the context of stochastic differential equations (SDEs) is to consider, additionally to the usual time discretization employed by the MLMC algorithm, another dimension of discretization, the discretization due to the restriction to finite precision. The latter is a key feature of reconfigurable computing systems, where each operation, such as the arithmetic operations, is performed in a user-defined finite precision. Our approach yields a multilevel algorithm with two dimensions of discretization, time discretization and discretization due to finite precision, that exploits a key feature of reconfigurable computing systems, namely the possibility of choosing arbitrary user-defined finite precisions for each elementary operation.

This so-called mixed precision multilevel Monte Carlo (MPML) algorithm is investigated theoretically and numerically. For the theoretical analysis, we define a model of computation based solely on floating point operations and a cost model that assigns polynomially increasing cost to operations in increasing precision.

Based on this model of computation, first a worst-case round-off error analysis of the Euler-Maruyama discretization scheme for SDEs under Lipschitz conditions for the coefficient of the SDE will be performed. It will be shown that the root-mean-square deviation of the Euler approximation in finite precision to the usual Euler approximation is bounded from above by a quantity that is proportional to the unit round-off of the employed precision and inversely proportional to the step size of the discretization scheme.

Next, the MPML algorithm will be analyzed and it will be shown that it has, up to a logarithmic factor, the same rate of convergence in our cost model for finite precision as the MLMC algorithm in the real number model for the same error criterion. Finally, an FPGA implementation of the MPML algorithm will be presented for pricing Asian options in the Heston model that adaptively chooses the necessary precisions based on a heuristic. For this problem, speedups of a factor of 3 to 9, compared to the implementation of the classical MLMC algorithm in reference precision on the same platform, are achieved.