janeiro 22, 2012

Aventuras em OpenCL: Mais que Um Segundo

Ok, aqui vai um post longo, cheio de linguagem técnica, mas acho que estava na hora de escrevê-lo. Quando me perguntam, normalmente, em que estou trabalhando agora, esta é a história que eu conto. Envolve um pouco de economia, um tanto de econometria e muita, muita computação. Para quem trabalha com economia, a parte de computação possivelmente diga muito pouco. Para quem trabalha em ciências computacionais, a parte de economia não diz nada, enquanto que a parte de computação pode ser muito básica, trivial até. Para quem tiver paciência, o texto vem a seguir.



Estou trabalhando agora em um conjunto de programas dentro de um projeto mais ou menos delineado ao final do último working paper publicado: a idéia é estimar modelos cuja solução não esteja baseada em aproximações lineares das condições de equilíbrio. Para isto, uma das condições é a obtenção da função de verossimilhança através de métodos de simulação, já que o bom e velho Filtro de Kalman só funciona se a equação de estado for linear e os choques apresentem distribuições Gaussianas.

O método escolhido por mim foi o filtro de partículas: a idéia básica de uma das versões (a mais simples talvez) deste filtro é fazer um bootstrap da função densidade de probabilidade em cada ponto disponível do conjunto de informações passado ao modelo. Este bootstrap é formado por um conjunto de choques (as partículas) que perturbam o vetor de estados e permitem uma aproximação da densidade sob algumas hipóteses adicionais a respeito da distribuição dos choques. Como se pode imaginar, o tempo de computação necessário para obter uma boa aproximação da função de verossimilhança é bem maior que no filtro de Kalman tradicional, onde uma sequência de inversões de matrizes resolvem bem o problema.

Eu comecei o trabalho escrevendo um rascunho de código para um modelo bem simples em Matlab. De fato, a velocidade não estava boa. Daí passei para o uso de arquivos MEX, ainda dentro do Matlab, para tentar ganhar algum tempo. Isto me forçou a estudar C/C++ para escrever comandos básicos. Quando senti que alguns gargalos do programa não poderiam ser resolvidos sem sair do Matlab, resolvi arriscar um código inteiramente em C/C++, e deu certo: o ganho de tempo foi incrível, mas ainda insuficiente para fazer algum trabalho mais sério. Daí veio a história do paralelismo...

Paralelismo, em computação, é o exercício de dividir as tarefas executadas no computador entre os diversos processadores disponíveis para a atividade. Até os anos 90, ganhos de velocidade na execução das tarefas estava estritamente associado aos ganhos de velocidade dos processadores: daí por que ter um Pentium com 100MHz no clock era melhor que um Pentium 70 ou 90. A história recente de computadores "dual core" e "quad core" nasceu de uma limitação tecnológica da indústria de processadores, já que a tecnologia atual simplesmente saturou, e aumentos nas velocidades dos clocks geravam superaquecimento das máquinas em troca de um ganho mínimo de velocidade. A idéia dos processadores "dual core" e "quad core" é exatamente aumentar a capacidade de processamento colocando, em apenas uma peça, duas ou mais unidades de processamento. Assim, enquanto você joga "The Need for Speed" no... OPS! Descupe: enquanto você escreve relatórios e projetos de pesquisa em seus processadores de texto e planilhas, ocupando um conjunto de unidades de processamento, o computador é capaz de manter o sistema funcionando normalmente com as unidades restantes.

A noção de divisão das tarefas foi levada ao extremo pela indústria do video game: os melhores jogos normalmente demandam gráficos e sons cada vez mais elaborados. Entretanto, nem todo mundo troca de console com a mesma frequência que atualiza o computador de casa. Assim, dado o conjunto restrito de peças contidas naquele console, os programadores precisavam extrair o máximo em termos de capacidade de processamento para rodar os jogos mais modernos. Daí surgiu a idéia de explorar um conjunto de processadores até então pouco utilizados para o processamento de dados: a placa de vídeo.

