Simulation Model for Core Functions

  From the above discussion, it should be evident that if the simulator correctly simulates the functionality and timings of MPI_Issend, MPI_Ibsend, MPI_Irecv and MPI_Wait, all other message passing calls can be correctly constructed and simulated using these calls. Consequently, we present a simulation model based only on these four calls.

As mentioned in the previous chapter, in the simulation model, there is an LP corresponding to each process of the target program execution, and each LP executes the target program. Code without communication is directly executed, and communication is simulated (see Chapter 4). For the simulation of MPI programs, there is a data structure associated with each LP called a request list. The request list is an ordered list (by simulation timestamp) of the pending non-blocking operations of the LP. An LP also has a set of message queues, one for each communicator its corresponding target process belongs to. The following is a description of the actions taken by an LP in the simulation model on the execution of each of the above four core calls:

1. MPI_Issend: The message (with source, destination, tag, communicator and data) is sent to the receiver LP. It is timestamped with the send timestamp, which is the current simulation time of the LP and the receive timestamp, which is the send timestamp plus the message latency. Message latency is predicted by locating (or interpolating) the delay for the given message size in previously measured delays for a range of message sizes. The message is also marked with a request for acknowledgment, meaning that when it is accepted by the receiver, it should return a timestamped acknowledgement. At the sender, a request is queued at the end of the LP's request list, and marked as a request from a synchronous send.
2. MPI_Ibsend: The same procedure is followed as for MPI_Issend, except for three differences: (a) Initially, a buffer availability check is performed. A buffer availability check reserves space for the message in the program allocated buffer area. Notice that in the simulation model, this space does not physically exist. There is only a number which indicates many bytes are occupied. If no space is available at that simulation time, the simulation is completed with the report that the program would have aborted at that point due to lack of buffer space. (b) While calculating the receive timestamp of the message, the delays are located in a table of delays for messages sent using buffered send rather than synchronous send (which accounts for the additional copying), and (c) The request queued at the request list is marked as a request from a buffered send.
3. MPI_Irecv: A request is queued at the request list. It is marked as a request to receive a message. The source, tag, and communicator of the receive are included in the request, as is the pointer to the buffer where the accepted message should be deposited.
4. MPI_Wait: The action taken depends on the type of request:
   1. MPI_Issend request: The request of a synchronous send is satisfied when the acknowledgement has been received. If it has been satisfied, the simulation time of the LP is updated to the maximum of the current simulation time and the receive timestamp of the acknowledgement. If it has not, the LP is blocked until it gets satisfied.
   2. MPI_Ibsend request: If the request is of a buffered send, the LP is resumed at the same simulation time, regardless or whether the request has been satisfied or not. However, if it has not been satisfied, the request stays in the request list until it is satisfied, at which simulation time the corresponding buffer space in the buffer attached to the LP is released. This information is used by the buffer availability check described earlier.
   3. MPI_Irecv request: If the type of request is a request to receive a message, and has been satisfied, the simulation time is updated to the maximum of the current simulation time and the receive timestamp of the arrived message, an acknowledgement with send timestamp equal to the maximum of the receive timestamp of the accepted message and the timestamp of the request is returned to the sender, and the LP is resumed. Otherwise the LP is blocked until a message arrives. Acknowledgements are assumed to have a constant message latency.

We assume that communication between LPs is FIFO. The simulation protocol used in this simulation model must ensure that MPI's in-order delivery rules are obeyed (in simulation time) while matching arriving messages with requests at an LP (see Section 5.2.1.2). Matching acknowledgements with their corresponding requests requires no such effort by the simulation protocol, simply because there is only one matching request for each acknowledgement.

This simulation model correctly reproduces the functionality and timings of any target MPI program that uses the MPI implementation described in the previous section (Section 5.3.1). This claim is strengthened by the results in Section 5.5.