Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/62443
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Wagner Meira Júnior | pt_BR |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/9092587237114334 | pt_BR |
dc.contributor.advisor-co1 | George Luiz Medeiros Teodoro | pt_BR |
dc.contributor.referee1 | Phillippe Olivier Alexandre Navaux | pt_BR |
dc.contributor.referee2 | Alba Cristina Magalhães Alves de Melo | pt_BR |
dc.contributor.referee3 | Fernando Magno Quintão Pereira | pt_BR |
dc.contributor.referee4 | Renato Antônio Celso Ferreira | pt_BR |
dc.creator | Samuel Benjoino Ferraz Aquino | pt_BR |
dc.creator.Lattes | http://lattes.cnpq.br/5538148900331053 | pt_BR |
dc.date.accessioned | 2024-01-04T00:02:45Z | - |
dc.date.available | 2024-01-04T00:02:45Z | - |
dc.date.issued | 2023-10-26 | - |
dc.identifier.uri | http://hdl.handle.net/1843/62443 | - |
dc.description.abstract | Mineração de padrões em grafos (MPG) é uma área em constante evolução e que compreende algoritmos com alto custo computacional. Algoritmos de MPG são construídos a partir da enumeração de subgrafos, que visita um grafo de entrada e retorna os subgrafos que atendem uma propriedade desejada. Graphics Processing Units (GPUs) tem sido amplamente utilizadas para acelerar algoritmos em diversas áreas. Entretanto, a enumeração de subgrafos apresenta um padrão irregular de processamento, e sua implementação em GPUs é ineficiente por conta de acessos não coalescidos de memória, divergências e desbalanceamento de carga. As estratégias existentes na literatura para a paralelização da enumeração de subgrafos em GPU são limitadas e não representam uma solução completa para todos os desafios desse problema nesta arquitetura. Esta tese propõe estratégias para projetar e implementar a enumeração de subgrafos de maneira eficiente em GPUs. Nossa estratégia de exploração DFS-wide reduz o consumo de memória e oportuniza otimizações no padrão de acesso a memória, que aliada ao fluxo de execução warp-centric, minimizam as divergências e melhoram o uso da capacidade computacional da GPU. Também propomos uma camada de balanceamento de carga de baixo custo para melhorar a utilização da GPU. Nossas estratégias foram implementadas em um sistema de enumeração chamado DuMato, que provê uma API para implementar eficientemente algoritmos de MPG. Nossa avaliação experimental mostrou que os algoritmos de MPG implementados com DuMato são até duas ordens de magnitude mais rápidos que os algoritmos implementados utilizando sistemas de MPG do estado da arte, além de serem capazes de minerar subgrafos maiores. | pt_BR |
dc.description.resumo | Graph Pattern Mining (GPM) is an important and rapidly evolving area which demands high computation-demanding algorithms. GPM algorithms rely on subgraph enumeration, extracting subgraphs from an input graph that matches a given property. Graphics Processing Units (GPUs) have been an excellent platform for accelerating algorithms in many areas. However, the irregularity of subgraph enumeration makes it challenging for efficient execution on GPUs due to typical uncoalesced memory access, divergence, and load imbalance. These aspects have not been extensively addressed in previous work on subgraph enumeration using GPU. This thesis proposes strategies to design and implement subgraph enumeration efficiently on GPU. We propose a depth-first search style search (DFS-wide) that reduces memory demand while enabling sufficient parallelism to utilize the GPU, along with a warp-centric design that minimizes execution divergence and improves utilization of the GPU computing capabilities. We also propose a low-cost load-balancing layer to mitigate the inherent load imbalance of parallel subgraph enumeration. Our strategies have been implemented in a system named DuMato, which provides a simple programming interface to implement GPM algorithms efficiently. We perform an extensive evaluation of all proposed strategies, comparing DuMato with the state-of-the-art subgraph enumeration systems. Our evaluation has shown that DuMato is up to two orders of magnitude faster and can mine larger subgraphs. | pt_BR |
dc.description.sponsorship | CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico | pt_BR |
dc.description.sponsorship | FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais | pt_BR |
dc.description.sponsorship | CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior | pt_BR |
dc.language | eng | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | pt_BR |
dc.publisher.program | Programa de Pós-Graduação em Ciência da Computação | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | GPU | pt_BR |
dc.subject | Subgraph enumeration | pt_BR |
dc.subject | Irregular processing | pt_BR |
dc.subject | Load balancing | pt_BR |
dc.subject.other | Computação – Teses | pt_BR |
dc.subject.other | Mineração de dados (Computação) – Teses | pt_BR |
dc.subject.other | Algoritmos de computador – Teses | pt_BR |
dc.title | Strategies for efficient subgraph enumeration on GPUs | pt_BR |
dc.title.alternative | Estratégias para enumeração de subgrafos eficiente em GPUs | pt_BR |
dc.type | Tese | pt_BR |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Tese Samuel Final.pdf | 5.2 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.