Parallelizing an algorithm with many exit points?

[RobP]

I'm faced with parallelizing an algorithm which in its serial implementation examines the six faces of a cube of array locations within a much larger three dimensional array. (That is, select an array element, and then define a cube or cuboid around that element 'n' elements distant in x, y, and z, bounded by the bounds of the array.

Each work unit looks something like this within the subroutine:

do n1=nlo,nhi
  do o1=olo,ohi          
    if (somecondition(n1,o1) .eq. .TRUE.) then
       retval =.TRUE.
       RETURN
    endif    
  end do 
end do 

There are six work units like this in the total algorithm, one for each face of the cube within the array, where the 'lo' and 'hi' values generally range between 10 and 300. In this serial implementation, execution terminates as soon as retval becomes True.

What I think would be best would be to schedule six or more threads of execution, round-robin if there aren't that many CPU cores, ideally with the loops executing in parallel, with the goal the same as the serial algorithm:somecondition()becomesTrue, execution among all the threads must immediately stop and a value ofTrueset in a shared location.

What techniques exist in the Fortran compiler or a compatible library to facilitate parallelizing tasks like this? Obviously, I need a master thread which waits on a semaphore or some other messaging mechanism, or the completion of the worker threads, so there is a need for nesting and signaling, but my experience with OpenMP is introductory at this point.

Are there message passing mechanisms in OpenMP? Other approaches within Fortran?

[TimP]

Perhaps the typical OpenMP treatment for linear search for the location of maximum value may illustrate some of your points:

[bash] max= aa(1,1) xindex=1 yindex=1 !$omp parallel do private(ml) if(n>103) do j=1,n ml= maxloc(aa(:n,j),dim=1) !$omp critical if(aa(ml,j)>max .or. aa(ml,j)==max .and. j
First, you need private specifications for values set by various threads.
Next, to avoid wasting time of multiple threads on small problems,
use the if clause.
Your inner loop could terminate with an EXIT, but individual threads can't jump out of a parallel do; they will wait for the others to
complete, unless you add a NOWAIT clause.
In this example, the inner "loop" is contained in the maxloc intrinsic.
You probably need a critical region for combining results which may come from various threads, but you should keep that critical in the
outer parallel do loop so as to permit each thread to run the inner loops independently.

In principle, with a full implementation of OpenMP 2.5, a search function such as maxloc, or one you have written yourself, could be
parallelized by omp workshare, but in practice this hasn't become a feasible alternative.
omp task would allow you to give independent tasks to multiple threads.[/bash]