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