We assume a target message passing program executes as a collection of processes. The input to the target program contains (a) the number of processes to be executed and, (b) the input for each process, i.e. values for the program's uninitialized variables. In other words, each process executes the target program with its part of the input. The target program can contain only three types of statements: local, send and receive statements. A local statement (a) does not involve interaction with other processes and (b) is deterministic. We do not describe the types and semantics of local statements. The reader can assume statements similar to those of any sequential programming language e.g. C. In a process, the sequence of local statements executed in between two message passing statements is a local code block. We explain the semantics of send and receive statements using message queues. Let there be a message queue associated with each process.
Send(Receiver,BufferPtr,NumBytes);Upon the execution of a send statement, a process composes a message of data size NumBytes bytes from the data in the buffer pointed to by the address BufferPtr. The header of the message contains the sender id, the receiver id (i.e. Receiver) and the size of the data (i.e. NumBytes). The message is sent to the receiver process's message queue.
Receive(Sender,BufferPtr);Upon the execution of a receive statement, a process searches its message queue for the first message from Sender and blocks until a matching message arrives. The message is removed from the queue and the data in it deposited into the buffer pointed to by BufferPtr. Sender may be the constant
, in which case a message from any
source can match the receive.