The EOT[Jha93] (for Earliest Output Time) of an LP is a lower bound on the receive timestamp of the next message the LP will send. The EOT minus the current simulation time of the LP is the LP's lookahead[Fuj88]. The source set[Bag94] of an LP is the set of LPs that can send messages to it. The destination set of an LP is the inverse of the source set: the set of LPs to which an LP can send messages. The EIT of an LP in the null message protocol is the minimum of the EOTs of all LPs in its source set. An LP communicates its EOT to an LP in its destination set using a special message called a null message.
The performance of a null message protocol implementation is determined by the three factors: (a) The quality of EOT computation i.e. how accurately an LP can predict its EOT, (b) Identification of communication topology i.e. how accurately source sets of all the LPs can be identified, and (c) Frequency of null message communication. In the simplest implementation, an LP computes its EOT as its current simulation time plus L, where L is the minimum communication latency of the target machine. Each LP is in every LP's source set. Each LP sends out null messages to all LPs whenever it reaches its EIT. In this implementation, the simulation proceeds as follows: all LPs start at simulation time zero (which is also each LP's EIT). All LPs compute their EOTs to be L, and send null messages to all other LPs. This amounts to a global synchronization. Upon receiving the null messages of all other LPs, each LP computes its EIT, which must be L. Consequently, all LPs simulate until L, after which they repeat these steps again. It is not hard to see that this implementation of the null message protocol is identical to the safe quantum protocol. However, the null message protocol implementation can be made more efficient without making it unsafe. We perform the following optimizations:
EOT Computation and Null Message Frequency
In our simulation model, an LP does not need to know its EIT until it reaches a receive statement. Consequently, an LP does not synchronize with other LPs except when it is at a receive statement, and cannot find a matching message with receive timestamp less than EIT. When the EIT needs to be computed, a demand driven null message scheme is used: an LP requests null messages from all LPs in its source set, and recomputes (advances) its EIT whenever a null message arrives, possibly revealing a matching message that can now be safely accepted. An LP can get requested for a null message at any time: it computes and returns its EOT, which is its current simulation time plus the minimum communication latency, L, of the target machine.
Identification of Communication Topology
In our model, we have simple communication statements that do not provide any information on the communication topology. However, the statements of MPI do provide this information to the MPI simulation model we present in the next chapter. We use this information to identify an LP's actual (possibly very small) source set, and consequently significantly reduce the number of LPs it needs to synchronize with in order to compute its EIT.
Using the matching conditions of a receive statement, it is possible to
reduce the source set even further. The effective source
set of an LP at a receive statement is the set of LPs from which the
LP can accept messages (at that receive statement).
The effective source set is the source set masked by
the Sender field of the receive statement (which in
our model may be a named source or a dont care (
)). At a given
receive statement, an LP calculates its EIT as the minimum of the EOTs
of all LPs in its effective source set.
Consequently, it needs to synchronize with even fewer LPs than those
in its source set.
In our execution model, we assume FIFO communication between processes of the target program. In the simulation model, we assume FIFO communication between LPs. Consequently, the receive timestamp of a message is its sender's EOT. If a receiver is at a statement which causes it to have only one sender in its effective source set, the receiver's EIT is equal to the sender's EOT. Consequently, the receiver can safely accept a message from the sender as soon as it arrives. In other words, no synchronization is necessary at such a receive statement. This means that in a program in which all receive statements have a named source in the Sender field, no simulation protocol is necessary. The same conclusion can be alternatively reached at by noticing that such programs are deterministic i.e. can have only one program trace.