\chapter{Machine Interface and Scheduler}

This chapter describes two of \converse{}'s modules: the CMI, and the
CSD.  Together, they serve to transmit messages and schedule the
delivery of messages. First, we describe the machine model assumed by
\converse{}.

\section{Machine Model}
\label{model}

\converse{} treats the parallel machine as a collection of {\em nodes}, where
each node is comprised of a number of {\em processors} that share memory 
In some cases, the number of processors per node may be exactly one  
(e.g. Distributed memory multicomputers such as IBM SP.)  
In addition, each of the processors may have multiple {\em threads} running on
them which share code and data but have different stacks.
Functions and macros are provided for handling shared memory across
processors and querying node information. These are discussed in section
\ref{globalvars}

\section{Defining Handler Numbers}
\label{handler1}

When a message arrives at a processor, it triggers the execution of a
{\em handler function}, not unlike a UNIX signal handler.  The handler
function receives, as an argument, a pointer to the message.
The message itself specifies which handler function is to be
called when the message arrives.  Messages are contiguous sequences of
bytes.  The message has two parts: the header, and the data.  The data
may contain anything you like.  The header contains a {\em handler
number}, which specifies which handler function is to be executed when
the message arrives.  Before you can send a message, you have to
define the handler numbers.

\converse{} maintains a table mapping handler numbers to function
pointers.  Each processor has its own copy of the mapping.  There is a
caution associated with this approach: it is the user's responsibility
to ensure that all processors have identical mappings.  This is easy
to do, nonetheless, and the user must be aware that this is (usually)
required.

The following functions are provided to define the handler numbers:

\function{typedef void (*CmiHandler)(void *)}
\index{CmiHandler}
\desc{Functions that handle \converse{} messages must be of this type.}

\function{int CmiRegisterHandler(CmiHandler h)}
\index{CmiRegisterHandler}
\desc{This represents the standard technique for associating numbers
with functions.  To use this technique, the \converse{} user registers
each of his functions, one by one, using \kw{CmiRegisterHandler}.  One must
register exactly the same functions in exactly the same order on all
processors.  The system assigns monotonically increasing numbers to
the functions, the same numbers on all processors.  This insures
global consistency.  \kw{CmiRegisterHandler} returns the number which was
chosen for the function being registered.}

\function {int CmiRegisterHandlerGlobal(CmiHandler h)}
\index{CmiRegisterHandlerLocal}
\desc{This represents a second registration technique.   The \converse{}
user registers his functions on processor zero, using
\kw{CmiRegisterHandlerGlobal}.  The \converse{} user is then responsible for
broadcasting those handler numbers to other processors, and installing
them using \kw{CmiNumberHandler} below.  The user should take care not to
invoke those handlers until they are fully installed.}

\function {int CmiRegisterHandlerLocal(CmiHandler h)}
\index{CmiRegisterHandlerLocal}
\desc{This function is used when one wishes to register functions
in a manner that is not consistent across processors.  This function
chooses a locally-meaningful number for the function, and records it
locally.  No attempt is made to ensure consistency across processors.}

\function {void CmiNumberHandler(int n, CmiHandler h)}
\index{CmiNumberHandler}
\desc{Forces the system to associate the specified handler number \uw{n}
with the specified handler function \uw{h}.  If the function number
\uw{n} was previously mapped to some other function, that old mapping
is forgotten.  The mapping that this function creates is local to the
current processor.  \kw{CmiNumberHandler} can be useful in combination with
\kw{CmiRegisterGlobalHandler}.  It can also be used to implement
user-defined numbering schemes: such schemes should keep in mind that
the size of the table that holds the mapping is proportional to the
largest handler number --- do not use big numbers!}

\note{Of the three registration methods, the \kw{CmiRegisterHandler} method
is by far the simplest, and is strongly encouraged.  The others are
primarily to ease the porting of systems that already use similar
registration techniques.  One may use all three registration methods
in a program.  The system guarantees that no numbering conflicts will
occur as a result of this combination.}

\section{Writing Handler Functions}
\label{handler2}

A message handler function is just a C function that accepts a void
pointer (to a message buffer) as an argument, and returns nothing.  The
handler may use the message buffer until it returns, at which time
\converse{} will automatically free the message buffer.  This behavior
can be overridden using \kw{CmiGrabBuffer}:

\function{void CmiGrabBuffer(void **pbuf)}
\index{CmiGrabBuffer}
\desc{A handler function receives a pointer to a message buffer
as an argument.  Normally, it is supposed to copy the data out of the
message buffer before it returns, at which time \converse{} automatically
frees the message buffer.  However, a handler function may use
\kw{CmiGrabBuffer} to claim ownership of the message buffer (and therefore
prevent \converse{} from freeing it).  Assuming, for example, that the
handler function called its argument \uw{msg}, it would call 
\begin{alltt}
CmiGrabBuffer(\&msg)
\end{alltt}
Afterward, \uw{msg} contains a pointer to the
message, or a copy of it.  From that point forward, it is the user's
responsibility to free the message using \kw{CmiFree}.
}

