\matlab is a popular numeric programming language, used by millions of
scientists, engineers as well as students worldwide\cite{MatlabGrowth}.  \matlab
programmers appreciate the high-level matrix operators,  the fact that variables
and types do not need to be declared, the large number of library and builtin
functions available, and the interactive style of program development available
through the IDE and the interpreter-style read-eval-print loop.  However, even
though \matlab programmers appreciate all of the features that enable rapid
prototyping,  their applications are often quite compute intensive and time
consuming. These applications could perform much more efficiently if they could
be easily ported to a high performance computing system.  

\xten\cite{x10}, on the other hand, is an object-oriented and statically-typed
language which uses cilk-style arrays indexed by \emph{Point} objects and
rail-backed multidimensional arrays, and has been designed with well-defined
semantics and high performance computing in mind.  The \xten compiler can
generate C++ or Java code and supports various communication interfaces
including sockets and MPI for communication between nodes on a parallel
computing system.

In this thesis we present MIX10, a source-to-source compiler that helps to
bridge the gap between MATLAB, a language familiar to scientists, and X10, a
language designed for high performance computing systems. MIX10 statically
compiles MATLAB programs to X10 and thus allows scientists and engineers to
write programs in MATLAB (or use old programs already written in MATLAB) and
still get the benefits of high performance computing without having to learn a
new language.Also, systems that use MATLAB for prototyping and C++ or Java for
production, can benefit from MIX10 by quickly convert- ing MATLAB prototypes to
C++ or Java programs via X10

On one hand, all the aforementioned characteristics of \matlab make it a very
user-friendly and thus a popular application to develop software among a
non-programmer community. On the other hand, these same characteristics make
\matlab a difficult language to compile statically. Even the de facto standard,
Mathworks' implementation of \matlab is essentially an interpreter with a
\emph{JIT accelarator}\cite{matlabjit} which is generally slower than statically
compiled languages. GNU Octave, which is a popular open source alternative to
\matlab and is mostly compatible with \matlab, introduced JIT compilation only
in its most recent release 3.8 in March 2014. Before that it was implemented
only as an interpreter\cite{Octave}.  Lack of formal language specification,
unconventional semantics and closed source make it even harder to write a
compiler for \matlab.  These are some of the challenges that \mixten shares with
other static compilers which convert \matlab to C or Fortran. However, targeting
\xten raises some significant new challenges.   For example, \xten is an
object-oriented,  heap-based, language with varying levels of high-level
abstractions for arrays and iterators of arrays.     An open question was
whether or not it was possible to generate \xten code that both maintains the
\matlab semantics,  but also leads to code that is as efficient as
state-of-the-art translators that target C and Fortran.  Finding an effective
and efficient translation from \matlab to \xten was not obvious, and this thesis
reports on the key problems we encountered and the solutions that we designed
and implemented in our \mixten system.  By demonstrating that we can generate
sequential \xten code that is as efficient as generated C or Fortran code,  we
then enabled the possibility of leveraging the high performance nature of
\xten's parallel constructs.   To demonstrate this, we exposed scalable
concurrency in \matlab via \xten and examined how to use \xten features to
provide a good implementation for \matlab's \parfor construct.
%Furthermore, the use of arrays as default data type and the dynamicity of the
%base types and shapes of arrays also make it harder to add support for
%concurrency in a static \matlab compiler.  Mathworks' proprietary solution for
%concurrency is the \emph{Parallel Computing Toolbox}\cite{pct}, which allows
%users to use multicore processors, GPUs and clusters. However, this toolbox uses
%heavyweight worker threads and has limited scalability.

Built on top of \mclab static analysis framework\cite{JesseThesis, TamerPaper},
\mixten, together with its set of reusable static analyses for performance
optimization and extended support for \matlab features, ultimately aims to
provide \matlab's ease of use, sequential performance comparable to that
provided by state-of-the art compilers targetting C and Fortran, to support
parallel constructs like \texttt{parfor} and to expose scalable concurrency.  

%With \mixten, our aim is to provide \matlab's ease of use, to benefit from the
%advantages of static compilation, and to expose scalable concurrency. We have
%concentrated both on providing an efficient translation for the
%sequential core of \xten, as well as providing an effective bridge to
%the concurrency features of \xten. We have also extended the \mclab analysis
%framework\cite{JesseThesis, TamerPaper} by adding a set of reusable static
%analyses for performance optimization and extended support for \matlab features.

\section{Contributions}

The major contributions  of this thesis are as follows:

\begin{description}

\item[Identifying key challenges:] We have identified the key challenges
in performing a semantics-preserving efficient translation of \matlab to \xten.

\item[Overall design of \mixten:] Building upon the \mclab frontend and analysis
framework, we provide the design of the \mixten
source-to-source translator that includes a low-level \xten IR and a
template-based specialization framework for handling builtin operations.

