Locality-Aware Scheduling for Stencil Code in Halide

摘要

Halide is a domain-specific language designed for image processing and stencil computation. Existing programming languages require the sacrifice of readability, portability and modularity to write high-performance image processing programs. Optimizing the execution strategy of a program oftentimes results in the heavy modification of code, which is a burden to a programmer. To simplify a programmer's task in optimizing his or her application, Halide separates the schedule and the algorithm of an application. A program's schedule can be changed independently in Halide, as the language decouples the algorithm and the schedule of an application. However, the exploration of possible schedules remains difficult and time-consuming. Exhaustive exploration is too common and brute-force. This paper proposes a locality-aware scheduler for the stencil computation. Exhaustive search is replaced by an algorithm using an analytical model. The algorithm delivers the overlapped tiling schedule with its tile size selection. We are able to achieve higher performance from the overlapped tiling scheduling due to better locality. In the Jacobi example, 8-time speedup over the baseline schedule is observed. We improve over the baseline scheduling in Halide without the exploration of all possible schedules.