A placa de vídeo de um desktop comum possui centenas de unidades de processamento muito leves, capazes de fazer milhões de operações em uma fração de segundo. Vendo o potencial destes processadores para a análise de dados, fabricantes como a Nvidia, com o CUDA, e a ATI/AMD, com o OpenCL, desenvolveram linguagens abertas, gratuitas e com linguagens muito próximas do C/C++ para difundir o uso destes recursos em outras áreas que não exatamente a criação de jogos. Aplicações em economia já existem, com resultados muito apreciáveis, ainda que o pessoal da engenharia pareça muito mais avançado no uso destes recursos.

Voltando para o meu trabalho, eu tinha o código ainda lento, e precisava de algo que acelerasse a obtenção da verossimilhança do modelo. Lendo alguns trabalhos em engenharia, vi que o Filtro de Partículas tinha uma parte importante do trabalho computacional que apresentaria ganhos significativos se fosse resolvida em paralelo. O primeiro resultado que obtive está na figura abaixo. O exercício consiste em gerar uma série artificial de dados a partir de um modelo DSGE muito simples (no caso, o piloto de provas é o conhecido modelo neo-clássico de crescimento) e repetir o cálculo da função de verossimilhança 5000 vezes para diferentes números de partículas usadas no bootstrap. O eixo horizontal mostra o número de partículas usadas em cada período da amostra para fazer o bootstrap, começando com 5000 partículas até 80000. A linha azul refere-se ao eixo vertical da esquerda, mostrando o desvio-padrão das 5000 simulações da verossimilhança. Como o esperado, quanto maior o número de partículas usadas, maior é a precisão no cálculo e menor é a dispersão das estimativas da função objetivo.


O resultado bacana, em termos computacionais, aparece nas linhas tracejadas em vermelho e preto, com os resultados exatos no eixo da direita: ele mede o tempo médio, em segundos, para se obter uma simulação da função de verossimilhança. A linha vermelha, quase linear ao longo das simulações, é a resolução do problema na versão serial, usando apenas um "core", sem nenhum paralelismo. No caso extremo do número de partículas, uma única avaliação da função de verossimilhança levava cerca de 7 segundos, uma eternidade! A linha preta, com alguns solavancos (obrigado, computador do trabalho!), é a primeira versão paralelizada do código, usando a placa de vídeo da ATI e o código em OpenCL. Para trabalhos maiores (acima de 10000 partículas no bootstrap), o código paralelizado arrebenta, com ganhos muito significativos de performance. Para se ter uma noção, cada décimo de segundo gasto na simulação representa, em um milhão de simulações, pouco mais que um dia de trabalho. Trazer o tempo médio de 7 para algo em torno de 2 segundos por simulação é um resultado bem bacana.

Dois aspectos positivos ainda: 1) o computador onde fiz o trabalho não é a máquina mais rápida do mundo, por óbvio: fazendo o exercicio com 80000 partículas em casa, o tempo médio ficou em 0.6 segundos; 2) este código é a versão mais básica em termos de paralelismo (o que o pessoal da computação chama de "paralelismo trivial"). Existem outros pedaços do programa que eu ainda estou mexendo para ver se o tempo melhora.

Depois destes resultados, ainda vou explorar um pouco mais o código para modelos maiores, e já com boas perspectivas: parece que um modelo igual a Christiano, Eichenbaum e Evans (2005), padrão em termos de modelos DSGE para economias monetárias, gasta um pouco mais de 2.6 segundos por simulação no codigo básico com 50000 partículas (e sem usar o computador do trabalho...), mesmo tendo 13 variáveis de estado, contra apenas 3 do modelo neoclássico de crescimento. A partir daí, abre-se uma tremenda janela de oportunidade para novos trabalhos empíricos pela frente.

Bom, já enchi demais o post. Agora posso dormir tranquilo: quando me perguntarem no que eu trabalho, já tenho para onde direcionar a explicação.

Saudações!

6 comentários:

Iury Santos disse...

Maneiríssimo! Keep walking, digo, coding!

