An Efficient Parallel Algorithm for Graph Isomorphism on GPU using CUDA
Min-Young Son, Young‐Hak Kim, Byoung-Woo Oh · 2015
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. Keyword- Graph isomorphism, CUDA, Large graphs, GPU I. INTRODUCTION Graph is one of popular data representations in the field of computers, engineering, science, etc. One of the most fundamental techniques in solving graph problems is graph isomorphism algorithms, and graph isomorphism algorithm is used in many other graph applications. In general, the implementation of a serial- based graph algorithm is time consuming as the number of vertex and edge in graph increases (1). In particular, the graph isomorphism algorithms require rapid calculation time as the size of graph increases. Therefore, the more graph has vertices and edges, the more ratio of time for solving isomorphism problem in the various graph algorithms is consumed. Recently, there have been increasing graph applications with large size because of increasing big data (2), (3). Due to this large data, the serial-based graph algorithms are impractical because the time complexity is too high. The parallel implementation of graph algorithms for large graph is more effective than serial-based implementation. Several graph algorithms on supercomputer have been studied in order to improve the execution time of large graphs, but the use of supercomputer has real restrictions due to high cost. Other studies use CPU cluster for parallel implementation instead of supercomputer, but the existence of bottle neck problem that is caused by the synchronization in this cluster environment. Recently, the GPU (Graphics Processing Unit) provides high calculation capacity at a low cost. Since the GPU provides high computing power, low cost, and easy accessibility, GPU is used in various application fields. CUDA (Compute Unified Device Architecture) of Nvidia is a parallel structure of the thread mass, and provides a programming model that can be used in parallel hardware with the CPU. This allows the BSP (bulk synchronous parallel). These bulk thread parallelism uses divide-and-conquer method that each processing node solves small sub-problems, and they are combined together to resolve big problems. Each thread can access the global memory, and can be operated independently at the same time. This study considers a graph isomorphism problem which can be used as basic tools to match large graphs. It is very difficult for a sequential isomorphism algorithm to parallelize because it includes inherently sequential characteristics. The research about the parallel algorithm of graph isomorphism on the GPU has been not studied deeply by reason of inherent sequential problem. In this paper, we propose a parallel graph isomorphism algorithm which runs efficiently on the GPU using CUDA for matching large graphs. Our approach divides given graphs into smaller blocks using a divide-and-conquer, and then maps the smaller blocks to parallel processing units on the GPU. The results in each block are combined using hierarchical procedures after each block is solved independently at the same time in individual processing unit. In the experiment, we expend random graphs from vertices of small size to up to tens of thousands of vertices in order to show efficiently graph isomorphism for matching large graphs. The experiment shows that our approach brings a considerable improvement in performance and efficiency comparing to the CPU-based results, especially on large graphs.