4320bbf595579d98f46ed0d4c2d3792511fb72ff
[charm.git] / doc / charm++ / sections.tex
1 \charmpp{} supports the array section operation, the section operation identifies a subset of array 
2 elements from a chare array for access via a single section proxy. \charmpp{} also supports array sections
3 which are a subset of array elements in multiple chare arrays of the
4 same type \ref{cross array section}.
5 A special proxy for an array section can be created given a list of array
6 indexes of elements.
7 Multicast operations, a broadcast to all members of a section, are directly supported in array section proxy with
8 an unoptimized direct-sending implementation.
9 Section reduction is not directly supported by the section proxy. 
10 However, an optimized section multicast/reduction 
11 library called ''CkMulticast'' is provided as a separate library module,
12 which can be plugged in as a delegation of a section proxy for performing
13 section-based multicasts and reductions using optimized spanning trees. 
14
15 For each chare array "A" declared in a ci file, a section proxy 
16 of type "CProxySection\_A" is automatically generated in the decl and def 
17 header files. 
18 In order to create an array section, the user needs to provide array indexes 
19 of all the array section members through either explicit enumeration, or an index range expression.
20 You can create an array section proxy in your application by 
21 invoking ckNew() function of the CProxySection.
22 For example, for a 3D array:
23
24 \begin{alltt}
25   CkVec<CkArrayIndex3D> elems;    // add array indices
26   for (int i=0; i<10; i++)
27     for (int j=0; j<20; j+=2)
28       for (int k=0; k<30; k+=2)
29          elems.push_back(CkArrayIndex3D(i, j, k));
30   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems.getVec(), elems.size());
31 \end{alltt}
32
33 Alternatively, one can do the same thing by providing the index range [lbound:ubound:stride] 
34 for each dimension:
35
36 \begin{alltt}
37   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, 0, 9, 1, 0, 19, 2, 0, 29, 2);
38 \end{alltt}
39
40 The above codes create a section proxy that contains array elements of 
41 [0:9, 0:19:2, 0:29:2].
42
43 For user-defined array index other than CkArrayIndex1D to CkArrayIndex6D,
44 one needs to use the generic array index type: CkArrayIndex.
45
46 \begin{alltt}
47   CkArrayIndex *elems;    // add array indices
48   int numElems;
49   CProxySection_Hello proxy = CProxySection_Hello::ckNew(helloArrayID, elems, numElems);
50 \end{alltt}
51
52 Once you have the array section proxy, you can broadcast to all the 
53 section members, or send messages to one member using its offset index within the section, like these:
54
55 \begin{alltt}
56   CProxySection_Hello proxy;
57   proxy.someEntry(...)          // section broadcast
58   proxy[0].someEntry(...)       // send to the first element in the section.
59 \end{alltt}
60
61 You can send the section proxy in a message to another processor, and still 
62 safely invoke the entry functions on the section proxy.
63
64 In the broadcast example above, for a section with k members, a total
65 number of k messages will be sent, one to each member, which is
66 inefficient when several members are on a same processor, in which
67 case only one message needs to be sent to that processor and delivered
68 to all section members on that processor locally. To support this
69 optimization, a separate library called CkMulticast is provided as a
70 target for delegation to an optimized implementation. This library
71 also supports section based reduction.
72
73 Note: Use of the bulk array constructor (dimensions given in the CkNew
74 or CkArrayOptions rather than individual insertion) will allow
75 construction to race ahead of several other startup procedures, this
76 creates some limitation on the construction delegation and use of
77 array section proxies.  For safety, array sections should be
78 created in a post constructor entry method.
79
80 \label {array_section_multicast}
81
82 To use the library, you need to compile and install CkMulticast library and 
83 link your applications against the library using -module:
84
85 \begin{alltt}
86   # compile and install the CkMulticast library, do this only once
87   # assuming a net-linux-x86\_64 build
88   cd charm/net-linux-x86\_64/tmp
89   make multicast
90
91   # link CkMulticast library using -module when compiling application
92   charmc  -o hello hello.o -module CkMulticast -language charm++ 
93 \end{alltt}
94
95 The CkMulticast library is implemented using delegation(Sec. ~\ref{delegation}). 
96 A special ''CkMulticastMgr'' Chare Group is created as a 
97 delegation for section multicast/reduction - all the messages sent
98 by the section proxy will be passed to the local delegation branch.
99
100 To use the CkMulticast delegation, one needs to create the CkMulticastMgr Group 
101 first, and then setup the delegation relationship between the section proxy and 
102 CkMulticastMgr Group. 
103 One only needs to create one CkMulticastMgr Group globally.
104 CkMulticastMgr group can serve all multicast/reduction delegations
105 for different array sections in an application:
106
107 \begin{alltt}
108   CProxySection_Hello sectProxy = CProxySection_Hello::ckNew(...);
109   CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew();
110   CkMulticastMgr *mCastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
111
112   sectProxy.ckSectionDelegate(mCastGrp);  // initialize section proxy
113
114   sectProxy.someEntry(...)           //multicast via delegation library as before
115 \end{alltt}
116
117 By default, CkMulticastMgr group builds a spanning tree for multicast/reduction
118 with a factor of 2 (binary tree).
119 One can specify a different factor when creating a CkMulticastMgr group.
120 For example,
121
122 \begin{alltt}
123   CkGroupID mCastGrpId = CProxy_CkMulticastMgr::ckNew(3);   // factor is 3
124 \end{alltt}
125
126 Note, to use CkMulticast library, all multicast messages must inherit from 
127 CkMcastBaseMsg, as the following.
128 Note that CkMcastBaseMsg must come first, this is IMPORTANT for CkMulticast 
129 library to retrieve section information out of the message.
130
131
132 \begin{alltt}
133 class HiMsg : public CkMcastBaseMsg, public CMessage_HiMsg
134 \{
135 public:
136   int *data;
137 \};
138 \end{alltt}
139
140 Due to this restriction, you must define message explicitly for multicast 
141 entry functions and no parameter marshalling can be used for multicast with 
142 CkMulticast library.
143
144 \subsection{Array Section Reduction} 
145
146 Since an array element can be a member of multiple array sections, 
147 it is necessary to disambiguate between which array
148 section reduction it is participating in each time it contributes to one. For this purpose, a data structure 
149 called ''CkSectionInfo'' is created by CkMulticastMgr for each 
150 array section that the array element belongs to.
151 During a section reduction, the array element must pass the 
152 \kw{CkSectionInfo} as a parameter in the \kw{contribute()}. 
153 The \kw{CkSectionInfo} for a section can be retrieved
154 from a message in a multicast entry point using function call 
155 \kw{CkGetSectionInfo}:
156
157 \begin{alltt}
158   CkSectionInfo cookie;
159
160   void SayHi(HiMsg *msg)
161   \{
162     CkGetSectionInfo(cookie, msg);     // update section cookie every time
163     int data = thisIndex;
164     mcastGrp->contribute(sizeof(int), &data, CkReduction::sum_int, cookie);
165   \}
166 \end{alltt}
167
168 Note that the cookie cannot be used as a one-time local variable in the 
169 function, the same cookie is needed for the next contribute. This is 
170 because the cookie includes some context sensive information (e.g., the 
171 reduction counter). Subsequent invocations of \kw{CkGetSectionInfo()} only updates part of the data in the cookie, rather than creating a brand new one.
172
173 Similar to array reduction, to use section based reduction, a
174 reduction client CkCallback object must be created. You may pass the
175 client callback as an additional parameter to \kw{contribute}. If
176 different contribute calls to the same reduction operation pass
177 different callbacks, some (unspecified, unreliable) callback will be
178 chosen for use. 
179
180 See the following example:
181
182 \begin{alltt}
183     CkCallback cb(CkIndex_myArrayType::myReductionEntry(NULL),thisProxy); 
184     mcastGrp->contribute(sizeof(int), &data, CkReduction::sum_int, cookie, cb);
185 \end{alltt}
186
187 If no member passes a callback to contribute, the reduction will use the 
188 default callback. You set the default callback for an array section using the 
189 \kw{setReductionClient} call in the section root member. A 
190 {\bf CkReductionMsg} message will be passed to this callback, which 
191 must delete the message when done.
192
193 \begin{alltt}
194   CProxySection_Hello sectProxy;
195   CkMulticastMgr *mcastGrp = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
196   mcastGrp->setReductionClient(sectProxy, new CkCallback(...));
197 \end{alltt}
198
199 As in an array reduction, users can use built-in reduction 
200 types(Section~\ref{builtin_reduction}) or define his/her own reducer functions
201 (Section~\ref{new_type_reduction}).
202
203 \subsection{Array section multicast/reduction when migration happens}
204
205 Using multicast/reduction, you don't need to worry about array migrations.
206 When migration happens, array element in the array section can still use 
207 the \kw{CkSectionInfo} it stored previously for doing reduction. 
208 Reduction messages will be correctly delivered but may not be as efficient 
209 until a new multicast spanning tree is rebuilt internally 
210 in \kw{CkMulticastMgr} library. 
211 When a new spanning tree is rebuilt, a updated \kw{CkSectionInfo} is 
212 passed along with a multicast message, 
213 so it is recommended that 
214 \kw{CkGetSectionInfo()} function is always called when a multicast 
215 message arrives (as shown in the above SayHi example).
216
217 In case when a multicast root migrates, the library must reconstruct the 
218 spanning tree to get optimal performance. One will get the following
219 warning message if not doing so:
220 "Warning: Multicast not optimized after multicast root migrated."
221 In current implementation, user needs to initiate the rebuilding process
222 using \kw{resetSection}.
223
224 \begin{alltt}
225 void Foo::pup(PUP::er & p) {
226     // if I am multicast root and it is unpacking
227    if (ismcastroot && p.isUnpacking()) {
228       CProxySection_Foo   fooProxy;    // proxy for the section
229       CkMulticastMgr *mg = CProxy_CkMulticastMgr(mCastGrpId).ckLocalBranch();
230       mg->resetSection(fooProxy);
231         // you may want to reset reduction client to root
232       CkCallback *cb = new CkCallback(...);
233       mg->setReductionClient(mcp, cb);
234    }
235 }
236 \end{alltt}
237
238 \subsection{Cross Array Sections}
239 \label{cross array section}
240 \experimental{}
241
242 Cross array sections contain elements from multiple arrays.
243 Construction and use of cross array sections is similar to normal
244 array sections with the following restrictions.  
245
246 \begin{itemize}
247
248 \item Arrays in a section my all be of the same type.
249
250 \item Each array must be enumerated by array ID
251
252 \item The elements within each array must be enumerated explicitly
253
254 \item No existing modules currently support delegation of cross
255   section proxies.  Therefore reductions are not currently supported.
256
257 \end{itemize}
258
259 Note: cross section logic also works for groups with analogous characteristics.
260
261 Given three arrays declared thusly:
262
263 \begin{alltt}
264           CkArrayID *aidArr= new CkArrayID[3];
265           CProxy\_multisectiontest\_array1d *Aproxy= new CProxy\_multisectiontest\_array1d[3];
266           for(int i=0;i<3;i++)
267             \{
268               Aproxy[i]=CProxy\_multisectiontest\_array1d::ckNew(masterproxy.ckGetGroupID(),ArraySize);   
269               aidArr[i]=Aproxy[i].ckGetArrayID();
270             \}
271 \end{alltt}
272
273 One can make a section including the  lower half elements of all three
274 arrays as follows:
275
276 \begin{alltt}
277           int aboundary=ArraySize/2;
278           int afloor=aboundary;
279           int aceiling=ArraySize-1;
280           int asectionSize=aceiling-afloor+1;
281           // cross section lower half of each array
282           CkArrayIndex **aelems= new CkArrayIndex*[3];
283           aelems[0]= new CkArrayIndex[asectionSize];
284           aelems[1]= new CkArrayIndex[asectionSize];
285           aelems[2]= new CkArrayIndex[asectionSize];
286           int *naelems=new int[3];
287           for(int k=0;k<3;k++)
288             \{
289               naelems[k]=asectionSize;
290               for(int i=afloor,j=0;i<=aceiling;i++,j++)
291                 aelems[k][j]=CkArrayIndex1D(i);
292             \}
293           CProxySection\_multisectiontest\_array1d arrayLowProxy(3,aidArr,aelems,naelems);
294 \end{alltt}
295
296
297
298 The resulting cross section proxy, as in the example \uw{arrayLowProxy},
299 can then be used for multicasts in the same way as a normal array
300 section.
301
302 Note: For simplicity the example has all arrays and sections of uniform
303 size.  The size of each array and the number of elements in each array
304 within a section can all be set independently.
305
306
307