Implementações paralelas para os problemas do fecho transitivo e caminho mínimo APSP na GPU
Carregando...
Data
2014-08-08
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
This paper presents a Graphics Processing Unit (GPU) based parallels implementations
for the All Pairs Shortest Paths and Transitive Closure problems in graph. The implementations
are based on the main sequential algorithms and takes full advantage of the
highly multithreaded architecture of current manycore GPUs. Our solutions reduces the
communication between CPU and GPU, improves the Streaming Multiprocessors (SMs)
utilization, and makes intensive use of coalesced memory access to optimize graph data
access. The advantages of the proposed implementations are demonstrated for several
graphs randomly generated using the widely known graph library GTgraph. Graphs containing
thousands of vertices and different edges densities, varying from sparse to complete
graphs, were generated and used in the experiments. Our results confirm that GPU
implementations can be competitive even for graph algorithms whose memory accesses
and work distribution are both irregular and data-dependent.
Keywords
Descrição
Palavras-chave
GPU , GPGPU , CUDA , Teoria dos Grafos , Fecho transitivo , APSP , Caminho mínimo , BFS , Warshall , Dijkstra , FloydWarshall , Paralelismo , GPU , GPGPU , CUDA , Graph Theory , Transitive closure , APSP , Warshall , BFS , Warshall , FloydWarshall , Dijkstra , Parallel , Minimum Path , Parallelism
Citação
GAIOSO, Roussian Di Ramos Alves. Implementações paralelas para os problemas do fecho transitivo e caminho mínimo APSP na GPU. 2014. 118 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2014.