733b27b6c2e83bdbfc85ecb7d470366218c9f80c
[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{Scheduling Messages}
464 \label{schedqueue}
465
466 The scheduler queue is a powerful priority queue.  The following
467 functions can be used to place messages into the scheduler queue.
468 These messages are treated very much like newly-arrived messages: when
469 they reach the front of the queue, they trigger handler functions,
470 just like messages transmitted with CMI functions.  Note that unlike
471 the CMI send functions, these cannot move messages across processors.
472
473 Every message inserted into the queue has a priority associated with
474 it.  \converse{} priorities are arbitrary-precision numbers between 0 and
475 1.  Priorities closer to 0 get processed first, priorities closer to 1
476 get processed last.  Arbitrary-precision priorities are very useful in
477 AI search-tree applications. Suppose we have a heuristic suggesting
478 that tree node N1 should be searched before tree node N2. We therefore
479 designate that node N1 and its descendants will use high priorities,
480 and that node N2 and its descendants will use lower priorities. We
481 have effectively split the range of possible priorities in two. If
482 several such heuristics fire in sequence, we can easily split the
483 priority range in two enough times that no significant bits remain,
484 and the search begins to fail for lack of meaningful priorities to
485 assign. The solution is to use arbitrary-precision priorities, aka
486 bitvector priorities.
487
488 These arbitrary-precision numbers are represented as bit-strings: for
489 example, the bit-string ``0011000101'' represents the binary number
490 (.0011000101).  The format of the bit-string is as follows: the
491 bit-string is represented as an array of unsigned integers. The most
492 significant bit of the first integer contains the first bit of the
493 bitvector.  The remaining bits of the first integer contain the next
494 31 bits of the bitvector.  Subsequent integers contain 32 bits
495 each. If the size of the bitvector is not a multiple of 32, then the
496 last integer contains 0 bits for padding in the least-significant bits
497 of the integer.
498
499 Some people only want regular integers as priorities.  For
500 simplicity's sake, we provide an easy way to convert integer
501 priorities to \converse{}'s built-in representation.
502
503 In addition to priorities, you may choose to enqueue a message
504 ``LIFO'' or ``FIFO''.  Enqueueing a message ``FIFO'' simply pushes it
505 behind all the other messages of the same priority.  Enqueueing a
506 message ``LIFO'' pushes it in front of other messages of the same
507 priority.
508
509 Messages sent using the CMI functions take precedence over everything
510 in the scheduler queue, regardless of priority.
511
512 A recent addition\experimental{} to \converse{} scheduling mechanisms is 
513 the introduction of
514 node-level scheduling designed to support low-overhead programming for the
515 SMP clusters. These functions have ``Node'' in their names. All processors
516 within the node has access to the node-level scheduler's queue, and thus
517 a message enqueued in a node-level queue may be handled by any processor within
518 that node. When deciding about which message to process next, i.e. from
519 processor's own queue or from the node-level queue, a quick priority check
520 is performed internally, thus a processor views scheduler's queue as a single
521 prioritized queue that includes messages directed at that processor and
522 messages from the node-level queue sorted according to priorities.
523
524 \function{void CsdEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)}
525 \index{CsdEnqueueGeneral}
526 \desc{This call enqueues a message to the processor's scheduler's queue, to
527 be sorted according to its priority and the queueing \param{strategy}.
528 The meaning of the \uw{priobits} and \uw{prioptr} fields depend
529 on the value of \uw{strategy}, which are explained below.}
530
531 \function{void CsdNodeEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)}
532 \index{CsdNodeEnqueueGeneral}
533 \desc{This call enqueues a message to the node-level scheduler's queue, to
534 be sorted according to its priority and the queueing \uw{strategy}.
535 The meaning of the \uw{priobits} and \uw{prioptr} fields depend
536 on the value of \uw{strategy}, which can be any of the following:
537
538 \begin{itemize}
539 \item{\kw{CQS\_QUEUEING\_BFIFO}: the priobits and prioptr point to
540 a bit-string representing an arbitrary-precision priority.  The message
541 is pushed behind all other message of this priority.}
542
543 \item{\kw{CQS\_QUEUEING\_BLIFO}: the priobits and prioptr point to
544 a bit-string representing an arbitrary-precision priority.  The message
545 is pushed in front all other message of this priority.}
546
547 \item{\kw{CQS\_QUEUEING\_IFIFO}: the prioptr is a pointer to a
548 signed integer.  The integer is converted to a bit-string priority,
549 normalizing so that the integer zero is converted to the bit-string
550 ``1000...'' (the ``middle'' priority).  To be more specific, the
551 conversion is performed by adding 0x80000000 to the integer, and then
552 treating the resulting 32-bit quantity as a 32-bit bitvector priority.
553 The message is pushed behind all other messages of this priority.}
554
555 \item{\kw{CQS\_QUEUEING\_ILIFO}: the prioptr is a pointer to a
556 signed integer.  The integer is converted to a bit-string priority,
557 normalizing so that the integer zero is converted to the bit-string
558 ``1000...'' (the ``middle'' priority).  To be more specific, the
559 conversion is performed by adding 0x80000000 to the integer, and then
560 treating the resulting 32-bit quantity as a 32-bit bitvector priority.
561 The message is pushed in front of all other messages of this
562 priority.}
563
564 \item{\kw{CQS\_QUEUEING\_FIFO}: the prioptr and priobits are ignored.
565 The message is enqueued with the middle priority ``1000...'', and is
566 pushed behind all other messages with this priority.}
567
568 \item{\kw{CQS\_QUEUEING\_LIFO}: the prioptr and priobits are ignored.
569 The message is enqueued with the middle priority ``1000...'', and is
570 pushed in front of all other messages with this priority.}
571
572 \end{itemize}
573
574 Caution: the priority itself is {\em not copied} by the scheduler.
575 Therefore, if you pass a pointer to a priority into the scheduler, you
576 must not overwrite or free that priority until after the message has
577 emerged from the scheduler's queue.  It is normal to actually store
578 the priority {\em in the message itself}, though it is up to the user
579 to actually arrange storage for the priority.
580 }
581
582 \function {void CsdEnqueue(void *Message)}
583 \index{CsdEnqueue}
584 \desc{This macro is a shorthand for 
585 \begin{alltt}
586 CsdEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL) 
587 \end{alltt}
588 provided here for backward compatibility.}
589
590 \function {void CsdNodeEnqueue(void *Message)}
591 \index{CsdNodeEnqueue}
592 \desc{This macro is a shorthand for 
593 \begin{alltt}
594 CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL) 
595 \end{alltt}
596 provided here for backward compatibility.}
597
598 \function{void CsdEnqueueFifo(void *Message)}
599 \index{CsdEnqueueFifo}
600 \desc{This macro is a shorthand for 
601 \begin{alltt}
602 CsdEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL)
603 \end{alltt}
604 provided here for backward compatibility.}
605
606 \function{void CsdNodeEnqueueFifo(void *Message)}
607 \index{CsdNodeEnqueueFifo}
608 \desc{This macro is a shorthand for 
609 \begin{alltt}
610 CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL)
611 \end{alltt}
612 provided here for backward compatibility.}
613
614 \function{void CsdEnqueueLifo(void *Message)}
615 \index{CsdEnqueueLifo}
616 \desc{This macro is a shorthand for
617 \begin{alltt}
618 CsdEnqueueGeneral(Message, CQS\_QUEUEING\_LIFO,0, NULL)
619 \end{alltt}
620 provided here for backward compatibility.}
621
622 \function{void CsdNodeEnqueueLifo(void *Message)}
623 \index{CsdNodeEnqueueLifo}
624 \desc{This macro is a shorthand for
625 \begin{alltt}
626 CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_LIFO,0, NULL) 
627 \end{alltt}
628 provided here for backward compatibility.}
629
630 \function{int CsdEmpty()}
631 \index{CsdEmpty}
632 \desc{This function returns non-zero integer when the scheduler's 
633 processor-level queue is empty, zero otherwise.}
634
635 \function{int CsdNodeEmpty()}
636 \index{CsdNodeEmpty}
637 \desc{This function returns non-zero integer when the scheduler's 
638 node-level queue is empty, zero otherwise.}
639
640 \section{Polling for Messages}
641 \label{polling}
642
643 As we stated earlier, \converse{} messages trigger handler functions when
644 they arrive.  In fact, for this to work, the processor must
645 occasionally poll for messages.  When the user starts \converse{}, he can
646 put it into one of several modes.  In the normal mode, the message
647 polling happens automatically.  However {\em user-calls-scheduler}
648 mode is designed to let the user poll manually.  To do this, the user
649 must use one of two polling functions: \kw{CmiDeliverMsgs}, or
650 \kw{CsdScheduler}.  \kw{CsdScheduler} is more general, it will notice any
651 \converse{} event.  \kw{CmiDeliverMsgs} is a lower-level function that ignores
652 all events except for recently-arrived messages.  (In particular, it
653 ignores messages in the scheduler queue).  You can save a tiny amount
654 of overhead by using the lower-level function.  We recommend the use
655 of \kw{CsdScheduler} for all applications except those that are using only
656 the lowest level of \converse{}, the CMI.  A third polling function,
657 \kw{CmiDeliverSpecificMsg}, is used when you know the exact event you want
658 to wait for: it does not allow any other event to occur.
659
660 In each iteration, a scheduler first looks for any message that 
661 has arrived from another processor, and delivers it.
662 If there isn't any, it selects a message from the locally enqueued
663 messages, and delivers it. 
664
665 \function {void CsdScheduleForever(void)} \index{CsdScheduleForever}
666 \desc{Extract and deliver messages until the scheduler is stopped.
667 Raises the idle handling converse signals.  This is the scheduler to
668 use in most \converse{} programs.}
669
670 \function {int CsdScheduleCount(int n)} \index{CsdScheduleCount}
671 \desc{Extract and deliver messages until $n$ messages
672 have been delivered, then return 0. If the scheduler is stopped
673 early, return $n$ minus the number of messages delivered so far.
674 Raises the idle handling converse signals.}
675
676 \function {void CsdSchedulePoll(void)} \index{CsdSchedulePoll}
677 \desc{Extract and deliver messages until no more messages
678 are available, then return.  This is useful for running
679 non-networking code when the networking code has nothing to do.}
680
681 \function {void CsdScheduler(int n)}
682 \index{CsdScheduler}
683 \desc{If $n$ is zero, call CsdSchedulePoll.  If $n$ is negative, call
684 CsdScheduleForever.  If $n$ is positive, call CsdScheduleCount($n$).}
685
686
687 \function{int CmiDeliverMsgs(int MaxMsgs)}
688 \index{CmiDeliverMsgs}
689 \desc{Retrieves messages from the network message queue and invokes 
690 corresponding handler functions for arrived messages. This function 
691 returns after either the network message queue becomes empty or after
692 \uw{MaxMsgs} messages have been retrieved and their handlers called. 
693 It returns the difference between total messages delivered and \uw{MaxMsgs}.
694 The handler is given a pointer to the message as  its parameter.}
695
696 \function{void CmiDeliverSpecificMsg(int HandlerId)}
697 \index{CmiDeliverSpecificMsg}
698 \desc{Retrieves messages from the network queue and delivers the first
699 message with its handler field equal to \uw{HandlerId}. This functions
700 leaves alone all other messages. It returns after the invoked handler
701 function returns.}
702
703 \function {void CsdExitScheduler(void)}
704 \index{CsdExitScheduler}
705 \desc{This call causes CsdScheduler to stop processing messages when
706 control has returned back to it. The scheduler then returns to its
707 calling routine.}
708
709
710 \zap{
711 \section{Global Pointer}
712
713 \function{int CmiGptrCreate(GlobalPtr *gptr, void *lptr, unsigned int size)}
714 \desc{This function creates a global pointer by initializing contents of
715 \param{*gptr} to point to memory on the local processor pointed to by
716 \param{lptr} of \param{size} bytes. \param{*gptr} could then be sent to other 
717 processors, and could be used by \param{CmiGet()} and \param{CmiPut()}
718 to read and write this memory by remote processors. This functions returns
719 a positive integer on success.}
720
721 \function{void *CmiGptrDref(GlobalPtr *gptr)}
722 \desc{This function returns the address of local memory associated
723 with global pointer \param{gptr}.}
724
725 \function{int CmiSyncGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
726 \desc{Copies \param{size} bytes from 
727 memory pointed to by global pointer \param{gptr}
728 to local memory pointed to by \param{lptr}. 
729 This is a synchronous operation and the calling processor blocks until
730 the data is transferred to local memory. This function returns
731 a positive integer on success.}
732
733 \function{CommHandle CmiGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
734 \desc{Initiates copying of \param{size} bytes from 
735 memory pointed to by global pointer \param{gptr}
736 to local memory pointed to by \param{lptr}. 
737 This function returns a  communication handle which could be used
738 to  enquire about the status of this operation.}
739
740 \function{CommHandle CmiPut(GlobalPtr *gptr, void *lptr, unsigned int size)}
741 \desc{Initiates copying of \param{size} bytes from a processor's local
742 memory pointed to by \param{lptr} to the memory pointed to by global
743 pointer \param{gptr}.  This function returns a  communication handle
744 which could be used to  enquire about the status of this operation.}
745 }
746
747 \section{The Timer}
748
749 \function{double CmiTimer(void)}
750 \index{CmiTimer}
751 \desc{Returns current value of the timer in seconds. This is
752 typically the time spent since the \kw{ConverseInit} call.
753 The precision of this timer is the best available on the particular machine,
754 and usually has at least microsecond accuracy.}
755
756 \section{Processor Ids}
757
758 \function{int CmiNumPe(void)}
759 \index{CmiNumPe}
760 \desc{Returns the total number of processors on which the 
761 parallel program is being run.}
762
763 \function{int CmiMyPe(void)}
764 \index{CmiMyPe}
765 \desc{Returns the logical processor identifier of processor on which the 
766 caller resides. A processor Id is between \texttt{0} and 
767 \texttt{\kw{CmiNumPe}()-1}.}
768
769 Also see the calls in Section~\ref{utility}.
770
771 \input{cpvmacros}
772
773 \section{Input/Output}
774
775 \function{void CmiPrintf(char *format, arg1, arg2, ...)}
776 \index{CmiPrintf}
777 \desc{This function does an atomic \texttt{printf()} on \texttt{stdout}. 
778 On machine with host, this is implemented on top of the messaging 
779 layer using asynchronous sends.}
780
781 \function{int CmiScanf(char *format, void *arg1, void *arg2, ...)}
782 \index{CmiScanf}
783 \desc{This function performs an atomic \texttt{scanf} from \texttt{stdin}.
784 The processor, on which the caller resides, blocks for input. On machines with
785 host, this is implemented on top of the messaging layer using asynchronous
786 send and blocking receive.}
787
788 \function{void CmiError(char *format, arg1, arg2, ...)}
789 \index{CmiError}
790 \desc{This function does an atomic \texttt{printf()} on \texttt{stderr}. 
791 On machines with host, this is implemented on top of the messaging 
792 layer using asynchronous sends.}
793
794 \zap{
795 \section{Processor Groups}
796
797 \function{void CmiPgrpCreate(Pgrp *group)}
798 \desc{Creates a processor-group with calling processsor as the root processor.}
799
800 \function{void CmiPgrpDestroy(Pgrp *group)}
801 \desc{Frees resources associated with a processor group \param{group}.}
802
803 \function{void CmiAddChildren(Pgrp *group, int penum, int size, int procs[])}
804 \desc{Adds \param{size} processors from array \param{procs[]} to the
805 processor-group \param{group} as children of processor penum. This function
806 could be called only by the root processor of processor-group \param{group}.}
807
808 \function{CommHandle CmiAsyncMulticast(Pgrp *group, unsigned int size, void *msg)}
809 \desc{Initiates asynchronous broadcast of message \param{msg} of
810 length \param{size} bytes to all processors belonging to \param{group}
811 excluding the processor on which the caller resides. It returns a
812 communication handle which could be used to check the status of this
813 send using \param{CmiAsyncMsgSent()}. If the returned communication handle 
814 is 0, message buffer can be reused immediately, thus saving a call to 
815 CmiAsyncMsgSent. \param{msg} should not be
816 overwritten or freed before the communication is complete. \note{Caller
817 need not belong to \param{group}.}} 
818
819 \function{int CmiPgrpRoot(Pgrp *group)}
820 \desc{Returns the processor id of root of processor-group \param{group}. }
821
822 \function{int CmiNumChildren(Pgrp *group, int penum)}
823 \desc{Returns  number of children of processor \param{penum} 
824 in the processor-group \param{group}.}
825
826 \function{int CmiParent(Pgrp *group, int penum)}
827 \desc{Returns  processor id of parent of processor \param{penum} 
828 in the processor-group \param{group}.}
829
830 \function{void CmiChildren(Pgrp *group, int node, int *children)}
831 \desc{Fills in array \param{children} with processor ids of all the
832 children processor \param{node} in processor-group \param{group}. This
833 array should at least be of size \param{CmiNumChildren()}.}
834 }
835
836 \section{Spanning Tree Calls}
837
838 Sometimes, it is convenient to view the processors/nodes of the machine as a
839 tree.  For this purpose, \converse{} defines a tree over processors/nodes.  We
840 provide functions to obtain the parent and children of each processor/node.  On
841 those machines where the communication topology is relevant, we
842 arrange the tree to optimize communication performance. The root of
843 the spanning tree (processor based or node-based) is always 0, thus
844 the \kw{CmiSpanTreeRoot} call has been eliminated.
845
846 \function{int CmiSpanTreeParent(int procNum)}
847 \index{CmiSpanTreeParent}
848 \desc{This function returns the processor number of the parent of
849 \uw{procNum} in the spanning tree.}
850
851 \function{int CmiNumSpanTreeChildren(int procNum)}
852 \index{CmiNumSpanTreeChildren}
853 \desc{Returns the number of children of \uw{procNum} in the spanning tree.}
854
855 \function{void CmiSpanTreeChildren(int procNum, int *children)}
856 \index{CmiSpanTreeChildren}
857 \desc{This function fills the array \uw{children} with processor
858 numbers of children of \uw{procNum} in the spanning tree.}
859
860 \function{int CmiNodeSpanTreeParent(int nodeNum)}
861 \index{CmiNodeSpanTreeParent}
862 \desc{This function returns the node number of the parent of
863 \uw{nodeNum} in the spanning tree.}
864
865 \function{int CmiNumNodeSpanTreeChildren(int nodeNum)}
866 \index{CmiNumNodeSpanTreeChildren}
867 \desc{Returns the number of children of \uw{nodeNum} in the spanning tree.}
868
869 \function{void CmiNodeSpanTreeChildren(int nodeNum, int *children)}
870 \index{CmiNodeSpanTreeChildren}
871 \desc{This function fills the array \uw{children} with node
872 numbers of children of \uw{nodeNum} in the spanning tree.}
873
874
875
876
877