Docs: refer to illinois.edu, not uiuc.edu
[charm.git] / doc / charm++ / advancedarrays.tex
1 The basic array features described previously (creation, messaging,
2 broadcasts, and reductions) are needed in almost every
3 \charmpp{} program.  The more advanced techniques that follow
4 are not universally needed, but represent many useful optimisations.
5
6 \section{Local Access}
7
8 \index{ckLocal for arrays}
9 \label{ckLocal for arrays}
10 Provides direct access to a local array element using the
11 proxy's \kw{ckLocal} method, which returns an ordinary \CC\ pointer
12 to the element if it exists on the local processor; and NULL if
13 the element does not exist or is on another processor.
14
15 \begin{alltt}
16 A1 *a=a1[i].ckLocal();
17 if (a==NULL) //...is remote-- send message
18 else //...is local-- directly use members and methods of a
19 \end{alltt}
20
21 Note that if the element migrates or is deleted, any pointers 
22 obtained with \kw{ckLocal} are no longer valid.  It is best,
23 then, to either avoid \kw{ckLocal} or else call \kw{ckLocal} 
24 each time the element may have migrated; e.g., at the start 
25 of each entry method.
26
27 An example of this usage is available
28 in \examplerefdir{topology/matmul3d}.
29
30 \section{Advanced Array Creation}
31 \label{advanced array create}
32
33 There are several ways to control the array creation process.
34 You can adjust the map and bindings before creation, change
35 the way the initial array elements are created, create elements
36 explicitly during the computation, and create elements implicitly,
37 ``on demand''.  
38
39 You can create all your elements using any one of these methods,
40 or create different elements using different methods.  
41 An array element has the same syntax and semantics no matter
42 how it was created.  
43
44
45
46 \subsection{Configuring Array Characteristics Using CkArrayOptions}
47 \index{CkArrayOptions}
48 \label{CkArrayOptions}
49
50 The array creation method \kw{ckNew} actually takes a parameter
51 of type \kw{CkArrayOptions}.  This object describes several
52 optional attributes of the new array.
53
54 The most common form of \kw{CkArrayOptions} is to set the number
55 of initial array elements.  A \kw{CkArrayOptions} object will be 
56 constructed automatically in this special common case.  Thus
57 the following code segments all do exactly the same thing:
58
59 \begin{alltt}
60 //Implicit CkArrayOptions
61   a1=CProxy_A1::ckNew(\uw{parameters},nElements);
62
63 //Explicit CkArrayOptions
64   a1=CProxy_A1::ckNew(\uw{parameters},CkArrayOptions(nElements));
65
66 //Separate CkArrayOptions
67   CkArrayOptions opts(nElements);
68   a1=CProxy_A1::ckNew(\uw{parameters},opts);
69 \end{alltt}
70
71
72 Note that the ``numElements'' in an array element is simply the
73 numElements passed in when the array was created.  The true number of
74 array elements may grow or shrink during the course of the
75 computation, so numElements can become out of date.  This ``bulk''
76 constructor approach should be preferred where possible, especially
77 for large arrays.  Bulk construction is handled via a broadcast which
78 will be significantly more efficient in the number of messages
79 required than inserting each element individually, which will require
80 one message send per element.
81
82 Examples of bulk construction are commonplace, see
83 \examplerefdir{jacobi3d-sdag}
84 for a demonstration of the slightly more complicated case of
85 multidimensional chare array bulk construction.
86
87 \kw{CkArrayOptions} contains a few flags that the runtime can use to
88 optimize handling of a given array. If the array elements will only
89 migrate at controlled points (such as periodic load balancing with
90 {\tt AtASync()}), this is signalled to the runtime by calling {\tt
91   opts.setAnytimeMigration(false)}\footnote{At present, this optimizes
92 broadcasts to not save old messages for immigrating chares.}. If all
93 array elements will be inserted by bulk creation or by {\tt
94   fooArray[x].insert()} calls, signal this by calling {\tt
95   opts.setStaticInsertion(true)} \footnote{This can enable a slightly
96   faster default mapping scheme.}.
97
98 \subsection{Initial Placement Using Map Objects}
99 \index{array map}
100 \label{array map}
101
102 You can use \kw{CkArrayOptions} to specify a ``map object'' for an
103 array.  The map object is used by the array manager to determine the
104 ``home'' PE of each element.  The home PE is the PE upon which it is
105 initially placed, which will retain responsibility for maintaining the
106 location of the element.
107
108 There is a default map object, which maps 1D array indices
109 in a block fashion to processors, and maps other array
110 indices based on a hash function. Some other mappings such as round-robin
111 (\kw{RRMap}) also exist, which can be used
112 similar to custom ones described below.
113
114 A custom map object is implemented as a group which inherits from
115 \kw{CkArrayMap} and defines these virtual methods:
116
117 \begin{alltt}
118 class CkArrayMap : public Group
119 \{
120 public:
121   //...
122   
123   //Return an ``arrayHdl'', given some information about the array
124   virtual int registerArray(CkArrayIndex& numElements,CkArrayID aid);
125   //Return the home processor number for this element of this array
126   virtual int procNum(int arrayHdl,const CkArrayIndex &element);
127 \}
128 \end{alltt}
129
130 For example, a simple 1D blockmapping scheme.  Actual mapping is
131 handled in the procNum function.
132
133 \begin{alltt}
134 class BlockMap : public CkArrayMap 
135 \{
136  public:
137   BlockMap(void) \{\}
138   BlockMap(CkMigrateMessage *m)\{\}
139   int registerArray(CkArrayIndex& numElements,CkArrayID aid) \{
140     return 0;
141   \}
142   int procNum(int /*arrayHdl*/,const CkArrayIndex &idx) \{
143     int elem=*(int *)idx.data();
144     int penum =  (elem/(32/CkNumPes()));
145     return penum;
146   \}
147 \};
148
149 \end{alltt}
150 Once you've instantiated a custom map object, you can use it to
151 control the location of a new array's elements using the
152 \kw{setMap} method of the \kw{CkArrayOptions} object described above.
153 For example, if you've declared a map object named ``BlockMap'':
154
155 \begin{alltt}
156 //Create the map group
157   CProxy_BlockMap myMap=CProxy_BlockMap::ckNew();
158 //Make a new array using that map
159   CkArrayOptions opts(nElements);
160   opts.setMap(myMap);
161   a1=CProxy_A1::ckNew(\uw{parameters},opts);
162 \end{alltt}
163
164 An example which contructs one element per physical node may be found in
165 \examplerefdir{PUP/pupDisk}
166
167 Other 3D Torus network oriented map examples are in
168 \examplerefdir{topology}
169
170 \subsection{Initial Elements}
171 \index{array initial}
172 \label{array initial}
173
174 The map object described above can also be used to create
175 the initial set of array elements in a distributed fashion.
176 An array's initial elements are created by its map object,
177 by making a call to \kw{populateInitial} on each processor.
178
179 You can create your own set of elements by creating your
180 own map object and overriding this virtual function of \kw{CkArrayMap}:
181
182 \begin{alltt}
183   virtual void populateInitial(int arrayHdl,int numInitial,
184         void *msg,CkArrMgr *mgr)
185 \end{alltt}
186
187 In this call, \kw{arrayHdl} is the value returned by \kw{registerArray},
188 \kw{numInitial} is the number of elements passed to \kw{CkArrayOptions},
189 \kw{msg} is the constructor message to pass, and \kw{mgr} is the
190 array to create.
191
192 \kw{populateInitial} creates new array elements using the method
193 \kw{void CkArrMgr::insertInitial(CkArrayIndex idx,void *ctorMsg)}.
194 For example, to create one row of 2D array elements on each processor,
195 you would write:
196
197 \begin{alltt}
198 void xyElementMap::populateInitial(int arrayHdl,int numInitial,
199         void *msg,CkArrMgr *mgr)
200 \{
201   if (numInitial==0) return; //No initial elements requested
202         
203   //Create each local element
204   int y=CkMyPe();
205   for (int x=0;x<numInitial;x++) \{
206     mgr->insertInitial(CkArrayIndex2D(x,y),CkCopyMsg(&msg));
207   \}
208   mgr->doneInserting();
209   CkFreeMsg(msg);
210 \}
211 \end{alltt}
212
213 Thus calling \kw{ckNew(10)} on a 3-processor machine would result in
214 30 elements being created.
215
216
217 \subsection{Bound Arrays}
218 \index{bound arrays} \index{bindTo}
219 \label{bound arrays}
220
221 You can ``bind'' a new array to an existing array
222 using the \kw{bindTo} method of \kw{CkArrayOptions}.  Bound arrays
223 act like separate arrays in all ways except for migration--
224 corresponding elements of bound arrays always migrate together.
225 For example, this code creates two arrays A and B which are
226 bound together-- A[i] and B[i] will always be on the same processor.
227
228 \begin{alltt}
229 //Create the first array normally
230   aProxy=CProxy_A::ckNew(\uw{parameters},nElements);
231 //Create the second array bound to the first
232   CkArrayOptions opts(nElements);
233   opts.bindTo(aProxy);
234   bProxy=CProxy_B::ckNew(\uw{parameters},opts);
235 \end{alltt}
236
237 An arbitrary number of arrays can be bound together--
238 in the example above, we could create yet another array
239 C and bind it to A or B.  The result would be the same
240 in either case-- A[i], B[i], and C[i] will always be
241 on the same processor.
242
243 There is no relationship between the types of bound arrays--
244 it is permissible to bind arrays of different types or of the
245 same type.  It is also permissible to have different numbers
246 of elements in the arrays, although elements of A which have
247 no corresponding element in B obey no special semantics.
248 Any method may be used to create the elements of any bound
249 array.
250
251 Bound arrays are often useful if A[i] and B[i] perform different 
252 aspects of the same computation, and thus will run most efficiently 
253 if they lie on the same processor.  Bound array elements are guaranteed
254 to always be able to interact using \kw{ckLocal} (see 
255 section~\ref{ckLocal for arrays}), although the local pointer must
256 be refreshed after any migration. This should be done during the \kw{pup}
257 routine. When migrated, all elements that are bound together will be created
258 at the new processor before \kw{pup} is called on any of them, ensuring that
259 a valid local pointer to any of the bound objects can be obtained during the
260 \kw{pup} routine of any of the others.
261
262 For example, an array {\it Alibrary} is implemented as a library module.
263 It implements a certain functionality by operating on a data array {\it dest}
264 which is just a pointer to some user provided data.
265 A user defined array {\it UserArray} is created and bound to 
266 the array {\it Alibrary} to take advanatage of the functionality provided 
267 by the library.
268 When bound array element migrated, the {\it data} pointer in {\it UserArray}
269 is re-allocated in {\it pup()}, thus {\it UserArray} is responsible to refresh
270 the pointer {\it dest} stored in {\it Alibrary}.
271
272 \begin{alltt}
273 class Alibrary: public CProxy_Alibrary \{
274 public:
275   ...
276   void set_ptr(double *ptr) \{ dest = ptr; \}
277   virtual void pup(PUP::er &p);
278 private:
279   double *dest;           // point to user data in user defined bound array
280 \};
281
282 class UserArray: public CProxy_UserArray \{
283 public:
284   virtual void pup(PUP::er &p) \{
285                 p|len;
286                 if(p.isUnpacking()) \{ 
287                   data = new double[len];
288                   Alibrary *myfellow = AlibraryProxy(thisIndex).ckLocal();
289                   myfellow->set_ptr(data);    // refresh data in bound array
290                 \}
291                 p(data, len);
292   \}
293 private:
294   CProxy_Alibrary  AlibraryProxy;   // proxy to my bound array
295   double *data;          // user allocated data pointer
296   int len;
297 \};
298 \end{alltt}
299
300 A demonstration of bound arrays can be found in
301 \testrefdir{startupTest}
302
303
304 \subsection{Dynamic Insertion}
305 \label{dynamic_insertion}
306
307 In addition to creating initial array elements using ckNew,
308 you can also
309 create array elements during the computation.
310
311 You insert elements into the array by indexing the proxy
312 and calling insert.  The insert call optionally takes 
313 parameters, which are passed to the constructor; and a
314 processor number, where the element will be created.
315 Array elements can be inserted in any order from 
316 any processor at any time.  Array elements need not 
317 be contiguous.
318
319 If using \kw{insert} to create all the elements of the array,
320 you must call \kw{CProxy\_Array::doneInserting} before using
321 the array.
322
323 \begin{alltt}
324 //In the .C file:
325 int x,y,z;
326 CProxy_A1 a1=CProxy_A1::ckNew();  //Creates a new, empty 1D array
327 for (x=...) \{
328    a1[x  ].insert(\uw{parameters});  //Bracket syntax
329    a1(x+1).insert(\uw{parameters});  // or equivalent parenthesis syntax
330 \}
331 a1.doneInserting();
332
333 CProxy_A2 a2=CProxy_A2::ckNew();   //Creates 2D array
334 for (x=...) for (y=...)
335    a2(x,y).insert(\uw{parameters});  //Can't use brackets!
336 a2.doneInserting();
337
338 CProxy_A3 a3=CProxy_A3::ckNew();   //Creates 3D array
339 for (x=...) for (y=...) for (z=...)
340    a3(x,y,z).insert(\uw{parameters});
341 a3.doneInserting();
342
343 CProxy_AF aF=CProxy_AF::ckNew();   //Creates user-defined index array
344 for (...) \{
345    aF[CkArrayIndexFoo(...)].insert(\uw{parameters}); //Use brackets...
346    aF(CkArrayIndexFoo(...)).insert(\uw{parameters}); //  ...or parenthesis
347 \}
348 aF.doneInserting();
349
350 \end{alltt}
351
352 The \kw{doneInserting} call starts the reduction manager (see ``Array
353 Reductions'') and load balancer (see ~\ref{lbFramework})-- since
354 these objects need to know about all the array's elements, they
355 must be started after the initial elements are inserted.
356 You may call \kw{doneInserting} multiple times, but only the first
357 call actually does anything.  You may even \kw{insert} or \kw{destroy}
358 elements after a call to \kw{doneInserting}, with different semantics-- 
359 see the reduction manager and load balancer sections for details.
360
361 If you do not specify one, the system will choose a processor to 
362 create an array element on based on the current map object.
363
364 A demonstration of dynamic insertion is available:
365 \examplerefdir{hello/fancyarray}
366
367 \subsection{Demand Creation}
368
369 Demand Creation is a specialized form of dynamic insertion. Normally, invoking an entry method on a nonexistant array
370 element is an error.  But if you add the attribute
371 \index{createhere} \index{createhome}
372 \kw{[createhere]} or \kw{[createhome]} to an entry method,
373  the array manager will 
374 ``demand create'' a new element to handle the message. 
375
376 With \kw{[createhome]}, the new element
377 will be created on the home processor, which is most efficient when messages for
378 the element may arrive from anywhere in the machine. With \kw{[createhere]},
379 the new element is created on the sending processor, which is most efficient
380 if when messages will often be sent from that same processor.
381
382 The new element is created by calling its default (taking no
383 parameters) constructor, which must exist and be listed in the .ci file.
384 A single array can have a mix of demand-creation and
385 classic entry methods; and demand-created and normally 
386 created elements. 
387
388 A simple example of demand creation
389 \testrefdir{demand\_creation}
390
391 \section{User-defined Array Indices}
392 \label{user-defined array index type}
393 \index{Array index type, user-defined}
394
395 \charmpp{} array indices are arbitrary collections of integers.
396 To define a new array index, you create an ordinary C++ class 
397 which inherits from \kw{CkArrayIndex} and sets the ``nInts'' member
398 to the length, in integers, of the array index.
399
400 For example, if you have a structure or class named ``Foo'', you 
401 can use a \uw{Foo} object as an array index by defining the class:
402
403 \begin{alltt}
404 #include <charm++.h>
405 class CkArrayIndexFoo:public CkArrayIndex \{
406     Foo f;
407 public:
408     CkArrayIndexFoo(const Foo \&in) 
409     \{
410         f=in;
411         nInts=sizeof(f)/sizeof(int);
412     \}
413     //Not required, but convenient: cast-to-foo operators
414     operator Foo &() \{return f;\}
415     operator const Foo &() const \{return f;\}
416 \};
417 \end{alltt}
418
419 Note that \uw{Foo}'s size must be an integral number of integers--
420 you must pad it with zero bytes if this is not the case.
421 Also, \uw{Foo} must be a simple class-- it cannot contain 
422 pointers, have virtual functions, or require a destructor.
423 Finally, there is a \charmpp\ configuration-time option called
424 CK\_ARRAYINDEX\_MAXLEN \index{CK\_ARRAYINDEX\_MAXLEN} 
425 which is the largest allowable number of 
426 integers in an array index.  The default is 3; but you may 
427 override this to any value by passing ``-DCK\_ARRAYINDEX\_MAXLEN=n'' 
428 to the \charmpp\ build script as well as all user code. Larger 
429 values will increase the size of each message.
430
431 You can then declare an array indexed by \uw{Foo} objects with
432
433 \begin{alltt}
434 //in the .ci file:
435 array [Foo] AF \{ entry AF(); ... \}
436
437 //in the .h file:
438 class AF : public CBase\_AF
439 \{ public: AF() \{\} ... \}
440
441 //in the .C file:
442     Foo f;
443     CProxy_AF a=CProxy_AF::ckNew();
444     a[CkArrayIndexFoo(f)].insert();
445     ...
446 \end{alltt}
447
448 Note that since our CkArrayIndexFoo constructor is not declared
449 with the explicit keyword, we can equivalently write the last line as:
450
451 \begin{alltt}
452     a[f].insert();
453 \end{alltt}
454
455 When you implement your array element class, as shown above you 
456 can inherit from \kw{CBase}\_\uw{ClassName}, 
457 a class templated by the index type \uw{Foo}. In the old syntax,
458 you could also inherit directly from \kw{ArrayElementT}.
459 The array index (an object of type \uw{Foo}) is then accessible as 
460 ``thisIndex''. For example:
461
462 \begin{alltt}
463
464 //in the .C file:
465 AF::AF()
466 \{
467     Foo myF=thisIndex;
468     functionTakingFoo(myF);
469 \}
470 \end{alltt}
471
472 A demonstration of user defined indices can be seen in
473 \examplerefdir{hello/fancyarray}
474
475 %\section{Load Balancing Chare Arrays}
476 %see section~\ref{lbFramework}
477