ISOMORPH: an efficient application on GPU for detecting graph isomorphism
ISSN: 0264-4401
Article publication date: 6 September 2023
Issue publication date: 12 October 2023
Abstract
Purpose
The authors will review the main concepts of graphs, present the implemented algorithm, as well as explain the different techniques applied to the graph, to achieve an efficient execution of the algorithm, both in terms of the use of multiple cores that the authors have available today, and the use of massive data parallelism through the parallelization of the algorithm, bringing the graph closer to the execution through CUDA on GPUs.
Design/methodology/approach
In this work, the authors approach the graphs isomorphism problem, approaching this problem from a point of view very little worked during all this time, the application of parallelism and the high-performance computing (HPC) techniques to the detection of isomorphism between graphs.
Findings
Results obtained give compelling reasons to ensure that more in-depth studies on the HPC techniques should be applied in these fields, since gains of up to 722x speedup are achieved in the most favorable scenarios, maintaining an average performance speedup of 454x.
Originality/value
The paper is new and original.
Keywords
Acknowledgements
Since acceptance of this article, the following author have updated their affiliations: Manuel Curado is at the Universidad de Alicante, Alicante, Spain.
This work has been supported by the Fundación Séneca del Centro de Coordinación de la Investigación de la Región de Murcia under Project 20813/PI/18 and by the Spanish “Agencia Estatal de Investigación” under grant PID2020-112827GB-I00/AEI/10.13039/501100011033.
Citation
Llanes, A., Imbernón Tudela, B., Curado, M. and Soto, J. (2023), "ISOMORPH: an efficient application on GPU for detecting graph isomorphism", Engineering Computations, Vol. 40 No. 7/8, pp. 1807-1818. https://doi.org/10.1108/EC-07-2022-0476
Publisher
:Emerald Publishing Limited
Copyright © 2023, Emerald Publishing Limited