\item[Techniques for efficient compilation of \matlab arrays:] Arrays are
the core of \matlab. All data, including scalar values are represented
as arrays in \matlab. Efficient compilation of arrays is the key for
good performance. \xten provides two
types of array representations for multidimensional arrays: (1)
Cilk-styled, region-based arrays and (2) rail-backed \emph{simple} arrays. 
We compare
and contrast these two array forms for a high performance computing
language in context of being used as a target language and provide techniques
to compile \matlab arrays to two different representations of arrays provided
by \xten.

\item[Builtin handling framework:] We have designed and implemented a
template-based system that allows us to generate specialized \xten code for a
collection of important \matlab builtin operations.

\item[Code generation strategies for the sequential core:]  There
are some very significant differences between the semantics of \matlab
and \xten.  A key difference is that \matlab is dynamically-typed,
whereas \xten is statically-typed.   Furthermore, the type rules are
quite different, which means that the generated \xten code must include
the appropriate explicit type conversion rules, so as to match the
\matlab semantics.   Other \matlab features, such as multiple returns
from functions, a non-standard semantics for \texttt{for} loops, and a
very general range operator, must also be handled correctly.

\item[Code generation for concurrency in \matlab:] \mixten not only supports all
the key sequential constructs but also supports concurrency constructs like
\parfor and can handle vectorized instructions in a concurrent fashion. We have
also introduced \xten-like concurrency constructs in \matlab via structured
comments.

\item[Safe use of integer variables:]  Even after determining the
correct use of \xten arrays,  we were still faced with a performance gap
between the code generated by the C/Fortran systems,
and the generated \xten code generated by \mixten.
Furthermore,  we found that the \mixten system using the
\xten Java backend was often generating
better code than with the \xten C++ backend,  which was counter-intuitive.

We determined that a key remaining problem was overhead due to casting
doubles to integers.  This casting overhead was quite high, and was
substantially higher for the C++ back-end than for the Java back-end
(since the casting instructions are handled efficiently by the Java VM).
This casting problem arises because the default data type for \matlab
variables is double - even variables used to iterate through arrays, and
to  index into arrays typically have double type, even though they hold
integral values.  To tackle this issue we developed an
\emph{IntegerOkay} analysis which determines which double variables can
be safely converted to integer variables in the generated \xten code,
hence greatly reducing the number of casting operations needed.
  
\item[Open implementation:] We have implemented the
\mixten compiler over various \matlab compiler tools provided by the \mclab
toolkit.  In the process we also implemented some enhancements to these existing
tools. Our implementation is extensible and allows for others to make further
improvements to the generated \xten code, or to reuse the analyses to generate
code for other target languages.  

\item[Experimental evaluation:]
We have experimented with our \mixten implementation on a set of
benchmarks.  Our results show that our generated code is almost an order
of magnitude faster than the Mathworks' standard JIT-based system,  and is
competitive with other state-of-the-art tools that generate C/Fortran.
Our more detailed results show the importance of using our
customized and optimized \xten array representations, and we
demonstrate the effectiveness of the \emph{IntegerOkay} analysis.
Finally, we show that our \xten-based treatment of \parfor
significantly outperforms \matlab on our benchmarks.

\end{description}

\section{Thesis Outline}

This thesis is divided into \ref{chap:Conclusions} chapters, including this one
and is structured as follows.

\chapref{chap:Xten} provides an introduction to the \xten language and describes
how it compares to \matlab from the point of view of language design.
\chapref{chap:Design} gives a description of various existing \matlab compiler
tools upon which \mixten is implemented, presents a high-level design of
\mixten, and explains the design and need of \mixten IR.  In
\chapref{chap:Arrays}  we compare the two kinds of arrays provided by \xten,
identify when each of them must be used in the generated code, identify and
address challenges involved in efficient compilation of \matlab arrays.
\chapref{chap:Builtins} describes the builtin handling framework used by
\mixten to generate specialized code for \matlab builtins used in the source
program.  \chapref{chap:CodegenSeq} gives a description of efficient and
effective code generation strategies for the core sequential constructs of
\matlab. A description of code generation for the \matlab \texttt{parfor}
construct is provided in \chapref{chap:CodegenCon}, which also describes our
strategy to introduce concurrency constructs in \matlab.  In
\chapref{chap:Analyses} we provide a description of the \emph{IntegerOkay}
analysis to identify variables that are safe to be declared as \texttt{Long}
type. \chapref{chap:Evaluation}
provides performance results for code generated using \mixten for a suite of
benchmarks. It gives a comparison between performance achieved by \mixten
generated code and that generated by the \matlab coder and \mctwofor compilers.
\chapref{chap:Related} provides an overview of related work and
\chapref{chap:Conclusions} concludes and outlines possible future work.
