B424 Introduction to message passing 1

Dana Vrajitoru
B424 Parallel and Distributed Programming

Message Passing Models

SIMD (MPI) or MIMD (PVM) models.
The memory is distributed, each process has its own memory that no other process has access to.
The information is exchanged by messages.
In general we have n processes numbered from 0 to n-1.
The code is written for a particular process (current process) for which we can find out the identity.

Pseudocode for message passing:
Send(data, destination_process);
Sends the value of the variable or array data to the specified process.

Receive(data, source_process);
Receives a value into the variable or array data from the specified source process.

Broadcast(data, source_process);
The specified process sends the data with all of the other processes. Each process must call this function with a variable of the same type and size as the first argument.

Barrier();
When a process encounters this function call, it must wait until all of the other processes have reached a call of the same function. After that they can all continue with the execution of the program.

In general, the pseudocode represents the function that will be executed by each process.
We may distinguish between the master/slave functions.

General purpose main function.

int main()
{
  int my_id;
  ... // Initialize and get process id.
  if (my_id == 0)
    Master();
  else
    Slave();
  ... // Some final statements.
  return 0;
}

Send-Receive. For each process i1 calling the function

Send(data1, i2);

the process i2 must call the function

Receive(data2, i1);

Unless specified otherwise, these are blocking send and receive: each process must wait until the matching call has been issued by the second process for the Send/Receive calls to be finished.

In these function calls, data1 and data2 must have the same type and size. The combination of the two function calls has the effect that

the process that has made the first call must wait for the second one to make the matching call in order to continue the execution of the program;
when both calls have been executed, the variable data2 will contain the same value as the variable data1;
in a shared memory mode, we could write instead

data2 = data1;

If a Send or Receive have been called with no matching call, the process cannot finish its execution.
Practically, Send may be blocking, or it may be buffered sometimes, which can allow the process to complete the call even though the message has not been received yet. The receive is simply blocking.

First example: computing the integral

Master function (id = 0)

Slave function (id = 1 to n-1)

Input(a);
Broadcast(a, 0);
Input(b);
Broadcast(b, 0);
sum_i = Integral(a,
a+(b-a)/n,
F);
integral = sum_i;
for (i=0; i<n; i++) {
Receive(sum_i, i);
integral = integral + sum_i;
}
Output(integral);

Broadcast(a, 0);

Broadcast(b, 0);
sum_i = Integral(a+id*(b-a)/n,
a+(id+1)*(b-a)/n,
F);

Send(sum_i, 0);

Second example: the IVP solver. s0 and s, are real arrays of size n, which is both the number of dimensions of the curve s and the number of processes. We have a different function to compute the derivative of the curve for each dimension.

if (id == 0)
Read(s0); // master
Broadcast(s0, 0);
Copy(s0, s);
for (t=0.0; t<c; t=t+delta_t) {
sprime=Fid(s);
s[id] = s[id]+sprime* delta_t;
for (i=0; i<n; i++)
Broadcast(s[i], i);
if (id == 0)
Write(s); // master
}