Implementações paralelas para os problemas do fecho transitivo e caminho mínimo APSP na GPU

Página do item simplificado
dc.contributor.advisor1Martins, Wellington Santos
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/3041686206689904por
dc.contributor.referee1Martins, Wellington Santos
dc.contributor.referee2Nascimento, Hugo Alexandre Dantas
dc.contributor.referee3Cárceres, Edson Norberto
dc.creatorGaioso, Roussian Di Ramos Alves
dc.creator.Latteshttp://lattes.cnpq.br/3536210071193629por
dc.date.accessioned2014-10-30T14:29:29Z
dc.date.issued2014-08-08
dc.description.abstractThis 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. Keywordseng
dc.description.provenanceSubmitted 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)eng
dc.description.provenanceApproved 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)eng
dc.description.provenanceMade 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-08eng
dc.description.resumoEste 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.por
dc.description.sponsorshipConselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPqpor
dc.formatapplication/pdf*
dc.identifier.citationGAIOSO, 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.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/3471
dc.languageporpor
dc.publisherUniversidade Federal de Goiáspor
dc.publisher.countryBrasilpor
dc.publisher.departmentInstituto de Informática - INF (RG)por
dc.publisher.initialsUFGpor
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)por
dc.rightsAcesso Abertopor
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectGPUpor
dc.subjectGPGPUpor
dc.subjectCUDApor
dc.subjectTeoria dos Grafospor
dc.subjectFecho transitivopor
dc.subjectAPSPpor
dc.subjectCaminho mínimopor
dc.subjectBFSpor
dc.subjectWarshallpor
dc.subjectDijkstrapor
dc.subjectFloydWarshallpor
dc.subjectParalelismopor
dc.subjectGPUeng
dc.subjectGPGPUeng
dc.subjectCUDAeng
dc.subjectGraph Theoryeng
dc.subjectTransitive closureeng
dc.subjectAPSPeng
dc.subjectWarshalleng
dc.subjectBFSeng
dc.subjectWarshalleng
dc.subjectFloydWarshalleng
dc.subjectDijkstraeng
dc.subjectParalleleng
dc.subjectMinimum Patheng
dc.subjectParallelismeng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor
dc.thumbnail.urlhttp://repositorio.bc.ufg.br/tede/retrieve/11246/Disserta%c3%a7%c3%a3o%20-%20Roussian%20Di%20Ramos%20Alves%20Gaioso%20-%202014.pdf.jpg*
dc.titleImplementações paralelas para os problemas do fecho transitivo e caminho mínimo APSP na GPUpor
dc.title.alternativeParallel implementations for transitive closure and minimum path APSP problems in GPUeng
dc.typeDissertaçãopor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Dissertação - Roussian Di Ramos Alves Gaioso - 2014.pdf
Tamanho:
5.84 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Mestrado em Ciência da Computação (INF)