Paralelização do problema de graph matching para grafos exatos utilizando CUDA
Carregando...
Arquivos
Data de Submissão
Data de Defesa
2020-12-03
Edição
Autores
Orientadores
Coorientadores
Editores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Descrição
O problema de graph matching aplicado a grafos exatos consiste em achar a similaridade entre dois grafos, definindo se estes possuem uma similaridade por completo (grafos isomorfos) ou se existe algum subgrafo similar (subgrafos isomorfos). Ainda não foi determinado se esse problema pertence à classe P ou NP-Completo, não existindo algoritmos polinomiais para a solução do mesmo. Desta forma, frequentemente são utilizadas heurísticas para a solução, sendo que entre essas destacam-se o VF2. Dentro deste contexto, neste trabalho foi desenvolvida uma implementação paralela da heurística VF2. Essa foi desenvolvida utilizando a biblioteca CUDA, de forma a explorar o paralelismo em GPUs. Para os testes, foram gerados grafos com três tamanhos distintos, sendo eles: grafos pequenos de 4 vértices, grafos médios com 8 vértices e grafos grandes com 12 vértices. A partir dos testes realizados verificou-se que versão paralela, utilizando grafos pequenos, médios e grande é, respectivamente, 1,66, 1,44 e 1,38 mais rápida que a versão sequencial. [resumo fornecido pelo autor]