Simulacao Estocastica Financeira em GPU

IntroducaoGPU Computing

Modelagem MatematicaEstudo de Casos em Financas

ConclusaoReferencias

Simulacoes Financeiras em GPUDissertacao de Mestrado

Tharsis T. P. [email protected]

Instituto de Matematica e EstatısticaUniversidade de Sao Paulo

26 de abril de 2013

Tharsis T. P. Souza Defesa de Mestrado - Ciencia da Computacao




Agenda

1 Introducao

2 GPU ComputingCUDADemais Topicos

3 Modelagem Matematica

4 Estudo de Casos em FinancasMetodoStops OtimosRisco de Mercado

5 Conclusao





Agenda

1 Introducao




5 Conclusao





Simulacao Estocastica

Stochastic Simulation and Modelling (Prodan, 2001):

Figura : Nıveis de Simulacao.





Simulacao Estocastica em GPU

On the utility of graphics cards to perform massively parallelsimulation of advanced Monte Carlo methods (Lee et al., 2010):

“We believe the speedup we observe should motivatewider use of parallelizable simulation methods andgreater methodological attention to their design.”





GPU Computing - Bloomberg

Figura : Estudo de caso GPU Tesla: Precificacao de produtos - Bloomberg (NVIDIA,2009b).





GPU Computing - BNP Paribas

Figura : Estudo de caso GPU Tesla: Precificacao de produtos - BNP-Paribas(NVIDIA, 2009b).





Objetivos

Utilizar um modelo de hardware e programacao para GPU,apresentando essa plataforma como um verdadeiroco-processador generico.

Estudo de geradores de numeros aleatorios sequencias eparalelos.

Apresentacao de ferramental matematico fundamental paramodelagem estocastica em financas.

Resolver problemas reais em financas ao aplicar a teoriaapresentada.





Agenda

1 Introducao




5 Conclusao





CUDADemais Topicos

Agenda

1 Introducao




5 Conclusao





CUDADemais Topicos

CPU X GPU

Figura : Poder computacional (GFLOP/s) e Throughput (GB/s) CPU X GPU(Brodtkorb et al., 2012).





CUDADemais Topicos

CPU X GPU

Figura : Representacao de Chip CPU X GPU.





CUDADemais Topicos

GPGPU

Figura : GPGPU - Evolucao.





CUDADemais Topicos

Agenda

1 Introducao




5 Conclusao





CUDADemais Topicos

Arquitetura CUDA

Figura : CUDA: Compute Unified Device Architecture





CUDADemais Topicos

Modelo de Programacao

Figura : Hierarquia de Threads





CUDADemais Topicos

Modelo de Memoria

Figura : Hierarquia de Memoria





CUDADemais Topicos

Agenda

1 Introducao




5 Conclusao





CUDADemais Topicos

Arquitetura Fermi

Detalhamento da Fermi (alvo do trabalho):

CUDA Cores

Warps

Streaming Multiprocessor





CUDADemais Topicos

Otimizacao de Codigo e Boas Praticas

Como medir tempo

Execucao concorrente assıncrona

Otimizacao de Memoria

Coalesced MemoryMemoria Compartilhada, Local, Global

Controle de Fluxo

Ocupacao





CUDADemais Topicos

Geradores de Numeros aleatorios e Modelos de Distribuicao

PRNGs: Linear Congruential Generator, Multiple RecursiveGenerator, Lagged Fibonacci Generator, Mersenne Twister

QRNGs: Van Der Corput, Halton, Faure, Sobol

Geracao de Distribuicoes nao-Uniformes: Metodo de Inversao,Metodo de Aceitacao e Rejeicao, Metodo de Box-Muller

Portabilidade em GPU dos geradores: Sobol e MRG32k3a





Agenda

1 Introducao




5 Conclusao





Simulacao de Monte Carlo

Metodo de Monte Carlo

Tecnicas de Reducao de Variancia

Variavel de ControleVariaveis AntiteticasAmostragem Estratificada





Processos Estocasticos

Processos Estocasticos

Processo de WienerProcesso de Ornstein-Uhlenbeck

Equacoes Diferenciais Estocasticas

Lema de ItoDiscretizacao de Euler-MaruyamaDiscretizacao de Milstein





MetodoStops OtimosRisco de Mercado

Agenda

1 Introducao




5 Conclusao






Agenda

1 Introducao




5 Conclusao






GPU

CUDA Cnvcc (CUDA Toolkit v.3.1)-use fast math

