Bachelor Thesis BCLR-2479

BibliographyBrunn, Malte: Data-mining on adaptively refined sparse grids with higher order basis functions on GPUs.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 2479 (2016).
87 pages, english.
CR-SchemaF.2.1 (Numerical Algorithms and Problems)
G.0 (Mathematics of Computing General)
G.1.2 (Numerical Analysis Approximation)
KeywordsData-mining, sparse grids, GPU

Mankind produces enormous amounts of data through simulations, observations, and experiments. With improving technology such as more precise measurements and faster supercomputers this data grows rapidly and has to be stored, computed, and evaluated. Thus, efficient algorithms are needed to process all this data in order to extract useful information. Most of this data is high-dimensional and it depends on a variety of parameters. Methods based on regular grids fail to handle it reasonably since the complexity of the problem exponentially depends on the number of dimensions. However, methods for sparse grids reduce this complexity while maintaining the accuracy. In this work a parallel approach for regression and classification tasks on adaptively refined sparse grids with higher order basis functions is presented. The developed algorithms are tested and analyzed on graphic accelerator cards. The results of a previous work about a parallel approach for the hierarchisation on regular sparse grids are reused to develop highly parallel algorithms for the hierarchisation, multi-evaluation, and the transposed evaluation on adaptively refined sparse grids. Furthermore, several optimizations for these sparse grid operations are explained. The hierarchisation as well as the multi-evaluation make use of the hierarchical structure of the grid to reduce the problem’s complexity, and the effects of sorting the evaluation points along a space-filling curve on the runtime of the operations are analyzed. The space-filling curve methods not only improve the cache usage and thread coherence of the parallel algorithms, but they also reduce the computational effort of algorithms based on the streaming approach. The transposed evaluation achieves speed-ups by factors from 2 to up to 11 compared to a parallel implementation without space-filling curve optimizations. The effects on the thread coherence and the cache usage improve the runtime of the hierarchical evaluation by a factor of up to 10 for adaptively refined grids. Additionally, a benchmark analysis of the developed methods with respect to the maximal polynomial degree shows that the degree for most of the basis functions is strongly limited by the grid level. Thus, the runtime and the complexity do not behave in a linear fashion with respect to the maximal polynomial degree as expected.

Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Simulation of Large Systems
Superviser(s)Jun.-Prof. Dr. rer. nat. Dirk Pflüger
Entry dateMarch 2, 2018
   Publ. Department   Publ. Institute   Publ. Computer Science