Patterns and Rewrite Rules for Systematic Code Generation From High-Level Functional Patterns to High-Performance OpenCL Code

Computing systems have become increasingly complex with the emergence of heterogeneous hardware combining multicore CPUs and GPUs. These parallel systems exhibit tremendous computa-tional power at the cost of increased programming effort. This re-sults in a tension between achieving performance and code porta-bility. Code is either tuned using device-specific optimizations to achieve maximum performance or is written in a high-level lan-guage to achieve portability at the expense of performance. We propose a novel approach that offers high-level program-ming, code portability and high-performance. It is based on algo-rithmic pattern composition coupled with a powerful, yet simple, set of rewrite rules. This enables systematic transformation and op-timization of a high-level program into a low-level hardware spe-cific representation which leads to high performance code. We test our design in practice by describing a subset of the OpenCL programming model with low-level patterns and by im-plementing a compiler which generates high performance OpenCL code. Our experiments show that we can systematically derive high-performance device-specific implementations from simple high-level algorithmic expressions. The performance of the gen-erated OpenCL code is on par with highly tuned implementations for multicore CPUs and GPUs written by experts