Chapel: allow serial iteration in forall / [ ] / reduce / promoted expressions or statements?

[vasslitvinov]

Should we allow serial iteration in forall loops - statements or expressions? How about reduce expressions and promoted expressions? Should we issue warnings in any of those cases?

Background

So far we have required that a forall statement or a forall expression invoke a parallel iterator. It is an error when a suitable parallel iterator does not exist. A reduce expression or a promoted expression, however, falls back on a serial iterator instead of issuing an error.

For example:

iter onlySerial() { ..... }

iter gotParallel() { ..... } // assume both the serial and leader/follower forms are present

forall idx in onlySerial() do ......;    // OK?
var A = [idx in onlySerial] f(idx);      // OK?

forall idx in gotParallel() do ......;  // great
var A = [idx in gotParallel] f(idx);    // great

var r1 = + reduce gotParallel();   // ok, executes in parallel
var r2 = + reduce onlySerial();    // ok, executes serially

See also

• 11793 considers a zippered forall where the second iterable does not have parallel forms.

• 5114 poses this question in the context of promotion instead of a forall. test/functions/promotion/theseShouldPromote2.future

• another example: test/functions/iterators/vass/forall-without-leaderfollower.future

This issue asks these questions:

• Should the compiler fall back on a serial iterator when a forall loop / expression does not have a suitable parallel iterator?

• Should the compiler issue a warning when falling back on a serial iterator?

• What should be the answers to the above for a promoted expression?

• How about a reduce expression?

Archaeology

Brad in #5114: "We usually think of promotion as generating data parallel execution, so there's a question in my mind as to whether a serial these() iterator should be sufficient to enable (serial) promotion or whether a parallel iterator (standalone or leader-follower) should be required." Vass responded "the answer should be the same as for a forall."

test/functions/iterators/vass/forall-without-leaderfollower.future was added in 43b9e7ad83 because Daniel Chavarria noticed that the compiler crashes in this case. Its point was "the compiler should not be crashing". #5221 changed it to say "do the same as for theseShouldPromote2.future".

Discussion

The motivation for disallowing serial iterators in foralls is to prevent a silent performance issue where a forall loop iterates serially when parallel iteration was intended.

This issue can be prevented with the "allow serial iteration" option by issuing a compiler warning when this happens.

Or, we could require the user to define leader/follower that simply redirect to the serial iterator -- perhaps with some syntactic support for that -- if the user wants to enable the use of a serial-only data structure in forall loops.

In #3158, Brad suggests that "it should generally be the data structure that warns about not being traversable in parallel rather than the reduction itself."

Proposed solution

When the forall keyword is present, it is considered an explicit requirement by the user to execute in parallel. Absence of parallel iterator(s) results in a compiler error. The forall keyword can be given in a forall statement or a forall expression. A forall expression written with the forall keyword cannot be iterated over in a for-loop.

In the absence of a forall keyword, it is OK to fall back on serial iteration if parallel iterators are not available. No warning is to be issued. This applies to forall statements and forall expressions written using the square bracket notation.

