d5b8812627793903ecb8cec4ed207c8d1609a065
[charm.git] / doc / charm++ / advancedarrays.tex
1 \subsection{Advanced Arrays}
2
3 \label{advanced arrays}
4
5 The basic array features described before (creation, messaging,
6 broadcasts, and reductions) are needed in almost every
7 \charmpp{} program.  The more advanced techniques that follow
8 are not universally needed; but are still often useful.
9
10 \subsubsection{Local Access}
11
12 \index{ckLocal for arrays}
13 \label{ckLocal for arrays}
14 You can get direct access to a local array element using the
15 proxy's \kw{ckLocal} method, which returns an ordinary \CC\ pointer
16 to the element if it exists on the local processor; and NULL if
17 the element does not exist or is on another processor.
18
19 \begin{alltt}
20 A1 *a=a1[i].ckLocal();
21 if (a==NULL) //...is remote-- send message
22 else //...is local-- directly use members and methods of a
23 \end{alltt}
24
25 Note that if the element migrates or is deleted, any pointers 
26 obtained with \kw{ckLocal} are no longer valid.  It is best,
27 then, to either avoid \kw{ckLocal} or else call \kw{ckLocal} 
28 each time the element may have migrated; e.g., at the start 
29 of each entry method.
30
31 \subsubsection{Advanced Array Creation}
32
33 \label{advanced array create}
34 There are several ways to control the array creation process.
35 You can adjust the map and bindings before creation, change
36 the way the initial array elements are created, create elements
37 explicitly during the computation, and create elements implicitly,
38 ``on demand''.  
39
40 You can create all your elements using any one of these methods,
41 or create different elements using different methods.  
42 An array element has the same syntax and semantics no matter
43 how it was created.  
44
45 \subsubsection{Advanced Array Creation: CkArrayOptions}
46
47 \index{CkArrayOptions}
48 \label{CkArrayOptions}
49
50 The array creation method \kw{ckNew} actually takes a parameter
51 of type \kw{CkArrayOptions}.  This object describes several
52 optional attributes of the new array.
53
54 The most common form of \kw{CkArrayOptions} is to set the number
55 of initial array elements.  A \kw{CkArrayOptions} object will be 
56 constructed automatically in this special common case.  Thus
57 the following code segments all do exactly the same thing:
58
59 \begin{alltt}
60 //Implicit CkArrayOptions
61   a1=CProxy_A1::ckNew(\uw{parameters},nElements);
62
63 //Explicit CkArrayOptions
64   a1=CProxy_A1::ckNew(\uw{parameters},CkArrayOptions(nElements));
65
66 //Separate CkArrayOptions
67   CkArrayOptions opts(nElements);
68   a1=CProxy_A1::ckNew(\uw{parameters},opts);
69 \end{alltt}
70
71 Note that the ``numElements'' in an array element is simply the
72 numElements passed in when the array was created.  The true number of
73 array elements may grow or shrink during the course of the
74 computation, so numElements can become out of date.  This ``bulk''
75 constructor approach should be preferred where possible, especially
76 for large arrays.  Bulk construction is handled via a broadcast which
77 will be significantly more efficient in the number of messages
78 required than inserting each element individually which will require
79 one message send per element.
80
81 \kw{CkArrayOptions} contains a few flags that the runtime can use to
82 optimize handling of a given array. If the array elements will only
83 migrate at controlled points (such as periodic load balancing with
84 {\tt AtASync()}), this is signalled to the runtime by calling {\tt
85   opts.setAnytimeMigration(false)}\footnote{At present, this optimizes
86 broadcasts to not save old messages for immigrating chares.}. If all
87 array elements will be inserted by bulk creation or by {\tt
88   fooArray[x].insert()} calls, signal this by calling {\tt
89   opts.setStaticInsertion(true)} \footnote{This can enable a slightly
90   faster default mapping scheme.}.
91
92 \subsubsection{Advanced Array Creation: Map Object}
93
94 \index{array map}
95 \label{array map}
96
97 You can use \kw{CkArrayOptions} to specify a ``map object''
98 for an array.  The map object is used by the array manager
99 to determine the ``home'' processor of each element.  The
100 home processor is the processor responsible for maintaining
101 the location of the element.
102
103 There is a default map object, which maps 1D array indices
104 in a block fashion to processors, and maps other array
105 indices based on a hash function. Some other mappings such as round-robin
106 (\kw{RRMap}) also exist, which can be used
107 similar to custom ones described below.
108
109 A custom map object is implemented as a group which inherits from
110 \kw{CkArrayMap} and defines these virtual methods:
111
112 \begin{alltt}
113 class CkArrayMap : public Group
114 \{
115 public:
116   //...
117   
118   //Return an ``arrayHdl'', given some information about the array
119   virtual int registerArray(CkArrayIndex& numElements,CkArrayID aid);
120   //Return the home processor number for this element of this array
121   virtual int procNum(int arrayHdl,const CkArrayIndex &element);
122 \}
123 \end{alltt}
124
125 For example, a simple 1D blockmapping scheme.  Actual mapping is
126 handled in the procNum function.
127
128 \begin{alltt}
129 class BlockMap : public CkArrayMap 
130 \{
131  public:
132   BlockMap(void) \{\}
133   BlockMap(CkMigrateMessage *m)\{\}
134   int registerArray(CkArrayIndex& numElements,CkArrayID aid) \{
135     return 0;
136   \}
137   int procNum(int /*arrayHdl*/,const CkArrayIndex &idx) \{
138     int elem=*(int *)idx.data();
139     int penum =  (elem/(32/CkNumPes()));
140     return penum;
141   \}
142 \};
143
144 \end{alltt}
145 Once you've instantiated a custom map object, you can use it to
146 control the location of a new array's elements using the
147 \kw{setMap} method of the \kw{CkArrayOptions} object described above.
148 For example, if you've declared a map object named ``BlockMap'':
149
150 \begin{alltt}
151 //Create the map group
152   CProxy_BlockMap myMap=CProxy_BlockMap::ckNew();
153 //Make a new array using that map
154   CkArrayOptions opts(nElements);
155   opts.setMap(myMap);
156   a1=CProxy_A1::ckNew(\uw{parameters},opts);
157 \end{alltt}
158
159
160
161 \subsubsection{Advanced Array Creation: Initial Elements}
162
163 \index{array initial}
164 \label{array initial}
165
166 The map object described above can also be used to create
167 the initial set of array elements in a distributed fashion.
168 An array's initial elements are created by its map object,
169 by making a call to \kw{populateInitial} on each processor.
170
171 You can create your own set of elements by creating your
172 own map object and overriding this virtual function of \kw{CkArrayMap}:
173
174 \begin{alltt}
175   virtual void populateInitial(int arrayHdl,int numInitial,
176         void *msg,CkArrMgr *mgr)
177 \end{alltt}
178
179 In this call, \kw{arrayHdl} is the value returned by \kw{registerArray},
180 \kw{numInitial} is the number of elements passed to \kw{CkArrayOptions},
181 \kw{msg} is the constructor message to pass, and \kw{mgr} is the
182 array to create.
183
184 \kw{populateInitial} creates new array elements using the method
185 \kw{void CkArrMgr::insertInitial(CkArrayIndex idx,void *ctorMsg)}.
186 For example, to create one row of 2D array elements on each processor,
187 you would write:
188
189 \begin{alltt}
190 void xyElementMap::populateInitial(int arrayHdl,int numInitial,
191         void *msg,CkArrMgr *mgr)
192 \{
193   if (numInitial==0) return; //No initial elements requested
194         
195   //Create each local element
196   int y=CkMyPe();
197   for (int x=0;x<numInitial;x++) \{
198     mgr->insertInitial(CkArrayIndex2D(x,y),CkCopyMsg(&msg));
199   \}
200   mgr->doneInserting();
201   CkFreeMsg(msg);
202 \}
203 \end{alltt}
204
205 Thus calling \kw{ckNew(10)} on a 3-processor machine would result in
206 30 elements being created.
207
208
209 \subsubsection{Advanced Array Creation: Bound Arrays}
210
211 \index{bound arrays} \index{bindTo}
212 \label{bound arrays}
213 You can ``bind'' a new array to an existing array
214 using the \kw{bindTo} method of \kw{CkArrayOptions}.  Bound arrays
215 act like separate arrays in all ways except for migration--
216 corresponding elements of bound arrays always migrate together.
217 For example, this code creates two arrays A and B which are
218 bound together-- A[i] and B[i] will always be on the same processor.
219
220 \begin{alltt}
221 //Create the first array normally
222   aProxy=CProxy_A::ckNew(\uw{parameters},nElements);
223 //Create the second array bound to the first
224   CkArrayOptions opts(nElements);
225   opts.bindTo(aProxy);
226   bProxy=CProxy_B::ckNew(\uw{parameters},opts);
227 \end{alltt}
228
229 An arbitrary number of arrays can be bound together--
230 in the example above, we could create yet another array
231 C and bind it to A or B.  The result would be the same
232 in either case-- A[i], B[i], and C[i] will always be
233 on the same processor.
234
235 There is no relationship between the types of bound arrays--
236 it is permissible to bind arrays of different types or of the
237 same type.  It is also permissible to have different numbers
238 of elements in the arrays, although elements of A which have
239 no corresponding element in B obey no special semantics.
240 Any method may be used to create the elements of any bound
241 array.
242
243 Bound arrays are often useful if A[i] and B[i] perform different 
244 aspects of the same computation, and thus will run most efficiently 
245 if they lie on the same processor.  Bound array elements are guaranteed
246 to always be able to interact using \kw{ckLocal} (see 
247 section~\ref{ckLocal for arrays}), although the local pointer must
248 be refreshed after any migration. This should be done during the \kw{pup}
249 routine. When migrated, all elements that are bound together will be created
250 at the new processor before \kw{pup} is called on any of them, ensuring that
251 a valid local pointer to any of the bound objects can be obtained during the
252 \kw{pup} routine of any of the others.
253
254 For example, an array {\it Alibrary} is implemented as a library module.
255 It implements a certain functionality by operating on a data array {\it dest}
256 which is just a pointer to some user provided data.
257 A user defined array {\it UserArray} is created and bound to 
258 the array {\it Alibrary} to take advanatage of the functionality provided 
259 by the library.
260 When bound array element migrated, the {\it data} pointer in {\it UserArray}
261 is re-allocated in {\it pup()}, thus {\it UserArray} is responsible to refresh
262 the pointer {\it dest} stored in {\it Alibrary}.
263
264 \begin{alltt}
265 class Alibrary: public CProxy_Alibrary \{
266 public:
267   ...
268   void set_ptr(double *ptr) \{ dest = ptr; \}
269   virtual void pup(PUP::er &p);
270 private:
271   double *dest;           // point to user data in user defined bound array
272 \};
273
274 class UserArray: public CProxy_UserArray \{
275 public:
276   virtual void pup(PUP::er &p) \{
277                 p|len;
278                 if(p.isUnpacking()) \{ 
279                   data = new double[len];
280                   Alibrary *myfellow = AlibraryProxy(thisIndex).ckLocal();
281                   myfellow->set_ptr(data);    // refresh data in bound array
282                 \}
283                 p(data, len);
284   \}
285 private:
286   CProxy_Alibrary  AlibraryProxy;   // proxy to my bound array
287   double *data;          // user allocated data pointer
288   int len;
289 \};
290 \end{alltt}
291
292
293 \subsubsection{Advanced Array Creation: Dynamic Insertion}
294
295 \label{dynamic_insertion}
296
297 In addition to creating initial array elements using ckNew,
298 you can also
299 create array elements during the computation.
300
301 You insert elements into the array by indexing the proxy
302 and calling insert.  The insert call optionally takes 
303 parameters, which are passed to the constructor; and a
304 processor number, where the element will be created.
305 Array elements can be inserted in any order from 
306 any processor at any time.  Array elements need not 
307 be contiguous.
308
309 If using \kw{insert} to create all the elements of the array,
310 you must call \kw{CProxy\_Array::doneInserting} before using
311 the array.
312
313 \begin{alltt}
314 //In the .C file:
315 int x,y,z;
316 CProxy_A1 a1=CProxy_A1::ckNew();  //Creates a new, empty 1D array
317 for (x=...) \{
318    a1[x  ].insert(\uw{parameters});  //Bracket syntax
319    a1(x+1).insert(\uw{parameters});  // or equivalent parenthesis syntax
320 \}
321 a1.doneInserting();
322
323 CProxy_A2 a2=CProxy_A2::ckNew();   //Creates 2D array
324 for (x=...) for (y=...)
325    a2(x,y).insert(\uw{parameters});  //Can't use brackets!
326 a2.doneInserting();
327
328 CProxy_A3 a3=CProxy_A3::ckNew();   //Creates 3D array
329 for (x=...) for (y=...) for (z=...)
330    a3(x,y,z).insert(\uw{parameters});
331 a3.doneInserting();
332
333 CProxy_AF aF=CProxy_AF::ckNew();   //Creates user-defined index array
334 for (...) \{
335    aF[CkArrayIndexFoo(...)].insert(\uw{parameters}); //Use brackets...
336    aF(CkArrayIndexFoo(...)).insert(\uw{parameters}); //  ...or parenthesis
337 \}
338 aF.doneInserting();
339
340 \end{alltt}
341
342 The \kw{doneInserting} call starts the reduction manager (see ``Array
343 Reductions'') and load balancer (see ~\ref{lbFramework})-- since
344 these objects need to know about all the array's elements, they
345 must be started after the initial elements are inserted.
346 You may call \kw{doneInserting} multiple times, but only the first
347 call actually does anything.  You may even \kw{insert} or \kw{destroy}
348 elements after a call to \kw{doneInserting}, with different semantics-- 
349 see the reduction manager and load balancer sections for details.
350
351 If you do not specify one, the system will choose a processor to 
352 create an array element on based on the current map object.
353
354
355
356 \subsubsection{Advanced Array Creation: Demand Creation}
357
358 Normally, invoking an entry method on a nonexistant array
359 element is an error.  But if you add the attribute
360 \index{createhere} \index{createhome}
361 \kw{[createhere]} or \kw{[createhome]} to an entry method,
362  the array manager will 
363 ``demand create'' a new element to handle the message.  
364
365 With \kw{[createhome]}, the new element
366 will be created on the home processor, which is most efficient when messages for
367 the element may arrive from anywhere in the machine. With \kw{[createhere]},
368 the new element is created on the sending processor, which is most efficient
369 if when messages will often be sent from that same processor.
370
371 The new element is created by calling its default (taking no
372 parameters) constructor, which must exist and be listed in the .ci file.
373 A single array can have a mix of demand-creation and
374 classic entry methods; and demand-created and normally 
375 created elements.
376
377
378
379 \subsubsection{User-defined Array Index Type}
380 \label{user-defined array index type}
381
382 \index{Array index type, user-defined}
383 \charmpp{} array indices are arbitrary collections of integers.
384 To define a new array index, you create an ordinary C++ class 
385 which inherits from \kw{CkArrayIndex} and sets the ``nInts'' member
386 to the length, in integers, of the array index.
387
388 For example, if you have a structure or class named ``Foo'', you 
389 can use a \uw{Foo} object as an array index by defining the class:
390
391 \begin{alltt}
392 #include <charm++.h>
393 class CkArrayIndexFoo:public CkArrayIndex \{
394     Foo f;
395 public:
396     CkArrayIndexFoo(const Foo \&in) 
397     \{
398         f=in;
399         nInts=sizeof(f)/sizeof(int);
400     \}
401     //Not required, but convenient: cast-to-foo operators
402     operator Foo &() \{return f;\}
403     operator const Foo &() const \{return f;\}
404 \};
405 \end{alltt}
406
407 Note that \uw{Foo}'s size must be an integral number of integers--
408 you must pad it with zero bytes if this is not the case.
409 Also, \uw{Foo} must be a simple class-- it cannot contain 
410 pointers, have virtual functions, or require a destructor.
411 Finally, there is a \charmpp\ configuration-time option called
412 CK\_ARRAYINDEX\_MAXLEN \index{CK\_ARRAYINDEX\_MAXLEN} 
413 which is the largest allowable number of 
414 integers in an array index.  The default is 3; but you may 
415 override this to any value by passing ``-DCK\_ARRAYINDEX\_MAXLEN=n'' 
416 to the \charmpp\ build script as well as all user code. Larger 
417 values will increase the size of each message.
418
419 You can then declare an array indexed by \uw{Foo} objects with
420
421 \begin{alltt}
422 //in the .ci file:
423 array [Foo] AF \{ entry AF(); ... \}
424
425 //in the .h file:
426 class AF : public CBase\_AF
427 \{ public: AF() \{\} ... \}
428
429 //in the .C file:
430     Foo f;
431     CProxy_AF a=CProxy_AF::ckNew();
432     a[CkArrayIndexFoo(f)].insert();
433     ...
434 \end{alltt}
435
436 Note that since our CkArrayIndexFoo constructor is not declared
437 with the explicit keyword, we can equivalently write the last line as:
438
439 \begin{alltt}
440     a[f].insert();
441 \end{alltt}
442
443 When you implement your array element class, as shown above you 
444 can inherit from \kw{CBase}\_\uw{ClassName}, 
445 a class templated by the index type \uw{Foo}. In the old syntax,
446 you could also inherit directly from \kw{ArrayElementT}.
447 The array index (an object of type \uw{Foo}) is then accessible as 
448 ``thisIndex''. For example:
449
450 \begin{alltt}
451
452 //in the .C file:
453 AF::AF()
454 \{
455     Foo myF=thisIndex;
456     functionTakingFoo(myF);
457 \}
458 \end{alltt}
459
460 %\subsubsection{Load Balancing Chare Arrays}
461
462 %see section~\ref{lbFramework}
463
464 \subsubsection{Array Section}
465
466 \label{array section}
467
468 \charmpp{} supports the array section operation, the section operation identifies a subset of array 
469 elements from a chare array for access via a single section proxy. \charmpp{} also supports array sections
470 which are a subset of array elements in multiple chare arrays of the
471 same type \ref{cross array section}.
472 A special proxy for an array section can be created given a list of array
473 indexes of elements.
474 Multicast operations, a broadcast to all members of a section, are directly supported in array section proxy with
475 an unoptimized direct-sending implementation.
476 Section reduction is not directly supported by the section proxy. 
477 However, an optimized section multicast/reduction 
478 library called ''CkMulticast'' is provided as a separate library module,
479 which can be plugged in as a delegation of a section proxy for performing
480 section-based multicasts and reductions using optimized spanning trees. 
481
482 For each chare array "A" declared in a ci file, a section proxy 
483 of type "CProxySection\_A" is automatically generated in the decl and def 
484 header files. 
485 In order to create an array section, the user needs to provide array indexes 
486 of all the array section members through either explicit enumeration, or an index range expression.
487 You can create an array section proxy in your application by 
488 invoking ckNew() function of the CProxySection.
489 For example, for a 3D array:
490
491 \begin{alltt}
492   CkVec<CkArrayIndex3D> elems;    // add array indices
493   for (int i=0; i<10; i++)
494     for (int j=0; j<20; j+=2)
495       for (int k=0; k<30; k+=2)
496          elems.push_back(CkArrayIndex3D(i, j, k));
497   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems.getVec(), elems.size());
498 \end{alltt}
499
500 Alternatively, one can do the same thing by providing the index range [lbound:ubound:stride] 
501 for each dimension:
502
503 \begin{alltt}
504   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, 0, 9, 1, 0, 19, 2, 0, 29, 2);
505 \end{alltt}
506
507 The above codes create a section proxy that contains array elements of 
508 [0:9, 0:19:2, 0:29:2].
509
510 For user-defined array index other than CkArrayIndex1D to CkArrayIndex6D,
511 one needs to use the generic array index type: CkArrayIndex.
512
513 \begin{alltt}
514   CkArrayIndex *elems;    // add array indices
515   int numElems;
516   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems, numElems);
517 \end{alltt}
518
519 Once you have the array section proxy, you can broadcast to all the 
520 section members, or send messages to one member using its offset index within the section, like these:
521
522 \begin{alltt}
523   CProxySection_Hello proxy;
524   proxy.someEntry(...)          // section broadcast
525   proxy[0].someEntry(...)       // send to the first element in the section.
526 \end{alltt}
527
528 You can send the section proxy in a message to another processor, and still 
529 safely invoke the entry functions on the section proxy.
530
531 In the broadcast example above, for a section with k members, a total
532 number of k messages will be sent, one to each member, which is
533 inefficient when several members are on a same processor, in which
534 case only one message needs to be sent to that processor and delivered
535 to all section members on that processor locally. To support this
536 optimization, a separate library called CkMulticast is provided as a
537 target for delegation to an optimized implementation. This library
538 also supports section based reduction.
539
540 Note: Use of the bulk array constructor (dimensions given in the CkNew
541 or CkArrayOptions rather than individual insertion) will allow
542 construction to race ahead of several other startup procedures, this
543 creates some limitation on the construction delegation and use of
544 array section proxies.  For safety, array sections should be
545 created in a post constructor entry method.
546
547
548 \label {array_section_multicast}
549
550
551 To use the library, you need to compile and install CkMulticast library and 
552 link your applications against the library using -module:
553
554 \begin{alltt}
555   # compile and install the CkMulticast library, do this only once
556   # assuming a net-linux-x86\_64 build
557   cd charm/net-linux-x86\_64/tmp
558   make multicast
559
560   # link CkMulticast library using -module when compiling application
561   charmc  -o hello hello.o -module CkMulticast -language charm++ 
562 \end{alltt}
563
564 The CkMulticast library is implemented using delegation(Sec. ~\ref{delegation}). 
565 A special ''CkMulticastMgr'' Chare Group is created as a 
566 delegation for section multicast/reduction - all the messages sent
567 by the section proxy will be passed to the local delegation branch.
568
569 To use the CkMulticast delegation, one needs to create the CkMulticastMgr Group 
570 first, and then setup the delegation relationship between the section proxy and 
571 CkMulticastMgr Group. 
572 One only needs to create one CkMulticastMgr Group globally.
573 CkMulticastMgr group can serve all multicast/reduction delegations
574 for different array sections in an application:
575
576 \begin{alltt}
577   CProxySection_Hello sectProxy = CProxySection_Hello::ckNew(...);
578   CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew();
579   CkMulticastMgr *mCastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
580
581   sectProxy.ckSectionDelegate(mCastGrp);  // initialize section proxy
582
583   sectProxy.someEntry(...)           //multicast via delegation library as before
584 \end{alltt}
585
586 By default, CkMulticastMgr group builds a spanning tree for multicast/reduction
587 with a factor of 2 (binary tree).
588 One can specify a different factor when creating a CkMulticastMgr group.
589 For example,
590
591 \begin{alltt}
592   CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew(3);   // factor is 3
593 \end{alltt}
594
595 Note, to use CkMulticast library, all multicast messages must inherit from 
596 CkMcastBaseMsg, as the following.
597 Note that CkMcastBaseMsg must come first, this is IMPORTANT for CkMulticast 
598 library to retrieve section information out of the message.
599
600
601 \begin{alltt}
602 class HiMsg : public CkMcastBaseMsg, public CMessage_HiMsg
603 \{
604 public:
605   int *data;
606 \};
607 \end{alltt}
608
609 Due to this restriction, you must define message explicitly for multicast 
610 entry functions and no parameter marshalling can be used for multicast with 
611 CkMulticast library.
612
613 \paragraph{Array Section Reduction} 
614
615 Since an array element can be a member of multiple array sections, 
616 it is necessary to disambiguate between which array
617 section reduction it is participating in each time it contributes to one. For this purpose, a data structure 
618 called ''CkSectionInfo'' is created by CkMulticastMgr for each 
619 array section that the array element belongs to.
620 During a section reduction, the array element must pass the 
621 \kw{CkSectionInfo} as a parameter in the \kw{contribute()}. 
622 The \kw{CkSectionInfo} for a section can be retrieved
623 from a message in a multicast entry point using function call 
624 \kw{CkGetSectionInfo}:
625
626 \begin{alltt}
627   CkSectionInfo cookie;
628
629   void SayHi(HiMsg *msg)
630   \{
631     CkGetSectionInfo(cookie, msg);     // update section cookie every time
632     int data = thisIndex;
633     mcastGrp->contribute(sizeof(int), &data, CkReduction::sum_int, cookie);
634   \}
635 \end{alltt}
636
637 Note that the cookie cannot be used as a one-time local variable in the 
638 function, the same cookie is needed for the next contribute. This is 
639 because the cookie includes some context sensive information (e.g., the 
640 reduction counter). Subsequent invocations of \kw{CkGetSectionInfo()} only updates part of the data in the cookie, rather than creating a brand new one.
641
642 Similar to array reduction, to use section based reduction, a
643 reduction client CkCallback object must be created. You may pass the
644 client callback as an additional parameter to \kw{contribute}. If
645 different contribute calls to the same reduction operation pass
646 different callbacks, some (unspecified, unreliable) callback will be
647 chosen for use. 
648
649 See the following example:
650
651 \begin{alltt}
652     CkCallback cb(CkIndex_myArrayType::myReductionEntry(NULL),thisProxy); 
653     mcastGrp->contribute(sizeof(int), &data, CkReduction::sum_int, cookie, cb);
654 \end{alltt}
655
656 If no member passes a callback to contribute, the reduction will use the 
657 default callback. You set the default callback for an array section using the 
658 \kw{setReductionClient} call in the section root member. A 
659 {\bf CkReductionMsg} message will be passed to this callback, which 
660 must delete the message when done.
661
662 \begin{alltt}
663   CProxySection_Hello sectProxy;
664   CkMulticastMgr *mcastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
665   mcastGrp->setReductionClient(sectProxy, new CkCallback(...));
666 \end{alltt}
667
668 As in an array reduction, users can use built-in reduction 
669 types(Section~\ref{builtin_reduction}) or define his/her own reducer functions
670 (Section~\ref{new_type_reduction}).
671
672 \paragraph{Array section multicast/reduction when migration happens}
673
674 Using multicast/reduction, you don't need to worry about array migrations.
675 When migration happens, array element in the array section can still use 
676 the \kw{CkSectionInfo} it stored previously for doing reduction. 
677 Reduction messages will be correctly delivered but may not be as efficient 
678 until a new multicast spanning tree is rebuilt internally 
679 in \kw{CkMulticastMgr} library. 
680 When a new spanning tree is rebuilt, a updated \kw{CkSectionInfo} is 
681 passed along with a multicast message, 
682 so it is recommended that 
683 \kw{CkGetSectionInfo()} function is always called when a multicast 
684 message arrives (as shown in the above SayHi example).
685
686 In case when a multicast root migrates, the library must reconstruct the 
687 spanning tree to get optimal performance. One will get the following
688 warning message if not doing so:
689 "Warning: Multicast not optimized after multicast root migrated."
690 In current implementation, user needs to initiate the rebuilding process
691 using \kw{resetSection}.
692
693 \begin{alltt}
694 void Foo::pup(PUP::er & p) {
695     // if I am multicast root and it is unpacking
696    if (ismcastroot && p.isUnpacking()) {
697       CProxySection_Foo   fooProxy;    // proxy for the section
698       CkMulticastMgr *mg = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
699       mg->resetSection(fooProxy);
700         // you may want to reset reduction client to root
701       CkCallback *cb = new CkCallback(...);
702       mg->setReductionClient(mcp, cb);
703    }
704 }
705 \end{alltt}
706
707 \paragraph{Cross Array Sections}
708
709
710 \experimental{}
711 \label{cross array section}
712
713 Cross array sections contain elements from multiple arrays.
714 Construction and use of cross array sections is similar to normal
715 array sections with the following restrictions.  
716
717 \begin{itemize}
718
719 \item Arrays in a section my all be of the same type.
720
721 \item Each array must be enumerated by array ID
722
723 \item The elements within each array must be enumerated explicitly
724
725 \item No existing modules currently support delegation of cross
726   section proxies.  Therefore reductions are not currently supported.
727
728 \end{itemize}
729
730 Note: cross section logic also works for groups with analogous characteristics.
731
732 Given three arrays declared thusly:
733
734 \begin{alltt}
735           CkArrayID *aidArr= new CkArrayID[3];
736           CProxy\_multisectiontest\_array1d *Aproxy= new CProxy\_multisectiontest\_array1d[3];
737           for(int i=0;i<3;i++)
738             \{
739               Aproxy[i]=CProxy\_multisectiontest\_array1d::ckNew(masterproxy.ckGetGroupID(),ArraySize);   
740               aidArr[i]=Aproxy[i].ckGetArrayID();
741             \}
742 \end{alltt}
743
744 One can make a section including the  lower half elements of all three
745 arrays as follows:
746
747 \begin{alltt}
748           int aboundary=ArraySize/2;
749           int afloor=aboundary;
750           int aceiling=ArraySize-1;
751           int asectionSize=aceiling-afloor+1;
752           // cross section lower half of each array
753           CkArrayIndex **aelems= new CkArrayIndex*[3];
754           aelems[0]= new CkArrayIndex[asectionSize];
755           aelems[1]= new CkArrayIndex[asectionSize];
756           aelems[2]= new CkArrayIndex[asectionSize];
757           int *naelems=new int[3];
758           for(int k=0;k<3;k++)
759             \{
760               naelems[k]=asectionSize;
761               for(int i=afloor,j=0;i<=aceiling;i++,j++)
762                 aelems[k][j]=CkArrayIndex1D(i);
763             \}
764           CProxySection\_multisectiontest\_array1d arrayLowProxy(3,aidArr,aelems,naelems);
765 \end{alltt}
766
767
768
769 The resulting cross section proxy, as in the example \uw{arrayLowProxy},
770 can then be used for multicasts in the same way as a normal array
771 section.
772
773 Note: For simplicity the example has all arrays and sections of uniform
774 size.  The size of each array and the number of elements in each array
775 within a section can all be set independently.
776
777