Docs: Update to reflect additions to CkArrayOptions
[charm.git] / doc / charm++ / arrays.tex
1 \subsection{Basic Arrays}
2
3 \label{basic arrays}
4
5 Arrays \index{arrays} are arbitrarily-sized collections of chares.  The
6 entire array has a globally unique identifier of type \kw{CkArrayID}, and
7 each element has a unique index of type \kw{CkArrayIndex}.  A \kw{CkArrayIndex}
8 can be a single integer (i.e. 1D array), several integers (i.e. a
9 multidimensional array), or an arbitrary string of bytes (e.g. a binary tree
10 index).
11
12 Array elements can be dynamically created and destroyed on any processor,
13 and messages for the elements will still arrive properly.
14 Array elements can be migrated at any time, allowing arrays to be efficiently
15 load balanced.  Array elements can also receive array broadcasts and
16 contribute to array reductions.
17
18 \subsubsection{Declaring a 1D Array}
19
20 You can declare a one-dimensional \index{array}\index{chare array}chare array
21 as:
22
23 \begin{alltt}
24 //In the .ci file:
25 array [1D] A \{
26   entry A(\uw{parameters1});
27   entry void someEntry(\uw{parameters2});
28 \};
29 \end{alltt}
30
31 Just as every Chare inherits from the system class \kw{CBase}\_\uw{ClassName}, every 
32 array element inherits from the system class \kw{CBase}\_\uw{ClassName}.
33 Just as a Chare inherits ``thishandle'', each
34 array element inherits ``thisArrayID'', the \kw{CkArrayID} of its array,
35 and ``thisIndex'', the element's array index.
36 As well as chares are allowed to inherit directly from class \kw{Chare},
37 array elements are allowed to inherit from \kw{ArrayElement1D} if 1D array,
38 \kw{ArrayElement2D} if 2D array, and so on up to 6D.
39
40 \begin{alltt}
41 class A : public CBase\_A \{
42   public:
43     A(\uw{parameters1});
44     A(CkMigrateMessage *);
45
46     void someEntry(\uw{parameters2});
47 \};
48 \end{alltt}
49
50 Note \uw{A}'s odd migration constructor, which is normally empty:
51
52 \begin{alltt}
53 //In the .C file:
54 A::A(void)
55 \{
56   //...your constructor code...
57 \}
58 A::A(CkMigrateMessage *m) \{ \}
59 \end{alltt}
60
61 Read the section ``Migratable Array Elements'' for more
62 information on the \kw{CkMigrateMessage} constructor. 
63
64
65 \subsubsection{Creating a Simple Array}
66
67 \label{basic array creation}
68
69 You always create an array using the \kw{CProxy\_Array::ckNew}
70 routine.  This returns a proxy object, which can
71 be kept, copied, or sent in messages.
72 To create a 1D \index{array}array containing elements indexed 
73 (0, 1, ..., \uw{num\_elements}-1), use:
74
75 \begin{alltt}
76 CProxy_A1 a1 = CProxy_A1::ckNew(\uw{parameters},num_elements);
77 \end{alltt}
78
79 The constructor is invoked on each array element.
80 For creating higher-dimensional arrays, or for more options
81 when creating the array, see section~\ref{advanced array create}.
82
83
84 \subsubsection{Messages}
85
86 An array proxy responds to the appropriate index call--
87 for 1D arrays, use [i] or (i); for 2D use (x,y); for 3D
88 use (x,y,z); and for user-defined types use [f] or (f).
89
90 To send a \index{Array message} message to an array element, index the proxy 
91 and call the method name:
92
93 \begin{alltt}
94 a1[i].doSomething(\uw{parameters});
95 a3(x,y,z).doAnother(\uw{parameters});
96 aF[CkArrayIndexFoo(...)].doAgain(\uw{parameters});
97 \end{alltt}
98
99 You may invoke methods on array elements that have not yet
100 been created-- by default, the system will buffer the message until the
101 element is created\footnote{However, the element must eventually be 
102 created-- i.e., within a 3-minute buffering period.}.
103
104 Messages are not guarenteed to be delivered in order.
105 For example, if I invoke a method A, then method B;
106 it is possible for B to be executed before A.
107
108 \begin{alltt}
109 a1[i].A();
110 a1[i].B();
111 \end{alltt}
112
113 Messages sent to migrating elements will be delivered after
114 the migrating element arrives.  It is an error to send 
115 a message to a deleted array element.
116
117
118 \subsubsection{Broadcasts}
119
120 To \index{Array broadcast} broadcast a message to all the current elements of an array, 
121 simply omit the index, as:
122
123 \begin{alltt}
124 a1.doIt(\uw{parameters}); //<- invokes doIt on each array element
125 \end{alltt}
126
127 The broadcast message will be delivered to every existing array 
128 element exactly once.  Broadcasts work properly even with ongoing
129 migrations, insertions, and deletions.
130
131
132 \subsubsection{Reductions on Chare Arrays}
133
134 A \index{array reduction}reduction applies a single operation (e.g. add,
135 max, min, ...) to data items scattered across many processors and
136 collects the result in one place.  \charmpp{} supports reductions on the
137 elements of a Chare array.
138
139 The data to be reduced comes from each array element, 
140 which must call the \kw{contribute} method:
141
142 \begin{alltt}
143 ArrayElement::contribute(int nBytes,const void *data,CkReduction::reducerType type);
144 \end{alltt}
145
146 Reductions are described in more detail in Section~\ref{reductions}.
147
148
149 \subsubsection{Destroying Arrays}
150
151 To destroy an array element-- detach it from the array,
152 call its destructor, and release its memory--invoke its 
153 \kw{Array destroy} method, as:
154
155 \begin{alltt}
156 a1[i].ckDestroy();
157 \end{alltt}
158
159 You must ensure that no messages are sent to a deleted element. 
160 After destroying an element, you may insert a new element at
161 its index.
162
163
164
165
166 \subsection{Advanced Arrays}
167
168 \label{advanced arrays}
169
170 The basic array features described above (creation, messaging,
171 broadcasts, and reductions) are needed in almost every
172 \charmpp{} program.  The more advanced techniques that follow
173 are not universally needed; but are still often useful.
174
175
176 \subsubsection{Declaring Multidimensional, or User-defined Index Arrays}
177
178 \charmpp{} contains direct support for multidimensional and
179 even user-defined index arrays.  These arrays can be declared as:
180
181 \begin{alltt}
182 //In the .ci file:
183 message MyMsg;
184 array [1D] A1 \{ entry A1(); entry void e(\uw{parameters});\}
185 array [2D] A2 \{ entry A2(); entry void e(\uw{parameters});\}
186 array [3D] A3 \{ entry A3(); entry void e(\uw{parameters});\}
187 array [4D] A4 \{ entry A4(); entry void e(\uw{parameters});\}
188 array [5D] A5 \{ entry A5(); entry void e(\uw{parameters});\}
189 array [6D] A6 \{ entry A6(); entry void e(\uw{parameters});\}
190 array [Foo] AF \{ entry AF(); entry void e(\uw{parameters});\}
191 \end{alltt}
192
193 The last declaration expects an array index of type \kw{CkArrayIndex}\uw{Foo},
194 which must be defined before including the \texttt{.decl.h} file 
195 (see ``User-defined array index type'' below).  
196
197 \begin{alltt}
198 //In the .h file:
199 class A1 : public CBase\_A1 \{ public: A1()\{\} ...\};
200 class A2 : public CBase\_A2 \{ public: A2()\{\} ...\};
201 class A3 : public CBase\_A3 \{ public: A3()\{\} ...\};
202 class A4 : public CBase\_A4 \{ public: A4()\{\} ...\};
203 class A5 : public CBase\_A5 \{ public: A5()\{\} ...\};
204 class A6 : public CBase\_A6 \{ public: A6()\{\} ...\};
205 class AF : public CBase\_AF \{ public: AF()\{\} ...\};
206 \end{alltt}
207
208 A 1D array element can access its index via its inherited ``thisIndex''
209 field; a 2D via ``thisIndex.x'' and ``thisIndex.y'', and a 3D via
210 ``thisIndex.x'', ``thisIndex.y'', and ``thisIndex.z''. The subfields
211 of 4D, 5D, and 6D are respectively \{w,x,y,z\}, \{v,w,x,y,z\}, and 
212 \{x1,y1,z1,x2,y2,z2\}.
213 A user-defined index array can access its index as ``thisIndex''.
214
215
216 Likewise, you can create a dense multidimensional array by passing the 
217 extents at creation time to \kw{ckNew}.
218
219 \begin{alltt}
220 CProxy_A1 a1 = CProxy_A1::ckNew(parameters, num_elements);
221 CProxy_A2 a2 = CProxy_A2::ckNew(parameters, num_rows, num_colums);
222 CProxy_A3 a3 = CProxy_A3::ckNew(parameters, num_rows, num_columns, num_depth);
223 \end{alltt}
224
225 For 4D, 5D, 6D and user-defined arrays, this functionality cannot be used. 
226 You need to insert the array elements individually (Section~\ref{dynamic_insertion}).
227
228 \subsubsection{Advanced Array Creation}
229
230 \label{advanced array create}
231 There are several ways to control the array creation process.
232 You can adjust the map and bindings before creation, change
233 the way the initial array elements are created, create elements
234 explicitly during the computation, and create elements implicitly,
235 ``on demand''.  
236
237 You can create all your elements using any one of these methods,
238 or create different elements using different methods.  
239 An array element has the same syntax and semantics no matter
240 how it was created.
241
242
243 \subsubsection{Advanced Array Creation: CkArrayOptions}
244
245 \index{CkArrayOptions}
246 \label{CkArrayOptions}
247
248 The array creation method \kw{ckNew} actually takes a parameter
249 of type \kw{CkArrayOptions}.  This object describes several
250 optional attributes of the new array.
251
252 The most common form of \kw{CkArrayOptions} is to set the number
253 of initial array elements.  A \kw{CkArrayOptions} object will be 
254 constructed automatically in this special common case.  Thus
255 the following code segments all do exactly the same thing:
256
257 \begin{alltt}
258 //Implicit CkArrayOptions
259   a1=CProxy_A1::ckNew(\uw{parameters},nElements);
260
261 //Explicit CkArrayOptions
262   a1=CProxy_A1::ckNew(\uw{parameters},CkArrayOptions(nElements));
263
264 //Separate CkArrayOptions
265   CkArrayOptions opts(nElements);
266   a1=CProxy_A1::ckNew(\uw{parameters},opts);
267 \end{alltt}
268
269 Note that the ``numElements'' in an array element is simply the
270 numElements passed in when the array was created.  The true number of
271 array elements may grow or shrink during the course of the
272 computation, so numElements can become out of date.  This ``bulk''
273 constructor approach should be preferred where possible, especially
274 for large arrays.  Bulk construction is handled via a broadcast which
275 will be significantly more efficient in the number of messages
276 required than inserting each element individually which will require
277 one message send per element.
278
279 \kw{CkArrayOptions} contains a few flags that the runtime can use to
280 optimize handling of a given array. If the array elements will only
281 migrate at controlled points (such as periodic load balancing with
282 {\tt AtASync()}), this is signalled to the runtime by calling {\tt
283   opts.setAnytimeMigration(false)}\footnote{At present, this optimizes
284 broadcasts to not save old messages for immigrating chares.}. If all
285 array elements will be inserted by bulk creation or by {\tt
286   fooArray[x].insert()} calls, signal this by calling {\tt
287   opts.setStaticInsertion(true)} \footnote{This can enable a slightly
288   faster default mapping scheme.}.
289
290 \subsubsection{Advanced Array Creation: Map Object}
291
292 \index{array map}
293 \label{array map}
294
295 You can use \kw{CkArrayOptions} to specify a ``map object''
296 for an array.  The map object is used by the array manager
297 to determine the ``home'' processor of each element.  The
298 home processor is the processor responsible for maintaining
299 the location of the element.
300
301 There is a default map object, which maps 1D array indices
302 in a round-robin fashion to processors, and maps other array
303 indices based on a hash function.
304
305 A custom map object is implemented as a group which inherits from
306 \kw{CkArrayMap} and defines these virtual methods:
307
308 \begin{alltt}
309 class CkArrayMap : public Group
310 \{
311 public:
312   //...
313   
314   //Return an ``arrayHdl'', given some information about the array
315   virtual int registerArray(CkArrayIndexMax& numElements,CkArrayID aid);
316   //Return the home processor number for this element of this array
317   virtual int procNum(int arrayHdl,const CkArrayIndex &element);
318 \}
319 \end{alltt}
320
321 For example, a simple 1D blockmapping scheme.  Actual mapping is
322 handled in the procNum function.
323
324 \begin{alltt}
325 class BlockMap : public CkArrayMap 
326 \{
327  public:
328   BlockMap(void) \{\}
329   BlockMap(CkMigrateMessage *m)\{\}
330   int registerArray(CkArrayIndexMax& numElements,CkArrayID aid) \{
331     return 0;
332   \}
333   int procNum(int /*arrayHdl*/,const CkArrayIndex &idx) \{
334     int elem=*(int *)idx.data();
335     int penum =  (elem/(32/CkNumPes()));
336     return penum;
337   \}
338 \};
339
340 \end{alltt}
341 Once you've instantiated a custom map object, you can use it to
342 control the location of a new array's elements using the
343 \kw{setMap} method of the \kw{CkArrayOptions} object described above.
344 For example, if you've declared a map object named ``blockMap'':
345
346 \begin{alltt}
347 //Create the map group
348   CProxy_blockMap myMap=CProxy_blockMap::ckNew();
349 //Make a new array using that map
350   CkArrayOptions opts(nElements);
351   opts.setMap(myMap);
352   a1=CProxy_A1::ckNew(\uw{parameters},opts);
353 \end{alltt}
354
355
356
357 \subsubsection{Advanced Array Creation: Initial Elements}
358
359 \index{array initial}
360 \label{array initial}
361
362 The map object described above can also be used to create
363 the initial set of array elements in a distributed fashion.
364 An array's initial elements are created by its map object,
365 by making a call to \kw{populateInitial} on each processor.
366
367 You can create your own set of elements by creating your
368 own map object and overriding this virtual function of \kw{CkArrayMap}:
369
370 \begin{alltt}
371   virtual void populateInitial(int arrayHdl,int numInitial,
372         void *msg,CkArrMgr *mgr)
373 \end{alltt}
374
375 In this call, \kw{arrayHdl} is the value returned by \kw{registerArray},
376 \kw{numInitial} is the number of elements passed to \kw{CkArrayOptions},
377 \kw{msg} is the constructor message to pass, and \kw{mgr} is the
378 array to create.
379
380 \kw{populateInitial} creates new array elements using the method
381 \kw{void CkArrMgr::insertInitial(CkArrayIndex idx,void *ctorMsg)}.
382 For example, to create one row of 2D array elements on each processor,
383 you would write:
384
385 \begin{alltt}
386 void xyElementMap::populateInitial(int arrayHdl,int numInitial,
387         void *msg,CkArrMgr *mgr)
388 \{
389   if (numInitial==0) return; //No initial elements requested
390         
391   //Create each local element
392   int y=CkMyPe();
393   for (int x=0;x<numInitial;x++) \{
394     mgr->insertInitial(CkArrayIndex2D(x,y),CkCopyMsg(&msg));
395   \}
396   mgr->doneInserting();
397   CkFreeMsg(msg);
398 \}
399 \end{alltt}
400
401 Thus calling \kw{ckNew(10)} on a 3-processor machine would result in
402 30 elements being created.
403
404
405 \subsubsection{Advanced Array Creation: Bound Arrays}
406
407 \experimental{}
408 \index{bound arrays} \index{bindTo}
409 \label{bound arrays}
410 You can ``bind'' a new array to an existing array
411 using the \kw{bindTo} method of \kw{CkArrayOptions}.  Bound arrays
412 act like separate arrays in all ways except for migration--
413 corresponding elements of bound arrays always migrate together.
414 For example, this code creates two arrays A and B which are
415 bound together-- A[i] and B[i] will always be on the same processor.
416
417 \begin{alltt}
418 //Create the first array normally
419   aProxy=CProxy_A::ckNew(\uw{parameters},nElements);
420 //Create the second array bound to the first
421   CkArrayOptions opts(nElements);
422   opts.bindTo(aProxy);
423   bProxy=CProxy_B::ckNew(\uw{parameters},opts);
424 \end{alltt}
425
426 An arbitrary number of arrays can be bound together--
427 in the example above, we could create yet another array
428 C and bind it to A or B.  The result would be the same
429 in either case-- A[i], B[i], and C[i] will always be
430 on the same processor.
431
432 There is no relationship between the types of bound arrays--
433 it is permissible to bind arrays of different types or of the
434 same type.  It is also permissible to have different numbers
435 of elements in the arrays, although elements of A which have
436 no corresponding element in B obey no special semantics.
437 Any method may be used to create the elements of any bound
438 array.
439
440 Bound arrays are often useful if A[i] and B[i] perform different 
441 aspects of the same computation, and thus will run most efficiently 
442 if they lie on the same processor.  Bound array elements are guaranteed
443 to always be able to interact using \kw{ckLocal} (see 
444 section~\ref{ckLocal for arrays}), although the local pointer must
445 be refreshed after any migration. This should be done during the \kw{pup}
446 routine. When migrated, all elements that are bound together will be created
447 at the new processor before \kw{pup} is called on any of them, ensuring that
448 a valid local pointer to any of the bound objects can be obtained during the
449 \kw{pup} routine of any of the others.
450
451 For example, an array {\it Alibrary} is implemented as a library module.
452 It implements a certain functionality by operating on a data array {\it dest}
453 which is just a pointer to some user provided data.
454 A user defined array {\it UserArray} is created and bound to 
455 the array {\it Alibrary} to take advanatage of the functionality provided 
456 by the library.
457 When bound array element migrated, the {\it data} pointer in {\it UserArray}
458 is re-allocated in {\it pup()}, thus {\it UserArray} is responsible to refresh
459 the pointer {\it dest} stored in {\it Alibrary}.
460
461 \begin{alltt}
462 class Alibrary: public CProxy_Alibrary \{
463 public:
464   ...
465   void set_ptr(double *ptr) \{ dest = ptr; \}
466   virtual void pup(PUP::er &p);
467 private:
468   double *dest;           // point to user data in user defined bound array
469 \};
470
471 class UserArray: public CProxy_UserArray \{
472 public:
473   virtual void pup(PUP::er &p) \{
474                 p|len;
475                 if(p.isUnpacking()) \{ 
476                   data = new double[len];
477                   Alibrary *myfellow = AlibraryProxy(thisIndex).ckLocal();
478                   myfellow->set_ptr(data);    // refresh data in bound array
479                 \}
480                 p(data, len);
481   \}
482 private:
483   CProxy_Alibrary  AlibraryProxy;   // proxy to my bound array
484   double *data;          // user allocated data pointer
485   int len;
486 \};
487 \end{alltt}
488
489
490 \subsubsection{Advanced Array Creation: Dynamic Insertion}
491
492 \label{dynamic_insertion}
493
494 In addition to creating initial array elements using ckNew,
495 you can also
496 create array elements during the computation.
497
498 You insert elements into the array by indexing the proxy
499 and calling insert.  The insert call optionally takes 
500 parameters, which are passed to the constructor; and a
501 processor number, where the element will be created.
502 Array elements can be inserted in any order from 
503 any processor at any time.  Array elements need not 
504 be contiguous.
505
506 If using \kw{insert} to create all the elements of the array,
507 you must call \kw{CProxy\_Array::doneInserting} before using
508 the array.
509
510 \begin{alltt}
511 //In the .C file:
512 int x,y,z;
513 CProxy_A1 a1=CProxy_A1::ckNew();  //Creates a new, empty 1D array
514 for (x=...) \{
515    a1[x  ].insert(\uw{parameters});  //Bracket syntax
516    a1(x+1).insert(\uw{parameters});  // or equivalent parenthesis syntax
517 \}
518 a1.doneInserting();
519
520 CProxy_A2 a2=CProxy_A2::ckNew();   //Creates 2D array
521 for (x=...) for (y=...)
522    a2(x,y).insert(\uw{parameters});  //Can't use brackets!
523 a2.doneInserting();
524
525 CProxy_A3 a3=CProxy_A3::ckNew();   //Creates 3D array
526 for (x=...) for (y=...) for (z=...)
527    a3(x,y,z).insert(\uw{parameters});
528 a3.doneInserting();
529
530 CProxy_AF aF=CProxy_AF::ckNew();   //Creates user-defined index array
531 for (...) \{
532    aF[CkArrayIndexFoo(...)].insert(\uw{parameters}); //Use brackets...
533    aF(CkArrayIndexFoo(...)).insert(\uw{parameters}); //  ...or parenthesis
534 \}
535 aF.doneInserting();
536
537 \end{alltt}
538
539 The \kw{doneInserting} call starts the reduction manager (see ``Array
540 Reductions'') and load balancer (see ~\ref{lbFramework})-- since
541 these objects need to know about all the array's elements, they
542 must be started after the initial elements are inserted.
543 You may call \kw{doneInserting} multiple times, but only the first
544 call actually does anything.  You may even \kw{insert} or \kw{destroy}
545 elements after a call to \kw{doneInserting}, with different semantics-- 
546 see the reduction manager and load balancer sections for details.
547
548 If you do not specify one, the system will choose a procesor to 
549 create an array element on based on the current map object.
550
551
552
553 \subsubsection{Advanced Array Creation: Demand Creation}
554
555 Normally, invoking an entry method on a nonexistant array
556 element is an error.  But if you add the attribute
557 \index{createhere} \index{createhome}
558 \kw{[createhere]} or \kw{[createhome]} to an entry method,
559  the array manager will 
560 ``demand create'' a new element to handle the message.  
561
562 With \kw{[createhome]}, the new element
563 will be created on the home processor, which is most efficient when messages for
564 the element may arrive from anywhere in the machine. With \kw{[createhere]},
565 the new element is created on the sending processor, which is most efficient
566 if when messages will often be sent from that same processor.
567
568 The new element is created by calling its default (taking no
569 paramters) constructor, which must exist and be listed in the .ci file.
570 A single array can have a mix of demand-creation and
571 classic entry methods; and demand-created and normally 
572 created elements.
573
574
575
576 \subsubsection{User-defined array index type}
577
578 \index{Array index type, user-defined}
579 \charmpp{} array indices are arbitrary collections of integers.
580 To define a new array index, you create an ordinary C++ class 
581 which inherits from \kw{CkArrayIndex} and sets the ``nInts'' member
582 to the length, in integers, of the array index.
583
584 For example, if you have a structure or class named ``Foo'', you 
585 can use a \uw{Foo} object as an array index by defining the class:
586
587 \begin{alltt}
588 #include <charm++.h>
589 class CkArrayIndexFoo:public CkArrayIndex \{
590     Foo f;
591 public:
592     CkArrayIndexFoo(const Foo \&in) 
593     \{
594         f=in;
595         nInts=sizeof(f)/sizeof(int);
596     \}
597     //Not required, but convenient: cast-to-foo operators
598     operator Foo &() \{return f;\}
599     operator const Foo &() const \{return f;\}
600 \};
601 \end{alltt}
602
603 Note that \uw{Foo}'s size must be an integral number of integers--
604 you must pad it with zero bytes if this is not the case.
605 Also, \uw{Foo} must be a simple class-- it cannot contain 
606 pointers, have virtual functions, or require a destructor.
607 Finally, there is a \charmpp\ configuration-time option called
608 CK\_ARRAYINDEX\_MAXLEN \index{CK\_ARRAYINDEX\_MAXLEN} 
609 which is the largest allowable number of 
610 integers in an array index.  The default is 3; but you may 
611 override this to any value by passing ``-DCK\_ARRAYINDEX\_MAXLEN=n'' 
612 to the \charmpp\ build script as well as all user code. Larger 
613 values will increase the size of each message.
614
615 You can then declare an array indexed by \uw{Foo} objects with
616
617 \begin{alltt}
618 //in the .ci file:
619 array [Foo] AF \{ entry AF(); ... \}
620
621 //in the .h file:
622 class AF : public CBase\_AF
623 \{ public: AF() \{\} ... \}
624
625 //in the .C file:
626     Foo f;
627     CProxy_AF a=CProxy_AF::ckNew();
628     a[CkArrayIndexFoo(f)].insert();
629     ...
630 \end{alltt}
631
632 Note that since our CkArrayIndexFoo constructor is not declared
633 with the explicit keyword, we can equivalently write the last line as:
634
635 \begin{alltt}
636     a[f].insert();
637 \end{alltt}
638
639 When you implement your array element class, as shown above you 
640 can inherit from \kw{CBase}\_\uw{ClassName}, 
641 a class templated by the index type \uw{Foo}. In the old syntax,
642 you could also inherit directly from \kw{ArrayElementT}.
643 The array index (an object of type \uw{Foo}) is then accessible as 
644 ``thisIndex''. For example:
645
646 \begin{alltt}
647
648 //in the .C file:
649 AF::AF()
650 \{
651     Foo myF=thisIndex;
652     functionTakingFoo(myF);
653 \}
654 \end{alltt}
655
656
657 \subsubsection{Migratable Array Elements}
658
659 \label{arraymigratable}
660 Array objects can \index{migrate}migrate from one PE to another.
661 For example, the load balancer (see section~\ref{lbFramework})
662 might migrate array elements to better balance the load between
663 processors.  For an array element to migrate, it must implement
664 a pack/unpack or ``pup'' method:
665
666 \begin{alltt}
667 //In the .h file:
668 class A2 : public CBase\_A2 \{
669 private: //My data members:
670     int nt;
671     unsigned char chr;
672     float flt[7];
673     int numDbl;
674     double *dbl;
675 public: 
676     //...other declarations
677
678     virtual void pup(PUP::er \&p);
679 \};
680
681 //In the .C file:
682 void A2::pup(PUP::er \&p)
683 \{
684     CBase\_A2::pup(p); //<- MUST call superclass's pup routine
685     p|nt;
686     p|chr;
687     p(flt,7);
688     p|numDbl;
689     if (p.isUnpacking()) dbl=new double[numDbl];
690     p(dbl,numDbl);
691 \}
692 \end{alltt}
693
694 Please note that if your object contains Structured Dagger code (see section ``Structured Dagger'') you must use the following syntax to correctly pup the object:
695
696 \begin{alltt}
697 class bar: public CBase\_bar \{
698  private:
699     int a,b;
700  public:
701     bar_SDAG_CODE 
702     ...other methods...
703
704     virtual void pup(PUP::er& p) \{
705       __sdag_pup(p);
706       ...pup other data here...
707     \}
708 \};
709 \end{alltt}
710
711 See the \index{PUP} section ``PUP'' for more details on pup routines
712 and the \kw{PUP::er} type.
713
714 The system uses one pup routine to do both packing and unpacking by
715 passing different types of \kw{PUP::er}s to it.  You can determine
716 what type of \kw{PUP::er} has been passed to you with the
717 \kw{isPacking()}, \kw{isUnpacking()}, and \kw{isSizing()} calls.
718
719 An array element can migrate by calling the \kw{migrateMe}(\uw{destination
720 processor}) member function-- this call must be the last action
721 in an element entry point.  The system can also migrate array elements
722 for load balancing (see the section~\ref{lbarray}).
723
724 To migrate your array element to another processor, the \charmpp{}
725 runtime will:
726
727 \begin{itemize}
728 \item Call your \kw{ckAboutToMigrate} method
729 \item Call your \uw{pup} method with a sizing \kw{PUP::er} to determine how 
730 big a message it needs to hold your element.
731 \item Call your \uw{pup} method again with a packing \kw{PUP::er} to pack 
732 your element into a message.
733 \item Call your element's destructor (killing off the old copy).
734 \item Send the message (containing your element) across the network.
735 \item Call your element's migration constructor on the new processor.
736 \item Call your \uw{pup} method on with an unpacking \kw{PUP::er} to unpack 
737 the element.
738 \item Call your \kw{ckJustMigrated} method
739 \end{itemize}
740
741 Migration constructors, then, are normally empty-- all the unpacking
742 and allocation of the data items is done in the element's \uw{pup} routine.
743 Deallocation is done in the element destructor as usual.
744
745
746 \subsubsection{Load Balancing Chare Arrays}
747
748 see section~\ref{lbFramework}
749
750
751 \subsubsection{Local Access}
752
753 \experimental{}
754 \index{ckLocal for arrays}
755 \label{ckLocal for arrays}
756 You can get direct access to a local array element using the
757 proxy's \kw{ckLocal} method, which returns an ordinary \CC\ pointer
758 to the element if it exists on the local processor; and NULL if
759 the element does not exist or is on another processor.
760
761 \begin{alltt}
762 A1 *a=a1[i].ckLocal();
763 if (a==NULL) //...is remote-- send message
764 else //...is local-- directly use members and methods of a
765 \end{alltt}
766
767 Note that if the element migrates or is deleted, any pointers 
768 obtained with \kw{ckLocal} are no longer valid.  It is best,
769 then, to either avoid \kw{ckLocal} or else call \kw{ckLocal} 
770 each time the element may have migrated; e.g., at the start 
771 of each entry method.
772
773
774 \subsubsection{Array Section}
775
776 \experimental{}
777 \label{array section}
778
779 \charmpp{} supports array section which is a subset of array 
780 elements in a chare array. \charmpp{} also supports array sections
781 which are a subset of array elements in multiple chare arrays of the
782 same type \ref{cross array section}.
783 A special proxy for an array section can be created given a list of array
784 indexes of elements.
785 Multicast operations are directly supported in array section proxy with
786 an unoptimized direct-sending implementation.
787 Section reduction is not directly supported by the section proxy. 
788 However, an optimized section multicast/reduction 
789 library called ''CkMulticast'' is provided as a separate library module,
790 which can be plugged in as a delegation of a section proxy for performing
791 section-based multicasts and reductions. 
792
793 For each chare array "A" declared in a ci file, a section proxy 
794 of type "CProxySection\_A" is automatically generated in the decl and def 
795 header files. 
796 In order to create an array section, a user needs to provide array indexes 
797 of all the array section members.
798 You can create an array section proxy in your application by 
799 invoking ckNew() function of the CProxySection.
800 For example, for a 3D array:
801
802 \begin{alltt}
803   CkVec<CkArrayIndex3D> elems;    // add array indices
804   for (int i=0; i<10; i++)
805     for (int j=0; j<20; j+=2)
806       for (int k=0; k<30; k+=2)
807          elems.push_back(CkArrayIndex3D(i, j, k));
808   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems.getVec(), elems.size());
809 \end{alltt}
810
811 Alternatively, one can do the same thing by providing [lbound:ubound:stride] 
812 for each dimension:
813
814 \begin{alltt}
815   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, 0, 9, 1, 0, 19, 2, 0, 29, 2);
816 \end{alltt}
817
818 The above codes create a section proxy that contains array elements of 
819 [0:9, 0:19:2, 0:29:2].
820
821 For user-defined array index other than CkArrayIndex1D to CkArrayIndex6D,
822 one needs to use the generic array index type: CkArrayIndexMax.
823
824 \begin{alltt}
825   CkArrayIndexMax *elems;    // add array indices
826   int numElems;
827   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems, numElems);
828 \end{alltt}
829
830 Once you have the array section proxy, you can do multicast to all the 
831 section members, or send messages to one member using its index that
832 is local to the section, like these:
833
834 \begin{alltt}
835   CProxySection_Hello proxy;
836   proxy.someEntry(...)          // multicast
837   proxy[0].someEntry(...)       // send to the first element in the section.
838 \end{alltt}
839
840 You can move the section proxy in a message to another processor, and still 
841 safely invoke the entry functions to the section proxy.
842
843 In the multicast example above, for a section with k members, total number 
844 of k messages will be sent to all the memebers, which is considered 
845 inefficient when several members are on a same processor, in which 
846 case only one message needs to be sent to that processor and delivered to
847 all section members on that processor locally. To support this optimization,
848 a separate library called CkMulticast is provided. This library also supports
849 section based reduction.
850
851 Note: Use of the bulk array constructor (dimensions given in the CkNew
852 or CkArrayOptions rather than individual insertion) will allow
853 construction to race ahead of several other startup procedures, this
854 creates some limitation on the construction delegation and use of
855 array section proxies.  For safety, array sections should be
856 created in a post constructor entry method.
857
858
859 \label {array_section_multicast}
860
861
862 To use the library, you need to compile and install CkMulticast library and 
863 link your applications against the library using -module:
864
865 \begin{alltt}
866   # compile and install the CkMulticast library, do this only once
867   cd charm/net-linux/tmp
868   make multicast
869
870   # link CkMulticast library using -module when compiling application
871   charmc  -o hello hello.o -module CkMulticast -language charm++ 
872 \end{alltt}
873
874 CkMulticast library is implemented using delegation(Sec. ~\ref{delegation}). 
875 A special ''CkMulticastMgr'' Chare Group is created as a 
876 deletegation for section multicast/reduction - all the messages sent
877 by the section proxy will be passed to the local delegation branch.
878
879 To use the CkMulticast delegation, one needs to create the CkMulticastMgr Group 
880 first, and then setup the delegation relationship between the section proxy and 
881 CkMulticastMgr Group. 
882 One only needs to create one CkMulticastMgr Group globally.
883 CkMulticastMgr group can serve all multicast/reduction delegations
884 for different array sections in an application:
885
886 \begin{alltt}
887   CProxySection_Hello sectProxy = CProxySection_Hello::ckNew(...);
888   CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew();
889   CkMulticastMgr *mCastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
890
891   sectProxy.ckSectionDelegate(mCastGrp);  // initialize section proxy
892
893   sectProxy.someEntry(...)           //multicast via delegation library as before
894 \end{alltt}
895
896 By default, CkMulticastMgr group builds a spanning tree for multicast/reduction
897 with a factor of 2 (binary tree).
898 One can specify a different factor when creating a CkMulticastMgr group.
899 For example,
900
901 \begin{alltt}
902   CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew(3);   // factor is 3
903 \end{alltt}
904
905 Note, to use CkMulticast library, all multicast messages must inherit from 
906 CkMcastBaseMsg, as the following.
907 Note that CkMcastBaseMsg must come first, this is IMPORTANT for CkMulticast 
908 library to retrieve section information out of the message.
909
910
911 \begin{alltt}
912 class HiMsg : public CkMcastBaseMsg, public CMessage_HiMsg
913 \{
914 public:
915   int *data;
916 \};
917 \end{alltt}
918
919 Due to this restriction, you need to define message explicitly for multicast 
920 entry functions and no parameter marshalling can be used for multicast with 
921 CkMulticast library.
922
923 \paragraph{Array Section Reduction} 
924
925 Since an array element can be members for multiple array sections, 
926 there has to be a way for each array element to tell for which array
927 section it wants to contribute. For this purpose, a data structure 
928 called ''CkSectionInfo'' is created by CkMulticastMgr for each 
929 array section that the array element belongs to.
930 When doing section reduction, the array element needs to pass the 
931 \kw{CkSectionInfo} as a parameter in the \kw{contribute()}. 
932 The \kw{CkSectionInfo} can be retrieved
933 from a message in a multicast entry function using function call 
934 \kw{CkGetSectionInfo}:
935
936 \begin{alltt}
937   CkSectionInfo cookie;
938
939   void SayHi(HiMsg *msg)
940   \{
941     CkGetSectionInfo(cookie, msg);     // update section cookie every time
942     int data = thisIndex;
943     mcastGrp->contribute(sizeof(int), &data, CkReduction::sum_int, cookie);
944   \}
945 \end{alltt}
946
947 Note that the cookie cannot be used as a one-time local variable in the 
948 function, the same cookie is needed for the next contribute. This is 
949 because cookie includes some context sensive information for example the 
950 reduction counter. Function \kw{CkGetSectionInfo()} only update some part 
951 of the data in cookie, not creating a brand new one.
952
953 Similar to array reduction, to use section based reduction, a reduction
954 client CkCallback object need to be created. You may pass the client callback 
955 as an additional parameter to \kw{contribute}. If different contribute calls 
956 pass different callbacks, some (unspecified, unreliable) callback will be 
957 chosen for use. See the followin example:
958
959 \begin{alltt}
960     CkCallback cb(CkIndex_myArrayType::myReductionEntry(NULL),thisProxy); 
961     mcastGrp->contribute(sizeof(int), &data, CkReduction::sum_int, cookie, cb);
962 \end{alltt}
963
964 If no member passes a callback to contribute, the reduction will use the 
965 default callback. You set the default callback for an array section using the 
966 \kw{setReductionClient} call by the section root member. A 
967 {\bf CkReductionMsg} message will be passed to this callback, which 
968 must delete the message when done.
969
970 \begin{alltt}
971   CProxySection_Hello sectProxy;
972   CkMulticastMgr *mcastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
973   mcastGrp->setReductionClient(sectProxy, new CkCallback(...));
974 \end{alltt}
975
976 Same as in array reduction, users can use built-in reduction 
977 types(Section~\ref{builtin_reduction}) or define his/her own reducer functions
978 (Section~\ref{new_type_reduction}).
979
980 \paragraph{Array section multicast/reduction when migration happens}
981
982 Using multicast/reduction, you don't need to worry about array migrations.
983 When migration happens, array element in the array section can still use 
984 the \kw{CkSectionInfo} it stored previously for doing reduction. 
985 Reduction messages will be correctly delivered but may not be as efficient 
986 until a new multicast spanning tree is rebuilt internally 
987 in \kw{CkMulticastMgr} library. 
988 When a new spanning tree is rebuilt, a updated \kw{CkSectionInfo} is 
989 passed along with a multicast message, 
990 so it is recommended that 
991 \kw{CkGetSectionInfo()} function is always called when a multicast 
992 message arrives (as shown in the above SayHi example).
993
994 In case when a multicast root migrates, one needs to reconstruct the 
995 spanning tree to get optimal performance. One will get the following
996 warning message if not doing so:
997 "Warning: Multicast not optimized after multicast root migrated."
998 In current implementation, user needs to initiate the rebuilding process
999 like:
1000
1001 \begin{alltt}
1002 void Foo::pup(PUP::er & p) {
1003     // if I am multicast root and it is unpacking
1004    if (ismcastroot && p.isUnpacking()) {
1005       CProxySection_Foo   fooProxy;    // proxy for the section
1006       CkMulticastMgr *mg = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
1007       mg->resetSection(fooProxy);
1008         // you may want to reset reduction client to root
1009       CkCallback *cb = new CkCallback(...);
1010       mg->setReductionClient(mcp, cb);
1011    }
1012 }
1013 \end{alltt}
1014
1015 \paragraph{Cross Array Sections}
1016
1017
1018 \experimental{}
1019 \label{cross array section}
1020
1021 Cross array sections contain elements from multiple arrays.
1022 Construction and use of cross array sections is similar to normal
1023 array sections with the following restrictions.  
1024
1025 \begin{itemize}
1026
1027 \item Arrays in a section my all be of the same type.
1028
1029 \item Each array must be enumerated by array ID
1030
1031 \item The elements within each array must be enumerated explicitly
1032
1033 \item No existing modules currently support delegation of cross
1034   section proxies.  Therefore reductions are not currently supported.
1035
1036 \end{itemize}
1037
1038 Note: cross section logic also works for groups with analogous characteristics.
1039
1040 Given three arrays declared thusly:
1041
1042 \begin{alltt}
1043           CkArrayID *aidArr= new CkArrayID[3];
1044           CProxy\_multisectiontest\_array1d *Aproxy= new CProxy\_multisectiontest\_array1d[3];
1045           for(int i=0;i<3;i++)
1046             \{
1047               Aproxy[i]=CProxy\_multisectiontest\_array1d::ckNew(masterproxy.ckGetGroupID(),ArraySize);   
1048               aidArr[i]=Aproxy[i].ckGetArrayID();
1049             \}
1050 \end{alltt}
1051
1052 One can make a section including the  lower half elements of all three
1053 arrays as follows:
1054
1055 \begin{alltt}
1056           int aboundary=ArraySize/2;
1057           int afloor=aboundary;
1058           int aceiling=ArraySize-1;
1059           int asectionSize=aceiling-afloor+1;
1060           // cross section lower half of each array
1061           CkArrayIndexMax **aelems= new CkArrayIndexMax*[3];
1062           aelems[0]= new CkArrayIndexMax[asectionSize];
1063           aelems[1]= new CkArrayIndexMax[asectionSize];
1064           aelems[2]= new CkArrayIndexMax[asectionSize];
1065           int *naelems=new int[3];
1066           for(int k=0;k<3;k++)
1067             \{
1068               naelems[k]=asectionSize;
1069               for(int i=afloor,j=0;i<=aceiling;i++,j++)
1070                 aelems[k][j]=CkArrayIndex1D(i);
1071             \}
1072           CProxySection\_multisectiontest\_array1d arrayLowProxy(3,aidArr,aelems,naelems);
1073 \end{alltt}
1074
1075
1076
1077 The resulting cross section proxy, as in the example \uw{arrayLowProxy},
1078 can then be used for multicasts in the same way as a normal array
1079 section.
1080
1081 Note: For simplicity the example has all arrays and sections of uniform
1082 size.  The size of each array and the number of elements in each array
1083 within a section can all be set independently.
1084
1085