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!