\subsection{Chare Arrays}

Chare arrays \index{arrays} are arbitrarily-sized collections of chares.  The
entire array is 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. 1D array), several integers (i.e. a
multidimentional array), or an arbitrary string of bytes (e.g. a binary tree
index).

Array elements can be dynamically created and destroyed on any processor,
and messages for the elements will still arrive properly.
Array elements can be migrated at any time, allowing arrays to be efficiently
load balanced.  Array elements can also receive array broadcasts and
contribute to array reductions.

\subsubsection{Declaring a 1D Array}

You can declare a one-dimentional \index{array}\index{chare array}chare array
as:

\begin{alltt}
//In the .ci file:
array [1D] A \{
  entry A();
  entry void someEntry(M1 *);
\};

//In the .h file:
class M1:public CMessage_M1 \{
//...message fields...
\};
\end{alltt}

Just as every Chare inherits from the system class \kw{Chare}, every 
array element inherits from the system class \kw{ArrayElement} (or one
of its subclasses, \kw{ArrayElement1D}, \kw{ArrayElement2D}, or 
\kw{ArrayElement3D}). Just as a Chare inherits ``thisChare'', each
array element inherits ``thisArrayID'', the \kw{CkArrayID} of its array,
and ``thisIndex'', the element's array index.

\begin{alltt}
class A : public ArrayElement1D \{
  public:
    A(void);
    A(CkMigrateMessage *);

    void someEntry(M1 *);
\};
\end{alltt}

Note \uw{A}'s odd migration constructor, which is normally empty:

\begin{alltt}
//In the .C file:
A::A(void)
\{
  //...your constructor code...
\}
A::A(CkMigrateMessage *m) \{ \}
\end{alltt}

Read the section ``Migratable Array Elements'' for more
information on the \kw{CkMigrateMessage} constructor. 


\subsubsection{Declaring 2D, 3D, or User-defined Index Arrays}

\charmpp{} contains direct support for 1D, 2D, 3D, and user-defined
index arrays.  These arrays can be declared as:

\begin{alltt}
//In the .ci file:
message MyMsg;
array [1D] A1 \{ entry A1(); entry void e(MyMsg *m);\}
array [2D] A2 \{ entry A2(); entry void e(MyMsg *m);\}
array [3D] A3 \{ entry A3(); entry void e(MyMsg *m);\}
array [Foo] AF \{ entry AF(); entry void e(MyMsg *m);\}
\end{alltt}

The last declaration expects an array index of type \kw{CkArrayIndex}\uw{Foo},
which must be defined before including the \texttt{.decl.h} file 
(see ``User-defined array index type'' below).  

\begin{alltt}
//In the .h file:
class MyMsg: public CMessage_MyMsg \{
public: 
  int val;
  MyMsg(int i) \{val=i;\}
\}
class A1:public ArrayElement1D \{ public: A1()\{\} ...\};
class A2:public ArrayElement2D \{ public: A2()\{\} ...\};
class A3:public ArrayElement3D \{ public: A3()\{\} ...\};
class AF:public ArrayElementT<CkArrayIndexFoo> 
  \{ public: AF()\{\} ...\};
\end{alltt}

A 1D array element can access its index via its inherited ``thisIndex''
field; a 2D via ``thisIndex.x'' and ``thisIndex.y'', and a 3D via
``thisIndex.x'', ``thisIndex.y'', and ``thisIndex.z''.  A user-defined
index array can access its index as ``thisIndex''.


\subsubsection{Creating an Array}

You create an array using the \kw{CProxy\_Array::ckNew}
routine.  This returns a proxy object, which can
be kept, copied, or sent in messages.
The array proxy responds to the appropriate index call--
for 1D arrays, use [i] or (i); for 2D use (x,y); for 3D
use (x,y,z); and for user-defined types use [f] or (f).

You insert elements into the array by indexing the proxy
and calling insert.  The insert call optionally takes 
a message, which is passed to the constructor, or a
processor number, where the element will be created.
Array elements can be inserted in any order from 
any processor at any time.  Array elements need not 
be contiguous.

