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