Figura : NVIDIA GeForce GT 525M






GPU

Placa Grafica GeForce GT 525M

Nucleos CUDA 96

Compute Capability 2.1

Streaming Multiprocessors 2

Dimensoes maximas de um bloco 1024 x 1024 x 64

Numero maximo de threads por bloco 1024

Numero maximo de registradores por bloco 32768

Memoria Global 961 MB

Memoria Compartilhada 48 KB

Memoria Constante 64 KB

Tabela : Caracterısticas da placa grafica NVIDIA GeForce GT 525M.






CPU

C/C++, compilador Microsoft (R) C/C++ OptimizingCompiler Version 16.00.30319.01 for x64

Processador Intel Core i5-2430M

Programas em CPU foram construıdos utilizando uma unicathread






Metodo

Dados Disponıveis:

Ativo objeto ITUB4

Perıodo de amostragem: 15/06/2011 a 31/05/2012

Geracao de Numeros Aleatorios:

Em CPU, o gerador padrao utilizado foi o Mersenne Twistercom implementacao retirada de (Matsumoto e Nishimura,2009).

Em GPU foi utilizada a biblioteca padrao NVIDIA CURAND.

Nos experimentos que utilizaram o gerador Sobol, aimplementacao foi obtida em (Joe e Kuo, 2008).

Para transformada gaussiana foi utilizado o metodo deBox-Muller.






Agenda

1 Introducao




5 Conclusao






Stops

Em negociacao de ativos, uma estrategia de Stop define valoreslimites do preco do ativo objeto a partir do qual uma acao deve sertomada.

Stop Loss: Limite maximo de movimentacao adversa de precode um ativo.

Stop Gain: Limite superior para o valor do ativo denegociacao.






Formulacao do Problema de Stops

Suponha que uma partıcula se move aleatoriamente em umsub-conjunto D ⊂ Rn. No instante t sua posicao e xt . Desejamosescolher o Tempo de Parada t do movimento de modo amaximizar o ganho esperado E[g(xt)], onde g(x) representa oganho correspondente a x ∈ D.

Figura : O problema de Stop






Formulacao do Problema de Stops Otimos

O problema de Stop Otimo pode ser formalizado como:

max Ex0 [g(xτ )] (1)

sujeito a τ tempo de parada






Formulacao do Problema de Stops Otimos

Figura : Exemplos de Tempo de Parada






Solucao do Problema de Stops Otimos

Suponha que a variavel aleatoria que representa o preco do ativoobjeto siga o seguinte processo

dS = µSdt + σSdW , (2)

onde µ e σ sao constantes e dW e um processo de Wiener.Entao, pelo Lema de Ito, podemos chegar na seguinte recorrenciageral para o valor do ativo objeto no tempo

Si+1 = Si e(µ−σ2/2)δt+σ

√δtz , z ∼ N (0, 1). (3)













Seja f (K ) = E[S(K )], entao o valor K = K ∗ tal que f ′(K ) = 0 eum ponto de extremo de Stop. Assim, a obtencao de Stop otimose reduz a um problema de obtencao de raiz de funcao, que podeser resolvido, por exemplo, pelo metodo de otimizacao de biseccaoaurea de Brent (W. H. Press e Flannery, 2007).






Experimentos

Figura : Simulacao de caminhos do processo log-normal.






Experimentos

Figura : Esperanca de retorno de Stop Gain. Analise da variacao damedia µ.






Experimentos

Figura : Esperanca de retorno de Stop Gain. Analise da variacao davolatilidade σ.






Experimentos

Com o aumento da media µ, temos uma esperanca maior parao valor da barreira configurado.

Em contraposicao, um valor maior de volatilidade sugere anecessidade de configuracao de um valor mais alto para o stop.






Experimentos

Figura : Esperanca de retorno otimo em funcao da taxa de juros.Configuracao µ = 0, 0521139% e σ = 2, 4432633%.






Experimentos

Podemos observar uma estimativa de ganho otimo de 9,91%sobre uma taxa de juros de 11%, na configuracao analisada.

Retorno otimo e negativo para rf > 13%.






Experimentos

Figura : Tempo computacional gasto em calculo da esperanca de ganhode um Stop Gain em funcao do numero de simulacoes. Configuracao:Stop = 65, µ = −0, 00055%, σ = 2%.






Experimentos

Figura : Tempo computacional gasto em calculo da esperanca de ganhode um Stop Gain. Configuracao: numero de simulacoes = 38.400,µ = −0, 00055%, σ = 2%.






