Accelerating Force-Directed Graph Drawing with RT Cores

Stefan Zellmann, Martin Weier, Ingo Wald

Graph drawing with spring embedders employs a V x 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 4x to 13x over a CUDA software implementation.