After creating elements, start using the array with 
\kw{CProxy\_Array::doneInserting}:

\begin{alltt}
//In the .C file:
int x,y,z;
CProxy_A1 a1=CProxy_A1::ckNew();  //Creates new 1D array
for (x=...) \{
   a1[x  ].insert();  //Bracket syntax
   a1(x+1).insert();  // or equivalent parenthesis syntax
\}
a1.doneInserting();

CProxy_A2 a2=CProxy_A2::ckNew();   //Creates new 2D array
for (x=...) for (y=...)
   a2(x,y).insert();  //Can't use brackets!
a2.doneInserting();

CProxy_A3 a3=CProxy_A3::ckNew();   //Creates new 3D array
for (x=...) for (y=...) for (z=...)
   a3(x,y,z).insert();
a3.doneInserting();

CProxy_AF aF=CProxy_AF::ckNew();   //Creates new user-defined index array
for (...) \{
   aF[CkArrayIndexFoo(...)].insert(); //Use brackets...
   aF(CkArrayIndexFoo(...)).insert(); //  ...or parenthesis
\}
aF.doneInserting();

\end{alltt}

To create a 1D \index{array}array containing elements indexed 
(0, 1, ..., \uw{num\_elements}-1), you can use the shorter:

\begin{alltt}
CProxy_A1 a1 = CProxy_A1::ckNew(num_elements);
\end{alltt}

This is exactly equivalent to the loop:
\begin{alltt}
CProxy_A1 a = CProxy_A1::ckNew();
for (i=0;i<num_elements;i++)
	a1[i].insert();
a1.doneInserting();
\end{alltt}


The \kw{doneInserting} call starts the the reduction manager (see ``Array
Reductions'') and load balancer (see ``Load Balancer'')-- since
these objects need to know about all the array's elements, they
must be started after the initial elements are inserted.
You may call \kw{doneInserting} multiple times, but only the first
call actually does anything.  You may even \kw{insert} or \kw{destroy}
elements after a call to \kw{doneInserting}, with different semantics-- 
see the reduction manager and load balancer sections for details.

If you do not specify one, the system will chooses a procesor to 
create an array element on based on the element's index: 1D indices 
map to processors in a round-robin fashion; other indices are mapped 
based on a hash function applied to the index.

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}
a3(x,y,z).destroy();
\end{alltt}

After destroying an element, you may insert a new element at
its index.

\subsubsection{Messages and Broadcasts}

To send a \index{Array message} message to an array element, index the proxy 
and call the method name, possibly passing a message:

\begin{alltt}
a1[i].doSomething(new MyMsg(7));
a3(x,y,z).doAnother(new MyMsg(23));
aF[CkArrayIndexFoo(...)].doAgain();
\end{alltt}

You may invoke methods on array elements that have not yet
been created-- the system will buffer the message until the
element is created.  However, the element must eventually be 
created (currently, there is a 3-minute buffering period).
Messages sent to migrating elements will be delivered after
the migrating element arrives.  It is an error to send 
a message to a deleted array element.


To \index{Array broadcast} broadcast a message to all the current elements of an array, 
simply omit the index, as:

\begin{alltt}
a3.doIt(new MyMsg(7)); //<- invokes doIt(7) 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.


\subsubsection{Reductions on Chare Arrays}
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 on the
elements of a Chare array.

The data to be reduced comes from each array element, 
which must call the \kw{contribute} method:

\begin{alltt}
ArrayElement::contribute(int nBytes,void *data,ReducerType type);
\end{alltt}

This call contributes \kw{nBytes} bytes starting at \kw{data} to the
reduction \kw{type} (see reduction types, below).  Unlike sending a
message, you may use \kw{data} after the call to \kw{contribute}.  All
array elements must call \kw{contribute}, and all must use the same
reduction type.  

When you create a new array element, it is expected
to contribute to the next reduction not already in progress.  The
reduction will complete properly even if array elements are migrated
or deleted. No reduction will complete until the first DoneInserting
is broadcast-- this gives every initial element a chance to contribute.