\function{void CmiReleaseBuffer(void *buf)}
\index{CmireleaseBuffer}
\desc{A handler function receives a pointer to a message buffer
as an argument.  Normally, it is supposed to copy the data out of the
message buffer before it returns, at which time \converse{} automatically
frees the message buffer or may reuse it for further communication.  
However, a handler function may use
\kw{CmiReleaseBuffer} to give up ownership of the message buffer in the
middle of handler execution (and therefore allowing \converse{} to reuse it).}

\section{Building Messages}

To send a message, one first creates a buffer to hold the message.
The buffer must be large enough to hold the header and the data.
The buffer can be in any kind of memory: it could be a local variable,
it could be a global, it could be allocated with {\tt malloc}, and
finally, it could be allocated with \kw{CmiAlloc}.  The \converse{} user
fills the buffer with the message data.  One puts a handler number
in the message, thereby specifying which handler function the message
should trigger when it arrives.  Finally, one uses a message-transmission
function to send the message.

The following functions are provided to help build message buffers:

\function{void *CmiAlloc(int size)}
\index{CmiAlloc}
\desc{Allocates memory of size \uw{size} in heap and returns pointer to 
the usable space.  There are some message-sending functions that
accept only message buffers that were allocated with \kw{CmiAlloc}.  Thus,
this is the preferred way to allocate message buffers.}

\function{void CmiFree(void *ptr)}
\index{CmiFree}
\desc{This function frees the memory pointed to by \uw{ptr}. \uw{ptr}
should be a pointer that was previously returned by \kw{CmiAlloc}.}

\function {\#define CmiMsgHeaderSizeBytes}
\index{CmiMsgHeaderSizeBytes}
\desc{This constant contains the size of the message header.  When one
allocates a message buffer, one must set aside enough space for the header
and the data.  This macro helps you to do so.}

\function {void CmiSetHandler(int *MessageBuffer, int HandlerId)}
\index{CmiSetHandler}
\desc{This macro sets the handler number of a message to \uw{HandlerId}.}

\function {int CmiGetHandler(int *MessageBuffer)}
\index{CmiGetHandler}
\desc{This call returns the handler of a message in the form of a
handler number.}
 
\function {CmiHandler CmiGetHandlerFunction(int *MessageBuffer)}
\index{CmiGetHandlerFunction}
\desc{This call returns the handler of a message in the form of a
function pointer.}

\section{Sending Messages}

The following functions allow you to send messages.  Our model is that
the data starts out in the message buffer, and from there gets
transferred ``into the network''.  The data stays ``in the network''
for a while, and eventually appears on the target processor.  Using
that model, each of these send-functions is a device that transfers
data into the network.  None of these functions wait for the data to
be delivered.

On some machines, the network accepts data rather slowly.  We don't
want the process to sit idle, waiting for the network to accept the
data.  So, we provide several variations on each send function:

\begin{itemize}

\item{{\bf sync}: a version that is as simple as possible, pushing the
data into the network and not returning until the data is ``in the
network''.  As soon as a sync function returns, you can reuse the
message buffer.}

\item{{\bf async}: a version that returns almost instantaneously, and then
continues working in the background.  The background job transfers the
data from the message buffer into the network.  Since the background job
is still using the message buffer when the function returns, you can't
reuse the message buffer immediately.  The background job sets a flag
when it is done and you can then reuse the message buffer.}

\item{{\bf sync and free}: a version that returns almost instantaneously,
and then continues working in the background.  The background job
transfers the data from the message buffer into the network.  When the
background job finishes, it \kw{CmiFree}s the message buffer.  In
this situation, you can't reuse the message buffer at all.  Of course,
to use a function of this type, you must allocate the message buffer
using \kw{CmiAlloc}.}

\item{{\bf node}\experimental{}: a version that send a message to a node 
instead of a
specific processor. This means that when the message is received, any ``free''
processor within than node can handle it.}

\end{itemize}

\function{void CmiSyncSend(unsigned int destPE, unsigned int size, void *msg)}
\index{CmiSyncSend}
\desc{Sends \uw{msg} of size \uw{size} bytes to processor
\uw{destPE}.  When it returns, you may reuse the message buffer.}

\function{void CmiSyncNodeSend(unsigned int destNode, unsigned int size, void *msg)}
\index{CmiSyncNodeSend}
\desc{Sends\experimental{} \uw{msg} of size \uw{size} bytes to node
\uw{destNode}.  When it returns, you may reuse the message buffer.}

\function{void CmiSyncSendAndFree(unsigned int destPE, unsigned int size, void *msg)}
\index{CmiSyncSendAndFree}
\desc{Sends \uw{msg} of size \uw{size} bytes to processor
\uw{destPE}.  When it returns, the message buffer has been freed
using \kw{CmiFree}.}

\function{void CmiSyncNodeSendAndFree(unsigned int destNode, unsigned int size, void *msg)}
\index{CmiSyncNodeSendAndFree}
\desc{Sends\experimental{} \uw{msg} of size \uw{size} bytes to node
\uw{destNode}.  When it returns, the message buffer has been freed
using \kw{CmiFree}.}

\function{CmiCommHandle CmiAsyncSend(unsigned int destPE, unsigned int size, void *msg)}
\index{CmiAsyncSend}
\desc{Sends \uw{msg} of size \uw{size} bytes to processor
\uw{destPE}.  It returns a communication handle which can be
tested using \kw{CmiAsyncMsgSent}: when this returns true, you may reuse
the message buffer. If the returned communication handle is 0, message buffer
can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}.}

