Building-Blocks for Performance Oriented DSLs

Tiark Rompf, Arvind K. Sujeeth, HyoukJoong Lee, Kevin J. Brown, Hassan Chafi, Martin Odersky, Kunle Olukotun

This paper, presented at the 2011 IFIP Working Conference on Domain-Specific Languages, introduces a powerful approach to bridging the gap between high-level programming productivity and low-level hardware performance.

TL;DR

The authors present Delite, a framework built on top of Scala that allows developers to create high-performance, domain-specific languages (DSLs) with minimal effort. By using "Lightweight Modular Staging," Delite turns high-level DSL code into an intermediate representation that can be automatically optimized and compiled for heterogeneous hardware like multi-core CPUs and GPUs.

What Problem Does This Paper Address?

Modern hardware is increasingly complex, featuring multiple CPU cores and specialized accelerators like GPUs. To get maximum performance, programmers are often forced to use low-level, hardware-specific models (like CUDA for GPUs or MPI for clusters). This creates a "productivity gap": you can have high-level, maintainable code that is slow, or low-level, brittle code that is fast.

Domain-Specific Languages (DSLs) offer a solution by providing abstractions tailored to a specific field (like machine learning or image processing). However, building a custom, high-performance compiler for every new DSL is an enormous task. The authors address this by providing a reusable "building block" framework that handles the "heavy lifting" of optimization and parallel code generation.

Methods

The core of the paper is the interaction between two technologies:

  1. Lightweight Modular Staging (LMS): This is a technique in Scala that allows a program to act as a "generator." Instead of just running the code, LMS builds an Intermediate Representation (IR)—essentially a graph of the program's logic. This IR can then be analyzed and transformed before any "real" code is generated.
  2. The Delite Framework: Delite sits on top of LMS and provides high-level parallel "building blocks" called DeliteOps (e.g., parallel map, reduce, filter).

When a developer writes a DSL using Delite, the framework:

  • Virtualizes the language so it feels like a standard library but acts like a compiler.
  • Fuses loops to reduce memory overhead and improve cache hits.
  • Generates target code (Scala, C++, or CUDA) automatically based on the available hardware.
  • Schedules execution across heterogeneous resources using a specialized runtime.

Datasets

The paper evaluates the framework using OptiML, a machine learning DSL built on Delite. The benchmarks include:

  • SPADE: A bioinformatics application for flow cytometry data.
  • Template Matching: An object recognition algorithm used in robotics.
  • Machine Learning Kernels: Restricted Boltzmann Machines (RBM), Gaussian Discriminant Analysis (GDA), and Naive Bayes (NB).

The evaluation compares OptiML's performance against hand-tuned C++ implementations and MATLAB.

Key Insights and Ideas

  • Staging is the "Secret Sauce": By separating the generation of the program from its execution, the framework can use the full power of a high-level language (Scala) to perform complex optimizations that would be impossible in a traditional compiler.
  • Domain Knowledge = Better Optimization: Because the compiler knows it is dealing with a "Vector" or a "Matrix" (rather than just generic pointers), it can perform aggressive "pattern rewrites." For example, it can recognize that the norm of a unit vector is always 1 and simply replace that entire computation with a constant.
  • Loop Fusion is Critical: One of the biggest performance wins comes from "fusing" multiple parallel operations into a single pass over the data. This drastically reduces the time spent moving data between the CPU and memory.

Key Results

  • Performance vs. C++: In the SPADE bioinformatics benchmark, OptiML generated code that performed comparably to (and in some cases slightly better than) hand-tuned, multi-threaded C++ code.
  • GPU Acceleration: For machine learning tasks, the framework showed massive speedups when targeting a GPU compared to a single-core CPU:
  • RBM: ~11x speedup.
  • GDA: ~4x speedup.
  • Naive Bayes: ~41x speedup.
  • Productivity: The authors demonstrate that complex optimizations (like those in the 9-line OptiML snippet for SPADE) result in generated code that looks remarkably similar to what a human expert would write in hundreds of lines of C++.

Limitations and Future Work

  • The "No-Sharing" Policy: To simplify parallelization, the current model is quite restrictive regarding mutable state and data sharing. The authors acknowledge that more sophisticated effect systems are needed for DSLs that rely heavily on mutation.
  • Fusion Heuristics: The current loop fusion is "greedy." While effective for functional-style code, more refined heuristics might be necessary for imperative-style DSLs to avoid creating overly complex loop bodies that hurt performance.
  • Debugging: Debugging "staged" code can be difficult, as the error might occur in the generator or the generated code. Improving the developer experience for DSL authors remains an ongoing challenge.

Summary updated

Abstract

Domain-specific languages raise the level of abstraction in software development. While it is evident that programmers can more easily reason about very high-level programs, the same holds for compilers only if the compiler has an accurate model of the application domain and the underlying target platform. Since mapping high-level, general-purpose languages to modern, heterogeneous hardware is becoming increasingly difficult, DSLs are an attractive way to capitalize on improved hardware performance, precisely by making the compiler reason on a higher level. Implementing efficient DSL compilers is a daunting task however, and support for building performance-oriented DSLs is urgently needed. To this end, we present the Delite Framework, an extensible toolkit that drastically simplifies building embedded DSLs and compiling DSL programs for execution on heterogeneous hardware. We discuss several building blocks in some detail and present experimental results for the OptiML machine-learning DSL implemented on top of Delite.
BibTeX
@misc{rompf2011building,
  author = {Tiark Rompf and Arvind K. Sujeeth and HyoukJoong Lee and Kevin J. Brown and Hassan Chafi and Martin Odersky and Kunle Olukotun},
  title = {{Building-Blocks for Performance Oriented DSLs}},
  year = {2011},
  eprint = {1109.0778},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1109.0778},
}

Loading related content...

Figure