Fri 17 Jun 2022 15:30 - 15:50 at Cockatoo - Rewriting Chair(s): Chandrakana Nandi

Optimizing programs to run efficiently on modern parallel hardware is hard but crucial for many applications. The predominantly used imperative languages - like C or OpenCL - force the programmer to intertwine the code describing functionality and optimizations. This results in a portability nightmare that is particularly problematic given the accelerating trend towards specialized hardware devices to further increase efficiency.

Many emerging DSLs used in performance demanding domains such as deep learning or high-performance image processing attempt to simplify or even fully automate the optimization process. Using a high-level - often functional - language, programmers focus on describing functionality in a declarative way. In some systems such as Halide or TVM, a separate schedule specifies how the program should be optimized. Unfortunately, these schedules are not written in well-defined programming languages. Instead, they are implemented as a set of ad-hoc predefined APIs that the compiler writers have exposed.

In this functional pearl, we show how to employ functional programming techniques to solve this challenge with elegance. We present two functional languages that work together - each addressing a separate concern. RISE is a functional language for expressing computations using well known functional data-parallel patterns. ELEVATE is a functional language for describing optimization strategies. A high-level RISE program is transformed into a low-level form using optimization strategies written in ELEVATE . From the rewritten low-level program high-performance parallel code is automatically generated. In contrast to existing high-performance domain-specific systems with scheduling APIs, in our approach programmers are not restricted to a set of built-in operations and optimizations but freely define their own computational patterns in RISE and optimization strategies in ELEVATE in a composable and reusable way. We show how our holistic functional approach achieves competitive performance with the state-of-the-art imperative systems Halide and TVM.

Fri 17 Jun

Displayed time zone: Pacific Time (US & Canada) change

15:30 - 16:50
RewritingSIGPLAN Track at Cockatoo
Chair(s): Chandrakana Nandi Certora, inc.
15:30
20m
Talk
(ICFP 2020) Achieving high-performance the functional way: a functional pearl on expressing high-performance optimizations as rewrite strategies
SIGPLAN Track
Bastian Hagedorn NVIDIA, Johannes Lenfers University of Münster, Thomas Koehler University of Glasgow, Xueying Qin University of Glasgow, United Kingdom, Sergei Gorlatch University of Münster, Germany, Michel Steuwer University of Edinburgh
Link to publication DOI Authorizer link Pre-print
15:50
20m
Talk
(PLDI 2020) Optimizing Homomorphic Evaluation Circuits by Program Synthesis and Term Rewriting
SIGPLAN Track
DongKwon Lee Seoul National University, South Korea, Woosuk Lee Hanyang University, Hakjoo Oh Korea University, Kwangkeun Yi Seoul National University
16:10
20m
Talk
(ICFP 2021) Grafs: Declarative Graph Analytics
SIGPLAN Track
Farzin Houshmand University of California, Riverside, Mohsen Lesani University of California at Riverside, Keval Vora Simon Fraser University
16:30
20m
Talk
(POPL 2022) Verified Tensor-Program Optimization Via High-level Scheduling Rewrites
SIGPLAN Track
Amanda Liu Massachusetts Institute of Technology, Gilbert Louis Bernstein University of California at Berkeley, Adam Chlipala MIT CSAIL, Jonathan Ragan-Kelley MIT