6.6. NETWORK FUNCTIONS

6.5. SYNCHRONIZATION OF PROCESSES

We mentioned earlier that an mpC parallel program is a set of parallel processes synchronizing their work and transferring data by message passing. The small subset of the mpC language, as was introduced, allows the programmer to specify the number of processes involved in the parallel computations and to distribute the computations among the processes. In principle, this subset of mpC is sufficient for synchronization of the processes during execution of the parallel program.

The basic synchronization mechanism for parallel processes interacting via message passing is a barrier. A barrier is a section of the parallel program where processes synchronizing their work wait for each other. The processes that do the synchronizing may leave the barrier and resume their computations only after all processes have entered this section. If for some reason one of the processes does not enter the barrier, all other processes will “hang” in this section of the program, and the program itself will never terminate normally.

Some barriers in the mpC applications are implicit. They are generated by the mpC compiler. However, mpC programmers can explicitly put barriers in their applications.

Consider, for example, the first program in Section 6.3 that outputs to the user’s terminal different messages from abstract processors with even and odd coordinates. This program does not define an order in which messages from different abstract processors of mynet appear on the user’s terminal. The order is not defined even under the assumption that a call to MPC_Printf is synchronous and thus can complete successfully only if the corresponding message has appeared on the user’s terminal. However, messages directed to the host-computer may not arrive in the same order as parallel processes calling function MPC_Printf have sent them.

Let us slightly modify this program to guarantee that if a call to MPC_Printf is synchronous, then messages from abstract processors with odd coordinates come to the user’s terminal only after messages from abstract processors with even coordinates. The modified mpC program is as follows:

#include <mpc.h> #define N 5 int [*]main() {    net SimpleNet(N) mynet;    int [mynet]my_coordinate;    my_coordinate = I coordof mynet;    if(my_coordinate%2==0)       [mynet]MPC_Printf("Hello, even world! My coordinate is %d.\n",                   my_coordinate);    Barrier:    {       int [host]bs[N], [mynet]b=1;       bs[]=b;       b=bs[];    }    if(my_coordinate%2==1)       [mynet]MPC_Printf("Hello, odd world! My coordinate is %d.\n",                   my_coordinate); }

To achive this result, a barrier section is inserted between calls to MPC_Printf made by the abstract processors of network mynet with even and odd coordinates.

The barrier section has the form of a block labeled Barrier. This block defines array bs located on the virtual host-process and variable b distributed over the network mynet. The number of elements in array bs is equal to the number of abstract processors in network mynet.

Assignment

bs[] = b

is evaluated by all abstract processors of network mynet as follows: Processor with coordinate I=i sends the value of its projection of variable b to the abstract host-processor, where this value is assigned to bs[i] (i=0,...,_N-1). Assignment

b = bs[]

is also evaluated by all abstract processors of network mynet. The host-processor sends the value of bs[i] to abstract processor with coordinate I=i, where this value is assigned to b (i=0,...,N-1).

Assume that the abstract host-processor has not entered the block. In that case no other abstract processor of network mynet can complete the second assignment and leave the block, because it must receive a value from the host-processor in order to complete the operation.

Assume now that some abstract processor of network mynet different from the host-processor has not entered the block. Here the host-processor cannot complete the first assignment because it must receive a value from this abstract processor in order to complete this operation.

Thus no abstract processor of mynet can leave the block until all processors of this network enter it. This shows that the barrier block is nothing more than a means of synchronizing the abstract processors of network mynet.

The mpC language does not specify whether a call to MPC_Printf is synchronous or not. If it is asynchronous, then the barrier cannot guarantee that messages from even abstract processors appear first on the user’s terminal. In that case it can only guarantee that messages from even processors start the race first, but it cannot guarantee that they finish first. In general, the properties of communication operations in mpC are the same as those in MPI.

The next mpC program implements explicit barrier synchronization in a simpler and more concise way:

#include <mpc.h> #define N 5 int [*]main() {    net SimpleNet(N) mynet;    int [mynet]my_coordinate;    my_coordinate = I coordof mynet;    if(my_coordinate%2==0)       [mynet]MPC_Printf("Hello, even world! My coordinate is %d.\n",                   my_coordinate);    Barrier:    {       int [mynet]b=1;       b[+];    }       if(my_coordinate%2==1)       [mynet]MPC_Printf("Hello, odd world! My coordinate is %d.\n",                   my_coordinate); }

The efficiency of this barrier section could hardly be made worse. The most obvious implementation of operator [+] only differs from the barrier in the preceding program by an additional summation on the host-processor. The execution time of the summation is too short compared to the time of data transfer.

Actually mpC programmers do not need to invent different ways to implement barriers. The mpC language provides two library functions that efficiently implement the barrier synchronization for the operating environment of the parallel program. First, the basic function MPC_Global_barrier synchronizes all processes of the parallel program. Its declaration is in header mpc.h and is stated as follows:

 int [*]MPC_Global_barrier(void);.

Next the program demonstrates the use of this function:

#include <mpc.h> #define N 5 int [*]main() {    net SimpleNet(N) mynet;    int [mynet]my_coordinate;    my_coordinate = I coordof mynet;    if(my_coordinate%2==0)       [mynet]MPC_Printf("Hello, even world! My coordinate is %d.\n",                   my_coordinate);    MPC_Global_barrier();    if(my_coordinate%2==1)       [mynet]MPC_Printf("Hello, odd world! My coordinate is %d.\n",                   my_coordinate); }

Unlike the two previous programs, all processes of this program, and not only those implementing network mynet, participate in the barrier synchronization. Naturally this implies a greater number of messages transferring during the execution of the barrier and hence some deceleration of the process.