\function{CmiCommHandle CmiAsyncNodeSend(unsigned int destNode, unsigned int size, void *msg)}
\index{CmiAsyncNodeSend}
\desc{Sends\experimental{} \uw{msg} of size \uw{size} bytes to node
\uw{destNode}.  It returns a communication handle which can be
tested using \kw{CmiAsyncMsgSent}: when this returns true, you may reuse
the message buffer. If the returned communication handle is 0, message buffer
can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}.}

\function{void CmiSyncVectorSend(int destPE, int len, int sizes[], char *msgComps[])}
\desc{Concatenates several pieces of data and sends them to processor
\uw{destPE}.  The data consists of \uw{len} pieces residing in
different areas of memory, which are logically concatenated.  The
\uw{msgComps} array contains pointers to the pieces; the size of
\uw{msgComps[i]} is taken from \uw{sizes[i]}. 
When it returns, \uw{sizes}, \uw{msgComps} and the message
components specified in \uw{msgComps} can be immediately reused.}

\function{void CmiSyncVectorSendAndFree(int destPE, int len, int sizes[], char *msgComps[])}
\desc{Concatenates several pieces of data and sends them to processor
\uw{destPE}.  The data consists of \uw{len} pieces residing in
different areas of memory, which are logically concatenated.  The
\uw{msgComps} array contains pointers to the pieces; the size of
\uw{msgComps[i]} is taken from \uw{sizes[i]}. 
The message components specified in \uw{msgComps} are \kw{CmiFree}d 
by this function therefore, they should be dynamically
allocated using \kw{CmiAlloc}.  However, the \uw{sizes} and
\uw{msgComps} array themselves are not freed.}

\function{CmiCommHandle CmiAsyncVectorSend(int destPE, int len, int sizes[], char *msgComps[])}
\desc{Concatenates several pieces of data and sends them to processor
\uw{destPE}.  The data consists of \uw{len} pieces residing in
different areas of memory, which are logically concatenated.  The
\uw{msgComps} array contains pointers to the pieces; the size of
\uw{msgComps[i]} is taken from \uw{sizes[i]}. 
The individual pieces of data as well as the arrays \uw{sizes} and
\uw{msgComps} should not be overwritten or freed before the
communication is complete.  This function returns a communication
handle which can be tested using \kw{CmiAsyncMsgSent}: when this returns
true, the input parameters can be reused. If the returned communication 
handle is 0, message buffer
can be reused immediately, thus saving a call to \kw{CmiAsyncMsgSent}.}

\function{int CmiAsyncMsgSent(CmiCommHandle handle)}
\index{CmiAsyncMsgSent}
\desc{Returns true if the communication specified by the given
\kw{CmiCommHandle} has proceeded to the point where the message buffer can
be reused.}

\function{void CmiReleaseCommHandle(CmiCommHandle handle)}
\index{CmiReleaseCommHandle}
\desc{Releases the communication handle \uw{handle} and
associated resources. It does not free the message buffer.}

\function{void CmiMultipleSend(unsigned int destPE, int len, int sizes[], char
*msgComps[])}
\index{CmiMultipleSend}
\desc{This function\experimental{} allows the user to send 
multiple messages that may be
destined for the SAME PE in one go. This is more efficient than sending
each message to the destination node separately. This function assumes
that the handlers that are to receive this message have already been set.
If this is not done, the behavior of the function is undefined.

In the function, The \uw{destPE} parameter identifies the destination
processor.
The \uw{len} argument identifies the {\it number} of messages that are to
be sent in one go. 
The \uw{sizes[]} array is an array of sizes of each of these messages.
The \uw{msgComps[]} array is the array of the messages. 
The indexing in each array is from 0 to len - 1.
\note{
Before calling this function, the program needs to initialise the system
to be able to provide this service. This is done by calling the function
\kw{CmiInitMultipleSendRoutine}. Unless this function is
called, the system will not be able to provide the service to the user.}
}

\section{Broadcasting Messages}

\function{void CmiSyncBroadcast(unsigned int size, void *msg)}
\index{CmiSyncBroadcast}
\desc{Sends \uw{msg} of length \uw{size} bytes to all processors
excluding the processor on which the caller resides. }

\function{void CmiSyncNodeBroadcast(unsigned int size, void *msg)}
\index{CmiSyncNodeBroadcast}
\desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
excluding the node on which the caller resides. }

\function{void CmiSyncBroadcastAndFree(unsigned int size, void *msg)}
\index{CmiSyncBroadcastAndFree}
\desc{Sends \uw{msg} of length \uw{size} bytes to all processors
excluding the processor on which the caller resides.  Uses \kw{CmiFree} to 
deallocate the message buffer for \uw{msg} when the
broadcast completes. Therefore \uw{msg} must point to a buffer
allocated with \kw{CmiAlloc}.}

