\begin{comment}
-Key factors for efficient compilation of arrays
-how do we handle them
\end{comment}

Arrays are the core of the \matlab programming language. Every value in
\matlab is a \emph{Matrix} and has an associated array shape. Even
scalar values are represented as $1\times1$ arrays.  Most of the data
read and write operations involve accessing individual or a set of array
elements.  Given the central role of arrays in \matlab, it is of utmost
importance for our \mixten compiler to find effective and efficient
translations to \xten arrays. 

Given the shape information provided by the shape analysis engine~\cite{mc2for}
built into the \mclab analysis
framework~\cite{McSAFecoop12,JesseThesis,TamerPaper}, it was not hard to compile
\matlab arrays to \xten. However, to generate \xten code whose performance would
be competitive to the generated C code (via \matlab coder) and the generated
Fortran code (via the \mctwofor compiler), was not straightforward, and required
deeper understanding of the \xten array system and
careful handling of several features of the \matlab arrays.

\section{Simple Arrays or Region Arrays}\label{Sec:CompileArrays}

As described in Section \ref{subsec:ArrayDesc}, \xten provides two higher level
abstractions for arrays, simple arrays, a high performance but rigid
abstraction, and region arrays, a flexible abstraction but not as efficient as
the simple arrays. In order to achieve more efficiency, our strategy is to use
the simple arrays whenever possible, and to fall back to the region arrays when
necessary. Note that it is possible to force the \mixten compiler to use region
arrays via a switch, for experimentation purposes.

\subsection{Compilation to Simple Arrays}\label{sec:compsimple}
In dealing with the simple
rail-backed arrays, there were two important challenges.  First, we needed to
determine when it is safe to use the simple rail-backed arrays,  and second, we
needed  an implementation of simple rail-backed arrays that handles the
column-major, 1-indexing, and linearization operations required by \matlab.
     
\paragraph{When to use simple rail-backed arrays:} After the shape analysis of
the source \matlab program, if shapes of all the arrays in the program: (1) are
known statically, (2) are supported by the \xten implementation of simple arrays
and (3) the dimensionality of the shapes remain same at all points in the
program; then \mixten generates \xten code that uses simple arrays. 

