Communication model

Given a par statement and its corresponding synchronization graph, the next step is to generate an SPMD program, that will be executed by each of the threads of the statement, embedded with explicit message passing calls that implement the dependence arcs of the graph. We assume the following inter thread communication model (a specialization of the model provided by the message passing/simulation language Maisie[Bag94]):

• There is a message queue associated with each thread. A thread sends a message to another by depositing the message in the receiving thread's queue.
• There are three types of messages:
  1. Request Message: Contains six fields, a message type (request), sender id, data address, a data value, a read bit, and an integer tag. The read bit specifies whether the message is a request to read or to write. If it is a request to write, the data value field contains data otherwise it is empty. A request message is sent using the syntax send. <dest> specifies the destination thread number.
  2. Reply Message: Contains four fields, a message type (reply), a sender id, a data value and an integer tag. A reply message is sent using the syntax send.
  3. Barrier Message: Contains two fields, a message type (barrier) and a sender id. A barrier message is sent using the syntax send.
• Messages are delivered in order
• A thread can receive messages in two ways:
  1. Blocking receive: The syntax for this statement is:

     brecv mtype (<msgtype1>) st (<guard1>) {<code1>}
     or mtype (<msgtype2>) st (<guard2>) {<code2>}...

     This allows a thread to select and remove a message from its queue. The message that is selected, called the enabling message, must satisfy the conditions of the receive. Specifically, if the message is of type msgtype1, then its fields must satisfy <guard1>. If it is of type msgtype2 then its fields must satisfy <guard2> and so on. The guards are side-effect free boolean expressions involving program variables and message fields. If more than one message of different types satisfy the conditions of the receive, one type is selected non-deterministically. Within a particular type, if more than one message satisfies the conditions of the receive, the earliest message to be deposited in the queue is selected. If no message satisfies the conditions, the thread must wait until an enabling message arrives. Upon accepting an enabling message, a thread executes the corresponding code. Within this code, the fields of the enabling message can be referenced using the syntax .
  2. Non blocking receive: The syntax for this statement is the same as above except that it is called recv. The semantics are also the same except that if no enabling message is present the thread continues execution from the statement following the receive.