\function{void CmiSyncNodeBroadcastAndFree(unsigned int size, void *msg)}
\index{CmiSyncNodeBroadcastAndFree}
\desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
excluding the node on which the caller resides.  Uses \kw{CmiFree} to 
deallocate the message buffer for \uw{msg} when the
broadcast completes. Therefore \uw{msg} must point to a buffer
allocated with \kw{CmiAlloc}.}

\function{void CmiSyncBroadcastAll(unsigned int size, void *msg)}
\index{CmiSyncBroadcastAll}
\desc{Sends \uw{msg} of length \uw{size} bytes to all processors
including the processor on which the caller resides. This function
does not free the message buffer for \uw{msg}.}

\function{void CmiSyncNodeBroadcastAll(unsigned int size, void *msg)}
\index{CmiSyncNodeBroadcastAll}
\desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
including the node on which the caller resides. This function
does not free the message buffer for \uw{msg}.}

\function{void CmiSyncBroadcastAllAndFree(unsigned int size, void *msg)}
\index{CmiSyncBroadcastAllAndFree}
\desc{Sends \uw{msg} of length \uw{size} bytes to all processors
including the processor on which the caller resides. This function
frees the message buffer for \uw{msg} before returning, so
\uw{msg} must point to a dynamically allocated buffer.}

\function{void CmiSyncNodeBroadcastAllAndFree(unsigned int size, void *msg)}
\index{CmiSyncNodeBroadcastAllAndFree}
\desc{Sends \uw{msg} of length \uw{size} bytes to all nodes
including the node on which the caller resides. This function
frees the message buffer for \uw{msg} before returning, so
\uw{msg} must point to a dynamically allocated buffer.}

\function{CmiCommHandle CmiAsyncBroadcast(unsigned int size, void *msg)}
\index{CmiAsyncBroadcast}
\desc{Initiates asynchronous broadcast of message \uw{msg} of
length \uw{size} bytes to all processors excluding the processor on
which the caller resides. It returns a communication handle which
could be used to check the status of this send using
\kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
message buffer can be reused immediately, thus saving a call to 
\kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
freed before the communication is complete.}

\function{CmiCommHandle CmiAsyncNodeBroadcast(unsigned int size, void *msg)}
\index{CmiAsyncNodeBroadcast}
\desc{Initiates asynchronous broadcast of message \uw{msg} of
length \uw{size} bytes to all nodes excluding the node on
which the caller resides. It returns a communication handle which
could be used to check the status of this send using
\kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
message buffer can be reused immediately, thus saving a call to 
\kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
freed before the communication is complete.}

\function{CmiCommHandle CmiAsyncBroadcastAll(unsigned int size, void *msg)}
\index{CmiAsyncBroadcastAll}
\desc{Initiates asynchronous broadcast of message \uw{msg} of
length \uw{size} bytes to all processors including the processor on
which the caller resides. It returns a communication handle which
could be used to check the status of this send using
\kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
message buffer can be reused immediately, thus saving a call to 
\kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
freed before the communication is complete.}

\function{CmiCommHandle CmiAsyncNodeBroadcastAll(unsigned int size, void *msg)}
\index{CmiAsyncNodeBroadcastAll}
\desc{Initiates asynchronous broadcast of message \uw{msg} of
length \uw{size} bytes to all nodes including the node on
which the caller resides. It returns a communication handle which
could be used to check the status of this send using
\kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
message buffer can be reused immediately, thus saving a call to 
\kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
freed before the communication is complete.}

\section{Multicasting Messages}

\function{typedef ... CmiGroup;}
\index{CmiGroup}
\desc{A \kw{CmiGroup} represents a set of processors.  It is an opaque type.
Group IDs are useful for the multicast functions below.}

