High Performance Exact Triangle Counting on GPUs
Mauro Bisson, Massimiliano Fatica · IEEE Transactions on Parallel and Distributed Systems · 2017
This paper presents a GPU implementation of the graph triangle counting operation based on the set intersection algorithm. The algorithm is implemented in four kernels optimized for different types of graphs in a code delivering performance higher than the current state-of-the-art and without preprocessing the input graph. At runtime, a lightweight heuristic is used to select the kernel to run based on the specific graph taken as input. In contrast to previous works, the presented approach takes advantage of a set intersection operation implemented via bitmaps. Moreover, the simplicity of the approach allows the code to have limited size and engineering complexity.