论文标题
带有RT芯的加速力指向图形图
Accelerating Force-Directed Graph Drawing with RT Cores
论文作者
论文摘要
带有弹簧嵌入式的图形图在该图的顶点设置上采用V X V计算阶段来计算排斥力。在这里，力的功效会减小距离：顶点可以有效地影响其位置周围某个半径的其他顶点。因此，该算法将自己用于使用搜索数据结构来降低运行时复杂性的实现。 NVIDIA RT核心在硬件中实现层次树遍历。我们展示了如何将以力定向方法查找图形布局的问题映射到射线跟踪问题，该问题随后可以使用专用的射线跟踪硬件来实现。因此，我们在CUDA软件实施中观察到4倍至13倍的加速度。
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.