Angelo Marsiglia Fasolo disse...

De fato, o bom e velho Johnny (quanto mais velho, melhor) ajuda nas horas ruins do coding... rsrsrsrs

Saudações!

M. Silveira disse...

Muito bacana, em que departamento do BC você trabalha?
Quem sabe um dia sejamos colegas de trabalho.
Bom trabalho.

Anônimo disse...

Angelo,

Li alguns trabalhos com filtro de partículas, basicamente do Villaverde. Se me lembro bem, ele tinha bons resultados com a velocidade. O que me deixou um pouco frustrado à época era que os resultados não mudavam muito em relação ao bom e velho FK. Além disso, minha capacidade computacional é nula, o que me restou deixar esperando que, um dia, o dynare me ajude nisso.
De toda forma, fico no aguardo de seus resultados e te desejo boa sorte. Ainda falta muita gente para consolidar os DSGE (e aperfeiçoá-los, desenvolve-los) aqui.
Abs,
Fernando Genta

Angelo Marsiglia Fasolo disse...

M.Silveira,

Eu trabalho no Departamento de Pesquisas do banco.

Fernando,

Algumas observações:

1) Os resultados que mostrei estão baseados no mesmo modelo daqui, com a única diferença sendo o método não-linear de solução do modelo: os autores usaram elementos finitos, eu usei perturbação de 2a ordem. Na página 896, quando eles tratam da computação dos resultados, eles falam em 6.1 segundos como o tempo para obter uma simulação do Metrópolis. Eu obtenho com o mesmo número de partículas um tempo médio de 1.7 segundos. Dando de barato que, para completar a simulação do Metrópolis, se gaste 0.3 segundos em média (é menos, com certeza), totalizando 2 segundos por simulação, o tempo total que eles falam em 88 horas para resolver 50000 simulações é reduzido para quase 28 horas. Um ganho, certamente, apreciável, já que, como falei, estava usando o computador do serviço.

2) Quando o modelo cresce, os trabalhos apresentados pelos autores sofrem com o tempo de solução: neste trabalho, cujo modelo tem um total de 19 variáveis de estado, no apêndice B, página 67, os autores falam que uma avaliação da função de verossimilhança com 10000 partículas gasta cerca de 22 segundos. Como eu falo no final do texto, eu gasto 2.6 segundos em um bom computador para avaliar a verossimilhança com 50000 partículas de um modelo com 13 variáveis de estado. Por mais que o acréscimo de variáveis aumente o tempo, acho difícil que eu chegue aos 22 segundos dos autores.

3) Conversando com o Pablo, um dos autores deste último trabalho, fiquei sabendo que o Juan e o Jesús estão usando verba de pesquisa deles para comprar uma máquina mais possante, com mais de uma placa de video, exatamente para fazer esta implementação que estou fazendo aqui. O paralelismo que eles fazem é inteiramente via CPU.

4) Sobre as diferenças nos resultados usando métodos não-lineares, para mim, os resultados apresentados na figura 2 do primeiro artigo são conclusivos sobre a importância do trabalho: bastou aumentar a volatilidade da economia que o viés entre valores estimados e simulados com a aproximação linear tornaram-se significativos. Não dá para dizer que temos, por aqui, dados "bem comportados" como nos EUA, certo?

5) Conversando com um dos desenvolvedores, fiquei sabendo que a equipe do Dynare possui os códigos prontos para o filtro de partículas. Eles só não colocam no ar exatamente pq querem desenvolver uma forma de acelerar as computações sem depender da instalação de outros programas pelo usuário. Ou seja, velocidade ainda é uma restrição séria para o uso do filtro.

Saudações!

Angelo Marsiglia Fasolo disse...

Desculpem a todos: meu HTML não deu muito certo aqui na área de comentários. No comentário acima, o primeiro artigo que falo é este:

http://economics.sas.upenn.edu/~jesusfv/jae_december05.pdf

O segundo é este:

http://economics.sas.upenn.edu/~jesusfv/Fortune_Virtue.pdf