Writing a DSL for high performance parallel programming in OxCaml

This article details the work of Sai Konkimalla during his summer internship at a firm, which focused on creating a domain-specific language (DSL) for high-performance parallel programming in OCaml. The DSL aims to make SIMD (single-instruction, multiple-data) code more ergonomic and accessible.

The company has a lot of performance-critical SIMD code running on CPUs, often requiring esoteric C code for inner loops. Writing and maintaining such code is challenging, and the programs are constrained to a specific instruction set, making it difficult to target different architectures or newer processors.

To address these challenges, Sai developed a compiler for his DSL that leverages recent OCaml features, such as runtime metaprogramming, to enable users to write kernel functions as regular OCaml functions. These functions can be compiled and run on multiple architectures, abstracting the SIMD code and allowing the compiler to optimize its execution.

The DSL utilizes the SPMD programming model, which differs from SIMD intrinsics and higher-level languages. In SPMD, developers write a program describing the loop body, and the compiler handles the parallel computation. This abstraction can lead to faster code execution, as compilers can make better decisions about hardware utilization.

For example, a CUDA kernel without a loop body would describe the loop body, and the compiler would translate it into low-level SIMD instructions. Similarly, Sai's DSL allows developers to write a function that computes a single entry of the output slice, and the SPMD compiler generates code to loop over the output slice, computing the value at each index.

By looping over the output rather than the inputs, the compiler can optimize the code more easily, as each iteration writes to a specific location. This design decision avoids complexities that arise from writing loops over inputs, as different iterations could potentially write to the same output entry.

One key aspect of Sai's project is executing the SPMD compiler at runtime, also known as just-in-time (JIT) compilation. JIT compilation allows the compiler to generate code while the program is running, offering two main advantages. Firstly, it eliminates the need to build for all potential target architectures at compile time. Secondly, it enables the compiler to use runtime data for optimizations, which is crucial for generating high-performance code.

For instance, in Sai's project, the compiler can use runtime data to compile away branch instructions, which can slow down execution by consuming CPU resources. By compiling after knowing the value of a metric variable, the JIT compiler can produce more efficient code without the need for branching during runtime.

Overall, Sai's DSL demonstrates the potential of higher-level programming models like SPMD in generating high-performance parallel code. By abstracting away hardware-specific details and leveraging runtime metaprogramming, the DSL aims to make SIMD programming more accessible and maintainable.