A Graph object is created based on an input graph. The object performs asynchronous, in-order, and flow-controlled multicast of event messages. The structure of the graph must remains static throughout the life time of the object. The graph object uses a user-supplied partitioner to assign nodes to processors (statically). The user also specifies the edge capacity, which bounds the maximum number of outstanding messages (i.e., those that have not been removed) for each edge. The higher the capacity, the less frequently the sender blocks due of bursty message traffic. However, an excessive capacity may lead to poor utilization of memory and, worst of all, excessive paging in the memory hierarchy.
There are three main operations on a Graph object - sending event messages (Graph_enqueueFIFO), receiving event messages (Graph_dequeueFIFO, Graph_readFIFO, Graph_deleteFIFO, Graph_deleteFIFOCommit), and taking a distributed snapshot (Graph_all_freeze, Graph_all_unFreeze). Event messages are not acknowledged - the send operation returns as soon as a buffer is allocated to hold the message. The interface eliminates communication for acknowledgement, but the user is burdened to check the status of message delivery by sending explicit acknowledgement messages, or taking snapshots using Graph_all_freeze. A thread can also explicitly wait on conditions such as the availability of buffer space (Graph_waitBufAvail), and the arrival of new messages (Graph_waitNewElt).
Graph_all_create, Graph_all_destroy, Graph_enqueueFIFO, Graph_waitBufAvail, Graph_dequeueFIFO, Graph_waitNewElt, Graph_all_freeze, and Graph_all_unFreeze are split-phase operations. A split-phase operations returns OK if it has completed upon return (i.e., no need to create a thread to wait for the the result), and WAIT otherwise. Graph_all_create, Graph_all_destroy, Graph_all_freeze and Graph_all_unFreeze must be called by one thread per processor on all processors. Non-split-phase primitives whose return type is Flag return OK if they succeed, and FAIL if exceptions occur.
Create a Graph object with id id. Use scheduler to deposit all threads associated with the object. The snapshot object sid is used for taking snapshot of the new Graph object with respect to its Graph_enqueueFIFO and Graph_dequeueFIFO operations. The input graph input specify the directed graph representing the sender/receiver relationship. The definition of input graphs is as follows:
typedef struct InputNode { /* Definition of a graph node */
int compCost; /* Estimated amount of computation */
int numIn; /* In degree */
int *inNodes; /* Array of indices of its fanin nodes */
int numOut; /* Out degree */
int *outNodes; /* Array of indices of its fanout nodes */
int *commOutCost; /* Estimated communication volume per edge */
} InputNode;
typedef struct InputGraph {/* Definition of a input graph */
int numNodes; /* Number of nodes in the graph */
InputNode* nodes; /* Node array (also define node indices) */
} InputGraph;
If anyElt is 0, the node is notified when a new message arrives at an empty edge. Otherwise, the node is notified whenever there is a new message. partitioner is a user supplied partitioner (see Graph_randomPartitioner) which assigns graph nodes to processors. FIFOSize specifies the edge capacity in number of messages. eltSize is the message size (in bytes). Graph_all_create increments the counter ctr after the object is created.
The Snapshot object sid must exist prior to the call. All operations on a graph node must be called on the assigned processor.
Free up the space taken by the Graph object id. Increment the counter ctr upon completion.
Graph_all_create currently does nothing.
Randomly assign nodes in the input graph input to the processors. Place the result mapping in the array map, with one entry per node containing the assigned processor number.
Return OK if the node nodeId of the Graph object id resides on the calling processor, and FAIL otherwise.
Return the in degree of the node nodeId of the Graph object id.
Send an event message along all outgoing edges for the node nodeId of the Graph object id. data points to the content of the message, which is copied into an internal buffer for delivery ( data cannot be modified when Graph_enqueueFIFO is executing). The message will arrive at all destination nodes in FIFO order. Graph_enqueueFIFO increments the counter ctr when there is space to hold the message on all destination nodes, that is, when the maximum number of outstanding messages over all edges is less than the edge capacity. The completion of Graph_enqueueFIFO does not imply the message has been received or processed by the destination nodes. It merely guarantees that the message will eventually be ready for the destination nodes to receive. When the message arrives at the destination node, threads suspended by Graph_waitNewElt or Graph_dequeueFIFO may be awaken.
Graph_enqueueFIFO cannot execute concurrently with Graph_enqueueFIFO on the same sending node, since the messages must be totally ordered. data cannot be modified until Graph_enqueueFIFO completes.
Wait until the maximum number of outstanding messages sent by the node nodeId of the Graph object id is less than the edge capacity. Increment the counter ctr upon completion. A message is outstanding if it has not been removed by all destination nodes via Graph_dequeueFIFO or Graph_deleteFIFOCommit.
Return the number of available out-going message buffers for the node nodeId of the Graph object id.
Receive and remove an incoming message at the FIFOId-th incoming edge of the node nodeId of the Graph object id. When the operation completes, the message body is copied into the buffer buf and the counter ctr is incremented. Graph_dequeueFIFO is similar to Graph_readFIFO, followed by Graph_deleteFIFO and then Graph_deleteFIFOCommit, except that it is split phased, and the message body is copied out into the user buffer.
Graph_dequeueFIFO cannot execute concurrently with Graph_dequeueFIFO, Graph_waitNewElt or any Graph_deleteFIFO/Graph_deleteFIFOCommit pairs on the same receiving node.
Return a pointer to the elt-th message at the FIFOId-th incoming edge of the node nodeId of the Graph object id. The pointer value is stored in bufPtr. The message is not copied, and cannot be modified directly (the change may not be visible to other nodes). The user must make a copy of the message prior to modification.
Node nodeId must have received (but not removed) at least elt incoming messages at the edge FIFOId. Graph_FIFONumElt is usually called before Graph_readFIFO to determine elt.
Remove the first numElt messages from the FIFOId-th incoming edge of the node nodeId of the Graph object id. Graph_deleteFIFO does not free up the space taken by these messages. The space must be freed by Graph_deleteFIFOCommit. Multiple Graph_deleteFIFO calls can precede a Graph_deleteFIFOCommit call to reduce the number of flow control messages for enforcing the edge capacity.
Node nodeId must have received (but not removed) at least elt incoming messages for the edge FIFOId. The Graph_deleteFIFO/ Graph_deleteFIFOCommit pair cannot be concurrent with Graph_dequeueFIFO on the same receiving node.
Graph_deleteFIFOCommit must be called eventually to ensure the messages' buffer space is available for reuse.
Free up the space for all messages removed from the incoming edge FIFOId of the node nodeId of the Graph object id. Graph_deleteFIFOCommit sends flow control messages to inform the sender of the availability of buffer space. Threads waiting for buffer space on the sending node (via Graph_enqueueFIFO or Graph_waitNewBuf may be enabled for execution.
The Graph_deleteFIFO/Graph_deleteFIFOCommit pair cannot be concurrent with Graph_dequeueFIFO on the same receiving node.
Wait until a new message arrives at some of the incoming edges of the node nodeId of the Graph object id. Increments the counter ctr upon completion. If anyElt is 0 when creating the object, Graph_waitNewElt completes when a new message arrives at an empty edge, otherwise, it completes when a new message arrives at any edge.
Graph_waitNewElt cannot execute concurrently with Graph_dequeueFIFO on the same receiving node. Threads awaken by Graph_waitNewElt must call Graph_FIFONumElt to ensure the availability of new messages, since there can be multiple threads competing to receive the same message.
Return the number of messages queued at the incoming edge FIFOId for the node nodeId of the Graph object id.
Wake up all threads waiting for Graph_waitNewElt. Graph_wakeUpNode is usually used in combination with Graph_waitNewElt when anyElt is 0, so that the threads may skip the first message of an edge to examine the rest of the messages.
Freeze the Graph object id with respect to the mutators Graph_enqueueFIFO and Graph_dequeueFIFO (by calling Snapshot_all_freeze on the Snapshot object sid). Increments the counter ctr upon completion. When Graph_all_freeze completes, all messages that are sent via completed Graph_enqueueFIFO operations are available for receive at the destination nodes. Some Graph_enqueueFIFO operations called before Graph_freeze may still be in a suspended state due to the lack of buffer space. Likewise, some Graph_dequeueFIFO operations called before Graph_freeze may also be in a suspended state to wait for new messages. The Graph_enqueueFIFO and Graph_dequeueFIFO operations that execute concurrently with Graph_freeze are suspended until Graph_unFreeze is called.
There cannot be concurrent Graph_all_freeze operations on the same object. Graph_all_freeze cannot be called when the object is already frozen. Non-split-phase operations such as Graph_readFIFO, Graph_deleteFIFO and Graph_deleteFIFOCommit are not affected by Graph_freeze.
Unfreeze the Graph object id and increment the counter ctr upon completion.
All Graph_enqueueFIFO and Graph_dequeueFIFO operations suspended by Graph_all_freeze are are reenabled for execution.
Graph_all_unFreeze must be called after the corresponding Graph_all_freeze completes. The Graph object id must be in a frozen state.