Re: [mpich-discuss] first exit problems

8 Jul 2013

      So in a ring termination approach, would it look like:

/* On process id n*/
while (!search_complete){

       /*Check if a message has been received from process n-1*/
       MPI_Iprobe(...,&global_exit_flag,...);

       /*If no one else finished, continue the algorithm */
       if(!global_exit_flag){
               /* Step algorithm */
               local_exit_flag = exit_test(...);	
       }

	/*If a message was received to terminate, or an exit is found, alert the neighbors */
	if(global_exit_flag || local_exit_flag){
		/* If an exit is found somewhere, tell n+1 to stop working */
		MPI_ISend(...);

		/* If an exit has been found, a message has been received from process n-1 */
		MPI_Recv(...);

		/* Loop is only exited on each process after it has sent to n+1 and received from n-1
		search_complete = 1;
	}
}

/* Sort out any tie breaking down here and reduce as needed*/

Is that an appropriate use of blocked/non-blocked communication?

-gideon

On Jul 8, 2013, at 12:22 PM, [email protected] wrote:
...
Date: Mon, 8 Jul 2013 12:05:48 -0500
From: Jeff Hammond <[email protected]>
To: [email protected]
Subject: Re: [mpich-discuss] first exit problems
Message-ID:
  <CAGKz=uKSbXpNkUU3H9FgmbCOAk_G5roMO-wy9vx1bLukkY62=Q@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Your global exit is going to end up being collective, right?  In that
case, you can break ties manually.  I don't think you need a
master-worker model either.  Just setup a ring and signal termination
to the right neighbor.  Everyone will stop after whatever local step
they were in before polling and then you do e.g. a Gather and have the
root sort out which was the true first passage, in the event that more
than one process found a passage during that iteration.
Jeff
On Mon, Jul 8, 2013 at 11:02 AM, Gideon Simpson
<[email protected]> wrote:
...
Hi, I was wondering if someone had a good MPI solution to the following first passage problem. Suppose I have N workers, each using a Monte Carlo method to solve a problem.  An example would be if I wanted to find the exit distribution in time and space of a stochastic differential equation from some compact set in space.
Assuming that each worker is properly receiving an independent stream of pseudo random numbers, and they are computing asynchronously, when one worker finds a solution, he must notify the others that they can cease working, and the program can continue.  I have in mind something like:
while (!local_exit & !global_exit){
/*Check if a message has been received*/
       MPI_Iprobe(...,&global_exit,...);
/*If no one else finished, continue the algorithm */
       if(!global_exit){
               /* Step algorithm */
               local_exit = exit_test(...);
       }
}
if(local_exit){
/* Alert all other workers */
       for(...){
               MPI_Isend(...);
       }
}
else{
/* Receive the message that was sent from the other worker */
MPI_Recv(...);
}
However, I believe this leads to a race condition because if processor 0 finds and exit, processor 1 might also find one before processor 0 has a chance to do an MPI_Isend() to 1. Assuming that, for the moment, I am not too concerned about tie breaking, I would really like to find a robust solution to this problem, as I have a lot of first exit/first passage type problems that could be solved asynchronously.
Thanks for any suggestions,
-gideon
_______________________________________________
discuss mailing list     [email protected]
To manage subscription options or unsubscribe:
https://lists.mpich.org/mailman/listinfo/discuss