Docs: refer to illinois.edu, not uiuc.edu
[charm.git] / doc / charm++ / commlib.tex
1 \subsection{Communication Optimizations Framework}
2
3 The communication framework in Charm++/Converse is aimed at optimizing certain
4 communication patterns. Currently the programmer has to specify the
5 communication pattern it intends to optimize, together with the strategy to be
6 used. The communications library uses the delegation framework
7 (\ref{delegation}) in order to enable easy and transparent access to the
8 framework by the programmer.
9
10 For \ampi{} programs, the communication optimization is done by the \ampi{}
11 layer, so that the user does not need to worry about that. In Charm++, however,
12 the user must create the strategies in the program explicitly. Charm++ programs
13 are normally based on communicating arrays of chares, that compute and then
14 invoke entry methods on local or remote chares by sending them messages. These
15 array elements send messages to each other through proxies. The messages are
16 passed to the Charm++ runtime which calls lower level network APIs to
17 communicate. To optimize communication in Charm++, the user can redirect a
18 communication {\em call} to go through an instance of a strategy.
19
20 To access the communication framework, the user first creates and initializes a
21 communication library strategy. He then needs to make a copy of the array proxy
22 and associate it with that strategy. In order to use the framework, the
23 receiving entry methods need to receive messages (see \ref{messages}), and not
24 marshalled parameters. The user can create several instances of the same or
25 different strategies, to optimize different communication calls in the
26 application. In order to access the class signatures, the file ``comlib.h''
27 should be included.
28
29 Each communication operation is associated with a proxy, through which the
30 message is sent. These proxies can be associated in the mainchare constructor
31 (useful for all-to-all strategies), or later in the single chare
32 array elements (useful for section multicasts). In both cases, some
33 information has to be kept, either the CProxy or the ComlibInstanceHandle, and
34 this can be done in readonly variables, or as internal variables of the objects.
35
36 An example on how to use commlib can be found in the charm distribution, under
37 \examplerefdir{commlib/multicast}, where the proxies are associated in the
38 chare arrays.
39
40
41 \subsubsection{Using commlib}
42
43 One thing typically useful is having the the proxy associated with the strategy,
44 or an instance of the strategy (to be used for future associations) to be
45 declared as readonly variable, although this in not necessary. This is done by
46 declaring them readonly (see \ref{readonly} for more information).
47
48 \begin{alltt}
49   readonly CProxy\_MyArray aproxy;
50   readonly CProxy\_MyArray comlibproxy;
51   readonly ComlibInstanceHandle cinst;
52 \end{alltt}
53
54 The creation of all the strategies needed, and their registration must be done
55 in the constructor of the mainchare (for more on array creation see
56 \ref{advanced array create}):
57
58 \begin{alltt}
59   // Create the array
60   aproxy = CProxy\_MyArray::ckNew();
61
62   // Create the strategy (description of constructors later)
63   CharmStrategy *strategy = new EachToManyMulticastStrategy(USE_MESH, srcarray, destarray);
64   //or
65   CharmStrategy *strategy = new StreamingStrategy(10,10);
66
67   // Either associate the strategy with the proxy we declared, or register the
68   // strategy to commlib for future association, or both.
69   comlibproxy = aproxy;
70   ComlibAssociateProxy(strategy, comlibproxy);
71
72   cinst = ComlibRegister(strategy);
73 \end{alltt}
74
75 In this example, after aproxy has been associated with comlibproxy it can only be
76 used with commlib, and cannot send anymore regular messages. For this, if
77 regular messages without commlib are desired, a copy of the original proxy
78 should be made (like here).
79
80 In the chare array element, if {\texttt{cinst}} has been defined, other proxies
81 can be created and associated, like here a CProxySection\_MyArray, which allows
82 to send multicasts (see \ref{array section} for more on section proxies).
83
84 \begin{alltt}
85   CProxySection\_MyArray mysection = .....
86   ComlibAssociateProxy(\&cinst, mysection);  // mysection will always use commlib
87 \end{alltt}
88
89 After a proxy has been associated in some way to commlib, it can be used to send
90 messages with commlib:
91
92 \begin{alltt}
93   comlibproxy.receive(msg); // send with commlib
94   mysection.compute(msg);   // send to a section with commlib
95
96   aproxy[0].single(msg);    // send to a single element {\textbf{without}} commlib
97 \end{alltt}
98
99 In case a bracketed strategy is used, two additional function calls have to
100 be added before starting to send the messages and after finishing. These are
101 discussed later in \ref{bracketed strategies}.
102
103 The signatures of the functions used here are the following:
104
105 \begin{alltt}
106 ComlibRegister (CharmStrategy *strat);
107 ComlibAssociateProxy (CharmStrategy *strat, CProxy &proxy);
108 ComlibAssociateProxy (ComlibInstanceHandle *cinst, CProxy &proxy);
109 \end{alltt}
110
111 %% \ subsubsection{Proxy interface}
112
113 %% A proxy containing the delegation should be kept, and reused every time the
114 %% associated stragety wants to be used.
115
116 %% \ begin{enumerate}
117 %% \ item main.C global
118 %% \ begin{alltt}
119 %% // Include the appropriate header file
120 %% #include <EachToManyMulticastStrategy.h>
121 %% #include <StreamingStrategy.h>
122
123 %% // Declare the global variable
124 %% CProxy_MyArray aproxy;
125 %% CProxy_MyArray dproxy;
126 %% \ end{alltt}
127
128 %% \ item main.C:main()
129 %% \ begin{alltt}
130 %% // Create the array
131 %% aproxy = CProxy_Hello::ckNew();
132
133 %% // Create the strategy (description of constructors later)
134 %% CharmStrategy *strategy = new EachToManyMulticastStrategy(USE_MESH, srcarray, destarray);
135 %% //or
136 %% CharmStrategy *strategy = new StreamingStrategy(10,10);
137
138 %% // Register the strategy to a new proxy, so that aproxy is without commlib,
139 %% // while dproxy uses it
140 %% dproxy = aproxy;
141 %% ComlibAssociateProxy(strategy, dproxy);
142 %% \ end{alltt}
143
144 %% \ item In the array element
145 %% \ begin{alltt}
146 %% // First proxy should be delegated
147 %% ComlibBeginIteration(dproxy);   // Only for bracketed strategies
148 %% dproxy[index].entry(message);   // Sending a message
149 %% .....     //sending more messages
150 %% .....
151 %% aproxy[index].entry2{message2); // Send a message without commlib
152 %% ComlibEndIteration(dproxy);     // Only for bracketed strategies
153 %% \ end{alltt}
154 %% \ end{enumerate}
155
156 %% The above example shows the usage of EachToManyStrategy. Notice the
157 %% ComlibBeginIteration and ComlibEndIteration calls, needed for bracketed
158 %% strategies. The construction of the strategies has been done in tha main::main,
159 %% from where they are broadcasted and initialized in every processor before being
160 %% used.
161
162 %% \ subsubsection{Instance interface}
163
164 %% In this interface, the chares need to keep information about the commlib instance.
165
166 %% \ begin{enumerate}
167 %% \ item main.C global
168 %% \ begin{alltt}
169 %% // Include the appropriate header file
170 %% #include <EachToManyMulticastStrategy.h>
171 %% #include <StreamingStrategy.h>
172
173 %% // Declare the global variable
174 %% CProxy_MyArray aproxy;
175 %% ComlibInstanceHandle cinst;
176 %% \ end{alltt}
177
178 %% \ item main.C:main()
179 %% \ begin{alltt}
180 %% // Create the array
181 %% aproxy = CProxy_Hello::ckNew();
182
183 %% // Create your strategy
184 %% Strategy *strategy = new EachToManyStrategy(USE_MESH, srcarray, destarray);
185 %% //or
186 %% Strategy *strategy = new StreamingStrategy(10,10);
187
188 %% // Create a Communication Library Instance
189 %% cinst = CkGetComlibInstance();
190
191 %% // Register the strategy
192 %% cinst.setStrategy(strategy);
193 %% \ end{alltt}
194
195 %% \ item In the array element 
196 %% \ begin{alltt}
197 %% // Before calling an entry method whose message should go thorough the
198 %% // library the proxy has to be delegated. Create a new copy of the
199 %% // proxy and delegate it before using it.
200 %% CProxy_Hello dproxy = aproxy;
201 %% ComlibDelegateProxy(&dproxy); //Now all calls to dproxy will go through the library.
202
203 %% cinst.beginIteration();       // Only for bracketed strategies
204 %% dproxy[index].entry();        // Send a message
205 %% .....
206 %% .....
207 %% aproxy[index].entry2();       // Send a message without commlib
208 %% cinst.endIteration();         // Only for bracketed strategies
209 %% \ end{alltt}
210 %% \ end{enumerate}
211
212 %% \ subsubsection{Sections}
213
214 %% In order to multicast only to a part of the array instead of the entire array,
215 %% it is necessary to create a {\ textrm{CProxySection\ _class}}
216 %% (\ ref{array_section_multicast}) of the desired portion of the destination array,
217 %% delegate it with {\ textrm{ComlibAssociateProxy()}}, and send a broadcast to it.
218 %% This broadcast on the section will result in the desired multicast on the global
219 %% array. Only multicast strategies can be used for this.
220
221
222 \subsubsection{Loadbalancing and Migration support}
223
224 The Communication optimization framework supports both loadbalancing and array
225 migration. It enables migration through message forwarding. Messages sent by a
226 migrated array are forwarded to the processor where it is mapped to, and from
227 here they get accounted. Messages sent to migrated arrays are forwarded from the
228 processor where they are mapped to their current destination.
229
230 This mapping of array elements to processors can be updated by the user by
231 calling {\textrm{ComlibResetProxy}} for array proxies, and
232 {\textrm{ComlibResetSectionProxy}} for section proxies. This should be done
233 especially during load-balancing, where most of the migrations happen. As shown
234 in the following example, these calls should be made inside the
235 {\textrm{resumeFromSync}} method.
236
237 \begin{alltt}
238   void arrayelement::resumeFromSync() {
239       .......
240       .......
241       ComlibResetProxy(comlibproxy);
242       ComlibResetSectionProxy(mysection);
243   }
244 \end{alltt}
245
246 A migrating array element containing {\em associated proxies} or {\em
247 instances} should pup them all at the source and destination.
248
249 \begin{alltt}
250   void arrayelement::pup(PUP::er &p){
251       ..........
252       ..........
253       p | mysection;
254       p | cinst;
255   }
256 \end{alltt}
257
258 \subsubsection{Compiling User Code}
259
260 All user programs that use the communication library should use the
261 linker option {\textrm{-module comlib}. For example,
262 \begin{alltt}
263 charmc -o pgm pgm.o -module comlib
264 \end{alltt}
265
266
267 \subsubsection{Supported Operations and Strategies}
268
269 The communication framework now supports four different communication
270 operations:
271 \begin{enumerate}
272 \item all-to-all/many-to-many communication,
273 \item array and group broadcast,
274 \item section multicast,
275 \item streaming.
276 \end{enumerate}
277 Table~\ref{tbl:com_operation} shows the different strategies that optimize these
278 communication operations. Some of these are converse strategies while others are
279 charm strategies. In the following paragraphs, we present in detail the
280 strategies optimizing the above mentioned operations.
281
282 \begin{table}[h]
283 \begin{center}
284 \begin{small}
285 \begin{tabular}{|c|c|c|}
286 \hline
287 {\bf Operation} & {\bf Object Strategy} & {\bf Processor Strategy} \\
288 \hline
289 \begin{tabular}{c}
290 All-to-All/Many-to-many \\
291 personalized and multicast
292 \end{tabular}
293  & EachToManyMulticastStrategy & Mesh, Grid, Hypercube, Direct \\
294 %Many-to-many  multicast    & EachToManyMulticastStrategy & Mesh, Grid, Hypercube, Direct \\
295 Broadcast  & BroadcastStrategy, PipeBroadcastStrategy & Binomial tree, Binary tree\\
296 Section Multicast &
297 \begin{tabular}{c}
298 DirectMulticastStrategy, RingMulticastStrategy,\\
299 MultiRingMulticast
300 \end{tabular} & \\
301 Streaming  & Streaming, MeshStreaming, PrioStreaming & \\
302 \hline
303 \end{tabular}
304 \end{small}
305 \end{center}
306 \caption{Communication Operations supported in the Framework}
307 \label{tbl:com_operation}
308 \end{table}
309
310 There are two types of strategies in the communication framework:
311
312 \begin{itemize}
313
314 \item \label{bracketed strategies}
315 Bracketed Strategies: In bracketed strategies each source chare (which could be
316 an array element or a group) deposits its entries and then the strategy performs
317 the communication optimization. For example the EachToManyMulticastStrategy is a
318 bracketed strategy. For bracketed strategies a beginIteration and an
319 endIteration must be called before and after making the deposits respectively.
320
321 The usage of the strategy becomes:
322
323 \begin{alltt}
324 ComlibBegin(dproxy);
325
326 dproxy[index].entry(message);   // Sending a message
327 .....     //sending more messages
328 .....
329
330 ComlibEnd(dproxy);
331 \end{alltt}
332
333 \item Non-Bracketed Strategies: Non-bracketed strategies perform communication
334 optimizations without needing calls to beginIteration and endIteration to start
335 processing. Non-bracketed strategies either immediately process messages or
336 after a timeout, and, in both cases, it's not triggered from the application.
337
338 \end{itemize}
339
340
341 \subsubsection{Many-to-many Strategies}
342
343 The class {\em EachToManyMulticastStrategy} optimizes both all-to-all
344 personalized and all-to-all multicast communication using several virtual
345 topologies like 2-D Mesh, 3-D Mesh and Hypercube. Personalized communication
346 happens when a chare sends different messages to the other chares, multicast
347 communication happens when a chare sends the same message to all other chares.
348 EachToManyMulticastStrategy also optimizes the special cases of many-to-many multicast where
349 not all the chares in an array are involved in the collective operation.
350
351 The charm level strategy collects all the messages from the chares and delivers
352 them to the destination, while the low level (processor-to-processor)
353 communication is performed through converse level {\em routers} and
354 implements the various virtual topologies.
355
356 %For example, with the mesh router, the strategy on each processor
357 %first sends messages to its row neighbors. After having received its row
358 %messages each processor sends the column messages. After having received the
359 %column messages an iteration of the strategy finishes. All local messages are
360 %delivered as soon they are received.
361
362 %{\em EachToManyMulticastStrategy} is also used to optimize all-to-all multicast
363 %communication, where a processor sends the same message to all others, using the
364 %same virtual topologies at the lower level.
365
366 EachToManyMulticastStrategy requires that all local messages be deposited
367 before they can be packed into single messages. Hence, it needs to be a {\em
368 bracketed} strategy. This strategy can also be used to optimize all-to-all collectives between charm
369 groups.
370
371 %Bracketed strategies require each of the participating objects to deposit their
372 %intended messages within brackets. Calls to {\em ComlibBeginIteration} and {\em
373 %ComlibEndIteration} create a bracket. The call ComlibBeginIteration sets up the
374 %delegation framework to forward user messages to the correct strategy instance.
375 %User messages then get passed to the insertMessage entry function of the
376 %strategy. When all local objects have called ComlibEndIteration, doneInserting
377 %is invoked on the strategy.
378
379 %Bracketed strategies are typically needed when the communication
380 %optimization requires local source objects to reach a barrier. At this
381 %local barrier the communication framework invokes doneInserting on
382 %that strategy, which the calls the converse level strategy.
383
384 %Non-bracketed strategies have no such restriction. They process
385 %messages as soon as they arrive. so, non-bracketed strategies should
386 %not expect a doneInserting to be invoked on them. They must all
387 %process messages in the insertMessage call itself.
388
389 As for the constructors to be used in the main chare, the two prototypes follow.
390 The first one is for groups, the second for arrays. The optional parameters
391 allow to specify the many-to-many behaviour, passing the lists of source and
392 destination elements participating in the operation. If they are left to the
393 default value, the collective is an all-to-all.
394
395 \begin{alltt}
396 EachToManyMulticastStrategy(int substrategy, int nsrcpes=0, int *srcpelist=0,
397                             int ndestpes=0, int *destpelist=0);
398
399 EachToManyMulticastStrategy(int substrategy, CkArrayID src, CkArrayID dest,
400                             int nsrc=0, CkArrayIndex *srcelements=0,
401                             int ndest=0, CkArrayIndex *destelements=0);
402 \end{alltt}
403
404 Both have as first parameter the virtual topology that the strategy will use for
405 the low level optimization. The possible values are:
406
407 \begin{description}
408 \item[USE\_DIRECT] to send messages directly;
409 \item[USE\_MESH] to send messages across a 2D Mesh;
410 \item[USE\_GRID] to send messages across a 3D Grid;
411 \item[USE\_HYPERCUBE] to send messages across a Hypercube.
412 \end{description}
413
414 USE\_HYPERCUBE will do best for very small messages and small number of
415 processors, 3d has better performance for slightly higher message sizes and then
416 Mesh starts performing best. The programmer is encouraged to try out all the
417 topologies.
418
419
420 \subsubsection{Broadcast Strategies}
421
422 There are two strategies of this type: {\em BroadcastStrategy} and {\em
423 PipeBroadcastStrategy}. The first works only for group broadcast, while the
424 second works for both groups and arrays.
425
426 BroadcastStrategy performs a broadcast through a hypercube (default) or a tree,
427 and the constructor is:
428
429 \begin{alltt}
430 BroadcastStrategy(int topology=USE_HYPERCUBE);
431 \end{alltt}
432
433 PipeBroadcastStrategy performs a broadcast through a ring or a hypercube
434 (default). The characteristic of this strategy is that it fragments the message
435 into small chunks that fit a predetermined size (passed as argument to the
436 constructor), and it reassembles them before delivery. The constructor
437 prototypes for groups and arrays respectively are:
438
439 \begin{alltt}
440 PipeBroadcastStrategy(int topology, CkArrayID aid, int pipeSize=DEFAULT_PIPE);
441 PipeBroadcastStrategy(CkGroupID gid, int topology=USE_HYPERCUBE, int pipeSize=DEFAULT_PIPE);
442 \end{alltt}
443
444
445 \subsubsection{Section Multicast Strategies}
446
447 The subclasses of MulticastStrategy can multicast a message to the entire array
448 or a section of array elements (MulticastStrategy itself is abstract). The
449 multicast strategies are non-bracketed, and the message is processed when the
450 application deposits it. These strategies do not combine messages, but they may
451 sequence the destinations of the multicast to minimize contention on a network.
452
453 In order to use these strategies, the message sent must inherit from class
454 {\textrm{CkMcastBaseMsg}}. (For an example see
455 \examplerefdir{commlib/multicast}).
456
457 These are the subclass strategies that are available:
458
459 \begin{description}
460 \item[DirectMulticastStrategy] sends the messages directly to all recipients;
461 \item[RingMulticastStrategy] sends the messages along ring resulting in good throughput as the ring permutation is contention free on many communication topologies;
462 \item[MultiRingMulticast] sends the message along two rings (the ordered list of recipients is split in half).
463 \end{description}
464
465 For these, the constructors are of the form:
466
467 \begin{alltt}
468 DirectMulticastStrategy(CkArrayID aid, int flag=0);
469 RingMulticastStrategy(CkArrayID dest_id, int flag=0);
470 MultiRingMulticast(CkArrayID dest_id, int flag=0);
471 \end{alltt}
472
473 For section multicast, the user must create a section proxy and delegate it to
474 the communication library. Invocations on section proxies are passed on to the
475 section multicast strategy.
476
477
478 \subsubsection{Streaming Strategies}
479
480 This strategy optimizes the scenario where chares send several small messages to
481 other chares. The StreamingStrategy collects messages destined to the same
482 physical processor and, after a timeout or when a certain number of messages
483 have been collected, it sends them as a single message. This results in sending
484 fewer messages of larger size. The timeout is a floating-point parameter to the
485 StreamingStrategy. It needs to be specified in milliseconds, with a default
486 value of 1ms. Micro-second timeouts can also be specified by passing values less
487 than 1. For example, $0.1$ represents $100\mu s$.
488
489 The Streaming Strategy is a non-bracketed strategy. Since messages can be
490 delayed due to the timeout present, it is possible to call
491 {\textrm{ComlibEnd()}} to flush all the messages to be sent immediately.
492
493 The prototype of the constructor is:
494
495 \begin{alltt}
496 StreamingStrategy(float period\_in\_ms, int nmsgs);
497 \end{alltt}
498
499 There are two variants of this strategy:
500
501 \begin{description}
502 \item[MeshStreamingStrategy] which sends the messages along a mesh instead of a linear array as the basic one;
503 \item[PrioStreaming] which looks at the priority of the messages, and sends those with a priority above a certain threshold directly, without delay. This strategy accepts a third parameter in the constructor for the threshold priority.
504 \end{description}
505
506
507 \subsubsection{Communication Optimization Development}
508
509 Optimization algorithms are implemented as Strategies in the communication
510 library. Strategies can be implemented at the Object (\charmpp) level or the
511 processor (\converse) level. Code reuse is possible by having a few object
512 managers perform object level optimizations and then call several other
513 processor level optimization schemes. For example, to optimize all-to-all
514 communication the processor level strategies could use the different virtual
515 topologies.
516
517 All processor (\converse) level strategies inherit from the {\em class~Strategy}
518 defined below and override its virtual methods.
519
520 \begin{alltt}
521 // Converse or Processor level strategy
522 class Strategy : public PUP::able{
523 public:
524     // Called for each message
525     virtual void insertMessage(MessageHolder *msg);
526     // Called after all chares and groups have finished depositing their
527     // messages on that processor.
528
529     virtual void doneInserting();
530     virtual void beginProcessing(int nelements);
531 };
532 \end{alltt}
533
534 The class method {\em insertMessage} is called to deposit messages with the
535 strategy. MessageHolder is a wrapper for converse messages. When a processor has
536 sent all its messages {\em doneInserting} is invoked on the strategy.
537
538 At the \charmpp{} level, all strategies inherit from the {\em
539 class~CharmStrategy} reported here.
540
541 \begin{alltt}
542 // Charm++ or Object level strategy
543 class CharmStrategy : public Strategy{
544  protected:
545     int isArray;
546     int isGroup;
547     int isStrategyBracketed;
548     ............   
549     ............   
550 public:
551     // Called for each message
552     virtual void insertMessage(CharmMessageHolder *msg);
553     // Called after all chares and groups have finished depositing their
554     // messages on that processor.
555     virtual void doneInserting();
556     virtual void beginProcessing(int nelements);
557 };
558 \end{alltt}
559
560 \charmpp{} level strategies also have to implement the insertMessage and
561 doneInserting methods. Here insertMessage takes a CharmMessageHolder which is a
562 \charmpp{} message wrapper. The call to beginProcessing initializes the strategies
563 on each processor. This additional call is needed because the constructor of the
564 strategy is called by user code in main::main on processor 0, while the strategy
565 needs to be constructed everywhere. Along with initializing its data,
566 beginProcessing can also register message handlers, as the communication library
567 strategies use Converse handlers to communicate between processors. The flags
568 {\em isArray} and {\em isGroup} store the type of objects that call the strategy
569 and the flag {\em isStrategyBracketed} specifies if the CharmStrategy is
570 bracketed or not. Bracketed strategies require that the application deposits
571 messages in brackets demarcated by the calls ComlibBegin and
572 ComlibEnd.