Nearest Neighbor Send and Receive
One of the most common patterns in MPI programming is nearest-neighbor exchanges. In this case, a process sends to its neighbor and receives from its neighbor. The definition of “neighbor” may depend on the topology of the layout of ranks. For a simple one-dimensional organization the neighbor to the left is rank- and the neighbor to the right is rank+1.
Any blocking point-to-point communications can potentially deadlock, but we must be especially careful with nearest-neighbor communications. Each process must be in an appropriate state when a message is sent to it. How do we accomplish this?
As an example, let us consider an exchange in which each process sends its rank to its neighbor and receives the neighbor’s rank. Even-number processes send to their right and odd-numbered processes send to their left.
Deadlock
We might first think all processes should be in the Receive state, then Send the message.
Examples
Contents of exchange_deadlock.cxxC++
Download exchange_deadlock.cxx file
#include <iostream>
#include <mpi.h>
using namespace std;
int main(int argc, char **argv) {
int rank, nprocs, message, neighbor;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &nprocs);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (nprocs < 2) {
cout<<"This program works only for at least two processes\n";
MPI_Finalize();
return 1;
}
else if (nprocs%2 != 0) {
cout<<"This program works only for an even number of processes\n";
MPI_Finalize();
return 2;
}
if (rank%2==0) {
neighbor = rank+1;
}
else {
neighbor = rank-1;
}
MPI_Recv(&message, 1, MPI_INT, neighbor, 0, MPI_COMM_WORLD, &status);
MPI_Send(&rank, 1, MPI_INT, neighbor, 0, MPI_COMM_WORLD);
cout<<rank<<" "<<message<<endl;
MPI_Finalize();
return 0;
}
Fortran
Contents of exchange_deadlock.f90
program exchange
use mpi
implicit none
integer :: rank, nprocs, neighbor, ierr
integer :: status(MPI_STATUS_SIZE)
integer :: message
call MPI_Init(ierr)
call MPI_Comm_rank(MPI_COMM_WORLD, rank, ierr)
call MPI_Comm_size(MPI_COMM_WORLD, nprocs, ierr)
if (nprocs < 2) then
write(6,*) "This program works only for at least two processes"
call MPI_Finalize(ierr)
stop
else if ( mod(nprocs,2) /= 0 ) then
write(6,*) "This program works only for an even number of processes"
call MPI_Finalize(ierr)
stop
end if
if ( mod(rank,2) == 0) then
neighbor = rank+1
else
neighbor = rank-1
end if
call MPI_Recv(message, 1, MPI_INTEGER, neighbor, 0, MPI_COMM_WORLD, status, ierr)
call MPI_Send(rank,1, MPI_INTEGER, neighbor, 0, MPI_COMM_WORLD, ierr)
write(*,*) rank, message
call MPI_Finalize(ierr)
end program
Python
Contents of exchange_deadlock.py
import sys
import numpy as np
from mpi4py import MPI
comm=MPI.COMM_WORLD
nprocs=comm.Get_size()
rank=comm.Get_rank()
if nprocs<2:
print("This program works only for at least two processes.")
sys.exit()
elif nprocs%2!=0:
print("This program works only for an even number of processes.")
sys.exit()
message=np.zeros(1,dtype='int')
rank_val=rank*np.ones(1,dtype='int')
if rank%2==0:
neighbor=rank+1
else:
neighbor=rank-1
comm.Recv([message,MPI.INT],source=neighbor)
comm.Send([rank_val,MPI.INT],dest=neighbor)
print(rank,message)
However, this pattern is guaranteed to deadlock because the MPI_Recv is blocking. It will wait indefinitely for a message, so the process never has a chance to send anything.
Unsafe
Perhaps we can swap the MPI_Send and MPI_Recv. The Send will pack up the message into the buffer and return. The process then proceeds to Receive, which accepts the message.
Contents of exchange_unsafe.cxxC++
Download exchange_unsafe.cxx file
#include <iostream>
#include <mpi.h>
using namespace std;
int main(int argc, char **argv) {
int rank, nprocs, message, neighbor;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &nprocs);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (nprocs < 2) {
cout<<"This program works only for at least two processes\n";
MPI_Finalize();
return 1;
}
else if (nprocs%2 != 0) {
cout<<"This program works only for an even number of processes\n";
MPI_Finalize();
return 2;
}
if (rank%2==0) {
neighbor = rank+1;
}
else {
neighbor = rank-1;
}
MPI_Send(&rank, 1, MPI_INT, neighbor, 0, MPI_COMM_WORLD);
MPI_Recv(&message, 1, MPI_INT, neighbor, 0, MPI_COMM_WORLD, &status);
cout<<rank<<" "<<message<<endl;
MPI_Finalize();
return 0;
}
Fortran
Contents of exchange_unsafe.f90
program exchange
use mpi
implicit none
integer :: rank, nprocs, neighbor, ierr
integer :: status(MPI_STATUS_SIZE)
integer :: message
call MPI_Init(ierr)
call MPI_Comm_rank(MPI_COMM_WORLD, rank, ierr)
call MPI_Comm_size(MPI_COMM_WORLD, nprocs, ierr)
if (nprocs < 2) then
write(6,*) "This program works only for at least two processes"
call MPI_Finalize(ierr)
stop
else if ( mod(nprocs,2) /= 0 ) then
write(6,*) "This program works only for an even number of processes"
call MPI_Finalize(ierr)
stop
end if
if ( mod(rank,2) == 0) then
neighbor = rank+1
else
neighbor = rank-1
end if
call MPI_Send(rank,1, MPI_INTEGER, neighbor, 0, MPI_COMM_WORLD, ierr)
call MPI_Recv(message, 1, MPI_INTEGER, neighbor, 0, MPI_COMM_WORLD, status, ierr)
write(*,*) rank, message
call MPI_Finalize(ierr)
end program
Python
Contents of exchange_unsafe.py
import sys
import numpy as np
from mpi4py import MPI
comm=MPI.COMM_WORLD
nprocs=comm.Get_size()
rank=comm.Get_rank()
if nprocs<2:
print("This program works only for at least two processes.")
sys.exit()
elif nprocs%2!=0:
print("This program works only for an even number of processes.")
sys.exit()
message=np.zeros(1,dtype='int')
rank_val=rank*np.ones(1,dtype='int')
if rank%2==0:
neighbor=rank+1
else:
neighbor=rank-1
comm.Send([rank_val,MPI.INT],dest=neighbor)
comm.Recv([message,MPI.INT],source=neighbor)
print(rank,message)
This pattern is unsafe because the buffer may not be able to contain all the messages to be sent. On most modern systems, however, it will very often work, especially with short messages. For that reason it is a good idea to use built-in MPI tools as much as possible, such as MPI_Sendrecv.
Safe
For a safe exchange, we split the ranks by even and odd. One set sends first, while the other is waiting to receive; the reverse is true for the other set. Note that we have restricted the example to run only on an even number of ranks to avoid the need for special handling of the rightmost process. In general we would have to add conditionals for that case, but we are keeping the example as simple as possible.
Contents of exchange_safe.cxxC++
Download exchange_safe.cxx file
#include <iostream>
#include <mpi.h>
using namespace std;
int main(int argc, char **argv) {
int rank, nprocs, message, neighbor;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &nprocs);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (nprocs < 2) {
cout<<"This program works only for at least two processes\n";
MPI_Finalize();
return 1;
}
else if (nprocs%2 != 0) {
cout<<"This program works only for an even number of processes\n";
MPI_Finalize();
return 2;
}
if (rank%2==0) {
neighbor = rank+1;
}
else {
neighbor = rank-1;
}
if (rank%2==0) {
MPI_Recv(&message, 1, MPI_INT, neighbor, 0, MPI_COMM_WORLD, &status);
MPI_Send(&rank, 1, MPI_INT, neighbor, 0, MPI_COMM_WORLD);
}
else {
MPI_Send(&rank, 1, MPI_INT, neighbor, 0, MPI_COMM_WORLD);
MPI_Recv(&message, 1, MPI_INT, neighbor, 0, MPI_COMM_WORLD, &status);
}
cout<<rank<<" "<<message<<endl;
MPI_Finalize();
return 0;
}
Fortran
Contents of exchange_safe.f90
program exchange
use mpi
implicit none
integer :: rank, nprocs, neighbor, ierr
integer :: status(MPI_STATUS_SIZE)
integer :: message
call MPI_Init(ierr)
call MPI_Comm_rank(MPI_COMM_WORLD, rank, ierr)
call MPI_Comm_size(MPI_COMM_WORLD, nprocs, ierr)
if (nprocs < 2) then
write(6,*) "This program works only for at least two processes"
call MPI_Finalize(ierr)
stop
else if ( mod(nprocs,2) /= 0 ) then
write(6,*) "This program works only for an even number of processes"
call MPI_Finalize(ierr)
stop
end if
if ( mod(rank,2)==0 ) then
neighbor = rank+1
else
neighbor = rank-1
end if
if ( mod(rank,2)==0 ) then
call MPI_Recv(message, 1, MPI_INTEGER, neighbor, 0, MPI_COMM_WORLD, status, ierr)
call MPI_Send(rank,1, MPI_INTEGER, neighbor, 0, MPI_COMM_WORLD, ierr)
else
call MPI_Send(rank,1, MPI_INTEGER, neighbor, 0, MPI_COMM_WORLD, ierr)
call MPI_Recv(message, 1, MPI_INTEGER, neighbor, 0, MPI_COMM_WORLD, status, ierr)
endif
write(*,*) rank, message
call MPI_Finalize(ierr)
end program
Python
Contents of exchange_safe.py
import sys
import numpy as np
from mpi4py import MPI
comm=MPI.COMM_WORLD
nprocs=comm.Get_size()
rank=comm.Get_rank()
if nprocs<2:
print("This program works only for at least two processes.")
sys.exit()
elif nprocs%2!=0:
print("This program works only for an even number of processes.")
sys.exit()
message=np.zeros(1,dtype='int')
rank_val=rank*np.ones(1,dtype='int')
if rank%2==0:
neighbor=rank+1
else:
neighbor=rank-1
if rank%2==0:
comm.Recv([message,MPI.INT],source=neighbor)
comm.Send([rank_val,MPI.INT],dest=neighbor)
else:
comm.Send([rank_val,MPI.INT],dest=neighbor)
comm.Recv([message,MPI.INT],source=neighbor)
print(rank,message)
Exercise
Download the three codes for your language and try them. The first example will have to be canceled manually.