65ª Reunião Anual da SBPC

A. Ciências Exatas e da Terra - 2. Ciência da Computação - 12. Simulação

IMPLEMENTAÇÃO PARALELA DO ALGORITMO DE METROPOLIS PARA GPUs NVIDIA

Wagner Leandro de Souza - Laboratório de Computação Científica Aplicada – UFRPE/UAG David Willians dos Santos Cavalcanti Beserra - Escuela Politécnica Superior, Universidad Autónoma de Madrid ­ EPS/UAM Ramon Santos Nascimento - Laboratório de Computação Científica Aplicada – UFRPE/UAG Alberto Einstein Pereira de Araujo - Prof. Dr. /Orientador-Laboratório de Computação Científica Aplicada – UFRPE/UAG

INTRODUÇÃO:

O Algoritmo de Metropolis é um método computacional que pode ser utilizado no cálculo das propriedades resultantes de iterações moleculares em materiais. Um dos seus usos mais comuns é no cálculo das propriedades magnéticas de materiais utilizando o Modelo de Ising. Este trabalho apresenta uma implementação do Algoritmo de Metropolis aplicado ao Modelo de Ising em 2 dimensões para arquiteturas de dispositivos computacionais do tipo GPU (Unidade de Processamento Gráfico) produzidas pela NVIDIA. É realizada uma comparação de seu desempenho e corretude com uma implementação sequencial executada em uma única CPU (Unidade Central de Processamento) de arquitetura x86_64. A simulação foi dividida em trechos de códigos paralelizáveis e não paralelizáveis, onde os trechos seriais da implementação paralela são executados na CPU e os trechos paralelos na GPU. Esses dispositivos são encontrados em placas gráficas e possuem milhares de núcleos de processamento que podem trabalhar em paralelo, de modo a obter melhor desempenho em relação ao processamento convencional em CPU.

OBJETIVO DO TRABALHO:

O objetivo deste trabalho é fazer uma implementação paralela do Algoritmo de Metropolis para GPUs e comparar tanto os resultados obtidos (verificação de corretude) quanto o desempenho obtido com uma versão sequencial executada em uma única CPU.

MÉTODOS:

O desenvolvimento desta pesquisa foi dividido em três etapas. A primeira refere-se aos estudos necessários para o desenvolvimento da pesquisa, onde foram realizados: a) Estudo de conceitos relacionados a técnicas de paralelização e otimização de código; b) Estudo de conceitos à programação de GPUs. A segunda etapa refere-se ao desenvolvimento e implementação dos algoritmos computacionais utilizando a linguagem de programação C para a implementação serial e da linguagem C acrescida da API CUDA para a implementação paralela. A terceira etapa corresponde à execução das implementações para verificar a corretude mediante observação das saídas geradas e comparar o desempenho de ambas, sobretudo focando o SpeedUp (fator de aceleração obtido por um programa executando em N processadores dividindo o tempo da execução serial pelo tempo nesses N processadores) obtido pelo código paralelo. Para a execução de ambos os algoritmos, foi empregado um computador com um processador Intel Core i7 (4 núcleos), 3.40 GHz de frequência de operação, 8 GB de memória principal e uma GPU GeForce GTS 450 com 192 CUDA cores e 1024 MB de memória principal. O sistema operacional utilizado foi o Ubuntu 12.04 64 bits. O sistema empregado na simulação foi armazenado em uma matriz de ordem 4096.

RESULTADOS E DISCUSSÃO:

Após o estudo das técnicas computacionais relacionadas ao algoritmo de Metropolis, observa­-se que determinadas etapas que requerem elevado esforço computacional. Uma delas é a escolha do estado inicial que implica na inicialização de uma matriz de 4096x4096. O computo de 6000 passos de monte Carlo (5000 passos de termalização da rede e 1000 passos para computo dos valores esperados). Para acelerar estas etapas, a escolha do estado inicial e os passos de monte carlo foram implementados em GPU. Após a implementação dos procedimentos citados, o código paralelo foi executado e suas saídas comparadas com a versão serial de corretude já comprovada. A implementação para GPUs obteve saídas similares, atestando sua corretude. Em sequência, foram comparados os desempenhos dos dois códigos. A versão paralela apresentou um SpeedUp de 9x para este sistema.

CONCLUSÕES:

Neste trabalho foi apresentada uma comparação entre uma versão serial e uma versão paralela implementada para GPU do Algoritmo de Metropolis. Após a análise dos resultados de desempenho, percebe-se que houve um ganho significativo de tempo de processamento pela versão paralela. A versão paralela apresentou resultados significantes, que, todavia podem ser melhorados mediante técnicas de otimização especificas para esta arquitetura. A próxima etapa desta pesquisa consiste em aplicar as técnicas de otimização de código existentes para essa arquitetura e observar o SpeedUp obtido com seu emprego.

Palavras-chave: Simulação Computacional, Computação de Alto Desempenho, GPU.