Just trying to make this whole manual make more sense.
[charm.git] / doc / converse / cpm.tex
1 \chapter{Automatic Parameter Marshalling}
2
3 Automatic Parameter Marshalling is a concise means of invoking
4 functions on remote processors.  The CPM module handles all the
5 details of packing, transmitting, translating, and unpacking the
6 arguments.  It also takes care of converting function pointers into
7 handler numbers.  With all these details out of the way, it is
8 possible to perform remote function invocation in a single line of
9 code.
10
11 \section{CPM Basics}
12
13 The heart of the CPM module is the CPM scanner.  The scanner reads a C
14 source file.  When it sees the keyword {\tt CpmInvokable} in front of
15 one of the user's function declarations, it generates a {\it launcher}
16 for that particular function.  The {\it launcher} is a function whose
17 name is {\tt Cpm\_} concatenated to the name of the user's function.
18 The launcher accepts the same arguments as the user's function, plus a
19 {\it destination} argument.  Calling the {\it launcher} transmits a
20 message to another processor determined by the {\it destination}
21 argument.  When the message arrives and is handled, the user's
22 function is called.
23
24 For example, if the CPM scanner sees the following function
25 declaration
26
27 \begin{verbatim}
28     CpmInvokable myfunc(int x, int y) { ... }
29 \end{verbatim}
30
31 The scanner will generate a launcher named {\tt Cpm\_myfunc}.
32 The launcher has this prototype:
33
34 \begin{verbatim}
35     void Cpm_myfunc(CpmDestination destination, int x, int y);
36 \end{verbatim}
37
38 If I were to call {\tt Cpm\_myfunc} as follows:
39
40 \begin{verbatim}
41     Cpm_myfunc(CpmSend(3), 8, 9);
42 \end{verbatim}
43
44 A message would be sent to processor 3 ordering it to call {\tt
45 myfunc(8,9)}.  Notice that the {\it destination} argument isn't just an
46 integer processor number.  The possible destinations for a message are
47 described later.
48
49 When the CPM scanner is applied to a C source file with a particular
50 name, it generates a great deal of parameter packing and unpacking
51 code, and this code is inserted into an include file with a name
52 similar to the original C file: the {\tt .c} is replaced with {\tt
53 .cpm.h}.  The include file must be included in the original {\tt .c}
54 file, after the declarations of the types which are being packed and
55 unpacked, but before all uses of the CPM invocation mechanisms.
56
57 Note that the {\tt .cpm.h} include file is {\em not} for prototyping.
58 It contains the C code for the packing and unpacking mechanisms.
59 Therefore, it should only be included in the one source file from
60 which it was generated.  If the user wishes to prototype his code, he
61 must do so normally, by writing a header file of his own.
62
63 Each {\tt .cpm.h} file contains a function {\tt
64 CpmInitializeThisModule}, which initializes the code in {\it that}
65 {\tt .cpm.h} file.  The function is declared {\tt static}, so it is
66 possible to have one in each {\tt .cpm.h} file without conflicts.  It
67 is the responsibility of the CPM user to call each of these {\tt
68 CpmInitializeThisModule} functions before using any of the CPM
69 mechanisms.
70
71
72 We demonstrate the use of the CPM mechanisms using the following
73 short program {\tt myprog.c}:
74
75 \begin{verbatim}
76  1:    #include "myprog.cpm.h"
77  2:   
78  3:    CpmInvokable print_integer(int n)
79  4:    {
80  5:      CmiPrintf("%d\n", n);
81  6:    }
82  7:    
83  8:    user_main(int argc, char **argv)
84  9:    {
85 10:      int i;
86 11:      CpmModuleInit();
87 12:      CpmInitializeThisModule();
88 13:      if (CmiMyPe()==0)
89 14:        for (i=1; i<CmiNumPes(); i++)
90 15:          Cpm_print_integer(CpmSend(i), rand());
91 16:    }
92 17:    
93 18:    main(int argc, char **argv)
94 19:    {
95 20:      ConverseInit(argc, argv, user_main, 0, 0);
96 21:    }
97 \end{verbatim}
98
99 Lines 3-6 of this program contain a simple C function that prints an
100 integer.  The function is marked with the word {\tt CpmInvokable}.
101 When the CPM scanner sees this word, it adds the function {\tt
102 Cpm\_print\_integer} to the file {\tt myprog.cpm.h}.  The program
103 includes {\tt myprog.cpm.h} on line 1, and initializes the code in
104 there on line 12.  Each call to {\tt Cpm\_print\_integer} on line 15
105 builds a message that invokes {\tt print\_integer}.  The
106 destination-argument {\tt CpmSend(i)} causes the message to be sent to
107 the {\it i}'th processor.
108
109 The effect of this program is that the first processor orders each of
110 the other processors to print a random number.  Note that the example
111 is somewhat minimalist, for example, it doesn't contain any code for
112 terminating itself.  Also note that it would have been more efficient
113 to use an explicit broadcast.  Broadcasts are described later.
114
115 All launchers accept a {\it CpmDestination} as their first argument.  A
116 {\it CpmDestination} is actually a pointer to a small C structure
117 containing routing and handling information.  The CPM module has many
118 built-in functions that return {\it CpmDestination}s.  Therefore, any
119 of these can be used as the first argument to a launcher:
120
121 \begin{itemize}
122
123 \item[]{{\bf CpmSend({\it pe})} - the message is transmitted to
124 processor {\it pe} with maximum priority}.
125
126 \item[]{{\bf CpmEnqueue({\it pe, queueing, priobits, prioptr})}
127 - The message is transmitted to processor {\it pe}, where it is
128 enqueued with the specified queueing strategy and priority.  The {\it
129 queueing}, {\it priobits}, and {\it prioptr} arguments are the same as
130 for {\bf CqsEnqueueGeneral}.}
131
132 \item[]{{\bf CpmEnqueueFIFO({\it pe})} - the message is transmitted to
133 processor {\it pe} and enqueued with the middle priority (zero), and
134 FIFO relative to messages with the same priority.}
135
136 \item[]{{\bf CpmEnqueueLIFO({\it pe})} - the message is transmitted to
137 processor {\it pe} and enqueued with the middle priority (zero), and
138 LIFO relative to messages with the same priority.}
139
140 \item[]{{\bf CpmEnqueueIFIFO({\it pe, prio})} - the message is
141 transmitted to processor {\it pe} and enqueued with the specified
142 integer-priority {\it prio}, and FIFO relative to messages with the
143 same priority.}
144
145 \item[]{{\bf CpmEnqueueILIFO({\it pe, prio})} - the message is
146 transmitted to processor {\it pe} and enqueued with the specified
147 integer-priority {\it prio}, and LIFO relative to messages with the
148 same priority.}
149
150 \item[]{{\bf CpmEnqueueBFIFO({\it pe, priobits, prioptr})} - the
151 message is transmitted to processor {\it pe} and enqueued with the
152 specified bitvector-priority, and FIFO relative to messages
153 with the same priority.}
154
155 \item[]{{\bf CpmEnqueueBLIFO({\it pe, priobits, prioptr})} - the
156 message is transmitted to processor {\it pe} and enqueued with the
157 specified bitvector-priority, and LIFO relative to messages with the
158 same priority.}
159
160 \item[]{{\bf CpmMakeThread({\it pe})} - The message is transmitted to
161 processor {\it pe} where a CthThread is created, and the thread
162 invokes the specified function.}
163
164 \end{itemize}
165
166 All the functions shown above accept processor numbers as arguments.
167 Instead of supplying a processor number, one can also supply the
168 special symbols CPM\_ALL or CPM\_OTHERS, causing a broadcast.  For
169 example,
170
171 \begin{verbatim}
172 Cpm_print_integer(CpmMakeThread(CPM_ALL), 5);
173 \end{verbatim}
174
175 Would broadcast a message to all the processors causing each processor
176 to create a thread, which would in turn invoke {\tt print\_integer}
177 with the argument 5.
178
179 \section{CPM Packing and Unpacking}
180
181 Functions preceeded by the word {\bf CpmInvokable} must have simple
182 argument lists.  In particular, the argument list of a CpmInvokable
183 function can only contain cpm-single-arguments and cpm-array-arguments,
184 as defined by this grammar:
185
186 \begin{verbatim}
187     cpm-single-argument :== typeword varname
188     cpm-array-argument  :== typeword '*' varname
189 \end{verbatim}
190
191 When CPM sees the cpm-array-argument notation, CPM interprets it as
192 being a pointer to an array.  In this case, CPM attempts to pack an
193 entire array into the message, whereas it only attempts to pack a
194 single element in the case of the cpm-single-argument notation.
195
196 Each cpm-array-argument must be preceeded by a cpm-single-argument of
197 type {\tt CpmDim}.  {\tt CpmDim} is simply an alias for {\tt int}, but
198 when CPM sees an argument declared {\tt CpmDim}, it knows that the
199 next argument will be a cpm-array-argument, and it interprets the {\tt
200 CpmDim} argument to be the size of the array.  Given a pointer to the
201 array, its size, and its element-type, CPM handles the packing of
202 array values as automatically as it handles single values.
203
204 Here is a second program, {\tt example2.c}, which uses array arguments:
205
206 \begin{verbatim}
207  1:    #include "example2.cpm.h"
208  2:   
209  3:    CpmInvokable print_program_arguments(CpmDim argc, CpmStr *argv)
210  4:    {
211  5:      int i;
212  6:      CmiPrintf("The program's arguments are: ");
213  7:      for (i=0; i<argc; i++) CmiPrintf("%s ", argv[i]);
214  8:      CmiPrintf("\n");
215  9:    }
216 10:
217 11:    user_main(int argc, char **argv)
218 12:    {
219 13:      CpmModuleInit();
220 14:      CpmInitializeThisModule();
221 15:      if (CmiMyPe()==0)
222 16:        Cpm_print_program_arguments(CpmSend(1), argc, argv);
223 17:    }
224 18:
225 19:    main(int argc, char **argv)
226 20:    {
227 21:      ConverseInit(argc, argv, user_main, 0, 0);
228 22:    }
229 \end{verbatim}
230
231 The word {\tt CpmStr} is a CPM built-in type, it represents a
232 null-terminated string:
233
234 \begin{verbatim}
235         typedef char *CpmStr;
236 \end{verbatim}
237
238 Therefore, the function {\tt print\_program\_arguments} takes exactly
239 the same arguments as {\tt user\_main}.  In this example, the main
240 program running on processor 0 transmits the arguments to processor 1,
241 which prints them out.
242
243 Thus far, we have only shown functions whose prototypes contain
244 builtin CPM types.  CPM has built-in knowledge of the following types:
245 char, short, int, long, float, double, CpmDim, and CpmStr (pointer to
246 a null-terminated string).  However, you may also also transmit
247 user-defined types in a CPM message.
248
249 For each (non-builtin) type the user wishes to pack, the user must
250 supply some pack and unpack routines.  The subroutines needed depend
251 upon whether the type is a pointer or a simple type.  Simple types are
252 defined to be those that contain no pointers at all.  Note that some
253 types are neither pointers, nor simple types.  CPM cannot currently
254 handle such types.
255
256 CPM knows which type is which only through the following declarations:
257
258 \begin{verbatim}
259     CpmDeclareSimple(typeword);
260     CpmDeclarePointer(typeword);
261 \end{verbatim}
262
263 The user must supply such declarations for each type that must be sent
264 via CPM.
265
266 When packing a value {\tt v} which is a simple type, CPM uses the
267 following strategy.  The generated code first converts {\tt v} to
268 network interchange format by calling {\tt CpmPack\_typename(\&v)},
269 which must perform the conversion in-place.  It then copies {\tt v}
270 byte-for-byte into the message and sends it.  When the data arrives,
271 it is extracted from the message and converted back using {\tt
272 CpmUnpack\_typename(\&v)}, again in-place.  The user must supply the
273 pack and unpack routines.
274
275 When packing a value {\tt v} which is a pointer, the generated code
276 determines how much space is needed in the message buffer by calling
277 {\tt CpmPtrSize\_typename(v)}.  It then transfers the data pointed to
278 by {\tt v} into the message using {\tt CpmPtrPack\_typename(p, v) },
279 where {\tt p} is a pointer to the allocated space in the message
280 buffer.  When the message arrives, the generated code extracts the
281 packed data from the message by calling {\tt
282 CpmPtrUnpack\_typename(p)}.  The unpack function must return a pointer
283 to the unpacked data, which is allowed to still contain pointers to
284 the message buffer (or simply be a pointer to the message buffer).
285 When the invocation is done, the function {\tt
286 CpmPtrFree\_typename(v)} is called to free any memory allocated by the
287 unpack routine. The user must supply the size, pack, unpack, and free
288 routines.
289
290 The following program fragment shows the declaration of two
291 user-defined types:
292
293 \begin{verbatim}
294  1:
295  2:    typedef struct { double x,y; } coordinate;    
296  3:    CpmDeclareSimple(coordinate);
297  4:    
298  5:    void CpmPack_coordinate(coordinate *p)
299  6:    {
300  7:      CpmPack_double(&(p->x));
301  8:      CpmPack_double(&(p->y));
302  9:    }
303 10:
304 11:    void CpmPack_coordinate(coordinate *p)
305 12:    {
306 13:      CpmUnpack_double(&(p->x));
307 14:      CpmUnpack_double(&(p->y));
308 15:    }
309 16:
310 17:    typedef int *intptr;
311 18:    CpmDeclarePointer(intptr);
312 19:
313 20:    #define CpmPtrSize_intptr(p) sizeof(int)
314 21:    
315 22:    void CpmPtrPack_intptr(void *p, intptr v)
316 23:    {
317 24:      *(int *)p = *v;
318 25:      CpmPack_int((int *)p);
319 26:    }
320 27:
321 28:    intptr CpmPtrUnpack_intptr(void *p)
322 29:    {
323 30:      CpmUnpack_int((int *)p);
324 31:      return (int *)p;
325 32:    }
326 33:
327 34:    #define CpmPtrFree_intptr(p) (0)
328 35:
329 36:    #include "example3.cpm.h"
330 37:    ...
331 \end{verbatim}
332
333 The first type declared in this file is the coordinate.  Line 2
334 contains the C type declaration, and line 3 notifies CPM that it is a
335 simple type, containing no pointers.  Lines 5-9 declare the pack
336 function, which receives a pointer to a coordinate, and must pack it
337 in place.  It makes use of the pack-function for doubles, which also
338 packs in place.  The unpack function is similar.
339
340 The second type declared in this file is the intptr, which we intend
341 to mean a pointer to a single integer.  On line 18 we notify CPM that
342 the type is a pointer, and that it should therefore use
343 CpmPtrSize\_intptr, CpmPtrPack\_intptr, CpmPtrUnpack\_intptr, and
344 CpmPtrFree\_intptr.  Line 20 shows the size function, a constant: we
345 always need just enough space to store one integer.  The pack function
346 copies the int into the message buffer, and packs it in place.  The
347 unpack function unpacks it in place, and returns an intptr, which
348 points right to the unpacked integer which is still in the message
349 buffer.  Since the int is still in the message buffer, and not in
350 dynamically allocated memory, the free function on line 34 doesn't
351 have to do anything.
352
353 Note that the inclusion of the {\tt .cpm.h} file comes after these
354 type and pack declarations: the {\tt .cpm.h} file will reference these
355 functions and macros, therefore, they must already be defined.
356
357 \section{Inventing new kinds of CpmDestinations}
358
359 It is possible for the user to invent new kinds of CpmDestinations,
360 and to write functions that return these new destinations.  In order
361 to do this, one must have a mental model of the steps performed when a
362 Cpm message is sent.  This knowledge is only necessary to those
363 wishing to invent new kinds of destinations.  Others can skip this
364 section.
365
366 The basic steps taken when sending a CPM message are:
367
368 \begin{itemize}
369
370 \item[]{{\bf 1. The destination-structure is created.}  The first
371 argument to the launcher is a CpmDestination.  Therefore, before the
372 launcher is invoked, one typically calls a function (like CpmSend)
373 to build the destination-structure.}
374
375 \item[]{{\bf 2. The launcher allocates a message-buffer}.  The buffer
376 contains space to hold a function-pointer and the function's arguments.
377 It also contains space for an ``envelope'', the size of which is
378 determined by a field in the destination-structure.}
379
380 \item[]{{\bf 3. The launcher stores the function-arguments in the message
381 buffer}.  In doing so, the launcher converts the arguments to a
382 contiguous sequence of bytes.}
383
384 \item[]{{\bf 4. The launcher sets the message's handler}.  For every
385 launcher, there is a matching function called an {\it invoker}.  The
386 launcher's job is to put the argument data in the message and send the
387 message.  The {\it invoker}'s job is to extract the argument data from
388 the message and call the user's function.  The launcher uses {\tt
389 CmiSetHandler} to tell Converse to handle the message by calling the
390 appropriate {\it invoker}.}
391
392 \item[]{{\bf 5. The message is sent, received, and handled}. 
393 The destination-structure contains a pointer to a {\it send-function}.
394 The {\it send-function} is responsible for choosing the message's
395 destination and making sure that it gets there and gets handled.  The
396 {\it send-function} has complete freedom to implement this in any
397 manner it wishes.  Eventually, though, the message should arrive at a
398 destination and its handler should be called.}
399
400 \item[]{{\bf 6. The user's function is invoked}.  The invoker
401 extracts the function arguments from the message buffer and calls
402 the user's function.}
403
404 \end{itemize}
405
406 The {\it send-function} varies because messages take different
407 routes to get to their final destinations.  Compare, for example,
408 CpmSend to CpmEnqueueFIFO.  When CpmSend is used, the message goes
409 straight to the target processor and gets handled.  When
410 CpmEnqueueFIFO is used, the message goes to the target processor, goes
411 into the queue, comes out of the queue, and {\it then} gets handled.
412 The {\it send-function} must implement not only the transmission of
413 the message, but also the possible ``detouring'' of the message
414 through queues or into threads.
415
416 We now show an example CPM command, and describe the steps that are
417 taken when the command is executed.  The command we will consider is
418 this one:
419
420 \begin{verbatim}
421 Cpm_print_integer(CpmEnqueueFIFO(3), 12);
422 \end{verbatim}
423
424 Which sends a message to processor 3, ordering it to call {\tt
425 print\_integer(12)}.
426
427 The first step is taken by CpmEnqueueFIFO, which builds the
428 CpmDestination.  The following is the code for CpmEnqueueFIFO:
429
430 \pagebreak
431
432 \begin{verbatim}
433 typedef struct CpmDestinationSend
434 {
435   void *(*sendfn)();
436   int envsize;
437   int pe;
438 }
439 *CpmDestinationSend;
440
441 CpmDestination CpmEnqueueFIFO(int pe)
442 {
443   static struct CpmDestinationSend ctrl;
444   ctrl.envsize = sizeof(int);
445   ctrl.sendfn  = CpmEnqueueFIFO1;
446   ctrl.pe = pe;
447   return (CpmDestination)&ctrl;
448 }
449 \end{verbatim}
450
451 Notice that the CpmDestination structure varies, depending upon which
452 kind of destination is being used.  In this case, the destination
453 structure contains a pointer to the send-function {\tt
454 CpmEnqueueFIFO1}, a field that controls the size of the envelope, and
455 the destination-processor.  In a CpmDestination, the {\tt sendfn} and
456 {\tt envsize} fields are required, additional fields are optional.
457
458 After CpmEnqueueFIFO builds the destination-structure, the launcher
459 Cpm\_print\_integer is invoked.  Cpm\_print\_integer performs all the
460 steps normally taken by a launcher:
461
462 \begin{itemize}
463
464 \item[]{{\bf 1. It allocates the message buffer.}  In this case, it sets aside
465 just enough room for one {\it int} as an envelope, as dictated by the
466 destination-structure's {\it envsize} field.}
467
468 \item[]{{\bf 2. It stores the function-arguments in the message-buffer.}  In
469 this case, the function-arguments are just the integer 12.}
470
471 \item[]{{\bf 3. It sets the message's handler.}  In this case, the message's
472 handler is set to a function that will extract the arguments and call
473 print\_integer.}
474
475 \item[]{{\bf 4. It calls the send-function to send the message.}}
476 \end{itemize}
477
478 The code for the send-function is here:
479
480 \begin{verbatim}
481 void *CpmEnqueueFIFO1(CpmDestinationSend dest, int len, void *msg)
482 {
483   int *env = (int *)CpmEnv(msg);
484   env[0] = CmiGetHandler(msg);
485   CmiSetHandler(msg, CpvAccess(CpmEnqueueFIFO2_Index));
486   CmiSyncSendAndFree(dest->pe,len,msg);
487 }
488 \end{verbatim}
489
490 The send-function CpmEnqueueFIFO1 starts by switching the handler.
491 The original handler is removed using using {\tt CmiGetHandler}.  It
492 is set aside in the message buffer in the ``envelope'' space described
493 earlier --- notice the use of {\tt CpmEnv} to obtain the envelope.
494 This is the purpose of the envelope in the message --- it is a place
495 where the send-function can store information.  The
496 destination-function must anticipate how much space the send-function
497 will need, and it must specify that amount of space in the
498 destination-structure field {\it envsize}.  In this case, the envelope
499 is used to store the original handler, and the message's handler is
500 set to an internal function called {\tt CpmEnqueueFIFO2}.
501
502 After switching the handler, {\tt CpmEnqueueFIFO1} sends the message.
503 Eventually, the message will be received by {\tt CsdScheduler}, and
504 its handler will be called.  The result will be that {\tt
505 CpmEnqueueFIFO2} will be called on the destination processor.  Here is
506 the code for {\tt CpmEnqueueFIFO2}:
507
508 \begin{verbatim}
509 void CpmEnqueueFIFO2(void *msg)
510 {
511   int *env;
512   CmiGrabBuffer(&msg);
513   env = (int *)CpmEnv(msg);
514   CmiSetHandler(msg, env[0]);
515   CsdEnqueueFIFO(msg);
516 }
517 \end{verbatim}
518
519 This function takes ownership of the message-buffer from Converse
520 using {\tt CmiGrabBuffer}.  It extracts the original handler from the
521 envelope (the handler that calls {\tt print\_integer}), and restores it
522 using {\tt CmiSetHandler}.  Having done so, it enqueues the message
523 with the FIFO queueing policy.  Eventually, the scheduler picks the
524 message from the queue, and {\tt print\_integer} is invoked.
525
526 In summary, the procedure for implementing new kinds of destinations
527 is to write one send-function, one function returning a CpmDestination
528 (which contains a reference to the send-function), and one or more
529 Converse handlers to manipulate the message.
530
531 The destination-function must return a pointer to a
532 ``destination-structure'', which can in fact be any structure matching
533 the following specifications:
534
535 \begin{itemize}
536 \item{The first field must be a pointer to a send-function,}
537 \item{The second field must the an integer, the envelope-size.}
538 \end{itemize}
539
540 This pointer must be coerced to type CpmDestination.
541
542 The send-function must have the following prototype:
543
544 \begin{verbatim}
545     void sendfunction(CpmDestination dest, int msglen, void *msgptr)
546 \end{verbatim}
547
548 It can access the envelope of the message using CpmEnv:
549
550 \begin{verbatim}
551     int *CpmEnv(void *msg);
552 \end{verbatim}
553
554 And it can also access the data stored in the destination-structure
555 by the destination-function.
556