Open MPI logo

Open MPI User's Mailing List Archives

  |   Home   |   Support   |   FAQ   |  

This web mail archive is frozen.

This page is part of a frozen web archive of this mailing list.

You can still navigate around this archive, but know that no new mails have been added to it since July of 2016.

Click here to be taken to the new web archives of this list; it includes all the mails that are in this frozen archive plus all new mails that have been sent to the list since it was migrated to the new archives.

Subject: Re: [OMPI users] Collective operations and synchronization
From: Shaun Jackman (sjackman_at_[hidden])
Date: 2009-03-23 19:36:41


Hi Ralph,

Thanks for your response. My problem is removing all leaf nodes from a
directed graph, which is distributed among a number of processes. Each
process iterates over its portion of the graph, and if a node is a
leaf (indegree(n) == 0 || outdegree(n) == 0), it removes the node
(which is a local operation) and notifies each of its neighbours
(using MPI_Ibsend) to remove any edges incident to the removed node.
If that node becomes a leaf, it is also removed and the process
cascades. I use the following algorithm to check if this cascade
process is complete:

loop {
MPI_Ibsend (for every edge of every leaf node)
MPI_barrier
MPI_Iprobe/MPI_Recv (until no messages pending)
MPI_Allreduce (number of nodes removed)
} until (no nodes removed by any node)

Previously, I attempted to use a single MPI_Allreduce without the
MPI_Barrier:

loop {
MPI_Iprobe/MPI_Recv (until no messages pending)
MPI_Ibsend (for every edge of every leaf node)
MPI_Allreduce (number of nodes removed)
} until (no nodes removed by any node)

This latter algorithm did not complete correctly. Now that I've
written out the algorithm in pseudo-code, it looks a little clearer.
There must be a race condition between the MPI_Iprobe and MPI_Recv. I
wonder if using MPI_Irecv would clear it up.

Cheers,
Shaun

Ralph Castain wrote:
> I think perhaps you folks are all caught up a tad too much in the
> standard and not reading the intent of someone's question... :-)
>
> I believe the original question was concerned with ensuring that all
> procs had completed MPI_Allreduce before his algorithm attempted other
> operations. As you folks know, procs can leave MPI_Allreduce at
> significantly different times. Using an MPI_Barrier after
> MPI_Allreduce would accomplish the questioner's objective.
>
> Whether or not the questioner's particular program really -needs- to
> do that is another matter - one I personally wouldn't attempt to
> answer without knowing a lot more about what that next step after
> MPI_Allreduce does.