A PARALLEL SUBGRAPH ISOMORPHISM ALGORITHM ON GPU USING BULK PROCESSING

• Main Author: AKBAR - NIM : 13514080 , ALI
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/25360
• Institution: Institut Teknologi Bandung

<p align="justify">Graph data structure becomes more popular since the ease given to represent complex relations and objects. A demand for a good performance on graph analytics becomes critical in business and scientific analysis. Subgraph isomorphism is one of those graph analytics tasks. Subgraph isomorphism problem is a NP-Hard problem to find all subgraphs that isomorph with the query graph within the data graph. This algorithm also becomes a fundamental step to perform analysis on graph e.g. extracting query from graph database and frequent subgraph mining. Serial algorithm on CPU becomes unpromising since a slow performance on a bigger dataset. GPU utilization on this algorithm has been developed but a lot of kernel function calls and harder work on a thread occurred in the process. In this paper we propose a new bulk processing strategy to minimize number of kernel function calls and ease the work on each thread to optimize the performance. This paper uses CUDA and NVIDIA GPU as its test environment.<p align="justify"> <br /> <br />