Publication

Implementação e Avaliação de Algoritmos BSP/CGM para o Fecho Transitivo e Problemas Relacionados

Bibliographic Details
Summary:	Neste trabalho, descrevemos e apresentamos os resultados da implementação de um algoritmo BSP/CGM para o fecho transitivo proposto por Cáceres et al. Além disso, apresentamos algumas aplicações deste algoritmo na resolução de problemas relacionados em teoria dos grafos, tais como caminhos mais curtos, busca em profundidade e árvore geradora mínima. Estes algoritmos foram implementados em C, usando a interface LAM/MPI e executados no Beowulf do IC-UNICAMP, contendo 66 processadores. Os resultados obtidos são melhores que os descritos na literatura. Para os problemas relacionados, as implementação que usam a estrutura do algoritmo de Warshall para o fecho transitivo apresentam melhores tempos, quando comparadas a algumas implementações paralelas para os mesmos problemas.
Main Authors:	Castro Junior, Amaury Antonio de
Subject:	Teoria dos Grafos Algoritmos Programação Paralela Algoritmos Úteis e Específicos
Year:	2011
Country:	Brazil
Document type:	master thesis
Access type:	open access
Associated institution:	IBICT
Language:	Portuguese
Origin:	Oasisbr

Description
Summary:	Neste trabalho, descrevemos e apresentamos os resultados da implementação de um algoritmo BSP/CGM para o fecho transitivo proposto por Cáceres et al. Além disso, apresentamos algumas aplicações deste algoritmo na resolução de problemas relacionados em teoria dos grafos, tais como caminhos mais curtos, busca em profundidade e árvore geradora mínima. Estes algoritmos foram implementados em C, usando a interface LAM/MPI e executados no Beowulf do IC-UNICAMP, contendo 66 processadores. Os resultados obtidos são melhores que os descritos na literatura. Para os problemas relacionados, as implementação que usam a estrutura do algoritmo de Warshall para o fecho transitivo apresentam melhores tempos, quando comparadas a algumas implementações paralelas para os mesmos problemas.

No funded projects found.