Enable support for building mpi-win-x86_64-gcc

[charm.git] / doc / charm++ / arrays.tex

%\subsection{Chare Arrays}
\label{basic arrays}

Chare arrays\index{chare array}\index{chare arrays}\index{arrays} are
arbitrarily-sized, possibly-sparse collections of chares that are distributed
across the processors. The entire array has a globally unique identifier of
type \kw{CkArrayID}, and each element has a unique index of type
\kw{CkArrayIndex}. A \kw{CkArrayIndex} can be a single integer (i.e. a one-dimensional array),
several integers (i.e. a multi-dimensional array), or an arbitrary string of
bytes (e.g. a binary tree index).

Array elements can be dynamically created and destroyed on any PE,
migrated between PEs, and messages for the elements will still arrive
properly. Array elements can be migrated at any time, allowing arrays to be
efficiently load balanced. A chare array (or a subset of array elements) can
receive a broadcast/multicast or contribute to a reduction.

An example program can be found here: \examplerefdir{array}.

\section{Declaring a One-dimensional Array}

You can declare a one-dimensional (1D) \index{array}\index{chare array}chare
array as:
%
\begin{alltt}
//In the .ci file:
array [1D] A \{
  entry A(\uw{parameters1});
  entry void someEntry(\uw{parameters2});
\};
\end{alltt}
%
Array elements extend the system class \kw{CBase}\_\uw{ClassName}, inheriting
several fields:
%
\begin{itemize}
\item \kw{thisProxy}: the proxy to the entire chare array that can be indexed
  to obtain a proxy to a specific array element (e.g. for a 1D chare array
  \kw{thisProxy[10]}; for a 2D chare array \kw{thisProxy(10, 20)})
\item \kw{thisArrayID}: the array's globally unique identifier
\item \kw{thisIndex}: the element's array index (an array element can obtain a
  proxy to itself like this \kw{thisProxy[thisIndex]})
\end{itemize}
%
\zap{As well as chares are allowed to inherit directly from class \kw{Chare},
  array elements are allowed to inherit from \kw{ArrayElement1D} if 1D array,
  \kw{ArrayElement2D} if 2D array, and so on up to 6D.}
%
\begin{alltt}
class A : public CBase\_A \{
  public:
    A(\uw{parameters1});

    void someEntry(\uw{parameters2});
\};
\end{alltt}
%
Note that \uw{A} must have a \emph{migration constructor}, which is typically
empty:
%
\begin{alltt}
//In the .C file:
A::A(void)
\{
  //... constructor code ...
\}

A::someEntry(\uw{parameters2})
\{
  // ... code for someEntry ...
\}
\end{alltt}
%
See the section~\ref{arraymigratable} on migratable array elements for more
information on the migration constructor that takes \kw{CkMigrateMessage *} as
the argument.

\section{Declaring Multi-dimensional Arrays}

