added new reduction built-in type: nop
[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::nop}-- no operation performed.
193
194 \item \kw{CkReduction::sum\_int}, \kw{sum\_float}, \kw{sum\_double}-- the
195 result will be the sum of the given numbers.
196
197 \item \kw{CkReduction::product\_int}, \kw{product\_float},
198 \kw{product\_double}-- the result will be the product of the given numbers.
199
200 \item \kw{CkReduction::max\_int}, \kw{max\_float}, \kw{max\_double}-- the
201 result will be the largest of the given numbers.
202
203 \item \kw{CkReduction::min\_int}, \kw{min\_float}, \kw{min\_double}-- the
204 result will be the smallest of the given numbers.
205
206 \item \kw{CkReduction::logical\_and}-- the result will be the logical AND of the given
207 integers.  0 is false, nonzero is true.
208
209 \item \kw{CkReduction::logical\_or}-- the result will be the logical OR of the given
210 integers.
211
212 \item \kw{CkReduction::bitvec\_and}-- the result will be the bitvector AND of the given numbers (represented as integers).
213
214 \item \kw{CkReduction::bitvec\_or}-- the result will be the bitvector OR of the given numbers (represented as integers).
215
216 \item \kw{CkReduction::set}-- the result will be a verbatim concatenation of
217 all the contributed data, separated into \kw{CkReduction::setElement} records.
218 The data contributed can be of any length, and can vary across array elements
219 or reductions.  To extract the data from each element, see the description
220 below.
221
222 \item \kw{CkReduction::concat}-- the result will be a byte-by-byte
223 concatentation of all the contributed data.  There is no separation
224 added between different contributions.
225
226 \end{enumerate}
227
228
229 \kw{CkReduction::set} returns a collection of \kw{CkReduction::setElement}
230 objects, one per contribution.  This class has definition:
231
232 \begin{alltt}
233 class CkReduction::setElement 
234 \{
235 public:
236   int dataSize;//The length of the data array below
237   char data[];//The (dataSize-long) array of data
238   CkReduction::setElement *next(void);
239 \};
240 \end{alltt}
241
242 To extract the contribution of each array element from a reduction set, use the
243 \uw{next} routine repeatedly:
244
245 \begin{alltt}
246   //Inside a reduction handler-- 
247   //  data is our reduced data from CkReduction_set
248   CkReduction::setElement *cur=(CkReduction::setElement *)data;
249   while (cur!=NULL)
250   \{
251     ... //Use cur->dataSize and cur->data
252     //Now advance to the next element's contribution
253     cur=cur->next();
254   \}
255 \end{alltt}
256
257 The reduction set order is undefined.  Add a source field to your
258 contribution if you need to know which array element gave a particular
259 contribution.  This will require you to do your own
260 serialize/unserialize operation on your element structure if your
261 reduction element data is complex.  Consider using the \kw{PUP}
262 interface see ~\ref{sec:pup} to simplify your object serialization
263 needs.
264
265 If your data is order dependant, or if your data is just too
266 heterogenous to be handled elegantly by the predefined types and you
267 don't want to undertake multiple reductions, it may be best to define
268 your own reduction type.  See the next section
269 (Section~\ref{new_type_reduction}) for details.
270
271
272 \subsubsection{Defining a New Reduction Type}
273
274 \label{new_type_reduction}
275
276 It is possible to define a new type of reduction, performing a 
277 user-defined operation on user-defined data.  A reduction function
278 combines separate contributions (from this or other processors)
279 into a single combined value.
280
281 The input to a reduction function is a list of \kw{CkReductionMsg}s.
282 A \kw{CkReductionMsg} is a thin wrapper around a buffer of untyped data
283 to be reduced.  
284 The output of a reduction function is a single CkReductionMsg
285 containing the reduced data, which you should create using the
286 \kw{CkReductionMsg::buildNew(int nBytes,const void *data)} method.  
287
288 Thus every reduction function has the prototype:
289 \begin{alltt}
290 CkReductionMsg *\uw{reductionFn}(int nMsg,CkReductionMsg **msgs);
291 \end{alltt}
292
293 For example, a reduction function to add up contributions 
294 consisting of two machine short integers would be:
295
296 \begin{alltt}
297 CkReductionMsg *sumTwoShorts(int nMsg,CkReductionMsg **msgs)
298 \{
299   //Sum starts off at zero
300   short ret[2]={0,0};
301   for (int i=0;i<nMsg;i++) \{
302     //Sanity check:
303     CkAssert(msgs[i]->getSize()==2*sizeof(short));
304     //Extract this message's data
305     short *m=(short *)msgs[i]->getData();
306     ret[0]+=m[0];
307     ret[1]+=m[1];
308   \}
309   return CkReductionMsg::buildNew(2*sizeof(short),ret);
310 \}
311 \end{alltt}
312
313 You must register your reduction function with \charmpp{} 
314 using \kw{CkReduction::addReducer} from
315 an \kw{initcall} routine (see section~\ref{initcall} for details
316 on the \kw{initcall} mechanism).   \kw{CkReduction::addReducer}
317 returns a \kw{CkReduction::reducerType} which you can later 
318 pass to \kw{contribute}.  Since \kw{initcall} routines are executed
319 once on every node, you can safely store the \kw{CkReduction::reducerType}
320 in a global or class-static variable.  For the example above:
321
322 \begin{alltt}
323 //In the .ci file:
324   initcall void registerSumTwoShorts(void);
325
326 //In some .C file:
327 /*global*/ CkReduction::reducerType sumTwoShortsType;
328 /*initcall*/ void registerSumTwoShorts(void)
329 \{
330   sumTwoShortsType=CkReduction::addReducer(sumTwoShorts);
331 \}
332
333 //In some member:
334   short data[2]=...;
335   contribute(2*sizeof(short),data,sumTwoShortsType);
336 \end{alltt}
337
338 Note that you cannot call \kw{CkReduction::addReducer}
339 from anywhere but in an \kw{initcall} routine.
340
341