Building-Blocks for Performance Oriented DSLs

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

Abstract

Domain-specific languages (DSLs) raise the level of abstraction in software development, allowing programmers to reason more easily about high-level logic. However, compilers can only achieve similar reasoning if they possess an accurate model of the application domain and the underlying target platform. As mapping high-level, general-purpose languages to modern, heterogeneous hardware becomes increasingly difficult, DSLs offer an attractive path to capitalizing on hardware performance by enabling compilers to operate at a higher level of abstraction. Implementing efficient DSL compilers is a daunting task; therefore, support for building performance-oriented DSLs is urgently needed. To this end, we present the Delite Framework, an extensible toolkit that simplifies building embedded DSLs and compiling DSL programs for execution on heterogeneous hardware. We discuss several building blocks in detail and present experimental results for the OptiML machine-learning DSL implemented on top of Delite.

Introduction: The Productivity Gap

Modern hardware architecture is characterized by increasing complexity, featuring multi-core CPUs and specialized accelerators like GPUs. To extract maximum performance from these systems, developers are often forced to use low-level, hardware-specific programming models such as CUDA for GPUs or MPI for clusters. This creates a significant "productivity gap": developers must choose between high-level, maintainable code that suffers from poor performance, or low-level, brittle code that is highly optimized but difficult to write and maintain.

Domain-Specific Languages (DSLs) provide a potential solution by offering abstractions tailored to specific fields, such as machine learning or image processing. However, the cost of building a custom, high-performance compiler for every new DSL is prohibitive. The Delite Framework addresses this by providing a reusable "building block" infrastructure that handles the complexities of optimization and parallel code generation.

The Delite Framework Architecture

Delite is built as a layer on top of Scala, utilizing two primary technological pillars to bridge the gap between productivity and performance:

1. Lightweight Modular Staging (LMS)

LMS is a technique that allows a Scala program to act as a generator. Instead of executing code immediately, LMS builds an Intermediate Representation (IR)—a graph representing the program's logic. This IR serves as the foundation for analysis and transformation before any final code is generated, allowing the framework to use the full expressive power of Scala to perform optimizations that are typically impossible in traditional compilers.

2. Delite Building Blocks (DeliteOps)

Delite provides high-level parallel building blocks known as DeliteOps. These include standard functional patterns such as parallel map, reduce, and filter. When a developer creates a DSL using Delite, the framework performs several critical tasks:

  • Virtualization: The DSL feels like a standard library to the user but functions as a compiler internally.
  • Loop Fusion: The framework automatically fuses multiple parallel operations into a single pass over the data, reducing memory overhead and improving cache locality.
  • Heterogeneous Code Generation: Delite automatically generates target code (Scala, C++, or CUDA) based on the available hardware resources.
  • Dynamic Scheduling: A specialized runtime schedules execution across heterogeneous resources to maximize throughput.

Domain-Specific Optimizations

One of the primary advantages of the Delite approach is the ability to leverage domain knowledge for better optimization. Because the compiler understands it is manipulating high-level constructs like "Vectors" or "Matrices" rather than generic pointers, it can perform aggressive pattern rewrites. For instance, the compiler can recognize that the norm of a unit vector is always 1 and replace the entire computation with a constant, or it can reorder matrix operations to minimize memory traffic.

Evaluation: The OptiML Case Study

To evaluate the framework, the authors implemented OptiML, a machine learning DSL. The performance of OptiML was tested against hand-tuned C++ and MATLAB implementations using several benchmarks:

  • Bioinformatics (SPADE): An application for flow cytometry data. OptiML generated code that performed comparably to, and occasionally outperformed, hand-tuned multi-threaded C++.
  • Machine Learning Kernels: The framework demonstrated massive speedups when targeting GPUs compared to single-core CPUs, including an 11x speedup for Restricted Boltzmann Machines (RBM), a 4x speedup for Gaussian Discriminant Analysis (GDA), and a 41x speedup for Naive Bayes (NB).

These results highlight that the generated code for complex operations—such as those found in the SPADE benchmark—closely mirrors the structure and efficiency of code written by human experts, but with significantly less development effort.

Limitations and Future Directions

While Delite represents a significant step forward, several challenges remain:

  • Mutable State: To simplify parallelization, Delite currently enforces a restrictive "no-sharing" policy. Future iterations will require more sophisticated effect systems to support DSLs that rely heavily on mutation.
  • Fusion Heuristics: The current loop fusion strategy is "greedy." While effective for functional code, more refined heuristics may be needed for imperative-style DSLs to prevent the creation of overly complex loop bodies that could degrade performance.
  • Developer Experience: Debugging "staged" code is inherently difficult because errors can occur in either the generator or the generated code. Improving the debugging and diagnostic tools for DSL authors is a priority for future work.

Conclusion

The Delite Framework demonstrates that by providing the right building blocks, it is possible to simplify the creation of high-performance DSLs. By combining Lightweight Modular Staging with parallel primitives and domain-specific optimizations, Delite allows developers to achieve the performance of hand-tuned low-level code without sacrificing the productivity of high-level programming languages.

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},
}
Figure