d304ce7d1d828ea7e9b46357d32c1ce7f2b51585
[charm.git] / doc / convext / manual.rst
1 ===========================
2 Converse Extensions Library
3 ===========================
4
5 .. contents::
6    :depth: 3
7 ..
8
9 Introduction
10 ============
11
12 The Converse Extensions Library is a collection of modules that have
13 been implemented on top of the Converse API. Each of these modules was
14 deemed potentially useful to other Converse users, thus, we distribute
15 these modules along with Converse as a convenience. *You don’t need to
16 read any part of this manual to use Converse.*
17
18 Tag Matching
19 ============
20
21 The message manager is a data structure that can be used to put together
22 runtime systems for languages that support tag-based message retrieval.
23
24 The purpose of the message manager is to store, index, and retrieve
25 messages according to a set of integer tags. It provides functions to
26 create tables, functions to insert messages into tables (specifying
27 their tags), and functions to selectively retrieve messages from tables
28 according to their tags. Wildcard tags can be specified in both storage
29 and retrieval.
30
31 To use the message manager, you must include ``converse.h`` and link
32 with the Converse library.
33
34 In actuality, the term “message manager” is unnecessarily specific. The
35 message manager can store and retrieve arbitrary pointers according to a
36 set of tags. The pointers do *not* necessarily need to be pointers to
37 Converse messages. They can be pointers to anything.
38
39 ``typedef struct CmmTableStruct *CmmTable``
40
41 This opaque type is defined in ``converse.h``. It represents a table
42 which can be used to store messages. No information is publicized about
43 the format of a CmmTableStruct.
44
45 ``#define CmmWildCard (-1)``
46
47 This #define is in ``converse.h``. The tag -1 is the “wild card” for the
48 tag-based lookup functions in the message manager.
49
50 ``CmmTable CmmNew();``
51
52 This function creates a new message-table and returns it.
53
54 ``void CmmPut(CmmTable t, int ntags, int *tags, void *msg)``
55
56 This function inserts a message into a message table, along with an
57 array of tags. ``ntags`` specifies the length of the ``tags`` array. The
58 ``tags`` array contains the tags themselves. ``msg`` and ``t`` specify
59 the message and table, respectively.
60
61 ``void *CmmGet(CmmTable t, int ntags, int *tags, int *ret_tags)``
62
63 This function looks up a message from a message table. A message will be
64 retrieved that “matches” the specified ``tags`` array. If a message is
65 found that “matches”, the tags with which it was stored are copied into
66 the ``ret_tags`` array, a pointer to the message will be returned, and
67 the message will be deleted from the table. If no match is found, 0 will
68 be returned.
69
70 To “match”, the array ``tags`` must be of the same length as the stored
71 array. Similarly, all the individual tags in the stored array must
72 “match” the tags in the ``tags`` array. Two tags match if they are equal
73 to each other, or if ``either`` tag is equal to ``CmmWildCard`` (this
74 means one can ``store`` messages with wildcard tags, making it easier to
75 find those messages on retrieval).
76
77 ``void *CmmProbe(CmmTable t, int ntags, int *tags, int *ret_tags)``
78
79 This function is identical to ``CmmGet`` above, except that the message
80 is not deleted from the table.
81
82 ``void CmmFree(CmmTable t);``
83
84 This function frees a message-table t. WARNING: It also frees all the
85 messages that have been inserted into the message table. It assumes that
86 the correct way to do this is to call ``CmiFree`` on the message. If
87 this assumption is incorrect, a crash will occur. The way to avoid this
88 problem is to remove and properly dispose all the messages in a table
89 before disposing the table itself.
90
91 Converse Master-Slave Library
92 =============================
93
94 Introduction
95 ------------
96
97 CMS is the implementation of the master-slave (or manager-worker or
98 agenda) parallel programming paradigm on top of Converse.
99
100 Available Functions
101 -------------------
102
103 Following functions are available in this library:
104
105 ``typedef int (*CmsWorkerFn) (void *, void *);``
106
107 Prototype for the worker function. See below.
108
109 ``typedef int (*CmsConsumerFn) (void *, int);``
110
111 Prototype for the consumer function. See below.
112
113 ``void CmsInit(CmsWorkerFn worker, int max);``
114
115 This function must be called before firing any tasks for the workers.
116 max is the largest possible number of tasks you will fire before calling
117 either ``CmsAwaitResponses`` or ``CmsProcessResponses`` next. (So the
118 system know how many it may have to buffer).
119
120 ``int worker(void *t, void **r)``
121
122 The user writes this function. Its name does not have to be worker; It
123 can be anything. worker can be any function that the use writes to
124 perform the task on the slave processors. It must allocate and compute
125 the response data structure, and return a pointer to it, by assigning to
126 r; It must also return the size of the response data structure as its
127 return value.
128
129 ``void CmsFireTask(int ref, void * t, int size)``
130
131 Creates task to be worked on by a worker. The task description is
132 pointed to by t, and goes on for size bytes. ref must be a unique serial
133 number between 0 and max (see ``CmsInit``).
134
135 ``void CmsAwaitResponses(void);``
136
137 This call allows the system to use processor 0 as a worker. It returns
138 after all the tasks have sent back their responses. The responses
139 themselves can be extracted using ``CmsGetResponse``.
140
141 ``void *CmsGetResponse(int ref);``
142
143 Extracts the response associated with the reference number ref from the
144 system’s buffers.
145
146 ``void CmsProcessResponses(CmsConsumerFn consumer);``
147
148 Instead of using ``CmsAwaitResponses``/``CmsGetResponse`` pair, you can
149 use this call alone. It turns the control over to the CMS system on
150 processor 0, so it can be used as a worker. As soon as a response is
151 available on processor 0, cms calls the user specified consumer function
152 with two parameters: the response (a void \*) and an integer refnum.
153 (Question: should the size of the response be passed as a parameter to
154 the consumer? User can do that as an explicit field of the response
155 themselves, if necessary.)
156
157
158 ``void CmsExit(void);``
159
160 Must be called on all processors to terminate execution.
161
162 Once either ``CmsProcessResponses`` or ``CmsAwaitResponses`` returns,
163 you may fire the next batch of tasks via CmsFireTask again.
164
165 Example Program
166 ---------------
167
168 ::
169
170    #include "cms.h"
171
172    #define MAX 10
173
174    typedef struct {
175        float a;
176    } Task;
177
178    typedef struct {
179        float result;
180    } Response;
181
182    Task t;
183
184    int worker(Task *t, Response **r)
185    {
186        /* do work and generate a single response */
187        int i;
188        Task *t1;
189        int k;
190
191        CmiPrintf("%d: in worker %f \n", CmiMyPe(), t->a);
192        *r = (Response *) malloc(sizeof(Response));
193        (*r)->result = t->a * t->a;
194        return sizeof(Response);
195    }
196
197    int consumer(Response * r, int refnum)
198    {
199        CmiPrintf("consumer: response with refnum = %d is %f\n", refnum,
200                  r->result);
201    }
202
203    main(int argc, char *argv[])
204    {
205        int i, j, k, ref;
206        /* 2nd parameter is the max number of tasks
207         * fired before "awaitResponses"
208         */
209        CmsInit((CmsWorkerFn)worker, 20);
210        if (CmiMyPe() == 0) { /* I am the manager */
211            CmiPrintf("manager inited\n");
212            for (i = 0; i < 3; i++) { /* number of iterations or phases */
213              /* prepare the next generation of problems to solve */
214              /* then, fire the next batch of tasks for the worker */
215                for (j = 0; j < 5; j++) {
216                    t.a = 10 * i + j;
217                    ref = j;  /* a ref number to associate with the task, */
218                    /* so that the reponse for this task can be identified. */
219                    CmsFireTask(ref, &t, sizeof(t));
220                }
221              /* Now wait for the responses */
222                CmsAwaitResponses();  /* allows proc 0 to be used as a worker. */
223                /* Now extract the resoneses from the system */
224                for (j = 0; j < 5; j++) {
225                    Response *r = (Response *) CmsGetResponse(j);
226                    CmiPrintf("Response %d is: %f \n", j, r->result);
227                }
228              /* End of one mast-slave phase */
229                CmiPrintf("End of phase %d\n", i);
230            }
231        }
232
233        CmiPrintf("Now the consumerFunction mode\n");
234
235        if (CmiMyPe() == 0) { /* I am the manager */
236           for (i = 0; i < 3; i++) {
237               t.a = 5 + i;
238               CmsFireTask(i, &t, sizeof(t));
239           }
240           CmsProcessResponses((CmsConsumerFn)consumer);
241           /* Also allows proc. 0 to be used as a worker.
242            * In addition, responses will be processed on processor 0
243            * via the "consumer" function as soon as they are available
244            */
245        }
246        CmsExit();
247    }
248
249 Data Structures
250 ===============
251
252 In the course of developing Converse and Charm++ we had to implement a
253 number of data structures efficiently. If the ANSI standard C library
254 were available to us on all platforms, we could have used it, but that
255 was not the case. Also, we needed both the C and C++ bindings of most
256 data structures. In most cases, the functionality we needed was also a
257 subset of the C standard library functionality, and by avoiding virtual
258 methods etc, we have tried to code the most efficient implementations of
259 those data structures.
260
261 Since these data structures are already part of Converse and Charm++,
262 they are available to the users of these system free of cost :-<).
263 In this chapter we document the available functions.
264
265 Queues, Lists, FIFOs etc.
266 -------------------------
267
268 This data structure is based on circular buffer, and can be used both
269 like a FIFO and a Stack.
270
271 The following functions are available for use in C:
272
273 ``typedef ... CdsFifo;``
274
275 An opaque data type representing a queue of ``void*`` pointers.
276
277 ``CdsFifo CdsFifo_Create(void);``
278
279 Creates a queue in memory and returns its pointer.
280
281 ``CdsFifo CdsFifo_Create_len(int len);``
282
283 Creates a queue in memory with the initial buffer size of len entries
284 and returns its pointer.
285
286 ``void CdsFifo_Enqueue(CdsFifo q, void *elt);``
287
288 Appends elt at the end of q.
289
290 ``void *CdsFifo_Dequeue(CdsFifo q);``
291
292 Removes an element from the front of the q, and returns it. Returns 0 if
293 the queue is empty.
294
295 ``void *CdsFifo_Pop(CdsFifo q);``
296
297 Removes an element from the front of the q, and returns it. Returns 0 if
298 the queue is empty. An alias for the dequeue function.
299
300 ``void CdsFifo_Push(CdsFifo q, void *elt);``
301
302 Inserts elt in the beginning of q.
303
304 ``int CdsFifo_Empty(CdsFifo q);``
305
306 Returns 1 if the q is empty, 0 otherwise.
307
308 ``int CdsFifo_Length(CdsFifo q);``
309
310 Returns the length of the q.
311
312 ``int CdsFifo_Peek(CdsFifo q);``
313
314 Returns the element from the front of the q without removing it.
315
316 ``void CdsFifo_Destroy(CdsFifo q);``
317
318 Releases memory used by q.
319
320 The following Templates are available for use in C++:
321
322 ::
323
324    template<class T>
325    class CkQ {
326      CkQ();  // default constructor
327      CkQ(int initial_size); // constructor with initial buffer size
328      ~CkQ(); // destructor
329      int length(void); // returns length of the q
330      bool isEmpty(void); // returns true if q is empty, false otherwise
331      T deq(void); // removes and returns the front element
332      void enq(const T&); // appends at the end of the list
333      void push(const T&); // inserts in the beginning of the list
334      T& operator[](size_t n); // returns the n'th element
335    };
336
337 Converse Pseudorandom Number Generator
338 ======================================
339
340 Converse provides three different Linear Congruential Random Number
341 Generators. Each random number stream has a cycle length of
342 :math:`2^{64}` as opposed to ANSI C standard’s :math:`2^{48}`. Also,
343 each of the three random number streams can be split into a number of
344 per processor streams, so that the random number sequences can be
345 computed in parallel, and are reproducible. Furthermore, there is no
346 implicit critical section in the random number generator,and yet, this
347 functionality is thread-safe, because all the state information is
348 stored in the structure allocated by the programmer. Further, this state
349 information is stored in a first class object, and can be passed to
350 other processors through messages. This module of Converse is based on
351 the public-domain SPRNG [1]_ package developed by Ashok Srinivasan [2]_
352 at NCSA.
353
354 For minimal change to programs already using C functions ``rand()``,
355 ``srand()``, and ``drand48()``, Converse also maintains a “default”
356 random number stream.
357
358 Interface to the Converse Pseudorandom Number Generator module is as
359 follows:
360
361 ``typedef ... CrnStream;``
362
363 State information for generating the next random number in the sequence.
364
365 ``void CrnInitStream(CrnStream *stream, int seed, int type)``
366
367 Initializes the new random number stream ``stream`` of ``type`` using
368 ``seed``. ``type`` can have values 0, 1, or 2 to represent three types
369 of linear congruential random number generators.
370
371 ``int CrnInt(CrnStream *stream)``
372
373 Returns an integer between 0 and :math:`2^{31}-1` corresponding to the
374 next random number in the sequence associated with ``stream``. Advances
375 ``stream`` by one in the sequence.
376
377 ``double CrnDouble(CrnStream *stream)``
378
379 Returns an double precision floating point number between 0 and 1
380 corresponding to the next random number in the sequence associated with
381 ``stream``. Advances ``stream`` by one in the sequence.
382
383 ``float CrnFloat(CrnStream *stream)``
384
385 Returns a single precision floating point number between 0 and 1
386 corresponding to the next random number in the sequence associated with
387 ``stream``. Advances ``stream`` by one in the sequence.
388
389 ``void CrnSrand(int seed)``
390
391 Specifies a different seed for the default random number stream.
392 Replaces ``srand()``.
393
394 ``int CrnRand(void)``
395
396 Generate the next integer random number from the default random number
397 stream. Replaces ``rand()``.
398
399 ``double CrnDrand(void)``
400
401 Generate the next double precision random number from the default random
402 number stream. Replaces ``drand48()``.
403
404 Automatic Parameter Marshalling
405 ===============================
406
407 Automatic Parameter Marshalling is a concise means of invoking functions
408 on remote processors. The CPM module handles all the details of packing,
409 transmitting, translating, and unpacking the arguments. It also takes
410 care of converting function pointers into handler numbers. With all
411 these details out of the way, it is possible to perform remote function
412 invocation in a single line of code.
413
414 CPM Basics
415 ----------
416
417 The heart of the CPM module is the CPM scanner. The scanner reads a C
418 source file. When it sees the keyword ``CpmInvokable`` in front of one
419 of the user’s function declarations, it generates a *launcher* for that
420 particular function. The *launcher* is a function whose name is ``Cpm_``
421 concatenated to the name of the user’s function. The launcher accepts
422 the same arguments as the user’s function, plus a *destination*
423 argument. Calling the *launcher* transmits a message to another
424 processor determined by the *destination* argument. When the message
425 arrives and is handled, the user’s function is called.
426
427 For example, if the CPM scanner sees the following function declaration
428
429 ::
430
431        CpmInvokable myfunc(int x, int y) { ... }
432
433 The scanner will generate a launcher named ``Cpm_myfunc``. The launcher
434 has this prototype:
435
436 ::
437
438        void Cpm_myfunc(CpmDestination destination, int x, int y);
439
440 If one were to call ``Cpm_myfunc`` as follows:
441
442 ::
443
444        Cpm_myfunc(CpmSend(3), 8, 9);
445
446 a message would be sent to processor 3 ordering it to call
447 ``myfunc(8,9)``. Notice that the *destination* argument isn’t just an
448 integer processor number. The possible destinations for a message are
449 described later.
450
451 When the CPM scanner is applied to a C source file with a particular
452 name, it generates a certain amount of parameter packing and unpacking
453 code, and this code is placed in an include file named similarly to the
454 original C file: the ``.c`` is replaced with ``.cpm.h``. The include
455 file must be included in the original ``.c`` file, after the
456 declarations of the types which are being packed and unpacked, but
457 before all uses of the CPM invocation mechanisms.
458
459 Note that the ``.cpm.h`` include file is *not* for prototyping. It
460 contains the C code for the packing and unpacking mechanisms. Therefore,
461 it should only be included in the one source file from which it was
462 generated. If the user wishes to prototype his code, he must do so
463 normally, by writing a header file of his own.
464
465 Each ``.cpm.h`` file contains a function ``CpmInitializeThisModule``,
466 which initializes the code in *that* ``.cpm.h`` file. The function is
467 declared ``static``, so it is possible to have one in each ``.cpm.h``
468 file without conflicts. It is the responsibility of the CPM user to call
469 each of these ``CpmInitializeThisModule`` functions before using any of
470 the CPM mechanisms.
471
472 We demonstrate the use of the CPM mechanisms using the following short
473 program ``myprog.c``:
474
475 .. code-block:: c++
476   :linenos:
477
478    #include "myprog.cpm.h"
479
480    CpmInvokable print_integer(int n)
481    {
482      CmiPrintf("%d\n", n);
483    }
484
485    user_main(int argc, char **argv)
486    {
487      int i;
488      CpmModuleInit();
489      CpmInitializeThisModule();
490      if (CmiMyPe()==0)
491        for (i=1; i<CmiNumPes(); i++)
492          Cpm_print_integer(CpmSend(i), rand());
493    }
494
495    main(int argc, char **argv)
496    {
497      ConverseInit(argc, argv, user_main, 0, 0);
498    }
499
500 Lines 3-6 of this program contain a simple C function that prints an
501 integer. The function is marked with the word ``CpmInvokable``. When the
502 CPM scanner sees this word, it adds the function ``Cpm_print_integer``
503 to the file ``myprog.cpm.h``. The program includes ``myprog.cpm.h`` on
504 line 1, and initializes the code in there on line 12. Each call to
505 ``Cpm_print_integer`` on line 15 builds a message that invokes
506 ``print_integer``. The destination-argument ``CpmSend(i)`` causes the
507 message to be sent to the *i*\ ’th processor.
508
509 The effect of this program is that the first processor orders each of
510 the other processors to print a random number. Note that the example is
511 somewhat minimalist since it doesn’t contain any code for terminating
512 itself. Also note that it would have been more efficient to use an
513 explicit broadcast. Broadcasts are described later.
514
515 All launchers accept a *CpmDestination* as their first argument. A
516 *CpmDestination* is actually a pointer to a small C structure containing
517 routing and handling information. The CPM module has many built-in
518 functions that return *CpmDestination*\ s. Therefore, any of these can
519 be used as the first argument to a launcher:
520
521 -  **CpmSend(\ pe)** - the message is transmitted to processor pe with
522    maximum priority.
523
524 -  **CpmEnqueue(\ pe, queueing, priobits, prioptr)** - The message is
525    transmitted to processor *pe*, where it is enqueued with the specified
526    queueing strategy and priority. The *queueing*, *priobits*, and *prioptr*
527    arguments are the same as for **CqsEnqueueGeneral**.
528
529 -  **CpmEnqueueFIFO(\ pe)** - the message is transmitted to processor pe and
530    enqueued with the middle priority (zero), and FIFO relative to
531    messages with the same priority.
532
533 -  **CpmEnqueueLIFO(\ pe)** - the message is transmitted to processor pe and
534    enqueued with the middle priority (zero), and LIFO relative to
535    messages with the same priority.
536
537 -  **CpmEnqueueIFIFO(\ pe, prio)** - the message is transmitted to processor
538    pe and enqueued with the specified integer-priority prio, and FIFO
539    relative to messages with the same priority.
540
541 -  **CpmEnqueueILIFO(\ pe, prio)** - the message is transmitted to processor
542    pe and enqueued with the specified integer-priority prio, and LIFO
543    relative to messages with the same priority.
544
545 -  **CpmEnqueueBFIFO(\ pe, priobits, prioptr)** - the message is transmitted
546    to processor pe and enqueued with the specified bitvector-priority,
547    and FIFO relative to messages with the same priority.
548
549 -  **CpmEnqueueBLIFO(\ pe, priobits, prioptr)** - the message is transmitted
550    to processor pe and enqueued with the specified bitvector-priority,
551    and LIFO relative to messages with the same priority.
552
553 -  **CpmMakeThread(\ pe)** - The message is transmitted to processor pe
554    where a CthThread is created, and the thread invokes the specified
555    function.
556
557 All the functions shown above accept processor numbers as arguments.
558 Instead of supplying a processor number, one can also supply the special
559 symbols CPM_ALL or CPM_OTHERS, causing a broadcast. For example,
560
561 ::
562
563    Cpm_print_integer(CpmMakeThread(CPM_ALL), 5);
564
565 would broadcast a message to all the processors causing each processor
566 to create a thread, which would in turn invoke ``print_integer`` with
567 the argument 5.
568
569 CPM Packing and Unpacking
570 -------------------------
571
572 Functions preceded by the word **CpmInvokable** must have simple
573 argument lists. In particular, the argument list of a CpmInvokable
574 function can only contain cpm-single-arguments and cpm-array-arguments,
575 as defined by this grammar:
576
577 ::
578
579        cpm-single-argument :== typeword varname
580        cpm-array-argument  :== typeword '*' varname
581
582 When CPM sees the cpm-array-argument notation, CPM interprets it as
583 being a pointer to an array. In this case, CPM attempts to pack an
584 entire array into the message, whereas it only attempts to pack a single
585 element in the case of the cpm-single-argument notation.
586
587 Each cpm-array-argument must be preceded by a cpm-single-argument of
588 type ``CpmDim``. ``CpmDim`` is simply an alias for ``int``, but when CPM
589 sees an argument declared ``CpmDim``, it knows that the next argument
590 will be a cpm-array-argument, and it interprets the ``CpmDim`` argument
591 to be the size of the array. Given a pointer to the array, its size, and
592 its element-type, CPM handles the packing of array values as
593 automatically as it handles single values.
594
595 A second program, ``example2.c``, uses array arguments:
596
597 .. code-block:: c++
598    :linenos:
599
600    #include "example2.cpm.h"
601
602    CpmInvokable print_program_arguments(CpmDim argc, CpmStr *argv)
603    {
604      int i;
605      CmiPrintf("The program's arguments are: ");
606      for (i=0; i<argc; i++) CmiPrintf("%s ", argv[i]);
607      CmiPrintf("\n");
608    }
609
610    user_main(int argc, char **argv)
611    {
612      CpmModuleInit();
613      CpmInitializeThisModule();
614      if (CmiMyPe()==0)
615        Cpm_print_program_arguments(CpmSend(1), argc, argv);
616    }
617
618    main(int argc, char **argv)
619    {
620      ConverseInit(argc, argv, user_main, 0, 0);
621    }
622
623 The word ``CpmStr`` is a CPM built-in type, it represents a
624 null-terminated string:
625
626 ::
627
628         typedef char *CpmStr;
629
630 Therefore, the function ``print_program_arguments`` takes exactly the
631 same arguments as ``user_main``. In this example, the main program
632 running on processor 0 transmits the arguments to processor 1, which
633 prints them out.
634
635 Thus far, we have only shown functions whose prototypes contain builtin
636 CPM types. CPM has built-in knowledge of the following types: char,
637 short, int, long, float, double, CpmDim, and CpmStr (pointer to a
638 null-terminated string). However, you may also transmit user-defined
639 types in a CPM message.
640
641 For each (non-builtin) type the user wishes to pack, the user must
642 supply some pack and unpack routines. The subroutines needed depend upon
643 whether the type is a pointer or a simple type. Simple types are defined
644 to be those that contain no pointers at all. Note that some types are
645 neither pointers, nor simple types. CPM cannot currently handle such
646 types.
647
648 CPM knows which type is which only through the following declarations:
649
650 ::
651
652        CpmDeclareSimple(typeword);
653        CpmDeclarePointer(typeword);
654
655 The user must supply such declarations for each type that must be sent
656 via CPM.
657
658 When packing a value ``v`` which is a simple type, CPM uses the
659 following strategy. The generated code first converts ``v`` to network
660 interchange format by calling ``CpmPack_typename(&v)``, which must
661 perform the conversion in-place. It then copies ``v`` byte-for-byte into
662 the message and sends it. When the data arrives, it is extracted from
663 the message and converted back using ``CpmUnpack_typename(&v)``, again
664 in-place. The user must supply the pack and unpack routines.
665
666 When packing a value ``v`` which is a pointer, the generated code
667 determines how much space is needed in the message buffer by calling
668 ``CpmPtrSize_typename(v)``. It then transfers the data pointed to by
669 ``v`` into the message using ``CpmPtrPack_typename(p, v)``, where ``p``
670 is a pointer to the allocated space in the message buffer. When the
671 message arrives, the generated code extracts the packed data from the
672 message by calling ``CpmPtrUnpack_typename(p)``. The unpack function
673 must return a pointer to the unpacked data, which is allowed to still
674 contain pointers to the message buffer (or simply be a pointer to the
675 message buffer). When the invocation is done, the function
676 ``CpmPtrFree_typename(v)`` is called to free any memory allocated by the
677 unpack routine. The user must supply the size, pack, unpack, and free
678 routines.
679
680 The following program fragment shows the declaration of two user-defined
681 types:
682
683 .. code-block:: c++
684   :linenos:
685
686
687    typedef struct { double x,y; } coordinate;
688    CpmDeclareSimple(coordinate);
689
690    void CpmPack_coordinate(coordinate *p)
691    {
692      CpmPack_double(&(p->x));
693      CpmPack_double(&(p->y));
694    }
695
696    void CpmPack_coordinate(coordinate *p)
697    {
698      CpmUnpack_double(&(p->x));
699      CpmUnpack_double(&(p->y));
700    }
701
702    typedef int *intptr;
703    CpmDeclarePointer(intptr);
704
705    #define CpmPtrSize_intptr(p) sizeof(int)
706
707    void CpmPtrPack_intptr(void *p, intptr v)
708    {
709      *(int *)p = *v;
710      CpmPack_int((int *)p);
711    }
712
713    intptr CpmPtrUnpack_intptr(void *p)
714    {
715      CpmUnpack_int((int *)p);
716      return (int *)p;
717    }
718
719    #define CpmPtrFree_intptr(p) (0)
720
721    #include "example3.cpm.h"
722    ...
723
724 The first type declared in this file is the coordinate. Line 2 contains
725 the C type declaration, and line 3 notifies CPM that it is a simple
726 type, containing no pointers. Lines 5-9 declare the pack function, which
727 receives a pointer to a coordinate, and must pack it in place. It makes
728 use of the pack-function for doubles, which also packs in place. The
729 unpack function is similar.
730
731 The second type declared in this file is the intptr, which we intend to
732 mean a pointer to a single integer. On line 18 we notify CPM that the
733 type is a pointer, and that it should therefore use CpmPtrSize_intptr,
734 CpmPtrPack_intptr, CpmPtrUnpack_intptr, and CpmPtrFree_intptr. Line 20
735 shows the size function, a constant: we always need just enough space to
736 store one integer. The pack function copies the int into the message
737 buffer, and packs it in place. The unpack function unpacks it in place,
738 and returns an intptr, which points right to the unpacked integer which
739 is still in the message buffer. Since the int is still in the message
740 buffer, and not in dynamically allocated memory, the free function on
741 line 34 doesn’t have to do anything.
742
743 Note that the inclusion of the ``.cpm.h`` file comes after these type
744 and pack declarations: the ``.cpm.h`` file will reference these
745 functions and macros, therefore, they must already be defined.
746
747 Inventing New Types of CpmDestinations
748 --------------------------------------
749
750 It is possible for the user to create new types of CpmDestinations, and
751 to write functions that return these new destinations. In order to do
752 this, one must have a mental model of the steps performed when a Cpm
753 message is sent. This knowledge is only necessary to those wishing to
754 invent new kinds of destinations. Others can skip this section.
755
756 The basic steps taken when sending a CPM message are:
757
758 #. **The destination-structure is created.** The first argument to the
759    launcher is a CpmDestination. Therefore, before the launcher is
760    invoked, one typically calls a function (like CpmSend) to build the
761    destination-structure.
762
763 #. **The launcher allocates a message-buffer.** The buffer contains space
764    to hold a function-pointer and the function’s arguments. It also
765    contains space for an “envelope”, the size of which is determined by
766    a field in the destination-structure.
767
768 #. **The launcher stores the function-arguments in the message buffer.**
769    In doing so, the launcher converts the arguments to a contiguous
770    sequence of bytes.
771
772 #. **The launcher sets the message’s handler.** For every launcher, there
773    is a matching function called an *invoker* The launcher’s job is to
774    put the argument data in the message and send the message. The
775    *invoker*\ ’s job is to extract the argument data from the message and
776    call the user’s function. The launcher uses ``CmiSetHandler`` to tell
777    Converse to handle the message by calling the appropriate *invoker*.
778
779 #. **The message is sent, received, and handled.** The
780    destination-structure contains a pointer to a send-function. The
781    send-function is responsible for choosing the message’s destination
782    and making sure that it gets there and gets handled. The
783    send-function has complete freedom to implement this in any manner it
784    wishes. Eventually, though, the message should arrive at a
785    destination and its handler should be called.
786
787 #. **The user’s function is invoked.** The invoker extracts the function
788    arguments from the message buffer and calls the user’s function.
789
790 The *send-function* varies because messages take different routes to get
791 to their final destinations. Compare, for example, CpmSend to
792 CpmEnqueueFIFO. When CpmSend is used, the message goes straight to the
793 target processor and gets handled. When CpmEnqueueFIFO is used, the
794 message goes to the target processor, goes into the queue, comes out of
795 the queue, and *then* gets handled. The *send-function* must implement
796 not only the transmission of the message, but also the possible
797 “detouring” of the message through queues or into threads.
798
799 We now show an example CPM command, and describe the steps that are
800 taken when the command is executed. The command we will consider is this
801 one:
802
803 ::
804
805    Cpm_print_integer(CpmEnqueueFIFO(3), 12);
806
807 Which sends a message to processor 3, ordering it to call
808 ``print_integer(12)``.
809
810 The first step is taken by CpmEnqueueFIFO, which builds the
811 CpmDestination. The following is the code for CpmEnqueueFIFO:
812
813 ::
814
815    typedef struct CpmDestinationSend_s
816    {
817      void *(*sendfn)();
818      int envsize;
819      int pe;
820    }
821    *CpmDestinationSend;
822
823    CpmDestination CpmEnqueueFIFO(int pe)
824    {
825      static struct CpmDestinationSend_s ctrl;
826      ctrl.envsize = sizeof(int);
827      ctrl.sendfn  = CpmEnqueueFIFO1;
828      ctrl.pe = pe;
829      return (CpmDestination)&ctrl;
830    }
831
832 Notice that the CpmDestination structure varies, depending upon which
833 kind of destination is being used. In this case, the destination
834 structure contains a pointer to the send-function ``CpmEnqueueFIFO1``, a
835 field that controls the size of the envelope, and the
836 destination-processor. In a CpmDestination, the ``sendfn`` and
837 ``envsize`` fields are required, additional fields are optional.
838
839 After CpmEnqueueFIFO builds the destination-structure, the launcher
840 Cpm_print_integer is invoked. Cpm_print_integer performs all the steps
841 normally taken by a launcher:
842
843 #. **It allocates the message buffer.** In this case, it sets aside just
844    enough room for one int as an envelope, as dictated by the
845    destination-structure’s envsize field.
846
847 #. **It stores the function-arguments in the message-buffer.** In this
848    case, the function-arguments are just the integer 12.
849
850 #. **It sets the message’s handler.** In this case, the message’s handler
851    is set to a function that will extract the arguments and call
852    print_integer.
853
854 #. **It calls the send-function to send the message.**
855
856 The code for the send-function is here:
857
858 ::
859
860    void *CpmEnqueueFIFO1(CpmDestinationSend dest, int len, void *msg)
861    {
862      int *env = (int *)CpmEnv(msg);
863      env[0] = CmiGetHandler(msg);
864      CmiSetHandler(msg, CpvAccess(CpmEnqueueFIFO2_Index));
865      CmiSyncSendAndFree(dest->pe,len,msg);
866    }
867
868 The send-function CpmEnqueueFIFO1 starts by switching the handler. The
869 original handler is removed using ``CmiGetHandler``. It is set aside in
870 the message buffer in the “envelope” space described earlier — notice
871 the use of ``CpmEnv`` to obtain the envelope. This is the purpose of the
872 envelope in the message — it is a place where the send-function can
873 store information. The destination-function must anticipate how much
874 space the send-function will need, and it must specify that amount of
875 space in the destination-structure field *envsize*. In this case, the
876 envelope is used to store the original handler, and the message’s
877 handler is set to an internal function called ``CpmEnqueueFIFO2``.
878
879 After switching the handler, ``CpmEnqueueFIFO1`` sends the message.
880 Eventually, the message will be received by ``CsdScheduler``, and its
881 handler will be called. The result will be that ``CpmEnqueueFIFO2`` will
882 be called on the destination processor. Here is the code for
883 ``CpmEnqueueFIFO2``:
884
885 ::
886
887    void CpmEnqueueFIFO2(void *msg)
888    {
889      int *env;
890      CmiGrabBuffer(&msg);
891      env = (int *)CpmEnv(msg);
892      CmiSetHandler(msg, env[0]);
893      CsdEnqueueFIFO(msg);
894    }
895
896 This function takes ownership of the message-buffer from Converse using
897 ``CmiGrabBuffer``. It extracts the original handler from the envelope
898 (the handler that calls ``print_integer``), and restores it using
899 ``CmiSetHandler``. Having done so, it enqueues the message with the FIFO
900 queueing policy. Eventually, the scheduler picks the message from the
901 queue, and ``print_integer`` is invoked.
902
903 In summary, the procedure for implementing new kinds of destinations is
904 to write one send-function, one function returning a CpmDestination
905 (which contains a reference to the send-function), and one or more
906 Converse handlers to manipulate the message.
907
908 The destination-function must return a pointer to a
909 “destination-structure”, which can in fact be any structure matching the
910 following specifications:
911
912 -  The first field must be a pointer to a send-function,
913
914 -  The second field must the an integer, the envelope-size.
915
916 This pointer must be coerced to type CpmDestination.
917
918 The send-function must have the following prototype:
919
920 ::
921
922        void sendfunction(CpmDestination dest, int msglen, void *msgptr)
923
924 It can access the envelope of the message using CpmEnv:
925
926 ::
927
928        int *CpmEnv(void *msg);
929
930 It can also access the data stored in the destination-structure by the
931 destination-function.
932
933 Load Balancing
934 ==============
935
936 Using Converse Load Balancers
937 -----------------------------
938
939 This module defines a function **CldEnqueue** that sends a message to a
940 lightly-loaded processor. It automates the process of finding a
941 lightly-loaded processor.
942
943 The function **CldEnqueue** is extremely sophisticated. It does not
944 choose a processor, send the message, and forget it. Rather, it puts the
945 message into a pool of movable work. The pool of movable work gradually
946 shrinks as it is consumed (processed), but in most programs, there is
947 usually quite a bit of movable work available at any given time. As load
948 conditions shift, the load balancers shifts the pool around,
949 compensating. Any given message may be shifted more than once, as part
950 of the pool.
951
952 **CldEnqueue** also accounts for priorities. Normal load-balancers try
953 to make sure that all processors have some work to do. The function
954 **CldEnqueue** goes a step further: it tries to make sure that all
955 processors have some reasonably high-priority work to do. This can be
956 extremely helpful in AI search applications.
957
958 The two assertions above should be qualified: **CldEnqueue** can use
959 these sophisticated strategies, but it is also possible to configure it
960 for different behavior. When you compile and link your program, you
961 choose a *load-balancing strategy*. That means you link in one of several
962 implementations of the load-balancer. Most are sophisticated, as
963 described above. But some are simple and cheap, like the random
964 strategy. The process of choosing a strategy is described in the manual
965 *Converse Installation and Usage*.
966
967 Before you send a message using **CldEnqueue**, you must write an *info*
968 function with this prototype:
969
970 ``void InfoFn(void *msg, CldPackFn *pfn, int *len, int *queueing, int
971 *priobits, unsigned int *prioptr);``
972
973 The load balancer will call the
974 info function when it needs to know various things about the message.
975 The load balancer will pass in the message via the parameter ``msg``.
976 The info function’s job is to “fill in” the other parameters. It must
977 compute the length of the message, and store it at ``*len``. It must
978 determine the *pack* function for the message, and store a pointer to it
979 at ``*pfm``. It must identify the priority of the message, and the
980 queueing strategy that must be used, storing this information at
981 ``*queueing``, ``*priobits``, and ``*prioptr``. Caution: the priority
982 will not be copied, so the ``*prioptr`` should probably be made to point
983 to the message itself.
984
985 After the user of **CldEnqueue** writes the “info” function, the user
986 must register it, using this:
987
988 ``int CldRegisterInfoFn(CldInfoFn fn)``
989
990 Accepts a pointer to an info-function. Returns an integer index for the
991 info-function. This index will be needed in **CldEnqueue**.
992
993 Normally, when you send a message, you pack up a bunch of data into a
994 message, send it, and unpack it at the receiving end. It is sometimes
995 possible to perform an optimization, though. If the message is bound for
996 a processor within the same address space, it isn’t always necessary to
997 copy all the data into the message. Instead, it may be sufficient to
998 send a message containing only a pointer to the data. This saves much
999 packing, unpacking, and copying effort. It is frequently useful, since
1000 in a properly load-balanced program, a great many messages stay inside a
1001 single address space.
1002
1003 With CldEnqueue, you don’t know in advance whether a message is going to
1004 cross address-space boundaries or not. If it’s to cross address spaces,
1005 you need to use the “long form”, but if it’s to stay inside an address
1006 space, you want to use the faster “short form”. We call this
1007 “conditional packing.” When you send a message with **CldEnqueue**, you
1008 should initially assume it will not cross address space boundaries. In
1009 other words, you should send the “short form” of the message, containing
1010 pointers. If the message is about to leave the address space, the load
1011 balancer will call your pack function, which must have this prototype:
1012
1013 ``void PackFn(void **msg)``
1014
1015 The pack function is handed a pointer to a
1016 pointer to the message (yes, a pointer to a pointer). The pack function
1017 is allowed to alter the message in place, or replace the message with a
1018 completely different message. The intent is that the pack function
1019 should replace the “short form” of the message with the “long form” of
1020 the message. Note that if it replaces the message, it should CmiFree the
1021 old message.
1022
1023 Of course, sometimes you don’t use conditional packing. In that case,
1024 there is only one form of the message. In that case, your pack function
1025 can be a no-op.
1026
1027 Pack functions must be registered using this:
1028
1029 ``int CldRegisterPackFn(CldPackFn fn)``
1030
1031 Accepts a pointer to an pack-function. Returns an integer index for the
1032 pack-function. This index will be needed in **CldEnqueue**.
1033
1034 Normally, **CldEnqueue** sends a message to a lightly-loaded processor.
1035 After doing this, it enqueues the message with the appropriate priority.
1036 The function CldEnqueue can also be used as a mechanism to simply
1037 enqueue a message on a remote processor with a priority. In other words,
1038 it can be used as a prioritized send-function. To do this, one of the
1039 CldEnqueue parameters allows you to override the load-balancing behavior
1040 and lets you choose a processor yourself.
1041
1042 The prototype for **CldEnqueue** is as follows:
1043
1044 ``void CldEnqueue(int pe, void *msg, int infofn)``
1045
1046 The argument ``msg`` is a pointer to the message. The parameter
1047 ``infofn`` represents a function that can analyze the message. The
1048 parameter ``packfn`` represents a function that can pack the message. If
1049 the parameter ``pe`` is ``CLD_ANYWHERE``, the message is sent to a
1050 lightly-loaded processor and enqueued with the appropriate priority. If
1051 the parameter ``pe`` is a processor number, the message is sent to the
1052 specified processor and enqueued with the appropriate priority.
1053 **CldEnqueue** frees the message buffer using **CmiFree**.
1054
1055 The following simple example illustrates how a Converse program can make
1056 use of the load balancers.
1057
1058 ``hello.c:``
1059
1060 ::
1061
1062    #include <stdio.h>
1063    #include "converse.h"
1064    #define CHARES 10
1065
1066    void startup(int argc, char *argv[]);
1067    void registerAndInitialize();
1068
1069    typedef struct pemsgstruct
1070    {
1071      char header[CmiExtHeaderSizeBytes];
1072      int pe, id, pfnx;
1073      int queuing, priobits;
1074      unsigned int prioptr;
1075    } pemsg;
1076
1077    CpvDeclare(int, MyHandlerIndex);
1078    CpvDeclare(int, InfoFnIndex);
1079    CpvDeclare(int, PackFnIndex);
1080
1081    int main(int argc, char *argv[])
1082    {
1083      ConverseInit(argc, argv, startup, 0, 0);
1084      CsdScheduler(-1);
1085    }
1086
1087    void startup(int argc, char *argv[])
1088    {
1089      pemsg *msg;
1090      int i;
1091
1092      registerAndInitialize();
1093      for (i=0; i<CHARES; i++) {
1094        msg = (pemsg *)malloc(sizeof(pemsg));
1095        msg->pe = CmiMyPe();
1096        msg->id = i;
1097        msg->pfnx = CpvAccess(PackFnIndex);
1098        msg->queuing = CQS_QUEUEING_FIFO;
1099        msg->priobits = 0;
1100        msg->prioptr = 0;
1101        CmiSetHandler(msg, CpvAccess(MyHandlerIndex));
1102        CmiPrintf("[%d] sending message %d\n", msg->pe, msg->id);
1103        CldEnqueue(CLD_ANYWHERE, msg, CpvAccess(InfoFnIndex));
1104        /*    CmiSyncSend(i, sizeof(pemsg), &msg); */
1105      }
1106    }
1107
1108    void MyHandler(pemsg *msg)
1109    {
1110      CmiPrintf("Message %d created on %d handled by %d.\n", msg->id, msg->pe,
1111             CmiMyPe());
1112    }
1113
1114    void InfoFn(pemsg *msg, CldPackFn *pfn, int *len, int *queuing, int *priobits,
1115             unsigned int *prioptr)
1116    {
1117      *pfn = (CldPackFn)CmiHandlerToFunction(msg->pfnx);
1118      *len = sizeof(pemsg);
1119      *queuing = msg->queuing;
1120      *priobits = msg->priobits;
1121      prioptr = &(msg->prioptr);
1122    }
1123
1124    void PackFn(pemsg **msg)
1125    {
1126    }
1127
1128    void registerAndInitialize()
1129    {
1130      CpvInitialize(int, MyHandlerIndex);
1131      CpvAccess(MyHandlerIndex) = CmiRegisterHandler(MyHandler);
1132      CpvInitialize(int, InfoFnIndex);
1133      CpvAccess(InfoFnIndex) = CldRegisterInfoFn((CldInfoFn)InfoFn);
1134      CpvInitialize(int, PackFnIndex);
1135      CpvAccess(PackFnIndex) = CldRegisterPackFn((CldPackFn)PackFn);
1136    }
1137
1138 How to Write a Load Balancer for Converse/Charm++
1139 -------------------------------------------------
1140
1141 .. _introduction-2:
1142
1143 Introduction
1144 ~~~~~~~~~~~~
1145
1146 This manual details how to write your own general-purpose message-based
1147 load balancer for Converse. A Converse load balancer can be used by any
1148 Converse program, but also serves as a *seed* load balancer for Charm++
1149 chare creation messages. Specifically, to use a load balancer, you would
1150 pass messages to CldEnqueue rather than directly to the scheduler. This
1151 is the default behavior with chare creation message in Charm++. Thus,
1152 the primary provision of a new load balancer is an implementation of the
1153 CldEnqueue function.
1154
1155 Existing Load Balancers and Provided Utilities
1156 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1157
1158 Throughout this manual, we will occasionally refer to the source code of
1159 two provided load balancers, the random initial placement load balancer
1160 (``cldb.rand.c``) and the virtual topology-based load balancer
1161 (``cldb.neighbor.c``) which applies virtual topology including dense
1162 graph to construct neighbors. The functioning of these balancers is
1163 described in the Charm++ manual load balancing section.
1164
1165 In addition, a special utility is provided that allows us to add and
1166 remove load-balanced messages from the scheduler’s queue. The source
1167 code for this is available in ``cldb.c``. The usage of this utility will
1168 also be described here in detail.
1169
1170 A Sample Load Balancer
1171 ----------------------
1172
1173 This manual steps through the design of a load balancer using an example
1174 which we will call ``test``. The ``test`` load balancer has each
1175 processor periodically send half of its load to its neighbor in a ring.
1176 Specifically, for N processors, processor K will send approximately half
1177 of its load to (K+1)%N, every 100 milliseconds (this is an example only;
1178 we leave the genius approaches up to you).
1179
1180 Minimal Requirements
1181 ~~~~~~~~~~~~~~~~~~~~
1182
1183 The minimal requirements for a load balancer are illustrated by the
1184 following code.
1185
1186 ::
1187
1188    #include <stdio.h>
1189    #include "converse.h"
1190
1191    const char *CldGetStrategy(void)
1192    {
1193      return "test";
1194    }
1195
1196    CpvDeclare(int, CldHandlerIndex);
1197
1198    void CldHandler(void *msg)
1199    {
1200      CldInfoFn ifn; CldPackFn pfn;
1201      int len, queueing, priobits; unsigned int *prioptr;
1202
1203      CmiGrabBuffer((void **)&msg);
1204      CldRestoreHandler(msg);
1205      ifn = (CldInfoFn)CmiHandlerToFunction(CmiGetInfo(msg));
1206      ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1207      CsdEnqueueGeneral(msg, queueing, priobits, prioptr);
1208    }
1209
1210    void CldEnqueue(int pe, void *msg, int infofn)
1211    {
1212      int len, queueing, priobits; unsigned int *prioptr;
1213      CldInfoFn ifn = (CldInfoFn)CmiHandlerToFunction(infofn);
1214      CldPackFn pfn;
1215
1216      if (pe == CLD_ANYWHERE) {
1217        /* do what you want with the message; in this case we'll just keep
1218           it local */
1219        ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1220        CmiSetInfo(msg,infofn);
1221        CsdEnqueueGeneral(msg, queueing, priobits, prioptr);
1222      }
1223      else {
1224        /* pe contains a particular destination or broadcast */
1225        ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1226        if (pfn) {
1227          pfn(&msg);
1228          ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1229        }
1230        CldSwitchHandler(msg, CpvAccess(CldHandlerIndex));
1231        CmiSetInfo(msg,infofn);
1232        if (pe==CLD_BROADCAST)
1233          CmiSyncBroadcastAndFree(len, msg);
1234        else if (pe==CLD_BROADCAST_ALL)
1235          CmiSyncBroadcastAllAndFree(len, msg);
1236        else CmiSyncSendAndFree(pe, len, msg);
1237      }
1238    }
1239
1240    void CldModuleInit()
1241    {
1242      char *argv[] = { NULL };
1243      CpvInitialize(int, CldHandlerIndex);
1244      CpvAccess(CldHandlerIndex) = CmiRegisterHandler(CldHandler);
1245      CldModuleGeneralInit(argv);
1246    }
1247
1248 The primary function a load balancer must provide is the **CldEnqueue**
1249 function, which has the following prototype:
1250
1251 ``void CldEnqueue(int pe, void *msg, int infofn);``
1252
1253 This function takes three parameters: ``pe``, ``msg`` and ``infofn``.
1254 ``pe`` is the intended destination of the ``msg``. ``pe`` may take on
1255 one of the following values:
1256
1257 -  Any valid processor number - the message must be sent to that
1258    processor
1259
1260 -  ``CLD_ANYWHERE`` - the message can be placed on any processor
1261
1262 -  ``CLD_BROADCAST`` - the message must be sent to all processors
1263    excluding the local processor
1264
1265 -  ``CLD_BROADCAST_ALL`` - the message must be sent to all processors
1266    including the local processor
1267
1268 **CldEnqueue** must handle all of these possibilities. The only case in
1269 which the load balancer should get control of a message is when
1270 ``pe = CLD_ANYWHERE``. All other messages must be sent off to their
1271 intended destinations and passed on to the scheduler as if they never
1272 came in contact with the load balancer.
1273
1274 The integer parameter ``infofn`` is a handler index for a user-provided
1275 function that allows CldEnqueue to extract information about (mostly
1276 components of) the message ``msg``.
1277
1278 Thus, an implementation of the **CldEnqueue** function might have the
1279 following structure:
1280
1281 ::
1282
1283    void CldEnqueue(int pe, void *msg, int infofn)
1284    {
1285      ...
1286      if (pe == CLD_ANYWHERE)
1287        /* These messages can be load balanced */
1288      else if (pe == CmiMyPe())
1289        /* Enqueue the message in the scheduler locally */
1290      else if (pe==CLD_BROADCAST)
1291        /* Broadcast to all but self */
1292      else if (pe==CLD_BROADCAST_ALL)
1293        /* Broadcast to all plus self */
1294      else /* Specific processor number was specified */
1295        /* Send to specific processor */
1296    }
1297
1298 In order to fill in the code above, we need to know more about the
1299 message before we can send it off to a scheduler’s queue, either locally
1300 or remotely. For this, we have the info function. The prototype of an
1301 info function must be as follows:
1302
1303 ``void ifn(void *msg, CldPackFn *pfn, int *len, int *queueing,
1304 int *priobits, unsigned int **prioptr);``
1305
1306 Thus, to use the info function, we need to get the actual function via
1307 the handler index provided to **CldEnqueue**. Typically,
1308 **CldEnqueue** would contain the following declarations:
1309
1310 ::
1311
1312      int len, queueing, priobits;
1313      unsigned int *prioptr;
1314      CldPackFn pfn;
1315      CldInfoFn ifn = (CldInfoFn)CmiHandlerToFunction(infofn);
1316
1317 Subsequently, a call to ``ifn`` would look like this:
1318
1319 ::
1320
1321      ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1322
1323 The info function extracts information from the message about its size,
1324 queuing strategy and priority, and also a pack function, which will be
1325 used when we need to send the message elsewhere. For now, consider the
1326 case where the message is to be locally enqueued:
1327
1328 ::
1329
1330      ...
1331      else if (pe == CmiMyPe())
1332        {
1333          ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1334          CsdEnqueueGeneral(msg, queueing, priobits, prioptr);
1335        }
1336      ...
1337
1338 Thus, we see the info function is used to extract info from the message
1339 that is necessary to pass on to **CsdEnqueueGeneral**.
1340
1341 In order to send the message to a remote destination and enqueue it in
1342 the scheduler, we need to pack it up with a special pack function so
1343 that it has room for extra handler information and a reference to the
1344 info function. Therefore, before we handle the last three cases of
1345 **CldEnqueue**, we have a little extra work to do:
1346
1347 ::
1348
1349      ...
1350      else
1351        {
1352          ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1353          if (pfn) {
1354            pfn(&msg);
1355            ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1356          }
1357          CldSwitchHandler(msg, CpvAccess(CldHandlerIndex));
1358          CmiSetInfo(msg,infofn);
1359          ...
1360
1361 Calling the info function once gets the pack function we need, if there
1362 is one. We then call the pack function which rearranges the message
1363 leaving space for the info function, which we will need to call on the
1364 message when it is received at its destination, and also room for the
1365 extra handler that will be used on the receiving side to do the actual
1366 enqueuing. **CldSwitchHandler** is used to set this extra handler, and
1367 the receiving side must restore the original handler.
1368
1369 In the above code, we call the info function again because some of the
1370 values may have changed in the packing process.
1371
1372 Finally, we handle our last few cases:
1373
1374 ::
1375
1376      ...
1377          if (pe==CLD_BROADCAST)
1378            CmiSyncBroadcastAndFree(len, msg);
1379          else if (pe==CLD_BROADCAST_ALL)
1380            CmiSyncBroadcastAllAndFree(len, msg);
1381          else CmiSyncSendAndFree(pe, len, msg);
1382        }
1383    }
1384
1385 The above example also provides **CldHandler** which is used to receive
1386 messages that **CldEnqueue** forwards to other processors.
1387
1388 ::
1389
1390    CpvDeclare(int, CldHandlerIndex);
1391
1392    void CldHandler(void *msg)
1393    {
1394      CldInfoFn ifn; CldPackFn pfn;
1395      int len, queueing, priobits; unsigned int *prioptr;
1396
1397      CmiGrabBuffer((void **)&msg);
1398      CldRestoreHandler(msg);
1399      ifn = (CldInfoFn)CmiHandlerToFunction(CmiGetInfo(msg));
1400      ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1401      CsdEnqueueGeneral(msg, queueing, priobits, prioptr);
1402    }
1403
1404 Note that the **CldHandler** properly restores the message’s original
1405 handler using **CldRestoreHandler**, and calls the info function to
1406 obtain the proper parameters to pass on to the scheduler. We talk about
1407 this more below.
1408
1409 Finally, Converse initialization functions call **CldModuleInit** to
1410 initialize the load balancer module.
1411
1412 ::
1413
1414    void CldModuleInit()
1415    {
1416      char *argv[] = { NULL };
1417      CpvInitialize(int, CldHandlerIndex);
1418      CpvAccess(CldHandlerIndex) = CmiRegisterHandler(CldHandler);
1419      CldModuleGeneralInit(argv);
1420
1421      /* call other init processes here */
1422      CldBalance();
1423    }
1424
1425 Provided Load Balancing Facilities
1426 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1427
1428 Converse provides a number of structures and functions to aid in load
1429 balancing (see cldb.c). Foremost amongst these is a method for queuing
1430 tokens of messages in a processor’s scheduler in a way that they can be
1431 removed and relocated to a different processor at any time. The
1432 interface for this module is as follows:
1433
1434 ::
1435
1436    void CldSwitchHandler(char *cmsg, int handler)
1437    void CldRestoreHandler(char *cmsg)
1438    int CldCountTokens()
1439    int CldLoad()
1440    void CldPutToken(char *msg)
1441    void CldGetToken(char **msg)
1442    void CldModuleGeneralInit(char **argv)
1443
1444 Messages normally have a handler index associated with them, but in
1445 addition they have extra space for an additional handler. This is used
1446 by the load balancer when we use an intermediate handler (typically
1447 **CldHandler**) to handle the message when it is received after
1448 relocation. To do this, we use **CldSwitchHandler** to temporarily swap
1449 the intended handler with the load balancer handler. When the message is
1450 received, **CldRestoreHandler** is used to change back to the intended
1451 handler.
1452
1453 **CldPutToken** puts a message in the scheduler queue in such a way that
1454 it can be retrieved from the queue. Once the message gets handled, it
1455 can no longer be retrieved. **CldGetToken** retrieves a message that was
1456 placed in the scheduler queue in this way. **CldCountTokens** tells you
1457 how many tokens are currently retrievable. **CldLoad** gives a slightly
1458 more accurate estimate of message load by counting the total number of
1459 messages in the scheduler queue.
1460
1461 **CldModuleGeneralInit** is used to initialize this load balancer helper
1462 module. It is typically called from the load balancer’s
1463 **CldModuleInit** function.
1464
1465 The helper module also provides the following functions:
1466
1467 ::
1468
1469    void CldMultipleSend(int pe, int numToSend)
1470    int CldRegisterInfoFn(CldInfoFn fn)
1471    int CldRegisterPackFn(CldPackFn fn)
1472
1473 **CldMultipleSend** is generally useful for any load balancer that sends
1474 multiple messages to one processor. It works with the token queue module
1475 described above. It attempts to retrieve up to ``numToSend`` messages,
1476 and then packs them together and sends them, via CmiMultipleSend, to
1477 ``pe``. If the number and/or size of the messages sent is very large,
1478 **CldMultipleSend** will transmit them in reasonably sized parcels. In
1479 addition, the **CldBalanceHandler** and its associated declarations and
1480 initializations are required to use it.
1481
1482 You may want to use the three status variables. These can be used to
1483 keep track of what your LB is doing (see usage in cldb.neighbor.c and
1484 itc++queens program).
1485
1486 ::
1487
1488    CpvDeclare(int, CldRelocatedMessages);
1489    CpvDeclare(int, CldLoadBalanceMessages);
1490    CpvDeclare(int, CldMessageChunks);
1491
1492 The two register functions register *info* and *pack* functions, returning
1493 an index for the functions. Info functions are used by the load balancer
1494 to extract the various components from a message. Amongst these
1495 components is the pack function index. If necessary, the pack function
1496 can be used to pack a message that is about to be relocated to another
1497 processor. Information on how to write info and pack functions is
1498 available in the load balancing section of the Converse Extensions
1499 manual.
1500
1501 Finishing the ``Test`` Balancer
1502 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1503
1504 The ``test`` balancer is a somewhat silly strategy in which every
1505 processor attempts to get rid of half of its load by periodically
1506 sending it to someone else, regardless of the load at the destination.
1507 Hopefully, you won’t actually use this for anything important!
1508
1509 The ``test`` load balancer is available in
1510 charm/src/Common/conv-ldb/cldb.test.c. To try out your own load balancer
1511 you can use this filename and SUPER_INSTALL will compile it and you can
1512 link it into your Charm++ programs with -balance test. (To add your own
1513 new balancers permanently and give them another name other than "test"
1514 you will need to change the Makefile used by SUPER_INSTALL. Don’t worry
1515 about this for now.) The cldb.test.c provides a good starting point for
1516 new load balancers.
1517
1518 Look at the code for the ``test`` balancer below, starting with the
1519 **CldEnqueue** function. This is almost exactly as described earlier.
1520 One exception is the handling of a few extra cases: specifically if we
1521 are running the program on only one processor, we don’t want to do any
1522 load balancing. The other obvious difference is in the first case: how
1523 do we handle messages that can be load balanced? Rather than enqueuing
1524 the message directly with the scheduler, we make use of the token queue.
1525 This means that messages can later be removed for relocation.
1526 **CldPutToken** adds the message to the token queue on the local
1527 processor.
1528
1529 ::
1530
1531    #include <stdio.h>
1532    #include "converse.h"
1533    #define PERIOD 100
1534    #define MAXMSGBFRSIZE 100000
1535
1536    const char *CldGetStrategy(void)
1537    {
1538      return "test";
1539    }
1540
1541    CpvDeclare(int, CldHandlerIndex);
1542    CpvDeclare(int, CldBalanceHandlerIndex);
1543    CpvDeclare(int, CldRelocatedMessages);
1544    CpvDeclare(int, CldLoadBalanceMessages);
1545    CpvDeclare(int, CldMessageChunks);
1546
1547    void CldDistributeTokens()
1548    {
1549      int destPe = (CmiMyPe()+1)%CmiNumPes(), numToSend;
1550
1551      numToSend = CldLoad() / 2;
1552      if (numToSend > CldCountTokens())
1553        numToSend = CldCountTokens() / 2;
1554      if (numToSend > 0)
1555        CldMultipleSend(destPe, numToSend);
1556      CcdCallFnAfter((CcdVoidFn)CldDistributeTokens, NULL, PERIOD);
1557    }
1558
1559    void CldBalanceHandler(void *msg)
1560    {
1561      CmiGrabBuffer((void **)&msg);
1562      CldRestoreHandler(msg);
1563      CldPutToken(msg);
1564    }
1565
1566    void CldHandler(void *msg)
1567    {
1568      CldInfoFn ifn; CldPackFn pfn;
1569      int len, queueing, priobits; unsigned int *prioptr;
1570
1571      CmiGrabBuffer((void **)&msg);
1572      CldRestoreHandler(msg);
1573      ifn = (CldInfoFn)CmiHandlerToFunction(CmiGetInfo(msg));
1574      ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1575      CsdEnqueueGeneral(msg, queueing, priobits, prioptr);
1576    }
1577
1578    void CldEnqueue(int pe, void *msg, int infofn)
1579    {
1580      int len, queueing, priobits; unsigned int *prioptr;
1581      CldInfoFn ifn = (CldInfoFn)CmiHandlerToFunction(infofn);
1582      CldPackFn pfn;
1583
1584      if ((pe == CLD_ANYWHERE) && (CmiNumPes() > 1)) {
1585        ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1586        CmiSetInfo(msg,infofn);
1587        CldPutToken(msg);
1588      }
1589      else if ((pe == CmiMyPe()) || (CmiNumPes() == 1)) {
1590        ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1591        CmiSetInfo(msg,infofn);
1592        CsdEnqueueGeneral(msg, queueing, priobits, prioptr);
1593      }
1594      else {
1595        ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1596        if (pfn) {
1597          pfn(&msg);
1598          ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
1599        }
1600        CldSwitchHandler(msg, CpvAccess(CldHandlerIndex));
1601        CmiSetInfo(msg,infofn);
1602        if (pe==CLD_BROADCAST)
1603          CmiSyncBroadcastAndFree(len, msg);
1604        else if (pe==CLD_BROADCAST_ALL)
1605          CmiSyncBroadcastAllAndFree(len, msg);
1606        else CmiSyncSendAndFree(pe, len, msg);
1607      }
1608    }
1609
1610    void CldModuleInit()
1611    {
1612      char *argv[] = { NULL };
1613      CpvInitialize(int, CldHandlerIndex);
1614      CpvAccess(CldHandlerIndex) = CmiRegisterHandler(CldHandler);
1615      CpvInitialize(int, CldBalanceHandlerIndex);
1616      CpvAccess(CldBalanceHandlerIndex) = CmiRegisterHandler(CldBalanceHandler);
1617      CpvInitialize(int, CldRelocatedMessages);
1618      CpvInitialize(int, CldLoadBalanceMessages);
1619      CpvInitialize(int, CldMessageChunks);
1620      CpvAccess(CldRelocatedMessages) = CpvAccess(CldLoadBalanceMessages) =
1621        CpvAccess(CldMessageChunks) = 0;
1622      CldModuleGeneralInit(argv);
1623      if (CmiNumPes() > 1)
1624        CldDistributeTokens();
1625    }
1626
1627 Now look two functions up from **CldEnqueue**. We have an additional
1628 handler besides the **CldHandler**: the **CldBalanceHandler**. The
1629 purpose of this special handler is to receive messages that can be still
1630 be relocated again in the future. Just like the first case of
1631 **CldEnqueue** uses **CldPutToken** to keep the message retrievable,
1632 **CldBalanceHandler** does the same with relocatable messages it
1633 receives. **CldHandler** is only used when we no longer want the message
1634 to have the potential for relocation. It places messages irretrievably
1635 in the scheduler queue.
1636
1637 Next we look at our initialization functions to see how the process gets
1638 started. The **CldModuleInit** function gets called by the common
1639 Converse initialization code and starts off the periodic load
1640 distribution process by making a call to **CldDistributeTokens**. The
1641 entirety of the balancing is handled by the periodic invocation of this
1642 function. It computes an approximation of half of the PE’s total load
1643 (**CsdLength**\ ()), and if that amount exceeds the number of movable
1644 messages ( **CldCountTokens**\ ()), we attempt to move all of the
1645 movable messages. To do this, we pass this number of messages to move
1646 and the number of the PE to move them to, to the **CldMultipleSend**
1647 function.
1648
1649 .. _conv-futures:
1650
1651 Futures
1652 =======
1653
1654 This library supports the *future* abstraction, defined and used by
1655 Halstead and other researchers.
1656
1657 **Cfuture CfutureCreate()**
1658
1659 Returns the handle of an empty future. The future is said to reside on
1660 the processor that created it. The handle is a *global* reference to the
1661 future, in other words, it may be copied freely across processors.
1662 However, while the handle may be moved across processors freely, some
1663 operations can only be performed on the processor where the future
1664 resides.
1665
1666 **Cfuture CfutureSet(Cfuture future, void \*value, int nbytes)**
1667
1668 Makes a copy of the value and stores it in the future. CfutureSet may be
1669 performed on processors other than the one where the future resides. If
1670 done remotely, the copy of the value is created on the processor where
1671 the future resides.
1672
1673 **void \*CfutureWait(Cfuture fut)**
1674
1675 Waits until the future has been filled, then returns a pointer to the
1676 contents of the future. If the future has already been filled, this
1677 happens immediately (without blocking). Caution: CfutureWait can only be
1678 done on the processor where the Cfuture resides. A second caution:
1679 blocking operations (such as this one) can only be done in user-created
1680 threads.
1681
1682 **void CfutureDestroy(Cfuture f)**
1683
1684 Frees the space used by the specified Cfuture. This also frees the value
1685 stored in the future. Caution: this operation can only be done on the
1686 processor where the Cfuture resides.
1687
1688 **void\* CfutureCreateValue(int nbytes)**
1689
1690 Allocates the specified amount of memory and returns a pointer to it.
1691 This buffer can be filled with data and stored into a future, using
1692 CfutureStoreBuffer below. This combination is faster than using
1693 CfutureSet directly.
1694
1695 **void CfutureStoreValue(Cfuture fut, void \*value)**
1696
1697 Make a copy of the value and stores it in the future, destroying the
1698 original copy of the value. This may be significantly faster than the
1699 more general function, CfutureSet (it may avoid copying). This function
1700 can *only* used to store values that were previously extracted from
1701 other futures, or values that were allocated using CfutureCreateValue.
1702
1703 **void CfutureModuleInit()**
1704
1705 This function initializes the futures module. It must be called once on
1706 each processor, during the handler-registration process (see the
1707 Converse manual regarding CmiRegisterHandler).
1708
1709 Converse-POSIX threads
1710 ======================
1711
1712 We have implemented the POSIX threads API on top of Converse threads. To
1713 use the Converse-pthreads, you must include the header file:
1714
1715 ``#include <cpthreads.h>``
1716
1717 Refer to the POSIX threads documentation for the documentation on the
1718 pthreads functions and types. Although Converse-pthreads threads are
1719 POSIX-compliant in most ways, there are some specific things one needs
1720 to know to use our implementation.
1721
1722 Pthreads and Converse
1723 ---------------------
1724
1725 Our pthreads implementation is designed to exist within a Converse
1726 environment. For example, to send messages inside a POSIX program, you
1727 would still use the usual Converse messaging primitives.
1728
1729 Suppressing Name Conflicts
1730 --------------------------
1731
1732 Some people may wish to use Converse pthreads on machines that already
1733 have a pthreads implementation in the standard library. This may cause
1734 some name-conflicts as we define the pthreads functions, and the system
1735 include files do too. To avoid such conflicts, we provide an alternative
1736 set of names beginning with the word Cpthread. These names are
1737 interchangeable with their pthread equivalents. In addition, you may
1738 prevent Converse from defining the pthread names at all with the
1739 preprocessor symbol SUPPRESS_PTHREADS:
1740
1741 ::
1742
1743    #define SUPPRESS_PTHREADS
1744    #include <cpthreads.h>
1745
1746 Interoperating with Other Thread Packages
1747 -----------------------------------------
1748
1749 Converse programs are typically multilingual programs. There may be
1750 modules written using POSIX threads, but other modules may use other
1751 thread APIs. The POSIX threads implementation has the following
1752 restriction: you may only call the pthreads functions from inside
1753 threads created with pthread_create. Threads created by other thread
1754 packages (for example, the CthThread package) may not use the pthreads
1755 functions.
1756
1757 Preemptive Context Switching
1758 ----------------------------
1759
1760 Most implementations of POSIX threads perform time-slicing: when a
1761 thread has run for a while, it automatically gives up the CPU to another
1762 thread. Our implementation is currently nonpreemptive (no time-slicing).
1763 Threads give up control at two points:
1764
1765 -  If they block (eg, at a mutex).
1766
1767 -  If they call pthread_yield().
1768
1769 Usually, the first rule is sufficient to make most programs work.
1770 However, a few programs (particularly, those that busy-wait) may need
1771 explicit insertion of yields.
1772
1773 Limits on Blocking Operations in main
1774 -------------------------------------
1775
1776 Converse has a rule about blocking operations — there are certain pieces
1777 of code that may not block. This was an efficiency decision. In
1778 particular, the main function, Converse handlers, and the Converse
1779 startup function (see ConverseInit) may not block. You must be aware of
1780 this when using the POSIX threads functions with Converse.
1781
1782 There is a contradiction here — the POSIX standard requires that the
1783 pthreads functions work from inside ``main``. However, many of them
1784 block, and Converse forbids blocking inside ``main``. This contradiction
1785 can be resolved by renaming your posix-compliant ``main`` to something
1786 else: for example, ``mymain``. Then, through the normal Converse startup
1787 procedure, create a POSIX thread to run ``mymain``. We provide a
1788 convenience function to do this, called Cpthreads_start_main. The
1789 startup code will be much like this:
1790
1791 ::
1792
1793    void mystartup(int argc, char **argv)
1794    {
1795      CpthreadModuleInit();
1796      Cpthreads_start_main(mymain, argc, argv);
1797    }
1798
1799    int main(int argc, char **argv)
1800    {
1801      ConverseInit(mystartup, argc, argv, 0, 0);
1802    }
1803
1804 This creates the first POSIX thread on each processor, which runs the
1805 function mymain. The mymain function is executing in a POSIX thread, and
1806 it may use any pthread function it wishes.
1807
1808 CpthreadModuleInit
1809 ------------------
1810
1811 On each processor, the function CpthreadModuleInit must be called before
1812 any other pthread function is called. This is shown in the example in
1813 the previous section.
1814
1815 Parallel Arrays of Threads
1816 ==========================
1817
1818 This module is CPath: Converse Parallel Array of Threads. It makes it
1819 simple to create arrays of threads, where the threads are distributed
1820 across the processors. It provides simple operations like sending a
1821 message to a thread, as well as group operations like multicasting to a
1822 row of threads, or reducing over an array of threads.
1823
1824 Creating Arrays of Threads
1825 --------------------------
1826
1827 This module defines a data type CPath, also known as an “array
1828 descriptor”. Arrays are created by the function CPathMakeArray, and
1829 individual threads are created using CPathMakeThread:
1830
1831 ``void CPathMakeArray(CPath *path, int threadfn, int mapfn, ...)``
1832
1833 This
1834 function initiates the creation of an array of threads. It fills in the
1835 array descriptor ``*path``. Each thread in the array starts executing
1836 the function represented by ``threadfn``. The function ``mapfn``
1837 represents a mapping function, controlling the layout of the array. This
1838 parameter must be followed by the dimensions of the array, and then a
1839 zero.
1840
1841 ``void CPathMakeThread(CPath *path, int startfn, int pe)``
1842
1843 This function makes a zero-dimensional array of threads, in other words,
1844 just one thread.
1845
1846 Mapping Functions for Arrays of Threads
1847 ---------------------------------------
1848
1849 One of the parameters to CPathMakeArray is a “mapping function”, which
1850 maps array elements to processors. Mapping functions must be registered.
1851 The integer index returned by the registration process is the number
1852 which is passed to CPathMakeArray. Mapping functions receive the array
1853 descriptor as a parameter, and may use it to determine the dimensions of
1854 the array.
1855
1856 ``unsigned int MapFn(CPath *path, int *indices)``
1857
1858 This is a prototype map
1859 function, all mapping functions must have this parameter list. It
1860 accepts an array descriptor and a set of indices. It returns the
1861 processor number of the specified element.
1862
1863 ``int CPathRegisterMapper(void *mapfn)``
1864
1865 Accepts a pointer to a mapping function, and returns an integer index
1866 for the function. This number can be used as a parameter to
1867 CPathMakeArray.
1868
1869 ``int CPathArrayDimensions(CPath *path)``
1870
1871 Returns the number of dimensions in the specified array.
1872
1873 ``int CPathArrayDimension(CPath *path, int n)``
1874
1875 Returns the nth dimension of the specified array.
1876
1877 Thread Functions for Arrays of Threads
1878 --------------------------------------
1879
1880 Thread functions (the functions that the threads execute) must have the
1881 following prototype, and must be registered using the following
1882 registration function. The integer index returned by the registration
1883 process is the number which is passed to CPathMakeArray.
1884
1885 ``void ThreadFn(CPath *self, int *indices)``
1886
1887 This is a prototype thread
1888 function. All thread-functions must have these parameters. When an array
1889 of threads is created, each thread starts executing the specified thread
1890 function. The function receives a pointer to a copy of the array’s
1891 descriptor, and the array element’s indices.
1892
1893 ``int CPathRegisterThreadFn(void *mapfn)``
1894
1895 Accepts a pointer to a thread function, and returns an integer index for
1896 the function. This number can be used as a parameter to CPathMakeArray.
1897
1898 Sending Messages to Threads
1899 ---------------------------
1900
1901 Threads may send messages to each other using CPathSend, which takes a
1902 complicated set of parameters. The parameters are most easily described
1903 by a context-free grammar:
1904
1905 ``void CPathSend(dest-clause, tag-clause, data-clause, end-clause)``
1906
1907 Where:
1908
1909 ::
1910
1911        dest-clause :== CPATH_DEST ',' pathptr ',' index ',' index ',' ...
1912        tag-clause  :== CPATH_TAG ',' tag
1913        tag-clause  :== CPATH_TAGS ',' tag ',' tag ',' ... ',' 0
1914        tag-clause  :== CPATH_TAGVEC ',' numtags ',' tagvector
1915        data-clause :== CPATH_BYTES ',' numbytes ',' bufptr
1916        end-clause  :== CPATH_END
1917
1918 The symbols ``CPATH_DEST``, ``CPATH_TAG``, ``CPATH_TAGS``,
1919 ``CPATH_TAGVEC``, ``CPATH_BYTES``, ``CPATH_END``, and the comma are
1920 terminal symbols. The symbols descriptor, index, tag, numtags,
1921 tagvector, numbytes, and bufptr all represent C expressions.
1922
1923 The dest-clause specifies which array and which indices the message is
1924 to go to. One must provide a pointer to an array descriptor and a set of
1925 indices. Any index may be either a normal index, or the wildcard
1926 ``CPATH_ALL``. Using the wildcard causes a multicast. The tag-clause
1927 provides several notations, all of which specify an array of one or more
1928 integer tags to be sent with the message. These tags can be used at the
1929 receiving end for pattern matching. The data-clause specifies the data
1930 to go in the message, as a sequence of bytes. The end-clause represents
1931 the end of the parameter list.
1932
1933 Messages sent with CPathSend can be received using CPathRecv, analyzed
1934 using CPathMsgDecodeBytes, and finally discarded with CPathMsgFree:
1935
1936 ``void *CPathRecv(tag-clause, end-clause)``
1937
1938 The tag-clause and end-clause
1939 match the grammar for CPathSend. The function will wait until a message
1940 with the same tags shows up (it waits using the thread-blocking
1941 primitives, see Converse threads). If any position in the CPathRecv
1942 tag-vector is ``CPATH_WILD``, then that one position is ignored.
1943 CPathRecv returns an “opaque CPath message”. The message contains the
1944 data somewhere inside it. The data can be located using
1945 CPathMsgDecodeBytes, below. The opaque CPath message can be freed using
1946 CPathMsgFree below.
1947
1948 ``void CPathMsgDecodeBytes(void *msg, int *len, void *bytes)``
1949
1950 Given an
1951 opaque CPath message (as sent by CPathSend and returned by CPathRecv),
1952 this function will locate the data inside it. The parameter ``*len`` is
1953 filled in with the data length, and ``*bytes`` is filled in with a
1954 pointer to the data bytes. Bear in mind that once you free the opaque
1955 CPath message, this pointer is no longer valid.
1956
1957 ``void CPathMsgFree(void *msg)``
1958
1959 Frees an opaque CPath message.
1960
1961 Performing Reductions over Array Elements
1962 -----------------------------------------
1963
1964 An set of threads may participate in a reduction. All the threads
1965 wishing to participate must call CPathReduce. The parameters to
1966 CPathReduce are most easily described by a context-free grammar:
1967
1968 ``void CPathReduce(over-clause, tag-clause, red-clause, data-clause,
1969 dest-clause, end-clause)``
1970
1971 Where:
1972
1973 ::
1974
1975        over-clause :== CPATH_OVER ',' pathptr ',' index ',' index ',' ...
1976        dest-clause :== CPATH_DEST ',' pathptr ',' index ',' index ',' ...
1977        tag-clause  :== CPATH_TAG ',' tag
1978        tag-clause  :== CPATH_TAGS ',' tag ',' tag ',' ... ',' 0
1979        tag-clause  :== CPATH_TAGVEC ',' numtags ',' tagvector
1980        data-clause :== CPATH_BYTES ',' vecsize ',' eltsize ',' data
1981        red-clause  :== CPATH_REDUCER ',' redfn
1982        end-clause  :== CPATH_END
1983
1984 The over-clause specifies the set of threads participating in the
1985 reduction. One or more of the indices should be ``CPATH_ALL``, the
1986 wildcard value. All array elements matching the pattern are
1987 participating in the reduction. All participants must supply the same
1988 over-clause. The tags-clause specifies a vector of integer tags. All
1989 participants must supply the same tags. The reducer represents the
1990 function used to combine data pairwise. All participants must supply the
1991 same reducer. The data-clause specifies the input-data, which is an
1992 array of arbitrary-sized values. All participants must agree on the
1993 vecsize and eltsize. The dest-clause specifies the recipient of the
1994 reduced data (which may contain ``CPATH_ALL`` again). The data is sent
1995 to the recipient. The results can be received with CPathRecv using the
1996 same tags specified in the CPathReduce. The results may be analyzed with
1997 CPathMsgDecodeReduction, and freed with CPathMsgFree.
1998
1999 ``void CPathMsgDecodeReduction(void *msg, int *vecsize, int *eltsize, void
2000 *bytes)``
2001
2002 This function accepts an opaque CPath message which was created
2003 by a reduction. It locates the data within the message, and determines
2004 the vecsize and eltsize.
2005
2006 The function that combines elements pairwise must match this prototype,
2007 and be registered with the following registration function. It is the
2008 number returned by the registration function which must be passed to
2009 CPathReduce:
2010
2011 ``void ReduceFn(int vecsize, void *data1, void *data2)``
2012
2013 The reduce function accepts two equally-sized arrays of input data. It
2014 combines the two arrays pairwise, storing the results in array 1.
2015
2016 ``int CPathRegisterReducer(void *fn)``
2017
2018 Accepts a pointer to a reduction function, and returns an integer index
2019 for the function. This number can be used as a parameter to CPathReduce.
2020
2021 .. [1]
2022    URL:\ \ ``http://www.ncsa.uiuc.edu/Apps/SPRNG/www/``
2023
2024 .. [2]
2025    Email:\ \ ``ashoks@ncsa.uiuc.edu``