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