63ª Reunião Anual da SBPC

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

Estudo e Implementação de Algoritmos Paralelos aplicados a Problemas de Física e Engenharia Computacional

Bruno Normande Lins 1,3,4,5 Leonardo Viana Pereira 2,3,4,5

1. Instituto de Computação - UFAL 2. Prof. Dr. / Orientador - Instituto de Computação - UFAL 3. Laboratório de Computação Científica e Visualização - LCCV 4. Laboratório de Computação Científica e Análise Numérica - LaCCAN 5. Centro de Pesquisas em Matemática Computacional - CPMAT

INTRODUÇÃO:

O Método de Elementos Discretos (DEM) é uma técnica de modelagem computacional que simula o comportamento de meios granulares com física real. Para isso, dado um conjunto de partículas, ele calcula em cada intervalo de tempo a força resultante da interação entre elas e de forças externas. O gargalo de tal método está na busca de contatos entre as partículas, já que o modo trivial é de complexidade computacional O(N2) e tipicamente N, o número de partículas, pode passar de milhões em casos de interesse. Para resolver este problema foram criados algoritmos de busca de vizinhos que buscam organizar a estrutura espacial de maneira a minimizar o tempo gasto em tais buscas. Nesse trabalho foram revisados os principais algoritmos para este fim, além do estudo de técnicas de programação paralela usando MPI e a API OpenMP.

METODOLOGIA:

O aluno iniciou a introdução ao sistema operacional linux com a tarefa de implementar, configurar e testar a operação de um mini-cluster de computadores classe Beowulf. Além do sistema operacional, foram estudados sistemas de compartilhamento de arquivos, sistemas de login e autenticação descentralizados e a instalação e manutenção de redes privadas. O estudo de programação paralela em C usando MPI e OpenMP se deu por meio de uma disciplina eletiva de programação paralela, além de estudos complementares e testes no mini-cluster montado. No segundo semestre o aluno foi incorporado ao grupo de HPC, Computação de Alto Desempenho, do LCCV e se deu inicio ao estudo da versão paralela do DEMOOP e do DEMPAD, softwares desenvolvidos no Laboratório. O aluno cursou uma disciplina eletiva de técnicas de computação científica, simulação e modelagem computacional. Onde passou a estudar o DEM e técnicas de derivação explícitas e implicitas, além do uso de bibliotecas de álgebra linear. Foram encontrados uma série de problemas de versão e implementação no DEMPAD, então foi decidido focar os estudos da pesquisa no principal gargalo do DEM, os algoritmos de detecção de contatos. Foi feito um levantamento do estado da arte na área, e por fim o aluno ficou responsável por implementar um desses algoritmos, o Sorting Contact Detection, e integrá-lo ao DEMOOP.

RESULTADOS:

O aluno instalou e configurou um mini-cluster Beowulf, adquirindo assim conhecimento suficiente para a implementação deum ambiente para computação científica e de alto desempenho. Além disto o bolsista estudou dois dos principais algoritmos de busca de vizinhos, utilizados no Método de Elementos Discreto: Direct Mapping e Cell Mapping. E implementou o algoritmo Sorting Contact Detection, que utiliza uma estrutura de dados diferente dos anteriores, de maneira a utilizar menor quantidade de memória em sua execução. Foram realizadas simulações em três cenários diferentes de distribuição de partículas: densa, esparsa e mista, todas com até 100 mil elementos de tamanhos homegêneo. Para tal foi usado o software DEMOOP desenvolvido pelo Laboratório de Computação Científica e Visualização (LCCV) e o cluster GradeBR/UFAL. Os algoritmos testados (Mapeamento Direto, Mapeamento por Célula e Checagem Direta) mostraram o comportamento esperado nos casos denso e esparso: com o mapeamento direto com peformace superior ao mapeamento por célula e a checagem direta impraticável para cenários com pouco mais de 500 elementos. No cenário misto ambos algoritmos de mapeamento se mostraram equivalentes.

CONCLUSÃO:

Com a instalação do cluster e o estudo das disciplinas específicas o aluno se familiarizou com o ambiente os principais modelos e técnicas usados para computação científica, assim como computação de alto desempenho. Focando-se no estudo do Método de Elementos Discretos, esse trabalho mostrou as principais abordagens para o problema de detecção de contatos. Integrando-se no grupo de HPC do LCCV o aluno desenvolveu um desses algoritmos integrando-o ao DEMOOP.Este trabalho continua com a implementação de outros algoritmos de busca de contatos e deverá utilizar técnicas de programação paralela em alguns destes algoritmos para possibilitar a simulação de problemas macroscópicos com centenas de milhões de partículas ou mais.

Palavras-chave: Computação Científica, Algoritmos de Busca de Contatos, Método de Elementos Discretos.