3.16 Reductions

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.

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

This call contributes nBytes bytes starting at data to the reduction type (see reduction types, below). 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.

When you create a new chare array element, it is expected to contribute to the next reduction not already in progress on that processor. The reduction will complete properly even if elements are migrated or deleted during the reduction.

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.

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:

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 below (Section 3.16.1).

3.16.1 Reduction Clients

After the data is reduced, it is passed to a you via a callback object, as described in section 3.17. The message passed to the callback is of type CkReductionMsg. The important members of CkReductionMsg are getSize(), which returns the number of bytes of reduction data; and getData(), which returns a ``void *'' to the actual reduced data.

You may pass the client callback as an additional parameter to contribute. If different contribute calls pass different callbacks, some (unspecified, unreliable) callback will be chosen for use.

double forces[2]=get_my_forces(); // When done, broadcast the CkReductionMsg to ``myReductionEntry'' CkCallback cb(CkIndex_myArrayType::myReductionEntry(NULL), thisProxy); contribute(2*sizeof(double), forces,CkReduction::sum_double, cb);

In the case of the reduced version used for synchronization purposes, the callback parameter will be the only input parameter:

CkCallback cb(CkIndex_myArrayType::myReductionEntry(NULL), thisProxy); contribute(cb);

If no member passes a callback to contribute, the reduction will use the default callback. Programmers can set the default callback for an array or group using the ckSetReductionClient proxy call on processor zero, or by passing the callback to CkArrayOptions::setReductionClient() before creating the array, as described in section 3.9.3. Again, a CkReductionMsg message will be passed to this callback, which must delete the message when done.

// Somewhere on processor zero: myProxy.ckSetReductionClient(new CkCallback(...));

CkCallback *cb = new CkCallback(CkIndex_main::reportIn(NULL), mainProxy); arr.ckSetReductionClient(cb);

void myReductionEntry(CkReductionMsg *msg) { int reducedArrSize=msg->getSize() / sizeof(double); double *output=(double *) msg->getData(); for(int i=0 ; i<reducedArrSize ; i++) { // Do something with the reduction results in each output[i] array element . . . } delete msg; }

For backward compatibility, in the place of a general callback, you can specify a particular kind of C function using ckSetReductionClient or setReductionClient. This C function takes a user-defined parameter (passed to setReductionClient) and the actual reduction data, which it must not deallocate.

// Somewhere on processor zero (possibly in Main::Main, after creating 'myProxy'): myProxy.setReductionClient(myClient,(void *)NULL); // Code for the C function that serves as reduction client: 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; }

3.16.2 Typed Reductions

Typically the client entry method of a reduction takes a single argument of type CkReductionMsg. 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 .cc file: // Create a callback that invokes the typed reduction client 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, and for any user-defined type with a PUP method (see 3.18). If you know that the reduction will yield a particular number of elements, say 3 ints, you can also specify a reduction target which takes 3 ints and it will be invoked correctly.

3.16.3 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 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 either single numbers (pass a pointer) or arrays- just pass the correct number of bytes to contribute.

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 below char data[];//The (dataSize-long) array of data CkReduction::setElement *next(void); };

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

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

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 see 3.18 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 heterogenous to be handled elegantly by the predefined types and you don't want to undertake multiple reductions, it may be best to define your own reduction type. See the next section (Section 3.16.4) for details.

3.16.4 Defining a New Reduction Type

It is possible to define a new type of reduction, performing a user-defined operation on user-defined data. This is done by creating a reduction function, which combines separate contributions into a single combined value.

The input to a reduction function is a list of CkReductionMsgs. A CkReductionMsg is a thin wrapper around a buffer of untyped data to be reduced. The output of a reduction function is a single CkReductionMsg containing the reduced data, which you should create using the CkReductionMsg::buildNew(int nBytes,const void *data) method.

CkReductionMsg *reductionFn(int nMsg,CkReductionMsg **msgs);

For example, a reduction function to add up contributions consisting of two machine short ints would be:

CkReductionMsg *sumTwoShorts(int nMsg,CkReductionMsg **msgs) { //Sum starts off at zero short ret[2]=0,0; for (int i=0;i<nMsg;i++) { //Sanity check: CkAssert(msgs[i]->getSize()==2*sizeof(short)); //Extract this message's data short *m=(short *)msgs[i]->getData(); ret[0]+=m[0]; ret[1]+=m[1]; } return CkReductionMsg::buildNew(2*sizeof(short),ret); }

The reduction function must be registered with CHARM++ using CkReduction::addReducer from an initcall routine (see section 3.20 for details on the initcall mechanism). CkReduction::addReducer returns a CkReduction::reducerType which you can later pass to contribute. Since initcall routines are executed once on every node, you can safely store the CkReduction::reducerType in a global or class-static variable. For the example above, the reduction function is registered and used in the following manner:

//In the .ci file: initcall void registerSumTwoShorts(void); //In some .C file: /*global*/ CkReduction::reducerType sumTwoShortsType; /*initcall*/ void registerSumTwoShorts(void) { sumTwoShortsType=CkReduction::addReducer(sumTwoShorts); } //In some member function, contribute data to the customized reduction: short data[2]=...; contribute(2*sizeof(short),data,sumTwoShortsType);

Note that you cannot call CkReduction::addReducer from anywhere but an initcall routine.