3.14 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 must call contribute, and all must use the same reduction type.

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

For example, if we want to sum each 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 an array has a pair of doubles forces[2] which need to be summed up (separately) across every element, from each element call:

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

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

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.14.1).

3.14.1 Reduction Clients

After the data is reduced, it is passed to a you via a callback object, as described in section 3.15. 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);

If no member passes a callback to contribute, the reduction will use the default callback. You set the default callback for an array or group using the ckSetReductionClient proxy call on processor zero. 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 compatability, rather than a general callback you can specify a peculiar 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: myProxy.setReductionClient(myClient,(void *)NULL); 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.14.2 Built-in Reduction Types

CHARM++ includes several built-in reduction types, used to combine the separate contributions. Any of them may be passed as an CkReduction::reducerType type to 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 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 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. Add a source field to your contribution if you need to know which array element gave a particular contribution. This will require you to do your own serialize/unserialize operation on your element structure if your reduction element data is complex. Consider using the PUP interface see 3.16 to simplify your object serialization needs.

If your data is order dependant, 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.14.3) for details.

3.14.3 Defining a New Reduction Type

It is possible to define a new type of reduction, performing a user-defined operation on user-defined data. A reduction function combines separate contributions (from this or other processors) 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 integers 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); }

You must register your reduction function with CHARM++ using CkReduction::addReducer from an initcall routine (see section 3.18 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:

//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: short data[2]=...; contribute(2*sizeof(short),data,sumTwoShortsType);

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