DependencyTools misses a simple opportunity for parallelisation?

[mn416]

While working on PR #3213 I encountered the following loop that I thought DependencyTools would be able to parallelise, but was surprised to find it couldn't:

module subroutine_example
contains
  subroutine main()
    integer :: i
    real :: re_m(10)
    real :: im_m(10)
    do i = 1, 10
      call sub(re_m(i), im_m(i))
    end do
  end subroutine

  pure subroutine sub(a, b)
    real, intent(inout) :: a
    real, intent(inout) :: b
  end subroutine
end module

Here's a small PSyclone script to try to parallelise it:

from psyclone.psyir.transformations import OMPLoopTrans, TransformationError
from psyclone.psyir.nodes import Loop, Routine

def trans(psyir):
    for loop in psyir.walk(Loop):
        OMPLoopTrans(omp_directive="paralleldo").apply(loop)

@hiker may be interested in this.

[mn416]

Another slightly curious case that's cropped up during testing:

subroutine double_loop(arr)
  integer, dimension(:,:), intent(inout) :: arr
  integer :: i, j, k

  do i = 1, size(arr, 2), 1
    do j = 1, size(arr, 1), 1
        arr(j,i) = 0
    enddo
    do k = 1, size(arr, 1), 1
        arr(k,i) = arr(k,i) + 1
    enddo
  enddo
end subroutine double_loop

Here, the i loop is not parallelised by ParallelLoopTrans.

[LonelyCat124]

from psyclone.psyir.transformations import OMPLoopTrans, TransformationError
from psyclone.psyir.nodes import Loop, Routine

def trans(psyir):
for loop in psyir.walk(Loop):
OMPLoopTrans(omp_directive="paralleldo").apply(loop)

@mn416 what PSyclone version did you test with? Using exactly this I get:

module subroutine_example
  implicit none
  public

  contains
  subroutine main()
    integer :: i
    real, dimension(10) :: re_m
    real, dimension(10) :: im_m

    !$omp parallel do default(shared) private(i) schedule(auto)
    do i = 1, 10, 1
      call sub(re_m(i), im_m(i))
    enddo
    !$omp end parallel do

  end subroutine main
  pure subroutine sub(a, b)
    real, intent(inout) :: a
    real, intent(inout) :: b


  end subroutine sub

end module subroutine_example

I tested with current master

[LonelyCat124]

The second one does still fail though - this is the error I get:

psyclone.psyir.transformations.transformation_error.TransformationError: Transformation Error: Loop cannot be parallelised because:
Error: The write access to 'arr(j,i)' and the read access to 'arr(k,i)' are dependent and cannot be parallelised. Variable: 'arr'.
Consider using the "ignore_dependencies_for" transformation option if this is a false dependency
Consider using the "array_privatisation" transformation option if this is a write-write dependency

I suspect this is not so easy to solve (since j/k are modified inside the outer loop) and probably we just expect ignore_dependencies_for or force to be the solution if the outer loop needs to be parallelised over at the moment. I think this outer/inner loop behaviour we could benefit from improving in a few places, but its not so straightforward to know what the solution is? I guess we could in theory resolve that index fully (i.e. we have accesses to arr(:,i) for each value of i, but I'm not sure how this stuff works in detail at the moment).

[mn416]

Thanks @LonelyCat124. My version of PSyclone is a month old and I confirm that the first example works on master. I notice @sergisiso has made changes to DependencyTools since then, which must have fixed it. Great!

Regarding the second example, I am also not overly familiar with how DependencyTools works but I found it surprising that it can parallelise the i loop if either of the two inner loops is present, but not both. Maybe it is just a tricky case, in which case please close the issue. (The analysis in #3213 can handle it but, I imagine, it works in quite a different way.)