High performance computing in finance - on the parallel implementation of pricing and optimization models

Abstract

Der Einsatz von Hochleistungsrechnern in der Finanzwirtschaft ist sinnvoll bei der Lösung von Anwendungsproblemen, die auf Szenarien und deren Eintrittswahrscheinlichkeiten definiert sind. Die Entwicklung von Aktienkursen und Zinsen kann auf diese Weise modelliert werden. In dieser Arbeit werden zwei Problemklassen behandelt, nämlich die Berechnung von Preisen für Finanzinstrumente, und die Optimierung von Anlageportefeuilles im Hinblick auf eine Zielfunktion mit Nebenbedingungen. Dynamische Optimierungsverfahren berücksichtigen mehrere Planungsperioden. Stochastische dynamische Verfahren beziehen Wahrscheinlichkeiten mit ein und führen daher zu (exponentiell wachsenden) Baumstrukturen, die sehr groß werden können. Die Lösung solcher Probleme auf einem Arbeitsplatzrechner kann Stunden oder Tage dauern, daher ist es wünschenswert, sie mittels Hochleistungsrechnern zu beschleunigen.<br />Die Parallelverarbeitung stellt den wichtigsten Ansatz zur Leistungssteigerung in dieser Arbeit dar. Es wurden Verfahren zur Preisberechnung pfadabhängiger Zinsderivate auf der Basis sowohl von Monte Carlo Simulationen als auch von Rückwärtsberechnungen parallel implementiert. Im Optimierungsteil der Arbeit wurde das Dekompositionsverfahren von Benders zur mehrstufigen stochastischen Optimierung eingesetzt und sowohl in einer synchronen als auch in einer asynchronen Variante parallelisiert. Mit diesen parallelen Implementierungen lassen sich angemessene bis sehr gute Verbesserungen der Ausführungszeiten im Vergleich zu den sequentiellen Programmversionen erzielen. Darüber hinaus dienen sie als Fallstudien in der Entwicklung von Softwarewerkzeugen für Hochleistungsrechner, die im Rahmen des Spezialforschungsbereichs F011 AURORA ("Advanced Models, Applications and Software Systems for High Performance Computing") des FWF durchgeführt wurden.<br />Die datenparallele Programmiersprache HPF+, mit Erweiterungen für SMP-Cluster, wurde erfolgreich bei der Implementierung von Preisberechnungsverfahren eingesetzt. Eine Notation für Pfade, die es erlaubt, parallele Algorithmen auf Gittern auf hoher Abstraktionsebene auszudrücken, wurde als Erweiterung von Fortran 95 spezifiziert. Das parallele Programmiermodell eines verteilten aktiven Baumes wurde entworfen und auf der Basis von Java Threads und RMI implementiert.<br />Parallele Implementierungen des Benders Verfahrens in Java zeigen, dass diese Sprache zur Entwicklung von Hochleistungsanwendungen geeignet ist.<br />Sowohl OpusJava als auch JavaSymphony und das Modell eines verteilten aktiven Baums haben sich als nützliche Werkzeuge bei der Implementierung paralleler baumstrukturierter Algorithmen erwiesen.<br />Zusätzlich zur Parallelisierung existierender sequentieller Verfahren, der Weiterentwicklung bekannter Parallelisierungsansätze und der Verwendung spezieller Programmiersprachen und Programmiermodelle wurden Leistungssteigerungen auch durch algorithmische Verbesserungen erzielt.<br />Eine Verallgemeinerung der klassischen Rückwärtsberechnungsmethode ermöglicht die schnellere Berechnung, und zwar in linearer statt exponentieller Zeit, von Preisen bestimmter pfadabhängiger Produkte mit "begrenzter" Pfadabhängigkeit. Dadurch wird auch gezeigt, dass besonders effiziente Ansätze zur Leistungssteigerung die Ebene der Algorithmen mit jener der parallelen Implementierung verbinden.<br />

High Performance Computing is useful in the field of finance for solving problems which are defined on models of financial variables in the form of sequences of scenarios along with their realization probabilities. Both the evolution of stock prices and interest rates is frequently described in this manner. This work deals with the two problem classes of determining prices of financial instruments, and of determining optimal portfolios of assets, with respect to some objective function and constraints. Dynamic optimization techniques allow for multiple planning periods, whereas stochastic dynamic optimization problems take into account also probabilities and exhibit (exponentially growing) tree structures, which can become very large. Computation times for solving these problems can extend to hours and days, hence high performance computing techniques of achieving speed up are desirable.<br />The major approach for performance improvement in this work is parallel computing. It includes the parallel implementation of Monte Carlo simulation techniques as well as of backward induction methods for pricing path dependent interest rate derivatives, in particular constant maturity floaters with embedded options. In the optimization part, the nested Benders decomposition method of multistage stochastic optimization has been parallelized in a synchronous as well as in an asynchronous version. The parallel implementations obtain speedups ranging from reasonable to excellent and demonstrate the potential of high performance computing for financial applications. In addition, they served as case studies in the development of software tools for high performance computing within the framework of the Special Research Program No. F011 AURORA "Advanced Models, Applications and Software Systems for High Performance Computing" of the Austrian Science Fund (FWF).<br />The data parallel programming language HPF+, with extensions for clusters of SMPs, has been successfully employed in the implementation of pricing algorithms. A path notation has been specified as an extension to Fortran 95, allowing for the high level formulation of parallel algorithms operating on lattice structures. The parallel programming model of a distributed active tree has been designed and implemented on top of Java's threads and RMI. Parallel implementations of the nested Benders decomposition algorithm in Java demonstrate that this is a suitable language for high performance computing. The OpusJava component framework, as well as the JavaSymphony class library, and the distributed active tree model proved their usefulness as programming support environments in the implementation of parallel tree structured algorithms.<br />In addition to the parallelization of sequential existing algorithms, the improvement of known parallelization approaches, and the use of specialized parallel programming languages and programming models, an increase in performance has been achieved by algorithmic developments.<br />The generalization of the classical backward induction method allows for the faster calculation, i.e., in linear instead of exponential time, of prices of a class of instruments exhibiting "limited" path dependence, demonstrating that highly effective approaches of performance improvement combine the levels of algorithms and parallel implementation.