Why does MPI_Iprobe return false when message has definitely been sent?

Question

I want to use MPI_Iprobe to test whether a message with a given tag is already pending.

However, the behaviour of MPI_Iprobe isn't quite as I was expecting. In the example below, I send messages from multiple tasks to a single task (rank 0). Then on rank 0, I wait several seconds to allow plenty of time for the MPI_Isends to complete. Then when I run MPI_Iprobe it returns with flag false. If I repeat after a (blocking) MPI_Probe, then it returns true.

#include "mpi.h"
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
  int rank;
  int numprocs;
  int tag;
  int receive_tag;
  int flag=0;
  int number;
  int recv_number=0;

  MPI_Request request;
  MPI_Status status;

  MPI_Init(&argc,&argv);
  MPI_Comm_rank(MPI_COMM_WORLD,&rank);
  MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

  // rank 0 receives messages, all others send messages
  if (rank > 0 ) {
    number = rank;
    tag = rank;
    MPI_Isend(&number, 1, MPI_INT, 0, tag, MPI_COMM_WORLD,&request); // send to rank 0
    printf("Sending tag : %d \n",tag);
   } 
   else if (rank == 0) {

   sleep(5); // [seconds] allow plenty of time for all sends from other tasks to complete

   receive_tag = 3; // just try and receive a single message from task 1

   MPI_Iprobe(MPI_ANY_SOURCE,receive_tag,MPI_COMM_WORLD,&flag,&status);
   printf("After MPI_Iprobe, flag = %d \n",flag);

   MPI_Probe(MPI_ANY_SOURCE,receive_tag,MPI_COMM_WORLD,&status);
   printf("After MPI_Probe, found message with tag : %d \n",receive_tag);

   MPI_Iprobe(MPI_ANY_SOURCE,receive_tag,MPI_COMM_WORLD,&flag,&status);
   printf("After second MPI_Iprobe, flag = %d \n",flag);

   // receive all the messages
   for (int i=1;i<numprocs;i++){    
     MPI_Recv(&recv_number, 1, MPI_INT, MPI_ANY_SOURCE, i, MPI_COMM_WORLD,&status);
     printf("Received : %d \n",recv_number);
   }

 }
 MPI_Finalize();
}

Gives this output:

Sending tag : 4 
Sending tag : 3 
Sending tag : 2 
Sending tag : 5 
Sending tag : 1 
After MPI_Iprobe, flag = 0 
After MPI_Probe, found message with tag : 3 
After second MPI_Iprobe, flag = 1 
Received : 1 
Received : 2 
Received : 3 
Received : 4 
Received : 5 

Why does mpi_iprobe return 'false' the first time?

Any help would be much appreciated!

---

EDIT: after the answer by Hristo Iliev I now have the following code:

#include "mpi.h"
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
  int rank;
  int numprocs;
  int tag;
  int receive_tag;
  int flag=0;
  int number;
  int recv_number=0;

  MPI_Request request;
  MPI_Status status;

  MPI_Init(&argc,&argv);
  MPI_Comm_rank(MPI_COMM_WORLD,&rank);
  MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

  // rank 0 receives messages, all others send messages
  if (rank > 0 ) {
    number = rank;
    tag = rank;

    MPI_Isend(&number, 1, MPI_INT, 0, tag, MPI_COMM_WORLD,&request); // send to rank 0
    printf("Sending tag : %d \n",tag);

    // do stuff

    MPI_Wait(&request,&status);
    printf("Sent tag : %d \n",tag);

   }
    else if (rank == 0) {

    sleep(5); // [seconds] allow plenty of time for all sends from other tasks to complete

    receive_tag = 3; // just try and receive a single message from task 1

    MPI_Iprobe(MPI_ANY_SOURCE,receive_tag,MPI_COMM_WORLD,&flag,&status);
    printf("After MPI_Iprobe, flag = %d \n",flag);

    MPI_Probe(MPI_ANY_SOURCE,receive_tag,MPI_COMM_WORLD,&status);
    printf("After MPI_Probe, found message with tag : %d \n",receive_tag);

    MPI_Iprobe(MPI_ANY_SOURCE,receive_tag,MPI_COMM_WORLD,&flag,&status);
    printf("After second MPI_Iprobe, flag = %d \n",flag);

    // receive all the other messages
    for (int i=1;i<numprocs;i++){   
       MPI_Recv(&recv_number, 1, MPI_INT, MPI_ANY_SOURCE, i, MPI_COMM_WORLD,&status);
    }

 }
 MPI_Finalize();
}

