Título: BUSCA EM LARGURA COM ESTRUTURA BAG E PADRÕES OPENMP E MPI EM MÁQUINAS DE ALTO DESEMPENHO

Autoria de: Márcio Inácio Santana

Orientação de: Sanderson Lincohn Gonzaga de Oliveira

Presidente da banca: Sanderson L. Gonzaga de Oliveira

Primeiro membro da banca: Diego Nunes Brandão

Segundo membro da banca: Denilson Alves Pereira

Palavras-chaves: Algoritmos Paralelos, Busca em Largura, Estrutura bag, MPI, OpenMP

Data da defesa: 19/11/2021

Semestre letivo da defesa: 2021-1

Data da versão final: 01/12/2021

Data da publicação: 01/12/2021

Referência: Santana, M. I. BUSCA EM LARGURA COM ESTRUTURA BAG E PADRÕES OPENMP E MPI EM MÁQUINAS DE ALTO DESEMPENHO. 2021. 83 p. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação Bacharelado)-Universidade Federal de Lavras, Lavras, 2021.

Resumo: O desenvolvimento de implementações paralelas eficientes da busca em largura é de interesse fundamental, pois esse algoritmo é largamente utilizado como base em aplicações na ciência e na indústria. O objetivo deste trabalho foi desenvolver implementações paralelas da busca em largura utilizando a API OpenMP e a biblioteca MPI e a realização de amplo conjunto de testes em máquinas de alto desempenho para medir e analisar a performance dessas implementações. A metodologia consistiu na utilização da estrutura bag, por meio de adaptação do algoritmo PBFS de Leiserson e Schardl para duas versões de paralelização, uma com OpenMP puro (PBFSO) e outra com MPI e OpenMP (PBFSH). Foram aferidos os speedups das implementações paralelas, quando executadas sobre 63 grafos de teste em 2 máquinas de alto desempenho distintas. Os resultados obtidos por este trabalho foram o alcance de implementações funcionais do algoritmo PBFS, a descrição detalhada das versões adaptadas e a realização de testagem ampla em máquinas de alto desempenho com a medição dos speedups alcançados. As implementações desenvolvidas neste trabalho se mostraram, quando executadas sequencialmente, mais rápidas do que o algoritmo tradicional de busca em largura sequencial com fila (BFS). As médias geométricas dos tempos de execução sequenciais dos algoritmos PBFSO e PBFSH , foram 5,93 e 4,82 menores, respectivamente, que a média geométrica dos tempos de execução do algoritmo BFS. O algoritmo PBFSO atingiu speedups máximos de 1,0 a 45,4, enquanto o PBFSH atingiu speedups máximos entre 1,0 e 23,3. A implementação que emprega MPI e OpenMP apresentou desempenho geral pior que a versão paralelizada por OpenMP puro, porém os resultados dos testes indicam um melhor uso do hyperthreading por parte daquela versão.

URI: sip.prg.ufla.br/publico/trabalhos_conclusao_curso/acessar_tcc_por_curso/
ciencia_da_computacao/20211201611010

URI alternaviva: repositorio.ufla.br/handle/1/54256

Curso: G010 - CIÊNCIA DA COMPUTAÇÃO (BACHARELADO)

Nome da editora: Universidade Federal de Lavras

Sigla da editora: UFLA

País da editora: Brasil

Gênero textual: Trabalho de Conclusão de Curso

Nome da língua do conteúdo: Português

Código da língua do conteúdo: por

Licença de acesso: Acesso aberto

Nome da licença: Licença do Repositório Institucional da Universidade Federal de Lavras

URI da licença: repositorio.ufla.br

Termos da licença: Acesso aos termos da licença em repositorio.ufla.br

Detentores dos direitos autorais: Márcio Inácio Santana e Universidade Federal de Lavras

Baixar arquivo