An Adaptive, Hybrid Data Structure for Sparse Volume Data on the GPU

Information

• Publication Type: Master Thesis
• Workgroup(s)/Project(s):
  • Visualization Group
• Date: January 2016
• First Supervisor:
  • Eduard Gröller
  • Peter Rautek

Abstract

Dealing with large, sparse, volume data on the GPU is a necessity in many applications such as volume rendering, processing or simulation. The limited memory budget of modern GPUs restricts users from uploading large volume data-sets entirely. Fortunately, sparse data, i.e., data containing large empty regions, can be represented more efficiently compared to a common dense array. Our approach makes it possible to upload a full data set even if the original volume does not fit on the GPU.

In previous work, a variety of sparse data structures have been utilized on the GPU, each with different properties. Tree representations, such as the octree, kd tree or N3 tree, provide a hierarchical solution for data sets of relatively low sparsity. For data sets of medium sparsity, spatial hashing makes more efficient access and storage possible. Extremely sparse data can be efficiently represented and accessed via binary search in sorted voxel lists.

Our observation is, that data sets often contain regions of different sparsity. Depending on the sparsity of a region, a specific data structure (e.g., an octree, a voxel list) requires the least memory to store the data. We formulate an algorithm that is able to automatically find this memory-optimal representation. By using such a combination of different data structures, we achieve an even better representation than any single data structure for real world data sets. We call such a data structure a hybrid data structure.

Any sparse data structure introduces an access overhead. For example, the access to an octree requires one additional indirection per height level of the tree. A voxel list has to be searched to retrieve a specific element. By using a hybrid data structure, we also introduce an access overhead on top of the overhead that comes from using a sparse data structure. In our work we introduce JiTTree, which utilizes a data aware just-in-time compilation step to improve the access performance of our hybrid data structure.

We show that the implementation of our hybrid data structure effectively reduces the memory requirement of sparse data sets. JiTTree can improve the performance of hybrid bricking for certain access patterns such as stencil accesses.

Additional Files and Images

Weblinks

No further information available.

BibTeX

@mastersthesis{Labschuetz_Matthias_2016_AHD,
  title =      "An Adaptive, Hybrid Data Structure for Sparse Volume Data on
               the GPU",
  author =     "Matthias Labsch\"{u}tz",
  year =       "2016",
  abstract =   "Dealing with large, sparse, volume data on the GPU is a
               necessity in many applications such as volume rendering,
               processing or simulation. The limited memory budget of
               modern GPUs restricts users from uploading large volume
               data-sets entirely. Fortunately, sparse data, i.e., data
               containing large empty regions, can be represented more
               efficiently compared to a common dense array. Our approach
               makes it possible to upload a full data set even if the
               original volume does not fit on the GPU.  In previous work,
               a variety of sparse data structures have been utilized on
               the GPU, each with different properties. Tree
               representations, such as the octree, kd tree or N3 tree,
               provide a hierarchical solution for data sets of relatively
               low sparsity. For data sets of medium sparsity, spatial
               hashing makes more efficient access and storage possible.
               Extremely sparse data can be efficiently represented and
               accessed via binary search in sorted voxel lists.  Our
               observation is, that data sets often contain regions of
               different sparsity. Depending on the sparsity of a region, a
               specific data structure (e.g., an octree, a voxel list)
               requires the least memory to store the data. We formulate an
               algorithm that is able to automatically find this
               memory-optimal representation. By using such a combination
               of different data structures, we achieve an even better
               representation than any single data structure for real world
               data sets. We call such a data structure a hybrid data
               structure.  Any sparse data structure introduces an access
               overhead. For example, the access to an octree requires one
               additional indirection per height level of the tree. A voxel
               list has to be searched to retrieve a specific element. By
               using a hybrid data structure, we also introduce an access
               overhead on top of the overhead that comes from using a
               sparse data structure. In our work we introduce JiTTree,
               which utilizes a data aware just-in-time compilation step to
               improve the access performance of our hybrid data structure.
                We show that the implementation of our hybrid data
               structure effectively reduces the memory requirement of
               sparse data sets. JiTTree can improve the performance of
               hybrid bricking for certain access patterns such as stencil
               accesses.",
  month =      jan,
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  school =     "Institute of Computer Graphics and Algorithms, Vienna
               University of Technology ",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2016/Labschuetz_Matthias_2016_AHD/",
}