GTC 2020 Invited Talk: New High Performance Graph Analytics Technique and a GPU Implementation

Abstract

We’ll introduce a new algorithm called anti-section transitive closure (ATC) for finding the transitive closure of a graph, including a new technique, called anti-sections, for finding reachable vertices. ATC works on both sparse and large networks. ATC scales naturally to massively multi-threaded systems such as GPUs. Finding the transitive closure of a graph is computationally expensive and has required a large memory footprint. Prior approaches assume dense graphs, however, real-world networks like cyber networks are extremely sparse, and the existing methods do not scale on large, sparse networks. By leveraging anti-sections and the Hornet dynamic graph data structure, we’re able to reduce the memory footprint required and show that ATC significantly outperforms common CPU and prior GPU implementations. ATC can outperform NetworkX by several orders of magnitude, and it outperforms a highly-tuned GraphBLAS CPU solution by 400x on a single NVIDIA GPU.

David A. Bader

Distinguished Professor and Director of the Institute for Data Science

David A. Bader is a Distinguished Professor in the Department of Computer Science at New Jersey Institute of Technology.