Data parallel implementation of the GRAIL index on many-core architectures

Reachability is among the most common problems to address when working on graphs since it is the base for many other algorithms, and scalable solutions have become of paramount importance with the advent of distributed systems that process large amounts of data. Specifically many applications explore graphs with millions of nodes and vertices, which explains why the development of fast and scalable algorithms entails complex challenges. Modern GPUs are highly parallel systems based on many-core architectures and have gained popularity in parallelizing algorithms that run on large data sets. In this context the NVIDIA CUDA platform has been used to provide a concrete implementation of the developed algorithms. The main focus of this work is to analyze the GRAIL algorithm, which creates a scalable index for answering reachability queries on large graphs, in order to design an implementation that exhibits a greater amount of data parallelism. The GRAIL index relies heavily on depth-first search, which is among the hardest algorithms to develop on parallel systems, so an alternative approach based on breadth-first search will be explored and significant effort will be devoted towards explaining the difficulties encountered and the solutions chosen to overcome them. Finally this work will provide a concrete implementation on CUDA of the proposed algorithms, a comparison between the indexing and search times for the CPU and the GPU based versions and insight on how to conduct further research in future.