Parallel algorithms for Subgraph Isomorphism (OpenMP and MPI)

We proposed two parallel implementations of popular subgraph isomorphism solvers: VF2 and Glasgow. The recursive DFS in VF2 was parallelized using OpenMP tasks, and we aimed to limit the excessive work done by additional threads. In Glasgow, we parallelized the complete algorithm using OpenMP, and we put special attention to compiler optimizations and OpenMP task amount limitation. Furthermore, a large section of Glasgow was parallelized with MPI one-sided communication. All the implementations are benchmarked on a wide range of graph pairs from literature, and we compare our Glasgow OpenMP implementation with the parallel version proposed by the author of Glasgow algorithm. We discuss when good scaling can be expected, and where improvements are possible.