Algoritmos BSP/CGM para o Fecho Transitivo

Abstract

Apresentamos duas estratégias e dois algoritmos BSP/CGM para computar o fecho transitivo de um digrafo. Nossas idéias foram obtidas através da avaliação dos resultados obtidos pelos algoritmos BSP/CGM de Alves et al. e Castro Jr.. Melhoramos o desempenho destes algoritmos diminuindo o tamanho das mensagens trocadas entre os processadores, a computação local e a quantidade de rodadas de comunicação entre os processadores. Os resultados obtidos através da implementação das nossas estratégias e algoritmos foram melhores que os resultados apresentados por outros autores.

We show two approaches and two BSP/CGM algorithms to compute a transitive closure of digraphs. Our ideas are based in a detailed observation of BSP/CGM algorithms presented by Alves et al. and Castro Jr.. We improved the algorithms performance by decreasing the message length changed between processors, the local computation and the number of communication rounds. The results obtained by implementations of our approaches and algorithms are better than the results obtained by other authors.