Parallelizing the Numerical Solution of the Diffusion Equation

In our problem the easiest way to allocate grid points among the processese is to decompose along the x-axis:

At each time step, each process computes only it's portion of the grid.

However, when a process computes a grid point that lies adjacent to the edge of its portion, one of the stencil points is actually owned by the neighboring process. This point is referred to as the process' "ghost points".

A process never computes the ghost points by itself; these points are computed during the prior time step by neighboring processes.

To compute the stencil at any given time step, each processor must receive values (of the grid point) at its ghost points from its neighbors at the conclusion of the previous time step. Thus, processes must share their ghost points between themselves after each time step, i.e. interprocessor communication is required at the conclusion of each time step.

A process' ghost points are u[0][j], which are received from its left neighbor's u[mynni][j], and u[mynni + 1][j], which are received from its right neighbor's u[1][j], for all j.

We will use the MPI_Send () and MPI_Recv () functions to transfer ghost points between the processors. These are blocking functions; they do not return until the communication is complete (in most installations of MPI). So we will need to make sure that a deadlock situation does not arise.

A deadlock arises in a perfectly symmetric situation when, for instance, two processes are sending to each other, and each process' call to MPI_Send () does not return, something which needs to happen for those processes to call their respective MPI_Recv () calls!

• It's better to program asymmetrically, whereby one process first calls MPI_Send () and its respective receiving process calls MPI_Recv ().

To prevent deadlocks we'll choose odd-numbered processes to do MPI_Send () first and MPI_Recv () second, while even-numbered processes will do MPI_Recv () first and MPI_Send () second.