\charmpp{} supports multi-dimensional or user-defined indices. These array types
can be declared as:
%
\begin{alltt}
//In the .ci file:
array [1D]  ArrayA \{ entry ArrayA(); entry void e(\uw{parameters});\}
array [2D]  ArrayB \{ entry ArrayB(); entry void e(\uw{parameters});\}
array [3D]  ArrayC \{ entry ArrayC(); entry void e(\uw{parameters});\}
array [4D]  ArrayD \{ entry ArrayD(); entry void e(\uw{parameters});\}
array [5D]  ArrayE \{ entry ArrayE(); entry void e(\uw{parameters});\}
array [6D]  ArrayF \{ entry ArrayF(); entry void e(\uw{parameters});\}
array [Foo] ArrayG \{ entry ArrayG(); entry void e(\uw{parameters});\}
array [Bar<3>] ArrayH \{ entry ArrayH(); entry void e(\uw{parameters});\}
\end{alltt}
%
The declaration of ArrayG expects an array index of type \kw{CkArrayIndex}\uw{Foo},
which must be defined before including the \texttt{.decl.h} file (see
section~\ref{user-defined array index type} on user-defined array indices for
more information).
%
\begin{alltt}
//In the .h file:
class ArrayA : public CBase\_ArrayA \{ public: ArrayA()\{\} ...\};
class ArrayB : public CBase\_ArrayB \{ public: ArrayB()\{\} ...\};
class ArrayC : public CBase\_ArrayC \{ public: ArrayC()\{\} ...\};
class ArrayD : public CBase\_ArrayD \{ public: ArrayD()\{\} ...\};
class ArrayE : public CBase\_ArrayE \{ public: ArrayE()\{\} ...\};
class ArrayF : public CBase\_ArrayF \{ public: ArrayF()\{\} ...\};
class ArrayG : public CBase\_ArrayG \{ public: ArrayG()\{\} ...\};
class ArrayH : public CBase\_ArrayH \{ public: ArrayH()\{\} ...\};
\end{alltt}
%
The fields in \kw{thisIndex} are different depending on the dimensionality of
the chare array:
%
\begin{itemize}
\item 1D array: \kw{thisIndex}
\item 2D array ($x$,$y$): \kw{thisIndex.x}, \kw{thisIndex.y}
\item 3D array ($x$,$y$,$z$): \kw{thisIndex.x}, \kw{thisIndex.y},
  \kw{thisIndex.z}
\item 4D array ($w$,$x$,$y$,$z$): \kw{thisIndex.w}, \kw{thisIndex.x},
  \kw{thisIndex.y}, \kw{thisIndex.z}
\item 5D array ($v$,$w$,$x$,$y$,$z$): \kw{thisIndex.v}, \kw{thisIndex.w},
  \kw{thisIndex.x}, \kw{thisIndex.y}, \kw{thisIndex.z}
\item 6D array ($x_1$,$y_1$,$z_1$,$x_2$,$y_2$,$z_2$): \kw{thisIndex.x1},
  \kw{thisIndex.y1}, \kw{thisIndex.z1}, \kw{thisIndex.x2}, \kw{thisIndex.y2},
  \kw{thisIndex.z2}
\item Foo array: \kw{thisIndex}
\item Bar<3> array: \kw{thisIndex}
\end{itemize}

\section{Creating an Array}
\label{basic array creation}

An array is created using the \kw{CProxy\_Array::ckNew} routine, which must
be called from PE 0. To create an array from any PE, asynchronous array creation
using a callback can be used. See section~\ref{asynchronous_array_creation} for
asynchronous array creation. \kw{CProxy\_Array::ckNew} returns a proxy object,
which can be kept, copied, or sent in messages. The following creates a
1D \index{array}array containing elements indexed (0, 1, \ldots, \uw{dimX}-1):
%
\begin{alltt}
CProxy_ArrayA a1 = CProxy_ArrayA::ckNew(\uw{params}, dimX);
\end{alltt}
%
Likewise, a dense multidimensional array can be created by passing the extents
at creation time to \kw{ckNew}.
%
\begin{alltt}
CProxy_ArrayB a2 = CProxy_ArrayB::ckNew(\uw{params}, dimX, dimY);
CProxy_ArrayC a3 = CProxy_ArrayC::ckNew(\uw{params}, dimX, dimY, dimZ);
CProxy_ArrayD a4 = CProxy_ArrayC::ckNew(\uw{params}, dimW, dimX, dimY, dimZ);
CProxy_ArrayE a5 = CProxy_ArrayC::ckNew(\uw{params}, dimV, dimW, dimX, dimY, dimZ);
CProxy_ArrayF a6 = CProxy_ArrayC::ckNew(\uw{params}, dimX1, dimY1, dimZ1, dimX2, dimY2, dimZ2);
\end{alltt}
%
For user-defined arrays, this functionality cannot be used.  The
array elements must be inserted individually as described in
section~\ref{dynamic_insertion}.