Experimentos

Speedup de mais de 12 vezes para um numero de simulacoesigual a 51.200.

Solucao em GPU escalavel para o numero de simulacoes evariacao de stop gain.






Agenda

1 Introducao




5 Conclusao






Risco de Mercado

Risco de Mercado e aquele relacionado com perdas no fluxode caixa da organizacao causadas por flutuacoes nos precos deativos e passivos da empresa (Kimura et al., 2010).

Para gestao desse risco, uma metrica particularmentedifundida e o Value-at-Risk (VaR), que visa a obter umamedida de perda maxima da instituicao.

Para o calculo do mesmo, o gestor de risco deve ser capaz decalcular o valor de mercado de seus produtos, para assimconseguir avaliar as possıveis variacoes na carteira da empresa.






Opcoes

Uma opcao confere, ao titular, o direito sobre um determinadoativo por um valor determinado, enquanto o vendedor eobrigado a concluir a transacao.

Opcao de Call: fornece ao titular o direito de compra do ativoobjeto a um valor determinado (strike).

Opcao de Put: fornece ao titular o direito de venda do ativoobjeto a um valor determinado.

Opcao Europeia e aquela que pode ser exercida somente emsua data de vencimento.

Para ter o direito, o titular deve pagar o preco da opcao,tambem chamado de premio.






Precificacao de Opcoes via Simulacao

Posicao comprada em uma opcao de Call : max(ST − X , 0).

Posicao vendida em uma opcao de Call : −max(ST − X , 0).

Posicao comprada em uma opcao de Put: max(X − ST , 0).

Posicao vendida em uma opcao de Put: −max(X − ST , 0).

O premio (cT ) de uma Opcao Europeia de Call pode ser calculadoa partir de um valor esperado de seu retorno, conforme:

cT = e−rTE[max(ST − X , 0)]. (4)







Figura : Payoffs das posicoes em opcoes europeias: (a) compra de Call ;(b) venda de Call ; (c) compra de Put; (d) venda de Put (Hull, 2012).







Paridade Put-Call

c + Xe−rT = p + S0. (5)

De posse da equacao 5, podemos estimar a esperanca do premiode uma opcao de call E[c] como:

E[c] = E[p] + S − Xe−rT (6)






Reducao de variancia da Precificacao

Em geral, a variancia de uma opcao de put e menor do queuma opcao de call ja que no primeiro caso o payoff e limitado.

Dessa forma, o preco da opcao de put se torna uma variavelde controle para o calculo do premio da opcao de call e,assim, obtemos um estimador de c com varianciapotencialmente reduzida.

Alem disso, podemos utilizar variaveis antiteticas comotecnica de reducao de variancia.












Value-at-Risk

(Choudhry e Tanna, 2007) define o VaR1−α como a perda maximaque pode ocorrer em um grau de confianca (1− α) e perıodo detempo (T ) determinados.Se assumirmos que F e a funcao de distribuicao acumulada doretorno da carteira da instituicao, podemos definir o VaR como

F (VaR) = α (7)

onde e α a probabilidade correspondente ao nıvel de confiancaestabelecido. Ao utilizar a funcao de densidade dos retornos f ,podemos definir o VaR de modo equivalente como

α =

∫ VaR

−∞f (x)dx . (8)






Value-at-Risk

Como obter uma funcao f de distribuicao dos retornos para umhorizonte de tempo definido?

Figura : Resumo comparativo de metodologias de calculo de VaR.Retirado de (Jorion, 2003)

.Tharsis T. P. Souza Defesa de Mestrado - Ciencia da Computacao





VaR via Metodo de Monte Carlo

Seja Π0 = (S10 , S

20 , . . . ,S

n0 ) o valor de um portfolio composto por n

ativos em t0. Desejamos calcular o VaR1−α de Π0 para um perıodoT . A seguir, apresentamos os passos para resolucao desseproblema via Simulacao de Monte Carlo:

1 Escolha e configure um modelo estocastico para projecao dosprecos dos ativos do portfolio.

2 Simule os precos dos ativos para projetar seus valores em T :S1

T , S2T , . . . ,S

nT

3 Calcule o valor do portfolio ΠT = (S1T , S

2T , . . . ,S

nT )

4 Repita os passos 2 e 3 um numero (N) de vezes tao grandequanto se queira







