added new section for converse reductions
[charm.git] / doc / converse / cmi.tex
1 \chapter{Machine Interface and Scheduler}
2
3 This chapter describes two of \converse{}'s modules: the CMI, and the
4 CSD.  Together, they serve to transmit messages and schedule the
5 delivery of messages. First, we describe the machine model assumed by
6 \converse{}.
7
8 \section{Machine Model}
9 \label{model}
10
11 \converse{} treats the parallel machine as a collection of {\em nodes}, where
12 each node is comprised of a number of {\em processors} that share memory 
13 In some cases, the number of processors per node may be exactly one  
14 (e.g. Distributed memory multicomputers such as IBM SP.)  
15 In addition, each of the processors may have multiple {\em threads} running on
16 them which share code and data but have different stacks.
17 Functions and macros are provided for handling shared memory across
18 processors and querying node information. These are discussed in section
19 \ref{globalvars}
20
21 \section{Defining Handler Numbers}
22 \label{handler1}
23
24 When a message arrives at a processor, it triggers the execution of a
25 {\em handler function}, not unlike a UNIX signal handler.  The handler
26 function receives, as an argument, a pointer to the message.
27 The message itself specifies which handler function is to be
28 called when the message arrives.  Messages are contiguous sequences of
29 bytes.  The message has two parts: the header, and the data.  The data
30 may contain anything you like.  The header contains a {\em handler
31 number}, which specifies which handler function is to be executed when
32 the message arrives.  Before you can send a message, you have to
33 define the handler numbers.
34
35 \converse{} maintains a table mapping handler numbers to function
36 pointers.  Each processor has its own copy of the mapping.  There is a
37 caution associated with this approach: it is the user's responsibility
38 to ensure that all processors have identical mappings.  This is easy
39 to do, nonetheless, and the user must be aware that this is (usually)
40 required.
41
42 The following functions are provided to define the handler numbers:
43
44 \function{typedef void (*CmiHandler)(void *)}
45 \index{CmiHandler}
46 \desc{Functions that handle \converse{} messages must be of this type.}
47
48 \function{int CmiRegisterHandler(CmiHandler h)}
49 \index{CmiRegisterHandler}
50 \desc{This represents the standard technique for associating numbers
51 with functions.  To use this technique, the \converse{} user registers
52 each of his functions, one by one, using \kw{CmiRegisterHandler}.  One must
53 register exactly the same functions in exactly the same order on all
54 processors.  The system assigns monotonically increasing numbers to
55 the functions, the same numbers on all processors.  This insures
56 global consistency.  \kw{CmiRegisterHandler} returns the number which was
57 chosen for the function being registered.}
58
59 \function {int CmiRegisterHandlerGlobal(CmiHandler h)}
60 \index{CmiRegisterHandlerLocal}
61 \desc{This represents a second registration technique.   The \converse{}
62 user registers his functions on processor zero, using
63 \kw{CmiRegisterHandlerGlobal}.  The \converse{} user is then responsible for
64 broadcasting those handler numbers to other processors, and installing
65 them using \kw{CmiNumberHandler} below.  The user should take care not to
66 invoke those handlers until they are fully installed.}
67
68 \function {int CmiRegisterHandlerLocal(CmiHandler h)}
69 \index{CmiRegisterHandlerLocal}
70 \desc{This function is used when one wishes to register functions
71 in a manner that is not consistent across processors.  This function
72 chooses a locally-meaningful number for the function, and records it
73 locally.  No attempt is made to ensure consistency across processors.}
74
75 \function {void CmiNumberHandler(int n, CmiHandler h)}
76 \index{CmiNumberHandler}
77 \desc{Forces the system to associate the specified handler number \uw{n}
78 with the specified handler function \uw{h}.  If the function number
79 \uw{n} was previously mapped to some other function, that old mapping
80 is forgotten.  The mapping that this function creates is local to the
81 current processor.  \kw{CmiNumberHandler} can be useful in combination with
82 \kw{CmiRegisterGlobalHandler}.  It can also be used to implement
83 user-defined numbering schemes: such schemes should keep in mind that
84 the size of the table that holds the mapping is proportional to the
85 largest handler number --- do not use big numbers!}
86
87 \note{Of the three registration methods, the \kw{CmiRegisterHandler} method
88 is by far the simplest, and is strongly encouraged.  The others are
89 primarily to ease the porting of systems that already use similar
90 registration techniques.  One may use all three registration methods
91 in a program.  The system guarantees that no numbering conflicts will
92 occur as a result of this combination.}
93
94 \section{Writing Handler Functions}
95 \label{handler2}
96
97 A message handler function is just a C function that accepts a void
98 pointer (to a message buffer) as an argument, and returns nothing.  The
99 handler may use the message buffer for any purpose, but is responsible
100 for eventually deleting the message using CmiFree.
101
102 \section{Building Messages}
103
104 To send a message, one first creates a buffer to hold the message.
105 The buffer must be large enough to hold the header and the data.
106 The buffer can be in any kind of memory: it could be a local variable,
107 it could be a global, it could be allocated with {\tt malloc}, and
108 finally, it could be allocated with \kw{CmiAlloc}.  The \converse{} user
109 fills the buffer with the message data.  One puts a handler number
110 in the message, thereby specifying which handler function the message
111 should trigger when it arrives.  Finally, one uses a message-transmission
112 function to send the message.
113
114 The following functions are provided to help build message buffers:
115
116 \function{void *CmiAlloc(int size)}
117 \index{CmiAlloc}
118 \desc{Allocates memory of size \uw{size} in heap and returns pointer to 
119 the usable space.  There are some message-sending functions that
120 accept only message buffers that were allocated with \kw{CmiAlloc}.  Thus,
121 this is the preferred way to allocate message buffers. The returned pointer
122 point to the message header, the user data will follow it. See
123 \kw{CmiMsgHeaderSizeBytes} for this.}
124
125 \function{void CmiFree(void *ptr)}
126 \index{CmiFree}
127 \desc{This function frees the memory pointed to by \uw{ptr}. \uw{ptr}
128 should be a pointer that was previously returned by \kw{CmiAlloc}.}
129
130 \function {\#define CmiMsgHeaderSizeBytes}
131 \index{CmiMsgHeaderSizeBytes}
132 \desc{This constant contains the size of the message header.  When one
133 allocates a message buffer, one must set aside enough space for the header
134 and the data.  This macro helps you to do so. For example, if one want to
135 allocate an array of 100 int, he should call the function this way:
136 \tt{``char *myMsg = CmiAlloc(100*sizeof(int) + CmiMsgHeaderSizeBytes)''}}
137
138 \function {void CmiSetHandler(int *MessageBuffer, int HandlerId)}
139 \index{CmiSetHandler}
140 \desc{This macro sets the handler number of a message to \uw{HandlerId}.}
141
142 \function {int CmiGetHandler(int *MessageBuffer)}
143 \index{CmiGetHandler}
144 \desc{This call returns the handler of a message in the form of a
145 handler number.}
146  
147 \function {CmiHandler CmiGetHandlerFunction(int *MessageBuffer)}
148 \index{CmiGetHandlerFunction}
149 \desc{This call returns the handler of a message in the form of a
150 function pointer.}
151
152 \section{Sending Messages}
153
154 The following functions allow you to send messages.  Our model is that
155 the data starts out in the message buffer, and from there gets
156 transferred ``into the network''.  The data stays ``in the network''
157 for a while, and eventually appears on the target processor.  Using
158 that model, each of these send-functions is a device that transfers
159 data into the network.  None of these functions wait for the data to
160 be delivered.
161
162 On some machines, the network accepts data rather slowly.  We don't
163 want the process to sit idle, waiting for the network to accept the
164 data.  So, we provide several variations on each send function:
165
166 \begin{itemize}
167
168 \item{{\bf sync}: a version that is as simple as possible, pushing the
169 data into the network and not returning until the data is ``in the
170 network''.  As soon as a sync function returns, you can reuse the
171 message buffer.}
172
173 \item{{\bf async}: a version that returns almost instantaneously, and then
174 continues working in the background.  The background job transfers the
175 data from the message buffer into the network.  Since the background job
176 is still using the message buffer when the function returns, you can't
177 reuse the message buffer immediately.  The background job sets a flag
178 when it is done and you can then reuse the message buffer.}
179
180 \item{{\bf send and free}: a version that returns almost instantaneously,
181 and then continues working in the background.  The background job
182 transfers the data from the message buffer into the network.  When the
183 background job finishes, it \kw{CmiFree}s the message buffer.  In
184 this situation, you can't reuse the message buffer at all. 
185 To use a function of this type, you must allocate the message buffer
186 using \kw{CmiAlloc}.}
187
188 \item{{\bf node}\experimental{}: a version that send a message to a node 
189 instead of a
190 specific processor. This means that when the message is received, any ``free''
191 processor within than node can handle it.}
192
193 \end{itemize}
194
195 \function{void CmiSyncSend(unsigned int destPE, unsigned int size, void *msg)}
196 \index{CmiSyncSend}
197 \desc{Sends \uw{msg} of size \uw{size} bytes to processor
198 \uw{destPE}.  When it returns, you may reuse the message buffer.}
199
200 \function{void CmiSyncNodeSend(unsigned int destNode, unsigned int size, void *msg)}
201 \index{CmiSyncNodeSend}
202 \desc{Sends\experimental{} \uw{msg} of size \uw{size} bytes to node
203 \uw{destNode}.  When it returns, you may reuse the message buffer.}
204
205 \function{void CmiSyncSendAndFree(unsigned int destPE, unsigned int size, void *msg)}
206 \index{CmiSyncSendAndFree}
207 \desc{Sends \uw{msg} of size \uw{size} bytes to processor
208 \uw{destPE}.  When it returns, the message buffer has been freed
209 using \kw{CmiFree}.}
210
211 \function{void CmiSyncNodeSendAndFree(unsigned int destNode, unsigned int size, void *msg)}
212 \index{CmiSyncNodeSendAndFree}
213 \desc{Sends\experimental{} \uw{msg} of size \uw{size} bytes to node
214 \uw{destNode}.  When it returns, the message buffer has been freed
215 using \kw{CmiFree}.}
216
217 \function{CmiCommHandle CmiAsyncSend(unsigned int destPE, unsigned int size, void *msg)}
218 \index{CmiAsyncSend}
219 \desc{Sends \uw{msg} of size \uw{size} bytes to processor
220 \uw{destPE}.  It returns a communication handle which can be
221 tested using \kw{CmiAsyncMsgSent}: when this returns true, you may reuse
222 the message buffer. If the returned communication handle is 0, message buffer
223 can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}.}
224
225 \function{CmiCommHandle CmiAsyncNodeSend(unsigned int destNode, unsigned int size, void *msg)}
226 \index{CmiAsyncNodeSend}
227 \desc{Sends\experimental{} \uw{msg} of size \uw{size} bytes to node
228 \uw{destNode}.  It returns a communication handle which can be
229 tested using \kw{CmiAsyncMsgSent}: when this returns true, you may reuse
230 the message buffer. If the returned communication handle is 0, message buffer
231 can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}.}
232
233 \function{void CmiSyncVectorSend(int destPE, int len, int sizes[], char *msgComps[])}
234 \desc{Concatenates several pieces of data and sends them to processor
235 \uw{destPE}.  The data consists of \uw{len} pieces residing in
236 different areas of memory, which are logically concatenated.  The
237 \uw{msgComps} array contains pointers to the pieces; the size of
238 \uw{msgComps[i]} is taken from \uw{sizes[i]}. 
239 When it returns, \uw{sizes}, \uw{msgComps} and the message
240 components specified in \uw{msgComps} can be immediately reused.}
241
242 \function{void CmiSyncVectorSendAndFree(int destPE, int len, int sizes[], char *msgComps[])}
243 \desc{Concatenates several pieces of data and sends them to processor
244 \uw{destPE}.  The data consists of \uw{len} pieces residing in
245 different areas of memory, which are logically concatenated.  The
246 \uw{msgComps} array contains pointers to the pieces; the size of
247 \uw{msgComps[i]} is taken from \uw{sizes[i]}. 
248 The message components specified in \uw{msgComps} are \kw{CmiFree}d 
249 by this function therefore, they should be dynamically
250 allocated using \kw{CmiAlloc}.  However, the \uw{sizes} and
251 \uw{msgComps} array themselves are not freed.}
252
253 \function{CmiCommHandle CmiAsyncVectorSend(int destPE, int len, int sizes[], char *msgComps[])}
254 \desc{Concatenates several pieces of data and sends them to processor
255 \uw{destPE}.  The data consists of \uw{len} pieces residing in
256 different areas of memory, which are logically concatenated.  The
257 \uw{msgComps} array contains pointers to the pieces; the size of
258 \uw{msgComps[i]} is taken from \uw{sizes[i]}. 
259 The individual pieces of data as well as the arrays \uw{sizes} and
260 \uw{msgComps} should not be overwritten or freed before the
261 communication is complete.  This function returns a communication
262 handle which can be tested using \kw{CmiAsyncMsgSent}: when this returns
263 true, the input parameters can be reused. If the returned communication 
264 handle is 0, message buffer
265 can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}.}
266
267 \function{int CmiAsyncMsgSent(CmiCommHandle handle)}
268 \index{CmiAsyncMsgSent}
269 \desc{Returns true if the communication specified by the given
270 \kw{CmiCommHandle} has proceeded to the point where the message buffer can
271 be reused.}
272
273 \function{void CmiReleaseCommHandle(CmiCommHandle handle)}
274 \index{CmiReleaseCommHandle}
275 \desc{Releases the communication handle \uw{handle} and
276 associated resources. It does not free the message buffer.}
277
278 \function{void CmiMultipleSend(unsigned int destPE, int len, int sizes[], char
279 *msgComps[])}
280 \index{CmiMultipleSend}
281 \desc{This function\experimental{} allows the user to send 
282 multiple messages that may be
283 destined for the SAME PE in one go. This is more efficient than sending
284 each message to the destination node separately. This function assumes
285 that the handlers that are to receive this message have already been set.
286 If this is not done, the behavior of the function is undefined.
287
288 In the function, The \uw{destPE} parameter identifies the destination
289 processor.
290 The \uw{len} argument identifies the {\it number} of messages that are to
291 be sent in one go. 
292 The \uw{sizes[]} array is an array of sizes of each of these messages.
293 The \uw{msgComps[]} array is the array of the messages. 
294 The indexing in each array is from 0 to len - 1.
295 \note{
296 Before calling this function, the program needs to initialise the system
297 to be able to provide this service. This is done by calling the function
298 \kw{CmiInitMultipleSendRoutine}. Unless this function is
299 called, the system will not be able to provide the service to the user.}
300 }
301
302 \section{Broadcasting Messages}
303
304 \function{void CmiSyncBroadcast(unsigned int size, void *msg)}
305 \index{CmiSyncBroadcast}
306 \desc{Sends \uw{msg} of length \uw{size} bytes to all processors
307 excluding the processor on which the caller resides. }
308
309 \function{void CmiSyncNodeBroadcast(unsigned int size, void *msg)}
310 \index{CmiSyncNodeBroadcast}
311 \desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
312 excluding the node on which the caller resides. }
313
314 \function{void CmiSyncBroadcastAndFree(unsigned int size, void *msg)}
315 \index{CmiSyncBroadcastAndFree}
316 \desc{Sends \uw{msg} of length \uw{size} bytes to all processors
317 excluding the processor on which the caller resides.  Uses \kw{CmiFree} to 
318 deallocate the message buffer for \uw{msg} when the
319 broadcast completes. Therefore \uw{msg} must point to a buffer
320 allocated with \kw{CmiAlloc}.}
321
322 \function{void CmiSyncNodeBroadcastAndFree(unsigned int size, void *msg)}
323 \index{CmiSyncNodeBroadcastAndFree}
324 \desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
325 excluding the node on which the caller resides.  Uses \kw{CmiFree} to 
326 deallocate the message buffer for \uw{msg} when the
327 broadcast completes. Therefore \uw{msg} must point to a buffer
328 allocated with \kw{CmiAlloc}.}
329
330 \function{void CmiSyncBroadcastAll(unsigned int size, void *msg)}
331 \index{CmiSyncBroadcastAll}
332 \desc{Sends \uw{msg} of length \uw{size} bytes to all processors
333 including the processor on which the caller resides. This function
334 does not free the message buffer for \uw{msg}.}
335
336 \function{void CmiSyncNodeBroadcastAll(unsigned int size, void *msg)}
337 \index{CmiSyncNodeBroadcastAll}
338 \desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
339 including the node on which the caller resides. This function
340 does not free the message buffer for \uw{msg}.}
341
342 \function{void CmiSyncBroadcastAllAndFree(unsigned int size, void *msg)}
343 \index{CmiSyncBroadcastAllAndFree}
344 \desc{Sends \uw{msg} of length \uw{size} bytes to all processors
345 including the processor on which the caller resides. This function
346 frees the message buffer for \uw{msg} before returning, so
347 \uw{msg} must point to a dynamically allocated buffer.}
348
349 \function{void CmiSyncNodeBroadcastAllAndFree(unsigned int size, void *msg)}
350 \index{CmiSyncNodeBroadcastAllAndFree}
351 \desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
352 including the node on which the caller resides. This function
353 frees the message buffer for \uw{msg} before returning, so
354 \uw{msg} must point to a dynamically allocated buffer.}
355
356 \function{CmiCommHandle CmiAsyncBroadcast(unsigned int size, void *msg)}
357 \index{CmiAsyncBroadcast}
358 \desc{Initiates asynchronous broadcast of message \uw{msg} of
359 length \uw{size} bytes to all processors excluding the processor on
360 which the caller resides. It returns a communication handle which
361 could be used to check the status of this send using
362 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
363 message buffer can be reused immediately, thus saving a call to 
364 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
365 freed before the communication is complete.}
366
367 \function{CmiCommHandle CmiAsyncNodeBroadcast(unsigned int size, void *msg)}
368 \index{CmiAsyncNodeBroadcast}
369 \desc{Initiates asynchronous broadcast of message \uw{msg} of
370 length \uw{size} bytes to all nodes excluding the node on
371 which the caller resides. It returns a communication handle which
372 could be used to check the status of this send using
373 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
374 message buffer can be reused immediately, thus saving a call to 
375 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
376 freed before the communication is complete.}
377
378 \function{CmiCommHandle CmiAsyncBroadcastAll(unsigned int size, void *msg)}
379 \index{CmiAsyncBroadcastAll}
380 \desc{Initiates asynchronous broadcast of message \uw{msg} of
381 length \uw{size} bytes to all processors including the processor on
382 which the caller resides. It returns a communication handle which
383 could be used to check the status of this send using
384 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
385 message buffer can be reused immediately, thus saving a call to 
386 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
387 freed before the communication is complete.}
388
389 \function{CmiCommHandle CmiAsyncNodeBroadcastAll(unsigned int size, void *msg)}
390 \index{CmiAsyncNodeBroadcastAll}
391 \desc{Initiates asynchronous broadcast of message \uw{msg} of
392 length \uw{size} bytes to all nodes including the node on
393 which the caller resides. It returns a communication handle which
394 could be used to check the status of this send using
395 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
396 message buffer can be reused immediately, thus saving a call to 
397 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
398 freed before the communication is complete.}
399
400 \section{Multicasting Messages}
401
402 \function{typedef ... CmiGroup;}
403 \index{CmiGroup}
404 \desc{A \kw{CmiGroup} represents a set of processors.  It is an opaque type.
405 Group IDs are useful for the multicast functions below.}
406
407 \function{CmiGroup CmiEstablishGroup(int npes, int *pes);}
408 \index{CmiGroup}
409 \index{CmiEstablishGroup}
410 \desc{Converts an array of processor numbers into a group ID.  Group
411 IDs are useful for the multicast functions below.  Caution: this call
412 uses up some resources.  In particular, establishing a group uses 
413 some network bandwidth (one broadcast's worth) and a small amount of
414 memory on all processors.}
415
416 \function{void CmiSyncMulticast(CmiGroup grp, unsigned int size, void *msg)}
417 \index{CmiSyncMulticast}
418 \desc{Sends \uw{msg} of length \uw{size} bytes to all members
419 of the specified group.  Group IDs are created using
420 \kw{CmiEstablishGroup}.}
421
422 \function{void CmiSyncMulticastAndFree(CmiGroup grp, unsigned int size, void *msg)}
423 \index{CmiSyncMulticastAndFree}
424 \desc{Sends \uw{msg} of length \uw{size} bytes to all members
425 of the specified group.  Uses \kw{CmiFree} to deallocate the
426 message buffer for \uw{msg} when the broadcast completes. Therefore
427 \uw{msg} must point to a buffer allocated with \kw{CmiAlloc}.
428 Group IDs are created using \kw{CmiEstablishGroup}.}
429
430 \function{CmiCommHandle CmiAsyncMulticast(CmiGroup grp, unsigned int size, void *msg)}
431 \index{CmiAsyncMulticast}
432 \desc{\note{Not yet implemented.} Initiates asynchronous broadcast of
433 message \uw{msg} of length \uw{size} bytes to all members of
434 the specified group.  It returns a communication handle which could
435 be used to check the status of this send using
436 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
437 message buffer can be reused immediately, thus saving a call to 
438 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
439 freed before the communication is complete.
440 Group IDs are created using \kw{CmiEstablishGroup}.}
441
442 \function{void CmiSyncListSend(int npes, int *pes, unsigned int size, void *msg)}
443 \index{CmiSyncListSend}
444 \desc{Sends \uw{msg} of length \uw{size} bytes to \uw{npes} processors in the
445 array \uw{pes}.}
446
447 \function{void CmiSyncListSendAndFree(int npes, int *pes, unsigned int size, void *msg)}
448 \index{CmiSyncListSendAndFree}
449 \desc{Sends \uw{msg} of length \uw{size} bytes to \uw{npes} processors in the
450 array \uw{pes}. Uses \kw{CmiFree} to deallocate the message buffer for \uw{msg}
451 when the multicast completes. Therefore, \uw{msg} must point to a buffer
452 allocated with \kw{CmiAlloc}.}
453
454 \function{CmiCommHandle CmiAsyncListSend(int npes, int *pes, unsigned int size, void *msg)}
455 \index{CmiAsyncListSend}
456 \desc{Initiates asynchronous multicast of message \uw{msg} of length \uw{size}
457 bytes to \uw{npes} processors in the array \uw{pes}. It returns a communication
458 handle which could be used to check the status of this send using
459 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, message buffer
460 can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}. \uw{msg}
461 should not be overwritten or freed before the communication is complete.}
462
463 \section{Reducing Messaging}
464 \label{reduce}
465
466 Reductions currently are implemented only over the entire set of processors. 
467 Therefore, one call to one of the forms below must be invoked exacly once from
468 each processor. For the ``node'' forms, each node must invoke it once, and in
469 particular on its rank zero. The handler function of every reduction is always
470 called on processor zero.
471
472 \function{void CmiReduce(void *msg, int size, void * (*mergeFn)(void*,void**,int));}
473 \index{CmiReduce}
474 \desc{Contribute a message \uw{msg} of size \uw{size} previously allocated with
475 CmiAlloc. The message will be deallocated by the system by calling CmiFree.
476 The destination handler will be taken by the converse header of the message itself.
477 The last parameter is a function pointer to a merge function (described below).}
478
479 \function{void CmiReduceStruct((void *data, void (*pupFn)(void*,void*),
480                      void * (*mergeFn)(void*,void**,int), CmiHandler dest,
481                      void (*deleteFn)(void*));}
482 \index{CmiReduceStruct}
483 \desc{Contribute a data structure \uw{data} which is allocated on the heap, possibly
484 in a distributed form (like a linked-list or a tree). On processor zero, the
485 function specified by \uw{dest} will be invoked with the data structure resulting
486 from the reduction (the pointer returned by the last merge function). This handler
487 does not need to be registered as a converse handler. The other parameters are
488 function pointers whose purpose is described below.}
489
490 \function{void CmiNodeReduce(void *msg, int size, void * (*mergeFn)(void*,void**,int));}
491 \index{CmiNodeReduce}
492 \desc{Similar to CmiReduce, only that the contribution is at the node level instead
493 of the processor level.}
494
495 \function{void CmiNodeReduceStruct((void *data, void (*pupFn)(void*,void*),
496                      void * (*mergeFn)(void*,void**,int), CmiHandler dest,
497                      void (*deleteFn)(void*));}
498 \index{CmiNodeReduceStruct}
499 \desc{Similar to CmiNodeReduce, only that the contribution is at the node level instead
500 of the processor level.}
501
502 Other than the fuction pointer \uw{dest} used to invoke the final handler on
503 processor zero, there are several other function pointers passed in by the user:
504
505 \function{void * (*mergeFn)(void *local, void **remore, int count)}
506 \desc{This function is used in all the CmiReduce forms to merge the local
507 message/data structure deposited on a processor with all the messages incoming
508 from the children processors of the reduction spanning tree. The input parameters
509 are in the order: the local data (the exact same pointer passed in as first
510 parameter of CmiReduce and similar); a pointer to an array of incoming messages;
511 the number of elements in the second parameter. The function returns a pointer
512 to a freshly allocated message (or data structure for the \kw{Struct} forms)
513 corresponding to the merge of all the messages. All the messages in the
514 \uw{remote} array are deleted by the system; the data pointed by the first parameter
515 should be deleted by this function. If the data can be merged ``in-place'' by
516 modifying or augmenting \uw{local}, the function can return the same pointer to
517 \uw{local} which can be considered freshly allocated. Each element in \uw{remote}
518 is the complete incoming message (including the converse header) for message
519 reductions, and the data as it has been packed by the pup function (without any
520 additional header) for struct reductions.}
521
522 \function{void (*pupFn)(pup\_er p, void *data)}
523 \desc{This function will use the PUP framework to pup the \uw{data} passed in
524 into a message for sending across the network. The data can be either the same
525 data passed in as first parameter of CmiReduceStruct of CmiNodeReduceStruct, or
526 the return of the merge function. It will be called for sizing and packing.
527 \note{It will not be called for unpacking.}}
528
529 \function{void (*deleteFn)(void *ptr)}
530 \desc{This function is used to delete either the data stucture passed in as first
531 parameter of CmiReduceStruct and CmiNodeReduceStruct, or the return of the merge
532 function. It can be as simple as ``free'' or as complicated as needed to delete
533 complex structures. If this function is NULL, the data structure will not be
534 deleted, and the program can continue to use it. Note: even if this function is
535 NULL, the input data structure can still be modified by the merge function.}
536
537
538 \section{Scheduling Messages}
539 \label{schedqueue}
540
541 The scheduler queue is a powerful priority queue.  The following
542 functions can be used to place messages into the scheduler queue.
543 These messages are treated very much like newly-arrived messages: when
544 they reach the front of the queue, they trigger handler functions,
545 just like messages transmitted with CMI functions.  Note that unlike
546 the CMI send functions, these cannot move messages across processors.
547
548 Every message inserted into the queue has a priority associated with
549 it.  \converse{} priorities are arbitrary-precision numbers between 0 and
550 1.  Priorities closer to 0 get processed first, priorities closer to 1
551 get processed last.  Arbitrary-precision priorities are very useful in
552 AI search-tree applications. Suppose we have a heuristic suggesting
553 that tree node N1 should be searched before tree node N2. We therefore
554 designate that node N1 and its descendants will use high priorities,
555 and that node N2 and its descendants will use lower priorities. We
556 have effectively split the range of possible priorities in two. If
557 several such heuristics fire in sequence, we can easily split the
558 priority range in two enough times that no significant bits remain,
559 and the search begins to fail for lack of meaningful priorities to
560 assign. The solution is to use arbitrary-precision priorities, aka
561 bitvector priorities.
562
563 These arbitrary-precision numbers are represented as bit-strings: for
564 example, the bit-string ``0011000101'' represents the binary number
565 (.0011000101).  The format of the bit-string is as follows: the
566 bit-string is represented as an array of unsigned integers. The most
567 significant bit of the first integer contains the first bit of the
568 bitvector.  The remaining bits of the first integer contain the next
569 31 bits of the bitvector.  Subsequent integers contain 32 bits
570 each. If the size of the bitvector is not a multiple of 32, then the
571 last integer contains 0 bits for padding in the least-significant bits
572 of the integer.
573
574 Some people only want regular integers as priorities.  For
575 simplicity's sake, we provide an easy way to convert integer
576 priorities to \converse{}'s built-in representation.
577
578 In addition to priorities, you may choose to enqueue a message
579 ``LIFO'' or ``FIFO''.  Enqueueing a message ``FIFO'' simply pushes it
580 behind all the other messages of the same priority.  Enqueueing a
581 message ``LIFO'' pushes it in front of other messages of the same
582 priority.
583
584 Messages sent using the CMI functions take precedence over everything
585 in the scheduler queue, regardless of priority.
586
587 A recent addition\experimental{} to \converse{} scheduling mechanisms is 
588 the introduction of
589 node-level scheduling designed to support low-overhead programming for the
590 SMP clusters. These functions have ``Node'' in their names. All processors
591 within the node has access to the node-level scheduler's queue, and thus
592 a message enqueued in a node-level queue may be handled by any processor within
593 that node. When deciding about which message to process next, i.e. from
594 processor's own queue or from the node-level queue, a quick priority check
595 is performed internally, thus a processor views scheduler's queue as a single
596 prioritized queue that includes messages directed at that processor and
597 messages from the node-level queue sorted according to priorities.
598
599 \function{void CsdEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)}
600 \index{CsdEnqueueGeneral}
601 \desc{This call enqueues a message to the processor's scheduler's queue, to
602 be sorted according to its priority and the queueing \param{strategy}.
603 The meaning of the \uw{priobits} and \uw{prioptr} fields depend
604 on the value of \uw{strategy}, which are explained below.}
605
606 \function{void CsdNodeEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)}
607 \index{CsdNodeEnqueueGeneral}
608 \desc{This call enqueues a message to the node-level scheduler's queue, to
609 be sorted according to its priority and the queueing \uw{strategy}.
610 The meaning of the \uw{priobits} and \uw{prioptr} fields depend
611 on the value of \uw{strategy}, which can be any of the following:
612
613 \begin{itemize}
614 \item{\kw{CQS\_QUEUEING\_BFIFO}: the priobits and prioptr point to
615 a bit-string representing an arbitrary-precision priority.  The message
616 is pushed behind all other message of this priority.}
617
618 \item{\kw{CQS\_QUEUEING\_BLIFO}: the priobits and prioptr point to
619 a bit-string representing an arbitrary-precision priority.  The message
620 is pushed in front all other message of this priority.}
621
622 \item{\kw{CQS\_QUEUEING\_IFIFO}: the prioptr is a pointer to a
623 signed integer.  The integer is converted to a bit-string priority,
624 normalizing so that the integer zero is converted to the bit-string
625 ``1000...'' (the ``middle'' priority).  To be more specific, the
626 conversion is performed by adding 0x80000000 to the integer, and then
627 treating the resulting 32-bit quantity as a 32-bit bitvector priority.
628 The message is pushed behind all other messages of this priority.}
629
630 \item{\kw{CQS\_QUEUEING\_ILIFO}: the prioptr is a pointer to a
631 signed integer.  The integer is converted to a bit-string priority,
632 normalizing so that the integer zero is converted to the bit-string
633 ``1000...'' (the ``middle'' priority).  To be more specific, the
634 conversion is performed by adding 0x80000000 to the integer, and then
635 treating the resulting 32-bit quantity as a 32-bit bitvector priority.
636 The message is pushed in front of all other messages of this
637 priority.}
638
639 \item{\kw{CQS\_QUEUEING\_FIFO}: the prioptr and priobits are ignored.
640 The message is enqueued with the middle priority ``1000...'', and is
641 pushed behind all other messages with this priority.}
642
643 \item{\kw{CQS\_QUEUEING\_LIFO}: the prioptr and priobits are ignored.
644 The message is enqueued with the middle priority ``1000...'', and is
645 pushed in front of all other messages with this priority.}
646
647 \end{itemize}
648
649 Caution: the priority itself is {\em not copied} by the scheduler.
650 Therefore, if you pass a pointer to a priority into the scheduler, you
651 must not overwrite or free that priority until after the message has
652 emerged from the scheduler's queue.  It is normal to actually store
653 the priority {\em in the message itself}, though it is up to the user
654 to actually arrange storage for the priority.
655 }
656
657 \function {void CsdEnqueue(void *Message)}
658 \index{CsdEnqueue}
659 \desc{This macro is a shorthand for 
660 \begin{alltt}
661 CsdEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL) 
662 \end{alltt}
663 provided here for backward compatibility.}
664
665 \function {void CsdNodeEnqueue(void *Message)}
666 \index{CsdNodeEnqueue}
667 \desc{This macro is a shorthand for 
668 \begin{alltt}
669 CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL) 
670 \end{alltt}
671 provided here for backward compatibility.}
672
673 \function{void CsdEnqueueFifo(void *Message)}
674 \index{CsdEnqueueFifo}
675 \desc{This macro is a shorthand for 
676 \begin{alltt}
677 CsdEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL)
678 \end{alltt}
679 provided here for backward compatibility.}
680
681 \function{void CsdNodeEnqueueFifo(void *Message)}
682 \index{CsdNodeEnqueueFifo}
683 \desc{This macro is a shorthand for 
684 \begin{alltt}
685 CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL)
686 \end{alltt}
687 provided here for backward compatibility.}
688
689 \function{void CsdEnqueueLifo(void *Message)}
690 \index{CsdEnqueueLifo}
691 \desc{This macro is a shorthand for
692 \begin{alltt}
693 CsdEnqueueGeneral(Message, CQS\_QUEUEING\_LIFO,0, NULL)
694 \end{alltt}
695 provided here for backward compatibility.}
696
697 \function{void CsdNodeEnqueueLifo(void *Message)}
698 \index{CsdNodeEnqueueLifo}
699 \desc{This macro is a shorthand for
700 \begin{alltt}
701 CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_LIFO,0, NULL) 
702 \end{alltt}
703 provided here for backward compatibility.}
704
705 \function{int CsdEmpty()}
706 \index{CsdEmpty}
707 \desc{This function returns non-zero integer when the scheduler's 
708 processor-level queue is empty, zero otherwise.}
709
710 \function{int CsdNodeEmpty()}
711 \index{CsdNodeEmpty}
712 \desc{This function returns non-zero integer when the scheduler's 
713 node-level queue is empty, zero otherwise.}
714
715 \section{Polling for Messages}
716 \label{polling}
717
718 As we stated earlier, \converse{} messages trigger handler functions when
719 they arrive.  In fact, for this to work, the processor must
720 occasionally poll for messages.  When the user starts \converse{}, he can
721 put it into one of several modes.  In the normal mode, the message
722 polling happens automatically.  However {\em user-calls-scheduler}
723 mode is designed to let the user poll manually.  To do this, the user
724 must use one of two polling functions: \kw{CmiDeliverMsgs}, or
725 \kw{CsdScheduler}.  \kw{CsdScheduler} is more general, it will notice any
726 \converse{} event.  \kw{CmiDeliverMsgs} is a lower-level function that ignores
727 all events except for recently-arrived messages.  (In particular, it
728 ignores messages in the scheduler queue).  You can save a tiny amount
729 of overhead by using the lower-level function.  We recommend the use
730 of \kw{CsdScheduler} for all applications except those that are using only
731 the lowest level of \converse{}, the CMI.  A third polling function,
732 \kw{CmiDeliverSpecificMsg}, is used when you know the exact event you want
733 to wait for: it does not allow any other event to occur.
734
735 In each iteration, a scheduler first looks for any message that 
736 has arrived from another processor, and delivers it.
737 If there isn't any, it selects a message from the locally enqueued
738 messages, and delivers it. 
739
740 \function {void CsdScheduleForever(void)} \index{CsdScheduleForever}
741 \desc{Extract and deliver messages until the scheduler is stopped.
742 Raises the idle handling converse signals.  This is the scheduler to
743 use in most \converse{} programs.}
744
745 \function {int CsdScheduleCount(int n)} \index{CsdScheduleCount}
746 \desc{Extract and deliver messages until $n$ messages
747 have been delivered, then return 0. If the scheduler is stopped
748 early, return $n$ minus the number of messages delivered so far.
749 Raises the idle handling converse signals.}
750
751 \function {void CsdSchedulePoll(void)} \index{CsdSchedulePoll}
752 \desc{Extract and deliver messages until no more messages
753 are available, then return.  This is useful for running
754 non-networking code when the networking code has nothing to do.}
755
756 \function {void CsdScheduler(int n)}
757 \index{CsdScheduler}
758 \desc{If $n$ is zero, call CsdSchedulePoll.  If $n$ is negative, call
759 CsdScheduleForever.  If $n$ is positive, call CsdScheduleCount($n$).}
760
761
762 \function{int CmiDeliverMsgs(int MaxMsgs)}
763 \index{CmiDeliverMsgs}
764 \desc{Retrieves messages from the network message queue and invokes 
765 corresponding handler functions for arrived messages. This function 
766 returns after either the network message queue becomes empty or after
767 \uw{MaxMsgs} messages have been retrieved and their handlers called. 
768 It returns the difference between total messages delivered and \uw{MaxMsgs}.
769 The handler is given a pointer to the message as  its parameter.}
770
771 \function{void CmiDeliverSpecificMsg(int HandlerId)}
772 \index{CmiDeliverSpecificMsg}
773 \desc{Retrieves messages from the network queue and delivers the first
774 message with its handler field equal to \uw{HandlerId}. This functions
775 leaves alone all other messages. It returns after the invoked handler
776 function returns.}
777
778 \function {void CsdExitScheduler(void)}
779 \index{CsdExitScheduler}
780 \desc{This call causes CsdScheduler to stop processing messages when
781 control has returned back to it. The scheduler then returns to its
782 calling routine.}
783
784
785 \zap{
786 \section{Global Pointer}
787
788 \function{int CmiGptrCreate(GlobalPtr *gptr, void *lptr, unsigned int size)}
789 \desc{This function creates a global pointer by initializing contents of
790 \param{*gptr} to point to memory on the local processor pointed to by
791 \param{lptr} of \param{size} bytes. \param{*gptr} could then be sent to other 
792 processors, and could be used by \param{CmiGet()} and \param{CmiPut()}
793 to read and write this memory by remote processors. This functions returns
794 a positive integer on success.}
795
796 \function{void *CmiGptrDref(GlobalPtr *gptr)}
797 \desc{This function returns the address of local memory associated
798 with global pointer \param{gptr}.}
799
800 \function{int CmiSyncGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
801 \desc{Copies \param{size} bytes from 
802 memory pointed to by global pointer \param{gptr}
803 to local memory pointed to by \param{lptr}. 
804 This is a synchronous operation and the calling processor blocks until
805 the data is transferred to local memory. This function returns
806 a positive integer on success.}
807
808 \function{CommHandle CmiGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
809 \desc{Initiates copying of \param{size} bytes from 
810 memory pointed to by global pointer \param{gptr}
811 to local memory pointed to by \param{lptr}. 
812 This function returns a  communication handle which could be used
813 to  enquire about the status of this operation.}
814
815 \function{CommHandle CmiPut(GlobalPtr *gptr, void *lptr, unsigned int size)}
816 \desc{Initiates copying of \param{size} bytes from a processor's local
817 memory pointed to by \param{lptr} to the memory pointed to by global
818 pointer \param{gptr}.  This function returns a  communication handle
819 which could be used to  enquire about the status of this operation.}
820 }
821
822 \section{The Timer}
823
824 \function{double CmiTimer(void)}
825 \index{CmiTimer}
826 \desc{Returns current value of the timer in seconds. This is
827 typically the time spent since the \kw{ConverseInit} call.
828 The precision of this timer is the best available on the particular machine,
829 and usually has at least microsecond accuracy.}
830
831 \section{Processor Ids}
832
833 \function{int CmiNumPe(void)}
834 \index{CmiNumPe}
835 \desc{Returns the total number of processors on which the 
836 parallel program is being run.}
837
838 \function{int CmiMyPe(void)}
839 \index{CmiMyPe}
840 \desc{Returns the logical processor identifier of processor on which the 
841 caller resides. A processor Id is between \texttt{0} and 
842 \texttt{\kw{CmiNumPe}()-1}.}
843
844 Also see the calls in Section~\ref{utility}.
845
846 \input{cpvmacros}
847
848 \section{Input/Output}
849
850 \function{void CmiPrintf(char *format, arg1, arg2, ...)}
851 \index{CmiPrintf}
852 \desc{This function does an atomic \texttt{printf()} on \texttt{stdout}. 
853 On machine with host, this is implemented on top of the messaging 
854 layer using asynchronous sends.}
855
856 \function{int CmiScanf(char *format, void *arg1, void *arg2, ...)}
857 \index{CmiScanf}
858 \desc{This function performs an atomic \texttt{scanf} from \texttt{stdin}.
859 The processor, on which the caller resides, blocks for input. On machines with
860 host, this is implemented on top of the messaging layer using asynchronous
861 send and blocking receive.}
862
863 \function{void CmiError(char *format, arg1, arg2, ...)}
864 \index{CmiError}
865 \desc{This function does an atomic \texttt{printf()} on \texttt{stderr}. 
866 On machines with host, this is implemented on top of the messaging 
867 layer using asynchronous sends.}
868
869 \zap{
870 \section{Processor Groups}
871
872 \function{void CmiPgrpCreate(Pgrp *group)}
873 \desc{Creates a processor-group with calling processsor as the root processor.}
874
875 \function{void CmiPgrpDestroy(Pgrp *group)}
876 \desc{Frees resources associated with a processor group \param{group}.}
877
878 \function{void CmiAddChildren(Pgrp *group, int penum, int size, int procs[])}
879 \desc{Adds \param{size} processors from array \param{procs[]} to the
880 processor-group \param{group} as children of processor penum. This function
881 could be called only by the root processor of processor-group \param{group}.}
882
883 \function{CommHandle CmiAsyncMulticast(Pgrp *group, unsigned int size, void *msg)}
884 \desc{Initiates asynchronous broadcast of message \param{msg} of
885 length \param{size} bytes to all processors belonging to \param{group}
886 excluding the processor on which the caller resides. It returns a
887 communication handle which could be used to check the status of this
888 send using \param{CmiAsyncMsgSent()}. If the returned communication handle 
889 is 0, message buffer can be reused immediately, thus saving a call to 
890 CmiAsyncMsgSent. \param{msg} should not be
891 overwritten or freed before the communication is complete. \note{Caller
892 need not belong to \param{group}.}} 
893
894 \function{int CmiPgrpRoot(Pgrp *group)}
895 \desc{Returns the processor id of root of processor-group \param{group}. }
896
897 \function{int CmiNumChildren(Pgrp *group, int penum)}
898 \desc{Returns  number of children of processor \param{penum} 
899 in the processor-group \param{group}.}
900
901 \function{int CmiParent(Pgrp *group, int penum)}
902 \desc{Returns  processor id of parent of processor \param{penum} 
903 in the processor-group \param{group}.}
904
905 \function{void CmiChildren(Pgrp *group, int node, int *children)}
906 \desc{Fills in array \param{children} with processor ids of all the
907 children processor \param{node} in processor-group \param{group}. This
908 array should at least be of size \param{CmiNumChildren()}.}
909 }
910
911 \section{Spanning Tree Calls}
912
913 Sometimes, it is convenient to view the processors/nodes of the machine as a
914 tree.  For this purpose, \converse{} defines a tree over processors/nodes.  We
915 provide functions to obtain the parent and children of each processor/node.  On
916 those machines where the communication topology is relevant, we
917 arrange the tree to optimize communication performance. The root of
918 the spanning tree (processor based or node-based) is always 0, thus
919 the \kw{CmiSpanTreeRoot} call has been eliminated.
920
921 \function{int CmiSpanTreeParent(int procNum)}
922 \index{CmiSpanTreeParent}
923 \desc{This function returns the processor number of the parent of
924 \uw{procNum} in the spanning tree.}
925
926 \function{int CmiNumSpanTreeChildren(int procNum)}
927 \index{CmiNumSpanTreeChildren}
928 \desc{Returns the number of children of \uw{procNum} in the spanning tree.}
929
930 \function{void CmiSpanTreeChildren(int procNum, int *children)}
931 \index{CmiSpanTreeChildren}
932 \desc{This function fills the array \uw{children} with processor
933 numbers of children of \uw{procNum} in the spanning tree.}
934
935 \function{int CmiNodeSpanTreeParent(int nodeNum)}
936 \index{CmiNodeSpanTreeParent}
937 \desc{This function returns the node number of the parent of
938 \uw{nodeNum} in the spanning tree.}
939
940 \function{int CmiNumNodeSpanTreeChildren(int nodeNum)}
941 \index{CmiNumNodeSpanTreeChildren}
942 \desc{Returns the number of children of \uw{nodeNum} in the spanning tree.}
943
944 \function{void CmiNodeSpanTreeChildren(int nodeNum, int *children)}
945 \index{CmiNodeSpanTreeChildren}
946 \desc{This function fills the array \uw{children} with node
947 numbers of children of \uw{nodeNum} in the spanning tree.}
948
949
950
951
952