Accelerating Force-Directed Graph Drawing with RT Cores

Stefan Zellmann, Martin Weier, Ingo Wald

External link (DOI)
View presentation:2020-10-28T16:00:00ZGMT-0600Change your timezone on the schedule page
2020-10-28T16:00:00Z
Exemplar figure
Drawing a Twitter feed graph (68K vertices, 101K edges) with a force-directed algorithm using RT cores. The images show the results after N = 1 (left), N = 100 (second from left), N = 2,000 (second from right), and N = 12,000 (right) iterations. We can generate these layouts in 0.003, 0.43, 7.35, and 39.3 seconds, and outperform a typical CUDA software implementation by 10.2×, 7.44×, 9.6×, and 10.9×, respectively.
Fast forward

Direct link to video on YouTube: https://youtu.be/HiPVx2NgmR4

Keywords

"Spatial Data Structures", "Acceleration Data Structures", "Search Data Structures" "Info-Vis", "Graph Drawing" "Graph Drawing", "Ray Tracing Hardware"

Abstract

Graph drawing with spring embedders employs a V × V computation phase over the graph's vertex set to compute repulsive forces. Here, the efficacy of forces diminishes with distance: a vertex can effectively only influence other vertices in a certain radius around its position. Therefore, the algorithm lends itself to an implementation using search data structures to reduce the runtime complexity. NVIDIA RT cores implement hierarchical tree traversal in hardware. We show how to map the problem of finding graph layouts with force-directed methods to a ray tracing problem that can subsequently be implemented with dedicated ray tracing hardware. With that, we observe speedups of 4× to 13× over a CUDA software implementation.