Reduce expressions and promoted expressions do not have a forall keyword. Therefore they allow fall back on serial execution. (This addresses part of #5114.) As an exception, if an argument of a reduce or promoted expression has a forall expression written using the forall keyword, it must be computed in parallel.

| Syntactic construct | Allow fall back on serial iteration? |
| :-- | :-- |
| forall .... do .... | no |
| [ .... ] .... | yes |
| .... reduce .... | yes, with the above exception |
| a promoted expression | yes, with the above exception |

Developer note

See if we can remove reqSerial in lowerPrimReduce().

[mppf]

I'm happy with forall i in someSerialIterator() to raise an error but I'm less certain what reduce or forall expressions should do.

[benharsh]

I generally lean towards allowing the compiler to fall back on the serial iterator, but feel that's not applicable in all of these situations. I think it's annoying that I need to go depth-first when writing an iterator (need serial + parallel) if I want to use certain loop expressions. I'd much rather write a quick serial iterator and get some compiler warnings so that I can make progress on other areas of the program.

I think it would make sense to only resolve the serial or parallel iterator when the for or forall keywords are explicitly used.

I think it's fine for reduce-expressions to choose either iterator, and would like a compiler warning if the parallel iterator could not be resolved. But I'd only want the compiler warning if it looked like there was any possible candidate for the parallel iterator. In other words, don't warn me if I only ever wrote a serial iterator, but do warn me if I wrote something that looks like a parallel iterator (e.g. has an iterKind formal).

Could the square-bracket form be used as a way to express that either the serial or parallel iterator is acceptable?

[bradcray]

I think @benharsh's proposal to distinguish between "stmts/exprs where forall is used" vs. "those that iterate implicitly" is an interesting one. That resonates nicely with me. "I said forall so invoke the parallel iterator" vs. "I used a form that should default to parallel, but could fall back to serial without any loss of correctness." This would also strengthen the case for supporting both forall expressions and square-bracket style loop expressions (which I want to do, but sometimes have trouble convincing others of my reasons).

[vasslitvinov]

+1 to Ben's proposal.

[bharsh]

Ah, I think you guys have tagged the wrong bharsh...

On Fri, Dec 7, 2018, 1:29 PM Brad Chamberlain <[email protected]
wrote:

I think @bharsh https://github.com/bharsh's proposal to distinguish
between "stmts/exprs where forall is used" vs. "those that iterate
implicitly" is an interesting one. That resonates nicely with me. "I said
forall so invoke the parallel iterator" vs. "I used a form that should
default to parallel, but could fall back to serial without any loss of
correctness." This would also strengthen the case for supporting both
forall expressions and square-bracket style loop expressions (which I want
to do, but sometimes have trouble convincing others of my reasons).

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/chapel-lang/chapel/issues/11819#issuecomment-445322768,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAaVyYLbYiksILdZxgzaLmjBKg4fZqTPks5u2rOPgaJpZM4ZHrfX
.

[bradcray]

Oops, sorry about that Brent!

[vasslitvinov]

How can we extend the "forall vs. brackets" rule to promoted expressions #5114 ?

We can apply whatever approach we use there (for allowing/disallowing the fall-back to the serial iterator) to reduce expressions.

[bradcray]

It seems to me that the rule suggests that since promoted expressions don't have the forall keyword, they would try to use parallel and fall back to serial if that wasn't possible.

[vasslitvinov]

I updated the main text of this issue with the current solution proposal.

[bradcray]

As an exception, if an argument of a reduce or promoted expression has a forall expression written using the forall keyword, it must be computed in parallel.

If I'm understanding this correctly, I don't think of it as an exception because I think if we write + reduce (forall i in I do i) or foo(forall j in J do j) then (1) I and J must support parallel iterators by the first rule in the proposed solution above; and (2) the iterator expression that the compiler introduces to represent the forall loop would presumably necessarily support parallel iteration (and perhaps _only_ support parallel iteration?). Therefore since reductions and promotions prefer parallel iteration anyway given the choice (rule 2 of the proposed solution), there's no reason to think it wouldn't be computed in parallel (?).

[vasslitvinov]

In #3158, Brad suggests that "it should generally be the data structure that warns about not being traversable in parallel rather than the reduction itself."

This supports the current proposal.

[bradcray]

Hi @vasslitvinov — Being excited about the decision we made / are making here, I started to make a change that takes advantage of it today, before realizing that it isn't on master yet. Is it part of the branch you're currently working on, or will it require a separate / additional effort? Thanks.

[vasslitvinov]

@bradcray - I am excited about it too. It is not part of my branch, I was planning to do it after merging the branch.

[vasslitvinov]

This issue was closed to signify the implementation of the proposed design for forall statements and reduce and promoted expressions. Reopening it pending satisfactory implementation for forall expressions, see #12312.

[vasslitvinov]

I am happy to close this issue now. Unresolved issues now have their own GitHub #s.