Towards Triangle Counting on GPU using Stable Radix binning
Nishith Tirpankar, Hari Sundar · 2018
The pattern of computations of graph algorithms makes them difficult to parallelize. They suffer from erratic data access patterns. We propose a set of algorithmic patterns that enable users to take advantage of fine grained parallelism provided by modern CPU and GPU architectures. This allows accesses to be regularized which improves hierarchical cache access. We also propose a parallel stable binning algorithm that can be used for computing set intersection. This is illustrated through its application to triangle counting in large graphs.