Subsections

4 . Chare Arrays

Chare 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 CkArrayID , and each element has a unique index of type CkArrayIndex . A 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: examples/charm++/array .

4 . 1 Declaring a One-dimensional Array

You can declare a one-dimensional (1D) chare array as:

 //In the .ci file:

array [1D] A {
  entry A(parameters1);
  entry void someEntry(parameters2);
};

Array elements extend the system class CBase _ClassName, inheriting several fields:

 class A : public CBase_A {
  public:
    A(parameters1);

    void someEntry(parameters2);
};

Note that A must have a migration constructor , which is typically empty:

 //In the .C file:

A::A(void)
{
  //... constructor code ...
}


A::someEntry(parameters2)
{
  // ... code for someEntry ...
}

See the section  6.3 on migratable array elements for more information on the migration constructor that takes CkMigrateMessage * as the argument.

4 . 2 Declaring Multi-dimensional Arrays

Charm++ supports multi-dimensional or user-defined indices. These array types can be declared as:

 //In the .ci file:

array [1D]  ArrayA { entry ArrayA(); entry void e(parameters);}

array [2D]  ArrayB { entry ArrayB(); entry void e(parameters);}

array [3D]  ArrayC { entry ArrayC(); entry void e(parameters);}

array [4D]  ArrayD { entry ArrayD(); entry void e(parameters);}

array [5D]  ArrayE { entry ArrayE(); entry void e(parameters);}

array [6D]  ArrayF { entry ArrayF(); entry void e(parameters);}

array [Foo] ArrayG { entry ArrayG(); entry void e(parameters);}

The last declaration expects an array index of type CkArrayIndex Foo, which must be defined before including the .decl.h file (see section  13.3 on user-defined array indices for more information).

 //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(){} ...};

The fields in thisIndex are different depending on the dimensionality of the chare array:


4 . 3 Creating an Array

An array is created using the 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  13.2.7 for asynchronous array creation. CProxy_Array::ckNew returns a proxy object, which can be kept, copied, or sent in messages. The following creates a 1D array containing elements indexed (0, 1, ..., dimX-1):

 CProxy_ArrayA a1 = CProxy_ArrayA::ckNew(params, dimX);

Likewise, a dense multidimensional array can be created by passing the extents at creation time to ckNew .

 CProxy_ArrayB a2 = CProxy_ArrayB::ckNew(params, dimX, dimY);

CProxy_ArrayC a3 = CProxy_ArrayC::ckNew(params, dimX, dimY, dimZ);

CProxy_ArrayD a4 = CProxy_ArrayC::ckNew(params, dimW, dimX, dimY, dimZ);

CProxy_ArrayE a5 = CProxy_ArrayC::ckNew(params, dimV, dimW, dimX, dimY, dimZ);

CProxy_ArrayF a6 = CProxy_ArrayC::ckNew(params, dimX1, dimY1, dimZ1, dimX2, dimY2, dimZ2);

For user-defined arrays, this functionality cannot be used. The array elements must be inserted individually as described in section  13.2.5 . During creation, the constructor is invoked on each array element. For more options when creating the array, see section  13.2 .

4 . 4 Entry Method Invocation

To obtain a proxy to a specific element in chare array, the chare array proxy (e.g. thisProxy ) must be indexed by the appropriate index call depending on the dimensionality of the array: To send a message to an array element, index the proxy and call the method name:

 a1[i].doSomething(parameters);

a3(x,y,z).doAnother(parameters);

aF[CkArrayIndexFoo(...)].doAgain(parameters);

You may invoke methods on array elements that have not yet been created. The Charm++ runtime system will buffer the message until the element is created. 4 . 1

Messages are not guaranteed to be delivered in order. For instance, if a method is invoked on method A and then method B ; it is possible that B is executed before A .


 a1[i].A();

a1[i].B();

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.

4 . 5 Broadcasts on Chare Arrays

To broadcast a message to all the current elements of an array, simply omit the index (invoke an entry method on the chare array proxy):


 a1.doIt(parameters); //<- invokes doIt on each array element

