Abstract
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.
Users
Please
log in to take part in the discussion (add own reviews or comments).