doc/charm++: startup text revisions
[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 \label{sec:multicast}
402
403 \function{typedef ... CmiGroup;}
404 \index{CmiGroup}
405 \desc{A \kw{CmiGroup} represents a set of processors.  It is an opaque type.
406 Group IDs are useful for the multicast functions below.}
407
408 \function{CmiGroup CmiEstablishGroup(int npes, int *pes);}
409 \index{CmiGroup}
410 \index{CmiEstablishGroup}
411 \desc{Converts an array of processor numbers into a group ID.  Group
412 IDs are useful for the multicast functions below.  Caution: this call
413 uses up some resources.  In particular, establishing a group uses 
414 some network bandwidth (one broadcast's worth) and a small amount of
415 memory on all processors.}
416
417 \function{void CmiSyncMulticast(CmiGroup grp, unsigned int size, void *msg)}
418 \index{CmiSyncMulticast}
419 \desc{Sends \uw{msg} of length \uw{size} bytes to all members
420 of the specified group.  Group IDs are created using
421 \kw{CmiEstablishGroup}.}
422
423 \function{void CmiSyncMulticastAndFree(CmiGroup grp, unsigned int size, void *msg)}
424 \index{CmiSyncMulticastAndFree}
425 \desc{Sends \uw{msg} of length \uw{size} bytes to all members
426 of the specified group.  Uses \kw{CmiFree} to deallocate the
427 message buffer for \uw{msg} when the broadcast completes. Therefore
428 \uw{msg} must point to a buffer allocated with \kw{CmiAlloc}.
429 Group IDs are created using \kw{CmiEstablishGroup}.}
430
431 \function{CmiCommHandle CmiAsyncMulticast(CmiGroup grp, unsigned int size, void *msg)}
432 \index{CmiAsyncMulticast}
433 \desc{\note{Not yet implemented.} Initiates asynchronous broadcast of
434 message \uw{msg} of length \uw{size} bytes to all members of
435 the specified group.  It returns a communication handle which could
436 be used to check the status of this send using
437 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
438 message buffer can be reused immediately, thus saving a call to 
439 \kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
440 freed before the communication is complete.
441 Group IDs are created using \kw{CmiEstablishGroup}.}
442
443 \function{void CmiSyncListSend(int npes, int *pes, unsigned int size, void *msg)}
444 \index{CmiSyncListSend}
445 \desc{Sends \uw{msg} of length \uw{size} bytes to \uw{npes} processors in the
446 array \uw{pes}.}
447
448 \function{void CmiSyncListSendAndFree(int npes, int *pes, unsigned int size, void *msg)}
449 \index{CmiSyncListSendAndFree}
450 \desc{Sends \uw{msg} of length \uw{size} bytes to \uw{npes} processors in the
451 array \uw{pes}. Uses \kw{CmiFree} to deallocate the message buffer for \uw{msg}
452 when the multicast completes. Therefore, \uw{msg} must point to a buffer
453 allocated with \kw{CmiAlloc}.}
454
455 \function{CmiCommHandle CmiAsyncListSend(int npes, int *pes, unsigned int size, void *msg)}
456 \index{CmiAsyncListSend}
457 \desc{Initiates asynchronous multicast of message \uw{msg} of length \uw{size}
458 bytes to \uw{npes} processors in the array \uw{pes}. It returns a communication
459 handle which could be used to check the status of this send using
460 \kw{CmiAsyncMsgSent}. If the returned communication handle is 0, message buffer
461 can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}. \uw{msg}
462 should not be overwritten or freed before the communication is complete.}
463
464 \section{Reducing Messaging}
465 \label{reduce}
466
467 Reductions are operations for which a message (or user data structure) is
468 contributed by each partecipant processor. All these contributions are merged
469 according to a merge-function provided by the user. A Converse handler is then
470 invoked with the resulting message. Reductions can be on the entire set of
471 processors, or on a subset of the whole.
472 Currently reductions are only implemented on processors sets. No equivalent
473 exists for SMP nodes.
474
475 There are eight functions used to deposit a message into the system, summarized
476 in Table~\ref{table:reductions}. Half of them receive as contribution a Converse
477 message (with a Converse header at its beginning). This message must have
478 already been set for delivery to the desired handler. The other half (ending
479 with ``Struct'') receives a pointer to a data structure allocated by the user. 
480 This second version may allow the user to write a simpler merging function. For
481 instance, the data structure could be a tree that can be easily expanded by
482 adding more nodes.
483
484 \begin{table}[h]
485 \begin{center}
486 \begin{tabular}{|l|llll|}
487 \hline
488  & {\bf global} & {\bf global with ID} & {\bf processor set} & {\bf CmiGroup} \\
489 \hline
490 {\bf message} & CmiReduce & CmiReduceID & CmiListReduce & CmiGroupReduce \\
491 {\bf data} & CmiReduceStruct & CmiReduceStructID & CmiListReduceStruct & CmiGroupReduceStruct \\
492 \hline
493 \end{tabular}
494 \end{center}
495 \caption{Reductions functions in Converse}
496 \label{table:reductions}
497 \end{table}
498
499 The signatures for the functions in Table~\ref{table:reductions} are:
500
501 \function{void CmiReduce(void *msg, int size, CmiReduceMergeFn mergeFn);}
502 \function{void CmiReduceStruct(void *data, CmiReducePupFn pupFn,
503                      CmiReduceMergeFn mergeFn, CmiHandler dest,
504                      CmiReduceDeleteFn deleteFn);}
505 \function{void CmiReduceID(void *msg, int size, CmiReduceMergeFn mergeFn, CmiReductionID id);}
506 \function{void CmiReduceStructID(void *data, CmiReducePupFn pupFn,
507                      CmiReduceMergeFn mergeFn, CmiHandler dest,
508                      CmiReduceDeleteFn deleteFn, CmiReductionID id);}
509 \function{void CmiListReduce(int npes, int *pes, void *msg, int size, CmiReduceMergeFn mergeFn, CmiReductionID id);}
510 \function{void CmiListReduceStruct(int npes, int *pes,
511                      void *data, CmiReducePupFn pupFn,
512                      CmiReduceMergeFn mergeFn, CmiHandler dest,
513                      CmiReduceDeleteFn deleteFn, CmiReductionID id);}
514 \function{void CmiGroupReduce(CmiGroup grp, void *msg, int size, CmiReduceMergeFn mergeFn, CmiReductionID id);}
515 \function{void CmiGroupReduceStruct(CmiGroup grp, void *data, CmiReducePupFn pupFn,
516                      CmiReduceMergeFn mergeFn, CmiHandler dest,
517                      CmiReduceDeleteFn deleteFn, CmiReductionID id);}
518
519 In all the above, \uw{msg} is the Converse message deposited by the local
520 processor, \uw{size} is the size of the message \uw{msg}, and \uw{data} is a
521 pointer to the user-allocated data structure deposited by the local processor.
522 \uw{dest} is the \kw{CmiHandler} where the final message shall be delivered. It
523 is explicitly passed in ``Struct'' functions only, since for the message
524 versions it is taken from the header of \uw{msg}. Moreover there are several
525 other function pointers passed in by the user:
526
527 \function{void * (*mergeFn)(int *size, void *local, void **remore, int count)}
528 \desc{Prototype for a \kw{CmiReduceMergeFn} function pointer argument.
529 This function is used in all the CmiReduce forms to merge the local
530 message/data structure deposited on a processor with all the messages incoming
531 from the children processors of the reduction spanning tree. The input parameters
532 are in the order: the size of the local data for message reductions (always zero
533 for struct reductions); the local data itself (the exact same pointer passed in as first
534 parameter of CmiReduce and similar); a pointer to an array of incoming messages;
535 the number of elements in the second parameter. The function returns a pointer
536 to a freshly allocated message (or data structure for the \kw{Struct} forms)
537 corresponding to the merge of all the messages. When performing message
538 reductions, this function is also responsible to updating the integer pointed by
539 \uw{size} to the new size of the returned message. All the messages in the
540 \uw{remote} array are deleted by the system; the data pointed by the first parameter
541 should be deleted by this function. If the data can be merged ``in-place'' by
542 modifying or augmenting \uw{local}, the function can return the same pointer to
543 \uw{local} which can be considered freshly allocated. Each element in \uw{remote}
544 is the complete incoming message (including the converse header) for message
545 reductions, and the data as it has been packed by the pup function (without any
546 additional header) for struct reductions.}
547
548 \function{void (*pupFn)(pup\_er p, void *data)}
549 \desc{Prototype for a \kw{CmiReducePupFn} function pointer argument.
550 This function will use the PUP framework to pup the \uw{data} passed in
551 into a message for sending across the network. The data can be either the same
552 data passed in as first parameter of any ``Struct'' function, or
553 the return of the merge function. It will be called for sizing and packing.
554 \note{It will not be called for unpacking.}}
555
556 \function{void (*deleteFn)(void *ptr)}
557 \desc{Prototype for a \kw{CmiReduceDeleteFn} function pointer argument.
558 This function is used to delete either the data stucture passed in as first
559 parameter of any ``Struct'' function, or the return of the merge
560 function. It can be as simple as ``free'' or as complicated as needed to delete
561 complex structures. If this function is NULL, the data structure will not be
562 deleted, and the program can continue to use it. Note: even if this function is
563 NULL, the input data structure may still be modified by the merge function.}
564
565 \uw{CmiReduce} and \uw{CmiReduceStruct} are the simplest reduction function, and
566 they reduce the deposited message/data across all the processors in the
567 system. Each processor must to call this function exactly once.
568 Multiple reductions can be invoked without waiting for previous ones to finish,
569 but the user is responsible to call CmiReduce/CmiReduceStruct in the same
570 order on every processor. \note{CmiReduce and CmiReduceStruct are not
571 interchangeable. Either every processor calls CmiReduce or every processor calls
572 CmiReduceStruct}.
573
574 In situations where it is not possible to guarantee the order of reductions, the
575 user may use \uw{CmiReduceID} or \uw{CmiReduceStructID}. These functions have an
576 additional parameter of type \kw{CmiReductionID} which will uniquely identify the
577 reduction, and match them correctly. \note{No two reductions can be active at
578 the same time with the same CmiReductionID. It is up to the user to guarantee
579 this.}
580
581 A \kw{CmiReductionID} can be obtained by the user in three ways, using one of
582 the following functions:
583
584 \function{CmiReductionID CmiGetGlobalReduction()}
585 \desc{This function must be called on every processor, and in the same order if
586 called multiple times. This would generally be inside initialization code, that
587 can set aside some CmiReductionIDs for later use.}
588
589 \function{CmiReductionID CmiGetDynamicReduction()}
590 \desc{This function may be called only on processor zero. It returns a unique
591 ID, and it is up to the user to distrubute this ID to any processor that needs
592 it.}
593
594 \function{void CmiGetDynamicReductionRemote(int handlerIdx, int pe, int dataSize, void *data)}
595 \desc{This function may be called on any processor. The produced CmiReductionID
596 is returned on the specified \uw{pe} by sending a message to the specified
597 \uw{handlerIdx}. If \uw{pe} is -1, then all processors will receive the
598 notification message. \uw{data} can be any data structure that the user wants to
599 receive on the specified handler (for example to differentiate between
600 requests). \uw{dataSize} is the size in bytes of \uw{data}. If \uw{dataSize} is
601 zero, \uw{data} is ignored.
602 The message received by \uw{handlerIdx} consists of the standard Converse
603 header, followed by the requested CmiReductionID (represented as a 4 bytes
604 integer the user can cast to a \kw{CmiReductionID}, a 4 byte integer containing
605 \uw{dataSize}, and the \uw{data} itself.}
606
607 The other four functions (CmiListReduce, CmiListReduceStruct, CmiGroupReduce,
608 CmiGroupReduceStruct) are used for reductions over subsets of processors. They
609 all require a CmiReductionID that the user must obtain in one of the ways
610 described above. The user is also responsible that no two reductions use the
611 same CmiReductionID simultaneously. The first two functions receive the subset
612 description as processor list (\uw{pes}) of size \uw{npes}. The last two receive
613 the subset description as a previously established CmiGroup
614 (see~\ref{sec:multicast}).
615
616 \section{Scheduling Messages}
617 \label{schedqueue}
618
619 The scheduler queue is a powerful priority queue.  The following
620 functions can be used to place messages into the scheduler queue.
621 These messages are treated very much like newly-arrived messages: when
622 they reach the front of the queue, they trigger handler functions,
623 just like messages transmitted with CMI functions.  Note that unlike
624 the CMI send functions, these cannot move messages across processors.
625
626 Every message inserted into the queue has a priority associated with
627 it.  \converse{} priorities are arbitrary-precision numbers between 0 and
628 1.  Priorities closer to 0 get processed first, priorities closer to 1
629 get processed last.  Arbitrary-precision priorities are very useful in
630 AI search-tree applications. Suppose we have a heuristic suggesting
631 that tree node N1 should be searched before tree node N2. We therefore
632 designate that node N1 and its descendants will use high priorities,
633 and that node N2 and its descendants will use lower priorities. We
634 have effectively split the range of possible priorities in two. If
635 several such heuristics fire in sequence, we can easily split the
636 priority range in two enough times that no significant bits remain,
637 and the search begins to fail for lack of meaningful priorities to
638 assign. The solution is to use arbitrary-precision priorities, aka
639 bitvector priorities.
640
641 These arbitrary-precision numbers are represented as bit-strings: for
642 example, the bit-string ``0011000101'' represents the binary number
643 (.0011000101).  The format of the bit-string is as follows: the
644 bit-string is represented as an array of unsigned integers. The most
645 significant bit of the first integer contains the first bit of the
646 bitvector.  The remaining bits of the first integer contain the next
647 31 bits of the bitvector.  Subsequent integers contain 32 bits
648 each. If the size of the bitvector is not a multiple of 32, then the
649 last integer contains 0 bits for padding in the least-significant bits
650 of the integer.
651
652 Some people only want regular integers as priorities.  For
653 simplicity's sake, we provide an easy way to convert integer
654 priorities to \converse{}'s built-in representation.
655
656 In addition to priorities, you may choose to enqueue a message
657 ``LIFO'' or ``FIFO''.  Enqueueing a message ``FIFO'' simply pushes it
658 behind all the other messages of the same priority.  Enqueueing a
659 message ``LIFO'' pushes it in front of other messages of the same
660 priority.
661
662 Messages sent using the CMI functions take precedence over everything
663 in the scheduler queue, regardless of priority.
664
665 A recent addition\experimental{} to \converse{} scheduling mechanisms is 
666 the introduction of
667 node-level scheduling designed to support low-overhead programming for the
668 SMP clusters. These functions have ``Node'' in their names. All processors
669 within the node has access to the node-level scheduler's queue, and thus
670 a message enqueued in a node-level queue may be handled by any processor within
671 that node. When deciding about which message to process next, i.e. from
672 processor's own queue or from the node-level queue, a quick priority check
673 is performed internally, thus a processor views scheduler's queue as a single
674 prioritized queue that includes messages directed at that processor and
675 messages from the node-level queue sorted according to priorities.
676
677 \function{void CsdEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)}
678 \index{CsdEnqueueGeneral}
679 \desc{This call enqueues a message to the processor's scheduler's queue, to
680 be sorted according to its priority and the queueing \param{strategy}.
681 The meaning of the \uw{priobits} and \uw{prioptr} fields depend
682 on the value of \uw{strategy}, which are explained below.}
683
684 \function{void CsdNodeEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)}
685 \index{CsdNodeEnqueueGeneral}
686 \desc{This call enqueues a message to the node-level scheduler's queue, to
687 be sorted according to its priority and the queueing \uw{strategy}.
688 The meaning of the \uw{priobits} and \uw{prioptr} fields depend
689 on the value of \uw{strategy}, which can be any of the following:
690
691 \begin{itemize}
692 \item{\kw{CQS\_QUEUEING\_BFIFO}: the priobits and prioptr point to
693 a bit-string representing an arbitrary-precision priority.  The message
694 is pushed behind all other message of this priority.}
695
696 \item{\kw{CQS\_QUEUEING\_BLIFO}: the priobits and prioptr point to
697 a bit-string representing an arbitrary-precision priority.  The message
698 is pushed in front all other message of this priority.}
699
700 \item{\kw{CQS\_QUEUEING\_IFIFO}: the prioptr is a pointer to a
701 signed integer.  The integer is converted to a bit-string priority,
702 normalizing so that the integer zero is converted to the bit-string
703 ``1000...'' (the ``middle'' priority).  To be more specific, the
704 conversion is performed by adding 0x80000000 to the integer, and then
705 treating the resulting 32-bit quantity as a 32-bit bitvector priority.
706 The message is pushed behind all other messages of this priority.}
707
708 \item{\kw{CQS\_QUEUEING\_ILIFO}: the prioptr is a pointer to a
709 signed integer.  The integer is converted to a bit-string priority,
710 normalizing so that the integer zero is converted to the bit-string
711 ``1000...'' (the ``middle'' priority).  To be more specific, the
712 conversion is performed by adding 0x80000000 to the integer, and then
713 treating the resulting 32-bit quantity as a 32-bit bitvector priority.
714 The message is pushed in front of all other messages of this
715 priority.}
716
717 \item{\kw{CQS\_QUEUEING\_FIFO}: the prioptr and priobits are ignored.
718 The message is enqueued with the middle priority ``1000...'', and is
719 pushed behind all other messages with this priority.}
720
721 \item{\kw{CQS\_QUEUEING\_LIFO}: the prioptr and priobits are ignored.
722 The message is enqueued with the middle priority ``1000...'', and is
723 pushed in front of all other messages with this priority.}
724
725 \end{itemize}
726
727 Caution: the priority itself is {\em not copied} by the scheduler.
728 Therefore, if you pass a pointer to a priority into the scheduler, you
729 must not overwrite or free that priority until after the message has
730 emerged from the scheduler's queue.  It is normal to actually store
731 the priority {\em in the message itself}, though it is up to the user
732 to actually arrange storage for the priority.
733 }
734
735 \function {void CsdEnqueue(void *Message)}
736 \index{CsdEnqueue}
737 \desc{This macro is a shorthand for 
738 \begin{alltt}
739 CsdEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL) 
740 \end{alltt}
741 provided here for backward compatibility.}
742
743 \function {void CsdNodeEnqueue(void *Message)}
744 \index{CsdNodeEnqueue}
745 \desc{This macro is a shorthand for 
746 \begin{alltt}
747 CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL) 
748 \end{alltt}
749 provided here for backward compatibility.}
750
751 \function{void CsdEnqueueFifo(void *Message)}
752 \index{CsdEnqueueFifo}
753 \desc{This macro is a shorthand for 
754 \begin{alltt}
755 CsdEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL)
756 \end{alltt}
757 provided here for backward compatibility.}
758
759 \function{void CsdNodeEnqueueFifo(void *Message)}
760 \index{CsdNodeEnqueueFifo}
761 \desc{This macro is a shorthand for 
762 \begin{alltt}
763 CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL)
764 \end{alltt}
765 provided here for backward compatibility.}
766
767 \function{void CsdEnqueueLifo(void *Message)}
768 \index{CsdEnqueueLifo}
769 \desc{This macro is a shorthand for
770 \begin{alltt}
771 CsdEnqueueGeneral(Message, CQS\_QUEUEING\_LIFO,0, NULL)
772 \end{alltt}
773 provided here for backward compatibility.}
774
775 \function{void CsdNodeEnqueueLifo(void *Message)}
776 \index{CsdNodeEnqueueLifo}
777 \desc{This macro is a shorthand for
778 \begin{alltt}
779 CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_LIFO,0, NULL) 
780 \end{alltt}
781 provided here for backward compatibility.}
782
783 \function{int CsdEmpty()}
784 \index{CsdEmpty}
785 \desc{This function returns non-zero integer when the scheduler's 
786 processor-level queue is empty, zero otherwise.}
787
788 \function{int CsdNodeEmpty()}
789 \index{CsdNodeEmpty}
790 \desc{This function returns non-zero integer when the scheduler's 
791 node-level queue is empty, zero otherwise.}
792
793 \section{Polling for Messages}
794 \label{polling}
795
796 As we stated earlier, \converse{} messages trigger handler functions when
797 they arrive.  In fact, for this to work, the processor must
798 occasionally poll for messages.  When the user starts \converse{}, he can
799 put it into one of several modes.  In the normal mode, the message
800 polling happens automatically.  However {\em user-calls-scheduler}
801 mode is designed to let the user poll manually.  To do this, the user
802 must use one of two polling functions: \kw{CmiDeliverMsgs}, or
803 \kw{CsdScheduler}.  \kw{CsdScheduler} is more general, it will notice any
804 \converse{} event.  \kw{CmiDeliverMsgs} is a lower-level function that ignores
805 all events except for recently-arrived messages.  (In particular, it
806 ignores messages in the scheduler queue).  You can save a tiny amount
807 of overhead by using the lower-level function.  We recommend the use
808 of \kw{CsdScheduler} for all applications except those that are using only
809 the lowest level of \converse{}, the CMI.  A third polling function,
810 \kw{CmiDeliverSpecificMsg}, is used when you know the exact event you want
811 to wait for: it does not allow any other event to occur.
812
813 In each iteration, a scheduler first looks for any message that 
814 has arrived from another processor, and delivers it.
815 If there isn't any, it selects a message from the locally enqueued
816 messages, and delivers it. 
817
818 \function {void CsdScheduleForever(void)} \index{CsdScheduleForever}
819 \desc{Extract and deliver messages until the scheduler is stopped.
820 Raises the idle handling converse signals.  This is the scheduler to
821 use in most \converse{} programs.}
822
823 \function {int CsdScheduleCount(int n)} \index{CsdScheduleCount}
824 \desc{Extract and deliver messages until $n$ messages
825 have been delivered, then return 0. If the scheduler is stopped
826 early, return $n$ minus the number of messages delivered so far.
827 Raises the idle handling converse signals.}
828
829 \function {void CsdSchedulePoll(void)} \index{CsdSchedulePoll}
830 \desc{Extract and deliver messages until no more messages
831 are available, then return.  This is useful for running
832 non-networking code when the networking code has nothing to do.}
833
834 \function {void CsdScheduler(int n)}
835 \index{CsdScheduler}
836 \desc{If $n$ is zero, call CsdSchedulePoll.  If $n$ is negative, call
837 CsdScheduleForever.  If $n$ is positive, call CsdScheduleCount($n$).}
838
839
840 \function{int CmiDeliverMsgs(int MaxMsgs)}
841 \index{CmiDeliverMsgs}
842 \desc{Retrieves messages from the network message queue and invokes 
843 corresponding handler functions for arrived messages. This function 
844 returns after either the network message queue becomes empty or after
845 \uw{MaxMsgs} messages have been retrieved and their handlers called. 
846 It returns the difference between total messages delivered and \uw{MaxMsgs}.
847 The handler is given a pointer to the message as  its parameter.}
848
849 \function{void CmiDeliverSpecificMsg(int HandlerId)}
850 \index{CmiDeliverSpecificMsg}
851 \desc{Retrieves messages from the network queue and delivers the first
852 message with its handler field equal to \uw{HandlerId}. This functions
853 leaves alone all other messages. It returns after the invoked handler
854 function returns.}
855
856 \function {void CsdExitScheduler(void)}
857 \index{CsdExitScheduler}
858 \desc{This call causes CsdScheduler to stop processing messages when
859 control has returned back to it. The scheduler then returns to its
860 calling routine.}
861
862
863 \zap{
864 \section{Global Pointer}
865
866 \function{int CmiGptrCreate(GlobalPtr *gptr, void *lptr, unsigned int size)}
867 \desc{This function creates a global pointer by initializing contents of
868 \param{*gptr} to point to memory on the local processor pointed to by
869 \param{lptr} of \param{size} bytes. \param{*gptr} could then be sent to other 
870 processors, and could be used by \param{CmiGet()} and \param{CmiPut()}
871 to read and write this memory by remote processors. This functions returns
872 a positive integer on success.}
873
874 \function{void *CmiGptrDref(GlobalPtr *gptr)}
875 \desc{This function returns the address of local memory associated
876 with global pointer \param{gptr}.}
877
878 \function{int CmiSyncGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
879 \desc{Copies \param{size} bytes from 
880 memory pointed to by global pointer \param{gptr}
881 to local memory pointed to by \param{lptr}. 
882 This is a synchronous operation and the calling processor blocks until
883 the data is transferred to local memory. This function returns
884 a positive integer on success.}
885
886 \function{CommHandle CmiGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
887 \desc{Initiates copying of \param{size} bytes from 
888 memory pointed to by global pointer \param{gptr}
889 to local memory pointed to by \param{lptr}. 
890 This function returns a  communication handle which could be used
891 to  enquire about the status of this operation.}
892
893 \function{CommHandle CmiPut(GlobalPtr *gptr, void *lptr, unsigned int size)}
894 \desc{Initiates copying of \param{size} bytes from a processor's local
895 memory pointed to by \param{lptr} to the memory pointed to by global
896 pointer \param{gptr}.  This function returns a  communication handle
897 which could be used to  enquire about the status of this operation.}
898 }
899
900 \section{The Timer}
901
902 \function{double CmiTimer(void)}
903 \index{CmiTimer}
904 \desc{Returns current value of the timer in seconds. This is
905 typically the time spent since the \kw{ConverseInit} call.
906 The precision of this timer is the best available on the particular machine,
907 and usually has at least microsecond accuracy.}
908
909 \section{Processor Ids}
910
911 \function{int CmiNumPe(void)}
912 \index{CmiNumPe}
913 \desc{Returns the total number of processors on which the 
914 parallel program is being run.}
915
916 \function{int CmiMyPe(void)}
917 \index{CmiMyPe}
918 \desc{Returns the logical processor identifier of processor on which the 
919 caller resides. A processor Id is between \texttt{0} and 
920 \texttt{\kw{CmiNumPe}()-1}.}
921
922 Also see the calls in Section~\ref{utility}.
923
924 \input{cpvmacros}
925
926 \section{Input/Output}
927
928 \function{void CmiPrintf(char *format, arg1, arg2, ...)}
929 \index{CmiPrintf}
930 \desc{This function does an atomic \texttt{printf()} on \texttt{stdout}. 
931 On machine with host, this is implemented on top of the messaging 
932 layer using asynchronous sends.}
933
934 \function{int CmiScanf(char *format, void *arg1, void *arg2, ...)}
935 \index{CmiScanf}
936 \desc{This function performs an atomic \texttt{scanf} from \texttt{stdin}.
937 The processor, on which the caller resides, blocks for input. On machines with
938 host, this is implemented on top of the messaging layer using asynchronous
939 send and blocking receive.}
940
941 \function{void CmiError(char *format, arg1, arg2, ...)}
942 \index{CmiError}
943 \desc{This function does an atomic \texttt{printf()} on \texttt{stderr}. 
944 On machines with host, this is implemented on top of the messaging 
945 layer using asynchronous sends.}
946
947 \zap{
948 \section{Processor Groups}
949
950 \function{void CmiPgrpCreate(Pgrp *group)}
951 \desc{Creates a processor-group with calling processsor as the root processor.}
952
953 \function{void CmiPgrpDestroy(Pgrp *group)}
954 \desc{Frees resources associated with a processor group \param{group}.}
955
956 \function{void CmiAddChildren(Pgrp *group, int penum, int size, int procs[])}
957 \desc{Adds \param{size} processors from array \param{procs[]} to the
958 processor-group \param{group} as children of processor penum. This function
959 could be called only by the root processor of processor-group \param{group}.}
960
961 \function{CommHandle CmiAsyncMulticast(Pgrp *group, unsigned int size, void *msg)}
962 \desc{Initiates asynchronous broadcast of message \param{msg} of
963 length \param{size} bytes to all processors belonging to \param{group}
964 excluding the processor on which the caller resides. It returns a
965 communication handle which could be used to check the status of this
966 send using \param{CmiAsyncMsgSent()}. If the returned communication handle 
967 is 0, message buffer can be reused immediately, thus saving a call to 
968 CmiAsyncMsgSent. \param{msg} should not be
969 overwritten or freed before the communication is complete. \note{Caller
970 need not belong to \param{group}.}} 
971
972 \function{int CmiPgrpRoot(Pgrp *group)}
973 \desc{Returns the processor id of root of processor-group \param{group}. }
974
975 \function{int CmiNumChildren(Pgrp *group, int penum)}
976 \desc{Returns  number of children of processor \param{penum} 
977 in the processor-group \param{group}.}
978
979 \function{int CmiParent(Pgrp *group, int penum)}
980 \desc{Returns  processor id of parent of processor \param{penum} 
981 in the processor-group \param{group}.}
982
983 \function{void CmiChildren(Pgrp *group, int node, int *children)}
984 \desc{Fills in array \param{children} with processor ids of all the
985 children processor \param{node} in processor-group \param{group}. This
986 array should at least be of size \param{CmiNumChildren()}.}
987 }
988
989 \section{Spanning Tree Calls}
990
991 Sometimes, it is convenient to view the processors/nodes of the machine as a
992 tree.  For this purpose, \converse{} defines a tree over processors/nodes.  We
993 provide functions to obtain the parent and children of each processor/node.  On
994 those machines where the communication topology is relevant, we
995 arrange the tree to optimize communication performance. The root of
996 the spanning tree (processor based or node-based) is always 0, thus
997 the \kw{CmiSpanTreeRoot} call has been eliminated.
998
999 \function{int CmiSpanTreeParent(int procNum)}
1000 \index{CmiSpanTreeParent}
1001 \desc{This function returns the processor number of the parent of
1002 \uw{procNum} in the spanning tree.}
1003
1004 \function{int CmiNumSpanTreeChildren(int procNum)}
1005 \index{CmiNumSpanTreeChildren}
1006 \desc{Returns the number of children of \uw{procNum} in the spanning tree.}
1007
1008 \function{void CmiSpanTreeChildren(int procNum, int *children)}
1009 \index{CmiSpanTreeChildren}
1010 \desc{This function fills the array \uw{children} with processor
1011 numbers of children of \uw{procNum} in the spanning tree.}
1012
1013 \function{int CmiNodeSpanTreeParent(int nodeNum)}
1014 \index{CmiNodeSpanTreeParent}
1015 \desc{This function returns the node number of the parent of
1016 \uw{nodeNum} in the spanning tree.}
1017
1018 \function{int CmiNumNodeSpanTreeChildren(int nodeNum)}
1019 \index{CmiNumNodeSpanTreeChildren}
1020 \desc{Returns the number of children of \uw{nodeNum} in the spanning tree.}
1021
1022 \function{void CmiNodeSpanTreeChildren(int nodeNum, int *children)}
1023 \index{CmiNodeSpanTreeChildren}
1024 \desc{This function fills the array \uw{children} with node
1025 numbers of children of \uw{nodeNum} in the spanning tree.}
1026
1027
1028
1029
1030