An upper bound of loop with OpenMP

[oleglebedev]

Good day,

I am trying toparallelize my project. A question is about an upper bound of do-loop... a code below.

The global variable upper_bound may change into someMethod procedure (it changes really).

In my case I see only the first loop with the upper_bound =1 and I do not see an iteration with upper_bound =2 after exacution the someMethod subrouting which changes upper_bound to 2.

Does anybody have any idea how to make it works.

PS

In a sequence code I used a do-while loop and there was no problem. But the do-while is not comparable with the OpenMP.

PPS

Some tricks with goto from a do-loop doesn`t work with the OpenMP, too.

Best, Oleg.

[fxfortran]module m    
    
integer :: upper_bound = 1    
    
contains
!...    
    
subroutine someSub(...)    
!...    
!$OMP parallel PRIVATE(i, ...)    
!$OMP do    
  lookAtThisLoop: do i = 1, upper_bound    
    call someMethod(...)    
  end do lookAtThisLoop    
!$OMP end do    
    
!...    
!$OMP critical    
!...    
!$OMP end critical  
!...  
end subroutine someSub  
!...  
end module m  [/fxfortran]

[IanH]

The number of iterations of a do loop is evaluated once only at the beginning of execution of the do loop. Once the loop has started executing changes in the expression for the terminal parameter do not change the number of iterations.

Consider using a DO WHILE style loop that generates OpenMP tasks (!$OMP TASK). Whether this is suitable or not depends on what the someMethod procedure does - additional changes to your source code may be required. Provide more details if you want further advice.

[jimdempseyatthecove]

In addition to IanH's comments...

If upper_bound changes inside the do loop for use with the next issuance of the loop as opposed to current issue of loop, then the code as written will likely be ok. However, your description indicates you want changes to the upper_bound to affect execution of the current loop. In this case there are some nuances that require investigation.

Is the new upper_bound determined/set) at the beginning of someMethod or at the end of someMethod?

If at the end of someMethod, then it makes no sense to parallize the code (unless initial upper_bound .gt. 1).

Now let's consider the situation where some work is being performed in someMethod _after_ the decision to bump the upper bound is determined. Consider using something along the line of

upper_bound = 1
!$omp parallel
nThreads = omp_get_num_threads()
!$omp do
do while(upper_bound .gt. 0)
if(mod((upper_bound - 1), nThreads) == 0)
call someMethod(...) ! which bumps upper_bound or sets to -1
endif
end do
!$omp end do
!$omp end parallel

you may need to make upper_bound volatile depending on if someMethod gets inlined or not.

Termination being made when no next upper_bump is needed (set upper_bound to -1 as opposed to upper_bound + 1). Note, only 1 thread at a time will advance the upper_bound. Also note, this technique assumes each process time following the advancement of the upper_bound is approximately the same or at least is assured to complete in a reasonable amout of time. If this is not the case then you could stall the advancemet. To correct for this you would use an InterlockedIncriment of a shared counter by each thread to obtain the next upper_bound value that it is assigned to execute.

Jim Dempsey

[oleglebedev]

Jim, thanks for you answer.

The upper_bound does change in the someMethod calling if some conditions are kept; and upper_bound may not change. Also it can increase not only by one.

The following peace of code reproduce my situation:

[fortran]PROGRAM main
    USE  omp_lib
    IMPLICIT NONE
    integer :: i, up

up = 10
i = 1
!$OMP parallel private(i)
!$OMP do
do i = 1, up
  !!!>>{ these two lines are quasi-someMethod
    if (i==3) up = up + 1
    if (i==7) up = up + 3
  !!!}<<
  write( *, * ) 'i', i, 'up', up
end do
!$OMP end do
!$OMP end parallel

end program[/fortran]

I did not understand your code fully. I tryied to type it with a while-loop but it does not work.

error #7623: An OpenMP* parallel loop must not be a DO WHILE loop.

Best, Oleg.

[Anonymous66]

An OpenMP do loop expects the number of iterations to be set when it starts the loop. OpenMP tasks are more suited to this type of program.

If you can separate out determining whether how much "up" will change from the rest of "someMethod(...)," this could be a workable solution. Otherwise a parallel version of your program would be non-deterministic which means it may do unexpected things because the order of execution will change the results.

Below is your code with the calls to "someMethod(...)" separated out into OpenMP tasks:

[fortran]
PROGRAM main
    IMPLICIT NONE
    integer :: i, up

i = 1
up = 10

do while (i < up)
    !! these two lines need to be kept as part of the serial do while loop
    if (i==3) up = up + 1
    if (i==7) up = up + 3

    !next 3 lines allow calls to "someMethod(...)" to move to other threads
    !$OMP TASK
        someMethod(...) !does not change value of "up"
    !$OMP END TASK

    write( *, * ) 'i', i, 'up', up
    i = 1 + 1
end do

!This will cause the program to wait until all of the tasks with calls
!to "someMethod(...)" are completed
!$OMP TASKWAIT  

end program[/fortran]

[jimdempseyatthecove]

up=10 ! external to following lines

if(up .ge. 3) up = up + 1
if(up .ge. 7) up = up + 1

i=1

!$OMPparallelprivate(i)

!$OMPdo

ddoi=1,up

write(*,*)'i',i,'up',up

enddo

!$OMPenddo

!$OMPendparallel

The advance of up determination is made in advance of the loop (remember to remove the advance within the called subroutine that currently performs the advance of up).

RE: using do while with advancing upper limit

Please read response #3 relating to as if the bump up occures at the beginning of the called subroutine or at the end of the called subroutine. If at the beginning of the called subroutine, then consider using code as outlined in #3. If determination is at the end then the code may or may not be as efficient.

In either case, for the thread executing with i==up (and assuming up is not advanced, then set up to -1 as soon as possible. This will signal the other threads to exit the loop (and possibly be available for other things).

Jim Dempsey

[oleglebedev]

Good news,

I found a solution going to a job this morning ;)

[fxfortran]PROGRAM main
    implicit none
    integer :: i, from, to, new, totNew


from = 1
to = 10

5 continue
totNew = 0

!$OMP parallel PRIVATE(i, new) REDUCTION(+:totNew)
!$OMP do
  do i = from, to
    write( *, * ) 'i', i, 'to ', to
    call someMethod(i, new)
    if (new/=0) totNew = totNew + new
  end do
!$OMP end do
!$OMP end parallel

if ( totNew/=0 ) then
  from = to + 1
  to = to + totNew
  write(*, *)
  write(*,*) 'GOTO 5; totNew is ', totNew, 'from =', from, 'to =', to
  goto 5
end if


    CONTAINS


subroutine someMethod(i, new)
    implicit none
    integer, intent(IN) :: i
    integer, intent(OUT) :: new
new = 0
if (i==2) new = 10
if (i==11) new = 2
if (i==12) new = 4
if (i==25) new = 15
if (new/=0) write(*,*) ' >> new is ', new, ' on i ', i
end subroutine someMethod

END PROGRAM main
[/fxfortran]

Thanks you all for full answers. I will investigate your solutions and advice.

Best, Oleg.

[jimdempseyatthecove]

Oleg,

Try placing the REDUCTION clause on the !$OMP DO statement, there is an implicit barrier on the !$OMP END DO, thenrunning a second prallelloop with totNew

!$OMP PARALLEL PRIVATE(i,new)
!$OMP DO REDUCTION(totNew
do i=from, to
...
end do
!$OMP END DO
if(totNew /=0) then
!$OMP DO REDUCTION(totNew
do i=to+1, to+totNew
...
end do
!$OMP END DO
endif
!$OMP END PARALLEL

The above assumes (requires) 2nd instance generates no new totNew.

N.B. if you can determine the correct "to" value prior to the loop, this would be much better.


Jim Dempsey