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