\function{CmiGroup CmiEstablishGroup(int npes, int *pes);}
\index{CmiGroup}
\desc{Converts an array of processor numbers into a group ID.  Group
IDs are useful for the multicast functions below.  Caution: this call
uses up some resources.  In particular, establishing a group uses 
some network bandwidth (one broadcast's worth) and a small amount of
memory on all processors.}

\function{void CmiSyncMulticast(CmiGroup grp, unsigned int size, void *msg)}
\index{CmiSyncBroadcast}
\desc{Sends \uw{msg} of length \uw{size} bytes to all members
of the specified group.  Group IDs are created using
\kw{CmiEstablishGroup}.}

\function{void CmiSyncMulticastAndFree(CmiGroup grp, unsigned int size, void *msg)}
\index{CmiSyncBroadcastAndFree}
\desc{Sends \uw{msg} of length \uw{size} bytes to all members
of the specified group.  Uses \kw{CmiFree} to deallocate the
message buffer for \uw{msg} when the broadcast completes. Therefore
\uw{msg} must point to a buffer allocated with \kw{CmiAlloc}.
Group IDs are created using \kw{CmiEstablishGroup}.}

\function{CmiCommHandle CmiAsyncMulticast(CmiGroup grp, unsigned int size, void *msg)}
\index{CmiAsyncBroadcast}
\desc{\note{Not yet implemented.} Initiates asynchronous broadcast of
message \uw{msg} of length \uw{size} bytes to all members of
the specified group.  It returns a communication handle which could
be used to check the status of this send using
\kw{CmiAsyncMsgSent}. If the returned communication handle is 0, 
message buffer can be reused immediately, thus saving a call to 
\kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
freed before the communication is complete.
Group IDs are created using \kw{CmiEstablishGroup}.}

\function{void CmiSyncListSend(int npes, int *pes, unsigned int size, void *msg)}
\index{CmiSyncBroadcast}
\desc{\note{Not yet implemented.} Sends \uw{msg} of length \uw{size} bytes
to all processors in the list.  Group IDs are created using
\kw{CmiEstablishGroup}.}

\function{void CmiSyncMulticastAndFree(int npes, int *pes, unsigned int size, void *msg)}
\index{CmiSyncBroadcastAndFree}
\desc{\note{Not yet implemented.} Sends \uw{msg} of length \uw{size}
bytes to all processors in the list.  Uses \kw{CmiFree} to deallocate the
message buffer for \uw{msg} when the broadcast completes. Therefore
\uw{msg} must point to a buffer allocated with \kw{CmiAlloc}.
Group IDs are created using \kw{CmiEstablishGroup}.}

\function{CmiCommHandle CmiAsyncMulticast(int npes, int *pes, unsigned int size, void *msg)}
\index{CmiAsyncBroadcast}
\desc{\note{Not yet implemented.} Initiates asynchronous broadcast of
message \uw{msg} of length \uw{size} bytes to all processors
in the list.  It returns a communication handle which could
be used to check the status of this send using
\kw{CmiAsyncMsgSent}. If the returned communication handle is 0,
message buffer can be reused immediately, thus saving a call to 
\kw{CmiAsyncMsgSent}. \uw{msg} should not be overwritten or
freed before the communication is complete.
Group IDs are created using \kw{CmiEstablishGroup}.}

\section{Scheduling Messages}
\label{schedqueue}

The scheduler queue is a powerful priority queue.  The following
functions can be used to place messages into the scheduler queue.
These messages are treated very much like newly-arrived messages: when
they reach the front of the queue, they trigger handler functions,
just like messages transmitted with CMI functions.  Note that unlike
the CMI send functions, these cannot move messages across processors.

Every message inserted into the queue has a priority associated with
it.  \converse{} priorities are arbitrary-precision numbers between 0 and
1.  Priorities closer to 0 get processed first, priorities closer to 1
get processed last.  Arbitrary-precision priorities are very useful in
AI search-tree applications. Suppose we have a heuristic suggesting
that tree node N1 should be searched before tree node N2. We therefore
designate that node N1 and its descendants will use high priorities,
and that node N2 and its descendants will use lower priorities. We
have effectively split the range of possible priorities in two. If
several such heuristics fire in sequence, we can easily split the
priority range in two enough times that no significant bits remain,
and the search begins to fail for lack of meaningful priorities to
assign. The solution is to use arbitrary-precision priorities, aka
bitvector priorities.

These arbitrary-precision numbers are represented as bit-strings: for
example, the bit-string ``0011000101'' represents the binary number
(.0011000101).  The format of the bit-string is as follows: the
bit-string is represented as an array of unsigned integers. The most
significant bit of the first integer contains the first bit of the
bitvector.  The remaining bits of the first integer contain the next
31 bits of the bitvector.  Subsequent integers contain 32 bits
each. If the size of the bitvector is not a multiple of 32, then the
last integer contains 0 bits for padding in the least-significant bits
of the integer.

Some people only want regular integers as priorities.  For
simplicity's sake, we provide an easy way to convert integer
priorities to \converse{}'s built-in representation.

In addition to priorities, you may choose to enqueue a message
``LIFO'' or ``FIFO''.  Enqueueing a message ``FIFO'' simply pushes it
behind all the other messages of the same priority.  Enqueueing a
message ``LIFO'' pushes it in front of other messages of the same
priority.

Messages sent using the CMI functions take precedence over everything
in the scheduler queue, regardless of priority.

A recent addition\experimental{} to \converse{} scheduling mechanisms is 
the introduction of
node-level scheduling designed to support low-overhead programming for the
SMP clusters. These functions have ``Node'' in their names. All processors
within the node has access to the node-level scheduler's queue, and thus
a message enqueued in a node-level queue may be handled by any processor within
that node. When deciding about which message to process next, i.e. from
processor's own queue or from the node-level queue, a quick priority check
is performed internally, thus a processor views scheduler's queue as a single
prioritized queue that includes messages directed at that processor and
messages from the node-level queue sorted according to priorities.

\function{void CsdEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)}
\index{CsdEnqueueGeneral}
\desc{This call enqueues a message to the processor's scheduler's queue, to
be sorted according to its priority and the queueing \param{strategy}.
The meaning of the \uw{priobits} and \uw{prioptr} fields depend
on the value of \uw{strategy}, which are explained below.}

