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