updated CkPriorityPtr.
[charm.git] / doc / charm++ / messages.tex
1 \subsection{Messages}
2
3 \label{messages}
4 A message encapsulates all the parameters sent to an
5 entry method.  Since the parameters are already encapsulated,
6 sending messages is often more efficient than parameter marshalling.
7 In addition, messages are easier to queue and store on the
8 receive side.
9
10 The largest difference between parameter marshalling and messages
11 is that entry methods {\em keep} the messages passed to them.
12 Thus each entry method must be passed a {\em new} message.
13 On the receiving side, the entry method must either store the
14 passed message or explicitly {\em delete} it, or else the message
15 will never be destroyed, wasting memory.
16
17 Several kinds of message are available.
18 Regular \charmpp{} messages are objects of
19 \textit{fixed size}. One can have messages that contain pointers or variable
20 length arrays (arrays with sizes specified at runtime) and still have these
21 pointers to be valid when messages are sent across processors, with some
22 additional coding.  Also available is a mechanism for assigning
23 \textit{priorities} to messages that applies all kinds of messages.
24 A detailed discussion of priorities appears later in this section.
25
26 Like all other entities involved in asynchronous method invocation, messages
27 need to be declared in the {\tt .ci} file. In the {\tt .ci} file (the
28 interface file), a message is declared as: 
29
30 \begin{alltt}
31  message MessageType;
32 \end{alltt}
33
34 A message that contains variable length arrays is declared as:
35
36 \begin{alltt}
37  message MessageType \{
38    type1 var_name1[];
39    type2 var_name2[];
40    type3 var_name3[];
41 \};
42 \end{alltt}
43
44 If the name of the message class is \uw{MessageType}, the class must inherit 
45 publicly from a class whose name is \uw{CMessage\_MessageType}. This class
46 is generated by the charm translator. Then message definition has the form:
47
48 \begin{alltt}
49  class MessageType : public CMessage_MessageType \{
50     // List of data and function members as in \CC
51  \};
52 \end{alltt}
53
54
55 \subsubsection{Message Creation and Deletion}
56
57 \label{memory allocation}
58
59 \index{message}Messages are allocated using the \CC\ \kw{new} operator:
60
61 \begin{alltt}
62  MessageType *msgptr =
63   new [(int sz1, int sz2, ... , int priobits=0)] MessageType[(constructor arguments)];
64 \end{alltt}
65
66 The optional arguments to the new operator are used when allocating messages
67 with variable length arrays or \kw{prioritized} messages. \uw{sz1, sz2, ...}
68 denote the size (in appropriate units) of the memory blocks that need to be
69 allocated and assigned to the pointers that the message contains. The
70 \uw{priobits} argument denotes the size of a bitfield (number of bits) that
71 will be used to store the message priority.   
72
73 For example, to allocate a message whose class declaration is:
74
75 \begin{alltt}
76 class Message : public CMessage_Message \{
77   // .. fixed size message
78   // .. data and method members
79 \};
80 \end{alltt}
81
82 do the following:
83
84 \begin{alltt}
85 Message *msg = new Message;
86 \end{alltt}
87
88 To allocate a message whose class declaration is:
89
90 \begin{alltt}
91 class VarsizeMessage : public CMessage_VarsizeMessage \{
92  public:
93   int *firstArray;
94   double *secondArray;
95 \};
96 \end{alltt}
97
98 do the following:
99
100 \begin{alltt}
101 VarsizeMessage *msg = new (10, 20) VarsizeMessage;
102 \end{alltt}
103
104 This allocates a \uw{VarsizeMessage}, in which \uw{firstArray} points to an
105 array of 10 ints and \uw{secondArray} points to an array of 20 doubles.  This
106 is explained in detail in later sections. 
107
108 To add a \index{priority}priority bitfield to this message, 
109
110 \begin{alltt}
111 VarsizeMessage *msg = new (10, 20, sizeof(int)*8) VarsizeMessage;
112 \end{alltt}
113
114 Note, you must provide number of bits which is used to store the priority as
115 the \uw{priobits} parameter. The section on prioritized execution describes how
116 this bitfield is used.
117
118 In Section~\ref{message packing} we explain how messages can contain arbitrary
119 pointers, and how the validity of such pointers can be maintained across
120 processors in a distributed memory machine.
121
122 When a message \index{message} is sent to a \index{chare}chare, the programmer
123 relinquishes control of it; the space allocated to the message is freed by the
124 system.  When a message is received at an entry point it is not freed by the
125 runtime system.  It may be reused or deleted by the programmer.  Messages can
126 be deleted using the standard \CC{} \kw{delete} operator.  
127
128 There are no limitations of the methods of message classes except that the
129 message class may not redefine operators \texttt{new} or \texttt{delete}.
130
131
132 \subsubsection{Messages with Variable Length Arrays}
133
134 \label{varsize messages}
135 \index{variable size messages}
136 \index{varsize message}
137
138 An ordinary message in \charmpp\ is a fixed size message that is allocated
139 internally with an envelope which encodes the size of the message. Very often,
140 the size of the data contained in a message is not known until runtime. One can
141 use packed\index{packed messages} messages to alleviate this problem.  However,
142 it requires multiple memory allocations (one for the message, and another for
143 the buffer.) This can be avoided by making use of a \emph{varsize} message.
144 In \emph{varsize} messages, the space required for these variable length arrays
145 is allocated with the message such that it is contiguous to the message.
146
147 Such a message is declared as 
148
149 \begin{alltt}
150  message mtype \{
151    type1 var_name1[];
152    type2 var_name2[];
153    type3 var_name3[];
154  \};
155 \end{alltt}
156
157 in \charmpp\ interface file. The class \uw{mtype} has to inherit from
158 \uw{CMessage\_mtype}. In addition, it has to contain variables of corresponding
159 names pointing to appropriate types. If any of these variables (data members)
160 are private or protected, it should declare class \uw{CMessage\_mtype} to be a
161 ``friend'' class. Thus the \uw{mtype} class declaration should be similar to:
162
163 \begin{alltt}
164 class mtype : public CMessage_mtype \{
165  private:
166    type1 *var_name1;
167    type2 *var_name2;
168    type3 *var_name3;
169    friend class CMessage_mtype;
170 \};
171 \end{alltt}
172
173 \small
174 \hrule
175
176 \noindent\textbf{An Example}
177
178 Suppose a \charmpp\ message contains two variable length arrays of types
179 \texttt{int} and \texttt{double}:
180
181 \begin{alltt} 
182 class VarsizeMessage: public CMessage_VarsizeMessage \{
183   public:
184     int lengthFirst;
185     int lengthSecond;
186     int* firstArray;
187     double* secondArray;
188     // other functions here
189 \};
190 \end{alltt}
191
192 Then in the \texttt{.ci} file, this has to be declared as: 
193
194 \begin{alltt}
195 message VarsizeMessage \{
196   int firstArray[];
197   double secondArray[];
198 \};
199 \end{alltt}
200
201 We specify the types and actual names of the fields that
202 contain variable length arrays. The dimensions of these arrays are NOT
203 specified in the interface file, since they will be specified in the
204 constructor of the message when message is created. In the {\tt .h} or {\tt .C}
205 file, this class is declared as:
206
207 \begin{alltt} 
208
209 class VarsizeMessage : public CMessage_VarsizeMessage \{ 
210   public: 
211     int lengthFirst;
212     int lengthSecond;
213     int* firstArray;
214     double* secondArray;
215     // other functions here
216 \};
217 \end{alltt}
218
219 The interface translator generates the \uw{CMessage\_VarsizeMessage} class,
220 which contains code to properly allocate, pack and unpack the
221 \uw{VarsizeMessage}.
222
223
224 One can allocate messages of the \uw{VarsizeMessage} class as follows:
225
226 \begin{alltt}
227 // firstArray will have 4 elements
228 // secondArray will have 5 elements 
229 VarsizeMessage* p = new(4, 5, 0) VarsizeMessage;
230 p->firstArray[2] = 13;     // the arrays have already been allocated 
231 p->secondArray[4] = 6.7; 
232 \end{alltt}
233
234 Another way of allocating a varsize message is to pass a \uw{sizes} in an array
235 instead of the parameter list. For example,
236
237 \begin{alltt}
238 int sizes[2];
239 sizes[0] = 4;               // firstArray will have 4 elements
240 sizes[1] = 5;               // secondArray will have 5 elements 
241 VarsizeMessage* p = new(sizes, 0) VarsizeMessage;
242 p->firstArray[2] = 13;     // the arrays have already been allocated 
243 p->secondArray[4] = 6.7; 
244 \end{alltt}
245
246 \hrule
247 \normalsize
248
249 No special handling is needed for deleting varsize messages.
250
251 \subsubsection{Message Packing}
252
253 \label{message packing}
254 \index{message packing}
255
256 The \charmpp{} interface translator generates implementation for three static
257 methods for the message class \uw{CMessage\_mtype}. These methods have the
258 prototypes:
259
260 \begin{alltt}
261     static void* alloc(int msgnum, size_t size, int* array, int priobits);
262     static void* pack(mtype*);
263     static mtype* unpack(void*);
264 \end{alltt}
265
266 One may choose not to use the translator-generated methods and may override
267 these implementations with their own \uw{alloc}, \uw{pack} and \uw{unpack}
268 static methods of the \uw{mtype} class.  The \kw{alloc} method will be called
269 when the message is allocated using the \CC\ \kw{new} operator. The programmer
270 never needs to explicitly call it.  Note that all elements of the message are
271 allocated when the message is created with \kw{new}. There is no need to call
272 \kw{new} to allocate any of the fields of the message. This differs from a
273 packed message where each field requires individual allocation. The \kw{alloc}
274 method should actually allocate the message using \kw{CkAllocMsg}, whose
275 signature is given below:
276
277 \begin{alltt}
278 void *CkAllocMsg(int msgnum, int size, int priobits); 
279 \end{alltt}  
280
281
282 For varsize messages, these static methods \texttt{alloc}, \texttt{pack}, and 
283 \texttt{unpack} are
284 generated by the interface translator.  For example, these
285 methods for the \kw{VarsizeMessage} class above would be similar to:
286
287 \begin{alltt}
288 // allocate memory for varmessage so charm can keep track of memory
289 static void* alloc(int msgnum, size_t size, int* array, int priobits)
290 \{
291   int totalsize, first_start, second_start;
292   // array is passed in when the message is allocated using new (see below).
293   // size is the amount of space needed for the part of the message known
294   // about at compile time.  Depending on their values, sometimes a segfault
295   // will occur if memory addressing is not on 8-byte boundary, so altered
296   // with ALIGN8
297   first_start = ALIGN8(size);  // 8-byte align with this macro
298   second_start = ALIGN8(first_start + array[0]*sizeof(int));
299   totalsize = second_start + array[1]*sizeof(double);
300   VarsizeMessage* newMsg = 
301     (VarsizeMessage*) CkAllocMsg(msgnum, totalsize, priobits);
302   // make firstArray point to end of newMsg in memory
303   newMsg->firstArray = (int*) ((char*)newMsg + first_start);
304   // make secondArray point to after end of firstArray in memory
305   newMsg->secondArray = (double*) ((char*)newMsg + second_start);
306
307   return (void*) newMsg;
308 \}
309
310 // returns pointer to memory containing packed message
311 static void* pack(VarsizeMessage* in)
312 \{
313   // set firstArray an offset from the start of in
314   in->firstArray = (int*) ((char*)in->firstArray - (char*)in);
315   // set secondArray to the appropriate offset
316   in->secondArray = (double*) ((char*)in->secondArray - (char*)in);
317   return in;
318 \}
319
320 // returns new message from raw memory
321 static VarsizeMessage* VarsizeMessage::unpack(void* inbuf)
322 \{
323   VarsizeMessage* me = (VarsizeMessage*)inbuf;
324   // return first array to absolute address in memory
325   me->firstArray = (int*) ((size_t)me->firstArray + (char*)me);
326   // likewise for secondArray
327   me->secondArray = (double*) ((size_t)me->secondArray + (char*)me);
328   return me;
329 \}
330 \end{alltt}
331
332 The pointers in a varsize message can exist in two states.  At creation, they
333 are valid \CC\ pointers to the start of the arrays.  After packing, they become
334 offsets from the address of the pointer variable to the start of the pointed-to
335 data.  Unpacking restores them to pointers. 
336
337 \subsubsection{Custom Packed Messages}
338
339 \index{packed messages}
340
341 In many cases, a message must store a {\em non-linear} data structure using
342 pointers.  Examples of these are binary trees, hash tables etc. Thus, the
343 message itself contains only a pointer to the actual data. When the message is
344 sent to the same processor, these pointers point to the original locations,
345 which are within the address space of the same processor. However, when such a
346 message is sent to other processors, these pointers will point to invalid
347 locations.
348
349 Thus, the programmer needs a way to ``serialize'' these messages
350 \index{serialized messages}\index{message serialization}{\em only if} the
351 message crosses the address-space boundary.  \charmpp{} provides a way to do
352 this serialization by allowing the developer to override the default
353 serialization methods generated by the \charmpp{} interface translator.
354 Note that this low-level serialization has nothing to do with parameter
355 marshalling or the PUP framework described later.
356
357 Packed messages are declared in the {\tt .ci} file the same way as ordinary
358 messages:
359
360 \begin{alltt}
361 message PMessage;
362 \end{alltt}
363
364 Like all messages, the class \uw{PMessage} needs to inherit from
365 \uw{CMessage\_PMessage} and should provide two {\em static} methods: \kw{pack}
366 and \kw{unpack}. These methods are called by the \charmpp\ runtime system, when
367 the message is determined to be crossing address-space boundary. The prototypes
368 for these methods are as follows:
369
370 \begin{alltt}
371 static void *PMessage::pack(PMessage *in);
372 static PMessage *PMessage::unpack(void *in);
373 \end{alltt}
374
375 Typically, the following tasks are done in \kw{pack} method:
376
377 \begin{itemize}
378
379 \item Determine size of the buffer needed to serialize message data.
380
381 \item Allocate buffer using the \kw{CkAllocBuffer} function. This function
382 takes in two parameters: input message, and size of the buffer needed, and
383 returns the buffer.
384
385 \item Serialize message data into buffer (alongwith any control information
386 needed to de-serialize it on the receiving side.
387
388 \item Free resources occupied by message (including message itself.)  
389
390 \end{itemize}
391
392 On the receiving processor, the \kw{unpack} method is called. Typically, the
393 following tasks are done in the \kw{unpack} method:
394
395 \begin{itemize}
396
397 \item Allocate message using \kw{CkAllocBuffer} function. {\em Do not
398 use \kw{new} to allocate message here. If the message constructor has
399 to be called, it can be done using the in-place \kw{new} operator.}
400
401 \item De-serialize message data from input buffer into the allocated message.
402
403 \item Free the input buffer using \kw{CkFreeMsg}.
404
405 \end{itemize}
406
407 Here is an example of a packed-message implementation:
408
409 \begin{alltt}
410 // File: pgm.ci
411 mainmodule PackExample \{
412   ...
413   message PackedMessage;
414   ...
415 \};
416
417 // File: pgm.h
418 ...
419 class PackedMessage : public CMessage_PackedMessage
420 \{
421   public:
422     BinaryTree<char> btree; // A non-linear data structure 
423     static void* pack(PackedMessage*);
424     static PackedMessage* unpack(void*);
425     ...
426 \};
427 ...
428
429 // File: pgm.C
430 ...
431 void*
432 PackedMessage::pack(PackedMessage* inmsg)
433 \{
434   int treesize = inmsg->btree.getFlattenedSize();
435   int totalsize = treesize + sizeof(int);
436   char *buf = (char*)CkAllocBuffer(inmsg, totalsize);
437   // buf is now just raw memory to store the data structure
438   int num_nodes = inmsg->btree.getNumNodes();
439   memcpy(buf, &num_nodes, sizeof(int));  // copy numnodes into buffer
440   buf = buf + sizeof(int);               // don't overwrite numnodes
441   // copies into buffer, give size of buffer minus header
442   inmsg->btree.Flatten((void*)buf, treesize);    
443   buf = buf - sizeof(int);              // don't lose numnodes
444   delete inmsg;
445   return (void*) buf;
446 \}
447
448 PackedMessage*
449 PackedMessage::unpack(void* inbuf)
450 \{
451   // inbuf is the raw memory allocated and assigned in pack
452   char* buf = (char*) inbuf;
453   int num_nodes;
454   memcpy(&num_nodes, buf, sizeof(int));
455   buf = buf + sizeof(int);
456   // allocate the message through charm kernel
457   PackedMessage* pmsg = 
458     (PackedMessage*)CkAllocBuffer(inbuf, sizeof(PackedMessage));
459   // call "inplace" constructor of PackedMessage that calls constructor
460   // of PackedMessage using the memory allocated by CkAllocBuffer,
461   // takes a raw buffer inbuf, the number of nodes, and constructs the btree
462   pmsg = new ((void*)pmsg) PackedMessage(buf, num_nodes);  
463   CkFreeMsg(inbuf);
464   return pmsg;
465 \}
466 ... 
467 PackedMessage* pm = new PackedMessage();  // just like always 
468 pm->btree.Insert('A');
469 ...
470 \end{alltt}
471
472
473 While serializing an arbitrary data structure into a flat buffer, one must be
474 very wary of any possible alignment problems.  Thus, if possible, the buffer
475 itself should be declared to be a flat struct.  This will allow the \CC\
476 compiler to ensure proper alignment of all its member fields.
477
478
479 \subsubsection{Prioritized Execution}
480
481 \label{prioritized message passing}
482 \index{prioritized execution}
483 \index{prioritized message passing}
484 \index{priorities}
485
486 By default, \charmpp\ will process the messages you send in roughly
487 FIFO\index{message delivery order} order.  For most programs, this
488 behavior is fine.  However, some programs need more explicit control
489 over the order in which messages are processed.  \charmpp\ allows you
490 to control queueing behavior on a per-message basis.
491
492 The simplest call available to change the order in which messages
493 are processed is \kw{CkSetQueueing}.
494
495 \function{void CkSetQueueing(MsgType message, int queueingtype)}
496
497 where \uw{queueingtype} is one of the following constants:
498
499 \begin{alltt}
500   CK_QUEUEING_FIFO
501   CK_QUEUEING_LIFO
502   CK_QUEUEING_IFIFO
503   CK_QUEUEING_ILIFO
504   CK_QUEUEING_BFIFO
505   CK_QUEUEING_BLIFO
506 \end{alltt}
507
508 The first two options,  \kw{CK\_QUEUEING\_FIFO} and
509 \kw{CK\_QUEUEING\_LIFO}, are used as follows: 
510
511 \begin{alltt}
512   MsgType *msg1 = new MsgType ;
513   CkSetQueueing(msg1, CK_QUEUEING_FIFO);
514
515   MsgType *msg2 = new MsgType ;
516   CkSetQueueing(msg2, CK_QUEUEING_LIFO);
517 \end{alltt}
518
519 When message \kw{msg1} arrives at its destination, it will be pushed onto the
520 end of the message queue as usual.  However, when \kw{msg2} arrives, it will be
521 pushed onto the {\em front} of the message queue.
522
523 The other four options involve the use of priorities\index{priorities}.  To
524 attach a priority field to a message, one needs to set aside space in the
525 message's buffer while allocating the message\index{message priority}.  To
526 achieve this, the size of the priority field\index{priority field} in bits
527 should be specified as a placement argument to the \kw{new} operator, as
528 described in Section \ref{memory allocation}.  Although the size of the
529 priority field is specified in bits, it is always padded to an integral number
530 of {\tt int}s.  A pointer to the priority part of the message buffer can be
531 obtained with this call:
532
533 \function{void *CkPriorityPtr(MsgType msg)}
534 \index{CkPriorityPtr}
535 \index{priority pointer}
536
537 There are two kinds of priorities which can be attached to a message:
538 {\sl integer priorities}\index{integer priorities} and {\sl bitvector
539 priorities}\index{bitvector priorities}.  Integer priorities are quite
540 straightforward.  One allocates a message, setting aside enough space
541 (in bits) in the message to hold the priority, which is an integer.
542 One then stores the priority in the message.  Finally, one informs the
543 system that the message contains an integer priority using
544 \kw{CkSetQueueing}:
545
546 \begin{alltt}
547   MsgType *msg = new (8*sizeof(int)) MsgType;
548   *(int*)CkPriorityPtr(msg) = prio;
549   CkSetQueueing(msg, CK_QUEUEING_IFIFO);
550 \end{alltt}
551
552 The predefined constant  \kw{CK\_QUEUEING\_IFIFO} indicates that the
553 message contains an integer priority, and that if there are other
554 messages of the same priority, they should be sequenced in FIFO order
555 (relative to each other).  Similarly, a  \kw{CK\_QUEUEING\_ILIFO} is
556 available.  Note that  \kw{MAXINT} is the lowest priority, and {\bf
557 NEGATIVE\_MAXINT} is the highest priority\index{integer priority range}.
558
559 Bitvector priorities are somewhat more complicated.  Bitvector
560 priorities are arbitrary-length bit-strings representing fixed-point
561 numbers in the range 0 to 1.  For example, the bit-string ``001001''
562 represents the number .001001\raisebox{-.5ex}{\scriptsize binary}.  As
563 with the simpler kind of priority, higher numbers represent lower
564 priorities.  Unlike the simpler kind of priority, bitvectors can be of
565 arbitrary length, therefore, the priority numbers they represent can
566 be of arbitrary precision.
567
568 Arbitrary-precision priorities\index{arbitrary-precision priorities}
569 are often useful in AI search-tree applications.  Suppose we have a
570 heuristic suggesting that tree node $N_1$ should be searched before
571 tree node $N_2$.  We therefore designate that node $N_1$ and its
572 descendants will use high priorities, and that node $N_2$ and its
573 descendants will use lower priorities.  We have effectively split the
574 range of possible priorities in two.  If several such heuristics fire
575 in sequence, we can easily split the priority range \index{priority
576 range splitting} in two enough times that no significant bits remain,
577 and the search begins to fail for lack of meaningful priorities to
578 assign.  The solution is to use arbitrary-precision priorities,
579 i.e. bitvector priorities.
580
581 To assign a bitvector priority, two methods are available.  The
582 first is to obtain a pointer to the priority field using  \kw{CkPriorityPtr},
583 and to then manually set the bits using the bit-setting operations
584 inherent to C.  To achieve this, one must know the format
585 \index{bitvector format} of the
586 bitvector, which is as follows: the bitvector is represented as an
587 array of unsigned integers.  The most significant bit of the first
588 integer contains the first bit of the bitvector.  The remaining bits
589 of the first integer contain the next 31 bits of the bitvector.
590 Subsequent integers contain 32 bits each.  If the size of the
591 bitvector is not a multiple of 32, then the last integer contains 0
592 bits for padding in the least-significant bits of the integer.
593
594 The second way to assign priorities is only useful for those who are
595 using the priority range-splitting\index{priority range splitting}
596 described above.  The root of the tree is assigned the null
597 priority-string.  Each child is assigned its parent's priority with
598 some number of bits concatenated.  The net effect is that the entire
599 priority of a branch is within a small epsilon of the priority of its
600 root.
601
602 It is possible to utilize unprioritized messages, integer priorities,
603 and bitvector priorities in the same program.  The messages will be
604 processed in roughly the following order\index{multiple priority types}:
605
606 \begin{itemize}
607
608 \item Among messages enqueued with bitvector priorities, the
609 messages are dequeued according to their priority.  The
610 priority ``0000...'' is dequeued first, and ``1111...'' is
611 dequeued last.
612
613 \item Unprioritized messages are treated as if they had the
614 priority ``1000...'' (which is the ``middle'' priority, it
615 lies exactly halfway between ``0000...'' and ``1111...'').
616  
617 \item Integer priorities are converted to bitvector priorities.  They
618 are normalized so that the integer priority of zero is converted to
619 ``1000...'' (the ``middle'' priority).  To be more specific, the
620 conversion is performed by adding 0x80000000 to the integer, and then
621 treating the resulting 32-bit quantity as a 32-bit bitvector priority.
622
623 \item Among messages with the same priority, messages are
624 dequeued in FIFO order or LIFO order, depending upon which
625 queuing strategy was used.
626
627 \end{itemize} 
628
629 A final warning about prioritized execution: \charmpp\ always processes
630 messages in {\it roughly} the order you specify; it never guarantees to
631 deliver the messages in {\it precisely} the order\index{message
632 delivery order} you specify.
633 However, it makes a serious attempt to be ``close'', so priorities
634 can strongly affect the efficiency of your program.
635
636
637 \subsubsection{Immediate Messages}
638
639 Immediate messages are specical messages that skip the Charm scheduler, they
640 can be executed in an ``immediate'' fashion even in the middle of 
641 a normal running entry method. 
642 They are supported only in nodegroup.
643 Also see Section~\ref{attributes} and example in {\it charm/pgms/charm++/megatest/immediatering.C}.
644
645
646
647