Finding optimal parameters for acceleration structures for raytracing is key to improved performance. Previous research has shown that a speedup of over 10% of rendering time is possible. Some parameters are interdependent which complicates the process of finding an optimal configuration. It is hence interesting to find them efficiently. Autotuning is an automatic optimization scheme able to search for optimal configurations and has been applied successfully to kD-trees in the past, which we apply today on BVHs. The more parameters to optimize, the more difficult it is to find optimal solutions. In this article, we analyze in detail the behavior of the parameters and their impact on acceleration structure building and rendering time. We show the interdependence and context sensitivity (i.e., scene, viewpoint) of the parameters. Based on the use case, this allows to target only crucial parameters. Convergence speed towards an optimal configuration is essential. To find better parameters, the autotuner needs to build the acceleration structure over and over, changing parameters every time. We introduce a hybrid model-based prediction and online autotuning method to address this issue. The prediction model allows for both instantaneous near-optimal configurations when inputs are known or similar, and efficient search of the configuration space when inputs are completely new. Online autotuning outperforms configurations recommended in literature by up to 11% median. The prediction model achieves 95% of the maximum speedup of the autotuner while reducing 90% of its overhead. Thus, hybrid online autonuning enables always-on tuning in ray tracing.

Identifying the (near) optimal program variants an optimizing and parallelizing compiler should generate is known to be difficult. Autotuning is the best solution to navigate the often high-dimensional space of possible options. However, to be practical an autotuner should (a) have high convergence speed and (b) be robust in face of varying inputs. Current techniques for offline tuning, where convergence speed is less important, provide solutions only for known inputs, whereas online tuning can be input sensitive but currently lacks in convergence speed. In this paper, we present hierarchical online-autotuning, a novel technique to exploit structure in the search space and the underlying tuning problem to increase convergence speed during online tuning. By modeling symmetries and redundancies in configurations and by exploiting domain knowledge to predict performance we reduce the search space size by orders of magnitudes. Combining our tuner with a polyhedral parallelizing compiler for GPUs, we show that the performance of a GEMM GPU kernel generated with default parameters is increased by 6× and that the convergence speed of the tuning process is increased by a factor of up to 1.7 compared to OpenTuner. With hierarchical tuning we make the deployment of always-on online-autotuning practical.

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.