Title: An adaptive, hybrid data structure for sparse volume data on the GPU
Other Titles: Eine adaptive, hybride Datenstruktur für Volumen Datensätze auf der GPU
Language: English
Authors: Labschütz, Matthias 
Qualification level: Diploma
Advisor: Gröller, Eduard 
Issue Date: 2016
Labschütz, M. (2016). An adaptive, hybrid data structure for sparse volume data on the GPU [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2016.26562
Number of Pages: 97
Qualification level: Diploma
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 access.
Keywords: Volumen-Datenstruktur; GPU
volume data structure; GPU
URI: https://doi.org/10.34726/hss.2016.26562
DOI: 10.34726/hss.2016.26562
Library ID: AC13049385
Organisation: E186 - Institut für Computergraphik und Algorithmen 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.

Page view(s)

checked on May 11, 2022


checked on May 11, 2022

Google ScholarTM