Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs
Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs
复制标题
Hornet：GPU 上动态稀疏图和矩阵的高效数据结构
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
David A. Bader
中科院分区：
文献类型：
--
作者：
F. Busato;Oded Green;N. Bombieri;David A. Bader
稀疏数据计算在科学和工程中无处不在。与密集数据计算不同，稀疏数据计算在执行中具有更少的局部性和更大的不规则性，这使得它们在并行化和优化方面更具挑战性。并行架构上的稀疏数据表示的许多现有格式仅限于静态数据问题，而动态数据表示的格式在性能和内存占用方面都效率低下。这项工作提出了大黄蜂，一种新的数据表示，目标是动态数据问题。Hornet是可扩展的输入大小，并且在数据演化期间不需要任何数据重新分配或重新初始化。我们展示了一个大黄蜂GPU架构的实现，并将其与最广泛使用的静态和动态数据结构进行比较。
Sparse data computations are ubiquitous in science and engineering. Unlike their dense data counterparts, sparse data computations have less locality and more irregularity in their execution, making them significantly more challenging to parallelize and optimize. Many of the existing formats for sparse data representations on parallel architectures are restricted to static data problems, while those for dynamic data suffer from inefficiency both in terms of performance and memory footprint. This work presents Hornet, a novel data representation that targets dynamic data problems. Hornet is scalable with the input size, and does not require any data re-allocation or re-initialization during the data evolution. We show a Hornet implementation for GPU architectures and compare it to the most widely used static and dynamic data structures.