Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/445
Tipo: Dissertação
Título: Implementação e Avaliação de Algoritmos BSP/CGM para o Fecho Transitivo e Problemas Relacionados
Autor(es): Castro Junior, Amaury Antonio de
Abstract: 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.
In this work we describe and present the results of the implementation of a transitive closure BSP/CGM algorithm proposed by Cáceres et al. We introduce some applications of this algorithm in the resolution of related problems in graph theory, such as shortest paths, breadth-first search and minimum spanning tree. These algorithms were implemented in C, using LAM/MPI interface and were executed on the Beowulf of IC-UNICAMP, containing 66 processors. The results obtained are better than described in the literature. For the related problems, the implementations that use the Warshall’s algorithm for transitive closure present better times, when compared them some existent parallel implementations or the same problems.
Palavras-chave: Teoria dos Grafos
Algoritmos
Programação Paralela
Algoritmos Úteis e Específicos
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/445
Data do documento: 2003
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Amaury Antonio de Castro Junior.pdf627,29 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.