ANATOMY OF HIGH PERFORMANCE PARALLEL 1-DIMENSIONAL STENCIL

Abstract

Stencils, or structured mesh computations, are a fundamental class of compu-tations characterized by convolutional neural networks, finite difference, image processing, computer vision, cellular automata, geophysics, and climate mod- eling. Reliably extracting performance from these operations across modern hardware is sufficiently challenging that they are included in standard compiler benchmarks. This is in part because the design space for these problems is very large, and only a few designs obtain high performance for a given target. For compilers, it is difficult to explore this design space, so they use heuristics that are still unable to find optimal solutions. Hand tuning stencils is also a chal- lenge as a unique kernel would be required for each problem of interest and each hardware target of interest. Whether the kernel is hand tuned or generated by a compiler, the problem is that many constraints need to be simultaneously satis- fied, such as maximizing instruction level parallelism, managing register pressure, utilizing vector instructions, while maximizing floating point throughput. This work provides a model-based approach for high performance 1-Dimensional sten- cils, along with a BLIS-like algorithm providing a layered interface. We validate our model by demonstrating very high performance across a variety of CPU microarchitectures.