HLLC / ParaM

Development of ParaMq, or Parallelizing MATLAB compiler, started originally with a contract from the Ohio Supercomputer Center. It was first developed in C++, then moved to a specialized language called Stratego/XT for reasons of productivity, and eventually to Ruby when Stratego turned out to be too restrictive for implementing general-purpose algorithms. The current version of the software is more than 40,000 lines of Ruby code that, according to general estimates, would be equivalent to about five times as many lines in C or C++, translating to more than 200,000 lines of code. The compiler development started in 2006 and has been a continuing joint effort of several of my PhD and masters students as well as my own.

The software is targeted at both domain programmers who code their algorithms in MATLAB and also compiler researchers.

Even though this compiler infrastructure started out being specific to MATLAB, it has since been extended to also handle the language R. Consequently, the project has been renamed HLLC, i.e., High-level Languages Compiler. It currently contains the following major components:

1. Parsers and unparsers for MATLAB and R languages.
2. Converters to and from Static Single Assignment (SSA) form.
3. Data-flow analysis, including constant propagation, and live variable analysis.
4. Type inference, based on a novel strategy of leveraging the language interpreters.
5. Code generation in C++ as well as NVIDIA CUDA C language for GPUs.
6. An automatic computation partitioning algorithm that can split the MATLAB programs into CPU and GPU components, using the GPUmat library.
7. Data- and control-dependence analysis.
8. An automatic converter to task-parallel, data-flow style, program using Intel Threading Building Block (TBB) C++ library, leveraging type inference and C++ code generator (under active development).

The software has served as a testbed for several papers and continues to be pivotal in the ongoing research on optimizing array languages, including their parallelization and memory locality optimization.

Related publications:

1. Chun-Yu Shei, Pushkar Ratnalikar and Arun Chauhan. Automating GPU Computing in MATLAB. In Proceedings of the International Conference on Supercomputing (ICS), pages 245–254, 2011.
   [Article DOI]
2. Chun-Yu Shei, Adarsh Yoga, Madhav Ramesh and Arun Chauhan. MATLAB Parallelization through Scalarization. In Proceedings of the 15th Workshop on the Interaction between Compilers and Computer Architectures (INTERACT), pages 44–53, 2011. Held in conjunction with the 17th IEEE International Symposium on High Performance Computer Architecture (HPCA).
   [Article DOI]
3. Arun Chauhan and Chun-Yu Shei. Static Reuse Distances for Locality-based Optimizations in MATLAB. In Proceedings of the 24th ACM International Conference on Supercomputing (ICS), 2010.
   [Article DOI]
4. Chun-Yu Shei, Arun Chauhan and Sidney Shaw. Compile-time Disambiguation of MATLAB Types through Concrete Interpretation with Automatic Run-time Fallback. In Proceedings of the 16th annual IEEE International Conference on High Performance Computing (HiPC), 2009.
   [Article DOI]
5. Daniel McFarlin and Arun Chauhan. Library Function Selection in Compiling Octave. In Proceedings of the Workshop on Performance Optimization for High-Level Languages and Libraries (POHLL), held in conjunction with the 21st IEEE Parallel and Distributed Processing Symposium (IPDPS), March 2007.
   [Article DOI]