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