\function{void CsdNodeEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)}
\index{CsdNodeEnqueueGeneral}
\desc{This call enqueues a message to the node-level scheduler's queue, to
be sorted according to its priority and the queueing \uw{strategy}.
The meaning of the \uw{priobits} and \uw{prioptr} fields depend
on the value of \uw{strategy}, which can be any of the following:

\begin{itemize}
\item{\kw{CQS\_QUEUEING\_BFIFO}: the priobits and prioptr point to
a bit-string representing an arbitrary-precision priority.  The message
is pushed behind all other message of this priority.}

\item{\kw{CQS\_QUEUEING\_BLIFO}: the priobits and prioptr point to
a bit-string representing an arbitrary-precision priority.  The message
is pushed in front all other message of this priority.}

\item{\kw{CQS\_QUEUEING\_IFIFO}: the prioptr is a pointer to a
signed integer.  The integer is converted to a bit-string priority,
normalizing so that the integer zero is converted to the bit-string
``1000...'' (the ``middle'' priority).  To be more specific, the
conversion is performed by adding 0x80000000 to the integer, and then
treating the resulting 32-bit quantity as a 32-bit bitvector priority.
The message is pushed behind all other messages of this priority.}

\item{\kw{CQS\_QUEUEING\_ILIFO}: the prioptr is a pointer to a
signed integer.  The integer is converted to a bit-string priority,
normalizing so that the integer zero is converted to the bit-string
``1000...'' (the ``middle'' priority).  To be more specific, the
conversion is performed by adding 0x80000000 to the integer, and then
treating the resulting 32-bit quantity as a 32-bit bitvector priority.
The message is pushed in front of all other messages of this
priority.}

\item{\kw{CQS\_QUEUEING\_FIFO}: the prioptr and priobits are ignored.
The message is enqueued with the middle priority ``1000...'', and is
pushed behind all other messages with this priority.}

\item{\kw{CQS\_QUEUEING\_LIFO}: the prioptr and priobits are ignored.
The message is enqueued with the middle priority ``1000...'', and is
pushed in front of all other messages with this priority.}

\end{itemize}

Caution: the priority itself is {\em not copied} by the scheduler.
Therefore, if you pass a pointer to a priority into the scheduler, you
must not overwrite or free that priority until after the message has
emerged from the scheduler's queue.  It is normal to actually store
the priority {\em in the message itself}, though it is up to the user
to actually arrange storage for the priority.
}

\function {void CsdEnqueue(void *Message)}
\index{CsdEnqueue}
\desc{This macro is a shorthand for 
\begin{alltt}
CsdEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL) 
\end{alltt}
provided here for backward compatibility.}

\function {void CsdNodeEnqueue(void *Message)}
\index{CsdNodeEnqueue}
\desc{This macro is a shorthand for 
\begin{alltt}
CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL) 
\end{alltt}
provided here for backward compatibility.}

\function{void CsdEnqueueFifo(void *Message)}
\index{CsdEnqueueFifo}
\desc{This macro is a shorthand for 
\begin{alltt}
CsdEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL)
\end{alltt}
provided here for backward compatibility.}

\function{void CsdNodeEnqueueFifo(void *Message)}
\index{CsdNodeEnqueueFifo}
\desc{This macro is a shorthand for 
\begin{alltt}
CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL)
\end{alltt}
provided here for backward compatibility.}

\function{void CsdEnqueueLifo(void *Message)}
\index{CsdEnqueueLifo}
\desc{This macro is a shorthand for
\begin{alltt}
CsdEnqueueGeneral(Message, CQS\_QUEUEING\_LIFO,0, NULL)
\end{alltt}
provided here for backward compatibility.}

\function{void CsdNodeEnqueueLifo(void *Message)}
\index{CsdNodeEnqueueLifo}
\desc{This macro is a shorthand for
\begin{alltt}
CsdNodeEnqueueGeneral(Message, CQS\_QUEUEING\_LIFO,0, NULL) 
\end{alltt}
provided here for backward compatibility.}

\function{int CsdEmpty()}
\index{CsdEmpty}
\desc{This function returns non-zero integer when the scheduler's 
processor-level queue is empty, zero otherwise.}

\function{int CsdNodeEmpty()}
\index{CsdNodeEmpty}
\desc{This function returns non-zero integer when the scheduler's 
node-level queue is empty, zero otherwise.}

\section{Polling for Messages}
\label{polling}

As we stated earlier, \converse{} messages trigger handler functions when
they arrive.  In fact, for this to work, the processor must
occasionally poll for messages.  When the user starts \converse{}, he can
put it into one of several modes.  In the normal mode, the message
polling happens automatically.  However {\em user-calls-scheduler}
mode is designed to let the user poll manually.  To do this, the user
must use one of two polling functions: \kw{CmiDeliverMsgs}, or
\kw{CsdScheduler}.  \kw{CsdScheduler} is more general, it will notice any
\converse{} event.  \kw{CmiDeliverMsgs} is a lower-level function that ignores
all events except for recently-arrived messages.  (In particular, it
ignores messages in the scheduler queue).  You can save a tiny amount
of overhead by using the lower-level function.  We recommend the use
of \kw{CsdScheduler} for all applications except those that are using only
the lowest level of \converse{}, the CMI.  A third polling function,
\kw{CmiDeliverSpecificMsg}, is used when you know the exact event you want
to wait for: it does not allow any other event to occur.

