Anti-Section Transitive Closure
Anti-Section Transitive Closure
复制标题
DOI：
10.1109/hipc53243.2021.00033
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Oded Green;Zhihui Du;Sanyamee Patel;Zehui Xie;Hang Liu;David A. Bader
中科院分区：
文献类型：
--
作者：
Oded Green;Zhihui Du;Sanyamee Patel;Zehui Xie;Hang Liu;David A. Bader
图的传递闭包是一个新的图，其中每个顶点都直接连接到原始图中所有与它有路的顶点。传递闭包对于可达性和关系查询很有用。查找传递闭包可能在计算上是昂贵的，并且需要很大的内存占用，因为输出通常大于输入。一些关于传递闭包的原始研究假设图是稠密的，并使用稠密邻接矩阵。我们已经了解到，许多现实世界的网络是非常稀疏的，现有的方法不能扩展。在这项工作中，我们介绍了一个新的算法，称为反截面传递闭包（ATC）的图的传递闭包。我们提出了一个新的平行边操作-反截面-为找到新的可达顶点的边缘。ATC可扩展到大规模多线程系统，例如具有数万个线程的NVIDIA GPU。我们证明了反截运算与图分析中的三角形求交运算具有某些共同的性质。最后，我们认为传递闭包问题是一个需要边插入的动态图问题。通过这样做，我们的内存占用更小。我们还展示了一种使用两种不同技术并行创建批处理的方法：双轮和哈希。使用这些技术和大黄蜂动态图数据结构，我们展示了我们的新算法的NVIDIA泰坦V GPU。我们比较了其他软件包，如NetworkX，SEI-GBTL，SuiteSparse和cuSparse。
The transitive closure of a graph is a new graph where every vertex is directly connected to all vertices to which it had a path in the original graph. Transitive closures are useful for reachability and relationship querying. Finding the transitive closure can be computationally expensive and requires a large memory footprint as the output is typically larger than the input. Some of the original research on transitive closures assumed that graphs were dense and used dense adjacency matrices. We have since learned that many real-world networks are extremely sparse, and the existing methods do not scale. In this work, we introduce a new algorithm called Anti-section Transitive Closure (ATC) for finding the transitive closure of a graph. We present a new parallel edges operation - anti-sections - for finding new edges to reachable vertices. ATC scales to massively multi-threaded systems such as NVIDIA's GPU with tens of thousands of threads. We show that the anti-section operation shares some traits with the triangle counting intersection operation in graph analysis. Lastly, we view the transitive closure problem as a dynamic graph problem requiring edge insertions. By doing this, our memory footprint is smaller. We also show a method for creating the batches in parallel using two different techniques: dual-round and hash. Using these techniques and the Hornet dynamic graph data structure, we show our new algorithm on an NVIDIA Titan V GPU. We compare with other packages such as NetworkX, SEI-GBTL, SuiteSparse, and cuSparse.