Generic Programming in Space and Time: Abstractions for High Performance Code Generation

The development of high performance libraries on modern hardware is extremely difficult and often requires reimplementation or retuning with every new processor generation. Program generators that produce such libraries automatically from a high level description are an appealing solution but only few exist to date. The difficulty is in both the design of the generator but also its actual implementation, which often results in an ad-hoc collection of standalone programs and scripts that are hard to extend, maintain, or reuse. At the same time, research in the area of metaprogramming is among the most promising candidates to resolve the abstraction/performance trade-off that plagues software engineering. It has been used to enable generic programming for a long time, with C++ templates being one of the most prominent examples. This dissertation focuses on the reverse task, applying generic programming in the field of metaprogramming and program generation. In the process we widen the implementation space covered in generic programming by the dimension of time, resulting in stage polymorphism. This allow us to reason about algorithms, without fixing their execution to specific execution stages. In this dissertation we develop and explore novel abstractions to achieve this goal. These abstractions allow us to build program generators using a principled generic programming approach. As a case study we implement a generator for the fast Fourier transform (FFT). This generator is able to abstract over various spatial and temporal aspects of the generated code