Revert "Drop requirement for user code to call CBase_foo::pup(p)"
[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 block fashion to processors, and maps other array
303 indices based on a hash function. Some other mappings such as round-robin
304 (\kw{RRMap}) also exist, which can be used
305 similar to custom ones described below.
306
307 A custom map object is implemented as a group which inherits from
308 \kw{CkArrayMap} and defines these virtual methods:
309
310 \begin{alltt}
311 class CkArrayMap : public Group
312 \{
313 public:
314   //...
315   
316   //Return an ``arrayHdl'', given some information about the array
317   virtual int registerArray(CkArrayIndex& numElements,CkArrayID aid);
318   //Return the home processor number for this element of this array
319   virtual int procNum(int arrayHdl,const CkArrayIndex &element);
320 \}
321 \end{alltt}
322
323 For example, a simple 1D blockmapping scheme.  Actual mapping is
324 handled in the procNum function.
325
326 \begin{alltt}
327 class BlockMap : public CkArrayMap 
328 \{
329  public:
330   BlockMap(void) \{\}
331   BlockMap(CkMigrateMessage *m)\{\}
332   int registerArray(CkArrayIndex& numElements,CkArrayID aid) \{
333     return 0;
334   \}
335   int procNum(int /*arrayHdl*/,const CkArrayIndex &idx) \{
336     int elem=*(int *)idx.data();
337     int penum =  (elem/(32/CkNumPes()));
338     return penum;
339   \}
340 \};
341
342 \end{alltt}
343 Once you've instantiated a custom map object, you can use it to
344 control the location of a new array's elements using the
345 \kw{setMap} method of the \kw{CkArrayOptions} object described above.
346 For example, if you've declared a map object named ``BlockMap'':
347
348 \begin{alltt}
349 //Create the map group
350   CProxy_BlockMap myMap=CProxy_BlockMap::ckNew();
351 //Make a new array using that map
352   CkArrayOptions opts(nElements);
353   opts.setMap(myMap);
354   a1=CProxy_A1::ckNew(\uw{parameters},opts);
355 \end{alltt}
356
357
358
359 \subsubsection{Advanced Array Creation: Initial Elements}
360
361 \index{array initial}
362 \label{array initial}
363
364 The map object described above can also be used to create
365 the initial set of array elements in a distributed fashion.
366 An array's initial elements are created by its map object,
367 by making a call to \kw{populateInitial} on each processor.
368
369 You can create your own set of elements by creating your
370 own map object and overriding this virtual function of \kw{CkArrayMap}:
371
372 \begin{alltt}
373   virtual void populateInitial(int arrayHdl,int numInitial,
374         void *msg,CkArrMgr *mgr)
375 \end{alltt}
376
377 In this call, \kw{arrayHdl} is the value returned by \kw{registerArray},
378 \kw{numInitial} is the number of elements passed to \kw{CkArrayOptions},
379 \kw{msg} is the constructor message to pass, and \kw{mgr} is the
380 array to create.
381
382 \kw{populateInitial} creates new array elements using the method
383 \kw{void CkArrMgr::insertInitial(CkArrayIndex idx,void *ctorMsg)}.
384 For example, to create one row of 2D array elements on each processor,
385 you would write:
386
387 \begin{alltt}
388 void xyElementMap::populateInitial(int arrayHdl,int numInitial,
389         void *msg,CkArrMgr *mgr)
390 \{
391   if (numInitial==0) return; //No initial elements requested
392         
393   //Create each local element
394   int y=CkMyPe();
395   for (int x=0;x<numInitial;x++) \{
396     mgr->insertInitial(CkArrayIndex2D(x,y),CkCopyMsg(&msg));
397   \}
398   mgr->doneInserting();
399   CkFreeMsg(msg);
400 \}
401 \end{alltt}
402
403 Thus calling \kw{ckNew(10)} on a 3-processor machine would result in
404 30 elements being created.
405
406
407 \subsubsection{Advanced Array Creation: Bound Arrays}
408
409 \experimental{}
410 \index{bound arrays} \index{bindTo}
411 \label{bound arrays}
412 You can ``bind'' a new array to an existing array
413 using the \kw{bindTo} method of \kw{CkArrayOptions}.  Bound arrays
414 act like separate arrays in all ways except for migration--
415 corresponding elements of bound arrays always migrate together.
416 For example, this code creates two arrays A and B which are
417 bound together-- A[i] and B[i] will always be on the same processor.
418
419 \begin{alltt}
420 //Create the first array normally
421   aProxy=CProxy_A::ckNew(\uw{parameters},nElements);
422 //Create the second array bound to the first
423   CkArrayOptions opts(nElements);
424   opts.bindTo(aProxy);
425   bProxy=CProxy_B::ckNew(\uw{parameters},opts);
426 \end{alltt}
427
428 An arbitrary number of arrays can be bound together--
429 in the example above, we could create yet another array
430 C and bind it to A or B.  The result would be the same
431 in either case-- A[i], B[i], and C[i] will always be
432 on the same processor.
433
434 There is no relationship between the types of bound arrays--
435 it is permissible to bind arrays of different types or of the
436 same type.  It is also permissible to have different numbers
437 of elements in the arrays, although elements of A which have
438 no corresponding element in B obey no special semantics.
439 Any method may be used to create the elements of any bound
440 array.
441
442 Bound arrays are often useful if A[i] and B[i] perform different 
443 aspects of the same computation, and thus will run most efficiently 
444 if they lie on the same processor.  Bound array elements are guaranteed
445 to always be able to interact using \kw{ckLocal} (see 
446 section~\ref{ckLocal for arrays}), although the local pointer must
447 be refreshed after any migration. This should be done during the \kw{pup}
448 routine. When migrated, all elements that are bound together will be created
449 at the new processor before \kw{pup} is called on any of them, ensuring that
450 a valid local pointer to any of the bound objects can be obtained during the
451 \kw{pup} routine of any of the others.
452
453 For example, an array {\it Alibrary} is implemented as a library module.
454 It implements a certain functionality by operating on a data array {\it dest}
455 which is just a pointer to some user provided data.
456 A user defined array {\it UserArray} is created and bound to 
457 the array {\it Alibrary} to take advanatage of the functionality provided 
458 by the library.
459 When bound array element migrated, the {\it data} pointer in {\it UserArray}
460 is re-allocated in {\it pup()}, thus {\it UserArray} is responsible to refresh
461 the pointer {\it dest} stored in {\it Alibrary}.
462
463 \begin{alltt}
464 class Alibrary: public CProxy_Alibrary \{
465 public:
466   ...
467   void set_ptr(double *ptr) \{ dest = ptr; \}
468   virtual void pup(PUP::er &p);
469 private:
470   double *dest;           // point to user data in user defined bound array
471 \};
472
473 class UserArray: public CProxy_UserArray \{
474 public:
475   virtual void pup(PUP::er &p) \{
476                 p|len;
477                 if(p.isUnpacking()) \{ 
478                   data = new double[len];
479                   Alibrary *myfellow = AlibraryProxy(thisIndex).ckLocal();
480                   myfellow->set_ptr(data);    // refresh data in bound array
481                 \}
482                 p(data, len);
483   \}
484 private:
485   CProxy_Alibrary  AlibraryProxy;   // proxy to my bound array
486   double *data;          // user allocated data pointer
487   int len;
488 \};
489 \end{alltt}
490
491
492 \subsubsection{Advanced Array Creation: Dynamic Insertion}
493
494 \label{dynamic_insertion}
495
496 In addition to creating initial array elements using ckNew,
497 you can also
498 create array elements during the computation.
499
500 You insert elements into the array by indexing the proxy
501 and calling insert.  The insert call optionally takes 
502 parameters, which are passed to the constructor; and a
503 processor number, where the element will be created.
504 Array elements can be inserted in any order from 
505 any processor at any time.  Array elements need not 
506 be contiguous.
507
508 If using \kw{insert} to create all the elements of the array,
509 you must call \kw{CProxy\_Array::doneInserting} before using
510 the array.
511
512 \begin{alltt}
513 //In the .C file:
514 int x,y,z;
515 CProxy_A1 a1=CProxy_A1::ckNew();  //Creates a new, empty 1D array
516 for (x=...) \{
517    a1[x  ].insert(\uw{parameters});  //Bracket syntax
518    a1(x+1).insert(\uw{parameters});  // or equivalent parenthesis syntax
519 \}
520 a1.doneInserting();
521
522 CProxy_A2 a2=CProxy_A2::ckNew();   //Creates 2D array
523 for (x=...) for (y=...)
524    a2(x,y).insert(\uw{parameters});  //Can't use brackets!
525 a2.doneInserting();
526
527 CProxy_A3 a3=CProxy_A3::ckNew();   //Creates 3D array
528 for (x=...) for (y=...) for (z=...)
529    a3(x,y,z).insert(\uw{parameters});
530 a3.doneInserting();
531
532 CProxy_AF aF=CProxy_AF::ckNew();   //Creates user-defined index array
533 for (...) \{
534    aF[CkArrayIndexFoo(...)].insert(\uw{parameters}); //Use brackets...
535    aF(CkArrayIndexFoo(...)).insert(\uw{parameters}); //  ...or parenthesis
536 \}
537 aF.doneInserting();
538
539 \end{alltt}
540
541 The \kw{doneInserting} call starts the reduction manager (see ``Array
542 Reductions'') and load balancer (see ~\ref{lbFramework})-- since
543 these objects need to know about all the array's elements, they
544 must be started after the initial elements are inserted.
545 You may call \kw{doneInserting} multiple times, but only the first
546 call actually does anything.  You may even \kw{insert} or \kw{destroy}
547 elements after a call to \kw{doneInserting}, with different semantics-- 
548 see the reduction manager and load balancer sections for details.
549
550 If you do not specify one, the system will choose a procesor to 
551 create an array element on based on the current map object.
552
553
554
555 \subsubsection{Advanced Array Creation: Demand Creation}
556
557 Normally, invoking an entry method on a nonexistant array
558 element is an error.  But if you add the attribute
559 \index{createhere} \index{createhome}
560 \kw{[createhere]} or \kw{[createhome]} to an entry method,
561  the array manager will 
562 ``demand create'' a new element to handle the message.  
563
564 With \kw{[createhome]}, the new element
565 will be created on the home processor, which is most efficient when messages for
566 the element may arrive from anywhere in the machine. With \kw{[createhere]},
567 the new element is created on the sending processor, which is most efficient
568 if when messages will often be sent from that same processor.
569
570 The new element is created by calling its default (taking no
571 paramters) constructor, which must exist and be listed in the .ci file.
572 A single array can have a mix of demand-creation and
573 classic entry methods; and demand-created and normally 
574 created elements.
575
576
577
578 \subsubsection{User-defined array index type}
579
580 \index{Array index type, user-defined}
581 \charmpp{} array indices are arbitrary collections of integers.
582 To define a new array index, you create an ordinary C++ class 
583 which inherits from \kw{CkArrayIndex} and sets the ``nInts'' member
584 to the length, in integers, of the array index.
585
586 For example, if you have a structure or class named ``Foo'', you 
587 can use a \uw{Foo} object as an array index by defining the class:
588
589 \begin{alltt}
590 #include <charm++.h>
591 class CkArrayIndexFoo:public CkArrayIndex \{
592     Foo f;
593 public:
594     CkArrayIndexFoo(const Foo \&in) 
595     \{
596         f=in;
597         nInts=sizeof(f)/sizeof(int);
598     \}
599     //Not required, but convenient: cast-to-foo operators
600     operator Foo &() \{return f;\}
601     operator const Foo &() const \{return f;\}
602 \};
603 \end{alltt}
604
605 Note that \uw{Foo}'s size must be an integral number of integers--
606 you must pad it with zero bytes if this is not the case.
607 Also, \uw{Foo} must be a simple class-- it cannot contain 
608 pointers, have virtual functions, or require a destructor.
609 Finally, there is a \charmpp\ configuration-time option called
610 CK\_ARRAYINDEX\_MAXLEN \index{CK\_ARRAYINDEX\_MAXLEN} 
611 which is the largest allowable number of 
612 integers in an array index.  The default is 3; but you may 
613 override this to any value by passing ``-DCK\_ARRAYINDEX\_MAXLEN=n'' 
614 to the \charmpp\ build script as well as all user code. Larger 
615 values will increase the size of each message.
616
617 You can then declare an array indexed by \uw{Foo} objects with
618
619 \begin{alltt}
620 //in the .ci file:
621 array [Foo] AF \{ entry AF(); ... \}
622
623 //in the .h file:
624 class AF : public CBase\_AF
625 \{ public: AF() \{\} ... \}
626
627 //in the .C file:
628     Foo f;
629     CProxy_AF a=CProxy_AF::ckNew();
630     a[CkArrayIndexFoo(f)].insert();
631     ...
632 \end{alltt}
633
634 Note that since our CkArrayIndexFoo constructor is not declared
635 with the explicit keyword, we can equivalently write the last line as:
636
637 \begin{alltt}
638     a[f].insert();
639 \end{alltt}
640
641 When you implement your array element class, as shown above you 
642 can inherit from \kw{CBase}\_\uw{ClassName}, 
643 a class templated by the index type \uw{Foo}. In the old syntax,
644 you could also inherit directly from \kw{ArrayElementT}.
645 The array index (an object of type \uw{Foo}) is then accessible as 
646 ``thisIndex''. For example:
647
648 \begin{alltt}
649
650 //in the .C file:
651 AF::AF()
652 \{
653     Foo myF=thisIndex;
654     functionTakingFoo(myF);
655 \}
656 \end{alltt}
657
658
659 \subsubsection{Migratable Array Elements}
660
661 \label{arraymigratable}
662 Array objects can \index{migrate}migrate from one PE to another.
663 For example, the load balancer (see section~\ref{lbFramework})
664 might migrate array elements to better balance the load between
665 processors.  For an array element to migrate, it must implement
666 a pack/unpack or ``pup'' method:
667
668 \begin{alltt}
669 //In the .h file:
670 class A2 : public CBase\_A2 \{
671 private: //My data members:
672     int nt;
673     unsigned char chr;
674     float flt[7];
675     int numDbl;
676     double *dbl;
677 public: 
678     //...other declarations
679
680     virtual void pup(PUP::er \&p);
681 \};
682
683 //In the .C file:
684 void A2::pup(PUP::er \&p)
685 \{
686     CBase\_A2::pup(p); //<- MUST call superclass's pup routine
687     p|nt;
688     p|chr;
689     p(flt,7);
690     p|numDbl;
691     if (p.isUnpacking()) dbl=new double[numDbl];
692     p(dbl,numDbl);
693 \}
694 \end{alltt}
695
696 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:
697
698 \begin{alltt}
699 class bar: public CBase\_bar \{
700  private:
701     int a,b;
702  public:
703     bar_SDAG_CODE 
704     ...other methods...
705
706     virtual void pup(PUP::er& p) \{
707       __sdag_pup(p);
708       ...pup other data here...
709     \}
710 \};
711 \end{alltt}
712
713 See the \index{PUP} section ``PUP'' for more details on pup routines
714 and the \kw{PUP::er} type.
715
716 The system uses one pup routine to do both packing and unpacking by
717 passing different types of \kw{PUP::er}s to it.  You can determine
718 what type of \kw{PUP::er} has been passed to you with the
719 \kw{isPacking()}, \kw{isUnpacking()}, and \kw{isSizing()} calls.
720
721 An array element can migrate by calling the \kw{migrateMe}(\uw{destination
722 processor}) member function-- this call must be the last action
723 in an element entry point.  The system can also migrate array elements
724 for load balancing (see the section~\ref{lbarray}).
725
726 To migrate your array element to another processor, the \charmpp{}
727 runtime will:
728
729 \begin{itemize}
730 \item Call your \kw{ckAboutToMigrate} method
731 \item Call your \uw{pup} method with a sizing \kw{PUP::er} to determine how 
732 big a message it needs to hold your element.
733 \item Call your \uw{pup} method again with a packing \kw{PUP::er} to pack 
734 your element into a message.
735 \item Call your element's destructor (killing off the old copy).
736 \item Send the message (containing your element) across the network.
737 \item Call your element's migration constructor on the new processor.
738 \item Call your \uw{pup} method on with an unpacking \kw{PUP::er} to unpack 
739 the element.
740 \item Call your \kw{ckJustMigrated} method
741 \end{itemize}
742
743 Migration constructors, then, are normally empty-- all the unpacking
744 and allocation of the data items is done in the element's \uw{pup} routine.
745 Deallocation is done in the element destructor as usual.
746
747
748 \subsubsection{Load Balancing Chare Arrays}
749
750 see section~\ref{lbFramework}
751
752
753 \subsubsection{Local Access}
754
755 \experimental{}
756 \index{ckLocal for arrays}
757 \label{ckLocal for arrays}
758 You can get direct access to a local array element using the
759 proxy's \kw{ckLocal} method, which returns an ordinary \CC\ pointer
760 to the element if it exists on the local processor; and NULL if
761 the element does not exist or is on another processor.
762
763 \begin{alltt}
764 A1 *a=a1[i].ckLocal();
765 if (a==NULL) //...is remote-- send message
766 else //...is local-- directly use members and methods of a
767 \end{alltt}
768
769 Note that if the element migrates or is deleted, any pointers 
770 obtained with \kw{ckLocal} are no longer valid.  It is best,
771 then, to either avoid \kw{ckLocal} or else call \kw{ckLocal} 
772 each time the element may have migrated; e.g., at the start 
773 of each entry method.
774
775
776 \subsubsection{Array Section}
777
778 \experimental{}
779 \label{array section}
780
781 \charmpp{} supports array section which is a subset of array 
782 elements in a chare array. \charmpp{} also supports array sections
783 which are a subset of array elements in multiple chare arrays of the
784 same type \ref{cross array section}.
785 A special proxy for an array section can be created given a list of array
786 indexes of elements.
787 Multicast operations are directly supported in array section proxy with
788 an unoptimized direct-sending implementation.
789 Section reduction is not directly supported by the section proxy. 
790 However, an optimized section multicast/reduction 
791 library called ''CkMulticast'' is provided as a separate library module,
792 which can be plugged in as a delegation of a section proxy for performing
793 section-based multicasts and reductions. 
794
795 For each chare array "A" declared in a ci file, a section proxy 
796 of type "CProxySection\_A" is automatically generated in the decl and def 
797 header files. 
798 In order to create an array section, a user needs to provide array indexes 
799 of all the array section members.
800 You can create an array section proxy in your application by 
801 invoking ckNew() function of the CProxySection.
802 For example, for a 3D array:
803
804 \begin{alltt}
805   CkVec<CkArrayIndex3D> elems;    // add array indices
806   for (int i=0; i<10; i++)
807     for (int j=0; j<20; j+=2)
808       for (int k=0; k<30; k+=2)
809          elems.push_back(CkArrayIndex3D(i, j, k));
810   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems.getVec(), elems.size());
811 \end{alltt}
812
813 Alternatively, one can do the same thing by providing [lbound:ubound:stride] 
814 for each dimension:
815
816 \begin{alltt}
817   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, 0, 9, 1, 0, 19, 2, 0, 29, 2);
818 \end{alltt}
819
820 The above codes create a section proxy that contains array elements of 
821 [0:9, 0:19:2, 0:29:2].
822
823 For user-defined array index other than CkArrayIndex1D to CkArrayIndex6D,
824 one needs to use the generic array index type: CkArrayIndex.
825
826 \begin{alltt}
827   CkArrayIndex *elems;    // add array indices
828   int numElems;
829   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems, numElems);
830 \end{alltt}
831
832 Once you have the array section proxy, you can do multicast to all the 
833 section members, or send messages to one member using its index that
834 is local to the section, like these:
835
836 \begin{alltt}
837   CProxySection_Hello proxy;
838   proxy.someEntry(...)          // multicast
839   proxy[0].someEntry(...)       // send to the first element in the section.
840 \end{alltt}
841
842 You can move the section proxy in a message to another processor, and still 
843 safely invoke the entry functions to the section proxy.
844
845 In the multicast example above, for a section with k members, total number 
846 of k messages will be sent to all the memebers, which is considered 
847 inefficient when several members are on a same processor, in which 
848 case only one message needs to be sent to that processor and delivered to
849 all section members on that processor locally. To support this optimization,
850 a separate library called CkMulticast is provided. This library also supports
851 section based reduction.
852
853 Note: Use of the bulk array constructor (dimensions given in the CkNew
854 or CkArrayOptions rather than individual insertion) will allow
855 construction to race ahead of several other startup procedures, this
856 creates some limitation on the construction delegation and use of
857 array section proxies.  For safety, array sections should be
858 created in a post constructor entry method.
859
860
861 \label {array_section_multicast}
862
863
864 To use the library, you need to compile and install CkMulticast library and 
865 link your applications against the library using -module:
866
867 \begin{alltt}
868   # compile and install the CkMulticast library, do this only once
869   cd charm/net-linux/tmp
870   make multicast
871
872   # link CkMulticast library using -module when compiling application
873   charmc  -o hello hello.o -module CkMulticast -language charm++ 
874 \end{alltt}
875
876 CkMulticast library is implemented using delegation(Sec. ~\ref{delegation}). 
877 A special ''CkMulticastMgr'' Chare Group is created as a 
878 deletegation for section multicast/reduction - all the messages sent
879 by the section proxy will be passed to the local delegation branch.
880
881 To use the CkMulticast delegation, one needs to create the CkMulticastMgr Group 
882 first, and then setup the delegation relationship between the section proxy and 
883 CkMulticastMgr Group. 
884 One only needs to create one CkMulticastMgr Group globally.
885 CkMulticastMgr group can serve all multicast/reduction delegations
886 for different array sections in an application:
887
888 \begin{alltt}
889   CProxySection_Hello sectProxy = CProxySection_Hello::ckNew(...);
890   CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew();
891   CkMulticastMgr *mCastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
892
893   sectProxy.ckSectionDelegate(mCastGrp);  // initialize section proxy
894
895   sectProxy.someEntry(...)           //multicast via delegation library as before
896 \end{alltt}
897
898 By default, CkMulticastMgr group builds a spanning tree for multicast/reduction
899 with a factor of 2 (binary tree).
900 One can specify a different factor when creating a CkMulticastMgr group.
901 For example,
902
903 \begin{alltt}
904   CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew(3);   // factor is 3
905 \end{alltt}
906
907 Note, to use CkMulticast library, all multicast messages must inherit from 
908 CkMcastBaseMsg, as the following.
909 Note that CkMcastBaseMsg must come first, this is IMPORTANT for CkMulticast 
910 library to retrieve section information out of the message.
911
912
913 \begin{alltt}
914 class HiMsg : public CkMcastBaseMsg, public CMessage_HiMsg
915 \{
916 public:
917   int *data;
918 \};
919 \end{alltt}
920
921 Due to this restriction, you need to define message explicitly for multicast 
922 entry functions and no parameter marshalling can be used for multicast with 
923 CkMulticast library.
924
925 \paragraph{Array Section Reduction} 
926
927 Since an array element can be members for multiple array sections, 
928 there has to be a way for each array element to tell for which array
929 section it wants to contribute. For this purpose, a data structure 
930 called ''CkSectionInfo'' is created by CkMulticastMgr for each 
931 array section that the array element belongs to.
932 When doing section reduction, the array element needs to pass the 
933 \kw{CkSectionInfo} as a parameter in the \kw{contribute()}. 
934 The \kw{CkSectionInfo} can be retrieved
935 from a message in a multicast entry function using function call 
936 \kw{CkGetSectionInfo}:
937
938 \begin{alltt}
939   CkSectionInfo cookie;
940
941   void SayHi(HiMsg *msg)
942   \{
943     CkGetSectionInfo(cookie, msg);     // update section cookie every time
944     int data = thisIndex;
945     mcastGrp->contribute(sizeof(int), &data, CkReduction::sum_int, cookie);
946   \}
947 \end{alltt}
948
949 Note that the cookie cannot be used as a one-time local variable in the 
950 function, the same cookie is needed for the next contribute. This is 
951 because cookie includes some context sensive information for example the 
952 reduction counter. Function \kw{CkGetSectionInfo()} only update some part 
953 of the data in cookie, not creating a brand new one.
954
955 Similar to array reduction, to use section based reduction, a reduction
956 client CkCallback object need to be created. You may pass the client callback 
957 as an additional parameter to \kw{contribute}. If different contribute calls 
958 pass different callbacks, some (unspecified, unreliable) callback will be 
959 chosen for use. See the followin example:
960
961 \begin{alltt}
962     CkCallback cb(CkIndex_myArrayType::myReductionEntry(NULL),thisProxy); 
963     mcastGrp->contribute(sizeof(int), &data, CkReduction::sum_int, cookie, cb);
964 \end{alltt}
965
966 If no member passes a callback to contribute, the reduction will use the 
967 default callback. You set the default callback for an array section using the 
968 \kw{setReductionClient} call by the section root member. A 
969 {\bf CkReductionMsg} message will be passed to this callback, which 
970 must delete the message when done.
971
972 \begin{alltt}
973   CProxySection_Hello sectProxy;
974   CkMulticastMgr *mcastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
975   mcastGrp->setReductionClient(sectProxy, new CkCallback(...));
976 \end{alltt}
977
978 Same as in array reduction, users can use built-in reduction 
979 types(Section~\ref{builtin_reduction}) or define his/her own reducer functions
980 (Section~\ref{new_type_reduction}).
981
982 \paragraph{Array section multicast/reduction when migration happens}
983
984 Using multicast/reduction, you don't need to worry about array migrations.
985 When migration happens, array element in the array section can still use 
986 the \kw{CkSectionInfo} it stored previously for doing reduction. 
987 Reduction messages will be correctly delivered but may not be as efficient 
988 until a new multicast spanning tree is rebuilt internally 
989 in \kw{CkMulticastMgr} library. 
990 When a new spanning tree is rebuilt, a updated \kw{CkSectionInfo} is 
991 passed along with a multicast message, 
992 so it is recommended that 
993 \kw{CkGetSectionInfo()} function is always called when a multicast 
994 message arrives (as shown in the above SayHi example).
995
996 In case when a multicast root migrates, one needs to reconstruct the 
997 spanning tree to get optimal performance. One will get the following
998 warning message if not doing so:
999 "Warning: Multicast not optimized after multicast root migrated."
1000 In current implementation, user needs to initiate the rebuilding process
1001 like:
1002
1003 \begin{alltt}
1004 void Foo::pup(PUP::er & p) {
1005     // if I am multicast root and it is unpacking
1006    if (ismcastroot && p.isUnpacking()) {
1007       CProxySection_Foo   fooProxy;    // proxy for the section
1008       CkMulticastMgr *mg = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
1009       mg->resetSection(fooProxy);
1010         // you may want to reset reduction client to root
1011       CkCallback *cb = new CkCallback(...);
1012       mg->setReductionClient(mcp, cb);
1013    }
1014 }
1015 \end{alltt}
1016
1017 \paragraph{Cross Array Sections}
1018
1019
1020 \experimental{}
1021 \label{cross array section}
1022
1023 Cross array sections contain elements from multiple arrays.
1024 Construction and use of cross array sections is similar to normal
1025 array sections with the following restrictions.  
1026
1027 \begin{itemize}
1028
1029 \item Arrays in a section my all be of the same type.
1030
1031 \item Each array must be enumerated by array ID
1032
1033 \item The elements within each array must be enumerated explicitly
1034
1035 \item No existing modules currently support delegation of cross
1036   section proxies.  Therefore reductions are not currently supported.
1037
1038 \end{itemize}
1039
1040 Note: cross section logic also works for groups with analogous characteristics.
1041
1042 Given three arrays declared thusly:
1043
1044 \begin{alltt}
1045           CkArrayID *aidArr= new CkArrayID[3];
1046           CProxy\_multisectiontest\_array1d *Aproxy= new CProxy\_multisectiontest\_array1d[3];
1047           for(int i=0;i<3;i++)
1048             \{
1049               Aproxy[i]=CProxy\_multisectiontest\_array1d::ckNew(masterproxy.ckGetGroupID(),ArraySize);   
1050               aidArr[i]=Aproxy[i].ckGetArrayID();
1051             \}
1052 \end{alltt}
1053
1054 One can make a section including the  lower half elements of all three
1055 arrays as follows:
1056
1057 \begin{alltt}
1058           int aboundary=ArraySize/2;
1059           int afloor=aboundary;
1060           int aceiling=ArraySize-1;
1061           int asectionSize=aceiling-afloor+1;
1062           // cross section lower half of each array
1063           CkArrayIndex **aelems= new CkArrayIndex*[3];
1064           aelems[0]= new CkArrayIndex[asectionSize];
1065           aelems[1]= new CkArrayIndex[asectionSize];
1066           aelems[2]= new CkArrayIndex[asectionSize];
1067           int *naelems=new int[3];
1068           for(int k=0;k<3;k++)
1069             \{
1070               naelems[k]=asectionSize;
1071               for(int i=afloor,j=0;i<=aceiling;i++,j++)
1072                 aelems[k][j]=CkArrayIndex1D(i);
1073             \}
1074           CProxySection\_multisectiontest\_array1d arrayLowProxy(3,aidArr,aelems,naelems);
1075 \end{alltt}
1076
1077
1078
1079 The resulting cross section proxy, as in the example \uw{arrayLowProxy},
1080 can then be used for multicasts in the same way as a normal array
1081 section.
1082
1083 Note: For simplicity the example has all arrays and sections of uniform
1084 size.  The size of each array and the number of elements in each array
1085 within a section can all be set independently.
1086
1087