During creation, the constructor is invoked on each array element. For more
options when creating the array, see section~\ref{advanced array create}.

\section{Entry Method Invocation}

To obtain a proxy to a specific element in chare array, the chare array proxy
(e.g. \kw{thisProxy}) must be indexed by the appropriate index call depending
on the dimensionality of the array:
%
\begin{itemize}
\item 1D array, to obtain a proxy to element $i$: \kw{thisProxy[$i$]} or
  \kw{thisProxy($i$)}
\item 2D array, to obtain a proxy to element $(i,j)$: \kw{thisProxy($i$,$j$)}
\item 3D array, to obtain a proxy to element $(i,j,k)$: \kw{thisProxy($i$,$j$,$k$)}
\item 4D array, to obtain a proxy to element $(i,j,k,l)$:
  \kw{thisProxy($i$,$j$,$k$,$l$)}
\item 5D array, to obtain a proxy to element $(i,j,k,l,m)$:
  \kw{thisProxy($i$,$j$,$k$,$l$,$m$)}
\item 6D array, to obtain a proxy to element $(i,j,k,l,m,n)$:
  \kw{thisProxy($i$,$j$,$k$,$l$,$m$,$n$)}
\item User-defined array, to obtain a proxy to element $i$: \kw{thisProxy[$i$]}
  or \kw{thisProxy($i$)}
\end{itemize}
%
To send a \index{Array message} message to an array element, index the proxy
and call the method name:
%
\begin{alltt}
a1[i].doSomething(\uw{parameters});
a3(x,y,z).doAnother(\uw{parameters});
aF[CkArrayIndexFoo(...)].doAgain(\uw{parameters});
\end{alltt}

You may invoke methods on array elements that have not yet been created. The
\charmpp{} runtime system will buffer the message until the element is
created. 
%\footnote{However, the element must eventually be created (i.e. within
%a 3-minute buffering period).}
\footnote{However, the element must eventually be created.}

Messages are not guaranteed to be delivered in order. For instance, if a method
is invoked on method \kw{A} and then method \kw{B}; it is possible that \kw{B}
is executed before \kw{A}.
%
\begin{alltt}
a1[i].A();
a1[i].B();
\end{alltt}

Messages sent to migrating elements will be delivered after the migrating
element arrives on the destination PE. It is an error to send a message
to a deleted array element.

\section{Broadcasts on Chare Arrays}

To \index{array broadcast} broadcast a message to all the current elements of
an array, simply omit the index (invoke an entry method on the chare array
proxy):
%
\begin{alltt}
a1.doIt(\uw{parameters}); //<- invokes doIt on each array element
\end{alltt}
%
The broadcast message will be delivered to every existing array element exactly
once. Broadcasts work properly even with ongoing migrations, insertions, and
deletions.

\section{Reductions on Chare Arrays}
\label{reductions}

A \index{array reduction}reduction applies a single operation (e.g. add,
max, min, ...) to data items scattered across many processors and
collects the result in one place.  \charmpp{} supports reductions
over the members of an array or group.

The data to be reduced comes from a call to the member \kw{contribute} 
method:
\begin{alltt}
void contribute(int nBytes, const void *data, CkReduction::reducerType type);
\end{alltt}

This call contributes \kw{nBytes} bytes starting at \kw{data} to the
reduction \kw{type} (see Section~\ref{builtin_reduction}).  Unlike sending a
message, you may use \kw{data} after the call to \kw{contribute}.  All
members of the chare array or group must call \kw{contribute}, 
and all of them must use the same reduction type.  


For example, if we want to sum each array/group member's single integer myInt, 
we would use:

\begin{alltt}
    // Inside any member method
    int myInt=get_myInt();
    contribute(sizeof(int),\&myInt,CkReduction::sum_int);
\end{alltt}

