Detalhes bibliográficos
| Ano de defesa: |
2014 |
| Autor(a) principal: |
Gaioso, Roussian Di Ramos Alves
 |
| Orientador(a): |
Martins, Wellington Santos
|
| Banca de defesa: |
Martins, Wellington Santos,
Nascimento, Hugo Alexandre Dantas,
Cárceres, Edson Norberto |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Universidade Federal de Goiás
|
| Programa de Pós-Graduação: |
Programa de Pós-graduação em Ciência da Computação (INF)
|
| Departamento: |
Instituto de Informática - INF (RG)
|
| País: |
Brasil
|
| Palavras-chave em Português: |
|
| Palavras-chave em Inglês: |
|
| Área do conhecimento CNPq: |
|
| Link de acesso: |
http://repositorio.bc.ufg.br/tede/handle/tede/3471
|
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 |
