From Loop Fusion to Kernel Fusion: A Domain-specific Approach to Locality Optimization

Bo Qiao, Oliver Reiche, Frank Hannig, J├╝rgen Teich

to appear in Proceedings of 2019 International Symposium on Code Generation and Optimization (CGO19)

Abstract

Optimizing data-intensive applications such as image processing for GPU targets with complex memory hierarchies requires to explore the tradeoffs among locality, parallelism, and computation. Loop fusion as one of the classical optimization techniques has been proven effective to improve locality at the instruction level. Algorithms in image processing are increasing their complexities and generally consist of many kernels in a pipeline. The inter-kernel communications are intensive and exhibit another opportunity for locality improvement at a higher level. The scope of this paper is an optimization technique called kernel fusion for data locality improvement. We present a formal description of the problem by defining an objective function for locality optimization. By transforming the fusion problem to a graph partitioning problem, we propose a solution based on the minimum cut technique to search fusible kernels recursively. In addition, we develop an analytic model to quantitatively estimate potential locality improvement by incorporating domain-specific knowledge and architecture details. The proposed technique is implemented in an image processing DSL and source-to-source compiler called HIPAcc, and evaluated over six image processing applications on three Nvidia GPUs. A geometric mean speedup of up to 2.52 can be observed in our experiments.

Individual Files

Results

Execution Times in ms.



Acknowledgements

This work is partially supported by Siemens Healthineers and the German Research Foundation (DFG) as part of the Transregional Collaborative Research Centre ``Invasive Computing.''

Last updated: