[J3] Locality of do-variable

[Malcolm Cohen]

Hi Tobias,

Please don't use Reply-All when replying to list messages, as that means people get multiple copies.

Anyway, this is a known situation with unspecified locality, and the very reason we added specified locality later.

There are many cases that can just be handled "automatically" by unspecified locality. If you start referencing or defining variables conditionally, you move outside of the simple region into the impossible region.

So how do you parallelise this? You emit a warning message telling the user to specify the correct locality, and don't parallelise it until they do. When the compiler does not have the information needed, it cannot do it, and the user who asked you to auto-parallelise it will be grateful when you tell him which variables need some kind of locality-spec for good auto-parallelising.

I am assuming here that do are not parallelising unless the user says he wants you to do that. My colleagues using OpenMP and other such are filled with horror at the idea of the compiler destroying their carefully-load-balanced threading by generating a whole load of threads itself. At the very least, the extra threads will slow their program down because it is already using the maximum number it can for good performance, at worst it can introduce cache conflicts and dramatically slow it down.

Even when you do not have enough info to parallelise the loop, the restrictions of DO CONCURRENT should mean that some optimisation techniques may still be available, e.g. software pipelining.

Cheers,
-- 
..............Malcolm Cohen, NAG Oxford/Tokyo.

-----Original Message-----
From: Tobias Burnus <burnus at net-b.de> 
Sent: Wednesday, February 19, 2025 5:37 PM
To: General J3 interest list <j3 at mailman.j3-fortran.org>
Cc: Malcolm Cohen <malcolm at nag-j.co.jp>
Subject: Re: [J3] Locality of do-variable

Malcolm Cohen via J3 wrote:
>> This seems to be fulfilled for n <= 1, making it conforming code.
> Perhaps more notable is that the code is also conforming if n>1, as j is defined before use in every iteration.

I have to admit that I missed combining the first with the second part (", or…" of the first sentence of "a variable has unspecified locality,":

"• if it is referenced in an iteration it shall either be previously defined
    during that iteration, or shall not be defined or become undefined during
    any other iteration; if it is defined or becomes undefined by more than
    one iteration it becomes undefined when the loop terminates;"

But I have to admit that I have no idea how an implementation should handle this that wants to run the loop concurrently (e.g. multiple threads). If the the variable with unspecified locality is never defined (or becomes undefined), the compiler can just use SHARED - and as the called procedures must be pure, it should be able to see this.

But how to handle the following example as compiler:

* If k < 1: j is not defined in the loop and 'j' remains 99 such that
   foo returns 99 and all A(1:n) = 99. This can be implemented for this
   example either as SHARED or, less efficient, as LOCAL_INIT.

* If k > 1, j is defined in multiple loop iterations and it is so before
   it is referenced in the loop iteration. The value of j after the outer
   loop is undefined (foo = 42). - In this case, LOCAL (or LOCAL_INIT)
   would work.  SHARED wouldn't work as - running concurrently - multiple
   do-concurrent loop iterations modify the very same variable.

* If k == 1, it is only defined in one of the loop iteration. Thus, the
   has undefined value rule after the do-concurrent loop does not apply
   and foo = m-1. Thus, in order to handle this, the variable must be SHARED.


! Assume n > 1 for simplicity.
integer function foo(n,m, k, A)
   implicit none
   integer, value, intent(in) :: n, m, k
   integer, intent(inout) :: A(n)
   integer :: i, j

   j = 99
   do concurrent (i=1:n)  SHARED(A)
     if (i <= k .or. k < 1) then
       if (i <= k) then
         do j = 1, m-i
         end do
       end if
       A(i) = A(i) + j
     endif
   end do
   if (k <= 1) then
     foo = j
   else
     foo = 42
   endif
end

Thus, we have cases where it must be SHARED (k == 1), where it can be SHARED or LOCAL(_INIT) (k < 1), and where it must be LOCAL(_INIT) (k > 1).

NOTE that SHARED(A) is required (for k /= 1) as it is referenced inside the do-concurrent by multiple loop iterations and is not previously defined in the loop.
(Unless 'A(i) = ' does only define 'A(i)' and not 'A' as a whole, but I do not see this kind of working in the Fortran standard.)


In any case, as the example above shows, there can be a rather complex control flow - making it very hard or impossible for a compiler to statically determine how to handle variables with unspecified locality. Of course, the compiler can always decide not to run the loop concurrently - as then SHARED always works.

If the example is not complex enough, add derived types with allocatable components, volatile/asynchronous, target attribute, save, ... into the mix.


Of course, just not parallelizing works - and the user can add local/local_init/shared to make it work, but I fear that many codes will have slightly too complex access pattern for a compiler to detect this - leading presumably both to wrong code because of compiler bugs and missed parallelization opportunities, albeit diagnostics like "did not parallelize because of too complex access pattern for variable 'x', please add a locality specifier"
is a way out.

Still, the rules do not seem to be very friendly in terms of enabling concurrency for any more complex do-concurrent loop, unless default(none) is used (or would work if added).

Tobias