Paralelização do problema de graph matching para grafos exatos utilizando CUDA
Loading...
Submission Date
Defense Date
2020-12-03
Edition
Authors
Advisors
Co-Advisors
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
Description
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]