1 Ordene de modo crescente os valores dos portfolios obtidos eobtenha a distribuicao: (Π1

T ,Π2T , . . . ,Π

NT )

2 Compute o VaR a partir do quantil (1− α) de interesse:

VaR1−α = Πb(1−α)NcT − Π0












Experimentos

Figura : Aplicacao de tecnicas de reducao de variancia na simulacao dopremio de uma opcao de call europeia utilizando Sobol como RNG.






Experimentos

Melhoria de mais de 4 vezes no erro padrao da simulacao paraprecificacao de opcoes.






Experimentos

Figura : O portfolio Π0 gerado com um total de 2 mil opcoes, o queresultou em um valor total de R$191.740. Valor obtido para o VaR95% de1 dia foi de aproximadamente -R$896.






Experimentos

Numero de Simulacoes Tempo CPU (s) Tempo GPU (s)

1280 2,91 0,07

3200 7,178 0,16

6400 14,79 0,31

12800 28,59 0,60

25600 56,58 1,19

38400 84,03 1,81

51200 112,02 2,43

Tabela : Tempo Computacional gasto em CPU e GPU no calculo de VaRem funcao do numero de simulacoes. Numero de opcoes fixo em 2.000.






Experimentos

Numero de Opcoes Tempo CPU (s) Tempo GPU (s)

500 28,03 0,99

750 42,54 1,23

1000 56,31 1,47

1250 70,41 1,70

1500 84,95 1,95

1750 99,17 2,18

2000 112,02 2,43

2500 146,76 2,90

Tabela : Tempo Computacional gasto em CPU e GPU no calculo de VaRem funcao do numero de opcoes no portfolio. Numero de simulacoes fixoem 51200.






Experimentos

Figura : Speedup no calculo de VaR de uma carteira com 2000 opcoesem funcao do numero de simulacoes.






Experimentos

Figura : Speedup no calculo de VaR em funcao do numero de opcoes noportfolio. Numero de simulacoes fixo em 51200.






Experimentos

Aceleracao de mais de 50 vezes do calculo de Value-at-Riskvia Simulacao de Monte Carlo





Agenda

1 Introducao




5 Conclusao





Conclusao

Apresentamos a GPU como uma plataforma de computacaode proposito geral.

Estudo de diferentes tipos de PRNGs e QRNGs emarquiteturas sequencial e paralela.

Descricao de solucoes exatas e numericas de EquacoesDiferenciais Estocasticas.





Conclusao

Stops (nessa apresentacao):

Resolucao do problema de obtencao de Stop Otimo.

Em analise experimental, as implementacoes em GPUmostraram ser mais escalaveis em relacao ao algoritmosequencial.

Para o algoritmo de obtencao de esperanca de retorno de umStop Gain, foi alcancado um speedup de mais de 12 vezes.





Conclusao

Stops (vide dissertacao):

Revisamos o modelo trinomial proposto por(Warburtona e Zhang, 2006) e propomos um algoritmoalternativo para o mesmo via simulacao utilizando umatecnica de aceitacao e rejeicao para probabilidade de transicaodos precos de (Cox et al., 1979).

O algoritmo sugerido e, comparativamente, de facilimplementacao e naturalmente portavel para GPU.





Conclusao

Risco de Mercado:

Melhoria de mais de 4 vezes no erro padrao da simulacao paraprecificacao de opcoes.

Calculo de Value-at-Risk via Simulacao de Monte Carlo comaceleracao de mais de 50 vezes.





Referencias Bibliograficas I

Brodtkorb et al.(2012) A. R. Brodtkorb, T. R. Hagen e Ma. L.Saetra. Graphics processing unit (gpu) programming strategiesand trends in gpu computing. Journal of Parallel and DistributedComputing.

Choudhry e Tanna(2007) M. Choudhry e K. Tanna. AnIntroduction to Value-at-Risk. Securities Institute. Wiley. ISBN9780470033777.

Cox et al.(1979) J. Cox, S. Ross e M. Rubenstein. Option pricing:a simplified approach. Journal of Financial Economics.

Hull(2012) J. Hull. Options, Futures, and Other Derivatives andDerivaGem CD Package. Prentice Hall. ISBN 9780132777421.





Referencias Bibliograficas II

Joe e Kuo(2008) S. Joe e F. Y. Kuo. Codigo fonte: Sobolsequence generator, 2008. URLhttp://web.maths.unsw.edu.au/~fkuo/sobol/. Ultimoacesso em 29/01/2013.