\function {void CsdScheduler(int NumberOfMessages)}
\index{CsdScheduler}
\desc{This call invokes the \converse{} scheduler, which repeatedly
delivers messages to their handlers (i.e. invokes the handler for each
message it selects).  In each iteration, the scheduler first looks for
any message that has arrived from another processor, and delivers it.
If there isn't any, it selects a message from the locally enqueued
messages, and delivers it.  The \uw{NumberOfMessages} parameter
specifies how many messages should be processed (i.e. delivered to
their handlers). If set to -1, the scheduler continues delivering
messages until \kw{CsdExitScheduler} is called from a message handler.
if \uw{NumberOfMessages} is 0, the scheduler continues delivering
messages until it exhausts its supply of messages (i.e. becomes idle)
or some handler calls \kw{CsdExitScheduler}.}

\function{int CmiDeliverMsgs(int MaxMsgs)}
\index{CmiDeliverMsgs}
\desc{Retrieves messages from the network message queue and invokes 
corresponding handler functions for arrived messages. This function 
returns after either the network message queue becomes empty or after
\uw{MaxMsgs} messages have been retrieved and their handlers called. 
It returns the difference between total messages delivered and \uw{MaxMsgs}.
The handler is given a pointer to the message as  its parameter.}

\function{void CmiDeliverSpecificMsg(int HandlerId)}
\index{CmiDeliverSpecificMsg}
\desc{Retrieves messages from the network queue and delivers the first
message with its handler field equal to \uw{HandlerId}. This functions
leaves alone all other messages. It returns after the invoked handler
function returns.}

\function {void CsdExitScheduler(void)}
\index{CsdExitScheduler}
\desc{This call causes CsdScheduler to stop processing messages when
control has returned back to it. The scheduler then returns to its
calling routine.}

\section{Scheduler Callbacks}
\label{schedcallbacks}

Scheduler callbacks are provided for programmers who want to utilize in
some way the event of scheduler becoming idle, or the scheduler becoming
busy again.  Typically, these callbacks are useful for determining idle
time in complex multilingual programs.  The callback function should not
contain calls to scheduler related functions.  Also, the callback
functions should not block indefinitely.  Doing so will cause the
conditional callbacks to fail.  Following functions are provided for
controlling the scheduler callbacks.

\function{void CsdStartNotifyIdle(void)}
\index{CsdStartNotifyIdle}
\desc{This call causes \kw{CsdScheduler} to invoke callback functions for
idle and busy notifications. Initially, the scheduler does not call
any callback functions.}

\function{void CsdStopNotifyIdle(void)}
\index{CsdStopNotifyIdle}
\desc{This call causes \kw{CsdScheduler} to stop invoking callback functions
for idle and busy norifications.}

\function{void CsdSetNotifyIdle(void (* fIdle)(void), void (* fBusy)(void))}
\index{CsdSetNotifyIdle}
\desc{This call registers the functions to be called when \kw{CsdScheduler} 
becomes
idle (\uw{fIdle}) or busy (\uw{fBusy}). These functions can be
overridden with another call to \kw{CsdSetNotifyIdle}.}

