8.1 The MPI Programming Model

  In the MPI programming model, a computation comprises one or more   processes that communicate by calling library routines to send   and receive messages to other processes. In most MPI implementations,   a fixed set of processes is created at program initialization, and one process is created per processor. However, these processes may execute different programs. Hence, the MPI programming model is sometimes referred to as multiple program multiple data (MPMD) to distinguish it from the SPMD model in which every processor   executes the same program.

Because the number of processes in an MPI computation is normally fixed,   our focus in this chapter is on the mechanisms used to communicate   data between processes. Processes can use point-to-point communication operations to send a message from one named process to another; these operations can be used to implement local and unstructured communications. A group of processes can call collective communication operations to perform commonly used   global operations such as summation and broadcast. MPI's ability to probe for messages supports asynchronous communication. Probably MPI's most important feature from a software engineering viewpoint is its support for modular programming. A mechanism called a communicator allows the MPI programmer to define modules that encapsulate internal communication structures. In the terminology used in Chapter 4, these modules can be combined by both sequential and parallel composition.

Most parallel algorithms designed using the techniques of Part I are readily implemented using MPI. Algorithms that create just one task per processor can be implemented directly, with point-to-point or collective communication routines used to meet communication requirements. Algorithms that create tasks in a dynamic fashion or that rely on the concurrent execution of several tasks on a processor must be further refined to permit an MPI implementation. For example, consider the first branch-and-bound search algorithm   developed in Section 2.7, which creates a tree of ``search'' tasks dynamically. This algorithm cannot be implemented directly in MPI; however, as discussed in Chapter 2, it can be refined to obtain an algorithm that creates a fixed set of worker processes that exchange messages representing tree nodes to be searched. The resulting SPMD algorithm can be implemented as an MPI program. Algorithms that are not easily modified in this way are better implemented using alternative technologies.