Download Pricing composable contracts on the GP-GPU PDF

TitlePricing composable contracts on the GP-GPU
LanguageEnglish
File Size2.9 MB
Total Pages158
Table of Contents
                            Introduction
	Background
		Financial contracts and pricing
		Pricing methods
		Composing contracts
		GP-GPU and Monte Carlo simulation
		The problem
	Our solution
	Results
	Acknowledgements
	Preliminaries and notation
Common financial contracts
Composable contracts
	Concepts and terminology
	Implementing the abstract pricer
	The combinators
	The two versions
Goals for a stochastic processes language
	Matching the domain
		Stochastic processes
		Distributions
	Composability and reuse
		Composable processes for composable pricing
		Discretization as a separate concern
	Supporting a wide range of contract prices
		Conditionals
		Multiple sources of uncertainty
		Forecasting
		Aggregation
	Having clear semantics
	Yielding efficient implementations
Probabilistic functional programming
	Discrete distributions
	Symbolic representation
	Stochastic processes
	Monte Carlo simulation
	Summary
Array languages targeting GP-GPUs
A stochastic process language - SPL
	Language design
		Built-in constructs
		Prelude functions
		Haskell's bindings vs. sample and trace
		Semantics
	Implementing a CC model
		Decisions based on the (expected) future
Implementation
	Employed Haskell extensions
		GADTs
		Type families
	High level code
		A running example
	Low level code
		De Bruijn indexing
		Low level syntax tree
	Translation from high level to low level code
		Distributions
		Simple lookups
		Lookups on accumulating processes
		Top level functions of arbitrary arity
		Low level code for the running example
	OpenCL device architecture
	Translation from low level code to OpenCL code
		Quasi quotation for C-like languages
		Preserving (some) typing with phantom types
		The simple cases of Intermediate
		The primitive distributions Uniform and Normal
		The Split and Use constructs
		The Accumulator loops
		Wrapping it up
		OpenCL code for the running example
	Execution on the GP-GPU(s)
		Execution of the kernels
		Result aggregation
Correctness
	Test strategy
	Structured language tests
	Pricing tests
		Zero coupon discount bond
		Underlying sanity check
		European call options
		Asian call options
		Lookback options
		Basket options
	Choice based on future value
	Summary
Benchmarks
	Hardware and software configurations
	Scalability
	How far can we go
	Scheduling and result gathering overhead
	Performance of selected SPL constucts
		De-nesting of loops
		Skip
Future work
Conclusion
Benchmark data
Selected SPL modules
	Module Language.SPL
	Module Language.SPL.Syntax
	Module Language.SPL.Semantics
	Module Language.SPL.Intermediate
	Module Language.SPL.OpenCL.Compiler
	Module Language.SPL.OpenCL.Runner
Unit test code
	Module Language.SPL.Test.UnitTests
Pricing test code
	Module Language.CC.Test.PricingTest
	Module Language.SPL.Test.AsianTest
	Module Language.SPL.Test.LookbackTest
	Module Language.SPL.Test.BasketTest
                        
Document Text Contents
Page 1

Pricing composable contracts on the GP-GPU

Joakim Ahnfelt-Rønne
Michael Flænø Werk

Department of Computer Science

University of Copenhagen

August 17, 2011

Page 2

Abstract

We present a language for specifying stochastic processes, called
SPL. We show that SPL can express the price of a range of finan-
cial contracts, including so called exotic options with path depen-
dence and with multiple sources of uncertainty. Jones, Eber and
Seward previously presented a language for writing down finan-
cial contracts in a compositional manner [JES00], and specified a
pricer for these contracts in terms of an abstract financial model
and abstract stochastic processes. For the subset of prices that
do not require nested forecasting, these can be specified in SPL,
and we show an example of how to do this. The ease of writ-
ing a model that matches reality and the speed of computing
the expected price is then highly dependent on the properties of
SPL.

SPL is declarative in the sense that it is agnostic of the com-
putational model. It is designed with the goal of matching the
notation used in mathematical finance, which allows a high level
specification of stochastic processes. The language is embedded
in Haskell, and we have given the language formal semantics in
terms of the probability monad [Gir82], as well as a type system
in terms of Haskell’s type system. We provide an implementation
of SPL that performs Monte Carlo simulation on the GP-GPU,
and we present data indicating that this implementation scales
linearly with the number of available cores.

1

Page 79

ing point numbers in global memory, as indicated by the global keyword.
Similarly, the local keyword specifies that the second argument is a pointer
to something in local memory. The last argument is a single value that is
neither in local nor global memory. There is no restriction on the number or
order of arguments, but any pointer arguments to a kernel must be declared
to belong to a specific memory region, such as the global or local memory.

There may be multiple functions in the source code, and any number of
those may be marked as kernels. It’s also possible to include code via the
#include directive, if the appropriate include directories are specified when
compiling the source code.

Certain features are only available via extensions, such as IEEE 754 dou-
ble precision floating point numbers, which can be enabled by the #pragma
OPENCL EXTENSION cl_khr_fp64 : enable directive.