\zap{
\section{Global Pointer}

\function{int CmiGptrCreate(GlobalPtr *gptr, void *lptr, unsigned int size)}
\desc{This function creates a global pointer by initializing contents of
\param{*gptr} to point to memory on the local processor pointed to by
\param{lptr} of \param{size} bytes. \param{*gptr} could then be sent to other 
processors, and could be used by \param{CmiGet()} and \param{CmiPut()}
to read and write this memory by remote processors. This functions returns
a positive integer on success.}

\function{void *CmiGptrDref(GlobalPtr *gptr)}
\desc{This function returns the address of local memory associated
with global pointer \param{gptr}.}

\function{int CmiSyncGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
\desc{Copies \param{size} bytes from 
memory pointed to by global pointer \param{gptr}
to local memory pointed to by \param{lptr}. 
This is a synchronous operation and the calling processor blocks until
the data is transferred to local memory. This function returns
a positive integer on success.}

\function{CommHandle CmiGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
\desc{Initiates copying of \param{size} bytes from 
memory pointed to by global pointer \param{gptr}
to local memory pointed to by \param{lptr}. 
This function returns a  communication handle which could be used
to  enquire about the status of this operation.}

\function{CommHandle CmiPut(GlobalPtr *gptr, void *lptr, unsigned int size)}
\desc{Initiates copying of \param{size} bytes from a processor's local
memory pointed to by \param{lptr} to the memory pointed to by global
pointer \param{gptr}.  This function returns a  communication handle
which could be used to  enquire about the status of this operation.}
}

\section{The Timer}

\function{double CmiTimer(void)}
\index{CmiTimer}
\desc{Returns current value of the timer in seconds. This is
typically the time spent since the \kw{ConverseInit} call.
The precision of this timer is the best available on the particular machine,
and usually has at least microsecond accuracy.}

\section{Processor Ids}

\function{int CmiNumPe(void)}
\index{CmiNumPe}
\desc{Returns the total number of processors on which the 
parallel program is being run.}

\function{int CmiMyPe(void)}
\index{CmiMyPe}
\desc{Returns the logical processor identifier of processor on which the 
caller resides. A processor Id is between \texttt{0} and 
\texttt{\kw{CmiNumPe}()-1}.}

Also see the calls in Section~\ref{utility}.

\input{cpvmacros}

\section{Input/Output}

\function{void CmiPrintf(char *format, arg1, arg2, ...)}
\index{CmiPrintf}
\desc{This function does an atomic \texttt{printf()} on \texttt{stdout}. 
On machine with host, this is implemented on top of the messaging 
layer using asynchronous sends.}

\function{int CmiScanf(char *format, void *arg1, void *arg2, ...)}
\index{CmiScanf}
\desc{This function performs an atomic \texttt{scanf} from \texttt{stdin}.
The processor, on which the caller resides, blocks for input. On machines with
host, this is implemented on top of the messaging layer using asynchronous
send and blocking receive.}

\function{void CmiError(char *format, arg1, arg2, ...)}
\index{CmiError}
\desc{This function does an atomic \texttt{printf()} on \texttt{stderr}. 
On machines with host, this is implemented on top of the messaging 
layer using asynchronous sends.}

\zap{
\section{Processor Groups}

\function{void CmiPgrpCreate(Pgrp *group)}
\desc{Creates a processor-group with calling processsor as the root processor.}

\function{void CmiPgrpDestroy(Pgrp *group)}
\desc{Frees resources associated with a processor group \param{group}.}

\function{void CmiAddChildren(Pgrp *group, int penum, int size, int procs[])}
\desc{Adds \param{size} processors from array \param{procs[]} to the
processor-group \param{group} as children of processor penum. This function
could be called only by the root processor of processor-group \param{group}.}

\function{CommHandle CmiAsyncMulticast(Pgrp *group, unsigned int size, void *msg)}
\desc{Initiates asynchronous broadcast of message \param{msg} of
length \param{size} bytes to all processors belonging to \param{group}
excluding the processor on which the caller resides. It returns a
communication handle which could be used to check the status of this
send using \param{CmiAsyncMsgSent()}. If the returned communication handle 
is 0, message buffer can be reused immediately, thus saving a call to 
CmiAsyncMsgSent. \param{msg} should not be
overwritten or freed before the communication is complete. \note{Caller
need not belong to \param{group}.}} 

\function{int CmiPgrpRoot(Pgrp *group)}
\desc{Returns the processor id of root of processor-group \param{group}. }

\function{int CmiNumChildren(Pgrp *group, int penum)}
\desc{Returns  number of children of processor \param{penum} 
in the processor-group \param{group}.}

\function{int CmiParent(Pgrp *group, int penum)}
\desc{Returns  processor id of parent of processor \param{penum} 
in the processor-group \param{group}.}

\function{void CmiChildren(Pgrp *group, int node, int *children)}
\desc{Fills in array \param{children} with processor ids of all the
children processor \param{node} in processor-group \param{group}. This
array should at least be of size \param{CmiNumChildren()}.}
}

\section{Spanning Tree Calls}

Sometimes, it is convenient to view the processors/nodes of the machine as a
tree.  For this purpose, \converse{} defines a tree over processors/nodes.  We
provide functions to obtain the parent and children of each processor/node.  On
those machines where the communication topology is relevant, we
arrange the tree to optimize communication performance. The root of
the spanning tree (processor based or node-based) is always 0, thus
the \kw{CmiSpanTreeRoot} call has been eliminated.

\function{int CmiSpanTreeParent(int procNum)}
\index{CmiSpanTreeParent}
\desc{This function returns the processor number of the parent of
\uw{procNum} in the spanning tree.}

\function{int CmiNumSpanTreeChildren(int procNum)}
\index{CmiNumSpanTreeChildren}
\desc{Returns the number of children of \uw{procNum} in the spanning tree.}

\function{void CmiSpanTreeChildren(int procNum, int *children)}
\index{CmiSpanTreeChildren}
\desc{This function fills the array \uw{children} with processor
numbers of children of \uw{procNum} in the spanning tree.}

\function{int CmiNodeSpanTreeParent(int nodeNum)}
\index{CmiNodeSpanTreeParent}
\desc{This function returns the node number of the parent of
\uw{nodeNum} in the spanning tree.}

\function{int CmiNumNodeSpanTreeChildren(int nodeNum)}
\index{CmiNumNodeSpanTreeChildren}
\desc{Returns the number of children of \uw{nodeNum} in the spanning tree.}

\function{void CmiNodeSpanTreeChildren(int nodeNum, int *children)}
\index{CmiNodeSpanTreeChildren}
\desc{This function fills the array \uw{children} with node
numbers of children of \uw{nodeNum} in the spanning tree.}

