faimGraph: High Performance Management of Fully-Dynamic Graphs Under Tight Memory Constraints on the GPU

Authors: Martin Winter (Graz University of Technology), Daniel Mlakar (Graz University of Technology), Rhaleb Zayer (Max Planck Institute for Informatics), Hans-Peter Seidel (Max Planck Institute for Informatics), Markus Steinberger (Graz University of Technology, Max Planck Institute for Informatics)

Abstract: In this paper, we present a fully-dynamic graph data structure for the Graphics Processing Unit (GPU). It delivers high update rates while keeping a low memory footprint using autonomous memory management directly on the GPU. The data structure is fully-dynamic, allowing not only for edge but also vertex updates. Performing the memory management on the GPU allows for fast initialization times and efficient update procedures without additional intervention or reallocation procedures from the host. faimGraph is the first GPU graph framework that fully reclaims unused memory, permitting long time application with highly changing graph structures. Performance evaluations show that our approach outperforms that previous state-of-the-art in for all types of graph updates. Furthermore, evaluate algorithmic performance using a PageRank and a Static Triangle Counting (STC) implementation, demonstrating the suitability of the framework even for memory access intensive algorithms.


Presentation: file


Back to Technical Papers Archive Listing