Docs: refer to illinois.edu, not uiuc.edu
[charm.git] / doc / charm++ / arrays.tex
1 %\subsection{Chare Arrays}
2 \label{basic arrays}
3
4 Chare arrays\index{chare array}\index{chare arrays}\index{arrays} are
5 arbitrarily-sized, possibly-sparse collections of chares that are distributed
6 across the processors. The entire array has a globally unique identifier of
7 type \kw{CkArrayID}, and each element has a unique index of type
8 \kw{CkArrayIndex}. A \kw{CkArrayIndex} can be a single integer (i.e. a one-dimensional array),
9 several integers (i.e. a multi-dimensional array), or an arbitrary string of
10 bytes (e.g. a binary tree index).
11
12 Array elements can be dynamically created and destroyed on any PE,
13 migrated between PEs, and messages for the elements will still arrive
14 properly. Array elements can be migrated at any time, allowing arrays to be
15 efficiently load balanced. A chare array (or a subset of array elements) can
16 receive a broadcast/multicast or contribute to a reduction.
17
18 An example program can be found here: \examplerefdir{array}.
19
20 \section{Declaring a One-dimensional Array}
21
22 You can declare a one-dimensional (1D) \index{array}\index{chare array}chare
23 array as:
24 %
25 \begin{alltt}
26 //In the .ci file:
27 array [1D] A \{
28   entry A(\uw{parameters1});
29   entry void someEntry(\uw{parameters2});
30 \};
31 \end{alltt}
32 %
33 Array elements extend the system class \kw{CBase}\_\uw{ClassName}, inheriting
34 several fields:
35 %
36 \begin{itemize}
37 \item \kw{thisProxy}: the proxy to the entire chare array that can be indexed
38   to obtain a proxy to a specific array element (e.g. for a 1D chare array
39   \kw{thisProxy[10]}; for a 2D chare array \kw{thisProxy(10, 20)})
40 \item \kw{thisArrayID}: the array's globally unique identifier
41 \item \kw{thisIndex}: the element's array index (an array element can obtain a
42   proxy to itself like this \kw{thisProxy[thisIndex]})
43 \end{itemize}
44 %
45 \zap{As well as chares are allowed to inherit directly from class \kw{Chare},
46   array elements are allowed to inherit from \kw{ArrayElement1D} if 1D array,
47   \kw{ArrayElement2D} if 2D array, and so on up to 6D.}
48 %
49 \begin{alltt}
50 class A : public CBase\_A \{
51   public:
52     A(\uw{parameters1});
53     A(CkMigrateMessage *);
54
55     void someEntry(\uw{parameters2});
56 \};
57 \end{alltt}
58 %
59 Note that \uw{A} must have a \emph{migration constructor}, which is typically
60 empty:
61 %
62 \begin{alltt}
63 //In the .C file:
64 A::A(void)
65 \{
66   //... constructor code ...
67 \}
68
69 A::A(CkMigrateMessage *m) \{ /* the migration constructor */ \}
70
71 A::someEntry(\uw{parameters2})
72 \{
73   // ... code for someEntry ...
74 \}
75 \end{alltt}
76 %
77 See the section~\ref{arraymigratable} on migratable array elements for more
78 information on the migration constructor that takes \kw{CkMigrateMessage *} as
79 the argument.
80
81 \section{Declaring Multi-dimensional Arrays}
82
83 \charmpp{} supports multi-dimensional or user-defined indices. These array types
84 can be declared as:
85 %
86 \begin{alltt}
87 //In the .ci file:
88 array [1D]  ArrayA \{ entry ArrayA(); entry void e(\uw{parameters});\}
89 array [2D]  ArrayB \{ entry ArrayB(); entry void e(\uw{parameters});\}
90 array [3D]  ArrayC \{ entry ArrayC(); entry void e(\uw{parameters});\}
91 array [4D]  ArrayD \{ entry ArrayD(); entry void e(\uw{parameters});\}
92 array [5D]  ArrayE \{ entry ArrayE(); entry void e(\uw{parameters});\}
93 array [6D]  ArrayF \{ entry ArrayF(); entry void e(\uw{parameters});\}
94 array [Foo] ArrayG \{ entry ArrayG(); entry void e(\uw{parameters});\}
95 \end{alltt}
96 %
97 The last declaration expects an array index of type \kw{CkArrayIndex}\uw{Foo},
98 which must be defined before including the \texttt{.decl.h} file (see
99 section~\ref{user-defined array index type} on user-defined array indices for
100 more information).
101 %
102 \begin{alltt}
103 //In the .h file:
104 class ArrayA : public CBase\_ArrayA \{ public: ArrayA()\{\} ...\};
105 class ArrayB : public CBase\_ArrayB \{ public: ArrayB()\{\} ...\};
106 class ArrayC : public CBase\_ArrayC \{ public: ArrayC()\{\} ...\};
107 class ArrayD : public CBase\_ArrayD \{ public: ArrayD()\{\} ...\};
108 class ArrayE : public CBase\_ArrayE \{ public: ArrayE()\{\} ...\};
109 class ArrayF : public CBase\_ArrayF \{ public: ArrayF()\{\} ...\};
110 class ArrayG : public CBase\_ArrayG \{ public: ArrayG()\{\} ...\};
111 \end{alltt}
112 %
113 The fields in \kw{thisIndex} are different depending on the dimensionality of
114 the chare array:
115 %
116 \begin{itemize}
117 \item 1D array: \kw{thisIndex}
118 \item 2D array ($x$,$y$): \kw{thisIndex.x}, \kw{thisIndex.y}
119 \item 3D array ($x$,$y$,$z$): \kw{thisIndex.x}, \kw{thisIndex.y},
120   \kw{thisIndex.z}
121 \item 4D array ($w$,$x$,$y$,$z$): \kw{thisIndex.w}, \kw{thisIndex.x},
122   \kw{thisIndex.y}, \kw{thisIndex.z}
123 \item 5D array ($v$,$w$,$x$,$y$,$z$): \kw{thisIndex.v}, \kw{thisIndex.w},
124   \kw{thisIndex.x}, \kw{thisIndex.y}, \kw{thisIndex.z}
125 \item 6D array ($x_1$,$y_1$,$z_1$,$x_2$,$y_2$,$z_2$): \kw{thisIndex.x1},
126   \kw{thisIndex.y1}, \kw{thisIndex.z1}, \kw{thisIndex.x2}, \kw{thisIndex.y2},
127   \kw{thisIndex.z2}
128 \item Foo array: \kw{thisIndex}
129 \end{itemize}
130
131 \section{Creating an Array}
132 \label{basic array creation}
133
134 An array is created using the \kw{CProxy\_Array::ckNew} routine. This returns a
135 proxy object, which can be kept, copied, or sent in messages. The following
136 creates a 1D \index{array}array containing elements indexed (0, 1, \ldots,
137 \uw{dimX}-1):
138 %
139 \begin{alltt}
140 CProxy_ArrayA a1 = CProxy_ArrayA::ckNew(\uw{parameters}, dimX);
141 \end{alltt}
142 %
143 Likewise, a dense multidimensional array can be created by passing the extents
144 at creation time to \kw{ckNew}.
145 %
146 \begin{alltt}
147 CProxy_ArrayB a2 = CProxy_ArrayB::ckNew(\uw{parameters}, dimX, dimY);
148 CProxy_ArrayC a3 = CProxy_ArrayC::ckNew(\uw{parameters}, dimX, dimY, dimZ);
149 \end{alltt}
150 %
151 For 4D, 5D, 6D and user-defined arrays, this functionality cannot be used.  The
152 array elements must be inserted individually as described in
153 section~\ref{dynamic_insertion}.
154
155 During creation, the constructor is invoked on each array element. For more
156 options when creating the array, see section~\ref{advanced array create}.
157
158 \section{Entry Method Invocation}
159
160 To obtain a proxy to a specific element in chare array, the chare array proxy
161 (e.g. \kw{thisProxy}) must be indexed by the appropriate index call depending
162 on the dimentionality of the array:
163 %
164 \begin{itemize}
165 \item 1D array, to obtain a proxy to element $i$: \kw{thisIndex[$i$]} or
166   \kw{thisIndex($i$)}
167 \item 2D array, to obtain a proxy to element $(i,j)$: \kw{thisIndex($i$,$j$)}
168 \item 3D array, to obtain a proxy to element $(i,j,k)$: \kw{thisIndex($i$,$j$,$k$)}
169 \item 4D array, to obtain a proxy to element $(i,j,k,l)$:
170   \kw{thisIndex($i$,$j$,$k$,$l$)}
171 \item 5D array, to obtain a proxy to element $(i,j,k,l,m)$:
172   \kw{thisIndex($i$,$j$,$k$,$l$,$m$)}
173 \item 6D array, to obtain a proxy to element $(i,j,k,l,m,n)$:
174   \kw{thisIndex($i$,$j$,$k$,$l$,$m$,$n$)}
175 \item User-defined array, to obtain a proxy to element $i$: \kw{thisIndex[$i$]}
176   or \kw{thisIndex($i$)}
177 \end{itemize}
178 %
179 To send a \index{Array message} message to an array element, index the proxy
180 and call the method name:
181 %
182 \begin{alltt}
183 a1[i].doSomething(\uw{parameters});
184 a3(x,y,z).doAnother(\uw{parameters});
185 aF[CkArrayIndexFoo(...)].doAgain(\uw{parameters});
186 \end{alltt}
187
188 You may invoke methods on array elements that have not yet been created. The
189 \charmpp{} runtime system will buffer the message until the element is
190 created. 
191 %\footnote{However, the element must eventually be created (i.e. within
192 %a 3-minute buffering period).}
193 \footnote{However, the element must eventually be created.}
194
195 Messages are not guarenteed to be delivered in order. For instance, if a method
196 is invoked on method \kw{A} and then method \kw{B}; it is possible that \kw{B}
197 is executed before \kw{A}.
198 %
199 \begin{alltt}
200 a1[i].A();
201 a1[i].B();
202 \end{alltt}
203
204 Messages sent to migrating elements will be delivered after the migrating
205 element arrives on the destination PE. It is an error to send a message
206 to a deleted array element.
207
208 \section{Broadcasts on Chare Arrays}
209
210 To \index{array broadcast} broadcast a message to all the current elements of
211 an array, simply omit the index (invoke an entry method on the chare array
212 proxy):
213 %
214 \begin{alltt}
215 a1.doIt(\uw{parameters}); //<- invokes doIt on each array element
216 \end{alltt}
217 %
218 The broadcast message will be delivered to every existing array element exactly
219 once. Broadcasts work properly even with ongoing migrations, insertions, and
220 deletions.
221
222 \section{Reductions on Chare Arrays}
223 \label{reductions}
224
225 A \index{array reduction}reduction applies a single operation (e.g. add,
226 max, min, ...) to data items scattered across many processors and
227 collects the result in one place.  \charmpp{} supports reductions
228 over the members of an array or group.
229
230 The data to be reduced comes from a call to the member \kw{contribute} 
231 method:
232 \begin{alltt}
233 void contribute(int nBytes, const void *data, CkReduction::reducerType type);
234 \end{alltt}
235
236 This call contributes \kw{nBytes} bytes starting at \kw{data} to the
237 reduction \kw{type} (see Section~\ref{builtin_reduction}).  Unlike sending a
238 message, you may use \kw{data} after the call to \kw{contribute}.  All
239 members of the chare array or group must call \kw{contribute}, 
240 and all of them must use the same reduction type.  
241
242
243 For example, if we want to sum each array/group member's single integer myInt, 
244 we would use:
245
246 \begin{alltt}
247     // Inside any member method
248     int myInt=get_myInt();
249     contribute(sizeof(int),\&myInt,CkReduction::sum_int);
250 \end{alltt}
251
252 The built-in reduction types (see below) can also handle arrays of
253 numbers.  For example, if each element of a chare array has a pair of
254 doubles \uw{forces}[2], the corresponding elements of which are to be added across
255 all elements, from each element call:
256
257 \begin{alltt}
258     double forces[2]=get_my_forces();
259     contribute(2*sizeof(double),forces,CkReduction::sum_double);
260 \end{alltt}
261
262 This will result in a {\tt double} array of 2 elements, the first of which
263 contains the sum of all \uw{forces}[0] values, with the second element 
264 holding the sum of all \uw{forces}[1] values of the chare array elements.
265
266 Note that since C++ arrays (like \uw{forces}[2]) are already pointers, we 
267 don't use \&\uw{forces}.
268
269
270 Typically the client entry method of a reduction takes a single argument of
271 type CkReductionMsg (see Section~\ref{reductionClients}). However, by giving an entry method the
272 \kw{reductiontarget} attribute in the {\tt .ci} file, you can instead use entry methods that take
273 arguments of the same type as specified by the {\em contribute} call.  
274 When creating a callback to the
275 reduction target, the entry method index is generated by 
276 {\tt CkReductionTarget(ChareClass, method\_name)} 
277 instead of {\tt CkIndex\_ChareClass::method\_name(...)}.
278 For example,
279 the code for a typed reduction that yields an {\tt int}, would look like this:
280
281 \begin{alltt}
282   // In the .ci file...
283   entry [reductiontarget] void done(int result);
284
285   // In some .cc file: 
286   // Create a callback that invokes the typed reduction client
287   // driverProxy is a proxy to the chare object on which 
288   // the reduction target method {\em done} is called upon completion 
289   // of the reduction
290   CkCallback cb(CkReductionTarget(Driver, done), driverProxy);
291
292   // Contribution to the reduction...
293   contribute(sizeof(int), &intData, CkReduction::sum_int, cb);
294
295   // Definition of the reduction client...
296   void Driver::done(int result) 
297   \{
298     CkPrintf("Reduction value: \%d", result);
299   \}
300 \end{alltt}
301
302 This will also work for arrays of data 
303 elements({\tt entry [reductiontarget] void done(int n, int result[n])}), 
304 and for any user-defined type with a PUP method
305 (see ~\ref{sec:pup}). If you know that the reduction will yield a particular
306 number of elements, say 3 {\tt int}s, you can also specify a reduction target which
307 takes 3 {\tt int}s and it will be invoked correctly. 
308
309 Reductions do not have to specify commutative-associative operations on data;
310 they can also be used to signal the fact that all array/group members
311 have reached a certain synchronization point. In this case, a simpler version
312 of contribute may be used:
313
314 %Sometimes it is not important the data to be reduced, but only the fact that all
315 %elements have reached a synchronization point. In this case a simpler version of
316 %contribute can be used:
317
318 \begin{alltt}
319     contribute();
320 \end{alltt}
321
322 In all cases, the result of the reduction operation is passed to the {\em reduction
323 client}.  Many different kinds of reduction clients can be used, as
324 explained in Section~\ref{reductionClients}.
325
326 Please refer to \examplerefdir{typed\_reduction} for a working example of
327 reductions in Charm++.
328
329 Note that the reduction will complete properly even if chare array elements are {\em migrated}
330 or {\em deleted} during the reduction. Additionally, when you create a new chare array element, 
331 it is expected to contribute to the next reduction not already in progress on that
332 processor. 
333
334 \subsection{Built-in Reduction Types}
335 \label{builtin_reduction}
336
337 \charmpp{} includes several built-in reduction types, used to combine 
338 individual contributions.  Any of them may be passed as an argument of type
339 \kw{CkReduction::reducerType} to \kw{contribute}.
340
341 The first four operations ({\tt sum}, {\tt product}, {\tt max}, and {\tt min}) work on {\tt int},
342 {\tt float}, or {\tt double} data as indicated by the suffix.  The logical
343 reductions ({\tt and}, {\tt or}) only work on integer data.  All the built-in
344 reductions work on either single numbers (pass a pointer) or arrays-- just
345 pass the correct number of bytes to \kw{contribute}.
346
347 \begin{enumerate}
348
349 \item \kw{CkReduction::nop}-- no operation performed.
350
351 \item \kw{CkReduction::sum\_int}, \kw{sum\_float}, \kw{sum\_double}-- the
352 result will be the sum of the given numbers.
353
354 \item \kw{CkReduction::product\_int}, \kw{product\_float},
355 \kw{product\_double}-- the result will be the product of the given numbers.
356
357 \item \kw{CkReduction::max\_int}, \kw{max\_float}, \kw{max\_double}-- the
358 result will be the largest of the given numbers.
359
360 \item \kw{CkReduction::min\_int}, \kw{min\_float}, \kw{min\_double}-- the
361 result will be the smallest of the given numbers.
362
363 \item \kw{CkReduction::logical\_and}-- the result will be the logical AND of the given
364 integers.  0 is false, nonzero is true.
365
366 \item \kw{CkReduction::logical\_or}-- the result will be the logical OR of the given
367 integers.
368
369 \item \kw{CkReduction::bitvec\_and}-- the result will be the bitvector AND of the given numbers (represented as integers).
370
371 \item \kw{CkReduction::bitvec\_or}-- the result will be the bitvector OR of the given numbers (represented as integers).
372
373 \item \kw{CkReduction::set}-- the result will be a verbatim concatenation of
374 all the contributed data, separated into \kw{CkReduction::setElement} records.
375 The data contributed can be of any length, and can vary across array elements
376 or reductions.  To extract the data from each element, see the description
377 below.
378
379 \item \kw{CkReduction::concat}-- the result will be a byte-by-byte
380 concatentation of all the contributed data.  The contributed elements
381 are not delimiter-separated. 
382
383 \end{enumerate}
384
385
386 \kw{CkReduction::set} returns a collection of \kw{CkReduction::setElement}
387 objects, one per contribution.  This class has the definition:
388
389 \begin{alltt}
390 class CkReduction::setElement 
391 \{
392 public:
393   int dataSize;//The length of the data array below
394   char data[];//The (dataSize-long) array of data
395   CkReduction::setElement *next(void);
396 \};
397 \end{alltt}
398
399 To extract the contribution of each array element from a reduction set, use the
400 \uw{next} routine repeatedly:
401
402 \begin{alltt}
403   //Inside a reduction handler-- 
404   //  data is our reduced data from CkReduction_set
405   CkReduction::setElement *cur=(CkReduction::setElement *)data;
406   while (cur!=NULL)
407   \{
408     ... //Use cur->dataSize and cur->data
409     //Now advance to the next element's contribution
410     cur=cur->next();
411   \}
412 \end{alltt}
413
414 The reduction set order is undefined.  You should add a source field to the
415 contributed elements if you need to know which array element gave a particular
416 contribution.  Additionally, if the contributed elements are of a complex 
417 data type, you will likely have to supply code for 
418 %serialize/unserialize operation on your element structure if your
419 %reduction element data is complex.  
420 serializing/deserializing them.
421 Consider using the \kw{PUP}
422 interface see ~\ref{sec:pup} to simplify your object serialization
423 needs.
424
425 If the outcome of your reduction is dependent on the order in which 
426 data elements are processed, or if your data is just too
427 heterogenous to be handled elegantly by the predefined types and you
428 don't want to undertake multiple reductions, it may be best to define
429 your own reduction type.  See the next section
430 (Section~\ref{new_type_reduction}) for details.
431
432 \section{Destroying Array Elements}
433
434 To destroy an array element -- detach it from the array,
435 call its destructor, and release its memory--invoke its 
436 \kw{Array destroy} method, as:
437
438 \begin{alltt}
439 a1[i].ckDestroy();
440 \end{alltt}
441
442 Note that this method can also be invoked remotely i.e. from 
443 a process different from the one on which the array element resides.
444 You must ensure that no messages are sent to a deleted element. 
445 After destroying an element, you may insert a new element at
446 its index.