Home | english  | Impressum | Sitemap | KIT

Online-Autotuning of Parallel SAH kD-Trees

Online-Autotuning of Parallel SAH kD-Trees
Tagung:

Konferenzartikel 

Jahr:

2016 

Autoren:

Martin Tillmann
Philip Pfaffe
Christopher Kaag
Walter F. Tichy

Links:PDF

Summary

 

We explore the benefits of using online-autotuning to find an optimal configuration for the parallel construction of Surface Area Heuristic (SAH) kD-trees.

Using a quickly converging autotuning mechanism, we achieve a significant performance improvement of up to 1.96x.

The SAH kD-tree is a spatial data structure and a fundamental tool in the domain of computer graphics and simulations.
The parallel construction of these trees is influenced by several parameters, controlling various aspects of the algorithm.
However, the parameter configurations advocated in the literature are hardly ever portable.

To boost portability, we apply online-autotuning to four state-of-the-art variants of parallel kD-tree construction.
We show that speedups over the variants' standard configurations are possible with low programmer effort.
We further demonstrate the performance portability of our approach by evaluating performance on varying multicore platforms and both static and dynamic geometries.

 

Beteiligte Mitarbeiter (zufällige Reihenfolge)
Titel Vorname Nachname

Bibtex

@inproceedings{,
author={Martin Tillmann, Philip Pfaffe, Christopher Kaag, Walter F. Tichy},
title={Online-Autotuning of Parallel SAH kD-Trees},
year=2016,
booktitle={IPDPS},
url={https://ps.ipd.kit.edu/../ka_2016_online_autotuning_parallel_sah_kd_trees.pdf},

abstract={We explore the benefits of using online-autotuning to find an optimal configuration for the parallel construction of Surface Area Heuristic (SAH) kD-trees.

Using a quickly converging autotuning mechanism, we achieve a significant performance improvement of up to 1.96x.

The SAH kD-tree is a spatial data structure and a fundamental tool in the domain of computer graphics and simulations.
The parallel construction of these trees is influenced by several parameters, controlling various aspects of the algorithm.
However, the parameter configurations advocated in the literature are hardly ever portable.

To boost portability, we apply online-autotuning to four state-of-the-art variants of parallel kD-tree construction.
We show that speedups over the variants' standard configurations are possible with low programmer effort.
We further demonstrate the performance portability of our approach by evaluating performance on varying multicore platforms and both static and dynamic geometries.},
}