Docs: refer to illinois.edu, not uiuc.edu
[charm.git] / doc / charm++ / messages.tex
1 \section{Messages}
2
3 \label{messages}
4 Although \charmpp{} supports automated parameter marshalling for entry methods,
5 you can also manually handle the process of packing and unpacking parameters by
6 using messages. 
7 %By using messages, you can potentially improve performance by
8 %avoiding unnecessary copying. 
9 A message encapsulates all the parameters sent to an
10 entry method.  Since the parameters are already encapsulated,
11 sending messages is often more efficient than parameter marshalling, and
12 can help to avoid unnecessary copying.
13 Moreover, assume that the receiver is unable to process the contents of the
14 message at the time that it receives it. For example, consider a 
15 tiled matrix multiplication program, wherein each chare receives an $A$-tile
16 and a $B$-tile before computing a partial result for $C = A \times B$. If we 
17 were using parameter marshalled entry methods, a chare would have to copy the first
18 tile it received, in order to save it for when it has both the tiles it needs. 
19 Then, upon receiving the second
20 tile, the chare would use the second tile and the first (saved) tile to 
21 compute a partial result. However, using messages, we would just save a {\em pointer} 
22 to the message encapsulating the tile received first, instead of the tile data itself.
23
24 \vspace{0.1in}
25 \noindent
26 {\bf Managing the memory buffer associated with a message.}
27 As suggested in the example above, the biggest difference between marshalled parameters and messages
28 is that an entry method invocation is assumed to {\em keep} the message that it
29 is passed. That is, the \charmpp{} runtime system assumes that code in the body of the invoked
30 entry method will explicitly manage the memory associated with the message that it is passed. Therefore,
31 in order to avoid leaking memory, the body of an entry method must either \kw{delete} the message that
32 it is receives, or save a pointer to it, and \kw{delete} it a later point in the execution of the code.
33 %is code written for the body of an 
34 %either store the passed message or explicitly {\em delete} it, or else the message
35 %will never be destroyed, wasting memory.
36
37 Moreover, in the \charm{} execution model, once you pass a message buffer to the runtime system (via 
38 an asynchronous entry method invocation), you should {\em not} reuse the buffer. That is, after you have
39 passed a message buffer into an asynchronous entry method invocation, you shouldn't 
40 access its fields, or pass that same buffer into a second entry method invocation. Note that this rule
41 doesn't preclude the {\em single reuse} of an input message -- consider an entry method invocation
42 $i_1$, which receives as input the message buffer $m_1$. Then, $m_1$ may be passed to an 
43 asynchronous entry method invocation $i_2$. However, once $i_2$ has been issued with $m_1$ as its input
44 parameter, $m_1$ cannot be used in any further entry method invocations.
45 %message buffer, that message buffer may in turn be passed to an entry method invocation that accepts a 
46 %message of the same type. However, 
47  
48 %Thus each entry method must be passed a {\em new} message.
49
50 Several kinds of message are available.
51 Regular \charmpp{} messages are objects of
52 \textit{fixed size}. One can have messages that contain pointers or variable
53 length arrays (arrays with sizes specified at runtime) and still have these
54 pointers as valid when messages are sent across processors, with some
55 additional coding.  Also available is a mechanism for assigning
56 \textit{priorities} to a message regardless of its type.
57 A detailed discussion of priorities appears later in this section.
58
59 \subsection{Message Types}
60
61 \smallskip
62 \noindent {\bf Fixed-Size Messages.}
63 The simplest type of message is a {\em fixed-size} message. The size of each data member
64 of such a message should be known at compile time. Therefore, such a message may encapsulate
65 primitive data types, user-defined data types that {\em don't} maintain pointers to memory
66 locations, and {\em static} arrays of the aforementioned types. 
67
68 \smallskip
69 \noindent {\bf Variable-Size Messages.}
70 %An ordinary message in \charmpp\ is a fixed size message that is allocated
71 %internally with an envelope which encodes the size of the message. 
72 Very often,
73 the size of the data contained in a message is not known until runtime. 
74 %One can
75 %use packed\index{packed messages} messages to alleviate this problem.  However,
76 %it requires multiple memory allocations (one for the message, and another for
77 %the buffer.) 
78 For such scenarious, you can use variable-size (\emph{varsize}) messages.
79 A {\em varsize} message can encapsulate several arrays,
80 each of whose size is determined at run time. 
81 %In \emph{varsize} messages, 
82 The space required for these encapsulated, variable length arrays
83 is allocated with the entire message comprises a 
84 contiguous buffer of memory.
85 %message such that it is contiguous to the message.
86
87 \smallskip
88 \noindent {\bf Packed Messages.} A {\em packed} message is used to communicate non-linear
89 data structures via messages. However, we defer a more detailed description of their use
90 to \S~\ref{sec:messages/packed_msgs}.
91
92 \subsection{Using Messages In Your Program}
93
94 There are five steps to incorporating a (fixed or varsize) message type in your \charmpp{} program:
95 (1) Declare message type in \kw{.ci} file; (2) Define message type in \kw{.h} file;
96 (3) Allocate message; (4) Pass message to asynchronous entry method invocation and (5) Deallocate
97 message to free associated memory resources. 
98
99 \medskip
100 \noindent {\bf Declaring Your Message Type.}
101 Like all other entities involved in asynchronous entry method invocation, messages
102 must be declared in the {\tt .ci} file. 
103 This allows the \charmpp{} translator 
104 to generate support code for messages. 
105 Message declaration is straightforward for fixed-size messages. Given a 
106 message of type {\tt MyFixedSizeMsg}, simply include the following in the \kw{.ci} file:
107
108 \begin{alltt}
109  message MyFixedSizeMsg;
110 \end{alltt}
111
112 For varsize messages, the \kw{.ci} declaration must also include the names and
113 types of the variable-length arrays that the message will encapsulate. The
114 following example illustrates this requirement. In it, a message of type {\tt
115 MyVarsizeMsg}, which encapsulates three variable-length arrays of different
116 types, is declared:
117
118 \begin{alltt}
119  message MyVarsizeMsg \{
120    int arr1[];
121    double arr2[];
122    MyPointerlessStruct arr3[];
123  \};
124 \end{alltt}
125
126 \medskip
127 \noindent {\bf Defining Your Message Type.}
128 Once a message type has been declared to the \charmpp{} translator, its type definition must be provided.
129 Your message type must inherit from a specific generated base class. If the type of 
130 your message is {\tt T}, then {\tt class T} must inherit from {\tt CMessage\_T}.
131 This is true for both fixed and varsize messages.
132 As an example, for our fixed size message
133 type {\tt MyFixedSizeMsg} above, we might write the following in the \kw{.h} file:
134
135 \begin{alltt}
136 class MyFixedSizeMsg : public CMessage_MyFixedSizeMsg \{
137   int var1;
138   MyPointerlessStruct var2;
139   double arr3[10];
140
141   // Normal C++ methods, constructors, etc. go here
142 \};
143 \end{alltt}
144
145 In particular, note the inclusion of the static array of {\tt double}s, {\tt arr3}, whose size
146 is known at compile time to be that of ten {\tt double}s.
147 Similarly, for our example varsize message of type {\tt MyVarsizeMsg}, we would write something
148 like:
149
150 \begin{alltt}
151 class MyVarsizeMsg : public CMessage_MyVarsizeMsg \{
152   // variable-length arrays
153   int *arr1;
154   double *arr2;
155   MyPointerlessStruct *arr3;
156   
157   // members that are not variable-length arrays 
158   int x,y;
159   double z;
160
161   // Normal C++ methods, constructors, etc. go here
162 \};
163 \end{alltt}
164
165 Note that the \kw{.h} definition of the class type must contain data members
166 whose names and types match those specified in the \kw{.ci} declaration.  In
167 addition, if any of data members are \kw{private} or \kw{protected}, it should
168 declare class \uw{CMessage\_MyVarsizeMsg} to be a \kw{friend} class.  Finally,
169 there are no limitations on the member methods of message classes, except that
170 the message class may not redefine operators \texttt{new} or \texttt{delete}.
171
172
173 Thus the \uw{mtype} class
174 declaration should be similar to:
175
176 \medskip
177 \noindent {\bf Creating a Message.}
178 With the \kw{.ci} declaration and \kw{.h} definition in place, messages can be allocated and 
179 used in the program.
180 \index{message}Messages are allocated using the \CC\ \kw{new} operator:
181
182 \begin{alltt}
183  MessageType *msgptr =
184   new [(int sz1, int sz2, ... , int priobits=0)] MessageType[(constructor arguments)];
185 \end{alltt}
186
187 The arguments enclosed within the square brackets are optional, and 
188 are used only when allocating messages
189 with variable length arrays or prioritized messages.
190 These arguments are not specified for fixed size messages. 
191 For instance, to allocate a message of our example message 
192 {\tt MyFixedSizeMsg}, we write:
193
194 \begin{alltt}
195 MyFixedSizeMsg *msg = new MyFixedSizeMsg(<constructor args>);
196 \end{alltt}
197
198 In order to allocate a varsize message, we must pass appropriate
199 values to the arguments of the overloaded \kw{new} operator presented previously. 
200 Arguments \uw{sz1, sz2, ...}
201 denote the size (in number of elements) of the memory blocks that need to be
202 allocated and assigned to the pointers (variable-length arrays) that the message contains. The
203 \uw{priobits} argument denotes the size of a bitvector (number of bits) that
204 will be used to store the message priority.   
205 So, if we wanted to create {\tt MyVarsizeMsg} whose 
206 {\tt arr1},  {\tt arr2} and {\tt arr3} arrays contain
207 10, 20 and 7 elements of their respective types, we would write:
208
209 \begin{alltt}
210 MyVarsizeMsg *msg = new (10, 20, 7) MyVarsizeMsg(<constructor args>);
211 \end{alltt}
212
213 %This allocates a \uw{VarsizeMessage}, in which \uw{firstArray} points to an
214 %array of 10 ints and \uw{secondArray} points to an array of 20 doubles.  This
215 %is explained in detail in later sections. 
216
217 Further, to add a 32-bit \index{priority}priority bitvector to this message, we would write:
218
219 \begin{alltt}
220 MyVarsizeMsg *msg = new (10, 20, 7, sizeof(uint32_t)*8) VarsizeMessage;
221 \end{alltt}
222
223 Notice the last argument to the overloaded \kw{new} operator, which specifies 
224 the number of bits used to store message priority.
225 The section on prioritized execution (\S~\ref{prioritized message passing}) describes how
226 priorities can be employed in your program.
227
228 Another version of the overloaded \kw{new} operator allows you to pass in
229 an array containing the size of each variable-length array, rather than specifying 
230 individual sizes as separate arguments. 
231 For example, we could create a message of type {\tt MyVarsizeMsg} in the following manner:
232
233 \begin{alltt}
234 int sizes[3];
235 sizes[0] = 10;               // arr1 will have 10 elements
236 sizes[1] = 20;               // arr2 will have 20 elements 
237 sizes[2] = 7;                // arr3 will have 7 elements 
238
239 MyVarsizeMsg *msg = new(sizes, 0) MyVarsizeMsg(<constructor args>); // 0 priority bits
240 \end{alltt}
241
242 %In Section~\ref{message packing} we explain how messages can contain arbitrary
243 %pointers, and how the validity of such pointers can be maintained across
244 %processors in a distributed memory machine.
245
246
247 \medskip
248 \noindent {\bf Sending a Message.}
249 Once we have a properly allocated message, 
250 we can set the various elements of the encapsulated arrays in the following manner:
251
252 \begin{alltt}
253   msg->arr1[13] = 1;
254   msg->arr2[5] = 32.82;
255   msg->arr3[2] = MyPointerlessStruct();
256   // etc.
257 \end{alltt}
258
259 And pass it to an asynchronous entry method invocation, thereby sending it to the 
260 corresponding chare:
261
262 \begin{alltt}
263 myChareArray[someIndex].foo(msg);
264 \end{alltt}
265
266 When a message \index{message} is {\em sent}, i.e.  passed to an asynchronous
267 entry method invocation, the programmer relinquishes control of it; the space
268 allocated for the message is freed by the runtime system.  However, when a
269 message is {\em received} at an entry point, it is {\em not} freed by the
270 runtime system.  As mentioned at the start of this section, received
271 messages may be reused or deleted by the programmer.  Finally, messages are
272 deleted using the standard \CC{} \kw{delete} operator.  
273
274 \zap{
275 \subsubsection{Messages with Variable Length Arrays}
276
277 \label{varsize messages}
278 \index{variable size messages}
279 \index{varsize message}
280
281 Such a message is declared as 
282
283 \begin{alltt}
284  message mtype \{
285    type1 var_name1[];
286    type2 var_name2[];
287    type3 var_name3[];
288  \};
289 \end{alltt}
290
291 in \charmpp\ interface file. 
292 \begin{alltt}
293 class mtype : public CMessage_mtype \{
294  private:
295    type1 *var_name1;
296    type2 *var_name2;
297    type3 *var_name3;
298    friend class CMessage_mtype;
299 \};
300 \end{alltt}
301
302 \small
303 \hrule
304
305 \noindent\textbf{An Example}
306
307 Suppose a \charmpp\ message contains two variable length arrays of types
308 \texttt{int} and \texttt{double}:
309
310 \begin{alltt} 
311 class VarsizeMessage: public CMessage_VarsizeMessage \{
312   public:
313     int lengthFirst;
314     int lengthSecond;
315     int* firstArray;
316     double* secondArray;
317     // other functions here
318 \};
319 \end{alltt}
320
321 Then in the \texttt{.ci} file, this has to be declared as: 
322
323 \begin{alltt}
324 message VarsizeMessage \{
325   int firstArray[];
326   double secondArray[];
327 \};
328 \end{alltt}
329
330 We specify the types and actual names of the fields that
331 contain variable length arrays. The dimensions of these arrays are NOT
332 specified in the interface file, since they will be specified in the
333 constructor of the message when message is created. In the {\tt .h} or {\tt .C}
334 file, this class is declared as:
335
336 \begin{alltt} 
337
338 class VarsizeMessage : public CMessage_VarsizeMessage \{ 
339   public: 
340     int lengthFirst;
341     int lengthSecond;
342     int* firstArray;
343     double* secondArray;
344     // other functions here
345 \};
346 \end{alltt}
347
348 The interface translator generates the \uw{CMessage\_VarsizeMessage} class,
349 which contains code to properly allocate, pack and unpack the
350 \uw{VarsizeMessage}.
351
352
353 One can allocate messages of the \uw{VarsizeMessage} class as follows:
354
355 \begin{alltt}
356 // firstArray will have 4 elements
357 // secondArray will have 5 elements 
358 VarsizeMessage* p = new(4, 5, 0) VarsizeMessage;
359 p->firstArray[2] = 13;     // the arrays have already been allocated 
360 p->secondArray[4] = 6.7; 
361 \end{alltt}
362
363 \hrule
364 \normalsize
365 No special handling is needed for deleting varsize messages.
366 } % end zap
367
368 \subsection{Message Packing}
369
370 \label{message packing}
371 \index{message packing}
372
373 The \charmpp{} interface translator generates implementation for three static
374 methods for the message class \uw{CMessage\_mtype}. These methods have the
375 prototypes:
376
377 \begin{alltt}
378     static void* alloc(int msgnum, size_t size, int* array, int priobits);
379     static void* pack(mtype*);
380     static mtype* unpack(void*);
381 \end{alltt}
382
383 One may choose not to use the translator-generated methods and may override
384 these implementations with their own \uw{alloc}, \uw{pack} and \uw{unpack}
385 static methods of the \uw{mtype} class.  The \kw{alloc} method will be called
386 when the message is allocated using the \CC\ \kw{new} operator. The programmer
387 never needs to explicitly call it.  Note that all elements of the message are
388 allocated when the message is created with \kw{new}. There is no need to call
389 \kw{new} to allocate any of the fields of the message. This differs from a
390 packed message where each field requires individual allocation. The \kw{alloc}
391 method should actually allocate the message using \kw{CkAllocMsg}, whose
392 signature is given below:
393
394 \begin{alltt}
395 void *CkAllocMsg(int msgnum, int size, int priobits); 
396 \end{alltt}  
397
398
399 For varsize messages, these static methods \texttt{alloc}, \texttt{pack}, and 
400 \texttt{unpack} are
401 generated by the interface translator.  For example, these
402 methods for the \kw{VarsizeMessage} class above would be similar to:
403
404 \begin{alltt}
405 // allocate memory for varmessage so charm can keep track of memory
406 static void* alloc(int msgnum, size_t size, int* array, int priobits)
407 \{
408   int totalsize, first_start, second_start;
409   // array is passed in when the message is allocated using new (see below).
410   // size is the amount of space needed for the part of the message known
411   // about at compile time.  Depending on their values, sometimes a segfault
412   // will occur if memory addressing is not on 8-byte boundary, so altered
413   // with ALIGN8
414   first_start = ALIGN8(size);  // 8-byte align with this macro
415   second_start = ALIGN8(first_start + array[0]*sizeof(int));
416   totalsize = second_start + array[1]*sizeof(double);
417   VarsizeMessage* newMsg = 
418     (VarsizeMessage*) CkAllocMsg(msgnum, totalsize, priobits);
419   // make firstArray point to end of newMsg in memory
420   newMsg->firstArray = (int*) ((char*)newMsg + first_start);
421   // make secondArray point to after end of firstArray in memory
422   newMsg->secondArray = (double*) ((char*)newMsg + second_start);
423
424   return (void*) newMsg;
425 \}
426
427 // returns pointer to memory containing packed message
428 static void* pack(VarsizeMessage* in)
429 \{
430   // set firstArray an offset from the start of in
431   in->firstArray = (int*) ((char*)in->firstArray - (char*)in);
432   // set secondArray to the appropriate offset
433   in->secondArray = (double*) ((char*)in->secondArray - (char*)in);
434   return in;
435 \}
436
437 // returns new message from raw memory
438 static VarsizeMessage* VarsizeMessage::unpack(void* inbuf)
439 \{
440   VarsizeMessage* me = (VarsizeMessage*)inbuf;
441   // return first array to absolute address in memory
442   me->firstArray = (int*) ((size_t)me->firstArray + (char*)me);
443   // likewise for secondArray
444   me->secondArray = (double*) ((size_t)me->secondArray + (char*)me);
445   return me;
446 \}
447 \end{alltt}
448
449 The pointers in a varsize message can exist in two states.  At creation, they
450 are valid \CC\ pointers to the start of the arrays.  After packing, they become
451 offsets from the address of the pointer variable to the start of the pointed-to
452 data.  Unpacking restores them to pointers. 
453
454 \subsubsection{Custom Packed Messages}
455 \label{sec:messages/packed_msgs}
456
457 \index{packed messages}
458
459 In many cases, a message must store a {\em non-linear} data structure using
460 pointers.  Examples of these are binary trees, hash tables etc. Thus, the
461 message itself contains only a pointer to the actual data. When the message is
462 sent to the same processor, these pointers point to the original locations,
463 which are within the address space of the same processor. However, when such a
464 message is sent to other processors, these pointers will point to invalid
465 locations.
466
467 Thus, the programmer needs a way to ``serialize'' these messages
468 \index{serialized messages}\index{message serialization}{\em only if} the
469 message crosses the address-space boundary.  \charmpp{} provides a way to do
470 this serialization by allowing the developer to override the default
471 serialization methods generated by the \charmpp{} interface translator.
472 Note that this low-level serialization has nothing to do with parameter
473 marshalling or the PUP framework described later.
474
475 Packed messages are declared in the {\tt .ci} file the same way as ordinary
476 messages:
477
478 \begin{alltt}
479 message PMessage;
480 \end{alltt}
481
482 Like all messages, the class \uw{PMessage} needs to inherit from
483 \uw{CMessage\_PMessage} and should provide two {\em static} methods: \kw{pack}
484 and \kw{unpack}. These methods are called by the \charmpp\ runtime system, when
485 the message is determined to be crossing address-space boundary. The prototypes
486 for these methods are as follows:
487
488 \begin{alltt}
489 static void *PMessage::pack(PMessage *in);
490 static PMessage *PMessage::unpack(void *in);
491 \end{alltt}
492
493 Typically, the following tasks are done in \kw{pack} method:
494
495 \begin{itemize}
496
497 \item Determine size of the buffer needed to serialize message data.
498
499 \item Allocate buffer using the \kw{CkAllocBuffer} function. This function
500 takes in two parameters: input message, and size of the buffer needed, and
501 returns the buffer.
502
503 \item Serialize message data into buffer (alongwith any control information
504 needed to de-serialize it on the receiving side.
505
506 \item Free resources occupied by message (including message itself.)  
507
508 \end{itemize}
509
510 On the receiving processor, the \kw{unpack} method is called. Typically, the
511 following tasks are done in the \kw{unpack} method:
512
513 \begin{itemize}
514
515 \item Allocate message using \kw{CkAllocBuffer} function. {\em Do not
516 use \kw{new} to allocate message here. If the message constructor has
517 to be called, it can be done using the in-place \kw{new} operator.}
518
519 \item De-serialize message data from input buffer into the allocated message.
520
521 \item Free the input buffer using \kw{CkFreeMsg}.
522
523 \end{itemize}
524
525 Here is an example of a packed-message implementation:
526
527 \begin{alltt}
528 // File: pgm.ci
529 mainmodule PackExample \{
530   ...
531   message PackedMessage;
532   ...
533 \};
534
535 // File: pgm.h
536 ...
537 class PackedMessage : public CMessage_PackedMessage
538 \{
539   public:
540     BinaryTree<char> btree; // A non-linear data structure 
541     static void* pack(PackedMessage*);
542     static PackedMessage* unpack(void*);
543     ...
544 \};
545 ...
546
547 // File: pgm.C
548 ...
549 void*
550 PackedMessage::pack(PackedMessage* inmsg)
551 \{
552   int treesize = inmsg->btree.getFlattenedSize();
553   int totalsize = treesize + sizeof(int);
554   char *buf = (char*)CkAllocBuffer(inmsg, totalsize);
555   // buf is now just raw memory to store the data structure
556   int num_nodes = inmsg->btree.getNumNodes();
557   memcpy(buf, &num_nodes, sizeof(int));  // copy numnodes into buffer
558   buf = buf + sizeof(int);               // don't overwrite numnodes
559   // copies into buffer, give size of buffer minus header
560   inmsg->btree.Flatten((void*)buf, treesize);    
561   buf = buf - sizeof(int);              // don't lose numnodes
562   delete inmsg;
563   return (void*) buf;
564 \}
565
566 PackedMessage*
567 PackedMessage::unpack(void* inbuf)
568 \{
569   // inbuf is the raw memory allocated and assigned in pack
570   char* buf = (char*) inbuf;
571   int num_nodes;
572   memcpy(&num_nodes, buf, sizeof(int));
573   buf = buf + sizeof(int);
574   // allocate the message through Charm RTS
575   PackedMessage* pmsg = 
576     (PackedMessage*)CkAllocBuffer(inbuf, sizeof(PackedMessage));
577   // call "inplace" constructor of PackedMessage that calls constructor
578   // of PackedMessage using the memory allocated by CkAllocBuffer,
579   // takes a raw buffer inbuf, the number of nodes, and constructs the btree
580   pmsg = new ((void*)pmsg) PackedMessage(buf, num_nodes);  
581   CkFreeMsg(inbuf);
582   return pmsg;
583 \}
584 ... 
585 PackedMessage* pm = new PackedMessage();  // just like always 
586 pm->btree.Insert('A');
587 ...
588 \end{alltt}
589
590
591 While serializing an arbitrary data structure into a flat buffer, one must be
592 very wary of any possible alignment problems.  Thus, if possible, the buffer
593 itself should be declared to be a flat struct.  This will allow the \CC\
594 compiler to ensure proper alignment of all its member fields.
595
596
597
598 \subsubsection{Immediate Messages}
599
600 Immediate messages are special messages that skip the Charm scheduler, they
601 can be executed in an ``immediate'' fashion even in the middle of 
602 a normal running entry method. 
603 They are supported only in nodegroup.
604
605
606