OpenMP and recursive subroutine

[david_sallngc_com]

I am trying to use OpenMP to speed up a subroutine that I wrote that calls a KDTREE algorithm (that I did not write). The KDTREE algorithm has a few recursive subroutines that are used for the search. My program keeps giving me errors and it is occuring inside the KDTREE code.

Is it possible to use OpenMP in a loop that calls a subroutine that, in turn, calls other subroutines that use recursion? If so, is there a particular qualifier I need to use in the !$OMP PARALLEL DO staement?

Thank you very much for your help.

Sincerely,

David

[Steven_L_Intel1]

What kind of errors?

No special qualifier is needed. In fact, if you compile with OpenMP enabled, the compiler effectively turns all your routines into recursive-capable routines. Of course, it's possible to screw this up by using SAVEd or data-initialized variables, or unsynchronized use of global variables.

[TimP]

As always with OpenMP, each iteration of the OpenMP loop would require data independence from all other iterations. Recursion would be OK only if that property is preserved.

[david_sallngc_com]

Here is a snippet of my code:

USE kdtree2_module
!DEC$ IF DEFINED (_OPENMP)
USE OMP_LIB
!DEC$ ENDIF
...
TYPE(kdtree2), POINTER :: tree
TYPE(kdtree2_result), ALLOCATABLE :: results(:)
INTEGER :: i, N, M
REAL*8, ALLOCATABLE :: ElemLoc(:,:)
...
allocate (results(M))
...
tree => kdtree2_create(ElemLoc, rearrange=.true., sort=.true.)
...
!DEC$ IF DEFINED (_OPENMP)
call OMP_set_num_threads(2)
!DEC$ ENDIF

!$OMP PARALLEL DO SCHEDULE (static) private (i, results) shared (N, tree, ElemLoc, M)
do i = 1,N
call kdtree2_n_nearest(tree, ElemLoc(:,i), M, results)
end do
!$OMP END PARALLEL DO

I compiled and ran the code in the debugger. I put a breakpoint right after the call to the subroutine containing this code. I also had a write statement after the breakpoint and it was never executed. When I ran the code, I got the following,

'foo.exe': Loaded 'c:\...\foo\Debug\foo.exe', Symbols loaded.
'foo.exe': Loaded 'c\windows\system32\ntdll.dll', No symbols loaded.
'foo.exe': Loaded 'c\windows\system32\kernel32.dll', No symbols loaded
'foo.exe': Loaded 'c\Program Files\Intel\Compiler\11.1\051\lib\ia32\libiomp5md.dll, Symbols loaded (source information stripped).
'foo.exe': Loaded 'c\windows\system32\imagehlp.dll', No symbols loaded
'foo.exe': Loaded 'c\windows\system32\msvcrt.dll', No symbols loaded
First-chance exception at 0x7c812a5b in foo.exe: 0xA1A01DB2: 0xa1a01db2.
The thread 'Win32 Thread (0x5a0) has exited ith code 0 (0x0)
The program '[3612] foo.exe: Native' has exited with code 0 (0x0).

Thanks Steve.

David

[jimdempseyatthecove]

Try moving the allocation of the private results array to inside the parallel region
...
tree => kdtree2_create(ElemLoc, rearrange=.true., sort=.true.)
...
!DEC$ IF DEFINED (_OPENMP)
call OMP_set_num_threads(2)
!DEC$ ENDIF

!$OMP PARALLEL private (i, results) shared (N, tree, ElemLoc, M)
allocate (results(M)) ! allocate the private copy of results
!$OMP DO SCHEDULE (static)
do i = 1,N
...
end do
deallocate(results)
!$OMP END PARALLEL

[david_sallngc_com]

Moving the allocation inside the OpenMP directive made the code error inside the recursive search routine within the KDTREE code. It had an undefined address for an array it was trying to aceess.

Any other suggestions? I am willing to try anything!!

Sincerely,

David

[jimdempseyatthecove]

As a diagnostic to eliminate other potential problems, using your code as-is, enclose the call to KDTREE in a critical section

!$OMP CRITICAL (KDTREE)
call KDTREE...
!$OMP END CRITICAL (KDTREE)

If the problem persists - then the problem is not inside KDTREE (look in your code).

If the problem goes away - then there is a multi-thread thread safe issue inside of KDTREE.

Do you have the source to KDTREE?

If so, then you may need to move the critical section in deeper into the KDTREE to places where you are modifying the tree structure under the assumption that assumption/requirement that it is not concurrently in the process of being modified. Places where you write/modify the tree. But this can also be a result of multiple threads using the same temporary variables (e.g. SAVE variables or COMMON or MODULE).

If you do not have the source to KDTREE, spend some time with Google searching for a thread-safe version of KDTREE.

Jim Dempsey

[katdg]

Hi David,

I realise it has been over a year since you posted this question but I wondered if you had any success using OpenMP on your KDtree? I am trying to do the same thing and am having the same problems! Any tips you could give would be great

Thanks :)

Kat.