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