high performance computing on graphics processing units: hgpu.org

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.