Jorion(2003) P. Jorion. Value at risk: a nova fonte de referenciapara a gestao do risco financeiro. Bolsa de Mercadorias &Futuros. ISBN 9788574380070.

Kimura et al.(2010) H. Kimura, A. S. Suen, L. C. J. Perera eL. F. C. Basso. Value at Risk - Como Entender e Calcular oRisco pelo VaR. INSIDE BOOKS. ISBN 9788560550074.


http://web.maths.unsw.edu.au/~fkuo/sobol/




Referencias Bibliograficas III

Lee et al.(2010) A. Lee, C. Yau, M. B. Giles, A. Doucet e C. C.Holmes. On the utility of graphics cards to perform massivelyparallel simulation of advanced monte carlo methods. Journal ofComputational and Graphical Statistics, paginas 769–789.

Matsumoto e Nishimura(2009) M. Matsumoto e T. Nishimura.A c-program for mt19937, 2009. URL http://www.math.sci.

hiroshima-u.ac.jp/~m-mat/MT/emt.html. Ultimo acesso em29/01/2013.

NVIDIA(2009b) NVIDIA. Site de computacao em financas danvidia, 2009b. URL http:

//www.nvidia.com/object/computational_finance.html.Ultimo acesso em 29/01/2013.

Prodan(2001) A. Prodan. Stochastic simulation and modelling.


http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

http://www.nvidia.com/object/computational_finance.html

http://www.nvidia.com/object/computational_finance.html




Referencias Bibliograficas IV

W. H. Press e Flannery(2007) W. T. Vetterling W. H. Press, S.A. Teukolsky e B. P. Flannery. Numerical Recipes 3rd Edition:The Art of Scientific Computing. Cambridge University Press,New York, NY, USA, 3 edicao. ISBN 0521880688,9780521880688.

Warburtona e Zhang(2006) A. Warburtona e Z. G. Zhang. Asimple computational model for analyzing the properties ofstop-loss, take-profit, and price breakout trading strategies.Computers and Operations Research.


Simulacao Estocastica Financeira em GPU

Text of Simulacao Estocastica Financeira em GPU

Uma Abordagem Paralela da Evolução Diferencial em GPU

Relatório Final Simulacao Empresarial (Revisto).pdf

Resumo Simulacao

Simulacao Calculo Prestacoes Juros Simples Compostos

A GPU mais rápida e eficiente já desenvolvida

2 Simulacao Pedagogica Inicial

Aula0 Gpu Te Ana Mpu

Programcao de Shaders em GPU´s

Arquitetura e Programação de GPU Nvidia - Home | INSTITUTO DE COMPUTAÇÃOducatte/mo401/1s2012/T2/G02-001963-023169... · A Figura 2 ilustra a arquitetura GPU Fermi. Figura 2: GPU

2013 simulacao 3 d_por_dipolos_magnéticos_henriquegasparoto_2013

Simulações financeiras em GPU

Arduino Simulacao Em Virtual Breadboard

Simulacao inicial

Curso Internacional de Hidrologia Estocastica

- SIPREV.war - SIPREV-SIMULACAO.sql - SIPREV-SIMULACAO

Projeção de Células baseada em GPU para Visualização ...w3.impa.br/~andmax/talks/defesa-dissertacao.pdf32 Passos de pré-processamento Preparação da memória da GPU – Construção

SIMULACAO, EXPERIMENTOS E CALIBRAÇÃO DO ATUADOR

Simulacao e Controle de Uma Upgn

OTIMIZACAO ESTOCASTICA - Bernardo PAGNONCELLI e Humberto - III-bienal-sbm-texto

ELEMENTOS FINITOS Alencar Simulacao Fraturamento

VANESSA HENRIQUES DANTAS MODELAGEM E SIMULACAO DO …

GPU Programming with CUDA

GPU - UFRJ

Multi-GPU Support on the Marrow Algorithmic Skeleton Framework · Fernando Jorge Marques Alexandre Licenciado em Engenharia Informática Multi-GPU Support on the Marrow Algorithmic

Programação em GPU

Simulacao de Unidade de Destilacao

Simulacao do ip_movel_via_network_simulator_(ns2)_uma_proposta_de_rede_wireless

IFFluminense - Planilha de Simulacao Do RSC

Modelagem e Simulacao de Calcinadores de Hidroxido

Uso Do Arena Em Simulacao

Economy & Finance

Simulacao Estocastica Financeira em GPU

Text of Simulacao Estocastica Financeira em GPU