The built-in reduction types (see below) can also handle arrays of
numbers.  For example, if each element of a chare array has a pair of
doubles \uw{forces}[2], the corresponding elements of which are to be added across
all elements, from each element call:

\begin{alltt}
    double forces[2]=get_my_forces();
    contribute(2*sizeof(double),forces,CkReduction::sum_double);
\end{alltt}

Note that since C++ arrays (like \uw{forces}[2]) are already pointers, we 
don't use \&\uw{forces}.

A slightly simpler interface is available for \verb+std::vector<T>+,
since the class determines the size and count of the underlying type:

\begin{alltt}
    CkCallback cb(...);
    vector<double> forces(2);
    get_my_forces(forces);
    contribute(forces, CkReduction::sum_double, cb);
\end{alltt}

Either of these will result in a {\tt double} array of 2 elements, the first of which
contains the sum of all \uw{forces}[0] values, with the second element
holding the sum of all \uw{forces}[1] values of the chare array elements.

Typically the client entry method of a reduction takes a single argument of
type CkReductionMsg (see Section~\ref{reductionClients}). However, by giving an entry method the
\kw{reductiontarget} attribute in the {\tt .ci} file, you can instead use entry methods that take
arguments of the same type as specified by the {\em contribute} call.  
When creating a callback to the
reduction target, the entry method index is generated by 
{\tt CkReductionTarget(ChareClass, method\_name)} 
instead of {\tt CkIndex\_ChareClass::method\_name(...)}.
For example,
the code for a typed reduction that yields an {\tt int}, would look like this:

\begin{alltt}
  // In the .ci file...
  entry [reductiontarget] void done(int result);

  // In some .C file: 
  // Create a callback that invokes the typed reduction client
  // driverProxy is a proxy to the chare object on which 
  // the reduction target method {\em done} is called upon completion 
  // of the reduction
  CkCallback cb(CkReductionTarget(Driver, done), driverProxy);

  // Contribution to the reduction...
  contribute(sizeof(int), &intData, CkReduction::sum_int, cb);

  // Definition of the reduction client...
  void Driver::done(int result) 
  \{
    CkPrintf("Reduction value: \%d", result);
  \}
\end{alltt}

This will also work for arrays of data 
elements({\tt entry [reductiontarget] void done(int n, int result[n])}), 
and for any user-defined type with a PUP method
(see ~\ref{sec:pup}). If you know that the reduction will yield a particular
number of elements, say 3 {\tt int}s, you can also specify a reduction target which
takes 3 {\tt int}s and it will be invoked correctly. 

Reductions do not have to specify commutative-associative operations on data;
they can also be used to signal the fact that all array/group members
have reached a certain synchronization point. In this case, a simpler version
of contribute may be used:

%Sometimes it is not important the data to be reduced, but only the fact that all
%elements have reached a synchronization point. In this case a simpler version of
%contribute can be used:

\begin{alltt}
    contribute();
\end{alltt}

In all cases, the result of the reduction operation is passed to the {\em reduction
client}.  Many different kinds of reduction clients can be used, as
explained in Section~\ref{reductionClients}.

Please refer to \examplerefdir{reductions/typed\_reduction} for a working example of
reductions in Charm++.

Note that the reduction will complete properly even if chare array elements are {\em migrated}
or {\em deleted} during the reduction. Additionally, when you create a new chare array element, 
it is expected to contribute to the next reduction not already in progress on that
processor. 

\subsection{Built-in Reduction Types}
\label{builtin_reduction}

\charmpp{} includes several built-in reduction types, used to combine 
individual contributions.  Any of them may be passed as an argument of type
\kw{CkReduction::reducerType} to \kw{contribute}.

The first four operations ({\tt sum}, {\tt product}, {\tt max}, and {\tt min}) work on {\tt char},
{\tt short}, {\tt int}, {\tt long}, {\tt long long}, {\tt float}, or {\tt double} data as indicated
by the suffix.  The logical reductions ({\tt and}, {\tt or}) only work on bool and integer data.
All the built-in reductions work on either single numbers (pass a pointer) or arrays-- just
pass the correct number of bytes to \kw{contribute}.