\paragraph{Column-major indexing:} In order
to make \xten simple arrays more compatible with \matlab, we modified the
implementation of the \verb|Array_2| and \verb|Array_3| classes in
\verb|x10.array| package to use column-major ordering instead of the default
row-major ordering when linearizing multidimensional arrays to the backing
\verb|Rail| storage.\footnote{
\url{http://www.sable.mcgill.ca/mclab/mix10/x10_update/}} Since \matlab uses
column-major ordering to linearize arrays, this modification also makes it
trivial to support linear indexing operations in \matlab.  \footnote{
\url{http://www.mathworks.com/help/matlab/math/matrix-indexing.html}}
\matlab naturally supports linear indexing for individual element
access. More precisely, if the number of subscripts in an array access
is less than the number of dimensions of the array, the last subscript
is linearly indexed over the remaining number of dimensions in a
column-major fashion. Our modification to use column-major ordering for
the backing \verb|Rail| make it easier and more efficient to support
linear indexing by allowing direct access to the underlying \verb|Rail|
at the calculated linear offset.

Given that we can determine when it is safe to use the simple rail-backed
arrays,  and our improved \xten implementation of them,  we then designed the
appropriate translations from \matlab to \xten, for array construction, array
accesses for both individual elements and ranges. Given the number of dimensions
and the size of each dimension, it is easy to construct a simple array. For
example a two-dimensional array \verb|A| of type \verb|T| and shape $m\times n$
can be constructed using a statement like \texttt{val A:Array\_2[T] = new
Array\_2[T](m,n);}. Additional arguments can be passed to the constructor to
initialize the array. Another important thing to note is that \matlab allows the
use of keyword \verb|end| or an expression involving \verb|end| (like
\verb|end-1|) as a subscript. \verb|end|  denotes the highest index in that
dimension. If the highest index is not known the \verb|numElems_i| property of
the simple arrays is used to get the number of elements in the \verb|i|th
dimension of the array.  


\subsection{Compilation to Region Arrays}

With \matlab's dynamic nature and unconventional semantics, it is not
always possible to statically determine the shape of an arrays 
accurately.  Luckily, with some thought to a proper translation, \xten's
region arrays are flexible enough to support \matlab's ``wild" arrays.
Also, since \verb|Point| objects can be a set of arbitrary integers,
there is no restriction on the starting index of the arrays. Region
arrays can easily use one-based indexing. 

\paragraph{Array construction:}
Array construction for region arrays involves creating a region over a set of
points (or index objects) and assigning it to an array. Regions of arbitrary
ranks can be created dynamically.  
For example, consider the following \matlab code snippet:

\begin{minipage}{0.4\linewidth}
\begin{lstlisting}[language=Matlab,numbers=none]                                
function[x] = foo(a)                                                        
    t = bar(a);  
    x = t;
    ...	                                                                    
end      
\end{lstlisting}  
\end{minipage}
\hfill
\hspace{.5cm}
\hfill
\begin{minipage}{0.5\linewidth}
\begin{lstlisting}[language=Matlab,numbers=none]                                
function[y] = bar(a)
    if (a == 3)
        y = zeros(a,a+1,a+2,a+3);
    else
        y = zeros(a,a+1,a+2);
    end
end		                                                           
\end{lstlisting}  
\end{minipage}

\noindent
In this code, the number of dimensions of array \verb|t| and hence array
\verb|x| cannot be determined statically at compile-time. In such case, it is 
not possible to generate \xten code that uses simple arrays, however, it can 
still be compiled to the following \xten code for function \verb|foo()|.

\begin{minipage}{0.4\linewidth}
\begin{lstlisting}[language=X10,numbers=none]                                   
static def foo(a: Double){
  val t: Array[Double] = 
    new Array[Double](bar(a));
  val x: Array[Double] = 
    new Array[Double](t);
  ...
  return x;
}                         
\end{lstlisting}              
\end{minipage}
\hfill
\hspace{.3cm}
\hfill
\begin{minipage}{0.5\linewidth}
\begin{lstlisting}[language=X10,numbers=none]                                   
static def bar(a:Double){
  var y:Array[Double]=null;
  if (a == 3) {
    y = new Array[Double]
      (Mix10.zeros(a,a+1,a+2,a+3));
  }
  else {
    y = new Array[Double]
      (Mix10.zeros(a,a+1,a+2));
  }
  return y;
}		                        
\end{lstlisting}              
\end{minipage}

\noindent
In this generated \xten code, \verb|t| is an array of type \verb|Double|
which can be created by copying from another array returned by
\verb|bar(a)| without knowing the shape of the returned array. 

\paragraph{Array access:}
Subscripting operations to access individual elements are mapped to
\xten's region array subscripting operation. If the rank of array is 4
or less, it is subscripted directly by integers corresponding to
subscripts in \matlab otherwise we create a \verb|Point| object from
these integer values and use it to subscript the array. In case an
expression involving \verb|end| is used for indexing and the complete
shape information is not available, method \verb|max(Long i)|, provided
by the \verb|Region| class is used, allowing to determine the highest
index for a particular dimension at runtime.

\paragraph{Rank specialization:} Although region arrays can be used with
minimal compile-time information, providing additional static
information can improve performance of the resultant code by eliminating
run-time checks involving provided information. One of the key
specializations that we introduced with use of region arrays is to
specify the rank of an array in its declaration, whenever it is known
statically. For example if rank of an array \verb|A| of type \verb|T| is
known to be two, it can be declared as \verb|val A:Array[T](2);|.  This
specialization provided better performance compared to
unspecialized code as shown in section~\ref{sec:EvalArrays}.


\section{Handling the Colon Expression}

\matlab allows the use of an expression such as \verb|a:b| (or
\texttt{colon(a,b)}) to create a vector of integers 
\verb|[a, a+1,| \verb| a+2, ... b]|. In another form, an expression like 
\verb|a:i:b| can be used to
specify an integer interval of size \verb|i| between the elements of the
resulting vector. Use of a \verb|colon| expression for
array subscripting takes all the elements of the array for
which the subscript in a particular dimension is in the vector
created by the \verb|colon| expression in that
dimension.\footnote{Use of ':' in place of an index without lower and
upper bounds indicates the use of all the indices in that dimension.}
Consider the following \matlab code:

\begin{lstlisting}[language=Matlab,numbers=none]                                
function [x] = crazyArray(a)                                                    
    y = ones(3,4,5);                                                            
    x = y(1,2:3,:);                                                             
end                                                                             
\end{lstlisting}

\noindent
Here \verb|y| is a three-dimensional array of shape $3\times4\times5$ and
\verb|x| is a sub-array of \verb|y| of shape $1\times2\times5$. 
Such array accesses can be handled by simply calling the \verb|getSubArray[T]()|
that we have implemented in a Helper class provided with the generated code. 
The generated \xten code with simple array for this example is as follows:

\begin{lstlisting}[language=x10,numbers=none]                                
static def crazyArray (a: Double){
    val y: Array_3[Double] = new Array_3[Double](Mix10.ones(3, 4, 5));
    val mc_t0: Array_1[Double] = new Array_1[Double](Mix10.colon(2, 3));
    var x: Array_3[Double];
    x = new Array_3[Double](Helper.getSubArray(1, 1, mc_t0(0), mc_t0(1), 1, 5, y)) ;
    return x;
}
\end{lstlisting}

The colon operator can also be used on the left hand side for an array set
operation that updates multiple values of the array. For example, in the
\matlab statement \texttt{x(:,4) = y;}, all the values of the fourth column of
\verb|x| will be set to \verb|y| if \verb|y| is a scalar or to corresponding
values of \verb|y| if \verb|y| is a column vector with length equal to the size
of first dimension of \verb|x|. To handle this kind of operation we have
implemented another helper method, \texttt{setSubArray()}. This method takes as
input, the target array, the bounds on each dimension, and the source array.
\texttt{x(:,4) = y;} will be translated by \mixten to \texttt{x =
Helper.setSubArray(x, 1, x.numElems\_1, 4, 4, y);}

We have implemented overloaded versions of the \texttt{getSubArray()} and the
\texttt{setSubArray()} methods for arrays of different dimensions. For region
arrays, we provide the same methods that operate on region arrays in a different
version of the Helper class.  \mixten provides the correct version of the Helper
class, based on what kind of arrays are used.


\section{Array Growth} 

\matlab allows explicit array growth during runtime via the \texttt{horzcat()}
and the \texttt{vertcat()} builtin functions for array concatenation operations. 
In \mixten this feature is
supported for simple arrays as long as the array growth does not change the
number of dimensions of the array. For region arrays, this feature is supported
in full. For simple arrays, \xten allows a variable declared to be an array of
rank i, to hold any array value of the same rank. For example, consider the
following set of statements:
\begin{lstlisting}[language=x10,numbers=none]                                
//...
var x:Array_2[Long];
x = new Array_2(3,4,0);
y = new Array_2(3,5,0);
x=y;
//...
\end{lstlisting}
Here, \verb|x| is defined to be of type \texttt{Array\_2[Long]} and can hold
arrays of different sizes at different points in the program.

Region arrays, being more dynamic, also support array growth even if it changes
the rank of the array. For example, the following set of statements are valid in
an \xten program that uses region arrays:
\begin{lstlisting}[language=x10,numbers=none]                                
//...
var x:Array[Long];
x = new Array(Region.make(1..3,1..4),0);
y = new Array(Region.make(1..3,1..5,1..6),1);
x=y;
//...
\end{lstlisting}
Here \verb|x| is a 2-dimensional array and \verb|y| is a 3-dimensional array. 

\par
Section \ref{sec:EvalArrays} discusses the performance results obtained by
using
different kinds of arrays and provides a comparison of them, thus showing the
efficiency of our approach for compiling \matlab arrays to \xten.
