DO CONCURRENT might be broken

[certik]

@klausler reported in #60 (comment):

DO CONCURRENT is fundamentally broken. It only guarantees to the compiler that the iterations of the loop can be run in any serial order. Its default localization rule (any variable read in an iteration will see the most recent value written in the same iteration, if any) prevents straightforward parallel execution.

Let's discuss that here. @klausler, can you work with @gklimowicz to fix that? Gary has some proposals regarding "do concurrent". Or there is no way to fix this issue.

[klausler]

See https://j3-fortran.org/doc/year/19/19-134.txt , which describes the problem and suggests a solution. The Committee "deferred" this problem and hasn't wanted to discuss it since.

[certik]

@klausler thanks a lot for submitting the proposal! Thanks also for commenting under the other issues. I am really sorry the committee didn't discuss this. Did they provide any feedback at all?

[klausler]

I received no official response.

[certik]

@klausler thank you. As a member of the committee, I apologize. This is unacceptable to me and I am trying to convince the committee that we need to consider every proposal that gets officially submitted (even if for just 5 to 10 minutes). In fact I was at the February 2019 meeting, but I don't recall what happened to your paper, as that was my first meeting and I was just trying to figure out how the committee works. Now when we have this GitHub repository, I plan to track every technical comment the committee makes in issues.

If it makes you feel any better, the committee didn't consider my proposal either (in #1). I know it happened to others too. I feel it's very inefficient, because had the committee provided feedback to you, you could have submitted a better paper for the October 2019 meeting, and so on, and we could have had this feature in a much more "ready" shape.

@sblionel, here is an example of a proposal that I suggest the committee spends 5 to 10 minutes at plenary to discuss and then I volunteer to summarize the feedback in this issue here. I still think this would be the most efficient. But I would be fine with the alternative that multiple committee members provide feedback here directly in the issue and the committee does not officially consider any such proposals until later, as that would still be an improvement and it would move us in the right direction.

[klausler]

My problem, as an implementor, is that Fortran users expect from its name that DO CONCURRENT is sufficient to guarantee to the compiler that loop iterations can be safely executed in parallel; but the standard only suffices to guarantee that the iterations can be executed in arbitrary serial order. What are my options? (1) just parallelize it anyway; (2) provide an option or directive or extension to force parallelization in the face of unresolvable localizations; (3) emit a warning about unresolvable localizations and recommend the use of OpenMP directives instead? People expect DO CONCURRENT to just mean "do concurrently", and it needs to be fixed or replaced so that it does.

[certik]

@klausler I agree. Let's discuss it further. Your proposal has an example:

SUBROUTINE FOO(N, A, B, T, K, L)
  IMPLICIT NONE
  INTEGER, INTENT(IN) :: N, K(N), L(N)
  REAL, INTENT(IN) :: A(N)
  REAL, INTENT(OUT) :: B(N)
  REAL, INTENT(INOUT) :: T(N)
  INTEGER :: J
  DO CONCURRENT (J=1:N)
    T(K(J)) = A(J)
    B(J) = T(L(J))
  END DO
END SUBROUTINE FOO

How would this be written if your proposal is accepted? Using the LOCAL specifier.

[klausler]

I should correct this case; I intend T() to be dead after the loop.

The validity of this loop depends on the values of K() and L(). Today, this loop is valid if the elements of K() are pairwise distinct from each other and from the noncorresponding elements of L() (obviously), and also in the case that K(J)==L(J) for all J. Even the extreme case of K(J)==L(J)==CONSTANT is fine.

I would restrict DO CONCURRENT to be valid only under the first condition. There's wouldn't be recourse to a LOCAL clause. If you want the compiler to automatically localize a temporary variable, it would have to be an obvious whole variable, not an array element or pointer target or anything else whose identity could not be known until execution.

[certik]

@klausler let's write down the actual examples, it's will be much easier for me (and I am sure others) to follow the arguments.

K = [1, 2, 3]
L = [4, 5, 6]

K = [1, 2, 3]
L = [1, 2, 3]

K = [1, 1, 1]
L = [1, 1, 1]

Currently 1., 2., and 3. are allowed. You are proposing for 1. and 2. to be allowed, but 3. to be forbidden (I corrected this sentence based on the comment below). Given that this depends on the values of the arrays K and L, which are only known at runtime, how would the compiler enforce it?

Isn't the idea of do concurrent that the user is responsible for ensuring that the loops are independent, which in many cases (such as this one) is impossible to do for the compiler, but quite possible for the user, since he knows his problem?

[klausler]

@klausler let's write down the actual examples, it's will be much easier for me (and I am sure others) to follow the arguments.

K = [1, 2, 3]
L = [4, 5, 6]

K = [1, 2, 3]
L = [1, 2, 3]

K = [1, 1, 1]
L = [1, 1, 1]

Currently 1., 2., and 3. are allowed. You are proposing for 1. to be allowed, but 2. and 3. to be forbidden. Given that this depends on the values of the arrays K and L, which are only known at runtime, how would the compiler enforce it?

Isn't the idea of do concurrent that the user is responsible for ensuring that the loops are independent, which in many cases (such as this one) is impossible to do for the compiler, but quite possible for the user, since he knows his problem?

No, I'm proposing only that your third case be disallowed. And I don't know what the original idea behind DO CONCURRENT was, but I think that the users and implementors that I deal with would agree with your characterization of the obligations that it places on the compiler and programmer (basically the same as an OpenMP parallel loop). The bug in DO CONCURRENT is that the compiler has to allow for your third case and make it work, either by running the code serially or detecting it and handling it dynamically.

EDIT: Your second case is fine as written; change it to K==L==[1,1,2] and it would be a better example of the condition I had in mind.

[certik]

I corrected my comment above to match what you are proposing.

Regarding your last edit K==L==[1,1,2], let's call this a case 4. Isn't case 4 the same as case 3 that should be disallowed? I am still a bit confused.

[klausler]

When all of the elements of K() are pairwise distinct, and distinct from all of the noncorresponding elements of L(), the loop is safe to parallelize.

Otherwise, and this is the problem, DO CONCURRENT also permits elements of K() to match each other, so long as K(J)==L(J). This is the problem. (The case of all elements of K() and L() being the same value is a degenerate case of this second situation.)

So K==[1,2,3],L==[4.5,6] is fine; so are K==[1,2,3],L==[1,5,6] and K==[1,2,3],L==[1,2,3].

But K=[1,1,2],L=[1,1,2] should not be; nor should K==[1,1,1],L=[1,1,1], and these are the cases that I think should be invalidated.

[certik]

Thank you. I think it is clear now which cases are allowed and which ones are not.

Let's get some feedback from other members of the committee.

@sblionel, do you know what the original idea behind do concurrent was and if what we are proposing here is aligned with it? See @klausler's previous comment: #62 (comment), and the rest of the discussion here.

If other members of the committee agree that this should be fixed, then the next step is to update the proposal. I am happy to help.

[sblionel]

This discussion puzzles me somewhat, as I don't agree with some of the assertions made. However, this is not my area of expertise and I would prefer to see opinions of committee members more versed in parallelism, such as Bill Long of Cray.

DO CONCURRENT was designed as a replacement for F95's FORALL as it was determined that FORALL's semantics made parallelism very difficult. The whole idea of DO CONCURRENT is that the iterations in any order and to any degree of parallelism, as the user promises there are no cross-iteration dependencies. There are already Fortran implementations that successfully parallelize DO CONCURRENT (Intel and probably Cray), so I don't really understand what the problem is. DO CONCURRENT was mainly modeled on OpenMP PARALLEL DO, especially with the F18 additions of locality clauses.

I see that Peter's paper got "deferred" at the February 2019 meeting and not taken up again. I'm not a good person to discuss this with.

[klausler]

I suspect that the language in what is now 11.1.7.5 para. 4 (first bullet) was intended to handle cases like:

DO CONCURRENT (J=1:N)
  TMP = ...
  ... = TMP
END DO

by requiring the processor to automatically localize the obvious temporary TMP. Unfortunately, the language is vague enough to also cover the cases that I've mentioned above where the "variable" in question can't be identified at compilation time. It doesn't make a difference if the iterations of the loop are executed in some arbitrary serial order, but it does matter when parallelizing (or failing to parallelize because of the requirement in 11.1.7.5 para. 4, first bullet).

(The specific language reads: If 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; ...)