The broadcast message will be delivered to every existing array element exactly once. Broadcasts work properly even with ongoing migrations, insertions, and deletions.


4 . 6 Reductions on Chare Arrays

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

The data to be reduced comes from a call to the member contribute method:


 void contribute(int nBytes, const void *data, CkReduction::reducerType type);

This call contributes nBytes bytes starting at data to the reduction type (see Section  4.6.1 ). Unlike sending a message, you may use data after the call to contribute . All members of the chare array or group must call 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:


     // Inside any member method
    int myInt=get_myInt();
    contribute(sizeof(int),&myInt,CkReduction::sum_int);

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 forces[2], the corresponding elements of which are to be added across all elements, from each element call:


     double forces[2]=get_my_forces();
    contribute(2*sizeof(double),forces,CkReduction::sum_double);

This will result in a double array of 2 elements, the first of which contains the sum of all forces[0] values, with the second element holding the sum of all forces[1] values of the chare array elements.

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

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


   // 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  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);
  }

This will also work for arrays of data elements( entry [reductiontarget] void done(int n, int result[n]) ), and for any user-defined type with a PUP method (see  6 ). If you know that the reduction will yield a particular number of elements, say 3 int s, you can also specify a reduction target which takes 3 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:


     contribute();

In all cases, the result of the reduction operation is passed to the reduction client . Many different kinds of reduction clients can be used, as explained in Section  16.1 .

Please refer to examples/charm++/reductions/typed_reduction for a working example of reductions in Charm++.

Note that the reduction will complete properly even if chare array elements are migrated or 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.


4 . 6 . 1 Built-in Reduction Types

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

The first four operations ( sum , product , max , and min ) work on char , short , int , long , long long , float , or double data as indicated by the suffix. The logical reductions ( and , 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 contribute .

  1. CkReduction::nop : no operation performed.

  2. CkReduction::sum_char , sum_short , sum_int , sum_long , sum_long_long , sum_uchar , sum_ushort , sum_uint , sum_ulong , sum_ulong_long , sum_float , sum_double : the result will be the sum of the given numbers.

  3. CkReduction::product_char , product_short , product_int , product_long , product_long_long , product_uchar , product_ushort , product_uint , product_ulong , product_ulong_long , product_float , product_double : the result will be the product of the given numbers.

  4. CkReduction::max_char , max_short , max_int , max_long , max_long_long , max_uchar , max_ushort , max_uint , max_ulong , max_ulong_long , max_float , max_double : the result will be the largest of the given numbers.

  5. CkReduction::min_char , min_short , min_int , min_long , min_long_long , min_uchar , min_ushort , min_uint , min_ulong , min_ulong_long , min_float , min_double : the result will be the smallest of the given numbers.

  6. CkReduction::logical_and_bool , logical_and_int : the result will be the logical AND of the given values.

  7. CkReduction::logical_or_bool , logical_or_int : the result will be the logical OR of the given values.

  8. CkReduction::logical_xor_bool , logical_xor_int : the result will be the logical XOR of the given values.

  9. CkReduction::bitvec_and_bool , bitvec_and_int : the result will be the bitvector AND of the given values.

  10. CkReduction::bitvec_or_bool , bitvec_or_int : the result will be the bitvector OR of the given values.

  11. CkReduction::bitvec_xor_bool , bitvec_xor_int : the result will be the bitvector XOR of the given values.

  12. CkReduction::set : the result will be a verbatim concatenation of all the contributed data, separated into 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.

  13. CkReduction::concat : the result will be a byte-by-byte concatenation of all the contributed data. The contributed elements are not delimiter-separated.

  14. CkReduction::random : the result will be a single randomly selected value of all of the contributed values.

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

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


 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);
};

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


 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);
}

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


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

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 serializing/deserializing them. Consider using the PUP interface (§  6 ) 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.


 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);

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


 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;
}

See the next section (Section  16.2 ) for details on custom reduction types.

4 . 7 Destroying Array Elements

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


 a1[i].ckDestroy();

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.