Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/62443
Type: | Tese |
Title: | Strategies for efficient subgraph enumeration on GPUs |
Other Titles: | Estratégias para enumeração de subgrafos eficiente em GPUs |
Authors: | Samuel Benjoino Ferraz Aquino |
First Advisor: | Wagner Meira Júnior |
First Co-advisor: | George Luiz Medeiros Teodoro |
First Referee: | Phillippe Olivier Alexandre Navaux |
Second Referee: | Alba Cristina Magalhães Alves de Melo |
Third Referee: | Fernando Magno Quintão Pereira |
metadata.dc.contributor.referee4: | Renato Antônio Celso Ferreira |
Abstract: | 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. |
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. |
Subject: | Computação – Teses Mineração de dados (Computação) – Teses Algoritmos de computador – Teses |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/62443 |
Issue Date: | 26-Oct-2023 |
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.