Which gives the following output:

Sending tag : 5 
Sending tag : 2 
Sending tag : 1 
Sending tag : 4 
Sending tag : 3 
Sent tag : 2 
Sent tag : 1 
Sent tag : 5 
Sent tag : 4 
Sent tag : 3 
After MPI_Iprobe, flag = 0 
After MPI_Probe, found message with tag : 3 
After second MPI_Iprobe, flag = 1 

Answer 1

You are using MPI_Isend in order to send the messages. MPI_Isend initiates an asynchronous (background) data transfer. The actual data transfer might not happen unless one of the MPI_Wait* or MPI_Test* calls has been made on the request. Some MPI implementations have (or can be configured so) background progression threads that will progress the send operation even if no wait/test has been done on the request, but one should not rely on such behaviour.

Simply replace MPI_Isend with MPI_Send or add MPI_Wait(&request); after the former (mind though that MPI_Isend + MPI_Wait immediately after is equivalent to MPI_Send).

MPI_Iprobe is intended to be used in busy waits, i.e.:

while (condition)
{
   MPI_Iprobe(...,&flag,...);
   if (flag)
   {
      MPI_Recv(...);
      ...
   }
   // Do something, e.g. background tasks
}

Real-life message transfers in actual MPI implementations are quite complicated things. Operations are usually split in multiple parts that are then queued. Executing that parts is called progression and it is done at various points in the MPI library, for example when a communication call is made or in background if the library implements a background progression thread. Calling MPI_Iprobe certainly does progress things but there is no guarantee that a single call will suffice. The MPI standard states:

The MPI implementation of MPI_PROBE and MPI_IPROBE needs to guarantee progress: if a call to MPI_PROBE has been issued by a process, and a send that matches the probe has been initiated by some process, then the call to MPI_PROBE will return, unless the message is received by another concurrent receive operation (that is executed by another thread at the probing process). Similarly, if a process busy waits with MPI_IPROBE and a matching message has been issued, then the call to MPI_IPROBE will eventually return flag = true unless the message is received by another concurrent receive operation.

Note the use of eventually. How progression is being done is very implementation-specific. Compare the following output from 5 consecutive calls to MPI_Iprobe (your original code + a tight loop):

Open MPI 1.6.5 w/o progression thread:

# Run 1
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1

# Run 2
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1

# Run 3
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 0

No consistency between several executions of the same MPI program is observed and in the 3rd run the flag is still false after 5 invocations of MPI_Iprobe.

Intel MPI 4.1.2:

# Run 1
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1

# Run 2
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1

# Run 3
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 0
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1
After MPI_Iprobe, flag = 1

Obviously Intel MPI progresses things differently than Open MPI.

The difference between the two implementations can be explained by the fact that MPI_Iprobe is supposed to be a tiny probe and therefore it should take as less time as possible. Progression on the other hand takes time and in single-threaded MPI implementations the only point in time where progression is possible is the call to MPI_Iprobe (in that particular case). Therefore the MPI implementer has to decide how much is actually progressed by each call to MPI_Iprobe and strike a balance between the amount of work done by the call and the time it takes.

With MPI_Probe things are different. It is a blocking call and therefore it is able to constantly progresses until a matching message (and more specifically its envelope) appears.