Next: Experiments
Up: Simulation Methodology
Previous: Simulation Methodology
The following terms are used in the sequel:
- DP program: The dataparallel program
- MP program: The message passing program that results
from compilation of DP. This is the target program.
- MPSIM program: The simulator for the MP program.
- N: Assuming some input, an execution of the
MP program on N nodes of the target machine (one process
per node)
-
: Assuming the same input, an execution of the
MPSIM program on k nodes (one simulation process per process
of the MP program, >= 1 simulation processes per processor)
As suggested in the previous subsection, a simple but inefficient
simulation of an MP program would require each simulation process of the
corresponding MPSIM program to synchronize with other simulation processes
before executing the next event on its event list. However,
the event list is basically the code of the MP program. The only
points at which a remote simulation process, say A, can affect
the execution of
a given simulation process, say B, is when B executes a receive statement.
Hence, the MPSIM program can execute send and local code block events
on its event list without first synchronizing with all other processes.
Upon encountering a receive statement however, the simulation process
B must accept the same message that was accepted by the corresponding
process of the MP program at the same point. However, receive statements
in MP programs occur only in deterministic communication patterns.
The following rule can then be used:
Rule: If in each execution of a MP program,
exactly k messages satisfy the conditions of receive R at
its each invocation, then
receive R can be accurately simulated by simply waiting for
k messages which satisfy the conditions of the receive, and then
invoking the receive
This rule helps us avoid a global barrier that would otherwise occur
in trying to determine which message to accept at R.
For instance, consider the simulation of the DP fragment
in Example 1 in the preceding section.
Assume that the corresponding MPSIM program is to be executed on
a single processor. The simulation will proceed as follows:
- Simulate the local block ending at statement s1 by
using direct execution. Assume that the simulation time at statement
s1 for process
in 
is 
.
- Simulate the send in statement s1 as follows: the message sent
at s1 is timestamped with
;
is computed by the simulator to model the transmission
time for this message sent by process 
in 8.
- The receive event in statement s2 is simulated as
follows: on receiving the message, update local simulation
time (for process
) as follows:
In 8, if the message arrives at s2 prior to the execution of
the receive by 
, then 
would be greater than
in 
. In contrast, if in 8 the process
had to wait at statement s2 for the message to arrive,
then in 
would be less than 
.
- The local block following the receive statement is again simulated
using direct execution.
In other words, in the compiled MP program, each process 'knows'
that exactly one message will be received at each receive statement.
Thus in 
, for k>1, each 
can simulate the receive
event at statement s2 as soon as the message is received.
Clearly parallel execution of the simulation will not incur
additional synchronization overhead compared to the sequential
execution and hence has significant potential for performance
improvements.
Next: Experiments
Up: Simulation Methodology
Previous: Simulation Methodology
Andy Kahn
Wed Jun 25 20:28:02 PDT 1997