\begin{enumerate}

\item \kw{CkReduction::nop} : no operation performed.


\item \kw{CkReduction::sum\_char},
  \kw{sum\_short},
  \kw{sum\_int},
  \kw{sum\_long},
  \kw{sum\_long\_long},
  \kw{sum\_uchar},
  \kw{sum\_ushort},
  \kw{sum\_uint},
  \kw{sum\_ulong},
  \kw{sum\_ulong\_long},
  \kw{sum\_float},
  \kw{sum\_double} :
  the result will be the sum of the given numbers.

\item \kw{CkReduction::product\_char},
  \kw{product\_short},
  \kw{product\_int},
  \kw{product\_long},
  \kw{product\_long\_long},
  \kw{product\_uchar},
  \kw{product\_ushort},
  \kw{product\_uint},
  \kw{product\_ulong},
  \kw{product\_ulong\_long},
  \kw{product\_float},
  \kw{product\_double} : the result will be the product of the given numbers.

\item \kw{CkReduction::max\_char},
  \kw{max\_short},
  \kw{max\_int},
  \kw{max\_long},
  \kw{max\_long\_long},
  \kw{max\_uchar},
  \kw{max\_ushort},
  \kw{max\_uint},
  \kw{max\_ulong},
  \kw{max\_ulong\_long},
  \kw{max\_float},
  \kw{max\_double} :
  the result will be the largest of the given numbers.

\item \kw{CkReduction::min\_char},
  \kw{min\_short},
  \kw{min\_int},
  \kw{min\_long},
  \kw{min\_long\_long},
  \kw{min\_uchar},
  \kw{min\_ushort},
  \kw{min\_uint},
  \kw{min\_ulong},
  \kw{min\_ulong\_long},
  \kw{min\_float},
  \kw{min\_double} :
  the result will be the smallest of the given numbers.

\item \kw{CkReduction::logical\_and\_bool}, \kw{logical\_and\_int} : the result will be the logical AND of the given
values.

\item \kw{CkReduction::logical\_or\_bool}, \kw{logical\_or\_int} : the result will be the logical OR of the given
values.

\item \kw{CkReduction::logical\_xor\_bool}, \kw{logical\_xor\_int} : the result will be the logical XOR of the given
values.

\item \kw{CkReduction::bitvec\_and\_bool}, \kw{bitvec\_and\_int} : the result will be the bitvector AND of the given
values.

\item \kw{CkReduction::bitvec\_or\_bool}, \kw{bitvec\_or\_int} : the result will be the bitvector OR of the given
values.

\item \kw{CkReduction::bitvec\_xor\_bool}, \kw{bitvec\_xor\_int} : the result will be the bitvector XOR of the given
values.

\item \kw{CkReduction::set} : the result will be a verbatim concatenation of
all the contributed data, separated into \kw{CkReduction::setElement} records.
The data contributed can be of any length, and can vary across array elements
or reductions.  To extract the data from each element, see the description
below.

\item \kw{CkReduction::concat} : the result will be a byte-by-byte
concatenation of all the contributed data.  The contributed elements
are not delimiter-separated.

\item \kw{CkReduction::random} : the result will be a single randomly
selected value of all of the contributed values.

\item \kw{CkReduction::statistics} : returns
a \kw{CkReduction::statisticsElement} struct, containing summary
statistics of the contributed data.  Specifically, the struct
contains the following fields: \kw{int count}, \kw{double
mean}, and \kw{double m2}, and the following functions: \kw {double
variance()} and \kw{double stddev()}.

\end{enumerate}

\kw{CkReduction::set} returns a collection of \kw{CkReduction::setElement}
objects, one per contribution.  This class has the definition:

