Paralelização do Algoritmo Floyd-Warshall usando GPU - Gaioso, Roussian R. A.; Jradi, Walid A. R.; Paula, Lauro C. M. de; Alencar, Wanderley de S.; Martins, Wellington S.; Nascimento, Hugo Alexandre D. do; Cáceres, Edson N. (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD); 2013: Anais do XIV Simpósio em Sistemas Computacionais de Alto DesempenhoDO - 10.5753/wscad.2013.16769, 2013)
Este artigo apresenta uma implementação paralela baseada em Graphics Processing Unit (GPU) para o problema da identiﬁcação dos caminhos mínimos entre todos os pares de vértices em um grafo. A implementação é baseada no algoritmo Floyd-Warshall e tira o máximo proveito da arquitetura multithreaded das GPUs atuais. Nossa solução reduz a comunicação entre a Central Processing Unit (CPU) e a GPU, melhora a utilização dos Streaming Multiprocessors (SMs) e faz um uso intensivo de acesso aglutinado em memória para otimizar o acesso de dados do grafo. A vantagem da implementação proposta é demonstrada por vários grafos gerados aleatoriamente utilizando a ferramenta GTgraph . Grafos contendo milhares de vértices foram gerados e utilizados nos experimentos. Os resultados mostraram um excelente desempenho em diversos grafos, alcançando ganhos de até 149x, quando comparado com uma implementação sequencial, e superando implementações tradicionais por um fator de quase quatro vezes. Nossos resultados conﬁrmam que implementações baseadas em GPU podem ser viáveis mesmo para algoritmos de grafos cujo acessos à memória e distribuição de trabalho são irregulares e causam dependência de dados.