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