\begin{alltt}
class CkReduction::setElement 
\{
public:
  int dataSize; //The length of the `data' array in bytes.
  char data[1]; //A place holder that marks the start of the data array.
  CkReduction::setElement *next(void);
\};
\end{alltt}

Example: Suppose you would like to contribute 3 integers from each array
element. In the reduction method you would do the following:

\begin{alltt}
void ArrayClass::methodName (CkCallback &cb)
\{
  int result[3];
  result[0] = 1;            // Copy the desired values into the result.
  result[1] = 2;
  result[2] = 3;
  // Contribute the result to the reductiontarget cb.
  contribute(3*sizeof(int), result, CkReduction::set, cb);
\}
\end{alltt}

Inside the reduction's target method, the contributions can be accessed by using
the \texttt{CkReduction::setElement->next()} iterator.

\begin{alltt}
void SomeClass::reductionTargetMethod (CkReductionMsg *msg)
\{
  // Get the initial element in the set.
  CkReduction::setElement *current = (CkReduction::setElement*) msg->getData();
  while(current != NULL) // Loop over elements in set.
  \{
    // Get the pointer to the packed int's.
    int *result = (int*) &current->data;
    // Do something with result.
    current = current->next(); // Iterate.
  \}
\}
\end{alltt}

The reduction set order is undefined.  You should add a source field to the
contributed elements if you need to know which array element gave a particular
contribution.  Additionally, if the contributed elements are of a complex 
data type, you will likely have to supply code for 
%serialize/unserialize operation on your element structure if your
%reduction element data is complex.  
serializing/deserializing them.
Consider using the \kw{PUP}
interface (\S~\ref{sec:pup}) to simplify your object serialization
needs.

If the outcome of your reduction is dependent on the order in which 
data elements are processed, or if your data is just too
heterogeneous to be handled elegantly by the predefined types and you
don't want to undertake multiple reductions, you can use a tuple
reduction or define your own custom reduction type.

Tuple reductions allow performing multiple different reductions in the
same message. The reductions can be on the same or different data, and
the reducer type for each reduction can be set independently as well.
The contributions that make up a single tuple reduction message are all
reduced in the same order as each other. As an example, a chare array
element can contribute to a gatherv-like operation using a tuple reduction
that consists of two set reductions.

\begin{alltt}
int tupleSize = 2;
CkReduction::tupleElement tupleRedn[] = \{
  CkReduction::tupleElement(sizeof(int), \&thisIndex, CkReduction::set),
  CkReduction::tupleElement(sizeData, data, CkReduction::set)
\};
CkReductionMsg* msg = CkReductionMsg::buildFromTuple(tupleRedn, tupleSize);
CkCallback allgathervCB(CkIndex\_Foo::allgathervResult(0), thisProxy);
msg->setCallback(allgathervCB);
contribute(msg);
\end{alltt}

The result of this reduction is a single CkReductionMsg that can be processed
as multiple reductions:

\begin{alltt}
void Foo::allgathervResult (CkReductionMsg* msg)
\{
  int numReductions;
  CkReduction::tupleElement* results;

  msg->toTuple(\&results, \&numReductions);
  CkReduction::setElement* currSrc  = (CkReduction::setElement*)results[0].data;
  CkReduction::setElement* currData = (CkReduction::setElement*)results[1].data;

  // ... process currSrc and currData

  delete [] results;
\}
\end{alltt}

See the next section (Section~\ref{new_type_reduction}) for details on
custom reduction types.

\section{Destroying Array Elements}

To destroy an array element -- detach it from the array,
call its destructor, and release its memory--invoke its 
\kw{Array destroy} method, as:

\begin{alltt}
a1[i].ckDestroy();
\end{alltt}

Note that this method can also be invoked remotely i.e. from 
a process different from the one on which the array element resides.
You must ensure that no messages are sent to a deleted element. 
After destroying an element, you may insert a new element at
its index.