Compact data structure and scalable algorithms for the sparse grid technique
Compact data structure and scalable algorithms for the sparse grid technique
复制标题
稀疏网格技术的紧凑数据结构和可扩展算法
DOI：
10.1145/1941553.1941559
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
D. Pflüger
中科院分区：
文献类型：
--
作者：
A. Murarasu;Josef Weidendorfer;G. Buse;D. Butnaru;D. Pflüger
稀疏网格离散化技术实现了高维函数的压缩表示。在最初的形式中，它严重依赖递归和复杂的数据结构，因此远远不能很好地适合GPU。在这篇文章中，我们描述了使我们能够在NVIDIA图形处理器上实现压缩和解压缩的优化，这是我们应用程序的关键稀疏网格算法。其主要思想是多维稀疏网格中的点集和一组连续的自然数之间的双射映射。所产生的数据结构消耗的内存量最小。对于大约有1.27亿个点的10维稀疏网格，它消耗的内存比通常使用的树或哈希表少30倍。与顺序CPU实现相比，在GPU上实现的压缩加速比高达17%，解压缩加速比高达70%。我们表明，这些优化也适用于多核CPU。
The sparse grid discretization technique enables a compressed representation of higher-dimensional functions. In its original form, it relies heavily on recursion and complex data structures, thus being far from well-suited for GPUs. In this paper, we describe optimizations that enable us to implement compression and decompression, the crucial sparse grid algorithms for our application, on Nvidia GPUs. The main idea consists of a bijective mapping between the set of points in a multi-dimensional sparse grid and a set of consecutive natural numbers. The resulting data structure consumes a minimum amount of memory. For a 10-dimensional sparse grid with approximately 127 million points, it consumes up to 30 times less memory than trees or hash tables which are typically used. Compared to a sequential CPU implementation, the speedups achieved on GPU are up to 17 for compression and up to 70 for decompression, respectively. We show that the optimizations are also applicable to multicore CPUs.