\matlab programmers often recognize the parallel nature of computations involved
in their programs but cannot express it due to the lack of fine-grained
concurrency controls in \matlab. Some concurrency can be achieved using controls
like \verb|parfor| and other tools in Mathwork's parallel computing toolbox, but
this has several drawbacks:  (1) the parallel toolbox is limited in terms of
scaling (\matlab currently supports only up to 12 workers \emph{processes} to
execute applications on a multicore processor~\cite{pct}); (2) the parallel
toolbox must be purchased separately, so not even all licensed \matlab users
will have it available; and (3) \matlab's concurrency is often slower compared
to \xten's concurrency controls (as shown in section~\ref{sec:parfor_results}).
Vectorization
\footnote{\url{http://www.mathworks.com/help/matlab/matlab_prog/vectorization.html}}
is a technique to convert loop-based scalar operations to vector operations, for
which \matlab is optimized.   So, another way of exposing parallelism in \matlab
is to optimize these instructions to perform the computations concurrently on
the elements of the vector.

\secref{sec:XX} gives an introduction to the concurrency controls in \xten.
Readers not familiar with \xten may find it useful to read it before continuing
with this chapter.



\section{Code Generation for the \matlab \texttt{parfor} Loop Construct}

The \matlab \texttt{parfor} construct is an important feature in \matlab and is
provided by the Mathworks' parallel computing toolbox~\cite{pct}. It allows the
for loop iterations in the \matlab programs to be executed in parallel, whenever
safely possible, thus greatly enhancing the performance of the for loop
execution. Other static \matlab compilers like \matlab coder and \mctwofor do
not support the \texttt{parfor} loop due to the lack of builtin concurrency
features in their target languages, C and Fortran. However, \xten, being a
parallel programming language, naturally provides concurrency control features.
The \mixten compiler supports parallel code generation for the \matlab
\texttt{parfor} construct and provides significantly better performance compared
to \matlab code with \texttt{parfor}, and also the sequential version of the
\xten code generated for the same program.   

The  \verb|parfor| (or parallel
for loop) is a key parallelization control provided by the
\matlab parallel computing toolbox that can be used to execute each
iteration of the for loop in parallel with each other. The challenge was
to implement it with \xten's concurrency controls while maintaining its
complex semantics and aiming for better performance than provided by the
parallel computing toolbox. 
There are three important semantic characteristics of \matlab's
\verb|parfor| loop: 
\begin{enumerate}
\item the scope of variables inside a \verb|parfor|
loop, including the loop index variable, is limited to each iteration.

\item if a variable defined outside the loop is modified inside the loop
such that its value after the loop is dependent on the sequence of
execution of iterations, then its value after the loop is set to its
value before the loop. 

\item if a variable defined outside the loop is
modified in a reduction assignment i.e., the final value after the
iterations is independent of the order of execution of iterations, the
updated value is retained after the \verb|parfor| loop. Consider the
\matlab code given on the left of \figref{fig:parforex}.

\begin{figure}[htbp]
\begin{minipage}{0.3\linewidth}
\begin{lstlisting}[language=Matlab,numbers=none]                                
function [] = saneParfor(v)
d = v; 
x=0;
A=zeros(1,10);
parfor i = 1:10
   x = x+i;
   d = i*2;
   A(i) = d;
end
disp(d);
end
\end{lstlisting}  
\end{minipage}\hfill
\begin{minipage}{0.6\linewidth}
\begin{lstlisting}[language=X10,numbers=none]                                   
static def saneParfor (v: Double){ 
  //This example does not 
  //use IntegerOkay analysis
  var d: Double = v;
  var x: Double = 0;
  val A: Array_1[Double] = 
     new Array_1[Double](Mix10.zeros(1, 10));
  var mc_t3: Double = 1;
  var mc_t4: Double = 10;
  finish {
    for (i in (mc_t3 as Long)..(mc_t4 as Long))
     async {
       atomic x = Mix10.plus(x, i as Double);
       var mc_t2: Double = 2;
       var d_local: Double = 
          Mix10.mtimes(i as Double, mc_t2);
       A(i as Long -1) = d_local ;
    }
  }
}
\end{lstlisting}              
\end{minipage}

\caption{Example of \texttt{parfor}, \matlab with
\texttt{parfor} on the left, generated \xten on the right.}\label{fig:parforex}
\end{figure}

Here \verb|x = x+i;| is a reduction assignment~\cite{reducassg}
statement. The value of \verb|d| is local to each iteration and the
initial value before the loop is retained after the loop. Note that the
value of \verb|d| outside the loop is invisible inside the loop. For
statement \verb|A(i) = d;|, each iteration modifies a unique element
accessible only to it, hence the final value of \verb|A| is independent
of order of execution; thus its value is updated after the loop.  
\end{enumerate}


The \mixten compiler uses the
following strategy to translate \texttt{parfor} loops to \xten:
\begin{enumerate}

\item Introduce \verb|finish| and \verb|async| constructs to control the flow
of statements in parallel. This puts the statement immediately after the
\texttt{for} loop in wait, until all the iterations have been executed.

\item Any variable defined inside the loop and not declared outside the
loop previously is declared inside the \verb|async| scope to
make it local to the iteration.

\item Any variable defined inside the loop that is previously defined
outside the loop and is not a reduction variable is replaced by
a local temporary variable defined inside the loop.

\item Statements identified to be reduction statements are made atomic
by using the \verb|atomic| construct in \xten.

\end{enumerate}

An equivalent \xten code for the above example \matlab code is
given on the right side of \figref{fig:parforex}. The use of \verb|finish| and
\verb|async| ensure that each iteration is executed in parallel and the
statement after the \verb|for| loop is blocked until all the iterations have
finished executing. Note that the \verb|for| loop is iterated over a
\verb|LongRange| to ensure that the declaration of the loop variable \verb|i| is
local to each iteration. The statement \texttt{x = x+i} is a reduction
statement, since its order of execution does not affect the value of x at the
end of the loop. It is declared to be \verb|atomic| to ensure that the two
operations of addition and assignment in the statement are executed as a whole,
without any interference from its execution in other iterations. Since the
variable \verb|d| is also defined outside the loop, it is replaced by a local
variable \verb|d_local| inside the loop. Finally, since each array variable
\verb|A(i)| is unique, it is executed normally for each iteration.

To conclude, we can translate the \verb|parfor| in \matlab to
semantically equivalent code in \xten and since \xten can handle massive
scaling, we can get significantly better performance for \xten compared
to \matlab as shown by our experimental results in Section
\ref{sec:parfor_results}.

\section{Introducing Concurrency Controls in \matlab}

In order to enable \matlab to be compiled for high performance computing
it is important to let programmers exploit fine-grained concurrency in
their \matlab programs. Due to the lack of fine-grained concurrency
controls in traditional \matlab, we decided to introduce such controls
in \matlab that can be translated by our \mixten compiler to analogous
concurrency controls in \xten. However it was important that
introduction of such controls should not have any side-effects when
compiled by traditional Mathworks' \matlab compiler, so we introduced
them as structured special comments. 

We introduced the following concurrency constructs in \matlab: (1)
\verb|%!async|, (2) \verb|%!finish|, (3) \verb|%!atomic|, (4)
\verb|%!when(condition)| (5) (where \verb|condition| is a boolean expression)
and (6) \verb|%!at(p)| (where \verb|p| is an integer value denoting a place in
\xten).  Programmers can express these constructs before the statements that
they want to control and specify the end of a control by using \verb|%!end|
after the statements. Note that because of the preceding \verb|%| sign these
constructs will be treated like comments by other \matlab compilers and will not
cause any unwanted effects.  It is important to note that the \matlab
programmer, using these constructs in her program, must ensure that the parallel
execution caused by the use of these constructs does not change the behavior of
the program from that of the sequential execution of the program. In short, it
is the responsibility of the programmer to ensure the safety
of the program when using these constructs. 

Figure \ref{fig:concex} 
shows an example of how to use these controls in
\matlab followed by the generated \xten code for it.   

\begin{figure}[htbp]
\begin{minipage}{0.3\linewidth}

\begin{lstlisting}[language=Matlab,numbers=none]       
function [x] = parallelFoo(a)    
  %!finish
  for (i = 1:length(a))
    %!async
    a(i)=a(i)*2;
    %!end	
  end
  %!end
end                                                                             
\end{lstlisting}

\end{minipage}\hfill
\begin{minipage}{0.6\linewidth}
\begin{lstlisting}[language=X10,numbers=none]                                   
static def parallelfoo (a: Array_1[Double]){
  //This example does not 
  //use the IntegerOkay analysis
  var mc_t2: Double = Mix10.length(a);
  var mc_t4: Double = 1;
  finish {
    for (i in (mc_t4 as Long)..(mc_t2 as Long)){
      async{
        var mc_t0: Double;
        mc_t0 = mtimes(a(i - 1), 2) ;
        a(i - 1) = mc_t0 ;
      }
    }
  }
  val x: Array_1[Double] = new Array_1[Double](a);
  return x;
}
\end{lstlisting}
\end{minipage}

\caption{Example of introduced concurrency controls, \matlab with
introduced concurrency on the left, generated \xten on the right.}\label{fig:concex}
\end{figure}

\section{Parallelizing Vectorized Instructions}\label{sec:parvec} 
The use of vectorized instructions is another optimization technique
used by \matlab to speedup single operations on multiple scalar values by
combining scalar values in a vector and executing the operation on the
vector.  Such \emph{Single instruction, multiple data} style operations
are good candidates for parallelization. However, efficiency of
parallelization of such operations depends on the size of the vector,
the complexity of the operation involved, and the executing hardware. Thus,
in order to make it most effective, we wanted to provide full support
for parallelization of vector instructions and give the programmer the
ability to control when the vector operation is executed concurrently,
based on the size of the vector. 

%Our solution to the problem is to introduce a parallelization specialization in
%the \mixten's builtin handling framework. 
We implemented a concurrent version of the relevant builtin operations that can
operate in a parallel fashion on vectors of arbitrary sizes.\footnote{Currently,
these concurrent builtin implementations are not integrated into the builtin
handling framework. However, due to the extensible nature of the builtin
handling framework, it should be straightforward to add a specialization for
a concurrent version of the builtins. We plan to do it as a future work.} We also
introduced a compiler switch for \mixten that lets programmers specify a
vector length threshold for all builtins or a specific builtin above
which the concurrent version of the builtin will be executed. For
example, if the user wants an operation \verb|sin(A)| to be executed
concurrently only if \verb|A| is a vector of length greater than, say,
1000; then while invoking the \mixten compiler she can specify the
threshold by using the switch \verb|-vec_par_length sin=1000|. \mixten
will generate a call to the concurrent version of \verb|sin()| if the
length of \verb|A| is greater than \verb|1000| else it will call the
sequential version. Using the \verb|-vec_par_length| switch programmer
can specify threshold for one or more or all builtin methods. For
example \verb|-vec_par_length all=500 sin=1000 cos=1000| will set the
threshold for \verb|sin()| and \verb|cos()| to \verb|1000| and to
\verb|500| for all other builtins. 

As a future work, we plan to extensively evaluate the concurrent execution for
the vectorized instructions. It would be interesting to study the performance 
variations of concurrently executing vector instructions, with varying
threshold vector length values and on different parallel architectures.   



