Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-30T14:24:27Z
No. of bitstreams: 2
Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-30T14:29:29Z (GMT) No. of bitstreams: 2
Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-30T14:29:29Z (GMT). No. of bitstreams: 2
Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf: 6127790 bytes, checksum: 9990f791c0f9abaee7e3e03e4cdc8ee4 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2014-08-08 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / 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 / Este trabalho apresenta implementações paralelas baseadas em Graphics Processing Unit
(GPU) para os problemas da identificação dos caminhos mínimos entre todos os pares
de vértices e do fecho transitivo em um grafo. As implementações são baseadas nos
principais algoritmos sequenciais e tiram 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. As vantagens dessas implementações propostas são demonstradas por vários grafos
gerados aleatoriamente utilizando a ferramenta GTgraph. Grafos contendo milhares de
vértices foram gerados e utilizados nos experimentos. Nossos resultados confirmam 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/3471 |
| Date | 08 August 2014 |
| Creators | Gaioso, Roussian Di Ramos Alves |
| Contributors | Martins, Wellington Santos, Martins, Wellington Santos, Nascimento, Hugo Alexandre Dantas, Cárceres, Edson Norberto |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, -2555911436985713659 |
Page generated in 0.0028 seconds