In search of a program generator to implement generic transformations for high-performance computing

• Published in: Science of computer programming 2006-09, Vol.62 (1), p.25-46
• Main Authors: Cohen, Albert, Donadio, Sébastien, Garzaran, Maria-Jesus, Herrmann, Christoph, Kiselyov, Oleg, Padua, David
• Format: Article
• Language: English
• Subjects: Adaptive libraries; Application-specific program generators; Computer Science; Distributed, Parallel, and Cluster Computing; Embedded Systems; Loop transformations; Multi-stage programming; Programming Languages
• ISSN: 0167-6423; 1872-7964
• DOI: 10.1016/j.scico.2005.10.013

The quality of compiler-optimized code for high-performance applications is far behind what optimization and domain experts can achieve by hand. Although it may seem surprising at first glance, the performance gap has been widening over time, due to the tremendous complexity increase in microprocessor and memory architectures, and to the rising level of abstraction of popular programming languages and styles. This paper explores in-between solutions, neither fully automatic nor fully manual ways to adapt a computationally intensive application to the target architecture. By mimicking complex sequences of transformations useful to optimize real codes, we show that generative programming is a practical means to implement architecture-aware optimizations for high-performance applications. This work explores the promises of generative programming languages and techniques for the high-performance computing expert. We show that complex, architecture-specific optimizations can be implemented in a type-safe, purely generative framework. Peak performance is achievable through the careful combination of a high-level, multi-stage evaluation language–MetaOCaml–with low-level code generation techniques. Nevertheless, our results also show that generative approaches for high-performance computing do not come without technical caveats and implementation barriers concerning productivity and reuse. We describe these difficulties and identify ways to hide or overcome them, from abstract syntaxes to heterogeneous generators of code generators, combining high-level and type-safe multi-stage programming with a back-end generator of imperative code.