AnyDSL: A Partial Evaluation Framework for Programming High-Performance Libraries

HiPEAC 2018 Paper Award

This paper advocates programming high-performance code using partial evaluation. We present a clean-slate programming system with a simple, annotation-based, online partial evaluator that operates on a CPS-style intermediate representation. Our system exposes code generation for accelerators (vectorization/parallelization for CPUs and GPUs) via compiler-known higher-order functions that can be subjected to partial evaluation. This way, generic implementations can be instantiated with target-specific code at compile time.

In our experimental evaluation we present three extensive case studies from image processing, ray tracing, and genome sequence alignment. We demonstrate that using partial evaluation, we obtain high-performance implementations for CPUs and GPUs from one language and one code base in a generic way. The performance of our codes is mostly within 10%, often closer to the performance of multi man-year, industry-grade, manually-optimized expert codes that are considered to be among the top contenders in their fields.

BibTeX
@article{leissa2018anydsl,
  author          = {Leißa, Roland and Boesche, Klaas and Hack, Sebastian and Pérard-Gayot, Arsène and Membarth, Richard and Slusallek, Philipp and Müller, André and Schmidt, Bertil},
  title           = {{AnyDSL}: A Partial Evaluation Framework for Programming High-Performance Libraries},
  journal         = {Proceedings of the ACM on Programming Languages (PACMPL)},
  pages           = {119:1--119:30},
  volume          = {2},
  number          = {OOPSLA},
  %year            = 2018,
  %month           = nov,
  date            = {2018-11-04/2018-11-09},
  note            = {{HiPEAC 2018 Paper Award}},
  doi             = {10.1145/3276489},
  publisher       = {ACM}
}

Recent Publications

A. Müller B. Schmidt A. Hildebrandt R. Membarth R. Leißa M. Kruse S. Hack
AnySeq: A High Performance Sequence Alignment Library based on Partial Evaluation

Proceedings of the 34th IEEE International Parallel \& Distributed Processing Symposium (IPDPS), pp. 1-11, New Orleans, LA, USA, May 5-8, 2020

Read more
E. Sánchez Morales R. Membarth A. Gaull P. Slusallek T. Dirndorfer A. Kammenhuber C. Lauer M. Botsch
Parallel Multi-Hypothesis Algorithm for Criticality Estimation in Traffic and Collision Avoidance

Proceedings of the 30th IEEE Intelligent Vehicles Symposium (IV), pp. 2164-2171, Paris, France, June 9-12, 2019

Read more
R. Membarth H. Dutta F. Hannig J. Teich
Efficient Mapping of Streaming Applications for Image Processing on Graphics Cards

Transactions on High-Performance Embedded Architectures and Compilers (Transactions on HiPEAC), V: 1-20, 2019

Read more