Introduction

In the previous chapter, we showed that when data parallel programs are compiled for execution on multicomputers, they are converted into message passing programs which contain exclusively deterministic communication patterns. We exploited this property to provide fast simulation of data parallel programs. For general message passing programs, techniques to simulate non-deterministic patterns must be devised as well. In this chapter, we start afresh by adapting existing theory on parallel simulation to the specific problem of parallel simulation of message passing parallel programs. We present the conservative simulation protocol used in the simulation engine for MPI programs, whose design and implementation are described in the following chapter. The contributions of this chapter include:

• A simulation model for message passing programs that incorporates a simple analytic model of the interprocess communication protocol and interconnection network delays, and turns out to be reasonably accurate (as shown in the next chapter).
• A simulation protocol for this model that uses a conjunction of the null message protocol and the conditional event protocol, and does not need compile time target program analysis.
• Automatic incorporation of the optimizations presented in the previous chapter into the overall simulation protocol.