If we want to sum each array element's single integer myInt, we would use:

\begin{alltt}
    //Inside any array element method
    int myInt=get_myInt();
    contribute(sizeof(int),(void *)\&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 an array has a pair of
doubles \uw{forces}[2] which need to be summed up (separately) across
all array elements, from each array element call:

\begin{alltt}
    //Inside any array element method
    double forces[2]=get_my_forces();
    contribute(2*sizeof(double),(void *)forces,CkReduction::sum_double);
\end{alltt}

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


After the data is reduced, it is passed to a ``client'' function on
node zero.  This is an ordinary C or C++ function that you pass to
\kw{CProxy\_Array::setReductionClient}.  Reduction clients are
typically registered from your main Chare's constructor, as in:

\begin{alltt}
//Outside any class definition:
void myClient(void *param,int dataSize,void *data)
\{
  double *forceSum=(double *)data;
  cout<<``First force sum is ``<<forceSum[0]<<endl;
  cout<<``Second force sum is ``<<forceSum[1]<<endl;
\}

...
    //Inside main::main
    myArray.setReductionClient(myClient,(void *)NULL);
\end{alltt}

This simple client prints out the double values received, and does not
use the \uw{param} value passed in (\kw{NULL}, in this case).  The
handler can use \uw{param}, \uw{dataSize}, and the data in any
fashion; but the data will be deleted after the handler returns.


\subsubsection{Built-in Array Reduction Types}

\charmpp{} includes several built-in reduction types, used to combine the
contributions from different array elements.  Any of them may be passed as an
\kw{ArrayReductionFn} type to \kw{ArrayElement::contribute}.

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

\begin{enumerate}

\item \kw{CkReduction::sum\_int}, \kw{sum\_float}, \kw{sum\_double}-- the
result will be the sum of the given numbers.

\item \kw{CkReduction::product\_int}, \kw{product\_float},
\kw{product\_double}-- the result will be the product of the given numbers.

\item \kw{CkReduction::max\_int}, \kw{max\_float}, \kw{max\_double}-- the
result will be the largest of the given numbers.

\item \kw{CkReduction::min\_int}, \kw{min\_float}, \kw{min\_double}-- the
result will be the smallest of the given numbers.

\item \kw{CkReduction::and}-- the result will be the logical AND of the given
integers.  0 is false, nonzero is true.

\item \kw{CkReduction::or}-- the result will be the logical OR of the given
integers.

\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.

\end{enumerate}


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

\begin{alltt}
class CkReduction::setElement 
\{
public:
  int dataSize;//The length of the data array below
  char data[];//The (dataSize-long) array of data
  CkReduction::setElement *next(void);
\};
\end{alltt}

To extract the contribution of each array element from a reduction set, use the
\uw{next} routine repeatedly:

\begin{alltt}
  //Inside a reduction handler-- 
  //  data is our reduced data from CkReduction_set
  CkReduction::setElement *cur=(CkReduction::setElement *)data;
  while (cur!=NULL)
  \{
    ... //Use cur->dataSize and cur->data
    //Now advance to the next element's contribution
    cur=cur->next();
  \}
\end{alltt}

The reduction set order is undefined.  Add a source field to your contribution
if you need to know which array element gave a particular contribution.



\subsubsection{User-defined array index type}

\index{Array index type, user-defined}
\charmpp{} array indices are arbitrary collections of integers.
To define a new array index, you create an ordinary C++ class 
which inherits from \kw{CkArrayIndex} and sets the ``nInts'' member
to the length, in integers, of the array index.

For example, if you have a structure or class named ``foo'', you 
can use a \uw{foo} object as an array index by defining the class:

\begin{alltt}
#include <charm++.h>
class CkArrayIndexFoo:public CkArrayIndex \{
public:
    foo f;

    CkArrayIndexFoo(const foo \&in) 
    \{
        f=in;
        nInts=sizeof(f)/sizeof(int);
    \}
\};
\end{alltt}

Note that \uw{foo}'s size must be an integral number of integers--
you must pad it with zero bytes if this is not the case.
Also, \uw{foo} must be a simple class-- it cannot contain 
pointers, have virtual functions, or require a destructor.
Finally, there is a \charmpp configuration-time option called
CK\_ARRAYINDEX\_MAXLEN \index{CK\_ARRAYINDEX\_MAXLEN} 
which is the largest allowable number of 
integers in an array index.  The default is 3; but you may 
override this to any value by passing ``-DCK\_ARRAYINDEX\_MAXLEN=n'' 
to the \charmpp build script. Larger values will increase the
size of each message.

You can then declare an array indexed by \uw{foo} objects with

\begin{alltt}
//in the .ci file:
array [Foo] AF \{ entry AF(); ... \}

//in the .h file:
class AF:public ArrayElementT<CkArrayIndexFoo>
\{ public: AF() \{\} ... \}

//in the .C file:
    foo f;
    CProxy_AF a=CProxy_AF::ckNew();
    a[new CkArrayIndexFoo(f)].insert();
    ...
\end{alltt}

\kw{ArrayElementT} is a class templated by the index type \uw{foo}.
The array index is then accessible as ``thisIndex'':
For example:

\begin{alltt}

//in the .C file:
AF::AF()
\{
    CkArrayIndexFoo myF=thisIndex;
    functionTakingFoo(myF);
\}
\end{alltt}


\subsubsection{Migratable Array Elements}
Array objects can \index{migrate}migrate from one PE to another.
For example, the load balancer (see section ``Load Balancing Chare Arrays'')
might migrate array elements to better balance the load between
processors.  For an array element to migrate, it must implement
a pack/unpack or ``pup'' method:

\begin{alltt}
//In the .h file:
class A2:public ArrayElement2D \{
private: //My data members:
    int nt;
    unsigned char chr;
    float flt[7];
    int numDbl;
    double *dbl;
public:	
    //...other declarations

    virtual void pup(PUP::er \&p);
\};

//In the .C file:
void A2::pup(PUP::er \&p)
\{
    ArrayElement2D::pup(p); //<- MUST call superclass's pup routine
    p(nt);
    p(chr);
    p(flt,7);
    p(numDbl);
    if (p.isUnpacking()) dbl=new double[numDbl];
    p(dbl,numDbl);
\}
\end{alltt}

You can apply a \kw{PUP::er} to any primitive variable
(as with ``p(nt)'') or array of primitive variables-- there,
the second parameter gives the length of the array (as with
``p(flt,7)'').  You can pass a simple run of bytes 
by calling the \kw{PUP::er} with a ``void *'' and number of bytes
(packing bytes, however, prevents cross-platform pack/unpacking).

The system uses one pup routine to do both packing and unpacking by
passing different types of \kw{PUP::er}s to it.  You can determine
what type of \kw{PUP::er} has been passed to you with the
\kw{isPacking()}, \kw{isUnpacking()}, and \kw{isSizing()} calls.

An array element can migrate by calling the \kw{migrateMe}(\uw{destination
processor}) member function-- this call must be the last action
in an element entry point.  The system can also migrate array elements
for load balancing (see the ``Load Balancing Chare Arrays'' chapter).

To migrate your array element to another processor, the \charmpp{}
runtime will:

\begin{itemize}
\item Call your \uw{pup} method with a sizing \kw{PUP::er} to determine how 
big a message it needs to hold your element.
\item Call your \uw{pup} method again with a packing \kw{PUP::er} to pack 
your element into a message.
\item Call your element's destructor (killing off the old copy).
\item Send the message (containing your element) across the network.
\item Call your element's migration constructor on the new processor.
\item Call your \uw{pup} method on with an unpacking \kw{PUP::er} to unpack 
the element.
\end{itemize}

Migration constructors, then, are normally empty-- all the unpacking
and allocation of the data items is done in the element's \uw{pup} routine.
Deallocation is done in the element destructor as usual.

The \kw{PUP::er} overhead is very small-- one virtual function call
for each item to be packed/unpacked.  The actual packing/unpacking is
a simple memory-to-memory binary copy.  In addition, the \uw{pup}
routine may also be called to pack your array element to disk (e.g.,
for a ``checkpoint'' operation), and unpack it from disk afterwards
(e.g., for ``restart'' operation).  During unpacking, a
``translating'' \kw{PUP::er} can be used to perform binary format
conversion if needed.

To easily pack user-defined types, we recommend adding
a \uw{pup} method to the user-defined type:

\begin{alltt}
class myData 
\{
private:
    int a,b;
    char c;
public:
    ...
    void pup(PUP::er \&p) \{
        p(a);
        p(b);
        p(c);
    \}
\};

//... array element can now easily pack myData as:
class myElement:public ArrayElement1D 
\{
private:
    myData d;
public:
    ...
    void pup(PUP::er \&p)
    \{
        ArrayElement1D::pup(p); //Call superclass
        d.pup(p); //<- pack/unpacks myData
    \}
\};
\end{alltt}


\subsubsection{Load Balancing Chare Arrays}
\charmpp{} includes a run-time load balancer which works
on array elements.  The idea is to run programs more efficiently
by migrating array elements away from overloaded processors.
To use the load balancer, you must make your elements migratable
(see migration section above) and chose a load balancing 
``strategy'' (see the load balancing section for a description
of load balancing strategy routines).

There are two ways to use the load balancer-- the AtSync
method, for elements that only want to be migrated at certain
times; and the Anytime method, for elements that can migrate
at any time.

The Anytime method is the default.  Your elements may be
asked to migrate any time they are not currently executing
an entry method.

For the AtSync method, set \kw{usesAtSync} to true in your 
array element constructor.  When an element is ready to migrate,
call \kw{ArrayElement::AtSync}.  Once all elements have reached \kw{AtSync}, 
and after the first DoneInserting call,
the load balancer runs and may migrate elements.  Once
all migrations are complete, the load balancer calls 
\kw{ArrayElement::ResumeFromSync}.  You must ensure no messages are
sent to an array element between its calls to \kw{AtSync} and
\kw{ResumeFromSync}. \kw{AtSync}/\kw{ResumeFromSync} is currently
a implemented as a global barrier.


\subsubsection{Array Syntax Changes}

The syntax for arrays changed in April, 2000 in the following ways:

\begin{itemize}

\item \kw{CkAID} is obsolete, and replaced with \kw{CkArrayID}.  In general,
you should now use CProxy's instead of \kw{CkArrayID}'s because the syntax
is more palatable and the compiler can do static type checking.

\item The translator syntax for arrays now includes the index type,
e.g. ``array [1D] foo \{ ... \}''.

\item Messages sent to array elements need no longer inherit from 
\kw{ArrayMessage}.

\item Array elements for 1D arrays must inherit from \kw{ArrayElement1D} to use
a 1D \kw{thisIndex}.  You may still inherit from \kw{ArrayElement}, but you
won't have a \kw{thisIndex}.

\item You may have multiple array constructors; each can now take a
user-defined message, or no message.  

\item The \kw{ArrayElementCreateMessage} constructor is obsolete;
as are the \kw{finishConstruction} and \kw{finishMigration} calls. No
constructor need explicitly call its superclass.

\item \kw{ArrayElementMigrateMessage} is now depricated-- use 
\kw{CkMigrateMessage}.

\item For migration, the old packsize, pack, and unpacking portion of
the migration constructor have been replaced by a unified pack/unpack 
``pup'' routine.

\item For load balancing, the \kw{uses\_at\_sync} variable is now called
\kw{usesAtSync}.

\item \kw{CkReduction\_sum\_int} is now an enumeration, not a function pointer,
and now called \kw{CkReduction::sum\_int}.

\item \function{CkRegisterArrayReductionHandler(proxy,fn,param)} is now
proxy.setReductionClient(fn,param). 

\end{itemize}



