15037

An Efficient Parallel Algorithm for Graph Isomorphism on GPU using CUDA

Min-Young Son, Young-Hak Kim, Byoung-Woo Oh
Dept. of Computer Engineering, Kumoh National Institute of Technology, Yangho-dong, Gumi, Gyeongbuk 730-701 Republic of Korea
International Journal of Engineering and Technology (IJET), Vol. 7 No. 5, 2015

@article{son2015efficient,

   title={An Efficient Parallel Algorithm for Graph Isomorphism on GPU using CUDA},

   author={Son, Min-Young and Kim, Young-Hak and Oh, Byoung-Woo},

   year={2015}

}

Download Download (PDF)   View View   Source Source   

748

views

Modern Graphics Processing Units (GPUs) have high computation power and low cost. Recently, many applications in various fields have been computed powerfully on the GPU using CUDA. In this paper, we propose an efficient parallel algorithm for graph isomorphism which runs on the GPU using CUDA for matching large graphs. Parallelization of a sequential graph isomorphism algorithm is one of the hardest problems because it includes inherently sequential characteristics. Our approach divides the given graphs into smaller blocks using a divide-and-conquer, and then maps the blocks to parallel processing units on the GPU. The smaller blocks are solved in individual processing units, and then the results are combined using hierarchical procedures. In the experiment, we used random graphs from vertices of small size to up to tens of thousands of vertices in order to solve efficiently graph isomorphism for large graphs. The experimental results show that the proposed approach brings a considerable improvement in performance and efficiency comparing to the CPU-based results. Our result also shows high performance, especially on large graphs.
VN:F [1.9.22_1171]
Rating: 5.0/5 (2 votes cast)
An Efficient Parallel Algorithm for Graph Isomorphism on GPU using CUDA, 5.0 out of 5 based on 2 ratings

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: