A carregar...
Publicação
Grafos Dinâmicos em GPUs
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 5.44 MB | Adobe PDF |
Orientador(es)
Resumo(s)
Os grafos são estruturas de dados utilizadas para modelar diversos problemas em várias
áreas da ciência, desde a sua representação de moléculas na química, ao uso da representa-
ção de redes de comunicação na ciência da computação. À medida que a sua popularidade
aumenta, aumenta também a necessidade de aplicações que simultaneamente analisem
e processem eficientemente grafos de grandes dimensões. Nestes casos a utilização das
capacidades altamente paralelizáveis da GPUs tem se relevado promissora.
Muitos dos problemas modelados com grafos necessitam que o grafo evolua com o
passar do tempo, com a adição e/ou remoção de novos nós e arestas. Este requisito propõe
novos desafios no processamento de grafos no GPU tornando o desenvolvimento destas
ferramentas uma área de investigação relevante e atual.
Nesta dissertação de mestrado apresentamos Marrow-Graph, uma biblioteca de pro-
cessamento de grafos dinâmicos em GPU, construída usando o Marrow – uma framework
em C++ para computação paralela de sistemas heterogéneos, desenvolvida no centro de
investigação NOVA-LINCS. Os nossos testes revelam que com a partição do grafo em
diferentes segmentos é possível criar um grafo que suporta adições e remoções de vértices
e arestas eficientes, em qualquer estado. Tornando possível não só evitar sobrecargas de
uma reconstrução do grafo como também é possível o seu processamento em GPU.
Graphs are data structures used to model diverse problems in various Sciences, from the representation of molecules in Chemistry, to their use in the representation of comunica- tion networks in computer science. As their popularity increases, so does the necessity for applications that simultaneously analyze and process efficiently large scale graphs. In these cases, the capability of a GPU to perform highly parallel computation has shown promise. Many of the problems modelled with graphs require the graph to evolve over time, with the addition and/or removal of new edges and vertices. This requirement poses new challenges in the processing of graphs by the GPU, turning the development of these tools into a relevant and current research area. In this master’s thesis we present Marrow-Graph, a dynamic GPU graph processing library, built using Marrow - a C++ framework for parallel computing of heterogeneous systems, developed at the NOVA-LINCS investigation center. Our tests show that by partiotioning the graph in different segments, it is possible to create a graph that supports the efficient addition and removal of vertices and edges in any state, making it possible not only to to avoid graph reconstruction overhead, but also possible to process it by GPU.
Graphs are data structures used to model diverse problems in various Sciences, from the representation of molecules in Chemistry, to their use in the representation of comunica- tion networks in computer science. As their popularity increases, so does the necessity for applications that simultaneously analyze and process efficiently large scale graphs. In these cases, the capability of a GPU to perform highly parallel computation has shown promise. Many of the problems modelled with graphs require the graph to evolve over time, with the addition and/or removal of new edges and vertices. This requirement poses new challenges in the processing of graphs by the GPU, turning the development of these tools into a relevant and current research area. In this master’s thesis we present Marrow-Graph, a dynamic GPU graph processing library, built using Marrow - a C++ framework for parallel computing of heterogeneous systems, developed at the NOVA-LINCS investigation center. Our tests show that by partiotioning the graph in different segments, it is possible to create a graph that supports the efficient addition and removal of vertices and edges in any state, making it possible not only to to avoid graph reconstruction overhead, but also possible to process it by GPU.
Descrição
Palavras-chave
Grafos GPU Processamento de Grafos Dinâmicos Marrow