Added new scheduler modes.
[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.}
122
123 \function{void CmiFree(void *ptr)}
124 \index{CmiFree}
125 \desc{This function frees the memory pointed to by \uw{ptr}. \uw{ptr}
126 should be a pointer that was previously returned by \kw{CmiAlloc}.}
127
128 \function {\#define CmiMsgHeaderSizeBytes}
129 \index{CmiMsgHeaderSizeBytes}
130 \desc{This constant contains the size of the message header.  When one
131 allocates a message buffer, one must set aside enough space for the header
132 and the data.  This macro helps you to do so.}
133
134 \function {void CmiSetHandler(int *MessageBuffer, int HandlerId)}
135 \index{CmiSetHandler}
136 \desc{This macro sets the handler number of a message to \uw{HandlerId}.}
137
138 \function {int CmiGetHandler(int *MessageBuffer)}
139 \index{CmiGetHandler}
140 \desc{This call returns the handler of a message in the form of a
141 handler number.}
142  
143 \function {CmiHandler CmiGetHandlerFunction(int *MessageBuffer)}
144 \index{CmiGetHandlerFunction}
145 \desc{This call returns the handler of a message in the form of a
146 function pointer.}
147
148 \section{Sending Messages}
149
150 The following functions allow you to send messages.  Our model is that
151 the data starts out in the message buffer, and from there gets
152 transferred ``into the network''.  The data stays ``in the network''
153 for a while, and eventually appears on the target processor.  Using
154 that model, each of these send-functions is a device that transfers
155 data into the network.  None of these functions wait for the data to
156 be delivered.
157
158 On some machines, the network accepts data rather slowly.  We don't
159 want the process to sit idle, waiting for the network to accept the
160 data.  So, we provide several variations on each send function:
161
162 \begin{itemize}
163
164 \item{{\bf sync}: a version that is as simple as possible, pushing the
165 data into the network and not returning until the data is ``in the
166 network''.  As soon as a sync function returns, you can reuse the
167 message buffer.}
168
169 \item{{\bf async}: a version that returns almost instantaneously, and then
170 continues working in the background.  The background job transfers the
171 data from the message buffer into the network.  Since the background job
172 is still using the message buffer when the function returns, you can't
173 reuse the message buffer immediately.  The background job sets a flag
174 when it is done and you can then reuse the message buffer.}
175
176 \item{{\bf send and free}: a version that returns almost instantaneously,
177 and then continues working in the background.  The background job
178 transfers the data from the message buffer into the network.  When the
179 background job finishes, it \kw{CmiFree}s the message buffer.  In
180 this situation, you can't reuse the message buffer at all. 
181 To use a function of this type, you must allocate the message buffer
182 using \kw{CmiAlloc}.}
183
184 \item{{\bf node}\experimental{}: a version that send a message to a node 
185 instead of a
186 specific processor. This means that when the message is received, any ``free''
187 processor within than node can handle it.}
188
189 \end{itemize}
190
191 \function{void CmiSyncSend(unsigned int destPE, unsigned int size, void *msg)}
192 \index{CmiSyncSend}
193 \desc{Sends \uw{msg} of size \uw{size} bytes to processor
194 \uw{destPE}.  When it returns, you may reuse the message buffer.}
195
196 \function{void CmiSyncNodeSend(unsigned int destNode, unsigned int size, void *msg)}
197 \index{CmiSyncNodeSend}
198 \desc{Sends\experimental{} \uw{msg} of size \uw{size} bytes to node
199 \uw{destNode}.  When it returns, you may reuse the message buffer.}
200
201 \function{void CmiSyncSendAndFree(unsigned int destPE, unsigned int size, void *msg)}
202 \index{CmiSyncSendAndFree}
203 \desc{Sends \uw{msg} of size \uw{size} bytes to processor
204 \uw{destPE}.  When it returns, the message buffer has been freed
205 using \kw{CmiFree}.}
206
207 \function{void CmiSyncNodeSendAndFree(unsigned int destNode, unsigned int size, void *msg)}
208 \index{CmiSyncNodeSendAndFree}
209 \desc{Sends\experimental{} \uw{msg} of size \uw{size} bytes to node
210 \uw{destNode}.  When it returns, the message buffer has been freed
211 using \kw{CmiFree}.}
212
213 \function{CmiCommHandle CmiAsyncSend(unsigned int destPE, unsigned int size, void *msg)}
214 \index{CmiAsyncSend}
215 \desc{Sends \uw{msg} of size \uw{size} bytes to processor
216 \uw{destPE}.  It returns a communication handle which can be
217 tested using \kw{CmiAsyncMsgSent}: when this returns true, you may reuse
218 the message buffer. If the returned communication handle is 0, message buffer
219 can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}.}
220
221 \function{CmiCommHandle CmiAsyncNodeSend(unsigned int destNode, unsigned int size, void *msg)}
222 \index{CmiAsyncNodeSend}
223 \desc{Sends\experimental{} \uw{msg} of size \uw{size} bytes to node
224 \uw{destNode}.  It returns a communication handle which can be
225 tested using \kw{CmiAsyncMsgSent}: when this returns true, you may reuse
226 the message buffer. If the returned communication handle is 0, message buffer
227 can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}.}
228
229 \function{void CmiSyncVectorSend(int destPE, int len, int sizes[], char *msgComps[])}
230 \desc{Concatenates several pieces of data and sends them to processor
231 \uw{destPE}.  The data consists of \uw{len} pieces residing in
232 different areas of memory, which are logically concatenated.  The
233 \uw{msgComps} array contains pointers to the pieces; the size of
234 \uw{msgComps[i]} is taken from \uw{sizes[i]}. 
235 When it returns, \uw{sizes}, \uw{msgComps} and the message
236 components specified in \uw{msgComps} can be immediately reused.}
237
238 \function{void CmiSyncVectorSendAndFree(int destPE, int len, int sizes[], char *msgComps[])}
239 \desc{Concatenates several pieces of data and sends them to processor
240 \uw{destPE}.  The data consists of \uw{len} pieces residing in
241 different areas of memory, which are logically concatenated.  The
242 \uw{msgComps} array contains pointers to the pieces; the size of
243 \uw{msgComps[i]} is taken from \uw{sizes[i]}. 
244 The message components specified in \uw{msgComps} are \kw{CmiFree}d 
245 by this function therefore, they should be dynamically
246 allocated using \kw{CmiAlloc}.  However, the \uw{sizes} and
247 \uw{msgComps} array themselves are not freed.}
248
249 \function{CmiCommHandle CmiAsyncVectorSend(int destPE, int len, int sizes[], char *msgComps[])}
250 \desc{Concatenates several pieces of data and sends them to processor
251 \uw{destPE}.  The data consists of \uw{len} pieces residing in
252 different areas of memory, which are logically concatenated.  The
253 \uw{msgComps} array contains pointers to the pieces; the size of
254 \uw{msgComps[i]} is taken from \uw{sizes[i]}. 
255 The individual pieces of data as well as the arrays \uw{sizes} and
256 \uw{msgComps} should not be overwritten or freed before the
257 communication is complete.  This function returns a communication
258 handle which can be tested using \kw{CmiAsyncMsgSent}: when this returns
259 true, the input parameters can be reused. If the returned communication 
260 handle is 0, message buffer
261 can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}.}
262
263 \function{int CmiAsyncMsgSent(CmiCommHandle handle)}
264 \index{CmiAsyncMsgSent}
265 \desc{Returns true if the communication specified by the given
266 \kw{CmiCommHandle} has proceeded to the point where the message buffer can
267 be reused.}
268
269 \function{void CmiReleaseCommHandle(CmiCommHandle handle)}
270 \index{CmiReleaseCommHandle}
271 \desc{Releases the communication handle \uw{handle} and
272 associated resources. It does not free the message buffer.}
273
274 \function{void CmiMultipleSend(unsigned int destPE, int len, int sizes[], char
275 *msgComps[])}
276 \index{CmiMultipleSend}
277 \desc{This function\experimental{} allows the user to send 
278 multiple messages that may be
279 destined for the SAME PE in one go. This is more efficient than sending
280 each message to the destination node separately. This function assumes
281 that the handlers that are to receive this message have already been set.
282 If this is not done, the behavior of the function is undefined.
283
284 In the function, The \uw{destPE} parameter identifies the destination
285 processor.
286 The \uw{len} argument identifies the {\it number} of messages that are to
287 be sent in one go. 
288 The \uw{sizes[]} array is an array of sizes of each of these messages.
289 The \uw{msgComps[]} array is the array of the messages. 
290 The indexing in each array is from 0 to len - 1.
291 \note{
292 Before calling this function, the program needs to initialise the system
293 to be able to provide this service. This is done by calling the function
294 \kw{CmiInitMultipleSendRoutine}. Unless this function is
295 called, the system will not be able to provide the service to the user.}
296 }
297
298 \section{Broadcasting Messages}
299
300 \function{void CmiSyncBroadcast(unsigned int size, void *msg)}
301 \index{CmiSyncBroadcast}
302 \desc{Sends \uw{msg} of length \uw{size} bytes to all processors
303 excluding the processor on which the caller resides. }
304
305 \function{void CmiSyncNodeBroadcast(unsigned int size, void *msg)}
306 \index{CmiSyncNodeBroadcast}
307 \desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
308 excluding the node on which the caller resides. }
309
310 \function{void CmiSyncBroadcastAndFree(unsigned int size, void *msg)}
311 \index{CmiSyncBroadcastAndFree}
312 \desc{Sends \uw{msg} of length \uw{size} bytes to all processors
313 excluding the processor on which the caller resides.  Uses \kw{CmiFree} to 
314 deallocate the message buffer for \uw{msg} when the
315 broadcast completes. Therefore \uw{msg} must point to a buffer
316 allocated with \kw{CmiAlloc}.}
317
318 \function{void CmiSyncNodeBroadcastAndFree(unsigned int size, void *msg)}
319 \index{CmiSyncNodeBroadcastAndFree}
320 \desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
321 excluding the node on which the caller resides.  Uses \kw{CmiFree} to 
322 deallocate the message buffer for \uw{msg} when the
323 broadcast completes. Therefore \uw{msg} must point to a buffer
324 allocated with \kw{CmiAlloc}.}
325
326 \function{void CmiSyncBroadcastAll(unsigned int size, void *msg)}
327 \index{CmiSyncBroadcastAll}
328 \desc{Sends \uw{msg} of length \uw{size} bytes to all processors
329 including the processor on which the caller resides. This function
330 does not free the message buffer for \uw{msg}.}
331
332 \function{void CmiSyncNodeBroadcastAll(unsigned int size, void *msg)}
333 \index{CmiSyncNodeBroadcastAll}
334 \desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
335 including the node on which the caller resides. This function
336 does not free the message buffer for \uw{msg}.}
337
338 \function{void CmiSyncBroadcastAllAndFree(unsigned int size, void *msg)}
339 \index{CmiSyncBroadcastAllAndFree}
340 \desc{Sends \uw{msg} of length \uw{size} bytes to all processors
341 including the processor on which the caller resides. This function
342 frees the message buffer for \uw{msg} before returning, so
343 \uw{msg} must point to a dynamically allocated buffer.}
344
345 \function{void CmiSyncNodeBroadcastAllAndFree(unsigned int size, void *msg)}
346 \index{CmiSyncNodeBroadcastAllAndFree}
347 \desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
348 including the node on which the caller resides. This function
349 frees the message buffer for \uw{msg} before returning, so
350 \uw{msg} must point to a dynamically allocated buffer.}
351
352 \function{CmiCommHandle CmiAsyncBroadcast(unsigned int size, void *msg)}
353 \index{CmiAsyncBroadcast}
354 \desc{Initiates asynchronous broadcast of message \uw{msg} of
355 length \uw{size} bytes to all processors excluding the processor on
356 which the caller resides. It returns a communication handle which
357 could be used to check the status of this send using
358 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
359 message buffer can be reused immediately, thus saving a call to 
360 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
361 freed before the communication is complete.}
362
363 \function{CmiCommHandle CmiAsyncNodeBroadcast(unsigned int size, void *msg)}
364 \index{CmiAsyncNodeBroadcast}
365 \desc{Initiates asynchronous broadcast of message \uw{msg} of
366 length \uw{size} bytes to all nodes excluding the node on
367 which the caller resides. It returns a communication handle which
368 could be used to check the status of this send using
369 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
370 message buffer can be reused immediately, thus saving a call to 
371 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
372 freed before the communication is complete.}
373
374 \function{CmiCommHandle CmiAsyncBroadcastAll(unsigned int size, void *msg)}
375 \index{CmiAsyncBroadcastAll}
376 \desc{Initiates asynchronous broadcast of message \uw{msg} of
377 length \uw{size} bytes to all processors including the processor on
378 which the caller resides. It returns a communication handle which
379 could be used to check the status of this send using
380 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
381 message buffer can be reused immediately, thus saving a call to 
382 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
383 freed before the communication is complete.}
384
385 \function{CmiCommHandle CmiAsyncNodeBroadcastAll(unsigned int size, void *msg)}
386 \index{CmiAsyncNodeBroadcastAll}
387 \desc{Initiates asynchronous broadcast of message \uw{msg} of
388 length \uw{size} bytes to all nodes including the node on
389 which the caller resides. It returns a communication handle which
390 could be used to check the status of this send using
391 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
392 message buffer can be reused immediately, thus saving a call to 
393 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
394 freed before the communication is complete.}
395
396 \section{Multicasting Messages}
397
398 \function{typedef ... CmiGroup;}
399 \index{CmiGroup}
400 \desc{A \kw{CmiGroup} represents a set of processors.  It is an opaque type.
401 Group IDs are useful for the multicast functions below.}
402
403 \function{CmiGroup CmiEstablishGroup(int npes, int *pes);}
404 \index{CmiGroup}
405 \desc{Converts an array of processor numbers into a group ID.  Group
406 IDs are useful for the multicast functions below.  Caution: this call
407 uses up some resources.  In particular, establishing a group uses 
408 some network bandwidth (one broadcast's worth) and a small amount of
409 memory on all processors.}
410
411 \function{void CmiSyncMulticast(CmiGroup grp, unsigned int size, void *msg)}
412 \index{CmiSyncBroadcast}
413 \desc{Sends \uw{msg} of length \uw{size} bytes to all members
414 of the specified group.  Group IDs are created using
415 \kw{CmiEstablishGroup}.}
416
417 \function{void CmiSyncMulticastAndFree(CmiGroup grp, unsigned int size, void *msg)}
418 \index{CmiSyncBroadcastAndFree}
419 \desc{Sends \uw{msg} of length \uw{size} bytes to all members
420 of the specified group.  Uses \kw{CmiFree} to deallocate the
421 message buffer for \uw{msg} when the broadcast completes. Therefore
422 \uw{msg} must point to a buffer allocated with \kw{CmiAlloc}.
423 Group IDs are created using \kw{CmiEstablishGroup}.}
424
425 \function{CmiCommHandle CmiAsyncMulticast(CmiGroup grp, unsigned int size, void *msg)}
426 \index{CmiAsyncBroadcast}
427 \desc{\note{Not yet implemented.} Initiates asynchronous broadcast of
428 message \uw{msg} of length \uw{size} bytes to all members of
429 the specified group.  It returns a communication handle which could
430 be used to check the status of this send using
431 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
432 message buffer can be reused immediately, thus saving a call to 
433 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
434 freed before the communication is complete.
435 Group IDs are created using \kw{CmiEstablishGroup}.}
436
437 \function{void CmiSyncListSend(int npes, int *pes, unsigned int size, void *msg)}
438 \index{CmiSyncBroadcast}
439 \desc{\note{Not yet implemented.} Sends \uw{msg} of length \uw{size} bytes
440 to all processors in the list.  Group IDs are created using
441 \kw{CmiEstablishGroup}.}
442
443 \function{void CmiSyncMulticastAndFree(int npes, int *pes, unsigned int size, void *msg)}
444 \index{CmiSyncBroadcastAndFree}
445 \desc{\note{Not yet implemented.} Sends \uw{msg} of length \uw{size}
446 bytes to all processors in the list.  Uses \kw{CmiFree} to deallocate the
447 message buffer for \uw{msg} when the broadcast completes. Therefore
448 \uw{msg} must point to a buffer allocated with \kw{CmiAlloc}.
449 Group IDs are created using \kw{CmiEstablishGroup}.}
450
451 \function{CmiCommHandle CmiAsyncMulticast(int npes, int *pes, unsigned int size, void *msg)}
452 \index{CmiAsyncBroadcast}
453 \desc{\note{Not yet implemented.} Initiates asynchronous broadcast of
454 message \uw{msg} of length \uw{size} bytes to all processors
455 in the list.  It returns a communication handle which could
456 be used to check the status of this send using
457 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0,
458 message buffer can be reused immediately, thus saving a call to 
459 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
460 freed before the communication is complete.
461 Group IDs are created using \kw{CmiEstablishGroup}.}
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