b006f8921326568f46d1889fc34eb0615e29af48
[charm.git] / doc / charm++ / reductions.tex
1 \subsection{Reductions}
2
3 \label{reductions}
4
5 A \index{array reduction}reduction applies a single operation (e.g. add,
6 max, min, ...) to data items scattered across many processors and
7 collects the result in one place.  \charmpp{} supports reductions
8 over the members of an array or group.
9
10 The data to be reduced comes from a call to the member \kw{contribute} 
11 method:
12 \begin{alltt}
13 void contribute(int nBytes,const void *data,CkReduction::reducerType type);
14 \end{alltt}
15
16 This call contributes \kw{nBytes} bytes starting at \kw{data} to the
17 reduction \kw{type} (see reduction types, below).  Unlike sending a
18 message, you may use \kw{data} after the call to \kw{contribute}.  All
19 members must call \kw{contribute}, and all must use the same
20 reduction type.  
21
22 When you create a new member, it is expected
23 to contribute to the next reduction not already in progress on that
24 processor.  The
25 reduction will complete properly even if members are migrated
26 or deleted during the reduction. 
27
28 For example, if we want to sum each member's single integer myInt, 
29 we would use:
30
31 \begin{alltt}
32     //Inside any member method
33     int myInt=get_myInt();
34     contribute(sizeof(int),\&myInt,CkReduction::sum_int);
35 \end{alltt}
36
37 The built-in reduction types (see below) can also handle arrays of
38 numbers.  For example, if each element of an array has a pair of
39 doubles \uw{forces}[2] which need to be summed up (separately) across
40 every element, from each element call:
41
42 \begin{alltt}
43     double forces[2]=get_my_forces();
44     contribute(2*sizeof(double),forces,CkReduction::sum_double);
45 \end{alltt}
46
47 Note that since C++ arrays (like \uw{forces}[2]) are already pointers, we 
48 don't use \&\uw{forces}.
49
50 Sometimes it is not important the data to be reduced, but only the fact that all
51 elements have reached a synchronization point. In this case a simpler version of
52 contribute can be used:
53
54 \begin{alltt}
55     contribute();
56 \end{alltt}
57
58 In all cases, the result of the reduction operation is passed to the {\em reduction
59 client}.  Many different kinds of reduction clients can be used, as
60 explained below (Section~\ref{reductionClients}).
61
62
63
64 \subsubsection{Reduction Clients}
65
66 \label{reductionClients}
67
68 After the data is reduced, it is passed to a you via a callback object,
69 as described in section~\ref{callbacks}.  The message passed to
70 the callback is of type \kw{CkReductionMsg}.
71 The important members of \kw{CkReductionMsg} are
72 \kw{getSize()}, which returns the number of bytes of reduction data; and
73 \kw{getData()}, which returns a ``void *'' to the actual reduced data.
74
75 You may pass the client callback as an additional parameter to \kw{contribute}.
76 If different \kw{contribute} calls pass different callbacks, some (unspecified,
77 unreliable) callback will be chosen for use.
78 \begin{alltt}
79     double forces[2]=get_my_forces();
80     //When done, broadcast the CkReductionMsg to ``myReductionEntry''
81     CkCallback cb(CkIndex_myArrayType::myReductionEntry(NULL), thisProxy);
82     contribute(2*sizeof(double), forces,CkReduction::sum_double, cb);
83 \end{alltt}
84
85 In the case of the reduced version used for synchronization purposes, the
86 callback parameter will be the only input parameter:
87 \begin{alltt}
88     contribute( CkCallback(CkIndex_myArrayType::myReductionEntry(NULL), thisProxy) );
89 \end{alltt}
90
91 If no member passes a callback to \kw{contribute}, the reduction will use
92 the default callback. Programmers can set the default callback for an array or group
93 using the \kw{ckSetReductionClient} proxy call on processor zero, or
94 by passing the callback to {\tt CkArrayOptions::setReductionClient()}
95 before creating the array, as described in section~\ref{CkArrayOptions}.
96 Again, a \kw{CkReductionMsg} message will be passed to this callback,
97 which must delete the message when done.
98
99 \begin{alltt}
100     //Somewhere on processor zero:
101     myProxy.ckSetReductionClient(new CkCallback(...));
102 \end{alltt}
103
104 So, for the previous reduction on chare array arr:
105 \begin{alltt}
106     CkCallback *cb = new CkCallback(CkIndex_main::reportIn(NULL),  mainProxy);
107     arr.ckSetReductionClient(cb);
108 \end{alltt}
109
110 and the actual entry point:
111
112 \begin{alltt}
113 void myReductionEntry(CkReductionMsg *msg)
114 \{
115   int reducedArrSize=msg->getSize() / sizeof(double);
116   double *output=(double *) msg->getData();
117   for(int i=0 ; i<reducedArrSize ; i++)
118   \{
119    // do something with the reduction results in each output[i] array element
120    .
121    .
122    .
123   \}
124   delete msg;
125 \}
126 \end{alltt}
127
128 (See \kw{pgms/charm++/RedExample} for a complete example).
129
130 For backward compatability, rather than a general callback you can
131 specify a peculiar kind of C function using \kw{ckSetReductionClient}
132 or \kw{setReductionClient}.  This C function takes a user-defined
133 parameter (passed to \kw{setReductionClient}) and the actual reduction data,
134 which it must not deallocate.
135
136 \begin{alltt}
137   //Somewhere on processor zero:
138   myProxy.setReductionClient(myClient,(void *)NULL);
139
140 void myClient(void *param,int dataSize,void *data)
141 \{
142   double *forceSum=(double *)data;
143   cout<<``First force sum is ``<<forceSum[0]<<endl;
144   cout<<``Second force sum is ``<<forceSum[1]<<endl;
145 \}
146 \end{alltt}
147
148 \subsubsection{Typed Reductions}
149
150 \label{typed_reductions}
151
152 Typically the entry method that is invoked when a reduction is completed
153 takes a single argument of type CkReductionMsg. However, by giving an entry
154 method the \kw{reductiontarget} attribute, you can instead use entry methods
155 that take arguments of the same type that the reduction function yields.
156 For example, for a reduction that yields an int, a typed reduction might look
157 like this:
158
159 \begin{alltt}
160 // in the .ci file...
161 entry [reductiontarget] void done(int result);
162
163 // in the .cc file...
164 void Driver::done(int result) {
165    CkPrintf("Reduction value: \%d", result);
166 }
167 \end{alltt}
168
169 This will also work for arrays, and for any user-defined type with a PUP method
170 (see ~\ref{sec:pup}). If you know that the reduction will yield a particular
171 number of elements, say 3 ints, you can also specify a reduction target which
172 takes 3 ints and it will be invoked correctly. When creating a callback to the
173 reduction target, the entry method index is generated by {\tt
174 CkReductionTarget(chare\_name, method\_name)}.
175
176 \subsubsection{Built-in Reduction Types}
177
178 \label{builtin_reduction}
179
180 \charmpp{} includes several built-in reduction types, used to combine 
181 the separate contributions.  Any of them may be passed as an
182 \kw{CkReduction::reducerType} type to \kw{contribute}.
183
184 The first four reductions (sum, product, max, and min) work on int,
185 float, or double data as indicated by the suffix.  The logical
186 reductions (and, or) only work on integer data.  All the built-in
187 reductions work on either single numbers (pass a pointer) or arrays-- just
188 pass the correct number of bytes to \kw{contribute}.
189
190 \begin{enumerate}
191
192 \item \kw{CkReduction::sum\_int}, \kw{sum\_float}, \kw{sum\_double}-- the
193 result will be the sum of the given numbers.
194
195 \item \kw{CkReduction::product\_int}, \kw{product\_float},
196 \kw{product\_double}-- the result will be the product of the given numbers.
197
198 \item \kw{CkReduction::max\_int}, \kw{max\_float}, \kw{max\_double}-- the
199 result will be the largest of the given numbers.
200
201 \item \kw{CkReduction::min\_int}, \kw{min\_float}, \kw{min\_double}-- the
202 result will be the smallest of the given numbers.
203
204 \item \kw{CkReduction::logical\_and}-- the result will be the logical AND of the given
205 integers.  0 is false, nonzero is true.
206
207 \item \kw{CkReduction::logical\_or}-- the result will be the logical OR of the given
208 integers.
209
210 \item \kw{CkReduction::bitvec\_and}-- the result will be the bitvector AND of the given numbers (represented as integers).
211
212 \item \kw{CkReduction::bitvec\_or}-- the result will be the bitvector OR of the given numbers (represented as integers).
213
214 \item \kw{CkReduction::set}-- the result will be a verbatim concatenation of
215 all the contributed data, separated into \kw{CkReduction::setElement} records.
216 The data contributed can be of any length, and can vary across array elements
217 or reductions.  To extract the data from each element, see the description
218 below.
219
220 \item \kw{CkReduction::concat}-- the result will be a byte-by-byte
221 concatentation of all the contributed data.  There is no separation
222 added between different contributions.
223
224 \end{enumerate}
225
226
227 \kw{CkReduction::set} returns a collection of \kw{CkReduction::setElement}
228 objects, one per contribution.  This class has definition:
229
230 \begin{alltt}
231 class CkReduction::setElement 
232 \{
233 public:
234   int dataSize;//The length of the data array below
235   char data[];//The (dataSize-long) array of data
236   CkReduction::setElement *next(void);
237 \};
238 \end{alltt}
239
240 To extract the contribution of each array element from a reduction set, use the
241 \uw{next} routine repeatedly:
242
243 \begin{alltt}
244   //Inside a reduction handler-- 
245   //  data is our reduced data from CkReduction_set
246   CkReduction::setElement *cur=(CkReduction::setElement *)data;
247   while (cur!=NULL)
248   \{
249     ... //Use cur->dataSize and cur->data
250     //Now advance to the next element's contribution
251     cur=cur->next();
252   \}
253 \end{alltt}
254
255 The reduction set order is undefined.  Add a source field to your
256 contribution if you need to know which array element gave a particular
257 contribution.  This will require you to do your own
258 serialize/unserialize operation on your element structure if your
259 reduction element data is complex.  Consider using the \kw{PUP}
260 interface see ~\ref{sec:pup} to simplify your object serialization
261 needs.
262
263 If your data is order dependant, or if your data is just too
264 heterogenous to be handled elegantly by the predefined types and you
265 don't want to undertake multiple reductions, it may be best to define
266 your own reduction type.  See the next section
267 (Section~\ref{new_type_reduction}) for details.
268
269
270 \subsubsection{Defining a New Reduction Type}
271
272 \label{new_type_reduction}
273
274 It is possible to define a new type of reduction, performing a 
275 user-defined operation on user-defined data.  A reduction function
276 combines separate contributions (from this or other processors)
277 into a single combined value.
278
279 The input to a reduction function is a list of \kw{CkReductionMsg}s.
280 A \kw{CkReductionMsg} is a thin wrapper around a buffer of untyped data
281 to be reduced.  
282 The output of a reduction function is a single CkReductionMsg
283 containing the reduced data, which you should create using the
284 \kw{CkReductionMsg::buildNew(int nBytes,const void *data)} method.  
285
286 Thus every reduction function has the prototype:
287 \begin{alltt}
288 CkReductionMsg *\uw{reductionFn}(int nMsg,CkReductionMsg **msgs);
289 \end{alltt}
290
291 For example, a reduction function to add up contributions 
292 consisting of two machine short integers would be:
293
294 \begin{alltt}
295 CkReductionMsg *sumTwoShorts(int nMsg,CkReductionMsg **msgs)
296 \{
297   //Sum starts off at zero
298   short ret[2]={0,0};
299   for (int i=0;i<nMsg;i++) \{
300     //Sanity check:
301     CkAssert(msgs[i]->getSize()==2*sizeof(short));
302     //Extract this message's data
303     short *m=(short *)msgs[i]->getData();
304     ret[0]+=m[0];
305     ret[1]+=m[1];
306   \}
307   return CkReductionMsg::buildNew(2*sizeof(short),ret);
308 \}
309 \end{alltt}
310
311 You must register your reduction function with \charmpp{} 
312 using \kw{CkReduction::addReducer} from
313 an \kw{initcall} routine (see section~\ref{initcall} for details
314 on the \kw{initcall} mechanism).   \kw{CkReduction::addReducer}
315 returns a \kw{CkReduction::reducerType} which you can later 
316 pass to \kw{contribute}.  Since \kw{initcall} routines are executed
317 once on every node, you can safely store the \kw{CkReduction::reducerType}
318 in a global or class-static variable.  For the example above:
319
320 \begin{alltt}
321 //In the .ci file:
322   initcall void registerSumTwoShorts(void);
323
324 //In some .C file:
325 /*global*/ CkReduction::reducerType sumTwoShortsType;
326 /*initcall*/ void registerSumTwoShorts(void)
327 \{
328   sumTwoShortsType=CkReduction::addReducer(sumTwoShorts);
329 \}
330
331 //In some member:
332   short data[2]=...;
333   contribute(2*sizeof(short),data,sumTwoShortsType);
334 \end{alltt}
335
336 Note that you cannot call \kw{CkReduction::addReducer}
337 from anywhere but in an \kw{initcall} routine.
338
339