Example 6.6 showed how FM constructs can be used to implement parallel and concurrent composition. The basic ideas are straightforward. A process (task) is defined for each component of a multicomponent program. These processes are then composed using a process block, with channels and/or mergers connecting ports in the different components. Mapping constructs control resource allocation and hence determine whether program components execute on the same or different processors.
In this section, we discuss the techniques used to implement sequential composition in FM programs. Recall that in sequential composition, different program components execute in sequence on all processors (Section 4.2.2). These program components may themselves communicate and synchronize, but they cannot create new tasks. Hence, each process executes the same program, and the entire computation moves sequentially from one parallel operation to the next. This is the SPMD programming model discussed in Section 1.3.2.
An FM implementation of an SPMD program comprises two components: initialization and execution. The initialization component creates the SPMD process structure and the communication structures (channels and mergers) required by the program components called in the sequential composition. The initialization typically comprises some channel and merger creation code followed by a process do-loop that creates one process per processor, with the appropriate ports passed as arguments.
The execution component implements the program executed by each process created by the process do-loop. This program comprises a sequence of calls to the program components involved in the sequential composition. These components can perform internal communication using the communication structure established during the setup phase of the computation.
The important point to understand about this structure is that once appropriate communication structures have been defined in the initialization phase, sequential composition can be used directly in the main body of the program, without any special constructs.
We consider the SPMD finite difference computation used to illustrate sequential composition in Section 4.2.2. This computation is structured as a sequence of calls to a finite difference routine that performs nearest-neighbor communication and a reduction routine used to detect termination; the latter routine performs global communication. The basic logic executed by each process in this computation is as follows, where localgrid is the local component of the grid data structure.
while(.not. done) do
call finite_difference(localgrid, localmax)
call global_maximum(localmax, globmax)
if(globmax .lt. threshold) done = .true.
Programs 6.10 and 6.11 implement the initialization and execution components of an FM implementation of this program. Because the program components invoked in the sequential composition perform both nearest-neighbor and hypercube communication, the initialization code first creates channels implementing these two communication structures. (The function xor is used as in Algorithm 11.1.) Then, a process do-loop creates P instances of the node process, passing each instance the appropriate ports.
The execution code comprises the process node, which calls first the procedure finite_difference and then the procedure global_maximum. These procedures use the ports passed as arguments to perform internal communication.
The various port variables passed as arguments in the execution component make for a rather clumsy program. The program can be made tidier by storing the ports in PROCESS COMMON with a series of MOVEPORT calls prior to calling user code. Each process can then execute the simpler code presented at the beginning of this example.
The initialization code in Program 6.10 defined a separate communication structure for each component in the sequential composition. In this example, we present an alternative approach in which the initialization component of an SPMD program creates a single, general-purpose communication structure that can be used to perform any communication. In effect, we implement a message-passing library that provides similar functionality to the MPI library described in Chapter 8. We also use this example to show how port variables can be stored in PROCESS COMMON to simplify program interfaces.
Program 6.12 is a skeleton message-passing library that implements just simple send and receive functions. The main program first creates P mergers to implement a fully connected network, and then creates P node processes, passing each a single inport and P outports. The node process stashes the inport and outports in PROCESS COMMON and then calls the subroutine compute, which performs the actual computation. The PROCESS COMMON is defined as follows (file mp_stashed.com).
C File "mp_stashed.com"
PROCESS COMMON /stashed/ stashed_inp, stashed_outp
INPORT (integer n, character x(n)) stashed_inp
OUTPORT (integer n, character x(n)) stashed_outp(P)
This initialization code makes it possible for the rest of the program to call mp_send and mp_receive routines to send and receive messages to and from other processes.
© Copyright 1995 by Ian Foster