[mpich-discuss] first exit problems

[Gideon Simpson]

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, discuss-request at mpich.org wrote:

> Date: Mon, 8 Jul 2013 12:05:48 -0500
> From: Jeff Hammond <jeff.science at gmail.com>
> To: discuss at mpich.org
> Subject: Re: [mpich-discuss] first exit problems
> Message-ID:
> 	<CAGKz=uKSbXpNkUU3H9FgmbCOAk_G5roMO-wy9vx1bLukkY62=Q at 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
> <gideon.simpson at gmail.com> 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     discuss at mpich.org
>> To manage subscription options or unsubscribe:
>> https://lists.mpich.org/mailman/listinfo/discuss
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mpich.org/pipermail/discuss/attachments/20130708/b9b6280d/attachment.html>