When executing a kernel from the host, it is necessary to specify the
total number of threads that will be executed, called the global work size,
as well as the number of threads in each thread group, called the local work
size. For each pointer argument to the kernel it is also necessary to specify
how much memory to allocate. Global memory can also be initialized from
the host before executing the kernel, as well as copied back into the host
memory after the kernel has finished executing.

These numbers can be queried from within the thread, as is evident from
the code example. The threads also have a global and a local ID, queried
with get_global_id(0) and get_local_id(0) respectively3.

Tasks like kernel execution and data transfer is performed asynchronously.
For each device, any number of event queues can be created, and tasks are
enqueued into these queues. When enqueueing tasks you can specify a list
of events to wait for before the task executes. Tasks fire a completion event
when they are done executing, and these events can be used to order data
transfers and execution of kernels.

There are several other memory regions, such as registers and private
memory, which are local to the individual process elements and used at the
discretion of the compiler when no memory region is specified. It should also
be noted that depending on the implementation, access to global memory
may be cached, but in general it can be assumed that access to local memory
is much faster than to global memory.

On most OpenCL targets, accessing shared memory in specific patterns
is required in order to get optimal performance. Our approach is to bypass
such difficulties simply by not using shared memory at all for the bulk of
the computation.

To use OpenCL from Haskell we use the HOpenCL library developed
by Martin Dybdal (unpublished), which is a one-to-one mapping of the
OpenCL C API to Haskell functions, providing a friendlier and less error

3The 0 speci�es the �rst dimension, which is the only for the purpose of this thesis.

78

Page 80

prone interface (eg. using lists instead of the (size, pointer) pairs required in
the C API). However, the library uses finalizers for resource management,
which is problematic because the resources on the device may run out before
the finalizers are executed. By choosing to use this library, we unfortunately
inherit this weakness.

8.6 Translation from low level code to OpenCL
code

This section describes the translation from low level code to OpenCL code.
The code for this translation step is given in module Language.SPL.OpenCL.Compiler.

8.6.1 Quasi quotation for C-like languages

In order to generate OpenCL code, we have extended the C quasi quoter
[Mai07] used in Nikola to support OpenCL’s variant of C. Like in Nikola,
this allows us to write C code in special quotation marks, while splicing in
code and values generated elsewhere in the Haskell program. Syntax errors
for the C code is then reported at Haskell compile time4.

8.6.2 Preserving (some) typing with phantom types

Since the C syntax tree we generate is untyped, we can’t be sure that the
generated code will type check, even if the syntax tree we generate it from is
fully typed. However, to get some help from the compiler, we use phantom
types for variable names and C expressions:

newtype Name a = Name String

newtype Expression a = Expression Exp

Note that the type variables are not used on the right hand side of the
definitions. At runtime, these are just String and Exp respectively, but
until then we can use the type variables to capture type information.

Since C (thankfully) uses names and not de Bruijn indexing for variables,
we need to generate suitable names and connect them to our de Bruijn in-
dexes. Our approach is to store the generated names in an environment
indexable by the type safe de Bruijn indexes. For this purpose, we con-
vert the iterated pair representation of the environment by wrapping each
element in the Name type using the following data type family:

data family Named :: * -> *

data instance Named () = NamedEmpty

data instance Named (env, b) = NamedBind (Named env) (Name b)

4C type errors are not caught until OpenCL compile time, however.

79

Page 157

]

D.4 Module Language.SPL.Test.BasketTest

module Language.SPL.Test.BasketTest where

import Language.SPL

import Language.SPL.Test.TestUtilities

import Test.HUnit

import Prelude hiding (lookup, map)

testList = [basketTests]

basketTests = TestLabel "Basket option" $ TestList [

testApproximate ("Basket test") 0.31 (basket t)

]

-- TODO: Requires a time step of 1/200 or so (to match the reference).

-- Ported from: http://stotastic.com/wordpress/2010/05/basket-option-pricing/ (See

also John Hull chapter 15)

basket t = lookup t $

pair (always normal) (always normal) ‘trace‘ \normals ->

rate ‘trace‘ \rate ->

let p1 = underlying s1 volatility1 first (pair rate normals) in

let p2 = underlying s2 volatility2 correlated (pair rate normals) in

if_ (p1 .>. always k1 .&&. p2 .>. always k2) (exp (-integral rate)) 0

correlated zs = rho * first zs + sqrt(1 - rho ^ 2) * second zs

rate = iterative (\dt r -> r + k * (theta - r) * dt + beta * sqrt dt * normal) r0

underlying initialPrice volatility f pairs =

inclusivePrefix (\dt s v -> s + s * (first v * dt + volatility * sqrt dt * f (

second v))) initialPrice pairs

-- Maturity time

t = 1

-- Interest rate model values

k = 0.4

theta = 0.05

beta = 0.03

-- Interest rate initially

r0 = 0.01

-- Strike prices

k1 = 500

k2 = 240

-- Initial prices

s1 = k1

s2 = k2

-- Volatility

volatility1 = 0.2262006

volatility2 = 0.2756421

-- Correlation

156

Page 158

rho = 0.5413732

157

Similer Documents